PaperlayerView exact revision on arXiv

Source-linked AI summary

Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints

Mehrdad Mahdavi, Rong Jin, Tianbao Yang

arXiv:1111.6082v3cs.LG

TL;DR

The paper tackles the computational burden of projection onto complex convex domains in online convex optimization. It replaces per-round feasibility with long-term constraint satisfaction and develops online convex-concave, modified OGD, mirror-prox, and bandit algorithms. The methods achieve sub-linear regret and constraint-violation bounds under their stated settings, including O(T^2/3) for both measures on finite linear-constraint domains.

  • Problem

    Projection onto complex convex domains can be computationally expensive, so the paper studies online convex optimization with constraints enforced in the long run rather than at every round.

  • Method

    The paper formulates the problem as online convex-concave optimization and develops OGD-based, modified OGD, mirror-prox, and two-point bandit-feedback algorithms.

  • Results

    The algorithms obtain O(T^1/2) regret with O(T^3/4) violation, O(T^3/4) regret without violation, and O(T^2/3) for both measures on finite linear-constraint domains.

  • Takeaways & Limitations

    Long-term constraints provide an alternative to projecting onto complex domains at every iteration, while the bandit extension achieves the basic algorithm’s bounds in expectation using two oracle evaluations.

  • Takeaways & Limitations

    The penalty method uses a fixed weight independent of prior violations, and some alternative approaches require Hessian computation, limiting their effectiveness for the intended setting.

Abstract

from arXiv · show

In this paper we propose a framework for solving constrained online convex optimization problem. Our motivation stems from the observation that most algorithms proposed for online convex optimization require a projection onto the convex set $\mathcal{K}$ from which the decisions are made. While for simple shapes (e.g. Euclidean ball) the projection is straightforward, for arbitrary complex sets this is the main computational challenge and may be inefficient in practice. In this paper, we consider an alternative online convex optimization problem. Instead of requiring decisions belong to $\mathcal{K}$ for all rounds, we only require that the constraints which define the set $\mathcal{K}$ be satisfied in the long run. We show that our framework can be utilized to solve a relaxed version of online learning with side constraints addressed in \cite{DBLP:conf/colt/MannorT06} and \cite{DBLP:conf/aaai/KvetonYTM08}. By turning the problem into an online convex-concave optimization problem, we propose an efficient algorithm which achieves $\tilde{\mathcal{O}}(\sqrt{T})$ regret bound and $\tilde{\mathcal{O}}(T^{3/4})$ bound for the violation of constraints. Then we modify the algorithm in order to guarantee that the constraints are satisfied in the long run. This gain is achieved at the price of getting $\tilde{\mathcal{O}}(T^{3/4})$ regret bound. Our second algorithm is based on the Mirror Prox method \citep{nemirovski-2005-prox} to solve variational inequalities which achieves $\tilde{\mathcal{\mathcal{O}}}(T^{2/3})$ bound for both regret and the violation of constraints when the domain $\K$ can be described by a finite number of linear constraints. Finally, we extend the result to the setting where we only have partial access to the convex set $\mathcal{K}$ and propose a multipoint bandit feedback algorithm with the same bounds in expectation as our first algorithm.

1. Introduction

The paper addresses the computational burden of projection-based online convex optimization by allowing constraint satisfaction in the long run. It develops OGD-, modified-, mirror-prox-, and bandit-based methods with explicit regret and constraint-violation guarantees.

  • Problem setting: Online convex optimization minimizes cumulative regret against the best fixed action in hindsight, with sub-linear regret implying Hannan consistency.Hannan consistency means the learner’s average per-round loss approaches that of the best fixed action in hindsight.
  • Motivation: Projection onto complex convex domains can be computationally expensive, motivating online decisions that need not remain feasible at every round.The paper specifically notes the cost of projection for domains such as the positive semidefinite cone and describes complex-domain projection as computationally burdensome.
  • Problem setting: The proposed long-term-constraint formulation replaces per-round feasibility with constraints satisfied by the overall sequence at a vanishing convergence rate.This avoids solving the projection problem on every round while retaining a long-run constraint requirement.
  • Algorithms and guarantees: O(T^1/2) regret and O(T^3/4) constraint violation are achieved by an OGD-based algorithm derived from an online convex-concave formulation.A penalty-based strategy instead fails to obtain sub-linear bounds for both regret and long-term constraint violation simultaneously.
  • Algorithms and guarantees: O(T^3/4) regret with no constraint violation is obtained by modifying the OGD-based algorithm to satisfy constraints exactly in the long run.The modification addresses the trade-off between regret and constraint violation in the basic approach.
  • Algorithms and guarantees: O(T^2/3) regret and constraint violation are achieved by a mirror-prox algorithm for domains described by finitely many linear constraints.A two-point value-oracle bandit version of the basic algorithm retains O(T^1/2) regret and O(T^3/4) violation in expectation.

