PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Online Optimization in Dynamic Environments Using Mirror Descent

Shahin Shahrampour, Ali Jadbabaie

arXiv:1609.02845v1math.OCcs.DCcs.LGstat.ML

TL;DR

The paper addresses decentralized online optimization when agents face sequentially revealed, time-varying local costs and a minimizer evolving under known dynamics with unknown unstructured noise. It develops a decentralized Mirror Descent method with dynamics and consensus updates, and analyzes it through dynamic regret. The resulting bound depends on network spectral gap and minimizer deviation from the dynamics, while extending prior decentralized optimization results and supporting noisy-gradient and dynamic-parameter tracking settings.

  • Problem

    Agents must track the minimizer of a global time-varying convex function despite private, sequentially revealed local costs and no knowledge of future functions.

  • Method

    The paper decentralizes Mirror Descent by combining local Bregman-divergence updates with dynamics-aware minimizer updates and neighborhood consensus.

  • Results

    The dynamic-regret bound scales inversely with network spectral gap and captures minimizer deviation from the prescribed dynamics, with an expectation guarantee for noisy local gradients.

  • Takeaways & Limitations

    The framework subsumes decentralized optimization of time-invariant objectives and time-varying objectives over fixed variables, and applies to dynamic-parameter tracking.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper develops decentralized online optimization for time-varying objectives and variables, where agents receive private local functions sequentially and track a dynamically evolving minimizer. It proposes a dynamic Mirror Descent framework whose regret captures both network effects and deviation from the assumed minimizer dynamics.

  • Evaluation criterion: Dynamic regret measures the online decentralized method against an offline centralized benchmark that knows the global functions in advance.The benchmark tracks the time-varying minimizer, making the comparison stricter than static regret.
  • Method: The proposed decentralized Mirror Descent interleaves local gradient updates, dynamics-aware prediction, and neighborhood consensus using Bregman divergence for the projection step.This combines optimization, minimizer dynamics, and agent interaction in one online procedure.
  • Results: The regret bound scales inversely with the network spectral gap and captures minimizer deviation from the prescribed dynamics, while recovering static and centralized dynamic optimization rates in special cases.The theoretical analysis separates tracking error from decentralization cost.
  • Results: The framework also covers noisy local gradients in expectation and applies to decentralized tracking of dynamic parameters, whose empirical quality depends on adherence to the given dynamics.Euclidean distance is used as the Bregman divergence in the tracking application.
  • Problem setting: Time-varying decentralized optimization requires agents to handle sequentially revealed local costs while lacking access to the global objective and future functions.The global function is formed from local convex functions held privately by network agents.
  • Problem setting: The paper studies simultaneous evolution of objective functions and comparator variables, extending beyond time-invariant objectives or changing objectives over fixed variables.The dynamic formulation tracks minimizers that evolve according to a known dynamics with possible unknown, unstructured noise.

B. Decentralized Online Mirror Descent

The decentralized online mirror descent method combines Bregman-divergence updates with minimizer dynamics and neighborhood consensus. Its design relies on convexity, Lipschitz, stochastic-matrix, and non-expansive-mapping assumptions.

  • B. Decentralized Online Mirror Descent: Bregman divergence generalizes Euclidean projection in Mirror Descent, with Euclidean and KL divergence as important examples.Euclidean distance reduces Mirror Descent to Gradient Descent, while KL divergence is another standard choice.
  • B. Decentralized Online Mirror Descent: The method assumes a 1-strongly convex regularizer and initializes estimates at a common point, although arbitrary initialization can work.The regularizer is defined on a convex set in a Banach space; the initialization convention simplifies analysis.
  • B. Decentralized Online Mirror Descent: The Bregman divergence is assumed separately convex and Lipschitz, conditions satisfied by Euclidean distance and, under suitable restrictions, KL divergence.For KL divergence, mixing a uniform distribution can avoid the boundary and yield a constant K of O(log T).
  • B. Decentralized Online Mirror Descent: The algorithm uses local gradients, dynamics of the minimizer sequence, and neighborhood averaging in three interleaved updates.The gradient step stays close to previous estimates through Bregman divergence; subsequent steps predict dynamics and perform consensus.
  • B. Decentralized Online Mirror Descent: The dynamics mapping A is non-expansive, preventing one-step prediction errors from being amplified over time.The assumption includes ∥A∥≤1 and constrains the mapping on the feasible set.

