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

Gradient descent

• Online gradient descent achieves sublinear regret against sufficiently regular feasible maps whose displacement Dϕ is an exact Euclidean gradient, with sharper finite-time bounds for endomorphisms.The comparator is the actual endpoint ϕ(x_t), and feasibility, convexity, and normal cones replace tangent-projection machinery.Source: §1 · p. 2

Deviation classes

• The smooth Euclidean exact-form class strictly contains weakly convex proximal deviations, while every smooth exact-form deviation admits sufficiently small identity interpolation that is proximal.For affine maps, symmetry of I−A makes the displacement a quadratic gradient; proximality is therefore a mechanism for exactness, not its defining property.Source: §1 · p. 2

Mirror descent

• Mirror descent admits an analogous exactness-versus-circulation theory in mirror geometry, including standard constrained updates with boundary iterates.The relevant one-form is Dϕ(x)^T d∇R(x), and Bregman proximal deviations arise as a special case.Source: §1 · p. 2

FTRL

• FTRL exactness is formulated in cumulative dual state; it implies mirror exactness, but the converse can fail, yielding deviations with O(T) mirror regret and linear FTRL regret.The separation occurs through boundary effects, despite coincidence of mirror descent and FTRL for constant-step linearized losses in the Legendre interior.Source: §1 · p. 2

Equilibrium implications

• Conservative correlated equilibrium induced by Euclidean exact-form deviations equals proximal correlated equilibrium under zero approximation error, coincides with correlated equilibrium in stated settings, and can be strictly smaller in two dimensions.Specifically, CE = ConCE = PCE on finite support and for interval action spaces, while a two-dimensional construction gives CE ⊊ ConCE = PCE.Source: §1 · pp. 2–3

• Φ-regret generalizes external regret by comparing actions with transformed actions ϕ(x_t), with external regret recovered when Φ contains all constant functions.A major research direction seeks efficiently achievable deviation classes, including linear or low-degree polynomial endomorphisms, though existing methods can require complex separation and fixed-point machinery.Source: §2 · pp. 3–4
• Recent work shows online gradient descent controls more than external regret, including symmetric linear endomorphisms and proximal transformations, motivating a broader characterization of its Φ-regret guarantees.The paper develops a finite feasible-map theory covering online gradient descent, mirror descent, and FTRL.Source: §2 · p. 4
• The paper extends prior first-order and proximal analyses by characterizing finite endpoint deviations through exactness and circulation, obtaining sharper finite-time bounds and nonlinear feasible deviations.Relative to Ahunbay [2026] and Ahunbay and Bichler [2025], the framework focuses on actual endpoints and extends tractable linear–quadratic deviations to nonlinear feasible maps; it also addresses the open question of Cai et al. [2026].Source: §2 · p. 4
• For gradient descent, smooth exact-form deviations strictly contain weakly convex proximal deviations; analogous exact-form characterizations apply to mirror descent, while FTRL can differ under boundary effects.The paper also separates proximal representability from exactness: identity interpolation recovers the Euclidean exact-form class, whereas radial Bregman proximal deviations may be smaller in mirror geometry.Source: §2 · p. 4
• The resulting equilibrium notions are new: ConCE and PCE coincide under unrestricted definitions, coincide with CE in finite-support and interval settings, but separate from CE on higher-dimensional continuous support.These equilibrium consequences arise from the finite deviation classes induced by the algorithms.Source: §2 · p. 4
• The paper’s nonlinear finite-displacement framework generalizes the potential-based gradient-equilibrium viewpoint of Angelopoulos et al. [2025] beyond constant directions while encoding feasibility directly in deviation maps.Both frameworks rely on a telescoping mechanism, but this work studies finite Φ-regret and nonlinear action-dependent deviations.Source: §2 · pp. 4–5

Basic setting

• The learner chooses x_t ∈ K and observes vector loss g_t ∈ R^d, with K a nonempty closed convex action set and Euclidean projections and normal cones taken in the ambient space.For intrinsically lower-dimensional statements, derivatives and differential forms use affine coordinates on aff(K).Source: §3 · p. 5

Regret notation