2. Notation and Setting

The setting minimizes online regret against a fixed decision while requiring convex constraints to hold cumulatively rather than at every round. Analysis assumes bounded domains, Lipschitz losses and constraints, known finite horizon, and standard Bregman-divergence notation.

  • Assumptions: The constraint domain K is represented as an intersection of finitely many convex constraints with Lipschitz-continuous functions.The analysis assumes K can be written using functions g_i, i ∈ [m].
  • Notation: The analysis uses Euclidean and ℓ1 norms, conditional expectations, and Bregman divergence notation.Bregman divergence measures deviation from a function’s linear approximation at a reference point.
  • Assumptions: K is bounded between scaled Euclidean balls, with rB ⊆ K ⊆ RB for constants R > 0 and r < 1.This bounded-domain assumption follows the standard setup used in online convex optimization.
  • Problem formulation: The learner minimizes regret relative to a fixed decision while satisfying each constraint cumulatively over T rounds.The long-term requirement is expressed as Σ_t=1^T g_i(x_t) ≤ 0 for every constraint i.
  • Problem formulation: Decisions are drawn from a ball B containing K, rather than necessarily from K at every round.The finite-horizon formulation explicitly distinguishes the decision ball B from the feasible domain K.
  • Assumptions: Loss and constraint functions are Lipschitz continuous on B, with constants L_f and L_g summarized by G = max{L_f, L_g}.The same regularity assumption applies to every online loss and fixed constraint function.

3. Online Convex Optimization with Long Term Constraints

The paper replaces per-round projection with long-term constraint satisfaction and formulates the problem as online convex-concave optimization. Its gradient-based algorithms adapt constraint weights, provide sublinear regret and violation bounds, and can enforce zero long-run violation at a higher regret cost.

  • Penalty limitation: A fixed penalty weight cannot achieve sublinear regret and sublinear long-term constraint violation simultaneously.The failure arises because the penalty constant is fixed independently of previous violations.
  • Problem formulation: The proposed framework allows constraint violations on some rounds while requiring the cumulative constraints to converge to feasibility in the long run.This avoids requiring every decision to lie in the convex domain at every iteration.
  • Adaptive gradient method: Algorithm 1 converts the problem into online convex-concave optimization and updates both decisions and Lagrangian multipliers.Unlike fixed penalties, the multiplier updates automatically adjust constraint weights as violations accumulate.
  • Exact long-run feasibility: O(T^3/4) regret with zero long-run constraint violation is obtained by modifying the algorithm with an appropriate γ-dependent construction.The modification uses γ = bT^-1/4 and guarantees the global constraints under the stated assumptions.

4. A Mirror Prox Based Approach

The mirror prox approach treats the constrained problem as a variational inequality and improves the joint regret–violation rate when the domain is described by finitely many linear constraints. A related modification can enforce the constraints exactly in the long run.

  • Variational-inequality formulation: The mirror prox method reduces the online convex-concave problem to approximating a saddle point through an associated variational inequality.This approach is introduced to improve the constraint-violation bound.
  • Assumptions: The method assumes the convex domain is represented by finitely many linear constraints with normalized constraint vectors.Under this setting, the relevant operator has a Lipschitz continuous gradient.
  • Mirror prox algorithm: Algorithm 2 uses auxiliary variables and separate functions for computing iterates and updating those auxiliary variables.This distinguishes the mirror prox updates from the gradient-based algorithm.
  • Rates: For polyhedral domains, projection onto the polyhedral set can be replaced by projection onto a containing ball while retaining O(T^2/3) regret.The constraints are satisfied in the long run under the stated assumptions.

5. Online Convex Optimization with Long Term Constraints under Bandit Feedback for Domain