III. THEORETICAL RESULTS

The theoretical results bound dynamic regret by separating tracking error from decentralization cost. Removing either component recovers established rates for static decentralized or centralized dynamic optimization.

  • III. THEORETICAL RESULTS: The main theorem bounds dynamic regret using minimizer-trajectory deviation from dynamics A and network-induced decentralization error.The result is presented as a generalization covering dynamic objectives and dynamic variables.
  • III. THEORETICAL RESULTS: Factoring out tracking error recovers prior rates for decentralized optimization with static objectives.
  • III. THEORETICAL RESULTS: Factoring out network error recovers prior rates for centralized online optimization with dynamic objectives.

A. Preliminary Results

The preliminary analysis separates network disagreement from tracking mismatch and identifies the parameters governing dynamic regret. These bounds account for network mixing, step sizes, dynamics, and mismatch noise.

  • A. Preliminary Results: The local-estimate convergence lemma extends time-invariant decentralized analysis to online optimization with dynamics A.It bounds each local estimate's deviation from the consensual value.
  • A. Preliminary Results: The algorithm is initialized at a common point for analytical convenience, while arbitrary initialization is also permitted.
  • A. Preliminary Results: The network-error bound depends on the mixing parameter σ2(W) and the step-size sequence.The analysis assumes Lipschitz local functions, doubly stochastic W, and non-expansive A.
  • A. Preliminary Results: σ2(W) = 0 for complete communication, yielding the most rapid mixing, while diminishing step sizes provide asymptotic closeness but suit static environments better.
  • A. Preliminary Results: The tracking-error lemma bounds the Bregman discrepancy between the intermediate update and the dynamic minimizer under regularity assumptions.The bound uses separate convexity, a Lipschitz Bregman condition, doubly stochastic W, and non-expansive A.
  • A. Preliminary Results: The mismatch-noise term ∥v_t∥ directly appears in the tracking bound, highlighting its impact on tracking quality.Together, the network and tracking lemmas identify the critical parameters entering the regret bound.

B. Finite-horizon Performance: Regret Bound

The paper establishes a finite-horizon dynamic-regret bound for decentralized online Mirror Descent, decomposing performance into tracking and network effects. The bound depends on network connectivity and mismatch between the minimizer sequence and its dynamics, while recovering several distributed-optimization results in special cases.

  • Regret bound: The main theorem gives a non-asymptotic dynamic-regret upper bound decomposed into tracking and network errors.It applies under convexity, Lipschitz, doubly stochastic, Bregman-divergence, and non-expansive-mapping assumptions.
  • Regret bound: The regret bound scales inversely with the network spectral gap and reflects deviations of the minimizer sequence from its prescribed dynamics.The theorem characterizes how network and dynamical mismatch contribute to finite-horizon performance.
  • Regret bound: The fixed-step-size corollary isolates CT, which collects mismatch errors between the minimizer sequence and dynamics A.The mismatch errors need not be Gaussian or follow a statistical distribution.
  • Special cases: When the objective is time-invariant, the result recovers rates for distributed dual averaging using η = (1 − σ2(W))/T.The dynamic term vanishes when the minimizer is fixed and A = Id.
  • Special cases: For time-varying objectives with fixed comparators, the result recovers distributed online dual averaging; for complete graphs, it recovers centralized online-learning results.In the complete-graph case, σ2(W) = 0 and the network term vanishes.
  • Limitations: If mismatch errors fluctuate drastically, CT can become linear in time, making the corollary unable to guarantee sub-linear dynamic regret.The paper notes that multiple gradient queries could reduce this error, but that direction is outside its scope.