• Deviation regret is defined through inner products between observed losses and deviation-induced displacements, including the general form Reg_T(D) for a displacement field D.For convex differentiable losses, setting g_t = ∇ℓ_t(x_t) transfers linearized regret bounds directly to convex-loss deviation regret.Source: §3 · p. 5

Exact-form deviations

• A deviation is Euclidean exact-form when it is generated by a continuously differentiable potential Ψ defined on a neighborhood of K, yielding the class Φ_exact.The paper uses subscripts to identify deviation classes, including Φ_prox and Φ_sm exact, while superscript R denotes regularizer-dependent mirror classes.Source: §3 · p. 5

Regularity

• Smooth exact-form deviations require the potential gradient to be locally Lipschitz on a neighborhood of K, a stronger condition later used to show that scaled exact deviations are proximal.This smoothness requirement is stronger than the basic C1 definition.Source: §3 · p. 5

Normalized classes

• Because bounds for individual deviations may depend on deviation parameters, normalized classes Φ_exact(B, L) are introduced when taking suprema over deviations.These classes impose bounded-potential and gradient conditions specified by constants B and L.Source: §3 · pp. 5–6

Theorem 4.1

• OGD admits a telescoping regret bound for every smooth feasible exact-form deviation ϕ, yielding sublinear regret under bounded gradients and bounded potential oscillation.The deviation has displacement field D_ϕ(x) = x − ϕ(x) = ∇Ψ(x), with Ψ smooth in Euclidean geometry.Source: §4 · p. 6

Proof mechanism

• Exactness, rather than proximality, enables telescoping on Ψ, while the projection residual contributes favorably because it lies in the normal cone and ϕ(K) ⊆ K.On an unconstrained domain, the projection residual vanishes.Source: §4 · p. 6

Corollary 4.2

• With compact K, bounded gradients, and bounded potential oscillation, OGD obtains the stated sublinear regret guarantee for exact-form deviations.The corollary assumes ∥g_t∥ ≤ G and osc_K(Ψ) ≤ B, with positive constants B, L, and G.Source: §4 · p. 6

Corollary 4.3

• A single learning rate lets OGD control the entire normalized class Φ_exact(B, L).The constrained proof uses a quadratic upper bound for Ψ and L-Lipschitz continuity of ∇Ψ; without projection, only the quadratic upper bound is needed.Source: §4 · p. 6

Proximal deviations

• The resulting regret guarantee applies to proximal deviations generated by ρ-weakly convex functions, using the weakly-convex Moreau-envelope identity rather than only its convex special case.The indicator ι_K ensures that the proximal minimization is over K; degenerate cases with B_F=0 or G=0 make the corresponding bound trivial.Source: §5 · p. 7
• For proper lower-semicontinuous ρ-weakly convex F=f+ι_K with 0≤ρ<1, the proximal map is feasible and Euclidean exact-form: x−prox_F(x)=∇M_F(x).The potential’s gradient is Lipschitz with constant (2−ρ)/(1−ρ), enabling projected gradient descent to control every such proximal deviation.Source: §5 · p. 7

Standard deviation classes

• The exact-form class contains external regret, projection to a convex subset, projection-based/no-move regret, interpolation deviations, and bounded-displacement local proximal deviations.These arise respectively from point indicators, convex-set indicators, constrained linear functions, quadratic-plus-indicator functions, and bounded proximal displacements.Source: §5 · p. 7
• Symmetric affine swaps are also exact-form when their restriction satisfies the stated invariant-subspace and self-adjointness conditions, with displacement generated directly by a quadratic potential.This exact-form characterization does not require first representing the affine map as a proximal operator.Source: §5 · pp. 7–8

