PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax-Optimal Small-Loss Bounds for Online Linear Optimisation on $\ell_p$ Balls

Jack J. Mayo

arXiv:2610.36097v1cs.LGmath.OCstat.ML

TL;DR

For full-information online linear optimisation on finite-p norm balls, the paper asks whether the best comparator’s loss above each round’s minimum can replace the horizon in regret bounds. It develops adaptive FTRL and a switching extension, obtaining minimax small-loss guarantees and a comparison with FTL.

  • Problem

    The paper asks whether the best comparator’s loss above each round’s minimum can replace the horizon in OLO regret bounds without losing the transition between the two worst-case rates.

    Source: §1 · p. 1

  • Method

    A bounded radial FTRL regulariser pays stability from shifted loss and switches at most once to a quadratic augmentation, with a switching extension that alternates between FTL and standalone FTRL.

    Source: §1 · p. 2

  • Results

    The learner attains the minimax small-loss rate for fixed p without knowing the horizon or slack, with leading coefficient (2 + o(1))p/log p as p grows.

    Source: §1 · p. 1, §8 · p. 11

  • Takeaways & Limitations

    The switching extension preserves the sharp coefficient while guaranteeing Reg_T ≤ 2 Reg_T^FTL, and the stochastic analysis separates FTL’s variance term from regulariser bias.

    Source: §1 · p. 2

    The analysis assumes a known loss-norm bound and full information; extending the results beyond ℓp balls remains unresolved.

    Source: §5.3 · p. 9, §8 · p. 11

Abstract

from arXiv · show

We study full-information online linear optimisation on the unit $\ell_p$ ball in $\mathbb{R}^d$, for fixed $2\le p<\infty$ and losses of dual norm at most one. Let $\Delta_T$ denote the cumulative loss of the best fixed action above each round's minimum. A follow-the-regularised-leader (FTRL) algorithm attains, on every loss sequence and without knowing $T$ or $\Delta_T$, regret $O_p(1+\min\{\Delta_T^{1-1/p},\, d^{1/2-1/p}\sqrt{\Delta_T}\})$. Matching lower bounds show that this rate is minimax for each fixed $p$, and its constant $(2+o(1))p/\log p$ is optimal as $p\to\infty$ among guarantees uniform in $d$ and $T$. The algorithm uses a bounded radial regulariser and switches at most once to its quadratic augmentation. On some paths where follow-the-leader (FTL) has regret one, its regret grows with $T$. A switching extension keeps the sharp constant and also guarantees $\mathrm{Reg}_T\le 2\,\mathrm{Reg}_T^{\mathrm{FTL}}$. For i.i.d. losses whose mean has no zero coordinates, we compute the exact $\log T$ coefficient of the expected regret, which separates FTL's variance term from the bias of the regulariser.

1 Introduction

The paper studies small-loss regret for full-information online linear optimisation on finite- p norm balls, using the best fixed action’s loss above each round’s minimum as the slack. It presents an adaptive FTRL method, establishes minimax-optimal bounds, and relates them to existing OLO guarantees and FTL comparisons.

1 Introduction

  • The cancellation slack is the best fixed action’s cumulative shifted loss after subtracting each round’s minimum, and it vanishes on losses aligned along a common ray.The slack is the triangle-inequality slack in the support function of the unit ℓp ball.Source: §1 · p. 1
  • The FTRL learner attains the minimax small-loss rate without knowing the horizon or slack, with leading coefficient (2 + o(1))p/log p as p grows.Matching lower bounds make the rate minimax for each fixed p, and no causal learner improves the leading constant two.Source: §1 · p. 1
  • The bounded radial regulariser pays stability from the learner’s shifted loss, then switches at most once to a quadratic augmentation for a dimension-dependent cap.The two geometric bounds supply the power and square-root branches of the regret rate.Source: §1 · p. 2
  • On some paths where FTL has regret one, standalone FTRL’s regret grows with T, while a switching extension preserves the sharp coefficient and guarantees Reg_T ≤ 2 Reg_T^FTL without an additive term.The extension alternates between FTL and standalone FTRL.Source: §1 · p. 2

