PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints

Xinlei Yi, Xiuxian Li, Lihua Xie, Karl H. Johansson

arXiv:1903.04277v2math.OCcs.DCcs.LGstat.ML

TL;DR

The paper addresses distributed online convex optimization with time-varying coupled inequality constraints and private functions revealed after each decision. It develops a distributed online primal-dual dynamic mirror descent method and derives regret and constraint-violation guarantees under varying comparator sequences and network conditions. The results establish sublinear dynamic and static performance under stated stepsize and variation conditions, with improved bounds under Slater’s condition or strong convexity.

  • Problem

    Distributed online optimization must handle private time-varying costs, regularization, and coupled constraints while agents communicate over changing networks.

  • Method

    The paper proposes a distributed online primal-dual dynamic mirror descent algorithm using local function information revealed after each time slot and network communication.

  • Results

    The algorithm attains sublinear dynamic regret and constraint violation when comparator variation grows sublinearly under suitable decreasing stepsizes, and also achieves sublinear static regret and constraint violation under mild conditions.

  • Takeaways & Limitations

    Performance bounds expose the roles of stepsizes, comparator variation, agent count, and network connectivity, while Slater’s condition and strong convexity yield smaller bounds in the stated cases.

Abstract

from arXiv · show

This paper considers distributed online optimization with time-varying coupled inequality constraints. The global objective function is composed of local convex cost and regularization functions and the coupled constraint function is the sum of local convex functions. A distributed online primal-dual dynamic mirror descent algorithm is proposed to solve this problem, where the local cost, regularization, and constraint functions are held privately and revealed only after each time slot. Without assuming Slater's condition, we first derive regret and constraint violation bounds for the algorithm and show how they depend on the stepsize sequences, the accumulated dynamic variation of the comparator sequence, the number of agents, and the network connectivity. As a result, under some natural decreasing stepsize sequences, we prove that the algorithm achieves sublinear dynamic regret and constraint violation if the accumulated dynamic variation of the optimal sequence also grows sublinearly. We also prove that the algorithm achieves sublinear static regret and constraint violation under mild conditions. Assuming Slater's condition, we show that the algorithm achieves smaller bounds on the constraint violation. In addition, smaller bounds on the static regret are achieved when the objective function is strongly convex. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.

I. INTRODUCTION

The paper formulates distributed online convex optimization with time-varying coupled constraints, private local functions, and decisions coordinated over changing networks. It evaluates algorithms through regret and cumulative constraint violation, seeking sublinear growth under suitable conditions.

  • Problem formulation: The network minimizes a time-varying global convex objective formed from local cost and regularization functions subject to coupled constraints summed across agents.Each agent holds a local decision in Xi, while the global decision lies in the product set X.
  • Online distributed setting: Agents select decisions before receiving their private time-varying cost, regularization, and constraint functions, while exchanging data over a time-varying directed graph.The algorithm therefore operates online with delayed function information and distributed communication.
  • Performance metrics: Dynamic regret compares the algorithm with an optimal feasible sequence that may change over time, whereas static regret uses one feasible decision repeated throughout the horizon.The paper assumes nonempty feasible sequence sets for both dynamic and static comparators.
  • Performance metrics: Constraint violation is measured as the norm of accumulated positive constraint values, allowing violations at some times to be offset by strictly feasible decisions later.This cumulative measure suits constraints such as energy budgets enforced through average power limits.
  • Performance goals: The target is sublinear regret and constraint violation, with Reg(xT, yT) = O(T^κ1) and ||[Σt=1^T gt(xt)]+|| = O(T^κ2) for κ1, κ2 ∈ (0, 1).These rates imply vanishing time-averaged cost difference and constraint violation, while stepsizes trade off how quickly the two bounds decrease.
  • Motivating example: A multi-target tracking example models agent and target trajectories with parameterized paths, local tracking and selection costs, and shared time-varying energy and communication constraints.Agents observe target actions and prices only after selecting their actions.

B. Literature Review