• Smooth feasible exact-form deviations strictly contain weakly convex proximal maps, as a nonmonotone one-dimensional exact-form deviation cannot be proximal.Every one-dimensional weakly convex proximal map with parameter 0 ≤ ρ < 1 is monotone, whereas Proposition 6.1 constructs a smooth feasible exact-form deviation that is not.Source: §6 · p. 8
• Every smooth feasible exact-form deviation becomes a weakly convex proximal map after sufficiently small positive interpolation with the identity.For compact convex K and locally C1,1 potential Ψ, Theorem 6.2 represents the interpolated map as prox_Fα with ρ_α < 1.Source: §6 · p. 8
• Identity-radial closure removes the map-class gap: RadI(Φprox) = Φsm_exact, despite Φprox ⊊ Φsm_exact.Thus the strict separation between the classes does not separate their corresponding equilibrium sets when approximation error is zero.Source: §6 · p. 9
• ConCE = PCE for convex games with compact action sets and jointly continuous losses, because profitable smooth exact deviations remain profitable under every positive identity interpolation.Linearized regret scales as Reg_T(ϕ_α) = α Reg_T(ϕ), and convexity preserves the profitability of the interpolated deviation.Source: §6 · p. 9

• Exact fields have zero circulation around every closed loop, so this obstruction cannot arise for exact-form regret.If D = ∇Ψ on a neighborhood of K, integrating the associated one-form around any closed loop gives zero.Source: §7 · p. 9
• Nonzero circulation on a closed feasible loop can be converted into a bounded cyclic adversary that forces online gradient descent to incur Ω(T) regret.The construction applies for every gradient bound G > 0 and sufficiently small step size η; starting elsewhere adds only an O(1/η) transient.Source: §7 · p. 9
• The linear lower bound extends to anytime learning-rate schedules and is therefore not an artifact of knowing the horizon in advance.Geometric epochs make positive loop contributions sum to Ω(T), while steering transients sum to O(√T).Source: §7 · p. 10
• On a simply connected relative interior, vanishing skew derivatives are equivalent to a C2 potential, whereas any nonzero skew derivative permits linear regret along a sufficiently small feasible loop.The curl-free case yields O(√T) projected-GD regret when the potential has a suitable ambient extension and the induced endpoint map remains feasible.Source: §7 · p. 10
• For finite deviation maps, feasibility supplies the tangent-to-action-set condition that conservative vector-field tests require.Convexity keeps the segment from x to a feasible endpoint ϕ(x) inside K, making exactness the finite-map counterpart of conservativeness.Source: §7 · p. 10

8 Online Mirror Descent and Exact One-forms

• Mirror-exact deviations are those whose displacement becomes a gradient in dual coordinates, equivalently making Dϕ(x)^T d∇R(x) an exact one-form.In primal coordinates, this is ordinary exactness after multiplying the displacement by the mirror metric ∇^2R(x).Source: §8 · pp. 10–12
• The Legendre-interior presentation supplies the clean dual recursion, but the exactness principle itself survives boundary effects through a direct mirror one-form formulation.The interior setting removes normal-cone terms; the general constrained analysis restores them without changing the underlying geometric condition.Source: §8 · pp. 10–11, §8.4 · p. 14

8.4 Full Mirror Characterization Beyond Legendre Regularizers

• Beyond Legendre regularizers, exactness remains the governing condition: standard constrained mirror descent admits matching upper and lower analyses even with boundary iterates and without a globally invertible dual map.The boundary proof controls the normal-cone residual using feasibility and Lipschitz continuity of the displacement.Source: §8 · p. 11, §8.4 · pp. 14–15

8.1 Examples of Mirror-exact Deviations

• The mirror-exact family contains every fixed-comparator deviation, includes multiplicative and geometric interpolation deviations for multiplicative weights, and contains deviations that are not Euclidean-exact.Examples can be constructed by choosing a dual potential, differentiating it, and pulling the resulting field back through θ = ∇R(x).Source: §8.1 · p. 12

8.2 Online Mirror Descent Controls Mirror-exact Regret

• Under Legendre-interior assumptions, online mirror descent achieves sublinear regret against mirror-exact deviations when the dual potential satisfies a relative-smoothness condition.With bounded gradients and a horizon-independent potential-oscillation bound, the theorem gives an O(√T) bound using a horizon-dependent constant step size.Source: §8.2 · pp. 12–13

8.3 Bregman Proximal Regret is Mirror-exact

• Bregman proximal deviations of weakly convex functions are mirror-exact, so mirror descent controls their regret under the stated strong-convexity and regularity conditions.The result follows because weakly convex Bregman proximal potentials are 1-relatively smooth with respect to R*; when 0 ≤ ρ < m, the proximal map is uniquely defined and continuous.Source: §8.3 · pp. 13–14

