Source-linked AI summary
Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
Rodolphe Jenatton, Jim Huang, Cédric Archambeau
TL;DR
The paper addresses online convex optimization when constraints need only hold cumulatively, allowing intermediate violations. It introduces adaptive online gradient descent based on a saddle-point formulation, achieving tunable regret and violation bounds without advance knowledge of T. The analysis applies to convex losses and arbitrary convex constraint sets, with experiments validating the approach in two online-learning tasks.
Problem
The problem is to control cumulative regret while satisfying constraints only over an accumulated horizon, rather than enforcing feasibility every round.
Method
The method uses an adaptive saddle-point algorithm whose step sizes and regularization parameter depend on the round.
Results
O(T^2/3) bounds hold for both cumulative loss and constraint violations without knowing T in advance, while the trade-off parameter β enables other bounds.
Takeaways & Limitations
The approach supports arbitrary convex constraint sets and is empirically compared with prior methods on two online-learning problems.
Takeaways & Limitations
The analysis currently relies on enclosing X within a simpler convex set B, leaving principled selection and its impact on regret bounds for future work.
Abstract
from arXiv · showhide
We present an adaptive online gradient descent algorithm to solve online convex optimization problems with long-term constraints , which are constraints that need to be satisfied when accumulated over a finite number of rounds T , but can be violated in intermediate rounds. For some user-defined trade-off parameter $β$ $\in$ (0, 1), the proposed algorithm achieves cumulative regret bounds of O(T^max{$β$,1--$β$}) and O(T^(1--$β$/2)) for the loss and the constraint violations respectively. Our results hold for convex losses and can handle arbitrary convex constraints without requiring knowledge of the number of rounds in advance. Our contributions improve over the best known cumulative regret bounds by Mahdavi, et al. (2012) that are respectively O(T^1/2) and O(T^3/4) for general convex domains, and respectively O(T^2/3) and O(T^2/3) when further restricting to polyhedral domains. We supplement the analysis with experiments validating the performance of our algorithm in practice.
1 Introduction
The paper studies online convex optimization with long-term constraints, where cumulative constraint violations matter alongside regret and per-round feasibility may be unnecessarily costly. It proposes an adaptive saddle-point algorithm with tunable regret–violation trade-offs and bounds that improve prior results while supporting arbitrary convex domains.
- Online convex optimization models repeated decisions against changing loss functions, with the learner choosing x_t from a compact convex set before incurring f_t(x_t).
- The learner minimizes cumulative regret relative to the best fixed vector x⋆ chosen in hindsight.
- Per-round projection can be computationally expensive for general convex sets, while applications may only require cumulative constraint satisfaction.
- The proposed adaptive algorithm uses a saddle-point formulation with step sizes and regularization depending on the round.
- O(T^2/3) bounds hold for both cumulative loss and constraint violations without knowing T in advance, while arbitrary convex constraint sets remain admissible.
- The algorithm interpolates between loss and constraint-violation bounds and is empirically evaluated on doubly stochastic matrix estimation and sparse logistic regression.
2 Online Convex Optimization with Long-term Constraints
The problem combines convex per-round losses with convex constraint functions and seeks an online sequence that minimizes cumulative loss while satisfying aggregate constraints. The formulation assumes boundedness and Lipschitz or subgradient conditions shared with prior work.
- The feasible set is induced by m convex constraint functions g_j: R^d → R.
- The bounded set X is enclosed in a Euclidean ball B with radius R.
- The loss and constraint functions are convex, Lipschitz continuous, and not generally assumed differentiable, with bounded subgradients.
- Constraint functions are assumed bounded over B, and the full assumption set is equivalent to that in prior work [15].
- The learner’s sequence x_t and incurred losses f_t(x_t) define an online optimization problem with a long-term constraint.
3 Adaptive Online Algorithms based on a Saddle-point Formulation
The paper develops an adaptive saddle-point algorithm that alternates primal descent and dual ascent for online convex optimization with long-term constraints. Its parameter choices yield tunable sublinear loss and constraint-violation bounds, including a no-violation regime under additional assumptions.
- 3 Adaptive Online Algorithms based on a Saddle-point Formulation: The saddle-point formulation aggregates the m convex constraints into one function g and alternates minimization over x with maximization over λ.The aggregated function preserves the relevant subdifferentiability, bounded-gradient, and bounded-value properties.
- 3 Adaptive Online Algorithms based on a Saddle-point Formulation: The algorithm alternates primal descent in x with dual ascent in λ using Euclidean projections and round-dependent step sizes.The updates use η_t for x and μ_t for λ, while θ_t acts as a round-dependent regularization parameter.
- 3.1 Main Results: The adaptive parameter sequences must satisfy three sufficient conditions controlling step-size decrease, coupling, and validity of the updates.The conditions account for the asymmetry between bounded primal iterates and potentially unbounded dual variables.
- 3.1 Main Results: Strongly convex losses admit tighter cumulative regret bounds than Theorem 1, while retaining the same leading terms.The corresponding η_t, μ_t, and θ_t instantiations are listed in Table 1.
- 3.1 Main Results: The method matches mirror-prox guarantees while applying to general convex constraint sets, and β = 3/4 gives O(T^3/4) loss regret with O(T^5/8) violations.The trade-off parameter can recover prior bounds at β = 1/2 while defining other loss–violation trade-offs.
- 3.2 Analysis and Proofs: The analysis derives the guarantees by exploiting strong concavity in the dual variable and combining upper and lower bounds on saddle-function variations.The proof verifies the sufficient conditions for the proposed θ_t, μ_t, and η_t sequences and uses telescoping sums.
- 3.3 Towards No Violation of Constraints: Under an additional lower-bound condition on constraint-function variations, setting γ = c1T^(−β/2) yields no constraint violations, with β = 2/3 minimizing the resulting O(T^2/3) regret.This extension applies to general convex domains rather than only polyhedral domains.
4 Experiments
The experiments evaluate adaptive online gradient descent on doubly-stochastic matrix estimation and sparse online binary classification, comparing it with methods from prior work. Across these settings, the reported figures examine cumulative loss regret and constraint regret, with several practical differences between methods.
- Experimental setup: Two experiments evaluate the algorithms: doubly-stochastic matrix estimation and sparse online binary classification with an elastic-net constraint.The classification experiments use the ijcnn1 and covtype datasets.
- Experimental setup: The comparisons include Convex A-OGD, Strongly convex A-OGD, Convex OGD, and Convex mirror prox.Convex and strongly convex A-OGD both have theoretical O(T^2/3) bounds for loss and constraint regret.
- Doubly-Stochastic Matrices: The doubly-stochastic matrix experiment averages results over 10 random sequences for T = 1000 iterations with d = 64.Offline solutions for computing regret are obtained using CVXPY.
- Doubly-Stochastic Matrices: Strongly convex A-OGD achieves lower cumulative regret than Convex A-OGD in the matrix experiment, especially for the long-term constraint.The analysis did not establish tighter bounds for Strongly convex A-OGD in this setting.
- Doubly-Stochastic Matrices: Mirror prox does not decrease cumulative regret at the same rate as Convex A-OGD in the matrix experiment, possibly because its guarantees require very large T.The cited discussion attributes this explanation to the theoretical guarantee conditions for mirror prox.
- Sparse Online Binary Classification: In sparse classification, the constraint is not violated on average and the iterates remain feasible within the elastic-net domain.This tendency is reported as more pronounced for Convex OGD.
- Sparse Online Binary Classification: Convex A-OGD achieves lower cumulative loss regret than Convex OGD despite its predicted O(T^2/3) loss bound versus O(T^1/2) for Convex OGD.The paper relates this observation to the larger A-OGD step sizes enabling faster progress.
5 Discussion
The discussion considers extending the adaptive method through coordinate-wise step sizes, alternative penalty functions, and better enclosing sets for the constraint domain. It identifies penalty design and enclosure selection as directions for future work.
- Broader families of step sizes: A diagonal matrix of coordinate-wise step sizes could update each coordinate of x separately and adaptively.This generalizes the single-step-size projected gradient update.
- Better penalties: Alternative smooth, 1-strongly-convex penalty functions could potentially yield lower cumulative regret guarantees.The proposed saddle-point formulation leads to a differential inequality constraining admissible penalties.
- Better penalties: The admissible penalty family must grow at least quadratically and exceed its squared first derivative, excluding a softmax penalty.The analysis also introduces the Moreau envelope of the Fenchel conjugate in the maximization step.
- Better penalties: The study of admissible penalties that minimize the regret bound is deferred to future work.For the squared ℓ2 norm over Ω = R+, the inverse mapping scales as u 7→√u.
- Enclosing sets: The current analysis keeps iterates in a simpler enclosing convex set B ⊇ X instead of projecting onto X at every update.The paper uses an Euclidean ball for B and proposes tighter enclosing sets as a future direction.
- Enclosing sets: A principled choice of the enclosing set B and its effect on regret bounds remain open research questions.The motivation is to preserve computational advantages while possibly tightening the enclosure.