A Geometric Approach to Constrained Online Learning

Dhruv Sarkar; Abhishek Sinha

cs.LGMay 20, 2026

A Geometric Approach to Constrained Online Learning

Authors: Dhruv Sarkar, Abhishek Sinha

Organizations: Indian Institute of Technology Kharagpur · Mohamed bin Zayed University of Artificial Intelligence · Tata Institute of Fundamental Research, Mumbai

Abstract

We study constrained online convex optimization with adversarial time-varying constraints. At each round the learner acts before observing the loss and constraint, and is compared with the best fixed action satisfying all constraints in hindsight. The goal is to obtain minimax-optimal regret while controlling cumulative constraint violation (CCV). Prior algorithms achieved $O(\log T)$ regret with $O(\sqrt{T\log T})$ CCV for strongly convex losses, and $O(\sqrt{T})$ regret with $O(\sqrt{T}\log T)$ CCV for convex losses. We propose NP-OGD, an iterated nested-projection algorithm. For strongly convex losses it achieves $O(\log T)$ regret and $O(\log T)$ CCV; for convex losses it achieves $O(\sqrt{T})$ regret and $O(\sqrt{T})$ CCV. The analysis relies on a geometric movement bound: after lifting the nested projected-gradient trajectory to one higher dimension, the lifted path is self-contracted under a nonstandard norm, so a finite-length theorem for self-contracted curves controls the total projection movement. We also prove complementary lower bounds using layered sphere packings. For strongly convex losses, any online algorithm with polynomially sublinear regret can incur CCV at least $Ω((\log T)^{(d-1)/(d+1)}/\log\log T)$ . For convex losses, we prove CCV lower bounds $Ω(T^{(d-1)/(2(d+3))})$ for weakly adaptive algorithms and $Ω(T^{(d-1)/(2d)})$ for NP-OGD. Finally, for the constrained experts special case over $N$ experts, an active Hedge algorithm attains $O(\sqrt{T\log N})$ regret and $O(N)$ CCV, with a matching minimax CCV lower bound for sufficiently large horizons.

Explore similar work

Jul 12, 2026cs.LG

Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action

x_t \in \mathcal{X} \subset \mathbb{R}^d

, a convex loss function

f_t

and a convex constraint function

g_t

that drives the constraint

g_t(x)\le 0

are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions

f_t

and

g_t

for all

t

ahead of time, and chooses a static optimal action that is feasible with respect to all

g_t(x)\le 0

. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of

O(\sqrt{T})

and CCV of

O(T^{1/3})

for

d=2

[Balasundaram et al., 2026], and simultaneous regret of

O(\sqrt{T})

and CCV of

O(\sqrt{T})

for any

d

[Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is

Ω(T^{\frac{d-1}{2d}})

. This is the first such lower bound result.

Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Convex Optimization O(T^Β)$ Simultaneous Regret Lower Bounds Structural Constraints Regret

Ask PDF

Jun 30, 2026cs.LG

Constrained Online Convex Optimization without Slater's Condition

We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves

O(\sqrt{T})

expected regret and

O(\sqrt{T}\log T)

expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to

O(\log T)

with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.

Kihyun Yu, Junehee Lee, Dabeen Lee

Convex Optimization Stochastic Optimization Adversarial Training

Ask PDF

Jul 28, 2026cs.LG

Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

Constrained online convex optimization requires minimizing regret against adversarial convex costs while satisfying a convex constraint at every round, as needed in safety-critical applications. A computationally efficient method combines online gradient descent with a Polyak feasibility step, using one constraint evaluation and one subgradient per round. Although this method achieves O(sqrt(T)) regret with per-round feasibility, we derive a tighter, data-dependent analysis by retaining two quantities omitted by the standard worst-case argument. First, we replace the gradient envelope G_f^2 T with the observed accumulation G_T = sum_t ||grad f_t(x_t)||^2. Second, we identify a nonnegative Polyak correction P_T that measures the cumulative squared displacement caused by feasibility projections and enters the regret bound with a negative sign. The resulting improvement, Delta_T = (eta/2)(G_f^2 T - G_T) + P_T/(2 eta), is always nonnegative. We further propose AdaOGD-PFS, an adaptive-step-size method that achieves O(sqrt(G_T)) regret while preserving per-round feasibility. Experiments on ball- and halfspace-constrained problems improve the regret bound by 38 to 43 percent, with both data-dependent gradients and Polyak corrections contributing substantially.

Wentao Zhang

Convex Optimization O(T^Β)$ Simultaneous Regret Linear Regret Primal-Dual Methods Gradient Descent Regret

Ask PDF