8.4 Full Mirror Characterization Beyond Legendre Regularizers

• With bounded gradients and bounded potential oscillation, mirror-exact deviations receive o(T) regret under standard constrained mirror descent, including the usual O(√T) rate when ∇R is Lipschitz.The result uses constant step size η = T^-1/2 under the theorem’s curvature and Lipschitz assumptions.Source: §8.4 · p. 15
• Every mirror-exact field has zero mirror circulation, whereas any feasible loop with nonzero circulation can be exploited by an adversary to force linear regret.For sufficiently small constant step sizes, bounded-gradient losses can repeatedly drive constrained mirror descent around the loop, yielding regret proportional to T.Source: §8.4 · p. 15
• Exactness, cross-derivative symmetry, and vanishing circulation are equivalent characterizations of standard constrained mirror descent under the stated regularity assumptions.The characterization applies on the relative interior U of the constraint set, where the regularizer has positive-definite Hessian and the relevant coefficient field is C1.Source: §8.4 · p. 16
• Nonzero circulation lets an adversary force linear regret on a sufficiently small loop, whereas exactness plus the theorem’s regularity conditions gives sublinear regret.The anytime statement follows using the same learning-rate quantifiers and geometric-epoch construction as in the earlier theorem.Source: §8.4 · p. 16
• Exactness is the sharp geometric boundary for constrained mirror descent; smoothness and potential oscillation determine rates, while proximality is a separate representation question.The characterization does not depend on proximality.Source: §8.4 · p. 16

8.5 Identity Interpolation of Bregman Proximal Deviations

• Identity interpolation scales deviations algebraically for every mirror map, but sufficiently small proximal interpolations of smooth exact deviations depend on regularizer curvature and can fail even in Legendre geometries.The representation results do not require compactness, and radial proximal deviations are mirror-exact under the stated setup.Source: §8.5 · pp. 16–17
• A mirror-exact interpolation is proximally representable only if R*−αΨ is convex and the reconstructed generator satisfies the required domain, regularity, and weak-convexity conditions.Convexity gives a variational Bregman representation, but admissibility additionally requires the reconstructed generator to belong to the allowed proximal class.Source: §8.5 · p. 18
• The convexity threshold is αLR(Ψ) ≤ 1, expressing that the interpolated potential’s relative curvature cannot exceed that of R*.This relative curvature requirement can be substantially stronger than an ordinary Euclidean Lipschitz bound on ∇Ψ.Source: §8.5 · pp. 18–19
• In Euclidean geometry, sufficiently small interpolation can satisfy both curvature requirements, but for nonquadratic regularizers they need not coincide.The reconstructed generator must also meet the weak-convexity margin and domain assumptions.Source: §8.5 · p. 19
• For 1 < p < 2, a feasible mirror-exact deviation with a C∞ dual potential and globally Lipschitz gradient has R*−αΨ nonconvex for every α > 0.The obstruction is curvature mismatch: R* lacks quadratic transverse curvature at e1, while Ψ has quadratic curvature there; the regularizer is differentiable but not C2 on coordinate axes.Source: §8.5 · p. 19

9.1 Coincidence with Mirror Descent in the Legendre Interior

• In the Legendre interior, FTRL and constant-step mirror descent generate identical iterates, so mirror-exact and Bregman-proximal regret guarantees transfer verbatim.Beyond the interior, boundary normal-cone effects can make the algorithms control different deviation classes.Source: §9.1 · p. 20

9.2 Exactness and Circulation in the Cumulative Dual State

• FTRL controls deviations that are exact in the cumulative dual state; under uniform convexity, trajectory-wise relative smoothness, and bounded potential oscillation, this yields sublinear regret.Nonzero circulation on a closed dual-state loop lets bounded gradients force cT − O(1/η) regret, while a C1 field is exact exactly when its Jacobian is symmetric.Source: §9.2 · p. 21
• Nonzero cumulative-dual circulation yields linear regret, even from every initial dual state, because an adversary can repeatedly steer FTRL around a loop after only a transient cost.The resulting upper- and lower-bound characterization is the FTRL analogue of the exactness-versus-circulation criterion.Source: §9.2 · p. 22

