Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries

Kaicheng Zhang; Lujing Zhang; Yifei Pang; Yuxiao Wen; Zhun Deng; Yanjun Han

cs.LGOct 25, 2026

Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries

Authors: Kaicheng Zhang, Lujing Zhang, Yifei Pang, Yuxiao Wen, Zhun Deng, Yanjun Han

Organizations: University of North Carolina at Chapel Hill · Carnegie Mellon University · New York University

Abstract

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

|S_{t}|

(left) and constraint violation

V_{t}

(right). All axes are linear.

Figure 2: LLM toxicity calibration ( $H=10$ , $\tau=10\%$ ): cumulative gradient imbalance $|S_{t}|$ (left) and constraint violation $V_{t}$ (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

\|S_{t}\|_{2}

(left) and constraint violation

V_{t}

(right). All axes are linear.

x_{t}\leftarrow\arg\min_{x\in C}\sumop\displaylimits_{s=(k-1)H+1}^{t-1}\left\langle u_{k},g_{s}(x)+\lambda(x-x_{0})\right\rangle

Algorithm 2 FTL on shifted directional losses within an

H

-round block

$M$	Soft-Blackwell FTRL ( $\kappa$ )	COCO ( $m$ )	Vanilla GD ( $\eta$ )	Lazy GD ( $\eta$ )
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

\eta_{H}=\kappa/\sqrt{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: $|S_{t}|$ ; right: $V_{t}$ . 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,\tau)=(10,10\%),(10,20\%),(20,10\%),(20,20\%)$ . The left column reports $|S_{t}|$ and the right column reports $V_{t}$ . 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 ( $\eta_{H}$ )		GD ( $\eta$ )	Lazy GD ( $\eta$ )
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 $\|S_{t}\|_{2}$ ; right: cumulative positive width violation $V_{t}$ . 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$ .

Online Learning

Online learning studies algorithms that update predictions or decisions from sequential feedback while controlling cumulative error or regret.

See all 133 papers

Blackwell Approachability and Gradient Equilibrium are Equivalent
Jun 25, 2026Brian W. Lee, Nika Haghtalab, Michael I. Jordan +1Blackwell Approachability
University of California, Berkeley · Inria & ´Ecole Normale Sup´erieure
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Apr 13, 2026Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Online Convex Optimization Dynamic Regret Minimization
Università degli Studi di Milano & Politecnico di Milano
Constrained Online Convex Optimization without Slater's Condition
Jun 30, 2026Kihyun Yu, Junehee Lee, Dabeen LeePrimal-Dual Optimization Online Convex Optimization
1KAIST · 2Seoul National University

Jun 25, 2026J/K move · Enter open · S save

Blackwell Approachability and Gradient Equilibrium are Equivalent

Brian W. Lee, Nika Haghtalab, Michael I. Jordan, Ryan J. Tibshirani

University of California, Berkeley · Inria & ´Ecole Normale Sup´erieure

Blackwell Approachability

Open paper AskPDF arXiv

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.

Abstract

Online Learning

Explore similar work

Blackwell Approachability and Gradient Equilibrium are Equivalent

Gradient-Variation Regret Bounds for Unconstrained Online Learning

Constrained Online Convex Optimization without Slater's Condition