Source-linked AI summary
Fast Algorithms for Online Stochastic Convex Programming
Shipra Agrawal, Nikhil R. Devanur
TL;DR
The paper studies online stochastic convex programming with arbitrary concave objectives and convex feasibility constraints, encompassing problems such as stochastic packing, covering, and matching with concave returns. It develops fast primal-dual algorithms using online learning and Fenchel-duality ideas for i.i.d. and random-permutation inputs. For online packing, the method achieves a competitive ratio of 1 − O(ε) with fast updates and at most one sample LP solve.
Problem
Existing essentially linear online matching and packing formulations do not capture practical concave underdelivery objectives and convex diversity penalties.
Method
The paper develops fast primal-dual algorithms for general online stochastic convex programs, using online-learning procedures and explicit duality-based analysis.
Results
1 − O(ε) competitive ratio is achieved for online stochastic packing in the random permutation model, with fast per-step updates and at most one sample LP solve.
Takeaways & Limitations
The framework unifies broad stochastic online problems and provides practical algorithms that combine strong guarantees with low per-step computation.
Takeaways & Limitations
The packing guarantee ignores the error from using initial requests as samples, and the general analysis includes an extra log T regret factor from a union bound.
Abstract
from arXiv · showhide
We introduce the online stochastic Convex Programming (CP) problem, a very general version of stochastic online problems which allows arbitrary concave objectives and convex feasibility constraints. Many well-studied problems like online stochastic packing and covering, online stochastic matching with concave returns, etc. form a special case of online stochastic CP. We present fast algorithms for these problems, which achieve near-optimal regret guarantees for both the i.i.d. and the random permutation models of stochastic inputs. When applied to the special case online packing, our ideas yield a simpler and faster primal-dual algorithm for this well studied problem, which achieves the optimal competitive ratio. Our techniques make explicit the connection of primal-dual paradigm and online learning to online stochastic CP.
1 Introduction
The paper extends stochastic online optimization to general convex programs with concave objectives, while developing fast algorithms for both i.i.d. and random-permutation inputs. Its primal-dual methods connect online learning with these problems and improve practical efficiency for online packing.
- Motivation: Online advertising motivates convex-programming extensions because underdelivery and diversity penalties create concave objectives and convex penalties beyond essentially linear formulations.The framework is designed to incorporate these practical extensions to online matching and packing/covering.
- Contributions: For online packing, the algorithm requires solving only a single LP, reducing per-step computation for real-time allocation decisions.The improvement follows because estimation error affects only second-order error bounds.
- Techniques: The analysis makes a formal connection between online stochastic convex programming and online learning through black-box low-regret algorithms.The paper also argues that primal-dual algorithms are as powerful as primal-only approaches in this setting.
- Contributions: The paper presents algorithms with optimal guarantees for a general online convex programming problem in a stochastic setting.
- Contributions: The primal-dual algorithms are fast, simple, and applicable to the random permutation model, while their analysis formalizes its similarity to the i.i.d. model.This addresses the prior gap between fast i.i.d. algorithms and slower or weaker random-permutation methods.
- Related work: The work builds on stochastic-model research targeting competitive-ratio convergence and relates online packing to Bandits with Knapsacks and Blackwell approachability.These neighboring problems differ in their persistence of choices and observation structure, while sharing related online-learning ideas.
2 Problem definition and main results
Online stochastic Convex Programming generalizes stochastic online optimization to concave objectives and convex feasibility constraints. The paper develops regret guarantees in the random-permutation model and a fast online-packing algorithm with near-optimal competitive performance.
- Online stochastic Convex Programming maximizes a concave objective over choices whose average satisfies convex feasibility constraints.
- Stochastic input models: The random-permutation model presents fixed input sets in uniformly random order, while the i.i.d. model draws independent samples from an unknown distribution.
- Benchmarks and regret: The benchmark is the optimal offline solution, and performance is measured mainly by additive average regret for objectives and constraint violations.
- Main results: Theorem 2.1 gives regret guarantees for online stochastic CP in the random-permutation model, with norm-dependent C and problem-dependent Z and L.
- Main results: High-probability versions add a √log T factor, although a more careful analysis may remove it in some cases.
- Online packing: 1 − O(ε) competitive ratio; the online-packing algorithm uses fast per-step updates and solves a sample LP at most once under the stated condition.
3 Preliminaries
The preliminaries connect Fenchel duality, strong convexity and smoothness, and online convex optimization. These tools provide fast online-learning updates with norm- and curvature-dependent regret bounds.
- Fenchel duality: Fenchel conjugacy converts convex functions and distance-to-set penalties into dual representations used by the algorithms.
- Strong convexity and smoothness: Strong convexity and strong smoothness are defined relative to a norm and are linked through Fenchel conjugation.
- Online learning: Online Convex Optimization chooses decisions from a domain using only previous observations and evaluates regret against the best fixed decision in hindsight.
- Online learning: OCO methods such as online mirror descent and gradient descent provide fast per-step updates with regret depending on domain diameter and gradient bounds.
- Online learning: For gt(θ) = θ · z − h∗(θ), regret scales as O(L√(dT)) for Euclidean norm and O(L√(log(d)T)) for L∞.
- Online learning: Multiplicative weights are especially fast on the simplex, while strongly concave losses can yield logarithmic regret bounds.
4 Feasibility Problem
The feasibility algorithm combines per-request minimization with online learning over dual variables. Fenchel duality and random-permutation concentration yield regret bounds for keeping the average decision near the feasible set.
- Feasibility problem: The feasibility problem has no objective function and seeks choices whose average lies in, or remains close to, a convex set S.
- Algorithm: The algorithm minimizes θt · v over each arriving option set and updates θt+1 using an OCO rule based on the selected vector.
- Algorithm: The per-step updates are simple and fast and do not require solving complex optimization problems.
- Guarantee: Theorem 4.1 establishes a random-permutation regret bound involving OCO regret and the coordinate bound s.
- Analysis: The random-permutation analysis conditions on the observed prefix and uses concentration for sampling without replacement.
- Guarantee: The gap between the i.i.d. and random-permutation models is characterized by an sT log(d) term, while high-probability bounds add logarithmic factors.
5 Online stochastic convex programming
The general CP algorithm linearizes both objectives and constraints through Fenchel duality and estimates dual variables with online learning. A parameter Z balances objective value against constraint violation without requiring precise OPT estimation.
- Motivation: Reducing general CP directly to feasibility would require knowing OPT, and repeated OPT-estimation errors could accumulate into regret.
- Algorithm: Z captures the objective–constraint tradeoff, appears only in second-order regret terms, and therefore needs only a constant-factor approximation.
- Online packing: For online packing, a constant-factor approximation of OPT suffices, and the resulting algorithm achieves the optimal competitive ratio with a single LP solve.
- Dual interpretation: OPTδ is non-decreasing and concave in constraint violation δ, and its derivative at zero equals the optimal dual variable for the distance constraint.
- Algorithm: The algorithm linearizes objectives and constraints with Fenchel duality, estimates dual variables through OCO, and combines them using parameter Z.
- Linear objectives: For linear objectives, Algorithm 5.2 selects reward–vector pairs using dual penalties and updates the constraint dual variable with OCO.
- Guarantees: Theorem 5.1 provides random-permutation regret bounds scaling with O(R(T) + Q(T)), where R(T) is OCO regret and Q(T) captures additional terms.
6 Online stochastic packing
The online stochastic packing algorithm estimates a problem-dependent parameter from an initial sample, then uses a primal-dual procedure with fast updates and at most one sample LP. Under a stated scale condition, it achieves competitive ratio 1 − O(ε) in the random permutation model.
- Algorithm: The algorithm stops when a budget constraint is breached, ensuring that online packing budgets are not violated.This modification distinguishes packing from the general online CP setting, which permits small constraint violations.
- Algorithm: The parameter Z captures the tradeoff between objective value and constraint distance in the online CP framework.For packing, the algorithm uses Z in its per-request maximization rule.
- Caveat: The initial sample requests must technically be ignored, but their O(ε^2 log(1/ε)) fraction contributes only a small error relative to the 1 − O(ε) guarantee.The paper omits this error from the presentation for simplicity.
- Guarantee: 1 − O(ε) competitive ratio holds when min{B, T OPT} ≥ log(d)/ε^2.This guarantee applies in the random permutation model for any ε > 0.
- Algorithm: The algorithm estimates Z from the first O(ε^2 log(1/ε)) requests and solves an LP only once.The sample-based estimate is designed to provide the accuracy required by the analysis.
7 Stronger bounds for smooth functions
For smooth objectives and constraint penalties, the paper uses online learning on gradient domains to obtain stronger regret bounds. In the i.i.d. model, strong smoothness yields logarithmic online-learning regret and improved problem-level guarantees.
- Stronger bounds: Strongly smooth functions yield stronger regret bounds, including ˜O(log T) terms in the smooth setting.The improvement relies on using a strongly smooth function for the objective and for measuring constraint violation.
- Problem formulation: The smooth formulation assumes a β-smooth concave utility function and a β-smooth convex constraint function.The paper also states that Lipschitzness is not required for these functions.
- Algorithm: The algorithm performs online learning for the objective and constraint terms over the gradient domains ∇g and ∇f.These domains are assumed convex and easy to project onto.
- Guarantee: Under Assumption 2 and a suitable Z, Algorithm 7.1 achieves the stated regret guarantee for online smooth CP with i.i.d. inputs.The algorithm updates θ and φ through online-convex-optimization steps after selecting each action.
- Guarantee: In the i.i.d. case, the online-learning components have regret O(∥1_d∥^2β log T).This follows from strong concavity of the dual online objectives and the corresponding smooth-function learning guarantees.
- Limitation: The analysis requires Assumption 2 because strong convexity is established only on the gradient domains ∇g and ∇f.The paper conjectures that this assumption may be removable.
B.1 Strong smoothness/Strong convexity duality.
This appendix connects strong smoothness of a function with strong convexity of its conjugate, enabling logarithmic regret guarantees for the smooth online CP setting. It also identifies standard online mirror descent updates and guarantees used by the analysis.
- Strong smoothness/Strong convexity duality: Strong smoothness implies strong convexity of the corresponding conjugate on the relevant gradient domain.The proof uses conjugate identities and the strong smoothness inequality.
- Strong smoothness/Strong convexity duality: The conjugate relationship supplies the curvature needed for online learning over gradient domains.This curvature is what supports stronger regret bounds for the smooth case.
- Online mirror descent: Online mirror descent selects the next decision using a regularizer through a fast update rule.When the domain is an Euclidean ball and the regularizer is squared Euclidean distance, the method becomes online gradient descent.
- Online mirror descent: The analysis assumes bounded subgradients and a 1-strongly-convex regularizer with respect to the dual norm.These conditions underlie the stated online mirror descent guarantees.
- Online mirror descent: For an ℓ1-constrained nonnegative domain, the entropic regularizer supplies the corresponding online learning update.The appendix contrasts this with the Euclidean regularizer used on an ℓ2 domain.
D Proof of Lemma 5.1
The proof characterizes the perturbed offline optimum as a concave function of the allowed constraint distance. Its gradient is the optimal dual variable associated with that distance constraint.
- Perturbed optimum: The offline optimum OPT_δ is a non-decreasing concave function of the constraint-distance allowance δ.This follows from its dual representation.
- Dual representation: For convex request sets, the support function of their convex hull equals the support function of the original request set.This lets the proof replace h_Conv(X_t) with h_X_t in the optimization expression.
- Perturbed optimum: The gradient of OPT_δ is the optimal dual variable λ*(δ) for the distance constraint.The dual variable is nonnegative because increasing the allowed distance cannot reduce the optimum.
- Dual representation: At δ = 0, λ* is the optimal dual variable for the unperturbed offline optimum.The proof uses this identification to complete the lemma.
E Proof of Theorem 2.1
The proof establishes Theorem 2.1 by combining regret inequalities, Assumption 1, and online convex optimization guarantees.
- Theorem E.1 gives Algorithm 5.1 regret bounds for online stochastic CP in the random-permutation model.
- The bound combines regret contributions R(T) and Q(T), with an additional term involving R′(T) and sT log(d).R′(T) is the OCO regret bound for ψ_t(·), R(T) is the OCO regret bound for g_t(·), and s bounds coordinates in S.
- Substituting the OCO regret bounds from Corollary 3.1 completes the connection to Theorem 2.1.
- Assumption 1 is used to upper-bound the algorithm’s reward using OPT and the distance from S.
- Combining the inequalities and applying norm bounds on φ_t and θ_t yields the desired lemma and theorem statements.The proof uses ||φ_t||∗ ≤ L and ||θ_t||∗ ≤ 1.
F Estimating the parameter Z
This section estimates the unknown parameter Z using random-permutation samples and phased restarts, preserving the order of regret guarantees up to stated factors.
- Z∗ equals the minimum feasible value and the optimal dual variable, while choosing Z = O(Z∗ + L) gives low-regret bounds.
- Regret with estimated Z: Algorithm 5.1 with an admissible Z achieves objective regret O((Z∗ + L)γ) and constraint regret O(γ).
- Estimating Z: Algorithm F.1 divides time into exponentially growing phases and recomputes Z from observations in the preceding phase-length sample.The phases have sizes 1, 2^1, 2^2, …, and Algorithm 5.1 is rerun within each phase.
- Estimating Z: The random-permutation model makes the first n observations a random sample, enabling concentration-based guarantees for the Z estimate.
- Final guarantee: Theorem F.1 states that the phased algorithm obtains objective regret O((Z∗ + L)T) and constraint regret (Z∗ + L) ˜O(T).
- Concentration lemmas: For δ ≥ γ, the supporting lemmas establish the required high-probability inequalities used to control the estimated parameter.
- Concentration lemmas: The analysis bounds sampled primal solutions through concentration and relates nearby feasible regions using the L-Lipschitz property of f.
G Proof of Lemma 6.3
The proof of Lemma 6.3 analyzes a sampled packing instance through scaled primal and dual programs, using concentration and union bounds to establish feasibility and value bounds.
- Primal bound: The offline optimal primal solution restricted to the sample is used to construct a feasible solution for the scaled problem.
- The analysis samples a δ fraction of requests and defines a scaled optimization problem whose optimum is denoted ˆOPT.
- Concentration: Chernoff-Hoeffding concentration bounds control the sampled objective and each coordinate, with failure probabilities combined by a union bound.
- Dual bound: The optimal dual solution of the original packing instance is used to derive the corresponding dual bound for the scaled optimization problem.
- Conclusion: The proof obtains a lower bound relating the sampled optimum to δ ˆOPT.