Distributed Online Optimization in Dynamic Environments Using Mirror Descent
From MaRDI portal
Abstract: This work addresses decentralized online optimization in non-stationary environments. A network of agents aim to track the minimizer of a global time-varying convex function. The minimizer evolves according to a known dynamics corrupted by an unknown, unstructured noise. At each time, the global function can be cast as a sum of a finite number of local functions, each of which is assigned to one agent in the network. Moreover, the local functions become available to agents sequentially, and agents do not have a prior knowledge of the future cost functions. Therefore, agents must communicate with each other to build an online approximation of the global function. We propose a decentralized variation of the celebrated Mirror Descent, developed by Nemirovksi and Yudin. Using the notion of Bregman divergence in lieu of Euclidean distance for projection, Mirror Descent has been shown to be a powerful tool in large-scale optimization. Our algorithm builds on Mirror Descent, while ensuring that agents perform a consensus step to follow the global function and take into account the dynamics of the global minimizer. To measure the performance of the proposed online algorithm, we compare it to its offline counterpart, where the global functions are available a priori. The gap between the two is called dynamic regret. We establish a regret bound that scales inversely in the spectral gap of the network, and more notably it represents the deviation of minimizer sequence with respect to the given dynamics. We then show that our results subsume a number of results in distributed optimization. We demonstrate the application of our method to decentralized tracking of dynamic parameters and verify the results via numerical experiments.
Cited in
(54)- A privacy-masking learning algorithm for online distributed optimization over time-varying unbalanced digraphs
- On stochastic mirror descent with interacting particles: convergence properties and variance reduction
- Distributed online bandit optimization under random quantization
- A unitary distributed subgradient method for multi-agent optimization with different coupling sources
- Personalized optimization with user's feedback
- Event-triggered distributed online convex optimization with delayed bandit feedback
- Projection-free decentralized online learning for submodular maximization over time-varying networks
- Online Distributed Optimization With Strongly Pseudoconvex-Sum Cost Functions
- Analysis of Online Composite Mirror Descent Algorithm
- Adaptive online distributed optimization in dynamic environments
- Distributed mirror descent algorithm over unbalanced digraphs based on gradient weighting technique
- Online distributed detection of sensor networks with delayed information
- Dynamic online convex optimization with long-term constraints via virtual queue
- Differentially private distributed online learning over time‐varying digraphs via dual averaging
- Distributed continuous‐time constrained convex optimization with general time‐varying cost functions
- Online distributed optimization with strongly pseudoconvex-sum cost functions and coupled inequality constraints
- Distributed online convex optimization with multiple coupled constraints: a double accelerated push-pull algorithm
- Online distributed dual averaging algorithm for multi-agent bandit optimization over time-varying general directed networks
- Distributed dynamic online learning with differential privacy via path-length measurement
- Distributed online optimisation in unknown dynamic environment
- Distributed inertial online game algorithm for tracking generalized Nash equilibria
- Online composite optimization with time-varying regularizers
- Online convex optimization using coordinate descent algorithms
- Distributed adaptive online learning for convex optimization with weight decay
- An accelerated distributed online gradient push-sum algorithm on time-varying directed networks
- Distributed second-order multi-agent constrained optimization algorithm with time-varying cost function
- Gradient-free algorithms for distributed online convex optimization
- Privacy-preserving distributed projected one-point bandit online optimization over directed graphs
- Stochastic mirror descent for convex optimization with consensus constraints
- Distributed online optimization subject to long-term constraints and time-varying topology: an event-triggered and bandit feedback approach
- Random gradient-free method for online distributed optimization with strongly pseudoconvex cost functions
- Online distributed nonconvex optimization with stochastic objective functions: high probability bound analysis of dynamic regrets
- Online distributed optimization with stochastic gradients: high probability bound of regrets
- Distributed online constrained convex optimization with event-triggered communication
- Distributed online stochastic gradient tracking
- Distributed online adaptive algorithm with quantized communication
- Distributed zeroth-order online optimization with communication delays
- Online distributed algorithms for mixed equilibrium problems in dynamic environments
- High probability convergence of distributed clipped stochastic gradient descent with heavy-tailed noise
- One-point residual feedback algorithms for distributed online convex and non-convex optimization
- Online distributed optimization with clipped stochastic gradients: high probability bound of regrets
- Online distributed optimization algorithm with dynamic regret analysis under unbalanced graphs
- Distributed mirror descent for online bandit saddle point problem
- Gradient-free distributed online optimization in networks
- Broadcast-based asynchronous convex optimization using quantized distributed stochastic mirror descent algorithm
- Privacy-preserving distributed online mirror descent for nonconvex optimization
- Distributed online path-length-independent algorithm for noncooperative games over unbalanced digraphs
- Cooperative online learning: keeping your neighbors updated
- Distributed online optimization with edge-based event-triggered communication
- Distributed online learning for joint regret with communication constraints
- Gradient-free algorithms based on weight-balancing for online distributed optimisation
- One-point residual feedback gradient tracking algorithm for distributed online optimization with gradient noises
- Forgetting-factor regrets for distributed second-order online optimisation
- Distributed online optimization with switching costs
This page was built for publication: Distributed Online Optimization in Dynamic Environments Using Mirror Descent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4567122)