9.3 Mirror Descent and FTRL Control Different Deviation Classes

• Every FTRL-exact deviation is mirror-exact, but the inclusion is strict: one smooth deviation has O(T) mirror-descent regret and cT − O(1/η) FTRL regret.The separation arises when cumulative dual states reach boundary-saturated regions with unequal cross derivatives and nonzero dual circulation.Source: §9.3 · pp. 22–23

9.4 Examples and Applications of the FTRL Bound

• Power-type regularizers specialize the FTRL theorem to geometry-dependent rates, with the uniform-convexity exponent determining the horizon dependence; one-homogeneous ℓp norms are excluded by the theorem’s assumptions.FTRL and mirror-descent theories coincide on Legendre trajectories, whereas normal directions make FTRL exactness stricter and permit extended-valued or nonsmooth regularizers.Source: §9.4 · pp. 23–24

10 Conservative Correlated Equilibria in Convex Games

• Zero-error equilibrium constraints are invariant under identity-radial closure, while quantitative radial guarantees additionally require a common lower bound on admissible interpolation scales.For specified exact-form families, regret bounds yield approximate ConCE with error ε_T = max_i R_i,T/T; the same convexity argument extends to mirror and FTRL families.Source: §10 · pp. 24–25

10.1 Exact and Proximal Equilibrium Constraints

• Under unrestricted deviation classes, the equilibrium constraints generated by smooth exact-form deviations and proximal deviations are equal in every convex game with compact convex action sets and jointly continuous losses.This equality need not persist for fixed weak-convexity, normalization, locality, or computational restrictions, which can affect quantitative guarantees.Source: §10.1 · pp. 25–26

10.2 Mirror-exact, Mirror-radial, and FTRL Equilibrium Constraints

• By radial invariance, radial and proximal equilibrium notions coincide, while mirror-exact and FTRL-exact deviation classes can differ under boundary effects, even with the same geometry and action set.For r_i = 2, the FTRL-exact deviation family has rate O(T −1/2), rather than the mirror-exact family.Source: §10.2 · pp. 26–27

10.3 Finite Support and Boundary-compatible Interpolation

• For every finitely supported distribution in a convex game, CE, ConCE, and PCE coincide; consequently, the three notions coincide in every finite game.Finite interpolation realizes any finite collection of recommended actions and deviation values through a sufficiently small common identity interpolation by one proximal map.Source: §10.3 · p. 27

10.4 Full Correlated Equilibrium on Intervals

• With compact interval action sets and continuous losses, unrestricted ConCE and PCE coincide with full measurable-deviation CE, even for arbitrary Borel distributions.The proof uses antiderivatives and approximation of measurable deviations by smooth feasible exact-form maps; infinite support alone therefore does not separate the notions.Source: §10.4 · p. 28

10.5 Strict Separation from CE on Continuous Support

• A two-player convex game admits an uncountably supported distribution with CE ⊊ConCE = PCE, although its marginals are absolutely continuous.The construction uses a diagonal law whose joint distribution is singular, so it does not establish separation for full-dimensional joint densities.Source: §10.5 · pp. 28–29

11 Conclusion

• Exactness determines interior regret behavior, while feasibility governs boundary interactions; exact fields yield sublinear regret and nonzero circulation can force linear regret.This principle holds in Euclidean geometry and extends to mirror geometry, where the regularizer determines the relevant one-form and boundary control requires additional regularity.Source: §11 · p. 29
• Proximal deviations and identity interpolations are exact-form subclasses, but radial closure fails in general Bregman geometry because convexity of the reconstructed dual potential adds an obstruction.Source: §11 · p. 29
• Mirror descent and FTRL agree in the Legendre interior but may control different deviation classes when constraints create nontrivial boundary effects.Source: §11 · p. 29
• Unrestricted ConCE and PCE coincide, and both coincide with CE on finite supports and on one-dimensional action spaces with continuous losses.Source: §11 · p. 29
• The positive mirror-descent result leaves open whether weaker curvature, Lipschitz, and ambient regularity assumptions can still control boundary residuals and preserve sublinear regret.A second open question asks whether continuous-support equilibrium separation persists for a full-dimensional absolutely continuous joint distribution, since the present construction lies on a lower-dimensional diagonal.Source: §11 · p. 29
• Exact-form analysis may connect to Blackwell approachability [Blackwell, 1956, Abernethy et al., 2011] and gradient equilibrium [Angelopoulos et al., 2025, Lee et al., 2026] by identifying geometric quantities that first-order dynamics telescope or drive toward target sets.The paper also proposes exact lifting [Farina et al., 2022a, Soleymani et al., 2025b] to control richer deviations, such as general linear endomorphisms, in higher-dimensional feature spaces.Source: §11 · p. 29

