Source-linked AI summary
Online Convex Optimization with Time-Varying Constraints
Michael J. Neely, Hao Yu
TL;DR
The paper asks whether online convex optimization can simultaneously handle objectives and constraints that are revealed over time, despite general impossibility results. It develops a virtual-queue and projected-subgradient algorithm, obtaining O(1/ε^2) convergence under a common feasible subset and expected guarantees under i.i.d. constraints. With i.i.d. objectives and constraints, the guarantee extends to the best possibly time-varying causal policy that knows the distribution but not the future.
Problem
Online optimization with time-varying convex constraints is generally unable to guarantee both ε-level objective optimality and time-average feasibility on arbitrary sample paths.
Method
The paper combines projected online subgradient updates with virtual queues and analyzes them under deterministic common-subset and stochastic i.i.d. assumptions.
Results
The algorithm achieves O(ε) accuracy with 1/ε^2 convergence time under a common subset, retains this expected rate with i.i.d. constraints, and compares against causal policies when all functions are i.i.d.
Takeaways & Limitations
The results provide an online solution to constrained convex optimization in settings where arbitrary sample paths are impossible but common-feasibility or i.i.d. structure is available.
Abstract
from arXiv · showhide
This paper considers online convex optimization with time-varying constraint functions. Specifically, we have a sequence of convex objective functions $\{f_t(x)\}_{t=0}^{\infty}$ and convex constraint functions $\{g_{t,i}(x)\}_{t=0}^{\infty}$ for $i \in \{1, ..., k\}$. The functions are gradually revealed over time. For a given $ε>0$, the goal is to choose points $x_t$ every step $t$, without knowing the $f_t$ and $g_{t,i}$ functions on that step, to achieve a time average at most $ε$ worse than the best fixed-decision that could be chosen with hindsight, subject to the time average of the constraint functions being nonpositive. It is known that this goal is generally impossible. This paper develops an online algorithm that solves the problem with $O(1/ε^2)$ convergence time in the special case when all constraint functions are nonpositive over a common subset of $\mathbb{R}^n$. Similar performance is shown in an expected sense when the common subset assumption is removed but the constraint functions are assumed to vary according to a random process that is independent and identically distributed (i.i.d.) over time slots $t \in \{0, 1, 2, \ldots\}$. Finally, in the special case when both the constraint and objective functions are i.i.d. over time slots $t$, the algorithm is shown to come within $ε$ of optimality with respect to the best (possibly time-varying) causal policy that knows the full probability distribution.
I. INTRODUCTION
The paper studies online convex optimization with objectives and constraints revealed only after each decision, extending unconstrained online subgradient methods to time-varying constraints. Prior work shows that satisfying time-average objectives and constraints simultaneously is generally impossible, while restricted settings provide various convergence-time tradeoffs.
- I. INTRODUCTION: At each slot, the controller chooses a decision without knowing the current objective or constraint functions, then incurs the objective cost and reveals the resulting penalties.The functions are convex, initially unknown, and revealed after the decision; bounded subgradients are available afterward.
- I. INTRODUCTION: The unconstrained Zinkevich algorithm uses the previous slot’s subgradient and projection onto X, achieving an O(ε)-approximation to the best hindsight fixed decision after O(1/ε^2) slots.The cited analysis states that this convergence time is asymptotically optimal for general linear-objective online problems, while strong convexity can improve it.
- A. Prior work with constraints: For time-varying constraints, a sample-path construction shows that no algorithm can generally achieve an ε-approximation for both objective optimality and time-average feasibility.Actions that are objective-optimal at one horizon can cause substantial constraint violations at a later horizon, while constraint-feasible alternatives can be far from objective-optimal.
- A. Prior work with constraints: When constraints are known and time-invariant, prior methods use either projections onto the feasible set or simpler projections onto X, with convergence times ranging from O(1/ε^2) to O(1/ε^4).Follow-up work trades objective and constraint convergence rates, and later work reaches O(1/ε^2) objective convergence with O(1/ε) constraint convergence.
- A. Prior work with constraints: For i.i.d. objective and constraint functions, prior work established a non-online batch approach, leaving online algorithms with convergence guarantees for this setting unresolved.The i.i.d. model avoids the worst-case sample paths used in the impossibility result.
B. Our contributions
The paper’s contributions cover deterministic and stochastic time-varying constraints under explicit regularity assumptions. Its guarantees reach O(ε) accuracy in O(1/ε^2) time in the common-subset setting and extend in expectation to broader i.i.d. models.
- B. Our contributions: For arbitrary sample paths satisfying a deterministic Slater condition, the algorithm achieves an O(ε)-approximation in 1/ε^2 time when all constraints are nonpositive on a common subset.This matches the best cited special-case convergence rate and improves on earlier methods in [5][6].
- B. Our contributions: With i.i.d. constraint functions and otherwise arbitrary stochastic objectives, the same O(ε), 1/ε^2 guarantee holds in expectation against fixed decisions satisfying constraints in expectation.This removes the deterministic common-subset requirement from the comparison class under the stated stochastic model.
- B. Our contributions: When the full objective-constraint vector is i.i.d., the algorithm approaches optimality against any causal policy that may vary decisions over time but does not know the future.The deterministic Slater condition is replaced by a mild Lagrange-multiplier assumption, and the algorithm does not require those multipliers as input.
- II. FORMULATION: The formulation allows continuous convex, possibly nonsmooth functions on a compact convex decision set with bounded function values and subgradients.These assumptions support the deterministic and stochastic analyses across Sections II–VI.
- B. Optimization over a common subset: The common subset A contains decisions satisfying every time-varying constraint at every slot, and the algorithm does not need to know A.The Slater vector makes A nonempty, while the formal guarantee compares against fixed decisions in A after the transient period.
- B. Optimization over a common subset: The paper identifies a broader fixed-decision objective based only on limiting average feasibility, but prior work shows that this goal is generally impossible without additional probabilistic structure.The stochastic sections recover this broader goal in expectation under i.i.d. constraints.
III. ALGORITHM
The algorithm combines virtual queues for constraint violations with projected online updates over the original decision set X. Its drift-plus-penalty construction balances queue stability, objective performance, and changes between successive decisions.
- III. ALGORITHM: At each slot, the algorithm chooses X_t in X by minimizing an expression based on virtual queues, the previous decision, objective subgradient information, and constraint information from the previous slot.It initializes X_0, observes the queues, makes the decision, and updates the queues after the slot’s functions are revealed.
- A. Implementation as a projection: The per-slot minimization has a unique implementation as a projection onto the compact convex set X, preserving the simple projection structure of the Zinkevich update.Compactness and convexity ensure that the projection exists and is unique.
- B. Virtual queue analysis: The virtual-queue analysis bounds cumulative constraint violations using the queue update, bounded subgradients, and a parameterized inequality for every β > 0.Summing the resulting inequality over slots and dividing by T yields the stated average bounds.
- C. Intuition on algorithm construction: The drift-plus-penalty design minimizes a Lyapunov drift term together with a weighted objective and movement penalty, thereby targeting both small queues and controlled decision changes.The movement term reflects the original unconstrained online method’s preference for keeping successive decisions close.
- B. Virtual queue analysis: The analysis explicitly treats low virtual queues and small ||X_t − X_{t−1}||^2 as desirable quantities for the algorithm to maintain.These quantities connect constraint enforcement with stability of the online iterate sequence.
D. Sample path drift analysis
The analysis derives a drift-plus-penalty bound for the algorithm and uses strong convexity of its decision objective to establish a sample-path inequality.
- D. Sample path drift analysis: The drift analysis controls queue growth by bounding each queue increment through the bounded constraint values and subgradients.The proof uses |b_i(t)|≤F+GD after summing the per-constraint inequalities.
- D. Sample path drift analysis: The algorithm chooses X_t by minimizing a strongly convex drift-plus-penalty expression over the convex set X.The proximal term α||X_t−X_{t−1}||2 provides the strong convexity used in the minimization argument.
- E. Strong convexity analysis: Lemma 4 bounds the sample-path drift-plus-penalty by B, the objective difference V f_{t−1}(y)−V f_{t−1}(X_{t−1}), and a telescoping distance term.The bound holds for every y∈X and every slot.
- E. Strong convexity analysis: The proof obtains the bound by applying subgradient inequalities and the strong-convex minimization fact to the algorithm’s decision expression.Completing the square establishes the required quadratic inequality.
IV. PERFORMANCE BOUNDS
The performance analysis converts the drift bounds into objective and constraint guarantees, yielding O(ε) accuracy after O(1/ε^2) slots under the deterministic Slater condition.
- A. Objective bound: Theorem 1 bounds the time-average objective relative to every feasible fixed decision x∈A when A is nonempty.The bound holds for every integer T≥1 and includes terms depending on V, α, B, G, and D.
- B. Queue bound: The queue drift inequality combines a bounded term, a negative term proportional to ||Q(t)||, and telescoping distance terms.The Slater vector s appears in the distance terms, while η controls the queue penalty.
- B. Queue bound: The virtual-queue norm remains O(V) for all slots when α=V^2.Theorem 2 supplies the queue bound used to control average constraint violations.
- B. Queue bound: Under the deterministic Slater condition, constraint violations are O(1/V) whenever T≥V^2.The result applies separately to each constraint and uses α=V^2.
- IV. PERFORMANCE BOUNDS: For any ε>0, choosing V≥1/ε and α=V^2 gives an O(ε) approximation with convergence time T=1/ε^2.This combines the objective and constraint guarantees under the deterministic Slater condition.
V. STOCHASTIC ANALYSIS
The stochastic analysis introduces probabilistic structure to obtain stronger performance guarantees than the general sample-path setting.
- V. STOCHASTIC ANALYSIS: The stochastic analysis studies stronger performance guarantees when a probabilistic structure is imposed on the time-varying functions.The supplied passage introduces the section but does not specify its particular models or bounds.
A. Probability model
The stochastic framework distinguishes a model with i.i.d. constraints from one with jointly i.i.d. objectives and constraints, then proves expected performance under Model 1.
- A. Probability model: Model 1 assumes i.i.d. constraint-function processes while allowing the objective process to vary arbitrarily and depend on them.The controller is not assumed to know the probability distribution.
- A. Probability model: Model 2 makes the objective and constraint functions jointly i.i.d. over time by setting η_t=ω_t.Model 2 is a special case of Model 1 and supports stronger results later in the paper.
- B. Goal for Model 1: The expected-feasibility set à contains fixed decisions whose expected constraint values are nonpositive for every constraint and time slot.It contains the deterministic feasible set A, and Slater’s condition ensures both sets are nonempty.
- C. Performance under Model 1: Under Model 1, the expected time-average objective is within O(1/V) of the optimal fixed decision in à when T≥V^2.The functions are assumed bounded, continuous, convex, and equipped with bounded subgradients.
- C. Performance under Model 1: Under the Slater condition, expected constraint violations are within O(1/V) of satisfaction when T≥V^2.The theorem gives the same scaling for each constraint.
- C. Performance under Model 1: Choosing V=⌈1/ε⌉ and α=V^2 yields an O(ε) expected approximation with convergence time V^2.The result combines the objective and constraint parts of Theorem 4.
VI. STOCHASTIC ANALYSIS FOR MODEL 2
Under i.i.d. time variation, the analysis removes the Slater condition, broadens comparison from feasible fixed decisions to all causal policies, and characterizes optimality through valid decision sequences and Lagrange multipliers.
- VI. STOCHASTIC ANALYSIS FOR MODEL 2: i.i.d. function sequences enable stronger results for Model 2.
- VI. STOCHASTIC ANALYSIS FOR MODEL 2: The analysis replaces the Slater condition with a mild Lagrange multiplier assumption.
- VI. STOCHASTIC ANALYSIS FOR MODEL 2: Optimality is compared against all causal policies, including distribution-aware time-varying policies, rather than only feasible fixed decisions.
- A. Optimality and Lagrange multipliers: Valid decisions are causal and independent of the current random function, while satisfying expected objective and constraint conditions.
- A. Optimality and Lagrange multipliers: The set R collects vectors entrywise above some expected objective-and-constraint vector h(x), and is closed and convex.
- A. Optimality and Lagrange multipliers: Lemma 8 establishes an optimal deterministic vector x* and places (f*, 0, ..., 0) on the boundary of R.
B. Queue bound for Model 2
For Model 2, the queue analysis derives a bound under feasibility and the Lagrange multiplier assumption, then specializes parameters to obtain the stated convergence scaling.
- B. Queue bound for Model 2: Theorem 5 bounds performance for every horizon T under Model 2, feasibility, and nonnegative Lagrange multipliers.
- B. Queue bound for Model 2: For any fixed ǫ > 0, setting V = 1/ǫ and α = 1/ǫ2, the cited result applies for all T ≥ 1/ǫ2.
C. Performance bound for Model 2
The performance theorem converts the Model 2 bounds into an O(ε)-approximation after convergence time 1/ε2 for objective and constraint quantities.
- C. Performance bound for Model 2: For V = 1/ε and α = 1/ε2, the algorithm achieves its stated objective and constraint bounds for every T ≥ 1/ε2.
APPENDIX
The appendix establishes the geometry underlying Model 2 optimality, proves convexity-based reduction from randomized to deterministic decisions, and derives the existence of an optimal fixed vector.
- A. Properties of h and R: The function h is continuous with convex components, and its upper set R is closed and convex.
- B. Proof of Lemma 7: Jensen’s inequality maps valid randomized decisions to deterministic expectations without worsening the expected objective or constraints.
- B. Proof of Lemma 7: Convexity of R extends the inclusion from individual slots to finite-horizon averages.
- C. Proof of Lemma 8: Lemma 8 obtains a deterministic x* whose expected objective equals f* and whose expected constraints are nonpositive.
- C. Proof of Lemma 8: The point (f*, 0, ..., 0) lies on the boundary of R because any lower objective value would contradict optimality.
D. Convergence time to regret conversion
The section uses a standard doubling trick to convert fixed-parameter convergence guarantees into regret bounds over arbitrary horizons. The paper’s algorithm satisfies the required per-frame objective and constraint guarantees, yielding sublinear regret under successively doubled frames.
- Method context: The doubling trick is presented as a standard method for translating convergence-time bounds into regret bounds.The section cites as an example of the technique’s broader use.
- Required guarantee: The conversion assumes an algorithm that provides deterministic objective and constraint guarantees for every ε > 0 over a set B.The paper states that its algorithm satisfies these required guarantees through Theorems 1 and 3.
- Frame-based conversion: The doubling trick restarts the algorithm on frames with sizes T_m = 2^m and uses ε_m = 1/√T_m to obtain regret bounds for all horizons.The construction combines guarantees within completed frames and controls the remaining partial frame.
- Result: The resulting modified algorithm achieves O(√T) regret for both the objective function and the constraints over every time horizon.The frame summation and residual-frame bounds establish the all-T result.