LIVIVO - Search results -

Search results

Result 1 - 10 of total 55

Search options

Book ; Online: Secure Distributed Optimization Under Gradient Attacks

Yu, Shuhua / Kar, Soummya

2022

Abstract: In this paper, we study secure distributed optimization against arbitrary gradient attack in multi-agent networks. In distributed optimization, there is no central server to coordinate local updates, and each agent can only communicate with its neighbors ...

Abstract	In this paper, we study secure distributed optimization against arbitrary gradient attack in multi-agent networks. In distributed optimization, there is no central server to coordinate local updates, and each agent can only communicate with its neighbors on a predefined network. We consider the scenario where out of $n$ networked agents, a fixed but unknown fraction $\rho$ of the agents are under arbitrary gradient attack in that their stochastic gradient oracles return arbitrary information to derail the optimization process, and the goal is to minimize the sum of local objective functions on unattacked agents. We propose a distributed stochastic gradient method that combines local variance reduction and clipping (CLIP-VRG). We show that, in a connected network, when unattacked local objective functions are convex and smooth, share a common minimizer, and their sum is strongly convex, CLIP-VRG leads to almost sure convergence of the iterates to the exact sum cost minimizer at all agents. We quantify a tight upper bound of the fraction $\rho$ of attacked agents in terms of problem parameters such as the condition number of the associated sum cost that guarantee exact convergence of CLIP-VRG, and characterize its asymptotic convergence rate. Finally, we empirically demonstrate the effectiveness of the proposed method under gradient attacks in both synthetic dataset and image classification datasets. Comment: 33 pages, 8 figures
Keywords	Mathematics - Optimization and Control ; Computer Science - Distributed ; Parallel ; and Cluster Computing ; Computer Science - Multiagent Systems
Subject code	510
Publishing date	2022-10-27
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Corrected

Fiscko, Carmel / Kar, Soummya / Sinopoli, Bruno

On Confident Policy Evaluation for Factored Markov Decision Processes with Node Dropouts

2023

Abstract: In this work we investigate an importance sampling approach for evaluating policies for a structurally time-varying factored Markov decision process (MDP), i.e. the policy's value is estimated with a high-probability confidence interval. In particular, ... ...

Abstract	In this work we investigate an importance sampling approach for evaluating policies for a structurally time-varying factored Markov decision process (MDP), i.e. the policy's value is estimated with a high-probability confidence interval. In particular, we begin with a multi-agent MDP controlled by a known policy but with unknown transition dynamics. One agent is then removed from the system - i.e. the system experiences node dropout - forming a new MDP of the remaining agents, with a new state space, action space, and new transition dynamics. We assume that the effect of removing an agent corresponds to the marginalization of its factor in the transition dynamics. The reward function may likewise be marginalized, or it may be entirely redefined for the new system. Robust policy importance sampling is then used to evaluate candidate policies for the new system, and estimated values are presented with probabilistic confidence bounds. This computation is completed with no observations of the new system, meaning that a safe policy may be found before dropout occurs. The utility of this approach is demonstrated in simulation and compared to Monte Carlo simulation of the new system. Comment: 7 pages, 2 figures
Keywords	Electrical Engineering and Systems Science - Systems and Control
Subject code	006
Publishing date	2023-02-04
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Model-Free Learning and Optimal Policy Design in Multi-Agent MDPs Under Probabilistic Agent Dropout

Fiscko, Carmel / Kar, Soummya / Sinopoli, Bruno

2023

Abstract: This work studies a multi-agent Markov decision process (MDP) that can undergo agent dropout and the computation of policies for the post-dropout system based on control and sampling of the pre-dropout system. The controller's objective is to find an ... ...