C. Optimization with Stochastic Gradients

The paper extends its decentralized online Mirror Descent analysis to noisy local gradients. Under the stated stochastic-oracle assumptions, the deterministic regret result continues to hold in expectation, supporting use in noisy dynamic environments.

  • Stochastic-gradient guarantee: The stochastic-gradient result shows that Theorem 3 remains valid in expectation when agents observe noisy local gradients.The stochastic oracle is defined relative to information available before the next round.
  • Stochastic-gradient updates: The stochastic updates differ from the deterministic updates by replacing the exact local gradient with a stochastic gradient.A common satisfying model is additive zero-mean noise with bounded variance.
  • Assumptions: The guarantee assumes a convex domain, a 1-strongly convex regularizer, Lipschitz local functions, a doubly stochastic mixing matrix, and a non-expansive dynamics mapping.The Bregman divergence must also satisfy Lipschitz and separate-convexity assumptions.

IV. NUMERICAL EXPERIMENT: STATE ESTIMATION AND TRACKING DYNAMIC PARAMETERS

The numerical study applies the framework to decentralized tracking of a moving target using a 25-agent sensor network and Euclidean Mirror Descent. The experiments examine noisy observations, dynamic-model mismatch, and estimator tracking of the target trajectory.

  • Algorithm instantiation: The Euclidean distance is used as the Bregman divergence, yielding an explicit tracking update based on local square losses.The online formulation gives agents one newly available signal per iteration.
  • Model distinctions: The framework does not require Gaussian system noise, a statistical noise distribution, or multiple samples per iteration.The analysis permits deterministic unknown-structure noise and stochastic noise with temporal dependence, whereas the experiment fixes one generated noise sequence per run.
  • Experimental setup: The experiment uses 25 agents on a 5 × 5 grid to collaboratively track a moving target whose state has four position and velocity components.The target follows a near-constant-velocity model with independently evolving position components.
  • Experimental setup: Each agent observes one noisy coordinate per iteration, while the whole network can globally identify the target.Agents are divided into four groups, each observing one state coordinate, with zero-mean finite-variance uniform noise on [−1, 1].
  • Dynamic-regret results: Lower system-noise variance produces lower normalized dynamic regret, while larger variance produces worse performance.The experiment averages dynamic regret over 50 runs and uses a fixed step size η = 0.5.
  • Tracking interpretation: The dynamic-regret bound is equivalent to a bound on collective tracking error when the minimizer sequence remains close to its dynamics.Small cumulative mismatch ∑T_t=1 ||v_t|| yields a small bound, and vice versa.
  • Tracking results: For σ2_v = 0.5, plotted estimators closely follow the moving target trajectory with high probability.Figure 2 shows the target in red and estimators for agents 1, 6, 12, and 23 in blue over T = 1000 iterations.

V. CONCLUSION

The paper develops a decentralized online optimization framework for tracking minimizers of dynamic global convex functions under unknown, unstructured noise. Its regret analysis captures network connectivity and model deviation, while identifying open directions for stronger and adaptive results.

  • V. CONCLUSION: The framework tracks a time-varying global convex-function minimizer whose known dynamics are perturbed by unknown, unstructured noise.The global objective is assembled from local functions observed sequentially by networked agents.
  • V. CONCLUSION: The proposed method is a decentralized Mirror Descent algorithm augmented with agent interactions and minimizer dynamics.Its performance is measured using network dynamic regret against an offline counterpart.
  • V. CONCLUSION: The regret bound scales inversely with the network spectral gap and captures minimizer deviation from the prescribed dynamics.For noisy local-gradient observations, the bound holds in expectation, and the results recover distributed optimization results in online and offline settings.
  • V. CONCLUSION: The method is applied to decentralized tracking of dynamic parameters in numerical experiments.
  • V. CONCLUSION: Stronger theoretical results for receiving multiple gradients per time step remain an open question.
  • V. CONCLUSION: Adaptive step-size tuning remains open because the relevant mismatch-noise quantity is not fully observable in the decentralized setting.Corollary 4 assumes advance step-size tuning requiring knowledge of CT or an upper bound on the quantity.