A Preliminaries

• For weakly convex proximal analysis, the normal-cone condition characterizes constrained optimality, and a proper lower-semicontinuous function with ρ < 1 has a unique proximal minimizer whose proximal map is monotone.The preliminaries establish these properties through weakly convex subdifferential hypomonotonicity and proximal optimality conditions.Source: A Preliminaries · pp. 33–34

Theorem 6.2

• For compact convex K, every feasible exact-form deviation ϕ(x) = x − ∇Ψ(x) with Ψ ∈ C1,1_loc has a sufficiently small interpolation that is proximal.There exists α0 > 0 such that ϕα = (1 − α)I + αϕ coincides on K with proxFα for Fα = fα + ιK.Source: B Scaled Exact Deviations and Proximal… · p. 34
• The proximal regularizer is ρα-weakly convex with ρα < 1, because Lipschitz smoothness yields strong convexity of the auxiliary function and its conjugate.For global gradient-Lipschitz constant L, ρα = αL/(1 + αL) < 1; feasibility and convexity of K ensure the constraint preserves the unconstrained minimizer.Source: B Scaled Exact Deviations and Proximal… · p. 35

Corollary 6.3

• The radial closure of Euclidean proximal deviations equals the smooth exact-form deviations: RadI(Φprox) = Φsm exact.Theorem 6.2 gives one inclusion, while the converse follows from proximal-map regularity and x − ϕα(x) = α(x − ϕ(x)).Source: B Scaled Exact Deviations and Proximal… · p. 35

C Boundary-Compatible Finite Interpolation

• Finite data admit subgradients of a proper closed convex function exactly when they are cyclically monotone.It is sufficient to check nontrivial simple cycles.Source: C Boundary-Compatible Finite… · p. 35
• The sufficiency proof constructs a finite polyhedral convex function from maximum-weight directed paths, with cyclic monotonicity ensuring finite path values and the required subgradients.Closed walks decompose into simple cycles, which explains why simple-cycle checks suffice.Source: C Boundary-Compatible Finite… · pp. 35–36
• For distinct points in a closed convex set and sufficiently small α, there exists a proper lower-semicontinuous ρ-weakly convex function whose proximal map sends each x_j to (1 − α)x_j + αy_j.The proximal minimizer is unique.Source: C Boundary-Compatible Finite… · p. 36
• The interpolation construction obtains cyclic monotonicity from continuity of finitely many cycle sums, then forms F_α using the resulting convex function and the constraint set.The argument uses convexity of K and normal-cone vectors, while strong convexity gives uniqueness of the proximal minimizer.Source: C Boundary-Compatible Finite… · p. 36

D.1 Proofs for Section 4

• For projected OGD, an exact-form deviation D_ϕ(x)=∇Ψ(x) with L-smooth Ψ yields a regret bound for every gradient sequence.The proof combines smoothness with a projection normal-vector lemma, then telescopes the potential terms.Source: §D.1 · pp. 36–37
• With bounded gradients and fixed B,L, OGD uses a learning rate that controls the entire normalized class Φexact(B,L) uniformly over deviations.Uniformity follows because the telescoping term is bounded by B and the same learning rate applies to every class member.Source: §D.1 · p. 38

D.2 Proofs for Section 5

