A primal-dual framework with adaptive dual regularizer achieves O(√T) regret and O(√T log T) constraint violation for constrained OCO without Slater's condition under stochastic constraints, with extensions to adversarial constraints and strongly convex losses.
Online Convex Optimization with Time-Varying Constraints
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
abstract
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 $\epsilon>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 $\epsilon$ 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/\epsilon^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 $\epsilon$ of optimality with respect to the best (possibly time-varying) causal policy that knows the full probability distribution.
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 6roles
background 1polarities
background 1representative citing papers
For convex losses in nested evolving feasible sets, a lazy algorithm balances O(T^{1-β}) regret with O(T^β) movement for any β; for strongly convex or sharp losses, Frugal achieves zero regret with O(log T) movement, shown optimal by matching lower bound.
A modular reduction from budget-constrained contextual bandits with adversarial contexts to unconstrained bandits via surrogate rewards, yielding improved guarantees and an efficient algorithm based on SquareCB.
Establishes a noise-adaptive high-probability regret bound scaling with noise level σ for full-info OCO, a linear log(1/δ) lower bound for bandit feedback, and joint regret-violation bounds for constrained OCO.
A projection-based algorithm for COCO achieves O(log T) regret and O(log T) CCV for strongly convex losses and O(sqrt(T)) for convex losses by leveraging self-contracted curves.
OSPHG algorithm achieves sub-linear (1-1/e)-regret and sub-linear budget violation for online DR-submodular maximization with long-term budgets when W = o(T).
citing papers explorer
-
Constrained Online Convex Optimization without Slater's Condition
A primal-dual framework with adaptive dual regularizer achieves O(√T) regret and O(√T log T) constraint violation for constrained OCO without Slater's condition under stochastic constraints, with extensions to adversarial constraints and strongly convex losses.
-
Convex Optimization with Nested Evolving Feasible Sets
For convex losses in nested evolving feasible sets, a lazy algorithm balances O(T^{1-β}) regret with O(T^β) movement for any β; for strongly convex or sharp losses, Frugal achieves zero regret with O(log T) movement, shown optimal by matching lower bound.
-
Constrained Contextual Bandits with Adversarial Contexts
A modular reduction from budget-constrained contextual bandits with adversarial contexts to unconstrained bandits via surrogate rewards, yielding improved guarantees and an efficient algorithm based on SquareCB.
-
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Establishes a noise-adaptive high-probability regret bound scaling with noise level σ for full-info OCO, a linear log(1/δ) lower bound for bandit feedback, and joint regret-violation bounds for constrained OCO.
-
Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction
A projection-based algorithm for COCO achieves O(log T) regret and O(log T) CCV for strongly convex losses and O(sqrt(T)) for convex losses by leveraging self-contracted curves.
-
Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints
OSPHG algorithm achieves sub-linear (1-1/e)-regret and sub-linear budget violation for online DR-submodular maximization with long-term budgets when W = o(T).