PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Convex Optimization with Stochastic Constraints

Hao Yu, Michael J. Neely, Xiaohan Wei

arXiv:1708.03741v1math.OCstat.ML

TL;DR

The paper addresses online convex optimization with unknown stochastic constraints revealed after decisions, a setting where direct projection onto the feasible set is unavailable. It proposes a learning algorithm based on projections onto the known set X0 and develops stochastic-analysis techniques for its guarantees. The reported bounds cover both expected and high-probability regret and constraint violations.

  • Problem

    Arbitrarily varying constraints can make simultaneous sublinear regret and cumulative constraint violations impossible, motivating an i.i.d. stochastic-constraint formulation with unknown constraint expectations.

  • Method

    The paper proposes an online subgradient-based algorithm that uses projections only onto the known set X0 and develops a technique for high-probability analysis with unbounded differences.

  • Results

    The algorithm guarantees sublinear expected and high-probability regret and constraint violations.

  • Takeaways & Limitations

    The framework covers stochastic constraints and important special cases including long-term constraints and stochastic constrained convex optimization.

Abstract

from arXiv · show

This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special cases, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves $O(\sqrt{T})$ expected regret and constraint violations and $O(\sqrt{T}\log(T))$ high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm.

I. INTRODUCTION

The paper studies online convex optimization when unknown stochastic functional constraints are revealed only after each decision, making the feasible set unavailable for direct projection. It proposes an algorithm with sublinear regret and constraint violations while using projections only onto the known set X0.

  • Motivation: Arbitrarily time-varying constraints can make simultaneous sublinear regret and cumulative constraint violations impossible, even for simple linear losses and constraints.The paper therefore restricts the constraint functions to be i.i.d. generated from an unknown probability model.
  • Problem setting: OCO with stochastic constraints uses multiple i.i.d. functional constraint realizations whose underlying expectations are unknown and revealed after each decision.The decision maker chooses x(t) in X0 before observing the corresponding loss and constraint functions.
  • Motivation: Zinkevich’s projected-gradient method is inapplicable because the stochastic feasible set is unknown and an instantaneous feasible set can be empty.Consequently, projections onto X or the realization-dependent set X(t) may not be well-defined.
  • Contributions: The proposed algorithm achieves sublinear expected regret and constraint violations, together with sublinear high-probability guarantees.The introduction reports expected and high-probability bounds for both quantities.
  • Scope: The formulation includes long-term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization as special cases.The long-term-constraint case uses known time-invariant functional constraints while allowing violations on some rounds.
  • Contributions: The method uses projections only onto the known simple set X0, avoiding the potentially complicated projection onto the stochastic constraint set.This projection choice also underlies its simultaneous regret and violation guarantees in the long-term-constraint special case.
  • Scope: The paper’s approach extends to arbitrarily time-varying constraints only under an additional deterministic Slater condition and regret comparison over a common subset.The current paper instead focuses on stochastic constraints and relaxes that deterministic condition to a stochastic one.
  • Methodological comparison: Unlike a related primal-dual subgradient method, the algorithm does not require an upper bound on optimal Lagrange multipliers to be known.The paper also characterizes the algorithm as subgradient based and applicable without smoothness or differentiability.

II. FORMULATION AND NEW ALGORITHM

The formulation combines arbitrarily varying convex losses with i.i.d. stochastic constraints revealed after each decision. Algorithm 1 uses virtual queues and drift-plus-penalty updates implemented through projections onto the known set X0.

  • II. FORMULATION AND NEW ALGORITHM: Constraint functions are i.i.d. samples from unknown stochastic expectations, while each loss function may vary arbitrarily subject to the stated independence condition.The feasible set is defined by expected constraint values over the known compact convex set X0.
  • II. FORMULATION AND NEW ALGORITHM: The analysis assumes bounded loss and constraint subgradients, bounded constraint vectors, bounded diameter of X0, and a stochastic Slater point with uniform expected slack.The Slater condition requires some x̂ whose expected value satisfies every constraint by at least ϵ.
  • A. New Algorithm: Algorithm 1 initializes x(1) in X0 and zero virtual queues, then selects x(t+1) from the observed loss and constraint functions at round t.The update uses current subgradients and does not require future loss or constraint functions.
  • A. New Algorithm: The paper’s analysis assumes a Slater-type condition, although related work removes that requirement when both objectives and constraints vary i.i.d. over time.That broader case includes deterministic constrained convex optimization as a time-invariant i.i.d. special case.
  • B. Intuitions of Algorithm 1: Virtual queues accumulate stochastic constraint functions, and the algorithm minimizes an upper bound on drift plus penalty to control both queue backlogs and losses.The drift term targets small queue norms, while the penalty corresponds to the loss-minimization component.
  • A. New Algorithm: The decision update reduces to a projection onto X0, avoiding projection onto the unknown stochastic feasible set X.Strong convexity makes the update well-defined, and the projection onto X0 is simple by construction.
  • B. Intuitions of Algorithm 1: When no stochastic constraints exist, the virtual queues remain zero and Algorithm 1 becomes Zinkevich’s algorithm over X0.In this case, the update minimizes only the penalty term.
  • B. Intuitions of Algorithm 1: The drift-plus-penalty intuition combines loss control with queue control because accumulated constraint values determine virtual queue backlogs.A drift upper bound supplies a tractable surrogate for the generally non-convex drift expression.