1.1 Related work

  • Prior OLO results include horizon-adaptive worst-case bounds, while the cited fixed-shape obstruction does not cover this learner’s threshold-triggered change of regulariser.Existing second-order and gradient-adaptive bounds are also discussed in relation to the cancellation slack.Source: §1.1 · pp. 2–3
  • For bounded i.i.d. losses with nonzero mean, the paper’s stochastic bound for fixed p > 2 attains the realised-comparator exponent without the logarithmic factor.The bound keeps the norm of the mean and cancellation separate.Source: §1.1 · p. 3

2 Protocol and main results

The protocol uses full-information losses on the unit ℓp ball and measures each action’s loss above the per-round minimum. The paper gives pathwise small-loss guarantees and minimax results under bounds on total loss norm and slack.

2.1 Protocol and loss geometry

  • The per-round shifted loss adds the support function h(θ) to the linear loss, making it nonnegative; the best fixed action’s cumulative shifted loss is the slack Δ_T.The slack measures disagreement between the losses and the best fixed action.Source: §2.1 · pp. 3–4
  • The bounds assume losses of dual norm at most one, and the learners know p and d but not the horizon or slack.Losses may be chosen adaptively, and the upper bounds hold pathwise and simultaneously for all horizons.Source: §2.1 · p. 4

2.2 Regret guarantees

  • For losses with dual norm at most one, the algorithms attain the small-loss rate with a coefficient asymptotic to (2 + o(1))p/log p, uniformly over dimensions and horizons.Algorithm 2 additionally guarantees Reg_T ≤ 2 Reg_T^FTL at every horizon.Source: §2.2 · p. 4

2.3 Minimax regret

  • Under upper bounds on total loss norm and slack, the minimax regret is characterized for H ≥ 1, while for H < 1 the value is exactly H.The lower bound uses oblivious losses; the upper bound also covers adversaries that see the current action.Source: §2.3 · p. 4
  • Sharp constants as a joint function of p, d, H, Δ, and T remain open.The paper optimizes a single coefficient required to hold for every dimension and horizon.Source: §2.3 · p. 4

3 Smoothing the support function

The paper smooths the support function with bounded radial and quadratic regularisers, then controls stability, approximation error, and changes of potential to obtain loss-adaptive bounds.

3.1 Regularisation and the regret decomposition

  • The regret decomposition separates one-round stability, terminal support deficit, and changes of potential, charging stability to each round’s shifted loss.Nondecreasing regularisation weights make potential changes nonpositive except at the single regulariser change.Source: §3.1 · p. 5

3.2 Radial and quadratic regularisers

  • The radial FTRL action follows the FTL ray, with its distance from the boundary set by exp(−h(y)/β).The bounded regulariser’s finite height controls approximation error, and its divergent boundary slope keeps FTRL actions in the interior.Source: §3.2 · p. 5
  • The shifted loss separates radial motion from angular misalignment, providing the quantities used to bound the regularisers’ stability.For an interior action x = ρu, the two components measure distance from the boundary along its ray and misalignment with the loss.Source: §3.2 · p. 5
  • The radial regulariser has cap 1 and is (r, 5/2)-shifted-loss stable, while the augmented regulariser has cap 1 + d^(1−2/p)/2 and is (2, κp)-stable.The augmented stability constant satisfies κp ∼ p/(2 log p), uniformly over d ≥ 2 its least possible value is (1 + o(1))p/(2 log p) as p grows.Source: §3.2 · pp. 5–6
  • Balancing cap-weighted approximation cost Cβ against stability cost κST/β^(r−1) sets the temperature scale for the regret bound.The resulting scale is C^(1−1/r)(κST)^(1/r), up to a factor depending only on r.Source: §3.2 · p. 6

4 Tuning by the shifted loss

The algorithm tunes regularisation from observed cumulative shifted loss, changing once from a radial phase to a quadratic-augmented phase. A separate stability argument bounds FTL’s regret against the slack.

