REVIEW 9 cited by
Online Convex Optimization with Time-Varying Constraints
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Online Convex Optimization with Time-Varying Constraints
read the original 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.
Forward citations
Cited by 9 Pith papers
-
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 adversa...
-
A Geometric Approach to Constrained Online Learning
NP-OGD attains O(log T) regret and O(log T) CCV for strongly convex losses, and O(√T) for both under convex losses, with complementary geometric lower bounds.
-
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, ...
-
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.
-
Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
OGD+Projection for constrained online convex optimization has cumulative constraint violation Ω(T^{(d-1)/(2d)}) in dimension d, the first lower bound of this form.
-
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.
-
A Geometric Approach to Constrained Online Learning
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).
-
Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization
OGD with Polyak feasibility steps gets a data-dependent regret bound that replaces the worst-case gradient envelope with the observed gradient sum and subtracts the cumulative squared projection displacement.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.