Exact-Form Regret and Conservative Correlated Equilibria

Gradient descent is usually studied through external regret, but recent work shows that it controls richer deviations through infinitesimal vector-field guarantees ahunbay2024first, semicoarse constraints ahunbay2025semicoarse, and weakly convex proximal maps cai2025proximal. We identify the finite-deviation invariant behind these guarantees. A feasible deviation \(\phi\colon K\to K\) induces the displacement field \(\Dphi(\xvec)=\xvec-\phi(\xvec)\). Online gradient descent has \(O(\sqrt T)\) regret against every feasible deviation with exact displacement, \(\Dphi=\nabla\Psi\) for a potential function $\Psi$, even when \(\Psi\) is nonconvex. Feasibility handles the projection boundary term, and exactness makes the potential telescope. The condition is sharp for smooth fields on simply connected domains, since any nonzero circulation along a feasible loop can be turned into a bounded cyclic adversary that forces linear regret. Semicoarse affine deviations are the linear-quadratic slice of this class, and proximal deviations are the Moreau-envelope slice. The exact-form class strictly contains weakly convex proximal deviations. For mirror descent, exactness is measured in the mirror geometry through the one-form \(\Dphi(\xvec)^\transpose\dd\nabla R(\xvec)\), which subsumes Bregman proximal regret and includes multiplicative deviations for multiplicative-weight updates. In convex games, no-regret with respect to exact-form deviations yields conservative correlated equilibrium, refining coarse and proximal correlated equilibrium.