VI. APPENDIX

The appendix develops the technical inequalities used in the mirror-descent analysis. It combines Bregman-divergence properties, network stochasticity, vector stacking, and non-expansiveness to derive the required bounds.

  • VI. APPENDIX: Lemma 6 gives a standard inequality for mirror-descent updates over a convex set using a strongly convex regularizer and Bregman divergence.
  • VI. APPENDIX: Strong convexity lower-bounds Bregman divergence by one-half the squared norm, enabling norm-based simplification of the update inequality.
  • VI. APPENDIX: The proof rewrites the algorithmic update using the error e_i,t := ˆx_i,t+1 − y_i,t and stacks local vectors into matrix form with a Kronecker product.
  • VI. APPENDIX: Doubly stochasticity of W, bounded error, and the norm condition ∥A∥≤1 provide the network bounds used in the derivation.

B. Proof of Lemma 2

The proof of Lemma 2 decomposes the target expression into four terms and bounds them using Bregman-divergence regularity, stochasticity, and non-expansiveness assumptions.

  • B. Proof of Lemma 2: The proof begins by adding, subtracting, and regrouping terms into a four-term decomposition.
  • B. Proof of Lemma 2: The second term is bounded using the Lipschitz condition on the Bregman divergence.
  • B. Proof of Lemma 2: Separate convexity of the Bregman divergence and stochasticity of W provide an additional bound for the decomposed terms.
  • B. Proof of Lemma 2: Non-expansiveness of A supplies the final inequality used before summing over t ∈[T].The first term then telescopes, while the second and third terms use earlier bounds.
  • B. Proof of Lemma 2: The argument uses that the step-size is positive and decreasing when applying the summed inequality.

C. An Auxiliary Lemma

The auxiliary lemma supplies a bound under convex local functions, network stochasticity, regularity of the Bregman divergence, and non-expansive dynamics. Its proof combines convexity, gradient boundedness, the update relation, and Lemma 6.

  • C. An Auxiliary Lemma: Lemma 7 assumes Lipschitz local functions, a doubly stochastic W, regular and separately convex Bregman divergence, and a non-expansive mapping A.
  • C. An Auxiliary Lemma: Convexity of each local function provides the initial inequality for any agent i ∈[n].
  • C. An Auxiliary Lemma: Bounded gradients and the AM-GM inequality bound the last term in the auxiliary estimate.
  • C. An Auxiliary Lemma: The update relation and assumptions on local functions and W bound the second term, using Lemma 1.
  • C. An Auxiliary Lemma: Applying Lemma 6 and the Bregman lower bound yields the auxiliary inequality before summation over agents and time.
  • C. An Auxiliary Lemma: Summing over t ∈[T] and i ∈[n], then applying Lemma 2, completes the proof.

D. Proof of Theorem 3

The proof bounds the regret using Lipschitz continuity, summation over agents and time, and previously established lemmata. A stochastic-gradient variant follows the same proof structure, replacing exact-gradient bounds with stochastic-gradient moment bounds.

  • Lipschitz continuity of f_t and f_i,t is used in the regret bound before summing over agents and time.
  • Summing over t ∈[T] and i ∈[n], together with Lemmata 1 and 7, completes the proof.
  • The stochastic-gradient proof reworks the argument for Theorem 3 by modifying equation (12) and the gradient step in Lemma 7.
  • Bounds based on an exact-gradient constant L are replaced by the norm or bounded second moment of the stochastic gradient, changing inequality (23).
  • After taking expectations and summing over agents and time, the stochastic-gradient argument obtains the Lemma 7 bound with L replaced by G.
Loading 1609.02845v1…