4 Tuning by the shifted loss

  • The algorithm uses F1 until cumulative shifted loss crosses a threshold, then switches to F2; the single regulariser change incurs one bounded potential increase.It uses cumulative shifted loss from its played actions and retains the full cumulative loss vector across the change.Source: §4 · p. 6, §4.1 · p. 6

4.1 Regularisation schedule and algorithm

  • The crossover is set at d* ≥ d, and the radial scale εp ≤ 1 improves tracking of FTL.The quadratic temperature rises by a factor √mp relative to placing the crossover at the branch crossing d.Source: §4.1 · p. 6
  • For the augmented regulariser, the upper bounds require shifted-loss stability (2, κp), 1 ≤ κp ≤ p, and κp/√p → ∞.Using the elementary choice κp = p gives the same upper bounds and leading constants, but a later crossover and larger augmentation-bias coefficient.Source: §4.1 · p. 6

4.2 FTL regret against the slack

  • FTL’s regret is bounded against the slack using contraction of Bregman divergences along segments and a radius cutoff.For log(1 + R) = o(p), the cost per unit of slack bp(R) is approximately 2(p − 1)/log(1 + R), so increasing the radius reduces that cost logarithmically.Source: §4.2 · p. 7

5 An extension for comparison with FTL

Standalone FTRL attains the sharp small-loss bound but can incur large regret on paths where FTL performs well. A switching extension preserves the sharp coefficient and guarantees regret at most twice FTL’s.

5.1 Standalone costs relative to FTL

  • Standalone FTRL cannot guarantee a uniform multiplicative comparison with FTL: radial damping costs regret at p = 2, while quadratic augmentation tilts actions at p > 2.The examples show regret accumulating because the learner stays inside the ball or moves away from the fixed leader direction.Source: §5 · p. 7, §5.1 · p. 8

5.2 Switching rule

  • The learner switches between full-history FTL and regularised actions using accumulated regret contributions and their running maximum.It leaves FTL when A > 4(c + M) and returns when 2(c + M) > A; switching does not reset accumulated quantities or the cumulative loss vector.Source: §5.2 · p. 8

5.3 Regret of the switching extension

  • The switching tests control regret relative to FTL, while bounds for regularised blocks preserve the small-loss guarantee.The proof combines block stability, a possible one-time crossover charge, and terminal support deficit.Source: §5.3 · p. 9
  • The switching extension preserves the sharp small-loss coefficient and guarantees RegT ≤ 2 RegFTL_T.On the cited paths where FTL’s regret is one at every horizon, the extension’s regret is at most 2, while standalone FTRL grows with T.Source: §5 · p. 7, §5.3 · p. 9
  • The known loss-norm bound is essential: for losses of arbitrary norms, small-loss adaptation and a uniform FTL comparison cannot both be guaranteed.This boundary is stated for the switching extension’s combined guarantees.Source: §5.3 · p. 9

6 Sharp dependence on p

The paper proves that the leading constant in the small-loss bound is asymptotically optimal when guarantees are uniform over dimensions and horizons. A matching lower-bound construction and upper-bound analysis establish the constant two.

6.2 Matching upper bounds

  • The matching upper bounds use FTL’s slack bound and radial tracking to establish the leading coefficient for both algorithms.On the small-slack power branch, εp → 0 removes damping cost so both algorithms inherit FTL’s leading coefficient two.Source: §6 · p. 9, §6.2 · p. 9

6.1 A universal lower bound

  • The result optimizes a coefficient required to hold for every dimension and horizon; sharp constants jointly depending on p, d, H, Δ, and T remain open.At fixed dimension, the paper notes a separate bound with an implied constant independent of p, while fixed-dimension sharp constants remain unresolved.Source: §6.1 · p. 9
  • The uniform-in-dimension leading constant satisfies lim inf as p grows of (log p/p)CL(p) = 2, and no causal learner can improve it.The lower bound is [2 − O(1/log p)]p/log p, matching the paper’s upper bound.Source: §6.1 · p. 9
  • The lower-bound construction uses T + 1 mean-zero unit losses with T = ⌈2p⌉ in dimension O(p^6), yet has expected slack only log p + O(1).The construction lies on the power branch; a matching leading constant for the square-root branch alone remains open.Source: §6.1 · p. 9