• For F=f+ι_K proper, lower semicontinuous, and ρ-weakly convex with 0≤ρ<1, prox_F is feasible and satisfies x−prox_F(x)=∇M_F(x), with Lipschitz constant (2−ρ)/(1−ρ).The resulting proximal deviations are controlled by projected gradient descent through Theorem 4.1.Source: §D.2 · p. 38
• The proximal and affine exactness claims follow by feasibility, completing the square, constrained first-order optimality, the Moreau identity, and differentiation using self-adjointness.If B_F=0 or G=0, the corresponding regret bound is trivial and the optimizing step size is unnecessary.Source: §D.2 · pp. 38–39
• The exact-form class contains external regret, projection onto closed convex subsets, projection-based/no-move regret, interpolation deviations, and bounded local proximal deviations.These arise respectively from indicator functions, linear-plus-indicator functions, quadratic proximal objectives, and the Moreau identity.Source: §D.2 · p. 38
• An affine map ϕ(x)=Ax+b is exact-form when it preserves the direction space of aff(K) and I−A is self-adjoint there, provided ϕ(K)⊆K.The proof constructs an affine-hull potential and extends it smoothly to the ambient space using orthogonal projection.Source: §D.2 · pp. 38–39

D.3 Proofs for Section 7

• Nonzero circulation around a feasible loop lets an adversary force online gradient descent to incur linear regret, whereas curl-free fields admit O(T) regret under extension, feasibility, smoothness, and bounded-oscillation assumptions.The cyclic construction follows polygonal loops with one-traversal regret C/η; projected GD then repeats the loop to obtain Ω(T) regret.Source: §D.3 · pp. 40–41

D.4 Proofs for Section 8

• A deviation is R-mirror-exact exactly when its displacement paired with d∇R is the differential of a scalar potential, equivalently admitting a dual-gradient representation.This proposition transfers exactness from primal displacement fields to the geometry induced by the mirror regularizer.Source: §D.4 · p. 41

D.5 Examples of Mirror-exact Deviations for Section 8.1

• The examples show that mirror-exact deviations must be pointwise feasible and include fixed comparators, identity deviations, dual translations, and dual-coordinate interpolation.For entropy on the simplex, dual translations become multiplicative-weights reweighting, while quadratic mirror maps impose symmetry in the mirror metric.Source: §D.5 · p. 41, §1 · pp. 42–43

1. Fixed comparators: external regret is always mirror-exact. Fix u ∈K and set

• Mirror-exact regret is geometry-dependent: some deviations are exact under a quadratic mirror metric but not Euclidean-exact, because the mirror map changes which displacements telescope.Thus mirror-exactness is not merely Euclidean exactness expressed in different notation.Source: §1 · p. 44

D.6 Proofs for Section 8.2

• Under strong convexity, bounded gradients, and bounded potential oscillation, online mirror descent achieves sublinear regret against any feasible R-mirror-exact deviation with an optimized O(√T) bound.The proof derives a one-step inequality from dual updates and strong convexity, then bounds the telescoping potential term and optimizes the constant step size.Source: §D.6 · pp. 44–45

D.7 Proofs for Section 8.3

• Bregman proximal deviations are feasible and R-mirror-exact, so Bregman proximal regret is a special case of mirror-exact regret.Properness, lower semicontinuity, attainment, and single-valued continuity of the proximal map yield a differentiable potential through the Bregman–Moreau identity.Source: §D.7 · p. 46
• If the regularizer is m-strongly convex and the extended loss-plus-indicator is ρ-weakly convex with 0 ≤ρ < m, the proximal subproblem has a unique continuous solution map and online mirror descent controls proximal regret.The conjugate of the strongly convex sum is differentiable with 1/(m−ρ)-Lipschitz gradient, yielding continuity of the proximal solution map.Source: §8.3 · p. 14, §D.7 · pp. 46–47
• Theorem 8.6 identifies the Bregman proximal displacement with ∇_θΨ_F(θ_t), and applying Theorem 8.4 with L = 1 yields (9).The preceding argument proves relative smoothness of the potential function Ψ_F with L = 1.Source: §D.7 · p. 47

D.8 Proofs for Section 8.4