C. Preliminary Analysis and More Intuitions of Algorithm 1

The preliminary analysis connects virtual queues to constraint violations and establishes bounded decision movement through strong convexity of the update objective.

  • C. Preliminary Analysis and More Intuitions of Algorithm 1: Constraint violations are bounded in terms of the corresponding virtual queue sequence.This relationship motivates controlling the norm of the queue backlog.
  • C. Preliminary Analysis and More Intuitions of Algorithm 1: The virtual-queue recurrence yields cumulative bounds by summing constraint values and using the initialization Qk(1)=0.The argument applies separately to each constraint index k.
  • C. Preliminary Analysis and More Intuitions of Algorithm 1: The quadratic regularization term makes the update objective strongly convex, ensuring a unique minimizer and enabling a movement bound.The relevant objective has strong-convexity modulus 2α.
  • C. Preliminary Analysis and More Intuitions of Algorithm 1: The update changes decisions by at most V D1 per round under the bounded loss-subgradient assumption.The bound follows by applying the update optimality relation with z = x(t).
  • C. Preliminary Analysis and More Intuitions of Algorithm 1: Small queue norms imply small constraint violations, explaining why minimizing drift is central to the algorithm’s feasibility analysis.Controlled drift is used to obtain boundedness of the stochastic queue process.

III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1

The expected-performance analysis introduces a drift lemma for stochastic processes and applies it to virtual queues. With V = √T and α = T, the resulting expected constraint violations are O(√T).

  • III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1: Choosing V = √T and α = T is the parameter scaling used to establish the expected performance bounds.The stated expectation is taken over all stochastic samples ω(t).
  • III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1: The paper proposes a drift-analysis lemma that provides both expected and high-probability bounds for stochastic processes satisfying a drift condition.The lemma is later applied to the virtual-queue norm.
  • III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1: The virtual-queue norm satisfies the drift condition for arbitrary integer lookback lengths t0, with parameters selected according to t0.This enables the stochastic-process lemma to control queue growth.
  • III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1: The filtration tracks the constraint samples observed through round t, while x(t) and Q(t) are measurable using information available before round t.This establishes the adaptedness needed for drift analysis.
  • III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1: The expected constraint analysis compares observed constraint samples with a fixed feasible point whose expected constraint vector is nonpositive.Independence between the current sample at x* and the current queue is used in the argument.
  • III. EXPECTED PERFORMANCE ANALYSIS OF ALGORITHM 1: The expected queue norm is O(√T), which yields an expected cumulative constraint-violation bound of O(√T).The constraint result follows by combining the queue bound with the earlier queue-to-violation relation.

C. Expected Regret Analysis

The regret analysis combines a drift-plus-penalty inequality with the nonpositive expected constraint term at a feasible comparator. This produces the algorithm’s expected regret bound under the prescribed parameter choice.

  • C. Expected Regret Analysis: The refined drift-plus-penalty inequality bounds cumulative loss relative to any comparator z in X0 using queue drift, regularization, and update terms.The bound includes the endpoint queue potentials and the squared movement contribution.
  • C. Expected Regret Analysis: The analysis controls the initial and terminal regularization terms using the diameter bound R and nonnegative queue potential.Initialization gives L(1)=0, while L(T+1) is nonnegative.
  • C. Expected Regret Analysis: For a feasible comparator x*, the expected contribution of the stochastic constraint term is non-positive.This removes that term when expectations are taken in the regret inequality.
  • C. Expected Regret Analysis: The expected regret bound follows by taking expectations of the refined inequality and using the feasible-comparator property.The expectation is with respect to all stochastic constraint realizations.
  • C. Expected Regret Analysis: The leading deterministic terms in the bound include T/(4α) and [G + √mD2R]^2T/(2V).These terms expose how α and V trade off in the regret analysis.