Abstract	This work studies a multi-agent Markov decision process (MDP) that can undergo agent dropout and the computation of policies for the post-dropout system based on control and sampling of the pre-dropout system. The controller's objective is to find an optimal policy that maximizes the value of the expected system given a priori knowledge of the agents' dropout probabilities. Finding an optimal policy for any specific dropout realization is a special case of this problem. For MDPs with a certain transition independence and reward separability structure, we assume that removing agents from the system forms a new MDP comprised of the remaining agents with new state and action spaces, transition dynamics that marginalize the removed agents, and rewards that are independent of the removed agents. We first show that under these assumptions, the value of the expected post-dropout system can be represented by a single MDP; this "robust MDP" eliminates the need to evaluate all $2^N$ realizations of the system, where $N$ denotes the number of agents. More significantly, in a model-free context, it is shown that the robust MDP value can be estimated with samples generated by the pre-dropout system, meaning that robust policies can be found before dropout occurs. This fact is used to propose a policy importance sampling (IS) routine that performs policy evaluation for dropout scenarios while controlling the existing system with good pre-dropout policies. The policy IS routine produces value estimates for both the robust MDP and specific post-dropout system realizations and is justified with exponential confidence bounds. Finally, the utility of this approach is verified in simulation, showing how structural properties of agent dropout can help a controller find good post-dropout policies before dropout occurs. Comment: 22 pages, 4 figures
Keywords	Electrical Engineering and Systems Science - Systems and Control ; Computer Science - Artificial Intelligence ; Computer Science - Machine Learning
Subject code	006
Publishing date	2023-04-24
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: On the Accuracy of Deterministic Models for Viral Spread on Networks

Sridhar, Anirudh / Kar, Soummya

2021

Abstract: We consider the emergent behavior of viral spread when agents in a large population interact with each other over a contact network. When the number of agents is large and the contact network is a complete graph, it is well known that the population ... ...

Abstract	We consider the emergent behavior of viral spread when agents in a large population interact with each other over a contact network. When the number of agents is large and the contact network is a complete graph, it is well known that the population behavior -- that is, the fraction of susceptible, infected and recovered agents -- converges to the solution of an ordinary differential equation (ODE) known as the classical SIR model as the population size approaches infinity. In contrast, we study interactions over contact networks with generic topologies and derive conditions under which the population behavior concentrates around either the classic SIR model or other deterministic models. Specifically, we show that when most vertex degrees in the contact network are sufficiently large, the population behavior concentrates around an ODE known as the network SIR model. We then study the short and intermediate-term evolution of the network SIR model and show that if the contact network has an expander-type property or the initial set of infections is well-mixed in the population, the network SIR model reduces to the classical SIR model. To complement these results, we illustrate through simulations that the two models can yield drastically different predictions, hence use of the classical SIR model can be misleading in certain cases. Comment: 8 pages, 4 figures
Keywords	Physics - Physics and Society ; Computer Science - Multiagent Systems ; Computer Science - Social and Information Networks ; Electrical Engineering and Systems Science - Systems and Control ; Mathematics - Probability
Subject code	612
Publishing date	2021-04-11
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Mean-field Approximations for Stochastic Population Processes with Heterogeneous Interactions

Sridhar, Anirudh / Kar, Soummya

2021

Abstract: This paper studies a general class of stochastic population processes in which agents interact with one another over a network. Agents update their behaviors in a random and decentralized manner according to a policy that depends only on the agent's ... ...

Abstract	This paper studies a general class of stochastic population processes in which agents interact with one another over a network. Agents update their behaviors in a random and decentralized manner according to a policy that depends only on the agent's current state and an estimate of the macroscopic population state, given by a weighted average of the neighboring states. When the number of agents is large and the network is a complete graph (has all-to-all information access), the macroscopic behavior of the population can be well-approximated by a set of deterministic differential equations called a {\it mean-field approximation}. For incomplete networks such characterizations remained previously unclear, i.e., in general whether a suitable mean-field approximation exists for the macroscopic behavior of the population. The paper addresses this gap by establishing a generic theory describing when various mean-field approximations are accurate for \emph{arbitrary} interaction structures. Our results are threefold. Letting $W$ be the matrix describing agent interactions, we first show that a simple mean-field approximation that incorrectly assumes a homogeneous interaction structure is accurate provided $W$ has a large spectral gap. Second, we show that a more complex mean-field approximation which takes into account agent interactions is accurate as long as the Frobenius norm of $W$ is small. Finally, we compare the predictions of the two mean-field approximations through simulations, highlighting cases where using mean-field approximations that assume a homogeneous interaction structure can lead to inaccurate qualitative and quantitative predictions. Comment: 25 pages, 1 figure. New version contains shorter and more streamlined proofs
Keywords	Mathematics - Probability ; Computer Science - Multiagent Systems ; Computer Science - Social and Information Networks
Subject code	612
Publishing date	2021-01-23
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: An Equivalent Circuit Workflow for Unconstrained Optimization