The literature spans centralized and distributed online convex optimization with inequality constraints, while this paper introduces a distributed primal-dual dynamic mirror descent method for time-varying coupled constraints. Its analysis establishes regret and constraint-violation guarantees under varying assumptions, including Slater’s condition and strong convexity.

  • Centralized online optimization: Prior work studied centralized online convex optimization with static or time-varying inequality constraints, often using primal-dual methods to avoid costly projections.These approaches include gradient, saddle-point, and virtual-queue techniques.
  • Distributed online optimization: Distributed online optimization has addressed static set constraints, static inequality constraints, and static coupled inequality constraints, but time-varying coupled constraints remained unconsidered.The paper identifies this setting as the gap motivating its contribution.
  • Proposed method: The paper proposes a distributed online primal-dual dynamic mirror descent algorithm with local primal and dual sequences, neighbor averaging, and separate primal, dual, and penalty stepsizes.The penalty sequence is designed to prevent dual variables from growing too large.
  • Main guarantees: Without Slater’s condition, the analysis relates regret and constraint-violation bounds to stepsizes, comparator variation, agent count, and network connectivity.With α_t = 1/t^c, β_t = 1/t^κ, and γ_t = 1/t^(1−κ), sublinear dynamic regret and constraint violation follow when optimal-sequence variation is sublinear.
  • Main guarantees: Under Slater’s condition, the constraint-violation bound improves to O(T^max{1−κ,κ}), while strong convexity yields O(T^κ) static regret and O(T^(1−κ/2)) constraint violation without Slater’s condition.The paper also states that the parameter κ enables a trade-off between static regret and constraint violation.
  • Comparison with prior work: The proposed bounds improve on selected centralized or distributed results by avoiding some prior assumptions, including known horizons, known function bounds, and explicitly assumed bounded dual sequences.The paper states that its dual sequence is bounded and that its static bounds can recover earlier results as special cases.

B. Projections

The paper introduces projections and Bregman divergences as geometric tools for constrained mirror descent. It assumes convex, compact decision sets and bounded convex functions and subgradients.

  • Projection onto a closed convex set exists uniquely, and [·]+ denotes projection onto the nonnegative orthant.
  • The analysis assumes convex compact local decision sets and uniformly bounded functions and subgradients.
  • Bregman divergence measures distance through a differentiable strongly convex function, generalizing Euclidean distance.
  • Euclidean distance and KL divergence are examples of Bregman divergences for convex compact sets and probability simplices, respectively.
  • The divergence is assumed Lipschitz in its first argument, with a uniform constant K.

III. DISTRIBUTED ONLINE PRIMAL-DUAL DYNAMIC MIRROR DESCENT ALGORITHMS

The section presents a distributed online primal-dual dynamic mirror descent algorithm in which agents maintain local primal and dual sequences and update them using consensus, mirror descent, and dual regularization.

  • Algorithm structure: The algorithm maintains local primal decisions x_i,t and dual variables q_i,t, initialized arbitrarily and at zero, respectively.Agents update these sequences recursively through the stated update rules.
  • Algorithm structure: Consensus averaging of dual variables supports distributed coordination over the time-varying network.The local dual variable is averaged with in-neighbors before subsequent primal and dual updates.
  • Algorithm structure: Each agent observes delayed local gradients, constraint values, and regularization information before determining its dynamic mapping and update directions.The algorithm uses information from time t−1 rather than the full current functions.
  • Stepsizes and dynamics: When agents lack information about optimal-sequence dynamics, their dynamic mappings are set to the identity mapping.The mappings otherwise provide decentralized estimates of the optimal dynamics.
  • Stepsizes and dynamics: Separate primal, dual, and regularization stepsize sequences control a trade-off between the rates at which regret and constraint violation decrease.The algorithm uses {α_t}, {γ_t}, and {β_t} rather than a single common stepsize.
  • Mirror descent update: The composite objective mirror descent step keeps the regularization function unlinearized, enabling sparse updates and efficient solution of a strongly convex subproblem.Closed-form solutions are available in special cases, while linear convergence applies to the strongly convex minimization problem.

IV. REGRET AND CONSTRAINT VIOLATION BOUNDS