• Mirror exactness yields o(T) mirror-descent regret under regularity and bounded-gradient assumptions, whereas nonzero mirror circulation permits linear regret.The proof uses telescoping potential differences; under Lipschitz-gradient conditions, the resulting bound has an optimized square-root dependence on T.Source: §D.8 · pp. 48–50
• On relint(K), mirror exactness is equivalent to exactness of D(x)^T d∇R(x), symmetry of cross derivatives, and vanishing circulation on every closed loop.If these conditions fail, a sufficiently small loop has nonzero circulation and yields a linear lower bound; if they hold and extension assumptions apply, mirror descent has sublinear regret.Source: §D.8 · pp. 50–51

D.9 Proofs for Section 8.5

• Admissible Bregman proximal maps generate mirror-exact deviations, with dual endpoint potentials equal up to constants to convex conjugates of generator-plus-regularizer functions.The interpolation scale must satisfy the convexity threshold αLR(Ψ) ≤ 1, together with domain, weak-convexity, and regularity conditions.Source: §D.9 · pp. 51–53
• For 1 < p < 2, a smooth feasible mirror-exact deviation with globally Lipschitz potential gradient admits no positive admissible Bregman-proximal interpolation.Restricting the associated dual potential to a line makes it nonconvex for every α > 0.Source: §D.9 · pp. 53–54

D.10 Proofs for Section 9.1

• With a constant step size, mirror-descent iterates coincide with FTRL iterates for linearized losses and the tilted regularizer R − ⟨θ1, ·⟩.This follows by unrolling the dual update and applying Legendre duality; the tilted regularizer differs from the Bregman divergence centered at x1 only by a constant.Source: §D.10 · p. 54

D.11 Proofs for Section 9.2

• For FTRL, bounded gradients and an exact displacement potential support a telescoping regret analysis, while any closed loop with nonzero FTRL circulation yields cT − O(1/η) regret from every initial dual state.The lower-bound construction applies for every G > 0 and sufficiently small constant η.Source: §D.11 · pp. 55–56
• A dual loop can force FTRL to incur average regret at least c0G/(4Lγ) per round, yielding linear regret despite bounded gradients.The construction steers the dual state onto a polygonal approximation of the loop, where one traversal earns at least c0/(2η) regret.Source: §D.11 · p. 56
• For FTRL, a C1 deviation is exact if and only if its Jacobian is symmetric; nonzero skew derivative yields linear regret, whereas exact fields have sublinear regret.The obstruction is a nonzero circulation on a sufficiently small dual loop, while exactness follows from the Poincaré lemma and gives O(T^(1/q)) regret for q > 1.Source: §D.11 · p. 56

D.12 Proofs for Section 9.3

• FTRL-exact deviations form a strict subset of mirror-exact deviations: mirror descent achieves O(√T) regret on ϕp,ε, while FTRL can incur cT − O(1/η) regret against it.The strictness is witnessed by a continuous dual displacement with nonzero circulation, to which the FTRL linear-regret construction applies.Source: §D.12 · pp. 56–58

D.13 Proofs for Section 9.4

• For 1 < p ≤ 2 and q = p/(p − 1), the regularizer used in Corollary 9.9 yields the stated mirror-descent regret guarantee through (p − 1)-strong convexity.The proof extends strong convexity to the constrained domain using the normal cone and applies the general exact-form regret theorem.Source: §D.13 · p. 58
• For 2 ≤ p < ∞ and q = p/(p − 1), the optimized bound is p^(1/p)2^((p−2)/p)GL^(1/q)B^(1/p)T^(1/q), which is O(T^(1−1/p)).The bound follows from (2 − p, p)-uniform convexity of the regularizer and the general regret theorem.Source: §D.13 · p. 58

D.14 Proofs for Section 10

• No-regret learning with exact-form deviations produces εT-conservative correlated equilibrium, and radial closure preserves the equilibrium constraints for unrestricted feasible deviations.For OGD on Φi,exact(Bi, Li), εT ≤ maxi GiSource: §D.14 · p. 59
• For every finitely supported distribution in a convex game, µ ∈ CE iff µ ∈ ConCE iff µ ∈ PCE, yet an uncountably supported example has CE ⊊ ConCE = PCE.The counterexample is a two-player convex game whose distribution has uncountable support and marginals absolutely continuous with respect to two-dimensional Lebesgue measure.Source: §D.14 · pp. 59–60