D. Special Case Performance Guarantees

Theorems 1 and 2 extend the algorithm’s expected guarantees to long-term, stochastic, and deterministic constrained optimization, while Theorems 3 and 4 provide high-probability bounds.

  • Guarantee derivation: The special-case guarantees follow from the expected performance guarantees of Algorithm 1.The paper explicitly derives these cases from Theorems 1 and 2.
  • OCO with long-term constraints: O(√T) deterministic regret and O(√T) deterministic constraint violations hold for OCO with long-term constraints.The stochastic expectations disappear because the constraint functions are deterministic.
  • Stochastic constrained convex optimization: O(1/√T) convergence is obtained for stochastic constrained convex optimization when the algorithm is used as a batch offline method.The fixed solution is formed by averaging the decisions across T slots.
  • Deterministic constrained convex optimization: O(1/√T) performance follows for deterministic constrained convex optimization after dividing the theorem bounds by T and applying Jensen’s inequality.Here both the loss and constraint functions are deterministic, so the expectations disappear.
  • High-probability guarantees: High-probability constraint bounds hold uniformly over t ∈ {1, ..., T + 1} with probability at least 1 − λ.A union bound gives Pr(∥Q(t)∥ ≤ γ for all t) ≥ 1 − λ.

B. High Probability Regret Analysis

The high-probability analysis addresses unbounded supermartingale differences caused by virtual queues and derives regret guarantees alongside an empirical data-center evaluation.

  • Analysis challenge: Unbounded virtual queues make the relevant supermartingale differences unbounded, preventing direct use of standard Hoeffding–Azuma analyses.The analysis therefore requires a concentration approach tailored to occasional large differences.
  • Concentration technique: Lemma 9 extends supermartingale concentration by allowing bounded increments to fail on events whose probabilities are controlled by p(t).When p(t)=0 for every t, the lemma reduces to the conventional Hoeffding–Azuma inequality.
  • Regret guarantee: Theorem 4 summarizes the high-probability regret guarantee for Algorithm 1 under the stated feasibility and parameter conditions.It assumes a feasible x* and uses V = √T and α = √T.
  • Empirical evaluation: The data-center experiment compares the proposed algorithm with the best fixed decision, react, and low-power strategies.The evaluation uses geo-distributed servers, time-varying electricity prices, and stochastic job arrivals.
  • Empirical evaluation: The proposed algorithm performs closely to the best fixed decision in hindsight for both electricity cost and constraint violations.React serves arrivals well but costs more, whereas low-power costs less but fails to serve arrivals.

APPENDIX A PROOF OF LEMMA 5

The appendix proves Lemma 5 by bounding an exponential moment of the queue process, then converting that bound into expectation and tail guarantees.

  • Exponential-moment bound: The proof first establishes an upper bound on E[e^(rZ(t))] for a positive constant r.Jensen’s inequality handles the expectation bound, while Markov’s inequality yields the tail bound.
  • Recursive bound: The exponential moment satisfies a recursive bound involving ρ, e^(rθ), and the block count ⌈t/t0⌉.The parameters are r = ζ/(4t0δmax^2) and ρ = 1 − ζ^2/(8δmax^2).
  • Two-case analysis: The process is analyzed separately when Z(t) is above or below a threshold θ.The large-queue case uses negative expected drift, while the small-queue case uses the bounded increment δmax.
  • Induction: Induction extends the recursive estimate from the initial time interval to all later times.The base case uses Z(τ) ≤ τδmax for τ ≤ t0.
  • Consequences: Taking logarithms and applying Markov’s inequality converts the exponential-moment estimate into expectation and probability bounds for Z(t).The proof explicitly derives the expectation statement before the tail statement.

APPENDIX B PROOF OF LEMMA 7

