Gradient equilibrium (GEQ) is a recent framework in online learning that requires the time-averaged gradients along the learner's trajectory to vanish. We study GEQ when the learner is constrained and ask when such an equilibrium remains achievable in an adversarial environment. We first show that constrained GEQ (CGEQ) can be impossible even under simple and slowly varying constraints, motivating imposing local temporal structure on the adversary. We then develop an approachability framework for CGEQ under locally constrained adversaries, and obtain necessary and sufficient characterizations in the spirit of classical Blackwell approachability. Beyond these theoretical characterizations, we provide an algorithmic principle that converts window-wise no-regret learners into CGEQ algorithms under a local feasibility condition with margin. Experiments on synthetic and real data demonstrate that the resulting algorithms perform strongly in both achieving GEQ and respecting the constraints.
Figures & tables
Figure 1: Binary forecasting with alternating outcome regimes: cumulative gradient imbalance ∣St∣ (left) and constraint violation Vt (right). All axes are linear.
Figure 2: LLM toxicity calibration ( H=10 , τ=10% ): cumulative gradient imbalance ∣St∣ (left) and constraint violation Vt (right). Lines and shading show means and min–max ranges over three prompt orders. Vertical axes use symmetric-log scaling.
Figure 3: Simultaneous 0.9 and 0.7 stock coverage on FNMA with window length H=10 : cumulative gradient imbalance ∥St∥2 (left) and constraint violation Vt (right). All axes are linear.
Algorithm 2 FTL on shifted directional losses within an H -round block
M
Soft-Blackwell FTRL ( κ )
COCO ( m )
Vanilla GD ( η )
Lazy GD ( η )
3
30
3
0.3
0.1
10
10
3
0.1
0.3
30
3
3
0.1
0.3
100
3
3
0.1
0.3
300
3
3
0.03
0.3
1000
3
3
0.03
0.3
Table 1: Validation-selected toy parameters. Soft-Blackwell FTRL uses ηH=κ/10 ; both GD rates are constant.
Figure 4: Binary forecasting across regime durations. Rows correspond to M=3,10,30,100,300,1000 , with H=10 and fifty test cycles in each setting. Left: ∣St∣ ; right: Vt . Both GD methods use validation-selected constant rates. All axes are linear; every test round is included.
Figure 5: Window and budget sensitivity for LLM toxicity. Rows correspond to (H,τ)=(10,10%),(10,20%),(20,10%),(20,20%) . The left column reports ∣St∣ and the right column reports Vt . We compute the absolute gradient sum within each run before averaging; shading gives the minimum–maximum range over the three prompt orders. Axes use the same scales across settings, with a linear region near zero and a logarithmic region above.
Soft-Blackwell FTRL ( ηH )
GD ( η )
Lazy GD ( η )
Stock
H=10
H=20
Both H
H=10
H=20
AMD
1
1
0.1
1
1
BB
1
0.1
0.01
0.1
0.001
FNMA
0.1
1
0.1
10
10
NVDA
0.1
1
0.1
0.1
1
Table 2: Validation-selected stock parameters.
Figure 6: Simultaneous stock coverage with H=10 . Rows show AMD, BB, FNMA, and NVDA. Left: cumulative gradient imbalance ∥St∥2 ; right: cumulative positive width violation Vt . All methods use the same observations, budgets, hard domain, and validation/test split. GD enforces subset consistency by Euclidean projection. All axes are linear.
Figure 7: Simultaneous stock coverage with H=20 , using the same stock order, cumulative metrics, and validation procedure as Figure 6 . The main-text FNMA comparison in Figure 3 uses H=10 .
Gradient equilibrium (GEQ) is a recently introduced online optimization framework that generalizes first-order stationarity from offline optimization and abstracts problems like online conformal prediction. While GEQ has curious similarities with known online learning frameworks, namely regret minimization, prior work has shown that GEQ error and regret are incomparable objectives, leaving open a precise understanding of how GEQ fits into the broader online learning landscape. In this work, we show that GEQ is equivalent to Blackwell approachability in the algorithmic sense. That is, a Blackwell approachability problem can always be solved using queries to a black-box GEQ oracle, with no asymptotic loss in the oracle's error rate, and vice versa. Taken together with known equivalences between approachability, regret minimization, and calibration, these results imply that GEQ is equivalent to these frameworks, as well. Our reductions are efficient and can be used to transfer refined guarantees, such as optimism and strong adaptivity, from regret minimization to GEQ. Along the way, we also identify necessary and sufficient conditions for GEQ, and establish reductions between different notions of GEQ with unconstrained and constrained decision sets.
Brian W. Lee, Nika Haghtalab, Michael I. Jordan +1
University of California, Berkeley · Inria & ´Ecole Normale Sup´erieure
We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation VT(u)=∑t=2T∥∇ft(u)−∇ft−1(u)∥2. For L-smooth convex losses, we provide fully-adaptive algorithms achieving regret of O(∥u∥VT(u)+L∥u∥2+G4) without requiring prior knowledge of comparator norm ∥u∥, Lipschitz constant G, or smoothness L. The update in each round can be computed efficiently via a closed-form expression. Our results extend to dynamic regret and find immediate implications for the stochastically-extended adversarial (SEA) model, which significantly improves upon the previous best-known result (Wang et al., 2025).
Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1
Università degli Studi di Milano & Politecnico di Milano
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(T) expected regret and O(TlogT) 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(logT) 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.