7 Cancellation and fast stochastic rates

For bounded i.i.d. losses with nonzero mean, the paper separates cancellation from the norm of the mean in expected-regret bounds, then characterizes local logarithmic regret and the cost of smoothing.

7.1 Adaptation to stochastic signal

  • Both algorithms adapt separately to cancellation and the norm of the mean without knowing the mean, the cancellation parameter, or the horizon.Expected regret is decomposed into a nonnegative hindsight correction for comparing with the best realised action and pseudo-regret against the population minimiser.Source: §7 · p. 10, §7.1 · p. 10
  • For fixed p > 2, the stochastic horizon dependence is O_p(T^((p−2)/(2(p−1)))); as p approaches 2, the rate recovers logarithmic dependence.The exponent is necessary in dimension two for p > 2, while sharp joint dependence on dimension, mean norm, and cancellation remains open.Source: §7.1 · p. 10

7.2 Local curvature and the cost of smoothing

  • At p = 2 or when every coordinate of the mean is nonzero, FTL's expected regret divided by log T converges to 1/2 tr(∇²h(µ)Σ).Standalone FTRL has this variance coefficient plus an augmentation-bias term.Source: §7.2 · p. 10
  • The switching extension's asymptotic expected regret divided by log T is at most tr(∇²h(µ)Σ), independently of the augmentation-bias term.For standalone FTRL, the bias can arise because quadratic augmentation tilts the leader even without transverse statistical fluctuations; it vanishes when γ = 0 or ∇h(µ) is parallel to µ.Source: §7.2 · pp. 10–11

8 Discussion

The discussion recaps minimax small-loss guarantees and the switching extension, then identifies limitations in the rate's approach, implementation analysis, and open directions.

8 Discussion

  • Standalone FTRL attains the minimax small-loss rate for fixed p without knowing the horizon or slack, while the switching extension retains the sharp coefficient and has regret at most twice FTL's.For i.i.d. losses at means with no zero coordinates, standalone FTRL's logarithmic coefficient adds augmentation bias to FTL's variance term; the switching extension's coefficient is at most twice FTL's with no bias term.Source: §8 · p. 11
  • As p grows, the proved upper bounds approach the sharp leading coefficient slowly; the small-slack coefficient at the proof's radius cutoff exceeds 2p/log p by a factor 1 + (2 + o(1)) log log p/log p.The quadratic scale in the tuning also enters stochastic analysis through the augmentation-bias coefficient.Source: §8 · p. 11
  • Finite-precision guarantees and bit complexity remain unanalyzed; they would require action and support-evaluation error bounds, root-solver stopping rules, and control of switching-test errors.The open bit-complexity question includes actions exponentially close to the boundary.Source: §8 · p. 11
  • For p > 2, it remains open whether one fixed regulariser shape with an adaptive scalar temperature attains the anytime worst-case rate.A direct FTRL tuning rule that combines the sharp small-loss guarantee with a uniform comparison to FTL is also unknown for this learner.Source: §8 · p. 11
  • Beyond ℓp balls, it is unknown whether computable bounded regularisers with shifted-loss stability improve small-loss bounds for general symmetric convex bodies.The argument uses strict convexity; under bandit feedback, scalar observations do not directly reveal the per-round shift.Source: §8 · p. 11

AI disclosure

The disclosure describes AI assistance and states that the author verified the mathematical arguments and takes responsibility for the content.

AI disclosure

  • AI tools assisted with proof auditing, revisions, experiments, numerical verification, literature checks, and editing; the author says they verified the mathematical arguments by hand and bears responsibility for the content.Source: AI disclosure · p. 11

Guide to the appendices

The appendices organize the supporting geometry and stability estimates, from bounded regularisation and norm curvature through radial stability. Their lemmas connect those estimates to loss increments and radial-potential control.

Guide to the appendices

A Geometry and stability

  • The geometry section establishes bounded regularisation, support-function curvature, and radial and quadratic stability estimates.These local estimates support the later regret analysis and introduce the effective dual point.Source: A Geometry and stability · p. 14