This section develops the preliminary estimates and main regret and constraint-violation bounds for the distributed algorithm. The bounds account for algorithmic stepsizes, comparator dynamics, agent count, and network connectivity.

  • Preliminary results: The analysis first establishes regularized Bregman projection estimates and bounds for the local dual variables.These preliminary results support the later regret and constraint-violation analysis.
  • Preliminary results: Dual regularization bounds local dual variables without Slater’s condition and controls consensus deviation and regularized dual drift.The penalty term −β_t q̃_i,t provides the local dual-variable upper bound.
  • Main bounds: The main lemmas derive a one-step regret inequality and then aggregate it into regret and constraint-violation bounds for arbitrary comparator sequences.The resulting bounds are stated for sequences generated by Algorithm 1 and comparator sequences in X^T.
  • Main bounds: The bounds explicitly depend on stepsize sequences, accumulated dynamic comparator variation, the number of agents, and network connectivity.Constraint variation measures used in some related results do not appear in these bounds.
  • Main bounds: The dynamic-variation term can be replaced by the variation of a chosen comparator sequence and reduces to the corresponding identity-mapping case when all mappings are identity.The paper also relates the optimal accumulated variation to feasible-sequence variation.

B. Dynamic Regret and Constraint Violation Bounds

Under decreasing stepsizes, the paper characterizes dynamic regret and constraint-violation rates in terms of optimal-sequence variation. With Slater’s condition and identity dynamics, it obtains smaller constraint-violation bounds.

  • Without Slater’s condition: Sublinear dynamic regret and constraint violation are achieved when the accumulated variation of the optimal sequence grows sublinearly.The result applies to the dynamic mappings used by the algorithm under Theorem 1’s stepsize choices.
  • Without Slater’s condition: If V_Φ(x*_T)=O(T^ν) with ν∈[0,1), choosing c∈(0,1−ν) in Theorem 1 yields the stated sublinear dynamic-regret result.The stepsize exponent is selected using a known upper bound on accumulated variation.
  • Scope and limitation: The bounds depend on the dynamic mapping Φ_i,t, whose estimation from finite or parametric candidate classes is left for future research.Agents may not know suitable mappings, and the mappings may change stochastically.
  • Under Slater’s condition: Under Slater’s condition and identity dynamic mappings, the algorithm achieves an O(T) constraint-violation bound with the improved rate characterized by Theorem 2.The theorem assumes the constraint functions satisfy Slater’s condition.
  • Under Slater’s condition: Under Slater’s condition, constraint violation is not affected by optimal-sequence variation or point-wise maximum variation of consecutive constraints.This differs from the bounds discussed for related methods.
  • Under Slater’s condition: Sublinear dynamic regret can still be obtained under Slater’s condition when V_I(x*_T) grows sublinearly and the stepsize exponent κ exceeds its growth exponent ν.The paper sets κ∈(ν,1) when V_I(x*_T)=O(T^ν).

C. Static Regret and Constraint Violation Bounds

The paper derives static regret and constraint-violation bounds by specializing the dynamic analysis, then shows how trade-off parameters and strong convexity affect these bounds.

  • Static bounds: κ trades off the static regret bound against the constraint-violation bound.The paper identifies κ ∈ (0, 1) as a user-defined trade-off parameter.
  • Static bounds: κ = 0.5 recovers O(T) static regret and O(T 3/4) constraint violation.
  • Comparison: The distributed algorithm matches previously reported static bounds while addressing time-varying coupled constraints without the same centralized or bounded-dual assumptions.
  • Strong convexity: Generalized strong convexity of fi,t + ri,t reduces the static regret bounds.Strong convexity is imposed on fi,t so ri,t may remain simply convex, including ℓ1-regularization.
  • Strong convexity: Theorem 3 and Corollary 3 establish stronger static-regret and constraint-violation results under the strong-convexity conditions.The results also remain valid when either fi,t or ri,t is strongly convex, with minor modifications.

A. Dynamics of Optimal Sequences

The simulations examine how optimal-sequence dynamics, regularization, κ, and algorithm choice affect dynamic regret and constraint violation. Across these tests, exploiting dynamics and explicit regularization improves the observed measures, while Algorithm 1 compares favorably with centralized baselines.

  • Dynamics of optimal sequences: Knowing the dynamics of the optimal sequence leads to smaller dynamic regret and constraint violation.
  • Regularization function: Including the regularization term explicitly leads to smaller dynamic regret and constraint violation.The comparison uses one case with explicit regularization and another with ri,t(xi) = 0.
  • Effects of parameter κ: κ is varied over 0.1, 0.3, 0.5, 0.7, and 0.9, with effects examined at T = 100, 500, 1000.For large T, such as T ≥ 500, κ almost does not affect the reported dynamic regret and constraint-violation measures.
  • Comparison to other algorithms: Algorithm 1 achieves smaller dynamic regret and constraint violation than the algorithms in [12] and [14], and nearly the same values as.
  • Conclusion: The paper concludes that its distributed algorithm achieves sublinear regret and constraint violation for arbitrary and strongly convex objective functions.