The bandit extension addresses settings where the learner lacks the exact constraint domain and receives constraint feedback through oracle queries. It estimates gradients using two randomized evaluations and matches the first algorithm’s bounds in expectation.

  • Partial constraint access: The bandit setting exposes only a containing ball and provides the maximum constraint violation of each submitted solution through an oracle.The exact definition of the feasible domain is not available to the learner.
  • Two-point feedback: The algorithm smooths the constraint function so that it is differentiable even when the original constraint function is not.The smoothed function retains the same Lipschitz constant G.
  • Two-point feedback: Algorithm 3 estimates constraint gradients by querying the constraint function at two points symmetrically around the current decision.The two-point estimator has a bounded norm independent of the exploration radius ζ.
  • Domain handling: The randomized iterates are restricted to (1−ξ)B so both exploration points remain inside the available ball.The exploration radius must be small enough relative to the distance from the boundary.
  • Guarantees: The bandit algorithm provides expected regret and expected long-term constraint-violation bounds corresponding to the gradient-based approach.It is described as a slight modification of Algorithm 1 using two constraint-function evaluations.

6. Conclusion

The paper frames constrained online convex optimization around satisfying constraints in the long run, including settings with limited domain access and linear constraints. It identifies improved regret and violation bounds, optimal lower bounds, stronger curvature assumptions, and relaxed exact-feasibility requirements as open directions.

  • 6. Conclusion: The framework addresses online convex optimization where constraints need only be satisfied in the long run, avoiding projection onto complex convex domains at every iteration.It turns the problem into online convex-concave optimization and applies online gradient descent.
  • 6. Conclusion: The paper proposes efficient algorithms for allowed violation, exact long-run satisfaction, limited domain access, and domains defined by linear constraints.The mirror prox method gives an O(T^2/3) bound for both regret and constraint violation in the linear-constraint setting.
  • 6. Conclusion: Improving the bounds remains open, including obtaining an O(T^1/2) regret bound and better than O(T^3/4) constraint violation for general convex domains.The paper also leaves open optimal lower bounds and extensions to strongly convex loss or constraint functions.
  • 6. Conclusion: Relaxing the assumption that constraints must be exactly satisfied in the long run is identified as another direction for future work.This is stated alongside stronger-curvature extensions and lower-bound questions.

Appendix A. Proof of Theorem 1

The proof analyzes online gradient descent applied to modified loss functions combining the original loss with a constraint penalty. It establishes separate regret and violation behavior, including a linear-violation failure mode for certain parameter choices.

  • Appendix A. Proof of Theorem 1: For δ < 1, a linear constraint and linear loss can produce constraint violation linear in T when the algorithm starts infeasible.The construction uses ft(x) = w⊤x and g(x) = 1−w⊤x.
  • Appendix A. Proof of Theorem 1: For strongly convex losses, the constrained and penalized optima differ when the loss gradient at the constrained optimum is nonzero and λ < δ.Strong convexity gives a positive objective gap Δ between the penalized and constrained optima.
  • Appendix A. Proof of Theorem 1: The proof applies OGD to modified losses ˆft(x), updating with their gradients instead of the original loss gradients.The analysis uses a standard OGD lemma and bounds the modified-gradient norm before optimizing the step size η.
  • Appendix A. Proof of Theorem 1: The penalty-based analysis shows that recovering an O(T^1/2) regret bound requires constant δ, which yields O(T) long-term constraint violation.Thus the parameter choice cannot achieve sublinear bounds for both quantities simultaneously in this analysis.

Appendix B. Proof of Corollary 13

The proof substitutes the stated parameter values into the established inequalities and simplifies the resulting expressions for regret and constraint violation. For sufficiently large T, it obtains the zero-violation guarantee.

  • Appendix B. Proof of Corollary 13: Setting η = δ = T^-1/3 and γ = bT^-1/3 yields the stated regret bound after combining the theorem inequalities.The proof first applies the parameter values and invokes the theorem bound.
  • Appendix B. Proof of Corollary 13: The intermediate bound contains terms R^2T^1/3, G^2T^2/3, and FT before simplification.These terms are used to derive the constraint-violation result.
  • Appendix B. Proof of Corollary 13: When FT ≥ R^2T^1/3 + G^2T^2/3 for sufficiently large T, the proof guarantees zero constraint violation.The simplification relies on the stated dominance condition.
Loading 1111.6082v3…