A.1 Bounded regularisers

  • A bounded regulariser with cap C yields a differentiable conjugate whose gradient lies in K and whose support deficit is at most Cβ.The conjugate also satisfies Φβ(0) = 0.Source: §A.1 · p. 14

A.2 Transverse geometry and local curvature

  • The support geometry projects vectors onto the hyperplane transverse to ∇h(a), with h(Πaz) ≤ 2h(z); local curvature is positive semidefinite with kernel span{a}.The quadratic expansion requires local smoothness; the projection statement applies for a ≠ 0.Source: §A.2 · pp. 14–15

A.3 Radial stability

  • The radial-stability argument separates changes in norm from changes in direction and extends to general norms where its steps permit.Source: §A.3 · p. 16

A.3.1 Power estimates and normalised increments

  • Normalising a norm increment relates FTL’s regret increment and slack to the same shifted-loss quantity, enabling a divergence comparison.The comparison uses a bound on DP(m,u) relative to DP(v,u) to control regret by shifted loss.Source: §A.3.1 · p. 17

A.3.2 Radial decomposition and control

  • For Φ = ψ ◦ h, DΦ(a,b) = Dψ(h(a),h(b)) + ψ′(h(b))Dh(a,b); if h is any norm and ψ is convex continuously differentiable with 0 ≤ ψ′ ≤ 1, then 0 ≤ z ≤ 2s and DΦ(y−θ,y) ≤ z.Source: §A.3.2 · pp. 18–19

A.3.3 Proof of radial stability

The appendix proves radial and quadratic shifted-loss stability, including a matching asymptotic lower bound for the quadratic constant. It also explains how augmentation uses an effective dual point and how local estimates feed regret bounds.

A.3.3 Proof of radial stability

  • The radial regulariser F1 is (r, 5/2)-shifted-loss stable, using bounded regularisation and separate radial and angular controls.Source: §A.3.3 · pp. 19–20

A.4.1 Reduction to a curvature bound

  • Quadratic stability reduces to bounding a curvature ratio by 2κ, where the ratio compares inverse-Hessian curvature with shifted loss.The regulariser F2 is bounded, and this ratio condition implies (2, κ)-shifted-loss stability.Source: §A.4.1 · p. 20, §A.4 · p. 20

A.4.2 Interior estimate

  • The interior estimate gives F2 shifted-loss stability with constant eκp, which is below p.Source: §A.4.2 · p. 21

A.4.3 Scalar and matrix estimates

  • Scalar Bregman-cost and matrix comparisons provide the estimates used to control inverse curvature.The weighted scalar bound lower-bounds Dφ(w,v) by ςr(|v|)(w − v)^2, and the diagonal comparison bounds ζ⊤J−1ζ by ζ⊤J.Source: §A.4.3 · p. 22

A.4.4 Boundary estimate and the stability constant

  • κp ∼ p/(2 log p) as p grows, after the boundary estimate improves the interior stability constant.The resulting boundary bound is at most 2κp and establishes (2, κp)-shifted-loss stability.Source: §A.4.4 · p. 24

A.4.5 A matching lower bound

  • For d ≥ 2, a two-dimensional near-boundary witness gives a matching lower bound, so the quadratic stability constant is asymptotically p/(2 log p) uniformly in dimension.The witness embeds in every higher dimension.Source: §A.4.5 · pp. 24–25

A.5 The effective dual point

  • Quadratic augmentation acts through an effective dual point w, with x = ∇P(w) and w = y − qx.The conjugate gradient at y equals the original conjugate gradient at that point.Source: §A.5 · p. 25

B Tuning by the shifted loss

  • The tuning analysis converts local stability into regret bounds in the learner’s shifted loss and bounds FTL regret by slack.Appendix D.4 supplies the standalone guarantee in slack and its sharp coefficient.Source: B Tuning by the shifted loss · p. 25

B.1 Tuning from observed shifted loss

