Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader

• URL: http://arxiv.org/abs/2609.09466v1
• Date: Tue, 08 Sep 2026 21:32:02 GMT
• Title: Exact-Form Regret for Gradient Descent, Mirror Descent and Follow-the-Regularized-Leader
• Abstract summary: Recent work shows that first-order methods control richer action-dependent deviations.<n>We ask for a geometric characterization of the deviations with respect to which online gradient descent, mirror descent, and follow-the-regularized-leader (FTRL) achieve no regret.
• Score: 46.31158375592562
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online gradient descent is usually studied through external regret, where the learner competes with fixed alternatives. Recent work shows that first-order methods control richer action-dependent deviations. We ask for a geometric characterization of the deviations with respect to which online gradient descent, mirror descent, and follow-the-regularized-leader (FTRL) achieve no regret. We identify exactness as the common principle. Exactness means that the relevant displacement field is generated by a scalar potential, or equivalently that the associated one-form is exact in the geometry used by the algorithm. This geometry depends on the algorithm. For gradient descent it is Euclidean geometry, for mirror descent it is the geometry induced by the regularizer, and for FTRL it is the cumulative dual state. Under mild regularity conditions, exactness yields sublinear regret, while nonzero circulation provides the complementary obstruction and leads to linear regret. This gives a unified geometric framework for understanding the deviation classes controlled by these algorithms and reveals that different first-order methods can control genuinely different classes of deviations. These deviation classes have direct consequences for learning, particularly in games. We study the equilibrium notions induced by exact-form deviations and introduce conservative correlated equilibrium, reflecting both the conservative geometry of the underlying displacement fields and the restricted family of deviations available to the players. We characterize its relation to correlated equilibrium, determine when the resulting equilibrium notions coincide and when they separate, and show how these relationships depend on the geometry and the learning algorithm. Overall, this work gives a unified geometric account of what first-order online learning algorithms are no-regret with respect to, beyond fixed comparators.

Related papers

• Symmetry-Structured Neural Completion of Islamic Geometric Patterns from Sparse Control Geometry [0.5115559623386962]
  Islamic geometric patterns are governed by exact rotational symmetry and strict construction rules.<n>This paper treats these rules as formal geometric knowledge and embeds them in a neural completion framework.
  arXiv  Detail & Related papers  (2026-06-30T11:12:12Z)
• Nonlinear Geometrizability of State-Dependent Proto-Area in Approximate Holographic Codes [0.0]
  State-dependent proto-area data produced by approximate recovery need not be compatible with a single local bulk metric.<n>We derive exact finite-resolution criteria and, near the hyperbolic disk, necessary and sufficient conditions for a regular proto-area two-jet.<n>Hamiltonian-skewed codes realize both first-order nongeometry and a calibrated response whose first obstruction appears only at quadratic order.
  arXiv  Detail & Related papers  (2026-06-21T17:16:10Z)
• A Unified Geometric Framework for Weighted Contrastive Learning [3.746889836344765]
  We show that weighted InfoNCE objectives can be interpreted as Distance Geometry Problems.<n>This viewpoint yields exact characterizations of the optimal embeddings for several supervised and weakly supervised objectives.<n>Our results show that the choice of weighting scheme determines whether contrastive learning is geometrically realizable, degenerate, or inconsistent.
  arXiv  Detail & Related papers  (2026-05-13T17:48:36Z)
• Orthogonalized Policy Optimization:Decoupling Sampling Geometry from Optimization Geometry in RLHF [0.0]
  Large language model alignment objectives are often presented as a collection of distinct algorithms, such as PPO, DPO, IPO, and their variants.<n>In this work, we argue that this diversity obscures a simpler underlying structure.<n>We show that this entanglement is not merely a modeling convenience but a source of systematic instability.
  arXiv  Detail & Related papers  (2026-01-18T13:57:44Z)
• Generalized Linear Mode Connectivity for Transformers [87.32299363530996]
  A striking phenomenon is linear mode connectivity (LMC), where independently trained models can be connected by low- or zero-loss paths.<n>Prior work has predominantly focused on neuron re-ordering through permutations, but such approaches are limited in scope.<n>We introduce a unified framework that captures four symmetry classes: permutations, semi-permutations, transformations, and general invertible maps.<n>This generalization enables, for the first time, the discovery of low- and zero-barrier linear paths between independently trained Vision Transformers and GPT-2 models.
  arXiv  Detail & Related papers  (2025-06-28T01:46:36Z)
• Gradient Equilibrium in Online Learning: Theory and Applications [56.02856551198923]
  gradient equilibrium is achieved by standard online learning methods.<n> gradient equilibrium translates into an interpretable and meaningful property in online prediction problems.<n>We show that gradient equilibrium framework can be used to develop a debiasing scheme for black-box predictions.
  arXiv  Detail & Related papers  (2025-01-14T18:59:09Z)
• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.<n>We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.<n>We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learning [68.76846801719095]
  We show that double descent appears exactly when and where it occurs, and that its location is not inherently tied to the threshold p=n. This provides a resolution to tensions between double descent and statistical intuition.
  arXiv  Detail & Related papers  (2023-10-29T12:05:39Z)
• Non-convex online learning via algorithmic equivalence [30.038975353298117]
  algorithmic equivalence technique non gradient descent convex mirror descent theory is presented. Our analysis is based on a new simple algorithmic method prove an $frac23$.
  arXiv  Detail & Related papers  (2022-05-30T16:50:34Z)
• Orthogonal Jacobian Regularization for Unsupervised Disentanglement in Image Generation [64.92152574895111]
  We propose a simple Orthogonal Jacobian Regularization (OroJaR) to encourage deep generative model to learn disentangled representations. Our method is effective in disentangled and controllable image generation, and performs favorably against the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-08-17T15:01:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.