APPENDIX

The appendix develops the mirror-descent inequalities and bounded dual-iterate arguments used in the main analysis. It combines optimality conditions, Bregman-divergence identities, convexity, and induction to establish the required intermediate bounds.

  • Appendix: The mirror-descent optimality condition yields a three-point Bregman-divergence inequality for the update.
  • Appendix: Strong convexity of the regularized function provides a squared-distance bound between the update and the reference point.
  • Appendix: The appendix proves boundedness of the modified dual variables by induction, starting from zero initial queues.
  • Appendix: Rewriting the dual update and using convexity, Cauchy–Schwarz, and the network mixing relations establishes the queue and descent inequalities.
  • Appendix: Summing the resulting inequalities over agents and time produces the intermediate bound needed for the main regret and constraint analysis.

C. Proof of Lemma 3

The proof of Lemma 3 bounds the two main terms generated by the mirror-descent update and combines them into the lemma’s stated inequality.

  • C. Proof of Lemma 3: The proof separately bounds the two terms arising from the update inequality.
  • C. Proof of Lemma 3: Applying the mirror-descent inequality to update rule (15) introduces Bregman-divergence differences involving the mapped previous iterate.
  • C. Proof of Lemma 3: The resulting inequalities rely on the stated update relations and assumptions before being combined and summed over agents.

D. Proof of Lemma 4

The proof derives the lemma’s bounds by combining intermediate inequalities, selecting dual variables, and establishing boundedness of the dual iterates through induction and contradiction.

  • Combining intermediate bounds: Combining inequalities (25) and (26) over t yields a bound involving gc(q) and Reg(xT, yT).The derivation uses inequalities (63)–(65), the initial-distance bound, and gt(yt) ≤ 0m.
  • Selecting dual variables: Choosing q = 0m and q = q0 in the combined inequality produces bounds (27) and (28), respectively.The proof also sets yi,T+1 = Φi,T+1(yi,T) for (27) and combines (67)–(68) for (28).
  • Bounding dual iterates: The proof establishes ∥qt∥ ≤ B2 by induction, assuming violation at T1 + 1 and deriving a contradiction from an earlier iterate.The base case is ∥q1∥ = 0, and the contradiction uses the averaged dual sequence and a time t0.
  • Completing the bound: Applying the update rule and norm inequalities then yields the remaining bound (35).The argument uses ∥q̃i,t+1∥ ≤ ∥qt∥ ≤ B2, ∥q̄t∥ ≤ B2, and inequality (69).

G. Proof of Theorem 3

The proof establishes Theorem 3 by replacing an earlier assumption-dependent bound, propagating the resulting inequality changes, and analyzing the stepsize cases for regret and constraint bounds.

  • Assumption-dependent replacement: Under Assumption 6, inequality (57) can be replaced by a stronger alternative used in the subsequent derivation.The replacement preserves inequalities (26)–(28) after modifying E2(t + 1).
  • Regret bound: The resulting argument gives the regret bound in (41) by treating κ ∈ (0, 0.5) and κ ∈ [0.5, 1) separately.For the first case, the proof uses αt = 1/t^(1−κ); for the second, αt = 1/t^κ.
  • Regret bound: For κ ∈ (0, 0.5), the proof obtains Reg(xT, ˇx∗T) ≤ C4T^κ.This is the first stepsize regime analyzed in the proof.
  • Regret bound: For κ ∈ [0.5, 1), the proof obtains Reg(xT, ˇx∗T) ≤ C1T^κ.The proof then concludes that (41) holds across both κ regimes.
  • Constraint bound: Substituting c = 1 − κ or c = κ according to the κ regime gives the constraint-related bound (42).The substitution is made in inequality (31).
Loading 1903.04277v2…