Agarwal, Aayushya / Fiscko, Carmel / Kar, Soummya / Pileggi, Larry / Sinopoli, Bruno

2023

Abstract: We introduce a new workflow for unconstrained optimization whereby objective functions are mapped onto a physical domain to more easily design algorithms that are robust to hyperparameters and achieve fast convergence rates. Specifically, we represent ... ...

Abstract	We introduce a new workflow for unconstrained optimization whereby objective functions are mapped onto a physical domain to more easily design algorithms that are robust to hyperparameters and achieve fast convergence rates. Specifically, we represent optimization problems as an equivalent circuit that are then solved solely as nonlinear circuits using robust solution methods. The equivalent circuit models the trajectory of component-wise scaled gradient flow problem as the transient response of the circuit for which the steady-state coincides with a critical point of the objective function. The equivalent circuit model leverages circuit domain knowledge to methodically design new optimization algorithms that would likely not be developed without a physical model. We incorporate circuit knowledge into optimization methods by 1) enhancing the underlying circuit model for fast numerical analysis, 2) controlling the optimization trajectory by designing the nonlinear circuit components, and 3) solving for step sizes using well-known methods from the circuit simulation. We first establish the necessary conditions that the controls must fulfill for convergence. We show that existing descent algorithms can be re-derived as special cases of this approach and derive new optimization algorithms that are developed with insights from a circuit-based model. The new algorithms can be designed to be robust to hyperparameters, achieve convergence rates comparable or faster than state of the art methods, and are applicable to optimizing a variety of both convex and nonconvex problems.
Keywords	Mathematics - Optimization and Control ; Electrical Engineering and Systems Science - Systems and Control
Subject code	510
Publishing date	2023-05-23
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Cluster-Based Control of Transition-Independent MDPs

Fiscko, Carmel / Kar, Soummya / Sinopoli, Bruno

2022

Abstract: This work studies efficient solution methods for cluster-based control policies of transition-independent Markov decision processes (TI-MDPs). We focus on control of multi-agent systems, whereby a central planner (CP) influences agents to select ... ...

Abstract	This work studies efficient solution methods for cluster-based control policies of transition-independent Markov decision processes (TI-MDPs). We focus on control of multi-agent systems, whereby a central planner (CP) influences agents to select desirable group behavior. The agents are partitioned into disjoint clusters whereby agents in the same cluster receive the same controls but agents in different clusters may receive different controls. Under mild assumptions, this process can be modeled as a TI-MDP where each factor describes the behavior of one cluster. The action space of the TI-MDP becomes exponential with respect to the number of clusters. To efficiently find a policy in this rapidly scaling space, we propose a clustered Bellman operator that optimizes over the action space for one cluster at any evaluation. We present Clustered Value Iteration (CVI), which uses this operator to iteratively perform "round robin" optimization across the clusters. CVI converges exponentially faster than standard value iteration (VI), and can find policies that closely approximate the MDP's true optimal value. A special class of TI-MDPs with separable reward functions are investigated, and it is shown that CVI will find optimal policies on this class of problems. Finally, the optimal clustering assignment problem is explored. The value functions TI-MDPs with submodular reward functions are shown to be submodular functions, so submodular set optimization may be used to find a near optimal clustering assignment. We propose an iterative greedy cluster splitting algorithm, which yields monotonic submodular improvement in value at each iteration. Finally, simulations offer empirical assessment of the proposed methods. Comment: 21 pages, 4 figures
Keywords	Electrical Engineering and Systems Science - Systems and Control ; Computer Science - Multiagent Systems
Subject code	006
Publishing date	2022-07-11
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Nonlinear consensus+innovations under correlated heavy-tailed noises

Vukovic, Manojlo / Jakovetic, Dusan / Bajovic, Dragana / Kar, Soummya

Mean square convergence rate and asymptotics

2022

Abstract: We consider distributed recursive estimation of consensus+innovations type in the presence of heavy-tailed sensing and communication noises. We allow that the sensing and communication noises are mutually correlated while independent identically ... ...

