Source-linked AI summary
Distributed Bandit Online Convex Optimization with Time-Varying Coupled Inequality Constraints
Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Karl H. Johansson, Tianyou Chai
TL;DR
The paper studies distributed bandit online optimization with time-varying coupled constraints, where learners privately observe sampled local loss and constraint values. It proposes one- and two-point algorithms and establishes sublinear expected regret and constraint violation under sublinear comparator variation.
Problem
The problem is to minimize global losses while satisfying time-varying coupled constraints using private bandit feedback; under a completely adaptive adversary, sublinear static regret may not be guaranteed.
Source: §I · pp. 1–2Method
The paper proposes distributed algorithms using one-point or two-point sampling gradient estimators for the corresponding bandit feedback settings.
Source: §I · pp. 2–3Results
With sublinear comparator variation, one-point feedback yields O(T^θ1) expected static regret and O(T^(7/4−θ1)) constraint violation, while two-point feedback yields O(T^max{κ,1−κ}) expected static regret and O(T^(1−κ/2)) constraint violation.
Source: §I · pp. 2–3Takeaways & Limitations
Both algorithms achieve sublinear expected regret and constraint violation when the accumulated comparator variation grows sublinearly.
Source: §I · pp. 2–3, §VII · p. 8
Abstract
from arXiv · showhide
This paper considers the problem of distributed bandit online convex optimization with time-varying coupled inequality constraints. This problem can be defined as a repeated game between a group of learners and an adversary. The learners attempt to minimize a sequence of global loss functions and at the same time satisfy a sequence of coupled constraint functions. The global loss and the coupled constraint functions are the sum of local convex loss and constraint functions, respectively, which are adaptively generated by the adversary. The local loss and constraint functions are revealed in a bandit manner, i.e., only the values of loss and constraint functions at sampled points are revealed to the learners, and the revealed function values are held privately by each learner. We consider two scenarios, one- and two-point bandit feedback, and propose two corresponding distributed bandit online algorithms used by the learners. We show that sublinear expected regret and constraint violation are achieved by these two algorithms, if the accumulated variation of the comparator sequence also grows sublinearly. In particular, we show that $\mathcal{O}(T^{\theta_1})$ expected static regret and $\mathcal{O}(T^{7/4-\theta_1})$ constraint violation are achieved in the one-point bandit feedback setting, and $\mathcal{O}(T^{\max\{\kappa,1-\kappa\}})$ expected static regret and $\mathcal{O}(T^{1-\kappa/2})$ constraint violation in the two-point bandit feedback setting, where $\theta_1\in(3/4,5/6]$ and $\kappa\in(0,1)$ are user-defined trade-off parameters. Finally, these theoretical results are illustrated by numerical simulations of a simple power grid example.
I. INTRODUCTION
The paper studies distributed bandit online convex optimization with time-varying coupled inequality constraints, proposing one- and two-point algorithms with sublinear expected regret and constraint violation when comparator variation grows sublinearly.
I. INTRODUCTION
- Bandit online optimization estimates loss gradients from sampled loss values; prior methods use one or multiple samples and obtain differing regret bounds under varying assumptions.Some cited one-sample methods assume linear, smooth, strongly convex, or self-concordant-barrier settings, while two-sample methods can reduce expected static regret bounds.Source: §I · p. 2
- Prior work rarely treated bandit feedback with inequality constraints, and most distributed bandit online optimization studies used centralized settings.Earlier work addressed static or time-varying constraints, but the cited studies did not cover this paper’s full combination of distributed optimization and time-varying coupled constraints.Source: §I · p. 2
- With sublinear comparator variation, the one-point algorithm achieves O(T^θ1) expected static regret and O(T^(7/4−θ1)) constraint violation, for θ1 ∈ (3/4, 5/6].Without inequality constraints, it achieves O(T^3/4) expected static regret.Source: §I · p. 2
- The two-point algorithm achieves O(T^max{κ,1−κ}) expected static regret and O(T^(1−κ/2)) constraint violation, for κ ∈ (0, 1).It does not require the total number of rounds or other parameters related to loss or constraint functions.Source: §I · p. 3
A. Graph Theory
- The communication model uses a time-varying directed graph whose edges indicate which agents can send data to others at each round.An edge (j, i) means agent i can receive data from agent j; the in- and out-neighbor sets are defined by edge direction.Source: A. Graph Theory · p. 3
B. Gradient Approximation
The section introduces one- and two-point gradient estimators for bandit feedback, then formulates the distributed problem with private local feedback and coupled constraints.
B. Gradient Approximation
- The one-point estimator samples on the unit sphere and uses a shrunken decision set so perturbations remain feasible in K.For x in (1−ξ)K and δ in (0,r(K)ξ], x+δu lies in K.Source: B. Gradient Approximation · p. 3
- Uniform smoothing makes the smoothed function differentiable even when the original function is not, and both estimators are unbiased estimates of its gradient.The smoothed function is defined on the shrunken set (1−ξ)K.Source: B. Gradient Approximation · p. 3
- The one-point estimator has a large norm as δ shrinks, whereas the two-point estimator has a bounded norm, motivating improved two-point results.The paper attributes the difference to the estimators' norm properties.Source: B. Gradient Approximation · p. 4
III. PROBLEM FORMULATION
- Learners privately sample local losses and constraints while communicating over a time-varying directed graph to minimize global loss and satisfy coupled constraints.The global objectives sum local functions, and the comparator sequence's accumulated variation is used in the problem formulation.Source: §III · p. 4
- The formulation assumes feasible sequences exist; its cumulative constraint-violation measure allows violations at some times to be offset by strictly feasible decisions at others.The paper identifies average power constraints as an example of cumulative constraints.Source: §III · p. 4
A. Motivating Example
The motivating power-grid example has distributed generation units with uncertain local costs and global constraints that require coordination.
A. Motivating Example
- Each unit's generation cost is modeled locally, often quadratically, but its accurate form is unknown in advance.The paper connects this uncertainty to fluctuating fossil-fuel prices and unpredictable renewable generation.Source: A. Motivating Example · p. 5
- Units must coordinate to satisfy global power-balance and emissions constraints formed by summing local constraint functions.Each unit also has its own feasible-output set.Source: A. Motivating Example · p. 5
- The operational goal is to reduce total generation cost while satisfying constraints that may change from hour to hour.The paper notes that power demand and emissions can vary with uncertain renewable energy.Source: A. Motivating Example · p. 5
IV. ONE-POINT BANDIT FEEDBACK
The paper proposes a distributed one-point bandit algorithm for online optimization with time-varying inequality constraints. Its bounds give sublinear constraint violation and, when comparator variation grows sublinearly, sublinear dynamic regret.
IV. ONE-POINT BANDIT FEEDBACK
- The method uses a one-point sampling gradient estimator to address the constrained distributed bandit problem.The section also derives expected regret and constraint-violation bounds for the algorithm.Source: §IV · p. 5
A. Distributed Bandit Online Algorithm with One-Point Sampling Gradient Estimator
- Algorithm 1 uses local primal, intermediate, dual, and average-dual estimate sequences, updated through distributed online gradient-free extensions of primal-dual updates.The updates are based on an augmented Lagrangian formulation.Source: A. Distributed Bandit Online Algorithm… · pp. 5–6
B. Expected Regret and Constraint Violation Bounds
- Theorem 1 characterizes expected regret and constraint-violation bounds for Algorithm 1 under specified parameter choices and assumptions.The bounds apply to comparator sequences and involve their accumulated variation.Source: B. Expected Regret and Constraint… · p. 6
- Sublinear comparator-path variation yields sublinear expected dynamic regret under the stated parameter condition, while the algorithm also has sublinear expected constraint violation.The paper states that if V(x*_T)=O(T^ν), choosing θ1 in (0,1−ν) gives expected dynamic regret o(T).Source: B. Expected Regret and Constraint… · p. 6
- Algorithm 1 does not require the total number of rounds in advance, but each learner needs a uniform upper bound on its time-varying constraint function.The authors identify the latter requirement as a potential drawback.Source: B. Expected Regret and Constraint… · p. 6
- The static-regret corollary uses θ1 in (3/4,5/6] and specifies θ2=2θ1−3/2 and θ3=θ1−1/2.The paper describes θ1 as a user-defined trade-off parameter between static regret and constraint violation.Source: B. Expected Regret and Constraint… · p. 6
V. TWO-POINT BANDIT FEEDBACK
Algorithm 2 uses two-point sampling and a modified dual update that avoids requiring known upper bounds. Its bounds give sublinear expected constraint violation and, when comparator variation grows sublinearly, sublinear expected dynamic regret.
A. Distributed Bandit Online Algorithm with Two-Point Sampling Gradient Estimator
- Two-point samples provide local loss and constraint values, while the dual update uses c_i,t instead of g_i,t−1(x_i,t−1).This modification avoids requiring upper bounds on the loss and constraint functions.Source: A. Distributed Bandit Online Algorithm… · p. 7
B. Expected Regret and Constraint Violation Bounds
- Theorem 2 states bounds for sequences generated under Assumptions 1–2 and any comparator sequence, with κ∈(0,1).Corollary 2 specializes these results to expected static regret and constraint violation.Source: B. Expected Regret and Constraint… · p. 7
- With sublinear comparator variation, Algorithm 2 achieves sublinear expected dynamic regret, while its expected constraint violation is sublinear.The dynamic-regret condition is stated for comparator sequences whose accumulated variation grows sublinearly.Source: B. Expected Regret and Constraint… · p. 7
- Algorithm 2 matches [43]'s bounds under the same assumptions despite using two-point bandit feedback rather than full-information feedback.The comparison is in an average sense.Source: B. Expected Regret and Constraint… · p. 7
- κ lets users trade off the expected static-regret bound against the expected constraint-violation bound.The section also contrasts these guarantees with prior results for centralized methods and static constraints.Source: B. Expected Regret and Constraint… · pp. 7–8
VI. NUMERICAL SIMULATIONS
In the power-generation simulation, Algorithm 2 outperforms Algorithm 1 on expected dynamic regret and constraint violation, while the centralized comparators perform better than the distributed methods. The conclusion identifies adaptive sampling as future work.
VI. NUMERICAL SIMULATIONS
- The evaluation applies Algorithms 1 and 2 to the power-generation example, using n=50 learners and a communication graph with connection probability ρ=0.2.The reported averages are taken over 100 realizations.Source: §VI · p. 8
- The normalized expected constraint violation E[∥[∑_t g_t(x_t)]+∥]/T tends to zero in the simulations.The paper says this agrees with its theoretical bounds and results in and.Source: §VI · p. 8
- Algorithm 2 has smaller expected dynamic regret and constraint violation than Algorithm 1, while centralized algorithms [39] and have smaller values than the distributed methods.Figures 1 and 2 show the compared evolutions; the averages use 100 realizations.Source: Figure 1 · p. 8, Figure 2 · p. 8, §VI · p. 8
VII. CONCLUSIONS
- Future research directions include adaptively choosing the number of samplings used by different learners at each round.Source: §VII · p. 8
A. Useful Lemmas
The useful lemmas establish projection properties, an inequality for positive-part vectors, and an optimality condition used in the proofs.
A. Useful Lemmas
- Projection onto a nonempty closed convex set exists uniquely and is nonexpansive.The projection result is attributed to Theorem 1.5.5 in.Source: A. Useful Lemmas · p. 10
- For componentwise ordered vectors a≤b, their positive parts satisfy [a]+≤[b]+.The proof applies the positive-part operation componentwise.Source: A. Useful Lemmas · p. 10
- A quadratic function h(y)=∥c−y∥²+2⟨a,y⟩ is minimized over K at x1, yielding an optimality condition used to derive (24).Source: A. Useful Lemmas · p. 10
B. Proof of Lemma 2
The proof uses identities for expected gradient estimates and properties of the shrunken feasible set to establish regularity of the smoothed function and its gradient.
B. Proof of Lemma 2
- The expected one- and two-point gradient estimators equal the gradient of the smoothed function under the stated identities.The two-point identity uses E[f(x)u]=0 for uniformly sampled u on the sphere.Source: B. Proof of Lemma 2 · p. 10
- The shrunken set (1−ξ)K lies inside K, so f is differentiable at points in that set.Source: B. Proof of Lemma 2 · p. 10
- The smoothed function is Lipschitz-continuous on (1−ξ)K, and its gradient is Lipschitz-continuous there with constant pL0(f)/δ.Source: B. Proof of Lemma 2 · p. 10
C. Proof of Theorem 1
The proof of Theorem 1 builds bounds on Algorithm 1’s dual variables and per-round regret, then combines them to establish bounds for arbitrary comparator sequences. It derives Theorem 1’s stated results by applying parameter conditions to those bounds.
C. Proof of Theorem 1
- Lemma 5 bounds Algorithm 1’s local dual variables, while Lemma 6 bounds regret for one round.Both lemmas assume Assumptions 1–2; Lemma 6 considers an arbitrary comparator sequence.Source: C. Proof of Theorem 1 · pp. 11–12
- Lemma 7 gives expected regret and constraint-violation bounds for Algorithm 1 over any comparator sequence.Its proof combines the dual-variable and regret bounds with comparator feasibility, then takes expectations.Source: C. Proof of Theorem 1 · pp. 13–14
- The proof of Lemma 7 uses feasibility of the comparator sequence to combine the regret and constraint terms.It sums the preceding bounds over time and takes expectation before deriving the aggregate results.Source: C. Proof of Theorem 1 · p. 14
- Theorem 1’s bounds follow by applying the parameter conditions to the bounds in (50a) and (50b).The proof separately derives the results in (14a) and (14b).Source: C. Proof of Theorem 1 · p. 14
D. Proof of Theorem 2
The proof of Theorem 2 follows the proof strategy for Theorem 1 with Algorithm 2-specific lemmas. It uses the resulting aggregate bounds to establish the two conclusions in (20a) and (20b).
D. Proof of Theorem 2
- Lemma 8 bounds the local dual variables generated by Algorithm 2 under Assumptions 1–2.The proof adapts the corresponding Algorithm 1 bounds.Source: D. Proof of Theorem 2 · pp. 14–15
- Under Assumptions 1–2, Lemma 9 considers, for all i ∈ [n], a sequence {x_t} generated by Algorithm 2 and an arbitrary sequence {y_t} in X.Its proof replaces z_i,t and a_i,t with x_i,t and b_i,t, deletes (47), and follows steps similar to those used to prove (38) to yield (69).Source: D. Proof of Theorem 2 · p. 15
- Lemma 10 gives aggregate bounds for Algorithm 2 over any comparator sequence.It is proved using Lemmas 8 and 9, following the approach used for Lemma 7.Source: D. Proof of Theorem 2 · p. 15
- Theorem 2’s results in (20a) and (20b) follow from Lemmas 8–10 using steps similar to the proof of Theorem 1.The proof of Lemma 10 likewise follows the steps used for Lemma 7.Source: D. Proof of Theorem 2 · p. 15