The appendix proves Lemma 7 using a Slater point, queue bounded differences, and negative drift when the virtual queue is sufficiently large.

  • Slater condition: A Slater point provides strictly negative expected constraint values, supplying the negative-drift condition used in the queue analysis.The condition is Eω[gk(ˆx;ω)] ≤ −ϵ for every constraint k.
  • Conditional drift: Independence of future constraint realizations from prior queue histories allows the Slater-point inequality to be conditioned on earlier information.This yields E[Qk(t1)gk,t1(ˆx) | W(t2)] ≤ −ϵE[Qk(t1) | W(t2)].
  • Queue bounds: The virtual queue has bounded one-step growth: ∥Q(t + 1)∥ ≤ ∥Q(t)∥ + G.This follows from the queue update and the bound on the constraint vector norm.
  • Queue bounds: The reverse change is also bounded by G + √mD^2R, controlling how quickly the queue norm can decrease.The bound follows from coordinate-wise queue changes and the triangle inequality.
  • Block drift: Over a t0-slot block, large queues experience negative expected drift while small queues are controlled by bounded increments.The proof combines the drift inequality with bounded distance changes from the decision updates.

APPENDIX C PROOF OF LEMMA 9

The proof truncates a supermartingale at a stopping time triggered by potentially large differences, producing a process with bounded differences. Hoeffding–Azuma is then applied while separately bounding the probability of truncation.

  • Probability bound: Hoeffding–Azuma bounds the truncated supermartingale, while a separate term accounts for the probability that truncation changes Z(t).The proof decomposes Pr(Z(t)≥z) according to whether eZ(t)=Z(t).
  • Stopping-time construction: T is a stopping time because the event that it occurs by time t is determined by the filtration through time t.The proof checks the time-zero case and then uses filtration measurability for later times.
  • Stopping-time construction: The proof defines T as the first time Y(t)>0 and truncates Z(t) as eZ(t)=Z(t∧T).This stopping-time construction ensures the truncated process differs from the original only after a trigger event.
  • Bounded truncated process: Z(t∧T) remains a supermartingale because truncation at a stopping time preserves the supermartingale property.This follows from the stated stopping-time theorem.
  • Bounded truncated process: The truncated process has differences bounded by c: before stopping, the original difference is at most c, and after stopping, the truncated process is constant.The argument handles T≤t′ and T≥t′+1 separately, using the inclusion {|Z(t+1)−Z(t)|>c}⊆{Y(t)>0}.

APPENDIX D PROOF OF THEOREM 4

The theorem proof instantiates the supermartingale argument for the queue-norm process under Algorithm 1. It uses i.i.d. stochastic constraints to establish the supermartingale property and then selects parameters to control the resulting probability terms.

  • Supermartingale construction: For any feasible fixed x*, the process Z(t) defined under Algorithm 1 is a supermartingale adapted to W(t).The construction uses Z(0)=0 and a cumulative process based on the algorithm’s constraint terms.
  • Supermartingale construction: The large-difference event satisfies {|Z(t+1)−Z(t)|>c}⊆{Y(t)>0}, with Y(t)=∥Q(t+1)∥−cG.Q(t+1) is adapted to W(t), so Y(t) is also adapted to that filtration.
  • Supermartingale construction: The supermartingale property follows because gt+1(x*) is independent of W(t) and has conditional mean ˜g(x*)≤0 under i.i.d. sampling.The proof also uses Z(t) and Q(t+1) being W(t)-measurable.
  • Parameter selection: The difference bound uses Cauchy–Schwarz together with the assumption ∥gt(x*)∥≤G.This supplies the boundedness condition needed by the preceding lemma.
  • Parameter selection: The proof chooses c and γ so that terms (I) and (II) in the probability bound are each no larger than λ.The selected c is obtained from Lemma 5, after which γ is chosen to control term (I).

APPENDIX E MORE EXPERIMENT DETAILS

The experiment models data-center scheduling with Poisson job arrivals, bounded server power, and logarithmic service rates over 2160 slots. It compares the proposed setting with hindsight-optimal, traffic-reactive, and low-power baselines.

  • Experimental setup: The simulation uses Poisson arrivals averaging 1000 jobs per slot over 2160 slots, with each server choosing power xi(t)∈[0,30].Service rate is hi(xi(t))=4 log(1+4xi(t)); the algorithm can also handle general concave service functions.
  • Baselines: The best-fixed-decision baseline selects one power vector using known electricity traces and the job-arrival distribution.Its decision is optimized from the complete 2160-slot data.
  • Baselines: React estimates arrivals from the latest five slots and evenly splits load, but it is unaware of electricity variation.The passage states that this leads to high electricity cost in the simulation.
  • Baselines: Low-power schedules to zones with the lowest estimated electricity prices but is not guaranteed to serve all arrivals because server capacity is finite.It estimates prices using five-slot averages, so unserved jobs may accumulate.
Loading 1708.03741v1…