The tuning analysis controls stability, regularisation cost, and the one possible potential increase when the regulariser changes. It also develops selected-round tracking and radius-dependent FTL stability for the switching extension.

B.1 Tuning from observed shifted loss

  • On selected rounds, the tuning proposition bounds stability by increments of Wp and bounds the support deficit by C(Ut); standalone regret is bounded by ΥWp(ST,d*) + C(ST).For the switching algorithm, the proposition also gives a guarantee on its FTRL rounds.Source: §B.1 · p. 26
  • The potential is nonincreasing within each phase, and its only possible increase is charged once at the change to F2.The crossover charge is made once across the execution, even when selected rounds form multiple FTRL blocks.Source: §B.1 · pp. 26–27

B.2 Temperature growth, the implicit inequality, and radial tracking

  • Selected-round radial tracking bounds the cumulative loss using the temperature cap B, horizon T, and slack Δ.Source: §B.2 · p. 28

B.3 Radius-dependent FTL stability

  • After the last FTL step within radius R, the analysis bounds later FTL regret relative to slack using a radius-dependent coefficient.The proof balances an initial cost of order R against the later cost per unit of slack.Source: §B.3 · p. 29

C The switching extension

C.1 Pathwise comparison with FTL

This section compares FTRL with FTL on specific paths, develops a switching comparison and coordinatewise potential, and establishes minimax bounds using a finite-horizon lower-bound construction with controlled expected slack. It also examines logarithmic regret coefficients for collinear paths and the asymptotically optimal coefficient, noting limitations at the Euclidean endpoint and when loss norms are unbounded.

C.1 Pathwise comparison with FTL

  • FTL has regret exactly 1 on the constructed paths, while Algorithm 1 incurs at least λT/2 on one of them.The collinear construction also gives standalone FTRL a logarithmic regret coefficient mp/F^2, which vanishes at p = 2.Source: §C.1 · pp. 31–32

C.2.1 Running maximum and comparison with FTL

  • The switching analysis controls the running maximum and preserves FTL regret when no FTRL rounds occur.The tuned bound is obtained through a bound on the FTRL blocks and their contribution to the final running maximum.Source: §C.2.1 · p. 32

C.2.2 Controlling the FTRL blocks

  • Under the condition c + MT ≤ 2ET + 3CT, the result bounds regret RegT by 5(2ET + 3CT) + 2 − c.Source: §C.2.2 · p. 33

C.2.3 Constants and the slack bound

  • Algorithm 2 satisfies RegT ≤ Asw + BswWp(UT, d∗), and Appendix D.4 sharpens the coefficient to (2 + o(1))p/log p.Source: §C.2.3 · p. 34

C.3 Loss normalisation and the FTL comparison

  • Without a loss-norm bound, no deterministic causal learner can both guarantee a fixed finite-factor comparison with FTL on every sequence and attain the sharp rate on all unit-norm paths.The proposition states that such a learner must play the exposed FTL action after every realisable nonzero history.Source: §C.3 · p. 35

D.1 Minimax regret

  • For the minimax problem, the upper bound is O_p(1 + W_p(n,d)), and coordinate-sign constructions give a matching-order lower bound.The constructions constrain loss mass and slack, and the lower-bound argument uses zero expected learner loss.Source: §D.1 · pp. 35–36

D.2.1 The finite-horizon construction

  • The finite-horizon lower-bound proposition applies to causal learners whose regret guarantee holds for every deterministic loss sequence, using a push–reverse construction with conditionally mean-zero losses.The construction uses only the first N0 coordinates; pushes raise a shared amplitude, while reversals move one coordinate near unit magnitude and remove it from future losses.Source: §D.2.1 · p. 36

D.2.2 Expected slack and the finite-horizon bound

  • The construction gives E[∆T+1] ≤ Up(T), while every causal learner has expected cumulative loss zero under its random losses.These facts yield the stated finite-horizon lower bound by averaging over the adversary’s random signs and coins.Source: §D.2.2 · pp. 37–38

D.2.3 Consequences for the coefficient

  • (2+o(1))p/log p is the optimal uniform-in-dimension-and-horizon coefficient as p tends to infinity.The proof takes T = ⌈2p⌉ in the finite-horizon bound and combines it with the appendix upper bound.Source: §D.2.3 · p. 38