Abstract	We consider distributed recursive estimation of consensus+innovations type in the presence of heavy-tailed sensing and communication noises. We allow that the sensing and communication noises are mutually correlated while independent identically distributed (i.i.d.) in time, and that they may both have infinite moments of order higher than one (hence having infinite variances). Such heavy-tailed, infinite-variance noises are highly relevant in practice and are shown to occur, e.g., in dense internet of things (IoT) deployments. We develop a consensus+innovations distributed estimator that employs a general nonlinearity in both consensus and innovations steps to combat the noise. We establish the estimator's almost sure convergence, asymptotic normality, and mean squared error (MSE) convergence. Moreover, we establish and explicitly quantify for the estimator a sublinear MSE convergence rate. We then quantify through analytical examples the effects of the nonlinearity choices and the noises correlation on the system performance. Finally, numerical examples corroborate our findings and verify that the proposed method works in the simultaneous heavy-tail communication-sensing noise setting, while existing methods fail under the same noise conditions.
Keywords	Mathematics - Optimization and Control ; Computer Science - Information Theory ; 93E10 ; 93E35 ; 60G35 ; 94A13 ; 62M05
Subject code	519
Publishing date	2022-12-22
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments

Armacki, Aleksandar / Bajovic, Dragana / Jakovetic, Dusan / Kar, Soummya

2022

Abstract: The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments in which users obtain data from one of $K$ different distributions. In the proposed setup, the grouping of users (based on the data ... ...

Abstract	The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments in which users obtain data from one of $K$ different distributions. In the proposed setup, the grouping of users (based on the data distributions they sample), as well as the underlying statistical properties of the distributions, are apriori unknown. A family of One-shot Distributed Clustered Learning methods (ODCL-$\mathcal{C}$) is proposed, parametrized by the set of admissible clustering algorithms $\mathcal{C}$, with the objective of learning the true model at each user. The admissible clustering methods include $K$-means (KM) and convex clustering (CC), giving rise to various one-shot methods within the proposed family, such as ODCL-KM and ODCL-CC. The proposed one-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. In particular, for strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error (MSE) rates in terms of the sample size. An explicit characterization of the threshold is provided in terms of problem parameters. The trade-offs with respect to selecting various clustering methods (ODCL-CC, ODCL-KM) are discussed and significant improvements over state-of-the-art are demonstrated. Numerical experiments illustrate the findings and corroborate the performance of the proposed methods.
Keywords	Computer Science - Machine Learning
Subject code	006
Publishing date	2022-09-22
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

Book ; Online: Large deviations rates for stochastic gradient descent with strongly convex functions

Bajovic, Dragana / Jakovetic, Dusan / Kar, Soummya

2022

Abstract: Recent works have shown that high probability metrics with stochastic gradient descent (SGD) exhibit informativeness and in some cases advantage over the commonly adopted mean-square error-based ones. In this work we provide a formal framework for the ... ...

Abstract	Recent works have shown that high probability metrics with stochastic gradient descent (SGD) exhibit informativeness and in some cases advantage over the commonly adopted mean-square error-based ones. In this work we provide a formal framework for the study of general high probability bounds with SGD, based on the theory of large deviations. The framework allows for a generic (not-necessarily bounded) gradient noise satisfying mild technical assumptions, allowing for the dependence of the noise distribution on the current iterate. Under the preceding assumptions, we find an upper large deviations bound for SGD with strongly convex functions. The corresponding rate function captures analytical dependence on the noise distribution and other problem parameters. This is in contrast with conventional mean-square error analysis that captures only the noise dependence through the variance and does not capture the effect of higher order moments nor interplay between the noise geometry and the shape of the cost function. We also derive exact large deviation rates for the case when the objective function is quadratic and show that the obtained function matches the one from the general upper bound hence showing the tightness of the general upper bound. Numerical examples illustrate and corroborate theoretical findings. Comment: 32 pages, 2 figures
Keywords	Computer Science - Machine Learning ; Computer Science - Information Theory ; Mathematics - Optimization and Control ; Statistics - Machine Learning
Subject code	519
Publishing date	2022-11-02
Publishing country	us
Document type	Book ; Online
Database	BASE - Bielefeld Academic Search Engine (life sciences selection)

Full text online

Full text

Inter-library loan at ZB MED

Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.

To top

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED

Full text online

More links

Kategorien

Inter-library loan at ZB MED