Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries

Kaicheng Zhang, Lujing Zhang, Yifei Pang, Yuxiao Wen, Zhun Deng, Yanjun HanarXiv 2026 · arXiv

TL;DR

This paper introduces a framework for Constrained Gradient Equilibrium (CGEQ), a goal in online learning where a learner must ensure time-averaged gradients vanish while strictly obeying constraints. The authors prove that CGEQ is impossible against unrestricted adversaries, propose a new theoretical "locally constrained" adversary model, and provide a practical algorithm that transforms standard no-regret learners into robust equilibrium-achieving tools.

What Problem Does This Paper Address?

In online learning, we often want to reach a Gradient Equilibrium (GEQ). This means that as we make predictions over time, the average of our "mistakes" (gradients) should cancel out to zero. This is the mathematical backbone of tasks like calibration (ensuring a model's predicted 70% probability actually happens 70% of the time) and conformal prediction.

However, real-world learners face constraints. For example, an LLM might need to keep its response toxicity below a certain threshold, or a stock trader might have a strict risk budget. Previous research often "cheated" by modifying the goal to account for the boundary of the constraint set. This paper asks a harder question: Can we achieve the original equilibrium goal while staying inside the lines?

The authors discover a major hurdle: even if a solution exists in hindsight, a clever adversary can prevent a learner from ever reaching equilibrium unless the adversary's moves are restricted over local time windows.

Methods

The paper approaches the problem through the lens of Blackwell Approachability, a classic game-theory framework for reaching target sets in vector-payoff games.

  1. Locally Constrained Adversaries: They define two types of restrictions on the adversary:
  2. Blockwise: The adversary is constrained within fixed, non-overlapping time blocks.
  3. Sliding Window: The adversary is constrained over every consecutive window of length $H$. This is more realistic but mathematically harder because the adversary's current move limits their future options.
  4. State-Corrected Blackwell Conditions: For the sliding window case, they derive a necessary and sufficient condition using a "potential function." This function acts like a Bellman operator in reinforcement learning, accounting for the trade-off between the adversary's immediate power and their future flexibility.
  5. Algorithmic Reduction: They provide a "recipe" (Algorithm 1) to convert any standard no-regret learner (like Follow-the-Regularized-Leader) into a CGEQ algorithm. The key is to run the learner within local windows and use the cumulative gradient to pick a "direction" for the next window.

Datasets

The authors validated their approach on three distinct setups:

  • Synthetic Binary Forecasting: A controlled environment with alternating regimes to test how quickly algorithms adapt to shifts.
  • LLM Response Toxicity: Using a public dataset of 9,500 prompts with toxicity scores. The goal was to calibrate the average maximum toxicity of accepted responses to a target level while respecting a "slack" threshold.
  • Stock Volatility Prediction: Using historical daily returns for AMD, BB, FNMA, and NVDA. The task was to simultaneously target 90% and 70% coverage intervals (calibration) while minimizing the physical width of those intervals (the constraint).

Key Insights and Ideas

  • Global Feasibility is a Trap: The most surprising finding is that even if there is a single fixed action that works perfectly for the entire sequence in hindsight, an adversary can still defeat a learner if they aren't constrained locally. This justifies why "local feasibility" is the right way to think about constrained online learning.
  • The Power of the Potential: In the sliding window model, the math reveals that the game is "stateful." The learner isn't just fighting the current gradient; they are fighting the adversary's ability to maneuver in the future.
  • No-Regret is Enough: You don't need to reinvent the wheel. If you have a good no-regret algorithm and the environment has a bit of "margin" (meaning a feasible solution exists with some room to spare), the proposed reduction will work.

Key Results

The authors' primary algorithm, Soft-Blackwell FTRL, was compared against several baselines, including Vanilla Gradient Descent (GD), Lazy GD, and COCO (a state-of-the-art constrained optimization algorithm).

  • Superior Balance: In the LLM toxicity and stock experiments, Soft-Blackwell FTRL consistently achieved the best balance between low gradient imbalance (better calibration) and low constraint violation.
  • Robustness to Shifts: In synthetic tests, while baselines like COCO struggled with "calibration excursions" when the environment changed, the proposed method stayed much closer to the equilibrium.
  • Quantitative Edge: In the stock experiments, the method achieved the smallest final calibration error in 6 out of 8 settings compared to COCO, and 5 out of 8 compared to GD.

Limitations and Future Work

  • Known Window Length: The current theory and algorithms require the user to specify the window length $H$ in advance. In many real-world scenarios, the "local" structure of the environment might be unknown or change over time.
  • The Margin Requirement: The algorithmic reduction relies on "strong local feasibility with margin." If the constraints are so tight that there's no "slack" for the learner to recover from past errors, the guarantees might not hold.
  • Hard vs. Soft Constraints: While the theory covers hard constraints, the practical experiments focused more on "soft" constraints (where you penalize cumulative violation). Extending the high-performance algorithmic principles to strictly hard per-round constraints remains an open challenge.

Summary updated

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.
BibTeX
@misc{zhang2026constrained,
  author = {Kaicheng Zhang and Lujing Zhang and Yifei Pang and Yuxiao Wen and Zhun Deng and Yanjun Han},
  title = {{Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries}},
  year = {2026},
  eprint = {2610.33985},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.33985},
}
Figure