D.3 An FTL refinement for small slack

  • A coordinatewise capped-power potential telescopes to refine the FTL comparison, with the slack coefficients bounded by 2√p.The potential uses ϖ(x) = min{|x|, 1}^r, and the argument divides rounds into three ranges.Source: §D.3 · pp. 38, 40

D.4 The leading constants

The leading-constant analysis establishes a uniform asymptotic coefficient of (2 + o(1))p/log p, with a matching lower bound. The stochastic analysis separates population excess loss from the hindsight correction.

D.4 The leading constants

  • At p = 2, the stated finite coefficient is 70.66… and therefore less than 71.The finite-coefficient bounds remain bounded as p decreases to 2.Source: §D.4 · p. 41
  • (2 + o(1))p/log p is the upper asymptotic coefficient, uniform over dimensions and horizons, and the matching lower bound makes it optimal.The proof covers all dimensions, horizons, and loss paths; its remainders depend only on p.Source: §D.4 · pp. 41–42
  • For sufficiently large p, the small-slack power branch yields the leading coefficient, while the quadratic-phase regime contributes only o(p/log p).The argument rules out quadratic actions in the small-slack case and bounds the remaining regime as lower order.Source: §D.4 · p. 42

E Stochastic adaptation and local asymptotics

  • The stochastic analysis separates population excess loss from the hindsight correction, whose forward remainder is linearised at μ.The standalone temperatures are denoted β1(St−1) and β2(St−1).Source: E Stochastic adaptation and local… · p. 42

E.1 Stochastic signal and cancellation

The stochastic analysis combines expected-slack control, local curvature, and bounds for baseline learners. It also gives an exact scalar-root procedure for computing quadratic actions.

E.1 Stochastic signal and cancellation

  • The population-excess analysis bounds loss on a good event and controls atypical events exponentially; FTL uses the same good-event argument without perturbation or damping.The switching extension transfers the FTL bound.Source: §E.1 · pp. 44–45
  • EΔT ≤ γT lets Jensen's inequality convert the pathwise theorem into the first expected-regret branch; taking the smaller bound yields the stated conclusion.The argument uses that Wp is increasing and concave.Source: §E.1 · pp. 43, 45

E.2 Local curvature and stochastic limits

  • The local expansion gives nE[(an−μ)(an−μ)^T] → Σ + k²∇h(μ)∇h(μ)^T, with the cross term vanishing.The calculation applies second-order Taylor expansions to the empirical mean and its regularisation perturbation.Source: §E.2 · p. 45

F Baseline reductions

  • A shifted-loss doubling scheme converts per-epoch regret O(√(bB)) into RegT = O(b + √(bΔT)) for every horizon.The implicit constant depends only on the per-epoch bound's constant.Source: F Baseline reductions · p. 45

F.1 The Euclidean bound from cone multiplicative weights

  • O(1 + √ΔT) is available with a universal dimension-independent constant for Euclidean balls using restarted symmetric-cone multiplicative weights.The guarantee holds simultaneously for every horizon.Source: §F.1 · p. 46

F.2 A general-body bound from norm perturbations

  • O(d + √(dΔT)) holds for general centrally symmetric convex bodies using norm perturbations and exact expected perturbed-leader and support oracles.The learner is deterministic and the pathwise bound covers adaptive loss paths.Source: §F.2 · p. 47

F.3 A general-body bound from MetaGrad

  • O(d log(T + 1) + √(dΔT log(T + 1))) is the MetaGrad Full bound after running it in coordinates where the body is sandwiched by Euclidean balls.The guarantee holds simultaneously for every horizon.Source: §F.3 · p. 47

G Computing the quadratic actions

  • The quadratic action is computed by solving one monotone scalar equation, with d independent coordinate solves per evaluation.The coordinate solutions define a continuous, strictly decreasing sum with a unique root specifying the exact oracle.Source: G Computing the quadratic actions · p. 48
Loading 2610.36097v1…