Fast Rates for Swap-Agnostic Learning of Proper Losses

# Fast Rates for Swap-Agnostic Learning of Proper Losses
Source: [https://arxiv.org/html/2607.28856](https://arxiv.org/html/2607.28856)
###### Abstract

Swap\-agnostic learning strengthens classical agnostic learning by allowing the comparator to use a different hypothesis on each prediction level set\. This benchmark captures prediction\-dependent postprocessing\. However, allowing the comparator to depend on the prediction value seems to require solving a separate agnostic\-learning problem at each possible prediction value\. We show that, for proper losses, these prediction\-level comparisons can be controlled jointly\.

Our main result is an offline swap\-agnostic learner for any fixed proper loss\. For a finite hypothesis classℋ\\mathcal\{H\}, the excess risk for a fixed smooth proper loss scales asO~​\(\(log⁡\(\|ℋ\|\)/m\)2/3\)\\widetilde\{O\}\(\(\\log\(\|\\mathcal\{H\}\|\)/m\)^\{2/3\}\)frommmi\.i\.d\. samples, with the corresponding online swap regret scaling asO~​\(T1/3​\(log⁡\|ℋ\|\)2/3\)\\widetilde\{O\}\(T^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\)\.

We also give algorithms whose predictions are swap\-agnostic simultaneously for entire families of losses\. For all proper losses bounded in\[−1,1\]\[\-1,1\], the rates areO~​\(T​log⁡\|ℋ\|\)\\widetilde\{O\}\(\\sqrt\{T\\log\|\\mathcal\{H\}\|\}\)online andO~​\(log⁡\|ℋ\|/m\)\\widetilde\{O\}\(\\sqrt\{\\log\|\\mathcal\{H\}\|/m\}\)offline\. For convex11\-Lipschitz proper losses, the rates improve toO~​\(T1/3​\(log⁡\|ℋ\|\)2/3\)\\widetilde\{O\}\(T^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\)online andO~​\(\(log⁡\|ℋ\|/m\)2/3\)\\widetilde\{O\}\(\(\\log\|\\mathcal\{H\}\|/m\)^\{2/3\}\)offline\. These rates are tight up to logarithmic factors and improve on theO~​\(T2/3​\(log⁡\|ℋ\|\)1/3\)\\widetilde\{O\}\(T^\{2/3\}\(\\log\|\\mathcal\{H\}\|\)^\{1/3\}\)rates implied by the swap\-omniprediction guarantee ofLuo et al\. \([2025](https://arxiv.org/html/2607.28856#bib.bib26)\)\. Our main technical approach reduces swap\-agnostic learning to a second\-order form of multicalibration, which we obtain using Blackwell approachability with a Bernstein\-style variance correction\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2607.28856#S1)1. [1\.1Contributions](https://arxiv.org/html/2607.28856#S1.SS1) 2. [1\.2Technical overview](https://arxiv.org/html/2607.28856#S1.SS2) 3. [1\.3Relation to prior work](https://arxiv.org/html/2607.28856#S1.SS3)
2. [2Preliminaries](https://arxiv.org/html/2607.28856#S2)1. [2\.1Swap Agnostic Learning](https://arxiv.org/html/2607.28856#S2.SS1) 2. [2\.2Online Protocol and Swap Regret](https://arxiv.org/html/2607.28856#S2.SS2) 3. [2\.3Conditional risks and proper losses](https://arxiv.org/html/2607.28856#S2.SS3) 4. [2\.4Finite covers](https://arxiv.org/html/2607.28856#S2.SS4)
3. [3Second\-Order Multicalibration](https://arxiv.org/html/2607.28856#S3)1. [3\.1Algorithm](https://arxiv.org/html/2607.28856#S3.SS1) 2. [3\.2Square\-root form by scaling the test class](https://arxiv.org/html/2607.28856#S3.SS2) 3. [3\.3Offline conversion](https://arxiv.org/html/2607.28856#S3.SS3)
4. [4Lipschitz Proper Losses](https://arxiv.org/html/2607.28856#S4)1. [4\.1A single Lipschitz loss](https://arxiv.org/html/2607.28856#S4.SS1) 2. [4\.2Finite families of Lipschitz losses](https://arxiv.org/html/2607.28856#S4.SS2) 3. [4\.3All Lipschitz proper losses through monotone transforms](https://arxiv.org/html/2607.28856#S4.SS3)
5. [5Bounded Proper Losses](https://arxiv.org/html/2607.28856#S5)1. [5\.1The V\-shaped decomposition and the main theorem](https://arxiv.org/html/2607.28856#S5.SS1) 2. [5\.2Controlling a finite set of thresholds](https://arxiv.org/html/2607.28856#S5.SS2) 3. [5\.3From finitely many thresholds to every threshold](https://arxiv.org/html/2607.28856#S5.SS3) 4. [5\.4Assembling the bound](https://arxiv.org/html/2607.28856#S5.SS4) 5. [5\.5Lower bounds](https://arxiv.org/html/2607.28856#S5.SS5)
6. [6Convex11\-Lipschitz Proper Losses](https://arxiv.org/html/2607.28856#S6)
7. [7Beyond Proper Losses](https://arxiv.org/html/2607.28856#S7)
8. [8Discussion and Open Problems](https://arxiv.org/html/2607.28856#S8)
9. [References](https://arxiv.org/html/2607.28856#bib)

## 1Introduction

Classical agnostic learning asks a learner to compete with the best fixed hypothesis in a reference classℋ\\mathcal\{H\}, without assuming realizability\(Vapnik,[1998](https://arxiv.org/html/2607.28856#bib.bib32); Shalev\-Shwartz and Ben\-David,[2014](https://arxiv.org/html/2607.28856#bib.bib31)\)\. In the offline setting, the learner receives i\.i\.d\. samples from an unknown distribution𝒟\\mathcal\{D\}over\(X,Y\)\(X,Y\)and outputs a predictor; for a lossℓ​\(p,y\)\\ell\(p,y\), the benchmark asks whether the predictor performs nearly as well as the best single hypothesish∈ℋh\\in\\mathcal\{H\}\.

In many applications, however, the prediction is not the final decision\. A probability forecast may be thresholded, discretized, or passed to a cost\-sensitive decision rule, and changing the downstream costs changes the optimal threshold and therefore the decision rule that gets applied\. A clinical risk score triggers different follow\-up protocols at low, medium, and high risk; a credit score is routed to different underwriting policies across score bands; an ad\-ranking score is postprocessed differently for cold\-start items than for high\-confidence ones\(Grundy et al\.,[2019](https://arxiv.org/html/2607.28856#bib.bib17); Consumer Financial Protection Bureau,[2024](https://arxiv.org/html/2607.28856#bib.bib6); Ardywibowo et al\.,[2025](https://arxiv.org/html/2607.28856#bib.bib2)\)\. In each case the predicted probability is an input to a later decision rather than the action itself – the standard role of probabilistic predictions in cost\-sensitive classification and surrogate\-loss theory\(Elkan,[2001](https://arxiv.org/html/2607.28856#bib.bib8); Bartlett et al\.,[2006](https://arxiv.org/html/2607.28856#bib.bib3)\), and central to the decision\-theoretic interpretation of proper scoring rules\(Dawid,[1982](https://arxiv.org/html/2607.28856#bib.bib7); Gneiting and Raftery,[2007](https://arxiv.org/html/2607.28856#bib.bib13)\)\.

Swap\-agnostic learning strengthens the comparator to reflect exactly this freedom\(Gopalan et al\.,[2023](https://arxiv.org/html/2607.28856#bib.bib15)\)\. Rather than asking whether one fixed hypothesis beats the predictor globally, it asks whether the predictor can be improved after first looking at its own predicted value\. If predictions lie on the gridΓN=\{γi=i/N:0≤i≤N\}\\Gamma\_\{N\}=\\\{\\gamma\_\{i\}=i/N:0\\leq i\\leq N\\\}, a hypothesis swap is a mapϕ:ΓN→ℋ\\phi:\\Gamma\_\{N\}\\to\\mathcal\{H\}, and when the learner predictsppthe comparator answers withϕ​\(p\)\\phi\(p\)instead of one fixed hypothesis – so a score near0\.10\.1and a score near0\.90\.9may be judged against entirely different hypotheses\. For a randomized offline predictorp^\\hat\{p\}, this gives the excess\-risk benchmark

SwapAgn𝒟⁡\(ℓ,ℋ\)=supϕ:ΓN→ℋ𝔼​\[ℓ​\(p,Y\)−ℓ​\(ϕ​\(p\)​\(X\),Y\)\],\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\sup\_\{\\phi:\\Gamma\_\{N\}\\to\\mathcal\{H\}\}\\mathbb\{E\}\\\!\\left\[\\ell\(p,Y\)\-\\ell\(\\phi\(p\)\(X\),Y\)\\right\],with\(X,Y\)∼𝒟\(X,Y\)\\sim\\mathcal\{D\}andp∼p^​\(X\)p\\sim\\hat\{p\}\(X\), and online it becomes swap regret,

SwapRegT⁡\(ℓ,ℋ\)=supϕ:ΓN→ℋ∑t=1T\[ℓ​\(pt,yt\)−ℓ​\(ϕ​\(pt\)​\(xt\),yt\)\]\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\sup\_\{\\phi:\\Gamma\_\{N\}\\to\\mathcal\{H\}\}\\sum\_\{t=1\}^\{T\}\\left\[\\ell\(p\_\{t\},y\_\{t\}\)\-\\ell\(\\phi\(p\_\{t\}\)\(x\_\{t\}\),y\_\{t\}\)\\right\]\.Ordinary agnostic learning is recovered when the same hypothesis is used at every prediction level, so swap\-agnostic learning is never easier than the ordinary benchmark – the question is how much harder it really is\.

A natural first approach already suggests a worrying answer\. A standard multicalibration\-based algorithm can be read as solving a separate agnostic\-learning problem inside each of theN\+1N\+1prediction buckets; if bucketiicollectsnin\_\{i\}examples, summing the usualni\\sqrt\{n\_\{i\}\}\-type rates over all of them produces an apparentN\\sqrt\{N\}overhead, and the known route to swap\-agnostic learning through multicalibration does indeed yieldO~​\(T2/3​\(log⁡\|ℋ\|\)1/3\)\\widetilde\{O\}\(T^\{2/3\}\(\\log\|\\mathcal\{H\}\|\)^\{1/3\}\)swap regret\(Hébert\-Johnson et al\.,[2018](https://arxiv.org/html/2607.28856#bib.bib16); Gopalan et al\.,[2023](https://arxiv.org/html/2607.28856#bib.bib15); Luo et al\.,[2025](https://arxiv.org/html/2607.28856#bib.bib26)\)\. This bucket\-by\-bucket analysis does not tell us whether the extra cost is real, or just an artifact of treating every bucket as its own independent statistical problem\.

###### Question 1\(Single\-loss swap\-agnostic learning\)\.

Can offline swap\-agnostic learning for a fixed proper loss avoid paying a separate statistical price for every prediction bucket?

A second question arises once the downstream objective is allowed to move\. Omniprediction asks for one predictor that supports near\-optimal decisions for many losses at once\(Gopalan et al\.,[2022](https://arxiv.org/html/2607.28856#bib.bib14)\); in the swap setting, swap omniprediction asks the same predictor to be swap\-agnostic for every loss in a family,111Swap omniprediction lets the comparator choose a different loss, together with a different hypothesis, at every prediction level, so the loss itself is swapped along with the hypothesis\. Question 2 instead fixes one loss for the entire run and asks a single predictor to satisfy the ordinary swap\-agnostic guarantee for every such loss, one at a time; the comparator never swaps between losses within a run\.[Section1\.3](https://arxiv.org/html/2607.28856#S1.SS3)makes this ordering of benchmarks precise\.and the existing route to that guarantee runs through multicalibration as well\(Gopalan et al\.,[2023](https://arxiv.org/html/2607.28856#bib.bib15)\), inheriting the same quantitative overhead\.

###### Question 2\(Simultaneous swap\-agnostic learning for loss families\)\.

Can one offline predictor be swap\-agnostic simultaneously for broad families of proper losses, such as bounded proper losses or convex11\-Lipschitz proper losses?

We answer both questions affirmatively, and the key to both is the same: stop treating prediction buckets as independent statistical problems, and instead measure directly how favorable each bucket already is to the predictor before paying anything to correct it\. A single algorithmic guarantee – a second\-order strengthening of multicalibration developed in[Section˜3](https://arxiv.org/html/2607.28856#S3)– turns this favorable measurement into a bound that absorbs the bucket cost instead of paying it once per bucket\. The rest of this section describes what this buys us and how it works\.

### 1\.1Contributions

#### A single proper loss\.

For any proper lossℓ\\ellwithLL\-Lipschitz partial losses and finite hypothesis classℋ\\mathcal\{H\}, one algorithm achieves

SwapRegT⁡\(ℓ,ℋ\)=O~​\(L​T1/3​\(log⁡\|ℋ\|\)2/3\)​online,SwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(L​\(log⁡\|ℋ\|m\)2/3\)​offline,\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\big\(LT^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\\big\)\\ \\text\{online,\}\\qquad\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\Big\(L\\big\(\\tfrac\{\\log\|\\mathcal\{H\}\|\}\{m\}\\big\)^\{2/3\}\\Big\)\\ \\text\{offline,\}with no convexity assumption needed \([Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)\)\. Both exponents are tight, matching anΩ​\(T1/3\)\\Omega\(T^\{1/3\}\)lower bound for the half\-Brier loss against a fixed three\-hypothesis class \([Theorem˜4\.7](https://arxiv.org/html/2607.28856#S4.Thmtheorem7)and[Section˜4\.1](https://arxiv.org/html/2607.28856#S4.SS1)\)\.

#### Families of losses\.

The same guarantee extends at only a logarithmic cost\. A finite familyℒ\\mathcal\{L\}sharing a Lipschitz constant costs an extralog⁡\|ℒ\|\\log\|\\mathcal\{L\}\|\([Theorem˜4\.9](https://arxiv.org/html/2607.28856#S4.Thmtheorem9)\)\. Every bounded proper loss decomposes into a positive mixture of V\-shaped basis losses\(Kleinberg et al\.,[2023](https://arxiv.org/html/2607.28856#bib.bib23); Li et al\.,[2022](https://arxiv.org/html/2607.28856#bib.bib24)\), but these are nonsmooth, so controlling them needs a localized version of the algorithm together with a new argument that extends the guarantee from finitely many thresholds to every threshold at once \([Section˜5](https://arxiv.org/html/2607.28856#S5)\)\. This gives*every*proper loss bounded in\[−1,1\]\[\-1,1\]at once the coarser rate

SwapRegT⁡\(ℓ,ℋ\)=O~​\(T​log⁡\|ℋ\|\)​online,SwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(log⁡\|ℋ\|/m\)​offline,\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\big\(\\sqrt\{T\\log\|\\mathcal\{H\}\|\}\\big\)\\ \\text\{online,\}\\qquad\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\big\(\\sqrt\{\\log\|\\mathcal\{H\}\|/m\}\\big\)\\ \\text\{offline,\}uniformly overℓ\\ell\([Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)\), matching known lower bounds \([Sections˜5\.5](https://arxiv.org/html/2607.28856#S5.SS5)and[5\.5](https://arxiv.org/html/2607.28856#S5.SS5)\)\. This extends the payoff\-bounded downstream\-task guarantee ofHu and Wu \([2024](https://arxiv.org/html/2607.28856#bib.bib18)\)to hypothesis\-valued comparators\.

#### Convex Lipschitz losses\.

We prove a new positive decomposition of every convex11\-Lipschitz proper loss into clipped\-ReLU basis losses \([Section˜6](https://arxiv.org/html/2607.28856#S6)\), which recovers the sharper single\-loss exponents for the entire family at once,

SwapRegT⁡\(ℓ,ℋ\)=O~​\(T1/3​\(log⁡\|ℋ\|\)2/3\)​online,SwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(\(log⁡\|ℋ\|m\)2/3\)​offline,\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\big\(T^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\\big\)\\ \\text\{online,\}\\qquad\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\Big\(\\big\(\\tfrac\{\\log\|\\mathcal\{H\}\|\}\{m\}\\big\)^\{2/3\}\\Big\)\\ \\text\{offline,\}uniformly overℓ\\ell\([Theorem˜6\.2](https://arxiv.org/html/2607.28856#S6.Thmtheorem2)\)\.

#### Beyond proper losses\.

Canonical properization \([Section˜7](https://arxiv.org/html/2607.28856#S7)\) transfers every rate above, with no loss in the exponent, to an arbitrary bounded binary loss evaluated after best\-response postprocessing: the relevant comparator complexity becomes the loss’s own slope class rather thanℋ\\mathcal\{H\}directly \([Section˜7](https://arxiv.org/html/2607.28856#S7)\)\.

#### The underlying engine\.

All of this follows from one online guarantee, second\-order multicalibration\. For a transcript\(xt,pt,yt\)\(x\_\{t\},p\_\{t\},y\_\{t\}\)and a testg:𝒳×ΓN→\[−1,1\]g:\\mathcal\{X\}\\times\\Gamma\_\{N\}\\to\[\-1,1\], write

BiasT⁡\(g\)=∑t=1T\(yt−pt\)​g​\(xt,pt\),MassT⁡\(g\)=∑t=1Tg​\(xt,pt\)2\.\\operatorname\{Bias\}\_\{T\}\(g\)=\\sum\_\{t=1\}^\{T\}\(y\_\{t\}\-p\_\{t\}\)g\(x\_\{t\},p\_\{t\}\),\\qquad\\operatorname\{Mass\}\_\{T\}\(g\)=\\sum\_\{t=1\}^\{T\}g\(x\_\{t\},p\_\{t\}\)^\{2\}\.Our algorithm guarantees, simultaneously for every test in a fixed finite class and with high probability,

BiasT⁡\(g\)≤c​MassT⁡\(g\)\+a,\\operatorname\{Bias\}\_\{T\}\(g\)\\leq c\\,\\operatorname\{Mass\}\_\{T\}\(g\)\+a,for a learning\-rate\-dependent constantccand an additive termaascaling with the log\-size of the test class \([Section˜3](https://arxiv.org/html/2607.28856#S3), achieved with high probability by[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3)\)\. An online\-to\-batch conversion \([Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)\) transfers this bound offline; every rate above comes from tuningccto the loss or family at hand, exactly as the technical overview below explains\.

### 1\.2Technical overview

Fix one proper lossℓ\\ell\. When a predictionppis compared against an alternative predictionqq, the proper\-loss identity of[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3)splits the comparison into two pieces:

ℓ​\(p,y\)−ℓ​\(q,y\)=\(y−p\)​\(Δℓ​\(p\)−Δℓ​\(q\)\)⏟bias term−\[Lp​\(q\)−Lp​\(p\)\]⏟drift term≥0\.\\ell\(p,y\)\-\\ell\(q,y\)=\\underbrace\{\(y\-p\)\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)\}\_\{\\text\{bias term\}\}\-\\underbrace\{\[L\_\{p\}\(q\)\-L\_\{p\}\(p\)\]\}\_\{\\text\{drift term\}\\ \\geq 0\}\.\(1\)The bias term is proportional to the calibration residualy−py\-p; it is what ordinary multicalibration controls, and controlling it directly bucket by bucket is exactly the expense identified above\. The drift term is always nonnegative – moving the prediction away from a bucket’s best response is only ever penalized, never rewarded, once the truth is revealed – and, crucially, it grows with precisely the quantity that makes the bias term large in the first place,Δℓ​\(p\)−Δℓ​\(q\)\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\. A quadratic\-growth inequality \([Section˜4](https://arxiv.org/html/2607.28856#S4)\) makes this precise:\(Δℓ​\(p\)−Δℓ​\(q\)\)2≲K⋅\[Lp​\(q\)−Lp​\(p\)\]\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)^\{2\}\\lesssim K\\cdot\[L\_\{p\}\(q\)\-L\_\{p\}\(p\)\]for a constantKKgoverned by the loss’s Lipschitz or smoothness constant\. So the same quantity that makes a bucket’s comparison risky also makes that bucket’s own drift large: the drift is collateral the loss’s geometry already offers, and the only remaining question is how to collect on it\.

This is exactly what second\-order multicalibration is for\. The online algorithm’s guarantee bounds the bias term,BiasT⁡\(g\)\\operatorname\{Bias\}\_\{T\}\(g\), by a constant multiple ofMassT⁡\(g\)\\operatorname\{Mass\}\_\{T\}\(g\)plus an additive term, where the constant is set by the learning rate\. Tuning the learning rate so that this constant matchesKKexactly \([Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)\) makes the quadratic bias and drift terms cancel identically, leaving only the additive term, which scales withlog⁡\|ℋ\|\\log\|\\mathcal\{H\}\|rather than with the number of prediction buckets\. Balancing the grid resolutionNNagainst this cancellation – a finer grid shrinks discretization error but creates more tests to control – then gives theT1/3T^\{1/3\}online andm−2/3m^\{\-2/3\}offline exponents\. This is precisely where the improvement over the bucket\-wise route occurs: that route pays an ordinary agnostic\-learning regret independently inside each bucket, so refining the grid also multiplies the number of independently\-paid\-for buckets, whereas here the offset lets the per\-bucket cost enter only additively, throughlog⁡\|ℋ\|\\log\|\\mathcal\{H\}\|– which is why the algorithm can afford a finer grid before discretization error dominates, landing atT1/3T^\{1/3\}instead ofT2/3T^\{2/3\}\.

The reduction is modular in a way that pays off immediately for families of losses: once a loss has told the algorithm which selector tests to control, the algorithm itself does not care which loss those tests came from\. A finite familyℒ\\mathcal\{L\}is therefore handled by simply pooling every loss’s tests into one larger test class, and since the guarantee depends only logarithmically on test\-class size, pooling in\|ℒ\|\|\\mathcal\{L\}\|losses’ worth of tests adds onlylog⁡\|ℒ\|\\log\|\\mathcal\{L\}\|to the bound rather than multiplying it\. Infinite families need the further idea already mentioned above – writing a complicated loss as a positive mixture of simpler basis losses, with prediction\-independent affine terms canceling against every comparator – and for bounded proper losses the relevant basis is the V\-shaped threshold decomposition ofKleinberg et al\. \([2023](https://arxiv.org/html/2607.28856#bib.bib23)\); Li et al\. \([2022](https://arxiv.org/html/2607.28856#bib.bib24)\)\([Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)\)\. These basis losses are nonsmooth – their slope jumps discontinuously at the threshold – so the single\-loss cancellation argument above \([Section˜4](https://arxiv.org/html/2607.28856#S4)\) does not apply to them directly\. Instead we run a*localized*version of the algorithm, with one test per prediction bucket that is active only on the rounds where the prediction equals that bucket’s grid value, since the favorable drift near a V\-shaped threshold depends on the distance from the current prediction to the threshold \([Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)\), which differs bucket by bucket rather than being governed by one global constant\. Second\-order control on every bucket’s test at once, followed by a harmonic\-sum argument in which buckets near the threshold contribute little while distant buckets contribute favorably \([Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)\), recombines these per\-bucket pieces into the square\-root rate for finitely many thresholds \([Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)\); a finite\-range assumption on the comparator class then extends this exactly to every threshold at once \([Section˜5\.3](https://arxiv.org/html/2607.28856#S5.SS3)\), giving the square\-root rate for the whole bounded\-proper\-loss family \([Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)\)\. For convex11\-Lipschitz proper losses, a different positive decomposition into clipped\-ReLU losses \([Section˜6](https://arxiv.org/html/2607.28856#S6)\) is rich enough to represent the whole family while still admitting a finite cover with useful metric entropy, and combining that cover with the offline conversion recovers the sharper single\-loss exponents for the entire family \([Theorem˜6\.2](https://arxiv.org/html/2607.28856#S6.Thmtheorem2)\)\. Canonical properization \([Section˜7](https://arxiv.org/html/2607.28856#S7)\) then carries every one of these guarantees past proper losses, since best\-response postprocessing of an arbitrary bounded loss reduces exactly to swap\-agnostic learning of one proper loss with redundant messages\.

It remains to produce the online guarantee itself and to carry it from the online setting to the offline one\. The algorithm is a multiplicative\-weights implementation of Blackwell approachability\(Blackwell,[1956](https://arxiv.org/html/2607.28856#bib.bib1)\): weights on tests summarize the direction in which the transcript so far most needs correcting, and the next prediction is chosen to make progress against that direction\. Two adjustments turn this into the second\-order guarantee we need\. Predictions must live on a finite grid, so the algorithm randomizes over two adjacent grid points, which behaves like the desired real\-valued forecast and costs only the usual grid\-rounding term\. And the potential itself is adjusted with a Bernstein correction that tracks not just cumulative residual error but also the squared size of the active tests – this is what turns an ordinary online guarantee into the offset form that \([1](https://arxiv.org/html/2607.28856#S1.E1)\) needs\. For the nonsmooth losses above, we run this same argument once more over a geometric grid of learning rates, so that whichever scale turns out to suit a given test’s realized mass, some rate on the grid is already close to it, without the algorithm needing to know that scale in advance \([Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)\)\. Finally, the offline learner simply runs this online algorithm on an i\.i\.d\. sample, records the sequence of predictors it produces, and returns one of them at random; a Freedman–Bernstein concentration argument transfers the realized online bias and mass bounds to their distributional counterparts \([Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)\), and infinite test classes are handled along the way by replacing them with a finite cover and paying the corresponding approximation error \([Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px3)\)\.

### 1\.3Relation to prior work

Calibration of probabilistic forecasts dates back toDawid \([1982](https://arxiv.org/html/2607.28856#bib.bib7)\), with online calibration developed byFoster and Vohra \([1998](https://arxiv.org/html/2607.28856#bib.bib10)\)\. Multicalibration asks for small residuals on every set in a rich class\(Hébert\-Johnson et al\.,[2018](https://arxiv.org/html/2607.28856#bib.bib16)\), multiaccuracy for the corresponding unconditional guarantee\(Kim et al\.,[2019](https://arxiv.org/html/2607.28856#bib.bib22)\), and omniprediction uses such residual information to support many downstream objectives with one predictor\(Gopalan et al\.,[2022](https://arxiv.org/html/2607.28856#bib.bib14)\)\.Collina et al\. \([2026](https://arxiv.org/html/2607.28856#bib.bib5)\)pin down the minimax sample complexity of batch multicalibration via an online\-to\-batch reduction, the same strategy our offline conversion \([Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3)\) uses to turn an online second\-order guarantee into a fast batch rate;Gibbs and Tibshirani \([2026](https://arxiv.org/html/2607.28856#bib.bib12)\)show that omniprediction over a family of proper losses is strictly easier than boosting\-based multicalibration by exploiting proper\-loss structure directly, in the same spirit as our use of the drift term below\. Ordinary multicalibration controls residual correlation by a common tolerance or by bucket size, and summing such bounds over swap buckets is what makes swap guarantees expensive; second\-order multicalibration instead controls residual correlation relative to a swap’s own squared activity, the same activity that produces the favorable drift we exploit throughout this paper\.

Three benchmarks are in play, ordered by how much the comparator may depend on the prediction: agnostic learning fixes one hypothesis; our swap\-agnostic benchmark fixes the loss but lets the comparator hypothesis vary with the prediction; and swap omniprediction lets both the loss and the comparator vary\.Gopalan et al\. \([2023](https://arxiv.org/html/2607.28856#bib.bib15)\)characterize swap omniprediction through swap multicalibration, with algorithmic and quantitative improvements inGarg et al\. \([2024](https://arxiv.org/html/2607.28856#bib.bib11)\); Luo et al\. \([2025](https://arxiv.org/html/2607.28856#bib.bib26)\)\. Our improvement comes from fixing the loss – which supplies one coherent drift term across all buckets – rather than from improving rates for swap omniprediction, so our results do not contradict lower bounds there\.Hu et al\. \([2026](https://arxiv.org/html/2607.28856#bib.bib19)\)obtain near\-optimalO~​\(T\)\\widetilde\{O\}\(\\sqrt\{T\}\)swap regret against an arbitrary Lipschitz convex loss revealed online, andLuo et al\. \([2025b](https://arxiv.org/html/2607.28856#bib.bib27)\)obtain a closely relatedO~​\(T1/3\)\\widetilde\{O\}\(T^\{1/3\}\)rate for any twice\-differentiable proper loss via a new KL\-calibration measure that generalizes a rate previously known only for the squared loss\(Fishelson et al\.,[2025](https://arxiv.org/html/2607.28856#bib.bib9)\)\. Both measure regret against an arbitrary postprocessing of the prediction rather than a hypothesis class, so their bounds carry nolog⁡\|ℋ\|\\log\|\\mathcal\{H\}\|term; our matchingT1/3T^\{1/3\}exponent instead carries an explicit\(log⁡\|ℋ\|\)2/3\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}factor for the hypothesis\-valued comparator, obtained through second\-order multicalibration rather than calibration error\.

Blackwell approachability steers vector\-valued averages toward a convex target set\(Blackwell,[1956](https://arxiv.org/html/2607.28856#bib.bib1)\), typically implemented with multiplicative weights\(Cesa\-Bianchi and Lugosi,[2006](https://arxiv.org/html/2607.28856#bib.bib4)\)\.Okoroafor et al\. \([2024](https://arxiv.org/html/2607.28856#bib.bib28)\)use approachability to recalibrate an online predictor with an adjustable calibration\-regret tradeoff, recent omniprediction algorithms use a halfspace\-oracle view of it to control many residual correlations at once\(Okoroafor et al\.,[2025](https://arxiv.org/html/2607.28856#bib.bib29)\), andHu et al\. \([2026a](https://arxiv.org/html/2607.28856#bib.bib20)\)develop a simultaneous approachability framework for multiclass omniprediction\. We retain this architecture but adjust the potential to yield a realized Bernstein\-type inequality for every selector test – the source of the second\-order term our offline reduction needs\. Proper losses are governed by the geometry of their Bayes risks\(Gneiting and Raftery,[2007](https://arxiv.org/html/2607.28856#bib.bib13); Reid and Williamson,[2010](https://arxiv.org/html/2607.28856#bib.bib30)\), which we exploit through the quadratic\-growth inequality and through positive decompositions of broad loss families\. U\-calibration studies regret against an unknown downstream agent using the same V\-shaped basis for bounded proper losses\(Kleinberg et al\.,[2023](https://arxiv.org/html/2607.28856#bib.bib23); Luo et al\.,[2024](https://arxiv.org/html/2607.28856#bib.bib25); Li et al\.,[2022](https://arxiv.org/html/2607.28856#bib.bib24)\), andHu and Wu \([2024](https://arxiv.org/html/2607.28856#bib.bib18)\)study predictions minimizing swap regret for all payoff\-bounded downstream tasks; our simultaneous bounded\-proper\-loss result is a hypothesis\-class analogue, replacing their arbitrary downstream action with a hypothesis\-valued rule chosen after the prediction, which their techniques do not reach directly since the comparison must control the whole hypothesis\-swap selector rather than only the downstream task induced by the scalar prediction\.

## 2Preliminaries

This section fixes notation for the offline and online swap\-agnostic benchmarks and records the one algebraic fact about proper losses that drives every result later in the paper\.

### 2\.1Swap Agnostic Learning

Fix an instance space𝒳\\mathcal\{X\}and the prediction grid

ΓN=\{0,1N,…,1\}=\{γ0,…,γN\},γi=iN\.\\Gamma\_\{N\}=\\left\\\{0,\\frac\{1\}\{N\},\\ldots,1\\right\\\}=\\\{\\gamma\_\{0\},\\ldots,\\gamma\_\{N\}\\\},\\qquad\\gamma\_\{i\}=\\frac\{i\}\{N\}\.An offline predictor is allowed to be randomized\. Formally, a predictorp^\\hat\{p\}mapsxxto a distribution overΓN\\Gamma\_\{N\}; on a fresh example\(X,Y\)∼𝒟\(X,Y\)\\sim\\mathcal\{D\}, it drawsp∼p^​\(X\)p\\sim\\hat\{p\}\(X\)\. A hypothesis\-swap rule is a map

ϕ:ΓN→ℋ,\\phi:\\Gamma\_\{N\}\\to\\mathcal\{H\},and, for a grid pointγi\\gamma\_\{i\}, writehi=ϕ​\(γi\)h\_\{i\}=\\phi\(\\gamma\_\{i\}\)\. For a proper lossℓ\\ell, define the offline swap\-agnostic excess risk

SwapAgn𝒟⁡\(ℓ,ℋ\)=supϕ:ΓN→ℋ𝔼\(X,Y\)∼𝒟,p∼p^​\(X\)​\[ℓ​\(p,Y\)−ℓ​\(ϕ​\(p\)​\(X\),Y\)\]\.\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\sup\_\{\\phi:\\Gamma\_\{N\}\\to\\mathcal\{H\}\}\\mathbb\{E\}\_\{\(X,Y\)\\sim\\mathcal\{D\},\\,p\\sim\\hat\{p\}\(X\)\}\\left\[\\ell\(p,Y\)\-\\ell\(\\phi\(p\)\(X\),Y\)\\right\]\.\(2\)The predictorp^\\hat\{p\}is implicit inSwapAgn\\operatorname\{SwapAgn\}, just as the realized transcript is implicit inSwapReg\\operatorname\{SwapReg\}\.

### 2\.2Online Protocol and Swap Regret

Fix a horizonTTand binary outcomesyt∈\{0,1\}y\_\{t\}\\in\\\{0,1\\\}\. At roundtt:

1. \(i\)Nature revealsxt∈𝒳x\_\{t\}\\in\\mathcal\{X\}\.
2. \(ii\)The learner announces a distributionψt\\psi\_\{t\}overΓN\\Gamma\_\{N\}\.
3. \(iii\)The learner privately drawspt∼ψtp\_\{t\}\\sim\\psi\_\{t\}\.
4. \(iv\)Nature revealsyt∈\{0,1\}y\_\{t\}\\in\\\{0,1\\\}\.

We allow a nonanticipating adaptive environment: conditional on the past and on the announced distributionψt\\psi\_\{t\}, the outcome may be chosen adversarially, but it cannot depend on the learner’s fresh private drawptp\_\{t\}\.

Fori∈\{0,…,N\}i\\in\\\{0,\\ldots,N\\\}, define the prediction bucket

Ii=\{t∈\[T\]:pt=γi\}\.I\_\{i\}=\\\{t\\in\[T\]:p\_\{t\}=\\gamma\_\{i\}\\\}\.Letℋ⊆\{h:𝒳→\[0,1\]\}\\mathcal\{H\}\\subseteq\\\{h:\\mathcal\{X\}\\to\[0,1\]\\\}be a hypothesis class\. Unless explicitly stated otherwise, online results assume thatℋ\\mathcal\{H\}and all online test classes are finite\. For a proper lossℓ\\ell, define

SwapRegT⁡\(ℓ,ϕ\)=∑t=1T\[ℓ​\(pt,yt\)−ℓ​\(ϕ​\(pt\)​\(xt\),yt\)\],SwapRegT⁡\(ℓ,ℋ\)=supϕ:ΓN→ℋSwapRegT⁡\(ℓ,ϕ\)\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\phi\)=\\sum\_\{t=1\}^\{T\}\\left\[\\ell\(p\_\{t\},y\_\{t\}\)\-\\ell\(\\phi\(p\_\{t\}\)\(x\_\{t\}\),y\_\{t\}\)\\right\],\\qquad\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\sup\_\{\\phi:\\Gamma\_\{N\}\\to\\mathcal\{H\}\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\phi\)\.\(3\)

### 2\.3Conditional risks and proper losses

For any binary lossℓ:\[0,1\]×\{0,1\}→ℝ\\ell:\[0,1\]\\times\\\{0,1\\\}\\to\\mathbb\{R\}, define the conditional risk and outcome slope

Lp​\(q\)=\(1−p\)​ℓ​\(q,0\)\+p​ℓ​\(q,1\),Δℓ​\(q\)=ℓ​\(q,1\)−ℓ​\(q,0\)\.L\_\{p\}\(q\)=\(1\-p\)\\ell\(q,0\)\+p\\ell\(q,1\),\\qquad\\Delta\_\{\\ell\}\(q\)=\\ell\(q,1\)\-\\ell\(q,0\)\.\(4\)The loss is*proper*ifp∈arg​minq⁡Lp​\(q\)p\\in\\operatorname\*\{arg\\,min\}\_\{q\}L\_\{p\}\(q\)for everypp\. Its Bayes risk isLp​\(p\)L\_\{p\}\(p\), and its negative Bayes risk is

Fℓ​\(p\)=−Lp​\(p\)\.F\_\{\\ell\}\(p\)=\-L\_\{p\}\(p\)\.\(5\)Properness implies that the Bayes riskp↦Lp​\(p\)p\\mapsto L\_\{p\}\(p\)is concave andFℓF\_\{\\ell\}is convex\.

The next lemma is the single algebraic identity behind every reduction in this paper: comparing a truthful predictionppto any alternative predictionqqsplits the loss difference into a bias term, proportional to the calibration residualy−py\-p, and a nonnegative drift term that always favors the truthful prediction\.

###### Lemma 2\.1\(Proper\-loss identity\)\.

For every proper lossℓ\\ell, everyp,q∈\[0,1\]p,q\\in\[0,1\], and everyy∈\{0,1\}y\\in\\\{0,1\\\},

ℓ​\(p,y\)−ℓ​\(q,y\)=\(y−p\)​\(Δℓ​\(p\)−Δℓ​\(q\)\)−\[Lp​\(q\)−Lp​\(p\)\],\\ell\(p,y\)\-\\ell\(q,y\)=\(y\-p\)\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)\-\[L\_\{p\}\(q\)\-L\_\{p\}\(p\)\],\(6\)andLp​\(q\)−Lp​\(p\)≥0L\_\{p\}\(q\)\-L\_\{p\}\(p\)\\geq 0\. Moreover,

−Δℓ​\(q\)∈∂Fℓ​\(q\),\-\\Delta\_\{\\ell\}\(q\)\\in\\partial F\_\{\\ell\}\(q\),so ifFℓF\_\{\\ell\}is differentiable thenFℓ′=−ΔℓF\_\{\\ell\}^\{\\prime\}=\-\\Delta\_\{\\ell\}andLp​\(q\)−Lp​\(p\)=DFℓ​\(p,q\)L\_\{p\}\(q\)\-L\_\{p\}\(p\)=D\_\{F\_\{\\ell\}\}\(p,q\), the Bregman divergence ofFℓF\_\{\\ell\}\.

###### Proof of[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3)\.

Sincey∈\{0,1\}y\\in\\\{0,1\\\},

ℓ​\(q,y\)=ℓ​\(q,0\)\+y​Δℓ​\(q\)=Lq​\(q\)\+\(y−q\)​Δℓ​\(q\)\.\\ell\(q,y\)=\\ell\(q,0\)\+y\\Delta\_\{\\ell\}\(q\)=L\_\{q\}\(q\)\+\(y\-q\)\\Delta\_\{\\ell\}\(q\)\.Taking expectation underY∼Ber⁡\(p\)Y\\sim\\operatorname\{Ber\}\(p\)gives

Lp​\(q\)=Lq​\(q\)\+\(p−q\)​Δℓ​\(q\)\.L\_\{p\}\(q\)=L\_\{q\}\(q\)\+\(p\-q\)\\Delta\_\{\\ell\}\(q\)\.\(7\)Rearranging that formula and subtracting the canonical representations forppandqqproves \([6](https://arxiv.org/html/2607.28856#S2.E6)\)\. Properness implies

Lp​\(p\)≤Lq​\(q\)\+\(p−q\)​Δℓ​\(q\),L\_\{p\}\(p\)\\leq L\_\{q\}\(q\)\+\(p\-q\)\\Delta\_\{\\ell\}\(q\),which is equivalent to−Δℓ​\(q\)∈∂Fℓ​\(q\)\-\\Delta\_\{\\ell\}\(q\)\\in\\partial F\_\{\\ell\}\(q\), and combined with \([7](https://arxiv.org/html/2607.28856#S2.E7)\) givesLp​\(q\)−Lp​\(p\)≥0L\_\{p\}\(q\)\-L\_\{p\}\(p\)\\geq 0and the Bregman\-divergence identity when the subgradient is unique\. ∎

### 2\.4Finite covers

For a class𝒢\\mathcal\{G\}of bounded tests, a finite set𝒢~\\widetilde\{\\mathcal\{G\}\}is a uniformρ\\rho\-cover if everyg∈𝒢g\\in\\mathcal\{G\}has ag~∈𝒢~\\widetilde\{g\}\\in\\widetilde\{\\mathcal\{G\}\}satisfying

supx,p\|g​\(x,p\)−g~​\(x,p\)\|≤ρ\.\\sup\_\{x,p\}\|g\(x,p\)\-\\widetilde\{g\}\(x,p\)\|\\leq\\rho\.We write𝒩∞​\(ρ,𝒢\)\\mathcal\{N\}\_\{\\infty\}\(\\rho,\\mathcal\{G\}\)for the smallest cover size\. Online algorithms in this paper are only run on finite classes\. Infinite classes are addressed offline by selecting a finite cover before training\.

## 3Second\-Order Multicalibration

[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3)shows that swap\-agnostic learning for a proper loss reduces to controlling the residual correlation of tests induced by swap selectors\. The right control is not a uniform correlation tolerance; it compares the residual correlation of a test to its realized squared activity, which is exactly what lets the drift term in \([6](https://arxiv.org/html/2607.28856#S2.E6)\) absorb the quadratic part of the error\. This section develops that control on its own terms, entirely independently of any particular loss:[Section˜3](https://arxiv.org/html/2607.28856#S3)defines second\-order multicalibration online and distributionally,[Section˜3\.1](https://arxiv.org/html/2607.28856#S3.SS1)gives the approachability algorithm and its high\-probability online guarantee[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3),[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)records a square\-root form needed later for nonsmooth losses, and[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3)converts the online guarantee into the distributional guarantee[Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)used by the offline learners\. How a particular loss family turns this generic control into a swap\-regret bound is worked out loss family by loss family starting in[Section˜4](https://arxiv.org/html/2607.28856#S4)\.

For a transcript and a testg:𝒳×ΓN→\[−1,1\]g:\\mathcal\{X\}\\times\\Gamma\_\{N\}\\to\[\-1,1\], define

BiasT⁡\(g\)=∑t=1T\(yt−pt\)​g​\(xt,pt\),MassT⁡\(g\)=∑t=1Tg​\(xt,pt\)2\.\\operatorname\{Bias\}\_\{T\}\(g\)=\\sum\_\{t=1\}^\{T\}\(y\_\{t\}\-p\_\{t\}\)g\(x\_\{t\},p\_\{t\}\),\\qquad\\operatorname\{Mass\}\_\{T\}\(g\)=\\sum\_\{t=1\}^\{T\}g\(x\_\{t\},p\_\{t\}\)^\{2\}\.\(8\)For a randomized offline predictorp^\\hat\{p\}, define the distributional analogues

Bias𝒟⁡\(g;p^\)=𝔼\(X,Y\)∼𝒟,p∼p^​\(X\)​\[\(Y−p\)​g​\(X,p\)\],Mass𝒟⁡\(g;p^\)=𝔼\(X,Y\)∼𝒟,p∼p^​\(X\)​\[g​\(X,p\)2\]\.\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\hat\{p\}\)=\\mathbb\{E\}\_\{\(X,Y\)\\sim\\mathcal\{D\},\\,p\\sim\\hat\{p\}\(X\)\}\[\(Y\-p\)g\(X,p\)\],\\qquad\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\hat\{p\}\)=\\mathbb\{E\}\_\{\(X,Y\)\\sim\\mathcal\{D\},\\,p\\sim\\hat\{p\}\(X\)\}\[g\(X,p\)^\{2\}\]\.\(9\)
###### Definition 3\.1\(Second\-order multicalibration\)\.

Let𝒢⊆\{g:𝒳×ΓN→\[−1,1\]\}\\mathcal\{G\}\\subseteq\\\{g:\\mathcal\{X\}\\times\\Gamma\_\{N\}\\to\[\-1,1\]\\\}\. A transcript satisfies\(c,a\)\(c,a\)second\-order multicalibration with respect to𝒢\\mathcal\{G\}if

BiasT⁡\(g\)≤c​MassT⁡\(g\)\+a\\operatorname\{Bias\}\_\{T\}\(g\)\\leq c\\,\\operatorname\{Mass\}\_\{T\}\(g\)\+a\(10\)for everyg∈𝒢g\\in\\mathcal\{G\}\. A randomized online algorithm satisfies the guarantee with confidence1−δ1\-\\deltaif the simultaneous event \([10](https://arxiv.org/html/2607.28856#S3.E10)\) has probability at least1−δ1\-\\delta\. A randomized predictorp^\\hat\{p\}satisfies*distributional*\(c,a\)\(c,a\)second\-order multicalibration with respect to𝒢\\mathcal\{G\}if, for everyg∈𝒢g\\in\\mathcal\{G\},

Bias𝒟⁡\(g;p^\)≤c​Mass𝒟⁡\(g;p^\)\+a\.\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\hat\{p\}\)\\leq c\\,\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\hat\{p\}\)\+a\.\(11\)In either case, the two\-sided version is obtained by including bothggand−g\-gin the test class\.

LetΦN=ℋN\+1\\Phi\_\{N\}=\\mathcal\{H\}^\{N\+1\}denote the class of hypothesis\-swap selectors\. A test class induced by selectors always has the form\{gϕ:ϕ∈ΦN\}\\\{g\_\{\\phi\}:\\phi\\in\\Phi\_\{N\}\\\}for some fixedgϕ​\(x,γi\)=f​\(x,γi,hi\)g\_\{\\phi\}\(x,\\gamma\_\{i\}\)=f\(x,\\gamma\_\{i\},h\_\{i\}\)depending onϕ\\phionly throughhi=ϕ​\(γi\)h\_\{i\}=\\phi\(\\gamma\_\{i\}\); every selector class used in this paper is of this form\. We record once, generically, the computational fact that lets the approachability algorithm below run in time linear inℋ\\mathcal\{H\}rather than exponential in the grid size\.

###### Proposition 3\.2\(Product\-class factorization\)\.

Letgϕ​\(x,γi\)=f​\(x,γi,hi\)g\_\{\\phi\}\(x,\\gamma\_\{i\}\)=f\(x,\\gamma\_\{i\},h\_\{i\}\)forϕ∈ΦN\\phi\\in\\Phi\_\{N\}as above\. Running[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)on\{gϕ:ϕ∈ΦN\}\\\{g\_\{\\phi\}:\\phi\\in\\Phi\_\{N\}\\\}, the weights factorize as

Wt​\(ϕ\)=∏i=0NWt,i​\(hi\)\.W\_\{t\}\(\\phi\)=\\prod\_\{i=0\}^\{N\}W\_\{t,i\}\(h\_\{i\}\)\.Consequently, the algorithm can be implemented with\(N\+1\)​\|ℋ\|\(N\+1\)\|\\mathcal\{H\}\|scalar weights rather than\|ℋ\|N\+1\|\\mathcal\{H\}\|^\{N\+1\}weights\.

###### Proof of[Section˜3](https://arxiv.org/html/2607.28856#S3)\.

InitializeW1,i​\(h\)=\|ℋ\|−1W\_\{1,i\}\(h\)=\|\\mathcal\{H\}\|^\{\-1\}for every bucketiiand hypothesishh, so

W1​\(ϕ\)=\|ℋ\|−\(N\+1\)=∏i=0NW1,i​\(hi\)\.W\_\{1\}\(\\phi\)=\|\\mathcal\{H\}\|^\{\-\(N\+1\)\}=\\prod\_\{i=0\}^\{N\}W\_\{1,i\}\(h\_\{i\}\)\.SupposeWt​\(ϕ\)=∏iWt,i​\(hi\)W\_\{t\}\(\\phi\)=\\prod\_\{i\}W\_\{t,i\}\(h\_\{i\}\)\. Ifpt=γjp\_\{t\}=\\gamma\_\{j\}, thengϕ​\(xt,pt\)=f​\(xt,γj,hj\)g\_\{\\phi\}\(x\_\{t\},p\_\{t\}\)=f\(x\_\{t\},\\gamma\_\{j\},h\_\{j\}\)depends onϕ\\phionly through itsjjth coordinate\. Define

Wt\+1,j​\(h\)=Wt,j​\(h\)​exp⁡\(η​\(yt−γj\)​f​\(xt,γj,h\)−2​η2​f​\(xt,γj,h\)2\),W\_\{t\+1,j\}\(h\)=W\_\{t,j\}\(h\)\\exp\\\!\\left\(\\eta\(y\_\{t\}\-\\gamma\_\{j\}\)f\(x\_\{t\},\\gamma\_\{j\},h\)\-2\\eta^\{2\}f\(x\_\{t\},\\gamma\_\{j\},h\)^\{2\}\\right\),and setWt\+1,i=Wt,iW\_\{t\+1,i\}=W\_\{t,i\}fori≠ji\\neq j\. ThenWt\+1​\(ϕ\)=∏iWt\+1,i​\(hi\)W\_\{t\+1\}\(\\phi\)=\\prod\_\{i\}W\_\{t\+1,i\}\(h\_\{i\}\)\.

The normalizing constant also factorizes:

∑ϕ∈ΦNWt​\(ϕ\)=∏i=0N∑h∈ℋWt,i​\(h\)\.\\sum\_\{\\phi\\in\\Phi\_\{N\}\}W\_\{t\}\(\\phi\)=\\prod\_\{i=0\}^\{N\}\\sum\_\{h\\in\\mathcal\{H\}\}W\_\{t,i\}\(h\)\.Thus the normalized distribution over selectors has independent marginals over buckets\. In particular, when evaluating a candidate predictionp=γip=\\gamma\_\{i\}, the weighted averagesFt​\(γi\)F\_\{t\}\(\\gamma\_\{i\}\)andAt​\(γi\)A\_\{t\}\(\\gamma\_\{i\}\)below only require the marginal distribution on theiith hypothesis coordinate\. ∎

### 3\.1Algorithm

At a high level, the algorithm is a halfspace\-oracle implementation of Blackwell approachability, implemented with multiplicative weights over the test class\.

Fix a horizonTT, grid sizeNN, finite test class𝒢⊆\{g:𝒳×ΓN→\[−1,1\]\}\\mathcal\{G\}\\subseteq\\\{g:\\mathcal\{X\}\\times\\Gamma\_\{N\}\\to\[\-1,1\]\\\}, and learning rateη∈\(0,1/4\]\\eta\\in\(0,1/4\]\. The learner maintains one weight per test\. After observingxtx\_\{t\}, it normalizes the weights and computes, for each grid point,

Ft​\(γi\)\\displaystyle F\_\{t\}\(\\gamma\_\{i\}\)=∑g∈𝒢wt​\(g\)​g​\(xt,γi\),\\displaystyle=\\sum\_\{g\\in\\mathcal\{G\}\}w\_\{t\}\(g\)g\(x\_\{t\},\\gamma\_\{i\}\),\(12\)At​\(γi\)\\displaystyle A\_\{t\}\(\\gamma\_\{i\}\)=∑g∈𝒢wt​\(g\)​g​\(xt,γi\)2\.\\displaystyle=\\sum\_\{g\\in\\mathcal\{G\}\}w\_\{t\}\(g\)g\(x\_\{t\},\\gamma\_\{i\}\)^\{2\}\.\(13\)The scalar functionFtF\_\{t\}is the current halfspace direction used to choose the next prediction\. The finite\-grid halfspace oracle chooses a randomized predictionψt\\psi\_\{t\}as follows\. IfFt​\(0\)≤0F\_\{t\}\(0\)\\leq 0, setψt=δ0\\psi\_\{t\}=\\delta\_\{0\}\. IfFt​\(1\)≥0F\_\{t\}\(1\)\\geq 0, setψt=δ1\\psi\_\{t\}=\\delta\_\{1\}\. Otherwise choose adjacent grid pointsa<b=a\+1/Na<b=a\+1/NwithFt​\(a\)≥0≥Ft​\(b\)F\_\{t\}\(a\)\\geq 0\\geq F\_\{t\}\(b\)\. If one endpoint has value zero, put all mass on that endpoint\. If both inequalities are strict, set

λt=Ft​\(a\)Ft​\(a\)−Ft​\(b\)\\lambda\_\{t\}=\\frac\{F\_\{t\}\(a\)\}\{F\_\{t\}\(a\)\-F\_\{t\}\(b\)\}and put mass1−λt1\-\\lambda\_\{t\}onaaand massλt\\lambda\_\{t\}onbb\. Then

𝔼p∼ψt​Ft​\(p\)=0\.\\mathbb\{E\}\_\{p\\sim\\psi\_\{t\}\}F\_\{t\}\(p\)=0\.This is the discrete analogue of choosing a point in\[0,1\]\[0,1\]where the weighted residual direction crosses zero\.

Algorithm 1Second\-order multicalibration by approachability1:Horizon

TT, grid size

NN, finite test class

𝒢\\mathcal\{G\}, rate

η∈\(0,1/4\]\\eta\\in\(0,1/4\]
2:Initialize

W1​\(g\)=1/\|𝒢\|W\_\{1\}\(g\)=1/\|\\mathcal\{G\}\|for all

g∈𝒢g\\in\\mathcal\{G\}
3:for

t=1,…,Tt=1,\\ldots,Tdo

4:Observe

xtx\_\{t\}and normalize

wt∝Wtw\_\{t\}\\propto W\_\{t\}
5:Compute

FtF\_\{t\}and

AtA\_\{t\}from \([12](https://arxiv.org/html/2607.28856#S3.E12)\)–\([13](https://arxiv.org/html/2607.28856#S3.E13)\)

6:if

Ft​\(0\)≤0F\_\{t\}\(0\)\\leq 0then

7:

ψt←δ0\\psi\_\{t\}\\leftarrow\\delta\_\{0\}
8:elseif

Ft​\(1\)≥0F\_\{t\}\(1\)\\geq 0then

9:

ψt←δ1\\psi\_\{t\}\\leftarrow\\delta\_\{1\}
10:else

11:Choose adjacent

a<b=a\+1/Na<b=a\+1/Nwith

Ft​\(a\)≥0≥Ft​\(b\)F\_\{t\}\(a\)\\geq 0\\geq F\_\{t\}\(b\)
12:if

Ft​\(a\)=0F\_\{t\}\(a\)=0or

Ft​\(b\)=0F\_\{t\}\(b\)=0then

13:

ψt←\\psi\_\{t\}\\leftarrowpoint mass on a zero endpoint

14:else

15:

λt←Ft​\(a\)/\(Ft​\(a\)−Ft​\(b\)\)\\lambda\_\{t\}\\leftarrow F\_\{t\}\(a\)/\(F\_\{t\}\(a\)\-F\_\{t\}\(b\)\)
16:

ψt←\(1−λt\)​δa\+λt​δb\\psi\_\{t\}\\leftarrow\(1\-\\lambda\_\{t\}\)\\delta\_\{a\}\+\\lambda\_\{t\}\\delta\_\{b\}
17:Draw

pt∼ψtp\_\{t\}\\sim\\psi\_\{t\}and observe

yty\_\{t\}
18:Update

Wt\+1​\(g\)←Wt​\(g\)​exp⁡\(η​\(yt−pt\)​g​\(xt,pt\)−2​η2​g​\(xt,pt\)2\)W\_\{t\+1\}\(g\)\\leftarrow W\_\{t\}\(g\)\\exp\\\!\\left\(\\eta\(y\_\{t\}\-p\_\{t\}\)g\(x\_\{t\},p\_\{t\}\)\-2\\eta^\{2\}g\(x\_\{t\},p\_\{t\}\)^\{2\}\\right\)

The following theorem is the main guarantee of this subsection\. Its proof has two ingredients\. First, the randomized adjacent\-grid step controls the linear bias direction up to one global grid\-rounding error\. Second, a Bernstein\-corrected exponential potential turns this one\-step control into a high\-probability offset guarantee for every test\.

###### Theorem 3\.3\(High\-probability second\-order multicalibration\)\.

Run[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)forTTrounds on𝒢\\mathcal\{G\}with rateη\\eta\. Then, with probability at least1−δ1\-\\delta, simultaneously for everyg∈𝒢g\\in\\mathcal\{G\},

BiasT\(g\)≤2ηMassT\(g\)\+log⁡\(\|𝒢\|/δ\)\+2​T/N2η\.\\boxed\{\\operatorname\{Bias\}\_\{T\}\(g\)\\leq 2\\eta\\operatorname\{Mass\}\_\{T\}\(g\)\+\\frac\{\\log\(\|\\mathcal\{G\}\|/\\delta\)\+2T/N^\{2\}\}\{\\eta\}\.\}\(14\)

#### The grid halfspace oracle\.

Letρ=1/N\\rho=1/N\. Given a distributionwwover𝒢\\mathcal\{G\}and a contextxx, define

F​\(γi\)=∑g∈𝒢w​\(g\)​g​\(x,γi\),A​\(γi\)=∑g∈𝒢w​\(g\)​g​\(x,γi\)2\.F\(\\gamma\_\{i\}\)=\\sum\_\{g\\in\\mathcal\{G\}\}w\(g\)g\(x,\\gamma\_\{i\}\),\\qquad A\(\\gamma\_\{i\}\)=\\sum\_\{g\\in\\mathcal\{G\}\}w\(g\)g\(x,\\gamma\_\{i\}\)^\{2\}\.
###### Lemma 3\.4\(Algorithmic grid oracle with quadratic slack\)\.

Letψ\\psibe the distribution constructed by the grid\-oracle step of[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)from the values ofFFonΓN\\Gamma\_\{N\}\. Then, for everyy∈\[0,1\]y\\in\[0,1\],

𝔼p∼ψ​\[\(y−p\)​F​\(p\)\]≤ρ​𝔼p∼ψ​A​\(p\)\.\\mathbb\{E\}\_\{p\\sim\\psi\}\[\(y\-p\)F\(p\)\]\\leq\\rho\\sqrt\{\\mathbb\{E\}\_\{p\\sim\\psi\}A\(p\)\}\.\(15\)

###### Proof of[Section˜3\.1](https://arxiv.org/html/2607.28856#S3.SS1.SSS0.Px1)\.

IfF​\(0\)≤0F\(0\)\\leq 0, the algorithm setsψ=δ0\\psi=\\delta\_\{0\}\. Then𝔼​\[\(y−p\)​F​\(p\)\]=y​F​\(0\)≤0\\mathbb\{E\}\[\(y\-p\)F\(p\)\]=yF\(0\)\\leq 0, while the right\-hand side of \([15](https://arxiv.org/html/2607.28856#S3.E15)\) is nonnegative\. IfF​\(1\)≥0F\(1\)\\geq 0, the algorithm setsψ=δ1\\psi=\\delta\_\{1\}, and\(y−1\)​F​\(1\)≤0\(y\-1\)F\(1\)\\leq 0\.

It remains to handle the crossing case\. The algorithm chooses adjacent grid pointsa<b=a\+ρa<b=a\+\\rhowithF​\(a\)≥0≥F​\(b\)F\(a\)\\geq 0\\geq F\(b\)\. IfF​\(a\)=0F\(a\)=0orF​\(b\)=0F\(b\)=0, it puts all mass on a zero endpoint\. Otherwise it sets

λ=F​\(a\)F​\(a\)−F​\(b\)∈\(0,1\),\\lambda=\\frac\{F\(a\)\}\{F\(a\)\-F\(b\)\}\\in\(0,1\),so that

\(1−λ\)​F​\(a\)\+λ​F​\(b\)=0,\(1\-\\lambda\)F\(a\)\+\\lambda F\(b\)=0,and letψ=\(1−λ\)​δa\+λ​δb\\psi=\(1\-\\lambda\)\\delta\_\{a\}\+\\lambda\\delta\_\{b\}\. Writing\(1−λ\)​F​\(a\)=−λ​F​\(b\)\(1\-\\lambda\)F\(a\)=\-\\lambda F\(b\), we get

𝔼​\[\(y−p\)​F​\(p\)\]\\displaystyle\\mathbb\{E\}\[\(y\-p\)F\(p\)\]=\(1−λ\)​F​\(a\)​\(y−a\)\+λ​F​\(b\)​\(y−b\)\\displaystyle=\(1\-\\lambda\)F\(a\)\(y\-a\)\+\\lambda F\(b\)\(y\-b\)=\(b−a\)​\(1−λ\)​F​\(a\)=ρ​\(1−λ\)​F​\(a\)\\displaystyle=\(b\-a\)\(1\-\\lambda\)F\(a\)=\\rho\(1\-\\lambda\)F\(a\)≤ρ​\(1−λ\)​A​\(a\)≤ρ​𝔼​A​\(p\)\.\\displaystyle\\leq\\rho\\sqrt\{\(1\-\\lambda\)A\(a\)\}\\leq\\rho\\sqrt\{\\mathbb\{E\}A\(p\)\}\.∎

#### The exponential potential\.

###### Lemma 3\.5\(Offset exponential inequality\)\.

Forη∈\(0,1/4\]\\eta\\in\(0,1/4\],g∈\[−1,1\]g\\in\[\-1,1\], andz∈\[−\|g\|,\|g\|\]z\\in\[\-\|g\|,\|g\|\],

exp⁡\(η​z−2​η2​g2\)≤1\+η​z−η24​g2\.\\exp\(\\eta z\-2\\eta^\{2\}g^\{2\}\)\\leq 1\+\\eta z\-\\frac\{\\eta^\{2\}\}\{4\}g^\{2\}\.\(16\)

###### Proof of[Section˜3\.1](https://arxiv.org/html/2607.28856#S3.SS1.SSS0.Px2)\.

Setu=η​zu=\\eta zandv=η2​g2v=\\eta^\{2\}g^\{2\}\. Then\|u\|≤1/4\|u\|\\leq 1/4,u2≤vu^\{2\}\\leq v, andv≤1/16v\\leq 1/16\. The standard Bernstein exponential inequalityeu−u2≤1\+ue^\{u\-u^\{2\}\}\\leq 1\+uforu≥−1/2u\\geq\-1/2holds, for example, as inCesa\-Bianchi and Lugosi \([2006](https://arxiv.org/html/2607.28856#bib.bib4), Chapter 2\)\. Sincer=2​v−u2r=2v\-u^\{2\}lies in\[0,1/8\]\[0,1/8\], we also havee−r≤1−r/2e^\{\-r\}\\leq 1\-r/2\. Therefore

eu−2​v=eu−u2​e−\(2​v−u2\)≤\(1\+u\)​\(1−2​v−u22\)\.e^\{u\-2v\}=e^\{u\-u^\{2\}\}e^\{\-\(2v\-u^\{2\}\)\}\\leq\(1\+u\)\\left\(1\-\\frac\{2v\-u^\{2\}\}\{2\}\\right\)\.Becauseu2≤vu^\{2\}\\leq v, the last display is at most

\(1\+u\)​\(1−v2\)=1\+u−v2−u​v2≤1\+u−v4,\(1\+u\)\\left\(1\-\\frac\{v\}\{2\}\\right\)=1\+u\-\\frac\{v\}\{2\}\-\\frac\{uv\}\{2\}\\leq 1\+u\-\\frac\{v\}\{4\},where the final inequality usesu≥−1/2u\\geq\-1/2\. Substituting backu=η​zu=\\eta zandv=η2​g2v=\\eta^\{2\}g^\{2\}proves \([16](https://arxiv.org/html/2607.28856#S3.E16)\)\. ∎

#### Completing the proof\.

###### Proof of[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3)\.

LetZt=∑g∈𝒢Wt​\(g\)Z\_\{t\}=\\sum\_\{g\\in\\mathcal\{G\}\}W\_\{t\}\(g\)\. Conditional on the past,xtx\_\{t\}, the announced distribution, and the nonanticipating value ofyty\_\{t\}, but not the fresh drawptp\_\{t\},[Section˜3\.1](https://arxiv.org/html/2607.28856#S3.SS1.SSS0.Px2)gives

𝔼t​Zt\+1Zt≤1\+η​𝔼t​\[\(yt−pt\)​Ft​\(pt\)\]−η24​𝔼t​At​\(pt\)\.\\mathbb\{E\}\_\{t\}\\frac\{Z\_\{t\+1\}\}\{Z\_\{t\}\}\\leq 1\+\\eta\\mathbb\{E\}\_\{t\}\[\(y\_\{t\}\-p\_\{t\}\)F\_\{t\}\(p\_\{t\}\)\]\-\\frac\{\\eta^\{2\}\}\{4\}\\mathbb\{E\}\_\{t\}A\_\{t\}\(p\_\{t\}\)\.By[Section˜3\.1](https://arxiv.org/html/2607.28856#S3.SS1.SSS0.Px1),

η​𝔼t​\[\(yt−pt\)​Ft​\(pt\)\]≤η​ρ​𝔼t​At​\(pt\)≤η28​𝔼t​At​\(pt\)\+2​ρ2\.\\eta\\mathbb\{E\}\_\{t\}\[\(y\_\{t\}\-p\_\{t\}\)F\_\{t\}\(p\_\{t\}\)\]\\leq\\eta\\rho\\sqrt\{\\mathbb\{E\}\_\{t\}A\_\{t\}\(p\_\{t\}\)\}\\leq\\frac\{\\eta^\{2\}\}\{8\}\\mathbb\{E\}\_\{t\}A\_\{t\}\(p\_\{t\}\)\+2\\rho^\{2\}\.Thus𝔼t​\[Zt\+1/Zt\]≤e2​ρ2\\mathbb\{E\}\_\{t\}\[Z\_\{t\+1\}/Z\_\{t\}\]\\leq e^\{2\\rho^\{2\}\}, ande−2​ρ2​\(t−1\)​Zte^\{\-2\\rho^\{2\}\(t\-1\)\}Z\_\{t\}is a nonnegative supermartingale\. Markov’s inequality givesZT\+1≤δ−1​e2​T/N2Z\_\{T\+1\}\\leq\\delta^\{\-1\}e^\{2T/N^\{2\}\}with probability at least1−δ1\-\\delta\. For eachgg,

1\|𝒢\|​exp⁡\(η​BiasT⁡\(g\)−2​η2​MassT⁡\(g\)\)≤ZT\+1\.\\frac\{1\}\{\|\\mathcal\{G\}\|\}\\exp\\\!\\left\(\\eta\\operatorname\{Bias\}\_\{T\}\(g\)\-2\\eta^\{2\}\\operatorname\{Mass\}\_\{T\}\(g\)\\right\)\\leq Z\_\{T\+1\}\.Taking logarithms and dividing byη\\etaproves \([14](https://arxiv.org/html/2607.28856#S3.E14)\)\. ∎

### 3\.2Square\-root form by scaling the test class

Nonsmooth losses will need a version of[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3)with no linear term inMassT⁡\(g\)\\operatorname\{Mass\}\_\{T\}\(g\)at all, only a square root of it\. No separate algorithm is needed for this: it is enough to run[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)at one fixed rate on a test class that already contains every rescaling of𝒢\\mathcal\{G\}, and then optimize the scale after the fact\. Let

𝒜T=\{2−j:j=0,1,…,⌈log2⁡T⌉\}\\mathcal\{A\}\_\{T\}=\\\{2^\{\-j\}:j=0,1,\\ldots,\\lceil\\log\_\{2\}T\\rceil\\\}be a dyadic grid of scales between11and about1/T1/T, and let

𝒢sc=\{s​α​g:s∈\{−1,1\},g∈𝒢,α∈𝒜T\}⊆\{g:𝒳×ΓN→\[−1,1\]\}\.\\mathcal\{G\}^\{\\mathrm\{sc\}\}=\\\{s\\alpha g:s\\in\\\{\-1,1\\\},\\ g\\in\\mathcal\{G\},\\ \\alpha\\in\\mathcal\{A\}\_\{T\}\\\}\\subseteq\\\{g:\\mathcal\{X\}\\times\\Gamma\_\{N\}\\to\[\-1,1\]\\\}\.SinceBiasT⁡\(α​g\)=α​BiasT⁡\(g\)\\operatorname\{Bias\}\_\{T\}\(\\alpha g\)=\\alpha\\operatorname\{Bias\}\_\{T\}\(g\)andMassT⁡\(α​g\)=α2​MassT⁡\(g\)\\operatorname\{Mass\}\_\{T\}\(\\alpha g\)=\\alpha^\{2\}\\operatorname\{Mass\}\_\{T\}\(g\), running[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)on𝒢sc\\mathcal\{G\}^\{\\mathrm\{sc\}\}with rateη=1/4\\eta=1/4and applying[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3)gives, with probability at least1−δ1\-\\delta, simultaneously for everys,g,αs,g,\\alpha,

α​s​BiasT⁡\(g\)−α22​MassT⁡\(g\)≤4​ΛT,ΛT=1\+log⁡\(2​\|𝒢\|​\|𝒜T\|δ\)\+2​TN2\.\\alpha s\\operatorname\{Bias\}\_\{T\}\(g\)\-\\frac\{\\alpha^\{2\}\}\{2\}\\operatorname\{Mass\}\_\{T\}\(g\)\\leq 4\\Lambda\_\{T\},\\qquad\\Lambda\_\{T\}=1\+\\log\\\!\\left\(\\frac\{2\|\\mathcal\{G\}\|\|\\mathcal\{A\}\_\{T\}\|\}\{\\delta\}\\right\)\+\\frac\{2T\}\{N^\{2\}\}\.\(17\)Choosingssto match the sign ofBiasT⁡\(g\)\\operatorname\{Bias\}\_\{T\}\(g\)turns this into, for everyα∈𝒜T\\alpha\\in\\mathcal\{A\}\_\{T\},

\|BiasT⁡\(g\)\|≤α2​MassT⁡\(g\)\+4​ΛTα\.\|\\operatorname\{Bias\}\_\{T\}\(g\)\|\\leq\\frac\{\\alpha\}\{2\}\\operatorname\{Mass\}\_\{T\}\(g\)\+\\frac\{4\\Lambda\_\{T\}\}\{\\alpha\}\.\(18\)
###### Corollary 3\.6\(Square\-root second\-order control\)\.

There is a universal constantCCsuch that, with probability at least1−δ1\-\\delta, simultaneously for everyg∈𝒢g\\in\\mathcal\{G\},

\|BiasT⁡\(g\)\|≤C​ΛT​MassT⁡\(g\)\+C​ΛT\.\|\\operatorname\{Bias\}\_\{T\}\(g\)\|\\leq C\\sqrt\{\\Lambda\_\{T\}\\operatorname\{Mass\}\_\{T\}\(g\)\}\+C\\Lambda\_\{T\}\.\(19\)

###### Proof of[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)\.

Work on the event where \([18](https://arxiv.org/html/2607.28856#S3.E18)\) holds for everyα∈𝒜T\\alpha\\in\\mathcal\{A\}\_\{T\}, which has probability at least1−δ1\-\\delta\. Fixggand writeM=MassT⁡\(g\)≤TM=\\operatorname\{Mass\}\_\{T\}\(g\)\\leq T\. IfM≤8​ΛTM\\leq 8\\Lambda\_\{T\}, takeα=1∈𝒜T\\alpha=1\\in\\mathcal\{A\}\_\{T\}in \([18](https://arxiv.org/html/2607.28856#S3.E18)\) to get\|BiasT⁡\(g\)\|≤4​ΛT\+4​ΛT=8​ΛT\|\\operatorname\{Bias\}\_\{T\}\(g\)\|\\leq 4\\Lambda\_\{T\}\+4\\Lambda\_\{T\}=8\\Lambda\_\{T\}\. Otherwise, the continuous minimizer of\(α/2\)​M\+4​ΛT/α\(\\alpha/2\)M\+4\\Lambda\_\{T\}/\\alphaoverα\>0\\alpha\>0isα∗=8​ΛT/M<1\\alpha\_\{\*\}=\\sqrt\{8\\Lambda\_\{T\}/M\}<1, with minimal value2​2​ΛT​M2\\sqrt\{2\\Lambda\_\{T\}M\}\. SinceM≤TM\\leq TandΛT≥1\\Lambda\_\{T\}\\geq 1,

α∗2=8​ΛTM≥8​ΛTT≥8T≥1T2,\\alpha\_\{\*\}^\{2\}=\\frac\{8\\Lambda\_\{T\}\}\{M\}\\geq\\frac\{8\\Lambda\_\{T\}\}\{T\}\\geq\\frac\{8\}\{T\}\\geq\\frac\{1\}\{T^\{2\}\},soα∗≥1/T\\alpha\_\{\*\}\\geq 1/T, which is at least the smallest scale2−⌈log2⁡T⌉2^\{\-\\lceil\\log\_\{2\}T\\rceil\}in𝒜T\\mathcal\{A\}\_\{T\}\. Hence someα∈𝒜T\\alpha\\in\\mathcal\{A\}\_\{T\}lies within a factor of22ofα∗\\alpha\_\{\*\}; substituting such anα\\alphainto \([18](https://arxiv.org/html/2607.28856#S3.E18)\) changes each term by at most a factor of22, giving\|BiasT⁡\(g\)\|≤4​2​ΛT​M\|\\operatorname\{Bias\}\_\{T\}\(g\)\|\\leq 4\\sqrt\{2\\Lambda\_\{T\}M\}\. Both cases are covered by \([19](https://arxiv.org/html/2607.28856#S3.E19)\) for a suitable universal constantCC\. ∎

### 3\.3Offline conversion

We now convert online second\-order multicalibration into an offline guarantee\. The conversion returns a randomized predictor, which is standard for online\-to\-batch reductions\. Unlike a naive holdout argument, it preserves the sequential prediction rules whose realized residuals were controlled online\.

###### Theorem 3\.7\(High\-probability offline second\-order multicalibration\)\.

Let𝒢⊆\{g:𝒳×ΓN→\[−1,1\]\}\\mathcal\{G\}\\subseteq\\\{g:\\mathcal\{X\}\\times\\Gamma\_\{N\}\\to\[\-1,1\]\\\}be finite, letZ1,…,ZmZ\_\{1\},\\ldots,Z\_\{m\}be i\.i\.d\. examples from𝒟\\mathcal\{D\}, and run[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)sequentially on this sample with rateη∈\(0,1/4\]\\eta\\in\(0,1/4\]\. Letp^\\widehat\{p\}be the randomized historical predictor constructed below\. Then, with probability at least1−δ1\-\\deltaover the training sample and all training randomization,p^\\widehat\{p\}satisfies

Bias𝒟⁡\(g;p^\)≤5​η​Mass𝒟⁡\(g;p^\)\+2​log⁡\(12​\|𝒢\|/δ\)\+2​m/N2η​m\\boxed\{\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\\leq 5\\eta\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\+\\frac\{2\\log\(12\|\\mathcal\{G\}\|/\\delta\)\+2m/N^\{2\}\}\{\\eta m\}\}\(20\)simultaneously for everyg∈𝒢g\\in\\mathcal\{G\}\.

#### The randomized historical predictor\.

LetZ1,…,ZmZ\_\{1\},\\ldots,Z\_\{m\}, withZt=\(Xt,Yt\)Z\_\{t\}=\(X\_\{t\},Y\_\{t\}\), be i\.i\.d\. from a distribution𝒟\\mathcal\{D\}\. Run[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)sequentially on this sample\. Before roundtt, the history determines a predictor

πt:𝒳→Δ​\(ΓN\),\\pi\_\{t\}:\\mathcal\{X\}\\to\\Delta\(\\Gamma\_\{N\}\),namely the distribution that the online algorithm would produce after seeing a new contextxxand the firstt−1t\-1examples\. Store these predictors\.

The offline outputp^\\widehat\{p\}is defined by:

1. \(i\)drawJJuniformly from\{1,…,m\}\\\{1,\\ldots,m\\\};
2. \(ii\)on inputxx, drawp∼πJ​\(x\)p\\sim\\pi\_\{J\}\(x\)\.

The indexJJand prediction draw are fresh randomization at test time\.

#### A martingale Bernstein lemma\.

We use the following standard fixed\-time form of Freedman’s inequality\.

###### Lemma 3\.8\(Freedman inequality\)\.

Let\(Xt,ℱt\)t=1m\(X\_\{t\},\\mathcal\{F\}\_\{t\}\)\_\{t=1\}^\{m\}be martingale differences satisfying\|Xt\|≤1\|X\_\{t\}\|\\leq 1, and let

Vm=∑t=1m𝔼​\[Xt2∣ℱt−1\]\.V\_\{m\}=\\sum\_\{t=1\}^\{m\}\\mathbb\{E\}\[X\_\{t\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\.For everyλ\>0\\lambda\>0, with probability at least1−2​e−λ1\-2e^\{\-\\lambda\},

\|∑t=1mXt\|≤2​Vm​λ\+2​λ3\.\\left\|\\sum\_\{t=1\}^\{m\}X\_\{t\}\\right\|\\leq\\sqrt\{2V\_\{m\}\\lambda\}\+\\frac\{2\\lambda\}\{3\}\.\(21\)

###### Proof of[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px2)\.

This is the two\-sided fixed\-time Freedman–Bernstein inequality; see, for example,Cesa\-Bianchi and Lugosi \([2006](https://arxiv.org/html/2607.28856#bib.bib4), Chapter 2\)\. ∎

#### Distributional transfer\.

For a fixed testgg, define on training roundtt

Ztg=\(Yt−pt\)​g​\(Xt,pt\),Rtg=g​\(Xt,pt\)2\.Z\_\{t\}^\{g\}=\(Y\_\{t\}\-p\_\{t\}\)g\(X\_\{t\},p\_\{t\}\),\\qquad R\_\{t\}^\{g\}=g\(X\_\{t\},p\_\{t\}\)^\{2\}\.Let

μtg=𝔼​\[Ztg∣ℱt−1\],νtg=𝔼​\[Rtg∣ℱt−1\],\\mu\_\{t\}^\{g\}=\\mathbb\{E\}\[Z\_\{t\}^\{g\}\\mid\\mathcal\{F\}\_\{t\-1\}\],\\qquad\\nu\_\{t\}^\{g\}=\\mathbb\{E\}\[R\_\{t\}^\{g\}\\mid\\mathcal\{F\}\_\{t\-1\}\],where the conditional expectation integrates over the fresh i\.i\.d\. example and the fresh prediction draw\. By construction of the historical predictor mixture,

Bias𝒟⁡\(g;p^\)=1m​∑t=1mμtg,Mass𝒟⁡\(g;p^\)=1m​∑t=1mνtg\.\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)=\\frac\{1\}\{m\}\\sum\_\{t=1\}^\{m\}\\mu\_\{t\}^\{g\},\\qquad\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)=\\frac\{1\}\{m\}\\sum\_\{t=1\}^\{m\}\\nu\_\{t\}^\{g\}\.\(22\)
###### Proof of[Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)\.

Let

λ=log⁡\(12​\|𝒢\|/δ\),Λm=2​λ\+2​mN2,\\lambda=\\log\(12\|\\mathcal\{G\}\|/\\delta\),\\qquad\\Lambda\_\{m\}=2\\lambda\+\\frac\{2m\}\{N^\{2\}\},and fixg∈𝒢g\\in\\mathcal\{G\}\. AbbreviateZt=ZtgZ\_\{t\}=Z\_\{t\}^\{g\},Rt=RtgR\_\{t\}=R\_\{t\}^\{g\},μt=μtg\\mu\_\{t\}=\\mu\_\{t\}^\{g\},νt=νtg\\nu\_\{t\}=\\nu\_\{t\}^\{g\}, andV=∑tνtV=\\sum\_\{t\}\\nu\_\{t\}\. SinceRt,νt∈\[0,1\]R\_\{t\},\\nu\_\{t\}\\in\[0,1\],\|Rt−νt\|≤1\|R\_\{t\}\-\\nu\_\{t\}\|\\leq 1, and[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px2)applies toRt−νtR\_\{t\}\-\\nu\_\{t\}directly\. SinceZt,μtZ\_\{t\},\\mu\_\{t\}only lie in\[−1,1\]\[\-1,1\], their difference satisfies\|Zt−μt\|≤2\|Z\_\{t\}\-\\mu\_\{t\}\|\\leq 2rather than the unit bound[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px2)assumes, so we instead apply the lemma to the rescaled difference\(Zt−μt\)/2\(Z\_\{t\}\-\\mu\_\{t\}\)/2– using𝔼​\[\(Zt−μt\)2∣ℱt−1\]≤𝔼​\[Zt2∣ℱt−1\]≤νt\\mathbb\{E\}\[\(Z\_\{t\}\-\\mu\_\{t\}\)^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq\\mathbb\{E\}\[Z\_\{t\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq\\nu\_\{t\}, sinceZt2≤RtZ\_\{t\}^\{2\}\\leq R\_\{t\}pointwise – and multiply the resulting inequality by22\. Union bound overgg\. With probability at least1−δ/31\-\\delta/3, simultaneously for allgg,

∑tRt≤2​V\+2​λ,∑tμt≤∑tZt\+2​V​λ\+4​λ3\.\\sum\_\{t\}R\_\{t\}\\leq 2V\+2\\lambda,\\qquad\\sum\_\{t\}\\mu\_\{t\}\\leq\\sum\_\{t\}Z\_\{t\}\+\\sqrt\{2V\\lambda\}\+\\frac\{4\\lambda\}\{3\}\.By a union bound,[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3)also holds on the training transcript with failure probabilityδ/3\\delta/3\. On the intersection of these events,

∑tμt\\displaystyle\\sum\_\{t\}\\mu\_\{t\}≤2​η​∑tRt\+log⁡\(3​\|𝒢\|/δ\)\+2​m/N2η\+2​V​λ\+4​λ3\\displaystyle\\leq 2\\eta\\sum\_\{t\}R\_\{t\}\+\\frac\{\\log\(3\|\\mathcal\{G\}\|/\\delta\)\+2m/N^\{2\}\}\{\\eta\}\+\\sqrt\{2V\\lambda\}\+\\frac\{4\\lambda\}\{3\}≤4​η​V\+4​η​λ\+log⁡\(3​\|𝒢\|/δ\)\+2​m/N2η\+2​V​λ\+4​λ3\\displaystyle\\leq 4\\eta V\+4\\eta\\lambda\+\\frac\{\\log\(3\|\\mathcal\{G\}\|/\\delta\)\+2m/N^\{2\}\}\{\\eta\}\+\\sqrt\{2V\\lambda\}\+\\frac\{4\\lambda\}\{3\}≤5​η​V\+Λmη\.\\displaystyle\\leq 5\\eta V\+\\frac\{\\Lambda\_\{m\}\}\{\\eta\}\.The last line uses2​V​λ≤η​V\+λ/\(2​η\)\\sqrt\{2V\\lambda\}\\leq\\eta V\+\\lambda/\(2\\eta\)andη≤1/4\\eta\\leq 1/4, which give4​η​λ\+λ/\(2​η\)\+4​λ/3≤2​λ/η4\\eta\\lambda\+\\lambda/\(2\\eta\)\+4\\lambda/3\\leq 2\\lambda/\\etathroughout this range with room to spare\. Divide bymmand use \([22](https://arxiv.org/html/2607.28856#S3.E22)\)\. ∎

Exactly as in[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2), running the historical\-predictor construction on the signed, geometrically scaled test class𝒢sc\\mathcal\{G\}^\{\\mathrm\{sc\}\}and optimizing the scale after the fact removes the linearMass𝒟\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}term at the cost of a square root\.

###### Corollary 3\.9\(Offline square\-root second\-order control\)\.

There is a universal constantCCsuch that, with probability at least1−δ1\-\\delta, simultaneously for everyg∈𝒢g\\in\\mathcal\{G\},

\|Bias𝒟⁡\(g;p^\)\|≤C​Λmm​Mass𝒟⁡\(g;p^\)\+C​Λmm,\|\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\|\\leq C\\sqrt\{\\frac\{\\Lambda\_\{m\}\}\{m\}\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\}\+C\\frac\{\\Lambda\_\{m\}\}\{m\},\(23\)whereΛm=1\+2​log⁡\(24​\|𝒢\|​\|𝒜m\|/δ\)\+2​m/N2\\Lambda\_\{m\}=1\+2\\log\(24\|\\mathcal\{G\}\|\|\\mathcal\{A\}\_\{m\}\|/\\delta\)\+2m/N^\{2\}and𝒜m=\{2−j:0≤j≤⌈log2⁡m⌉\}\\mathcal\{A\}\_\{m\}=\\\{2^\{\-j\}:0\\leq j\\leq\\lceil\\log\_\{2\}m\\rceil\\\}\.

###### Proof of[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px3)\.

Apply[Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)with rateη=1/4\\eta=1/4to𝒢sc=\{s​α​g:s∈\{−1,1\},g∈𝒢,α∈𝒜m\}\\mathcal\{G\}^\{\\mathrm\{sc\}\}=\\\{s\\alpha g:s\\in\\\{\-1,1\\\},g\\in\\mathcal\{G\},\\alpha\\in\\mathcal\{A\}\_\{m\}\\\}, whose cardinality is2​\|𝒢\|​\|𝒜m\|2\|\\mathcal\{G\}\|\|\\mathcal\{A\}\_\{m\}\|, usingBias𝒟⁡\(α​g;p^\)=α​Bias𝒟⁡\(g;p^\)\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(\\alpha g;\\widehat\{p\}\)=\\alpha\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)andMass𝒟⁡\(α​g;p^\)=α2​Mass𝒟⁡\(g;p^\)\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(\\alpha g;\\widehat\{p\}\)=\\alpha^\{2\}\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\. This gives, with probability at least1−δ1\-\\delta, simultaneously for everys,g,αs,g,\\alpha,

α​s​Bias𝒟⁡\(g;p^\)≤54​α2​Mass𝒟⁡\(g;p^\)\+4​Λmm,\\alpha s\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\\leq\\frac\{5\}\{4\}\\alpha^\{2\}\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\+\\frac\{4\\Lambda\_\{m\}\}\{m\},using2​log⁡\(12​\|𝒢sc\|/δ\)≤Λm2\\log\(12\|\\mathcal\{G\}^\{\\mathrm\{sc\}\}\|/\\delta\)\\leq\\Lambda\_\{m\}\. Choosingssto match the sign ofBias𝒟⁡\(g;p^\)\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)and writingM=Mass𝒟⁡\(g;p^\)≤1M=\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\\leq 1gives, for everyα∈𝒜m\\alpha\\in\\mathcal\{A\}\_\{m\},

\|Bias𝒟⁡\(g;p^\)\|≤5​α4​M\+4​Λmα​m=1m​\(5​α4​M′\+4​Λmα\),M′=m​M≤m\.\|\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\|\\leq\\frac\{5\\alpha\}\{4\}M\+\\frac\{4\\Lambda\_\{m\}\}\{\\alpha m\}=\\frac\{1\}\{m\}\\left\(\\frac\{5\\alpha\}\{4\}M^\{\\prime\}\+\\frac\{4\\Lambda\_\{m\}\}\{\\alpha\}\\right\),\\qquad M^\{\\prime\}=mM\\leq m\.The bracketed expression is exactly of the form optimized in the proof of[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2), withmmin place ofTT,M′M^\{\\prime\}in place ofMassT⁡\(g\)\\operatorname\{Mass\}\_\{T\}\(g\), andΛm\\Lambda\_\{m\}in place ofΛT\\Lambda\_\{T\}\(the constant5/45/4in place of1/21/2only changes the case\-split threshold and the universal constant, not the argument\)\. That optimization overα∈𝒜m\\alpha\\in\\mathcal\{A\}\_\{m\}bounds the bracket byC​Λm​M′=C​Λm​m​MC\\sqrt\{\\Lambda\_\{m\}M^\{\\prime\}\}=C\\sqrt\{\\Lambda\_\{m\}mM\}for a suitable universalCC, and dividing bymmgives

\|Bias𝒟⁡\(g;p^\)\|≤C​Λm​m​Mm=C​Λmm​M,\|\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g;\\widehat\{p\}\)\|\\leq\\frac\{C\\sqrt\{\\Lambda\_\{m\}mM\}\}\{m\}=C\\sqrt\{\\frac\{\\Lambda\_\{m\}\}\{m\}M\},which is \([23](https://arxiv.org/html/2607.28856#S3.E23)\) \(the additive termC​Λm/mC\\Lambda\_\{m\}/mappears in the same way in the small\-M′M^\{\\prime\}case of that optimization\)\. ∎

The offline theorem is stated for a finite test class, but the guarantee extends from a finite uniform cover to the full class with only the following approximation cost\.

###### Lemma 3\.10\(Uniform\-cover transfer\)\.

Let𝒢~\\widetilde\{\\mathcal\{G\}\}be a uniformρ\\rho\-cover of a class𝒢\\mathcal\{G\}\. If a randomized predictorp^\\hat\{p\}satisfies distributional\(c,a\)\(c,a\)second\-order multicalibration for𝒢~\\widetilde\{\\mathcal\{G\}\}, then it satisfies distributional\(2​c,a\+\(2​c\+1\)​ρ\)\(2c,\\,a\+\(2c\+1\)\\rho\)second\-order multicalibration for𝒢\\mathcal\{G\}\.

###### Proof of[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px3)\.

Fixg∈𝒢g\\in\\mathcal\{G\}and chooseg~\\widetilde\{g\}with‖g−g~‖∞≤ρ\\\|g\-\\widetilde\{g\}\\\|\_\{\\infty\}\\leq\\rho\. Since\|Y−p\|≤1\|Y\-p\|\\leq 1,

Bias𝒟⁡\(g\)≤Bias𝒟⁡\(g~\)\+ρ\.\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g\)\\leq\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(\\widetilde\{g\}\)\+\\rho\.Alsog~2≤2​g2\+2​ρ2≤2​g2\+2​ρ\\widetilde\{g\}^\{2\}\\leq 2g^\{2\}\+2\\rho^\{2\}\\leq 2g^\{2\}\+2\\rho, and hence

Bias𝒟⁡\(g\)≤2​c​Mass𝒟⁡\(g\)\+a\+\(2​c\+1\)​ρ\.\\operatorname\{Bias\}\_\{\\mathcal\{D\}\}\(g\)\\leq 2c\\operatorname\{Mass\}\_\{\\mathcal\{D\}\}\(g\)\+a\+\(2c\+1\)\\rho\.∎

## 4Lipschitz Proper Losses

This section instantiates the generic second\-order control of[Section˜3](https://arxiv.org/html/2607.28856#S3)for a first, concrete family of proper losses: those whose partial losses are Lipschitz\. We start with a single fixed Lipschitz proper loss, pass to finite families of such losses, and then, in the next subsection, use monotone transforms to reach every Lipschitz proper loss at once\. Two further families – bounded proper losses and convex Lipschitz proper losses – are treated in the sections that follow this one\.

The section’s key inequality – and, later, the key inequality of the convex Lipschitz family in[Section˜6](https://arxiv.org/html/2607.28856#S6)– both come from one fact about convex functions in general: the curvature of a convex function controls how much its Bregman divergence must grow away from a point\. We record this fact once, as a lemma about a general convexFF, and specialize it below to the negative Bayes riskFℓF\_\{\\ell\}to obtain[Section˜4](https://arxiv.org/html/2607.28856#S4), the inequality this section is built around\.

###### Lemma 4\.1\(Smooth Bregman lower bound\)\.

LetF:\[0,1\]→ℝF:\[0,1\]\\to\\mathbb\{R\}be convex and differentiable, and supposeF′F^\{\\prime\}isWW\-Lipschitz\. Then

DF​\(p,q\)≥\(F′​\(p\)−F′​\(q\)\)22​WD\_\{F\}\(p,q\)\\geq\\frac\{\(F^\{\\prime\}\(p\)\-F^\{\\prime\}\(q\)\)^\{2\}\}\{2W\}\(24\)for everyp,q∈\[0,1\]p,q\\in\[0,1\]\.

###### Proof of[Section˜4](https://arxiv.org/html/2607.28856#S4)\.

Assumep\>qp\>qand leta=F′​\(p\)−F′​\(q\)≥0a=F^\{\\prime\}\(p\)\-F^\{\\prime\}\(q\)\\geq 0\. Foru∈\[q,p\]u\\in\[q,p\],

F′​\(u\)−F′​\(q\)≥max⁡\{0,a−W​\(p−u\)\}\.F^\{\\prime\}\(u\)\-F^\{\\prime\}\(q\)\\geq\\max\\\{0,a\-W\(p\-u\)\\\}\.Sincea≤W​\(p−q\)a\\leq W\(p\-q\),

DF​\(p,q\)\\displaystyle D\_\{F\}\(p,q\)=∫qp\(F′​\(u\)−F′​\(q\)\)​𝑑u\\displaystyle=\\int\_\{q\}^\{p\}\(F^\{\\prime\}\(u\)\-F^\{\\prime\}\(q\)\)\\,du≥∫p−a/Wp\(a−W​\(p−u\)\)​𝑑u=a22​W\.\\displaystyle\\geq\\int\_\{p\-a/W\}^\{p\}\(a\-W\(p\-u\)\)\\,du=\\frac\{a^\{2\}\}\{2W\}\.The casep<qp<qis symmetric\. ∎

We call a proper lossℓ\\ell*LL\-Lipschitz*if both partial losses satisfy\|ℓ​\(p,y\)−ℓ​\(q,y\)\|≤L​\|p−q\|\|\\ell\(p,y\)\-\\ell\(q,y\)\|\\leq L\|p\-q\|fory∈\{0,1\}y\\in\\\{0,1\\\}\. The next lemma is the key loss\-specific inequality used throughout this section: it upgrades the identity of[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3)to a quantitative statement in which the drift term controls the square of the bias coefficient, with an explicit constant governed byLL\.

###### Lemma 4\.2\(Quadratic\-growth inequality\)\.

Ifℓ\\ellis anLL\-Lipschitz proper loss, thenFℓF\_\{\\ell\}is differentiable,Fℓ′=−ΔℓF\_\{\\ell\}^\{\\prime\}=\-\\Delta\_\{\\ell\}is2​L2L\-Lipschitz, and for everyp,q∈\[0,1\]p,q\\in\[0,1\],

Lp​\(q\)−Lp​\(p\)≥14​L​\(Δℓ​\(p\)−Δℓ​\(q\)\)2\.L\_\{p\}\(q\)\-L\_\{p\}\(p\)\\geq\\frac\{1\}\{4L\}\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)^\{2\}\.\(25\)Consequently,

ℓ​\(p,y\)−ℓ​\(q,y\)≤\(y−p\)​\(Δℓ​\(p\)−Δℓ​\(q\)\)−14​L​\(Δℓ​\(p\)−Δℓ​\(q\)\)2\.\\ell\(p,y\)\-\\ell\(q,y\)\\leq\(y\-p\)\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)\-\\frac\{1\}\{4L\}\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)^\{2\}\.\(26\)Conversely, if \([25](https://arxiv.org/html/2607.28856#S4.E25)\) holds with4​L4Lreplaced by a constantKK, then both partial losses areK/2K/2\-Lipschitz\.

###### Proof of[Section˜4](https://arxiv.org/html/2607.28856#S4)\.

The triangle inequality gives\|Δℓ​\(p\)−Δℓ​\(q\)\|≤2​L​\|p−q\|\|\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\|\\leq 2L\|p\-q\|\. Thus, by[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3),g​\(q\)=−Δℓ​\(q\)g\(q\)=\-\\Delta\_\{\\ell\}\(q\)is a continuous2​L2L\-Lipschitz selection from∂Fℓ​\(q\)\\partial F\_\{\\ell\}\(q\)\. Forx<zx<z, the subgradient inequalities giveg​\(x\)≤\(Fℓ​\(z\)−Fℓ​\(x\)\)/\(z−x\)≤g​\(z\)g\(x\)\\leq\(F\_\{\\ell\}\(z\)\-F\_\{\\ell\}\(x\)\)/\(z\-x\)\\leq g\(z\); lettingz↓xz\\downarrow xandz↑xz\\uparrow xshows thatFℓF\_\{\\ell\}is differentiable withFℓ′=gF\_\{\\ell\}^\{\\prime\}=g, henceFℓ′F\_\{\\ell\}^\{\\prime\}is2​L2L\-Lipschitz\.[Section˜4](https://arxiv.org/html/2607.28856#S4)withW=2​LW=2L, together with the Bregman\-divergence identity of[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3), gives \([25](https://arxiv.org/html/2607.28856#S4.E25)\); substituting into[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3)proves \([26](https://arxiv.org/html/2607.28856#S4.E26)\)\.

For the converse, apply the assumed inequality to\(p,q\)\(p,q\)and to\(q,p\)\(q,p\)and add\. The identity

\[Lp​\(q\)−Lp​\(p\)\]\+\[Lq​\(p\)−Lq​\(q\)\]=−\(p−q\)​\(Δℓ​\(p\)−Δℓ​\(q\)\)\[L\_\{p\}\(q\)\-L\_\{p\}\(p\)\]\+\[L\_\{q\}\(p\)\-L\_\{q\}\(q\)\]=\-\(p\-q\)\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)and monotonicity ofΔℓ\\Delta\_\{\\ell\}\(which is nonincreasing, since−Δℓ∈∂Fℓ\-\\Delta\_\{\\ell\}\\in\\partial F\_\{\\ell\}andFℓF\_\{\\ell\}is convex\) give\|Δℓ​\(p\)−Δℓ​\(q\)\|≤\(K/2\)​\|p−q\|\|\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\|\\leq\(K/2\)\|p\-q\|\. The canonical formulasℓ​\(p,0\)=Lp​\(p\)−p​Δℓ​\(p\)\\ell\(p,0\)=L\_\{p\}\(p\)\-p\\Delta\_\{\\ell\}\(p\),ℓ​\(p,1\)=Lp​\(p\)\+\(1−p\)​Δℓ​\(p\)\\ell\(p,1\)=L\_\{p\}\(p\)\+\(1\-p\)\\Delta\_\{\\ell\}\(p\)then imply that both partial losses areK/2K/2\-Lipschitz\. ∎

Lipschitzness of the partial losses is often introduced as a separate condition from smoothness of the negative Bayes risk, but for proper losses the two coincide up to a factor of22, so there is no need to treat them as two different hypotheses\.

###### Corollary 4\.3\(Lipschitzness and smoothness coincide\)\.

If both partial losses ofℓ\\ellareLL\-Lipschitz, thenFℓ′F\_\{\\ell\}^\{\\prime\}is2​L2L\-Lipschitz \([Section˜4](https://arxiv.org/html/2607.28856#S4)\)\. Conversely, ifFℓ′F\_\{\\ell\}^\{\\prime\}isWW\-Lipschitz, then both partial losses ofℓ\\ellareWW\-Lipschitz\.

###### Proof of[Section˜4](https://arxiv.org/html/2607.28856#S4)\.

Only the converse needs proof\. IfFℓ′F\_\{\\ell\}^\{\\prime\}isWW\-Lipschitz, thenFℓ′′F\_\{\\ell\}^\{\\prime\\prime\}exists almost everywhere with\|Fℓ′′\|≤W\|F\_\{\\ell\}^\{\\prime\\prime\}\|\\leq W\. Differentiating the canonical formulasℓ​\(p,0\)=−Fℓ​\(p\)−p​Fℓ′​\(p\)\\ell\(p,0\)=\-F\_\{\\ell\}\(p\)\-pF\_\{\\ell\}^\{\\prime\}\(p\)andℓ​\(p,1\)=−Fℓ​\(p\)−\(1−p\)​Fℓ′​\(p\)\\ell\(p,1\)=\-F\_\{\\ell\}\(p\)\-\(1\-p\)F\_\{\\ell\}^\{\\prime\}\(p\)givesℓ​\(⋅,0\)′​\(p\)=p​Fℓ′′​\(p\)\\ell\(\\cdot,0\)^\{\\prime\}\(p\)=pF\_\{\\ell\}^\{\\prime\\prime\}\(p\)andℓ​\(⋅,1\)′​\(p\)=−\(1−p\)​Fℓ′′​\(p\)\\ell\(\\cdot,1\)^\{\\prime\}\(p\)=\-\(1\-p\)F\_\{\\ell\}^\{\\prime\\prime\}\(p\), both bounded in absolute value byWWsincep,1−p≤1p,1\-p\\leq 1\. ∎

Convexity of the partial losses is not enough by itself to give any quadratic\-growth constant, however large – Lipschitzness \(equivalently, smoothness\) is doing real work above\.

###### Example 4\.4\(Convex bounded proper loss with no quadratic\-growth constant\)\.

Let

w​\(p\)=1p​\(1−p\),w\(p\)=\\frac\{1\}\{\\sqrt\{p\(1\-p\)\}\},and define

ℓ​\(p,0\)=∫0pu​w​\(u\)​𝑑u,ℓ​\(p,1\)=∫p1\(1−u\)​w​\(u\)​𝑑u\.\\ell\(p,0\)=\\int\_\{0\}^\{p\}uw\(u\)\\,du,\\qquad\\ell\(p,1\)=\\int\_\{p\}^\{1\}\(1\-u\)w\(u\)\\,du\.The loss is bounded, strictly proper, and both partial losses are convex\. Its negative Bayes risk has curvatureF′′​\(p\)=w​\(p\)F^\{\\prime\\prime\}\(p\)=w\(p\), which diverges asp→0p\\to 0orp→1p\\to 1\. ConsequentlyFℓ′=−ΔℓF\_\{\\ell\}^\{\\prime\}=\-\\Delta\_\{\\ell\}is notWW\-Lipschitz for any finiteWW, so no quadratic\-growth inequalityLp​\(q\)−Lp​\(p\)≥\(1/K\)​\(Δℓ​\(p\)−Δℓ​\(q\)\)2L\_\{p\}\(q\)\-L\_\{p\}\(p\)\\geq\(1/K\)\(\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(q\)\)^\{2\}holds for any finiteKK: locally,

\(F′​\(p\)−F′​\(q\)\)2DF​\(p,q\)→2​F′′​\(q\)→∞as​q→0​or​q→1\.\\frac\{\(F^\{\\prime\}\(p\)\-F^\{\\prime\}\(q\)\)^\{2\}\}\{D\_\{F\}\(p,q\)\}\\to 2F^\{\\prime\\prime\}\(q\)\\to\\infty\\qquad\\text\{as \}q\\to 0\\text\{ or \}q\\to 1\.Thus convexity alone does not control the quadratic\-growth constant, and[Section˜4](https://arxiv.org/html/2607.28856#S4)applies to this loss for no finite Lipschitz \(or, equivalently, smoothness\) constant\.

Consequently, every result in this section stated for anLL\-Lipschitz proper loss applies verbatim to a proper loss whose negative Bayes risk isWW\-smooth, simply by takingL=WL=W; we do not restate the theorems separately for smoothness\.

### 4\.1A single Lipschitz loss

For a swap ruleϕ\\phi, define

gℓ,ϕ​\(x,p\)=Δℓ​\(p\)−Δℓ​\(ϕ​\(p\)​\(x\)\)2​L\.g\_\{\\ell,\\phi\}\(x,p\)=\\frac\{\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(\\phi\(p\)\(x\)\)\}\{2L\}\.Sinceℓ\\ellisLL\-Lipschitz, these tests take values in\[−1,1\]\[\-1,1\]\.

###### Theorem 4\.5\(Single Lipschitz proper loss\)\.

Letℓ\\ellbe anLL\-Lipschitz proper loss and letℋ\\mathcal\{H\}be finite\. There is a choice of the prediction grid such that, with probability at least1−δ1\-\\delta,

SwapRegT⁡\(ℓ,ℋ\)=O~​\(L​T1/3​\(log⁡\|ℋ\|\)2/3\)\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(LT^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\\right\)\.The historical predictor satisfies

SwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(L​\(log⁡\|ℋ\|m\)2/3\)\.\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(L\\left\(\\frac\{\\log\|\\mathcal\{H\}\|\}\{m\}\\right\)^\{2/3\}\\right\)\.

###### Proof of[Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)\.

Fix a swap ruleϕ\\phi\. By[Section˜4](https://arxiv.org/html/2607.28856#S4),

SwapRegT⁡\(ℓ,ϕ\)≤2​L​BiasT⁡\(gℓ,ϕ\)−L​MassT⁡\(gℓ,ϕ\)\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\phi\)\\leq 2L\\operatorname\{Bias\}\_\{T\}\(g\_\{\\ell,\\phi\}\)\-L\\operatorname\{Mass\}\_\{T\}\(g\_\{\\ell,\\phi\}\)\.Run[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)on the selector class\{gℓ,ϕ:ϕ∈ΦN\}\\\{g\_\{\\ell,\\phi\}:\\phi\\in\\Phi\_\{N\}\\\}, of size at most\|ℋ\|N\+1\|\\mathcal\{H\}\|^\{N\+1\}, withη=1/4\\eta=1/4\. By[Theorem˜3\.3](https://arxiv.org/html/2607.28856#S3.Thmtheorem3), theMassT\\operatorname\{Mass\}\_\{T\}term cancels exactly and

SwapRegT⁡\(ℓ,ϕ\)≤8​L​\[\(N\+1\)​log⁡\|ℋ\|\+log⁡1δ\+2​TN2\]\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\phi\)\\leq 8L\\left\[\(N\+1\)\\log\|\\mathcal\{H\}\|\+\\log\\frac\{1\}\{\\delta\}\+\\frac\{2T\}\{N^\{2\}\}\\right\]\.This event is simultaneous over all swap rules, so it boundsSwapRegT⁡\(ℓ,ℋ\)\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)\. OptimizingN≍\(T/log⁡\|ℋ\|\)1/3N\\asymp\(T/\\log\|\\mathcal\{H\}\|\)^\{1/3\}proves the online statement\.

For the offline statement, apply[Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)to the same selector class withη=1/10\\eta=1/10\. Again the population mass term cancels, leaving

SwapAgn𝒟⁡\(ℓ,ℋ\)=O​\(L​\(N\+1\)​log⁡\|ℋ\|\+log⁡\(1/δ\)\+m/N2m\)\.\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=O\\\!\\left\(L\\,\\frac\{\(N\+1\)\\log\|\\mathcal\{H\}\|\+\\log\(1/\\delta\)\+m/N^\{2\}\}\{m\}\\right\)\.OptimizeN≍\(m/log⁡\|ℋ\|\)1/3N\\asymp\(m/\\log\|\\mathcal\{H\}\|\)^\{1/3\}\. ∎

By[Section˜3](https://arxiv.org/html/2607.28856#S3), the exponential weights on the selector class factorize over prediction buckets, so the algorithm above uses\(N\+1\)​\|ℋ\|\(N\+1\)\|\\mathcal\{H\}\|scalar weights rather than\|ℋ\|N\+1\|\\mathcal\{H\}\|^\{N\+1\}\.

The online exponent in[Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)cannot be improved in general\. The next result is stated for the half\-Brier loss, and uses the following sharp online recalibration lower bound as a black box\.

###### Theorem 4\.6\(Recalibration lower bound, black\-box form,\(Hu et al\.,[2026b](https://arxiv.org/html/2607.28856#bib.bib21)\)\)\.

There are constantsc0,ε0\>0c\_\{0\},\\varepsilon\_\{0\}\>0such that for everyε≤ε0\\varepsilon\\leq\\varepsilon\_\{0\}and everyT≤c0​ε−3T\\leq c\_\{0\}\\varepsilon^\{\-3\}, there is a nonanticipating distribution over hintsqt∈\[1/4,3/4\]q\_\{t\}\\in\[1/4,3/4\]and labelsYt∼Ber⁡\(qt\)Y\_\{t\}\\sim\\operatorname\{Ber\}\(q\_\{t\}\)for which no forecaster simultaneously has

𝔼​𝒦1​\(p1:T,Y1:T\)≤ε\\mathbb\{E\}\\mathcal\{K\}\_\{1\}\(p\_\{1:T\},Y\_\{1:T\}\)\\leq\\varepsilonand

𝔼​1T​∑t=1T\[\(pt−Yt\)2−\(qt−Yt\)2\]≤ε2\.\\mathbb\{E\}\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\left\[\(p\_\{t\}\-Y\_\{t\}\)^\{2\}\-\(q\_\{t\}\-Y\_\{t\}\)^\{2\}\\right\]\\leq\\varepsilon^\{2\}\.Here

𝒦1​\(p1:T,y1:T\)=1T​∑v\|∑t:pt=v\(pt−yt\)\|\.\\mathcal\{K\}\_\{1\}\(p\_\{1:T\},y\_\{1:T\}\)=\\frac\{1\}\{T\}\\sum\_\{v\}\\left\|\\sum\_\{t:p\_\{t\}=v\}\(p\_\{t\}\-y\_\{t\}\)\\right\|\.

###### Theorem 4\.7\(Fixed three\-hypothesis lower bound\)\.

Let

ℓB​\(p,y\)=12​\(p−y\)2\.\\ell\_\{\\mathrm\{B\}\}\(p,y\)=\\frac\{1\}\{2\}\(p\-y\)^\{2\}\.There is a fixed domain𝒳\\mathcal\{X\}and a fixed classℋ⋆\\mathcal\{H\}\_\{\\star\}of three hypotheses such that every randomized learner satisfies

sup\(xt,yt\)𝔼​SwapRegT⁡\(ℓB,ℋ⋆\)≥c​T1/3\\sup\_\{\(x\_\{t\},y\_\{t\}\)\}\\mathbb\{E\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{\\mathrm\{B\}\},\\mathcal\{H\}\_\{\\star\}\)\\geq cT^\{1/3\}for all sufficiently largeTT\.

###### Proof of[Theorem˜4\.7](https://arxiv.org/html/2607.28856#S4.Thmtheorem7)\.

Let

𝒳=\[1/4,3/4\]×\[0,1/8\]\\mathcal\{X\}=\[1/4,3/4\]\\times\[0,1/8\]and

h0​\(q,s\)=q,h\+​\(q,s\)=q\+s,h−​\(q,s\)=q−s\.h\_\{0\}\(q,s\)=q,\\qquad h\_\{\+\}\(q,s\)=q\+s,\\qquad h\_\{\-\}\(q,s\)=q\-s\.Fixε\\varepsilonand puts=ε/2s=\\varepsilon/2\. Feed the learner contextsxt=\(qt,s\)x\_\{t\}=\(q\_\{t\},s\)from the hard recalibration instance\. Work first with the unscaled square lossℓ¯​\(p,y\)=\(p−y\)2\\bar\{\\ell\}\(p,y\)=\(p\-y\)^\{2\}, and letSwapReg¯T\\overline\{\\operatorname\{SwapReg\}\}\_\{T\}denote the corresponding swap regret\. ThenSwapReg¯T=2​SwapRegT⁡\(ℓB,ℋ⋆\)\\overline\{\\operatorname\{SwapReg\}\}\_\{T\}=2\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{\\mathrm\{B\}\},\\mathcal\{H\}\_\{\\star\}\)\.

Let

R0=∑t\[\(pt−Yt\)2−\(qt−Yt\)2\]\.R\_\{0\}=\\sum\_\{t\}\[\(p\_\{t\}\-Y\_\{t\}\)^\{2\}\-\(q\_\{t\}\-Y\_\{t\}\)^\{2\}\]\.The constant selectorh0h\_\{0\}givesSwapReg¯T≥R0\\overline\{\\operatorname\{SwapReg\}\}\_\{T\}\\geq R\_\{0\}, and conditional unbiasedness gives

𝔼​R0=𝔼​∑t\(pt−qt\)2\.\\mathbb\{E\}R\_\{0\}=\\mathbb\{E\}\\sum\_\{t\}\(p\_\{t\}\-q\_\{t\}\)^\{2\}\.For every realized prediction valuevv, letIv=\{t:pt=v\}I\_\{v\}=\\\{t:p\_\{t\}=v\\\}and chooseh\+h\_\{\+\}orh−h\_\{\-\}according to the sign of∑t∈Iv\(Yt−qt\)\\sum\_\{t\\in I\_\{v\}\}\(Y\_\{t\}\-q\_\{t\}\)\. Since

\(q−y\)2−\(q\+τ​s−y\)2=2​τ​s​\(y−q\)−s2,\(q\-y\)^\{2\}\-\(q\+\\tau s\-y\)^\{2\}=2\\tau s\(y\-q\)\-s^\{2\},this selector gives

SwapReg¯T≥R0\+2​s​MT−T​s2,MT=∑v\|∑t∈Iv\(Yt−qt\)\|\.\\overline\{\\operatorname\{SwapReg\}\}\_\{T\}\\geq R\_\{0\}\+2sM\_\{T\}\-Ts^\{2\},\\qquad M\_\{T\}=\\sum\_\{v\}\\left\|\\sum\_\{t\\in I\_\{v\}\}\(Y\_\{t\}\-q\_\{t\}\)\\right\|\.If𝔼​SwapReg¯T≤r​T\\mathbb\{E\}\\overline\{\\operatorname\{SwapReg\}\}\_\{T\}\\leq rT, then

𝔼​∑t\(pt−qt\)2≤r​T,𝔼​MTT≤r\+s22​s\.\\mathbb\{E\}\\sum\_\{t\}\(p\_\{t\}\-q\_\{t\}\)^\{2\}\\leq rT,\\qquad\\frac\{\\mathbb\{E\}M\_\{T\}\}\{T\}\\leq\\frac\{r\+s^\{2\}\}\{2s\}\.Moreover,

T​𝒦1​\(p,Y\)≤MT\+∑t\|pt−qt\|,T\\mathcal\{K\}\_\{1\}\(p,Y\)\\leq M\_\{T\}\+\\sum\_\{t\}\|p\_\{t\}\-q\_\{t\}\|,so Cauchy–Schwarz gives

𝔼​𝒦1​\(p,Y\)≤r\+s22​s\+r\.\\mathbb\{E\}\\mathcal\{K\}\_\{1\}\(p,Y\)\\leq\\frac\{r\+s^\{2\}\}\{2s\}\+\\sqrt\{r\}\.Ifr≤ε2/64r\\leq\\varepsilon^\{2\}/64ands=ε/2s=\\varepsilon/2, the right side is less thanε\\varepsilon, while𝔼​R0/T≤ε2\\mathbb\{E\}R\_\{0\}/T\\leq\\varepsilon^\{2\}\. This contradicts[Theorem˜4\.6](https://arxiv.org/html/2607.28856#S4.Thmtheorem6)wheneverT≤c0​ε−3T\\leq c\_\{0\}\\varepsilon^\{\-3\}\. Choosingε≍T−1/3\\varepsilon\\asymp T^\{\-1/3\}yields

𝔼​SwapRegT⁡\(ℓB,ℋ⋆\)=12​𝔼​SwapReg¯T≥c​T1/3\.\\mathbb\{E\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{\\mathrm\{B\}\},\\mathcal\{H\}\_\{\\star\}\)=\\frac\{1\}\{2\}\\mathbb\{E\}\\overline\{\\operatorname\{SwapReg\}\}\_\{T\}\\geq cT^\{1/3\}\.∎

###### Corollary 4\.8\(Optimal smooth\-loss time exponent from[Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)and[Theorem˜4\.7](https://arxiv.org/html/2607.28856#S4.Thmtheorem7)\)\.

For the fixed pair\(ℓB,ℋ⋆\)\(\\ell\_\{\\mathrm\{B\}\},\\mathcal\{H\}\_\{\\star\}\),

inflearnerssupadversaries𝔼​SwapRegT⁡\(ℓB,ℋ⋆\)=Θ​\(T1/3\)\\inf\_\{\\text\{learners\}\}\\sup\_\{\\text\{adversaries\}\}\\mathbb\{E\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{\\mathrm\{B\}\},\\mathcal\{H\}\_\{\\star\}\)=\\Theta\(T^\{1/3\}\)up to logarithmic factors and universal constants\.

The half\-Brier lossℓB​\(p,y\)=12​\(p−y\)2\\ell\_\{\\mathrm\{B\}\}\(p,y\)=\\frac\{1\}\{2\}\(p\-y\)^\{2\}hasℓB​\(⋅,0\)′​\(p\)=p\\ell\_\{\\mathrm\{B\}\}\(\\cdot,0\)^\{\\prime\}\(p\)=pandℓB​\(⋅,1\)′​\(p\)=p−1\\ell\_\{\\mathrm\{B\}\}\(\\cdot,1\)^\{\\prime\}\(p\)=p\-1, both bounded by11in absolute value on\[0,1\]\[0,1\], soℓB\\ell\_\{\\mathrm\{B\}\}is11\-Lipschitz and[Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)gives the matching upper boundO~​\(T1/3\)\\widetilde\{O\}\(T^\{1/3\}\);[Theorem˜4\.7](https://arxiv.org/html/2607.28856#S4.Thmtheorem7)gives the lower bound\.

### 4\.2Finite families of Lipschitz losses

The single\-loss result extends to a finite set of proper losses by running the same second\-order multicalibration algorithm on the union of the loss\-and\-selector induced test classes\. The selector part contributes\(N\+1\)​log⁡\|ℋ\|\(N\+1\)\\log\|\\mathcal\{H\}\|, while the loss family contributes onlylog⁡\|ℒ\|\\log\|\\mathcal\{L\}\|\.

###### Theorem 4\.9\(Finite Lipschitz families\)\.

Letℒ\\mathcal\{L\}be finite and suppose everyℓ∈ℒ\\ell\\in\\mathcal\{L\}isLL\-Lipschitz\. One learner satisfies, simultaneously for everyℓ∈ℒ\\ell\\in\\mathcal\{L\},

SwapRegT⁡\(ℓ,ℋ\)=O~​\(L​T1/3​\(log⁡\|ℋ\|\+log⁡\|ℒ\|\)2/3\)\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(LT^\{1/3\}\(\\log\|\\mathcal\{H\}\|\+\\log\|\\mathcal\{L\}\|\)^\{2/3\}\\right\)and

SwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(L​\(log⁡\|ℋ\|\+log⁡\|ℒ\|m\)2/3\)\.\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(L\\left\(\\frac\{\\log\|\\mathcal\{H\}\|\+\\log\|\\mathcal\{L\}\|\}\{m\}\\right\)^\{2/3\}\\right\)\.

###### Proof of[Theorem˜4\.9](https://arxiv.org/html/2607.28856#S4.Thmtheorem9)\.

Run the algorithm of[Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)on the union\{gℓ,ϕ:ℓ∈ℒ,ϕ∈ΦN\}\\\{g\_\{\\ell,\\phi\}:\\ell\\in\\mathcal\{L\},\\phi\\in\\Phi\_\{N\}\\\}of the selector classes, whose logarithmic cardinality is at mostlog⁡\|ℒ\|\+\(N\+1\)​log⁡\|ℋ\|\\log\|\\mathcal\{L\}\|\+\(N\+1\)\\log\|\\mathcal\{H\}\|\. Since everyℓ∈ℒ\\ell\\in\\mathcal\{L\}shares the same Lipschitz constantLL, the coefficient cancellation in the proof of[Theorem˜4\.5](https://arxiv.org/html/2607.28856#S4.Thmtheorem5)\(atη=1/4\\eta=1/4online andη=1/10\\eta=1/10offline\) applies uniformly, and this displayed event now boundsSwapRegT⁡\(ℓ,ℋ\)\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)\(respectivelySwapAgn𝒟⁡\(ℓ,ℋ\)\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)\) simultaneously for everyℓ∈ℒ\\ell\\in\\mathcal\{L\}\. Optimize the grid\. ∎

### 4\.3All Lipschitz proper losses through monotone transforms

This subsection records a useful auxiliary route for proper losses with Lipschitz partial losses\. The main statement is the rate theorem[Theorem˜4\.10](https://arxiv.org/html/2607.28856#S4.Thmtheorem10)\. It follows by reducing the loss family to monotone transforms in[Theorem˜4\.11](https://arxiv.org/html/2607.28856#S4.Thmtheorem11)and covering that transform class in[Section˜4\.3](https://arxiv.org/html/2607.28856#S4.SS3)\.

###### Theorem 4\.10\(Offline simultaneous Lipschitz proper losses\)\.

Letℋ\\mathcal\{H\}be finite and letℒLip\\mathcal\{L\}\_\{\\mathrm\{Lip\}\}be the class of proper losses with11\-Lipschitz partial losses\. There is a choice of prediction grid and finite cover for the offline historical\-predictor procedure such that, with probability at least1−δ1\-\\deltaover the training sample and training randomization,

supℓ∈ℒLipSwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(\(log⁡\|ℋ\|m\)2/3\+1m\+log⁡\(1/δ\)m\)\.\\sup\_\{\\ell\\in\\mathcal\{L\}\_\{\\mathrm\{Lip\}\}\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(\\left\(\\frac\{\\log\|\\mathcal\{H\}\|\}\{m\}\\right\)^\{2/3\}\+\\frac\{1\}\{\\sqrt\{m\}\}\+\\frac\{\\log\(1/\\delta\)\}\{m\}\\right\)\.

The proof of[Theorem˜4\.10](https://arxiv.org/html/2607.28856#S4.Thmtheorem10)appears after[Theorems˜4\.11](https://arxiv.org/html/2607.28856#S4.Thmtheorem11)and[4\.3](https://arxiv.org/html/2607.28856#S4.SS3), which provide the reduction and covering estimates used to obtain the displayed rate\.

We now introduce the transform class that will replace the original continuum of Lipschitz proper losses\.

Let

ℳ2=\{g:\[0,1\]→ℝ:g​\(0\)=0,g​is nonincreasing, and​\|g​\(p\)−g​\(q\)\|≤2​\|p−q\|\}\.\\mathcal\{M\}\_\{2\}=\\left\\\{g:\[0,1\]\\to\\mathbb\{R\}:g\(0\)=0,\\ g\\text\{ is nonincreasing, and \}\|g\(p\)\-g\(q\)\|\\leq 2\|p\-q\|\\right\\\}\.\(27\)Define

𝒢mon​\(ℋ\)=\{\(x,p\)↦g​\(p\)−g​\(ϕ​\(p\)​\(x\)\)2:g∈ℳ2,ϕ∈ΦN\}\.\\mathcal\{G\}\_\{\\mathrm\{mon\}\}\(\\mathcal\{H\}\)=\\left\\\{\(x,p\)\\mapsto\\frac\{g\(p\)\-g\(\\phi\(p\)\(x\)\)\}\{2\}:g\\in\\mathcal\{M\}\_\{2\},\\ \\phi\\in\\Phi\_\{N\}\\right\\\}\.\(28\)
The next theorem explains why this transform class is the right one: if the predictor is second\-order multicalibrated against these transform tests, then it is swap\-agnostic for every Lipschitz proper loss at once\.

###### Theorem 4\.11\(Monotone\-transform reduction\)\.

If a transcript satisfies one\-sided\(c,a\)\(c,a\)second\-order multicalibration for𝒢mon​\(ℋ\)\\mathcal\{G\}\_\{\\mathrm\{mon\}\}\(\\mathcal\{H\}\)withc≤1/2c\\leq 1/2, then simultaneously for every proper loss with11\-Lipschitz partial losses,

SwapRegT⁡\(ℓ,ℋ\)≤2​a\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)\\leq 2a\.\(29\)The same statement holds distributionally\.

###### Proof of[Theorem˜4\.11](https://arxiv.org/html/2607.28856#S4.Thmtheorem11)\.

Fix such a loss and letgℓ​\(p\)=Δℓ​\(p\)−Δℓ​\(0\)g\_\{\\ell\}\(p\)=\\Delta\_\{\\ell\}\(p\)\-\\Delta\_\{\\ell\}\(0\)\. By the proof of[Section˜4](https://arxiv.org/html/2607.28856#S4)withL=1L=1,Δℓ\\Delta\_\{\\ell\}is nonincreasing and22\-Lipschitz, sogℓ∈ℳ2g\_\{\\ell\}\\in\\mathcal\{M\}\_\{2\}\. By[Equation˜26](https://arxiv.org/html/2607.28856#S4.E26)withL=1L=1, writingaϕ​\(x,p\)=\(gℓ​\(p\)−gℓ​\(ϕ​\(p\)​\(x\)\)\)/2a\_\{\\phi\}\(x,p\)=\(g\_\{\\ell\}\(p\)\-g\_\{\\ell\}\(\\phi\(p\)\(x\)\)\)/2for the corresponding test in𝒢mon​\(ℋ\)\\mathcal\{G\}\_\{\\mathrm\{mon\}\}\(\\mathcal\{H\}\),

ℓ​\(p,y\)−ℓ​\(ϕ​\(p\)​\(x\),y\)≤2​\(y−p\)​aϕ​\(x,p\)−aϕ​\(x,p\)2\.\\ell\(p,y\)\-\\ell\(\\phi\(p\)\(x\),y\)\\leq 2\(y\-p\)a\_\{\\phi\}\(x,p\)\-a\_\{\\phi\}\(x,p\)^\{2\}\.Summing over the transcript and using\(c,a\)\(c,a\)second\-order multicalibration withc≤1/2c\\leq 1/2,

SwapRegT⁡\(ℓ,ϕ\)≤\(2​c−1\)​MassT⁡\(aϕ\)\+2​a≤2​a\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\phi\)\\leq\(2c\-1\)\\operatorname\{Mass\}\_\{T\}\(a\_\{\\phi\}\)\+2a\\leq 2a\.Take the supremum overϕ\\phi\. The distributional proof is identical\. ∎

To make the offline procedure finite, we approximate the transform class by a uniform cover\. The following crude entropy estimate is enough for the rate claimed in[Theorem˜4\.10](https://arxiv.org/html/2607.28856#S4.Thmtheorem10)\.

###### Proposition 4\.12\(A crude cover of monotone Lipschitz transforms\)\.

There is a universal constantC0C\_\{0\}such that, for everyρ∈\(0,1\)\\rho\\in\(0,1\),

log⁡𝒩∞​\(ρ,ℳ2\)≤C0ρ​log⁡\(C0ρ\)\.\\log\\mathcal\{N\}\_\{\\infty\}\(\\rho,\\mathcal\{M\}\_\{2\}\)\\leq\\frac\{C\_\{0\}\}\{\\rho\}\\log\\\!\\left\(\\frac\{C\_\{0\}\}\{\\rho\}\\right\)\.Ifℋ\\mathcal\{H\}is finite, then

𝒩∞​\(ρ,𝒢mon​\(ℋ\)\)≤\|ℋ\|N\+1​𝒩∞​\(ρ,ℳ2\)\.\\mathcal\{N\}\_\{\\infty\}\(\\rho,\\mathcal\{G\}\_\{\\mathrm\{mon\}\}\(\\mathcal\{H\}\)\)\\leq\|\\mathcal\{H\}\|^\{N\+1\}\\mathcal\{N\}\_\{\\infty\}\(\\rho,\\mathcal\{M\}\_\{2\}\)\.

###### Proof of[Section˜4\.3](https://arxiv.org/html/2607.28856#S4.SS3)\.

Partition\[0,1\]\[0,1\]into intervals of length at mostρ/8\\rho/8\. Quantize the value ofggat each grid point to a mesh of widthρ/4\\rho/4in\[−2,0\]\[\-2,0\]and linearly interpolate\. Lipschitzness and quantization give uniform error at mostρ/2\\rho/2after adjusting constants\. There areO​\(1/ρ\)O\(1/\\rho\)grid points andO​\(1/ρ\)O\(1/\\rho\)possible quantized values at each point, proving the first claim\. For the second, approximate onlygg; the same approximation works for every difference\[g​\(p\)−g​\(h​\(x\)\)\]/2\[g\(p\)\-g\(h\(x\)\)\]/2\. ∎

We now combine the reduction and the cover to prove the rate theorem stated at the beginning of the subsection\.

###### Proof of[Theorem˜4\.10](https://arxiv.org/html/2607.28856#S4.Thmtheorem10)\.

Let𝒢~\\widetilde\{\\mathcal\{G\}\}be a uniformρ\\rho\-cover of𝒢mon​\(ℋ\)\\mathcal\{G\}\_\{\\mathrm\{mon\}\}\(\\mathcal\{H\}\)and run the offline algorithm of[Theorem˜3\.7](https://arxiv.org/html/2607.28856#S3.Thmtheorem7)on𝒢~\\widetilde\{\\mathcal\{G\}\}with rateη=1/20\\eta=1/20\. This gives distributional\(5​η,a¯m\)\(5\\eta,\\bar\{a\}\_\{m\}\)second\-order multicalibration for𝒢~\\widetilde\{\\mathcal\{G\}\}with

a¯m=2​log⁡\(12​\|𝒢~\|/δ\)\+2​m/N2η​m\.\\bar\{a\}\_\{m\}=\\frac\{2\\log\(12\|\\widetilde\{\\mathcal\{G\}\}\|/\\delta\)\+2m/N^\{2\}\}\{\\eta m\}\.By[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px3), the output satisfies distributional\(c¯m,a¯m′\)\(\\bar\{c\}\_\{m\},\\bar\{a\}\_\{m\}^\{\\prime\}\)second\-order multicalibration for𝒢mon​\(ℋ\)\\mathcal\{G\}\_\{\\mathrm\{mon\}\}\(\\mathcal\{H\}\)with

c¯m=10​η=12,a¯m′=a¯m\+\(10​η\+1\)​ρ=Λmη​m\+\(10​η\+1\)​ρ,\\bar\{c\}\_\{m\}=10\\eta=\\frac\{1\}\{2\},\\qquad\\bar\{a\}\_\{m\}^\{\\prime\}=\\bar\{a\}\_\{m\}\+\(10\\eta\+1\)\\rho=\\frac\{\\Lambda\_\{m\}\}\{\\eta m\}\+\(10\\eta\+1\)\\rho,where

Λm=2​log⁡\(12​\|𝒢~\|δ\)\+2​mN2\.\\Lambda\_\{m\}=2\\log\\\!\\left\(\\frac\{12\|\\widetilde\{\\mathcal\{G\}\}\|\}\{\\delta\}\\right\)\+\\frac\{2m\}\{N^\{2\}\}\.[Theorem˜4\.11](https://arxiv.org/html/2607.28856#S4.Thmtheorem11)therefore gives, simultaneously for all proper losses with11\-Lipschitz partial losses,

SwapAgn𝒟⁡\(ℓ,ℋ\)≤2​a¯m′\.\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)\\leq 2\\bar\{a\}\_\{m\}^\{\\prime\}\.Using[Section˜4\.3](https://arxiv.org/html/2607.28856#S4.SS3),

log⁡\|𝒢~\|≤\(N\+1\)​log⁡\|ℋ\|\+O​\(1ρ​log⁡1ρ\)\.\\log\|\\widetilde\{\\mathcal\{G\}\}\|\\leq\(N\+1\)\\log\|\\mathcal\{H\}\|\+O\\\!\\left\(\\frac\{1\}\{\\rho\}\\log\\frac\{1\}\{\\rho\}\\right\)\.Optimizing the grid size givesN≍\(m/log⁡\|ℋ\|\)1/3N\\asymp\(m/\\log\|\\mathcal\{H\}\|\)^\{1/3\}, contributingO~​\(\(log⁡\|ℋ\|/m\)2/3\)\\widetilde\{O\}\(\(\\log\|\\mathcal\{H\}\|/m\)^\{2/3\}\)\. Optimizing the transform\-cover radius givesρ≍m−1/2\\rho\\asymp m^\{\-1/2\}up to logarithmic factors, contributingO~​\(m−1/2\)\\widetilde\{O\}\(m^\{\-1/2\}\)\. The remaining confidence term contributesO​\(log⁡\(1/δ\)/m\)O\(\\log\(1/\\delta\)/m\)\. ∎

## 5Bounded Proper Losses

A bounded proper loss need not be Lipschitz \(equivalently, by[Section˜4](https://arxiv.org/html/2607.28856#S4), its negative Bayes risk need not be smooth\): its slope may jump, so[Section˜4](https://arxiv.org/html/2607.28856#S4)need not hold for any finite constant, and the single\-loss and finite\-family arguments of[Section˜4](https://arxiv.org/html/2607.28856#S4)do not apply\. Worse, even the trick that handled a continuum of Lipschitz losses – covering the loss family in the sup norm and running the finite\-family algorithm on the cover \([Theorem˜4\.10](https://arxiv.org/html/2607.28856#S4.Thmtheorem10)\) – breaks down here\. A threshold is a discontinuity, not a Lipschitz parameter: two V\-shaped losses with arbitrarily close thresholds disagree by a constant amount at every point strictly between the two thresholds, so the V\-shaped family admits no finite cover of this kind at all\. This is why passing from finitely many thresholds to every threshold in\[0,1\]\[0,1\]needs a genuinely new ingredient – a finite\-range assumption on the comparator classℋ\\mathcal\{H\}, in place of an approximation argument – and why this section has more moving parts than the Lipschitz and convex\-Lipschitz families treated elsewhere in the paper\.

We record the known V\-shaped basis decomposition and state our main bounded\-loss rate,[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2), in[Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)\.[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)proves the rate for any finite set of thresholds by applying the square\-root form of[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)to V\-shaped basis losses\.[Section˜5\.3](https://arxiv.org/html/2607.28856#S5.SS3)is where the new ingredient appears: it extends the finite\-threshold guarantee to*every*threshold in\[0,1\]\[0,1\], exactly and with no approximation, under the finite\-range assumption\.[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)integrates this over the representation of[Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)to complete the proof, and[Section˜5\.5](https://arxiv.org/html/2607.28856#S5.SS5)gives matching lower bounds\.

### 5\.1The V\-shaped decomposition and the main theorem

Forv∈\[0,1\]v\\in\[0,1\]andτ∈\[−1,1\]\\tau\\in\[\-1,1\], define

Thv,τ⁡\(u\)=\{1,u<v,τ,u=v,−1,u\>v,ℓv,τ​\(u,y\)=\(y−v\)​Thv,τ⁡\(u\)\.\\operatorname\{Th\}\_\{v,\\tau\}\(u\)=\\begin\{cases\}1,&u<v,\\\\ \\tau,&u=v,\\\\ \-1,&u\>v,\\end\{cases\}\\qquad\\ell\_\{v,\\tau\}\(u,y\)=\(y\-v\)\\operatorname\{Th\}\_\{v,\\tau\}\(u\)\.\(30\)The tie parameter is needed only to represent the value of a proper loss at a kink of its Bayes risk\. The canonical choiceτ=1\\tau=1recovers the convention2​𝟏​\{u≤v\}−12\\mathbf\{1\}\\\{u\\leq v\\\}\-1\.

###### Lemma 5\.1\(Measure representation of bounded proper losses\)\.

Letℓ\\ellbe proper and satisfy\|ℓ​\(p,y\)\|≤M\|\\ell\(p,y\)\|\\leq M\. Then there are constantsc,d∈ℝc,d\\in\\mathbb\{R\}, a finite nonnegative Borel measureμℓ\\mu\_\{\\ell\}on\[0,1\]\[0,1\], and tie parametersτv∈\[−1,1\]\\tau\_\{v\}\\in\[\-1,1\]for the atoms ofμℓ\\mu\_\{\\ell\}such that

ℓ​\(p,y\)=c\+d​y\+∫\[0,1\]ℓv,τv​\(p,y\)​𝑑μℓ​\(v\)\.\\ell\(p,y\)=c\+dy\+\\int\_\{\[0,1\]\}\\ell\_\{v,\\tau\_\{v\}\}\(p,y\)\\,d\\mu\_\{\\ell\}\(v\)\.\(31\)Moreover,

μℓ​\(\[0,1\]\)≤2​M\.\\mu\_\{\\ell\}\(\[0,1\]\)\\leq 2M\.The values ofτv\\tau\_\{v\}on the nonatomic part ofμℓ\\mu\_\{\\ell\}are irrelevant\. This V\-shaped threshold decomposition of bounded proper losses is due toKleinberg et al\. \([2023](https://arxiv.org/html/2607.28856#bib.bib23)\)andLi et al\. \([2022](https://arxiv.org/html/2607.28856#bib.bib24)\)\.

###### Theorem 5\.2\(Bounded proper losses\)\.

Suppose there is a finite setΓℋ⊆\[0,1\]\\Gamma\_\{\\mathcal\{H\}\}\\subseteq\[0,1\]withh​\(𝒳\)⊆Γℋh\(\\mathcal\{X\}\)\\subseteq\\Gamma\_\{\\mathcal\{H\}\}for everyh∈ℋh\\in\\mathcal\{H\}, and writeK=\|Γℋ\|K=\|\\Gamma\_\{\\mathcal\{H\}\}\|\. The localized algorithm based on[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)has a choice of prediction grid such that, with probability at least1−δ1\-\\delta, it is simultaneously swap\-agnostic for all proper losses bounded in\[−1,1\]\[\-1,1\]:

supℓ:\|ℓ\|≤1SwapRegT⁡\(ℓ,ℋ\)=O~​\(T​\(log⁡\|ℋ\|\+log⁡K\+log⁡1δ\)\)\.\\sup\_\{\\ell:\\ \|\\ell\|\\leq 1\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(\\sqrt\{T\\left\(\\log\|\\mathcal\{H\}\|\+\\log K\+\\log\\frac\{1\}\{\\delta\}\\right\)\}\\right\)\.The corresponding historical\-predictor conversion satisfies

supℓ:\|ℓ\|≤1SwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(log⁡\|ℋ\|\+log⁡K\+log⁡\(1/δ\)m\)\.\\sup\_\{\\ell:\\ \|\\ell\|\\leq 1\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(\\sqrt\{\\frac\{\\log\|\\mathcal\{H\}\|\+\\log K\+\\log\(1/\\delta\)\}\{m\}\}\\right\)\.

The proof of[Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)is given in[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)below, alongside the basis\-loss drift calculation; the proof of[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)itself is assembled in[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)\.

### 5\.2Controlling a finite set of thresholds

The proof starts with a drift inequality for a single V\-shaped basis loss\. This is the main piece of machinery that lets the localized algorithm handle nonsmooth losses\.

###### Lemma 5\.3\(V\-shaped basis\-loss drift\)\.

The lossℓv,τ\\ell\_\{v,\\tau\}is proper\. Forp,q∈\[0,1\]p,q\\in\[0,1\], define

gv,τ​\(p,q\)=12​\(Thv,τ⁡\(p\)−Thv,τ⁡\(q\)\)∈\[−1,1\]\.g\_\{v,\\tau\}\(p,q\)=\\frac\{1\}\{2\}\\left\(\\operatorname\{Th\}\_\{v,\\tau\}\(p\)\-\\operatorname\{Th\}\_\{v,\\tau\}\(q\)\\right\)\\in\[\-1,1\]\.Then, for everyy∈\{0,1\}y\\in\\\{0,1\\\},

ℓv,τ​\(p,y\)−ℓv,τ​\(q,y\)≤2​\(y−p\)​gv,τ​\(p,q\)−2​\|p−v\|​gv,τ​\(p,q\)2\.\\ell\_\{v,\\tau\}\(p,y\)\-\\ell\_\{v,\\tau\}\(q,y\)\\leq 2\(y\-p\)g\_\{v,\\tau\}\(p,q\)\-2\|p\-v\|g\_\{v,\\tau\}\(p,q\)^\{2\}\.\(32\)If neitherppnorqqequalsvv, equality holds\.

###### Proof of[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)\.

Under a true meanpp, the expected basis loss at predictionqqis\(p−v\)​Thv,τ⁡\(q\)\(p\-v\)\\operatorname\{Th\}\_\{v,\\tau\}\(q\)\. Ifp<vp<v, it is minimized by predictions belowvv; ifp\>vp\>v, it is minimized by predictions abovevv; and ifp=vp=v, every prediction is optimal\. Thus the loss is proper\.

The exact algebra gives

ℓv,τ​\(p,y\)−ℓv,τ​\(q,y\)\\displaystyle\\ell\_\{v,\\tau\}\(p,y\)\-\\ell\_\{v,\\tau\}\(q,y\)=2​\(y−v\)​gv,τ​\(p,q\)\\displaystyle=2\(y\-v\)g\_\{v,\\tau\}\(p,q\)=2​\(y−p\)​gv,τ​\(p,q\)\+2​\(p−v\)​gv,τ​\(p,q\)\.\\displaystyle=2\(y\-p\)g\_\{v,\\tau\}\(p,q\)\+2\(p\-v\)g\_\{v,\\tau\}\(p,q\)\.Ifp≠vp\\neq vandgv,τ​\(p,q\)≠0g\_\{v,\\tau\}\(p,q\)\\neq 0, the sign ofgv,τ​\(p,q\)g\_\{v,\\tau\}\(p,q\)is opposite to the sign ofp−vp\-v\. Ifp=vp=v, the product below is zero\. In either case,

\(p−v\)​gv,τ​\(p,q\)≤−\|p−v\|​\|gv,τ​\(p,q\)\|≤−\|p−v\|​gv,τ​\(p,q\)2\.\(p\-v\)g\_\{v,\\tau\}\(p,q\)\\leq\-\|p\-v\|\\,\|g\_\{v,\\tau\}\(p,q\)\|\\leq\-\|p\-v\|g\_\{v,\\tau\}\(p,q\)^\{2\}\.If neither prediction is tied atvv, then\|g\|∈\{0,1\}\|g\|\\in\\\{0,1\\\}and equality holds\. ∎

We can now prove the basis decomposition of[Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)above\.

###### Proof of[Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)\.

LetF=FℓF=F\_\{\\ell\}\. It is convex, and−Δℓ​\(p\)∈∂F​\(p\)\-\\Delta\_\{\\ell\}\(p\)\\in\\partial F\(p\)\. LetD2​FD^\{2\}Fbe the distributional second derivative, a finite nonnegative measure, and set

μℓ=12​D2​F\.\\mu\_\{\\ell\}=\\frac\{1\}\{2\}D^\{2\}F\.The standard one\-dimensional representation of a convex function gives

F​\(p\)=α\+β​p\+∫\[0,1\]\|p−v\|​𝑑μℓ​\(v\)\.F\(p\)=\\alpha\+\\beta p\+\\int\_\{\[0,1\]\}\|p\-v\|\\,d\\mu\_\{\\ell\}\(v\)\.\(33\)At every atomvv, chooseτv\\tau\_\{v\}so that the selected subgradient of the termμℓ​\(\{v\}\)​\|p−v\|\\mu\_\{\\ell\}\(\\\{v\\\}\)\|p\-v\|atp=vp=vequals−μℓ​\(\{v\}\)​τv\-\\mu\_\{\\ell\}\(\\\{v\\\}\)\\tau\_\{v\}\. This is possible because the subdifferential of\|p−v\|\|p\-v\|atvvis\[−1,1\]\[\-1,1\]\. With these choices, the selected subgradient of \([33](https://arxiv.org/html/2607.28856#S5.E33)\) is exactly−Δℓ​\(p\)\-\\Delta\_\{\\ell\}\(p\)\.

The proper loss generated by a convex potentialFFand selected subgradients​\(p\)∈∂F​\(p\)s\(p\)\\in\\partial F\(p\)is

ℓ​\(p,y\)=−F​\(p\)−\(y−p\)​s​\(p\)\.\\ell\(p,y\)=\-F\(p\)\-\(y\-p\)s\(p\)\.ForFv​\(p\)=\|p−v\|F\_\{v\}\(p\)=\|p\-v\|andsv​\(p\)=−Thv,τv⁡\(p\)s\_\{v\}\(p\)=\-\\operatorname\{Th\}\_\{v,\\tau\_\{v\}\}\(p\), this generated loss is exactlyℓv,τv​\(p,y\)\\ell\_\{v,\\tau\_\{v\}\}\(p,y\)\. The affine partα\+β​p\\alpha\+\\beta pcontributes the prediction\-independent term−α−β​y\-\\alpha\-\\beta y\. This proves \([31](https://arxiv.org/html/2607.28856#S5.E31)\)\.

Finally,F′=−ΔℓF^\{\\prime\}=\-\\Delta\_\{\\ell\}wherever the derivative exists\. Since\|ℓ​\(p,y\)\|≤M\|\\ell\(p,y\)\|\\leq M,\|Δℓ​\(p\)\|≤2​M\|\\Delta\_\{\\ell\}\(p\)\|\\leq 2M\. Therefore the total increase of the monotone derivativeF′F^\{\\prime\}is at most4​M4M, and

μℓ​\(\[0,1\]\)=12​D2​F​\(\[0,1\]\)≤2​M\.\\mu\_\{\\ell\}\(\[0,1\]\)=\\frac\{1\}\{2\}D^\{2\}F\(\[0,1\]\)\\leq 2M\.∎

The finite\-family theorem will sum the basis\-loss bounds over grid points\. The only extra estimate needed for that summation is the following harmonic inequality\.

###### Lemma 5\.5\(Harmonic drift–variance inequality\)\.

Fixv∈\[0,1\]v\\in\[0,1\], setai=\|γi−v\|a\_\{i\}=\|\\gamma\_\{i\}\-v\|, and letD0,…,DN≥0D\_\{0\},\\ldots,D\_\{N\}\\geq 0satisfy∑iDi≤T\\sum\_\{i\}D\_\{i\}\\leq T\. For everyR\>0R\>0,

∑i=0N\(R​Di−2​ai​Di\)≤R​2​T\+R24​N​HN,\\sum\_\{i=0\}^\{N\}\\left\(R\\sqrt\{D\_\{i\}\}\-2a\_\{i\}D\_\{i\}\\right\)\\leq R\\sqrt\{2T\}\+\\frac\{R^\{2\}\}\{4\}NH\_\{N\},\(34\)whereHN=∑k=1N1/kH\_\{N\}=\\sum\_\{k=1\}^\{N\}1/k\.

###### Proof of[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)\.

The summand is potentially large only when the grid pointγi\\gamma\_\{i\}lies close to the thresholdvv, because then the negative drift coefficientaia\_\{i\}is small\. We first isolate those nearby grid points\. There are at most two grid points withai<1/Na\_\{i\}<1/N, one on each side ofvv, and their contribution is at most

R​∑i:ai<1/NDi≤R​2​∑iDi≤R​2​TR\\sum\_\{i:a\_\{i\}<1/N\}\\sqrt\{D\_\{i\}\}\\leq R\\sqrt\{2\\sum\_\{i\}D\_\{i\}\}\\leq R\\sqrt\{2T\}by Cauchy–Schwarz\.

For every remaining point, the drift term controls large values ofDiD\_\{i\}\. Writingz=Dz=\\sqrt\{D\}, the expressionR​D−2​ai​D=R​z−2​ai​z2R\\sqrt\{D\}\-2a\_\{i\}D=Rz\-2a\_\{i\}z^\{2\}is a concave quadratic inz≥0z\\geq 0\. Its maximum occurs atz=R/\(4​ai\)z=R/\(4a\_\{i\}\), which gives

R​D−2​ai​D≤R28​ai\.R\\sqrt\{D\}\-2a\_\{i\}D\\leq\\frac\{R^\{2\}\}\{8a\_\{i\}\}\.
It remains to sum the reciprocal distances\. Away from the two nearest grid points, the grid spacing implies that on each side ofvvthe distances are at least1/N,2/N,…,N/N1/N,2/N,\\ldots,N/N, up to constants\. Hence the reciprocal distances are bounded by a harmonic sum:

∑i:ai≥1/N1ai≤2​N​HN\.\\sum\_\{i:a\_\{i\}\\geq 1/N\}\\frac\{1\}\{a\_\{i\}\}\\leq 2NH\_\{N\}\.Adding the nearby contribution and the far\-grid contribution proves the claim\. ∎

We next state the finite\-threshold online theorem that drives the bounded\-loss rate\. Let𝒱\\mathcal\{V\}be a finite set of pairs\(v,τ\)\(v,\\tau\)and define

gv,τ,h​\(x,p\)=12​\(Thv,τ⁡\(p\)−Thv,τ⁡\(h​\(x\)\)\)\.g\_\{v,\\tau,h\}\(x,p\)=\\frac\{1\}\{2\}\\left\(\\operatorname\{Th\}\_\{v,\\tau\}\(p\)\-\\operatorname\{Th\}\_\{v,\\tau\}\(h\(x\)\)\\right\)\.
###### Theorem 5\.6\(Finite V\-shaped family\)\.

Letℋ\\mathcal\{H\}and𝒱\\mathcal\{V\}be finite\. Run[Algorithm˜1](https://arxiv.org/html/2607.28856#alg1)on the localized test class

𝒢𝒱=\{\(x,p\)↦𝟏​\{p=γi\}​gv,τ,h​\(x,γi\):i=0,…,N,\(v,τ\)∈𝒱,h∈ℋ\}\\mathcal\{G\}\_\{\\mathcal\{V\}\}=\\left\\\{\(x,p\)\\mapsto\\mathbf\{1\}\\\{p=\\gamma\_\{i\}\\\}g\_\{v,\\tau,h\}\(x,\\gamma\_\{i\}\):i=0,\\ldots,N,\\ \(v,\\tau\)\\in\\mathcal\{V\},\\ h\\in\\mathcal\{H\}\\right\\\}using the square\-root form[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)\. There is a universal constantC′C^\{\\prime\}such that, with probability at least1−δ1\-\\delta, simultaneously for every\(v,τ\)∈𝒱\(v,\\tau\)\\in\\mathcal\{V\}and every swap comparator,

SwapRegT⁡\(ℓv,τ,ℋ\)\\displaystyle\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{v,\\tau\},\\mathcal\{H\}\)≤C′​ΛT​T\+C′​ΛT​N​HN\+C′​ΛT​\(N\+1\),\\displaystyle\\leq C^\{\\prime\}\\sqrt\{\\Lambda\_\{T\}T\}\+C^\{\\prime\}\\Lambda\_\{T\}NH\_\{N\}\+C^\{\\prime\}\\Lambda\_\{T\}\(N\+1\),\(35\)whereΛT=ΛT​\(𝒢𝒱,δ,N\)\\Lambda\_\{T\}=\\Lambda\_\{T\}\(\\mathcal\{G\}\_\{\\mathcal\{V\}\},\\delta,N\)is as in[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)\.

###### Proof of[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)\.

On the simultaneous second\-order event, fix\(v,τ\)\(v,\\tau\)and a swap rulehih\_\{i\}\. Put

Di=∑t∈Iigv,τ,hi​\(xt,γi\)2\.D\_\{i\}=\\sum\_\{t\\in I\_\{i\}\}g\_\{v,\\tau,h\_\{i\}\}\(x\_\{t\},\\gamma\_\{i\}\)^\{2\}\.For each bucketii, the test\(x,p\)↦𝟏​\{p=γi\}​gv,τ,hi​\(x,p\)\(x,p\)\\mapsto\\mathbf\{1\}\\\{p=\\gamma\_\{i\}\\\}g\_\{v,\\tau,h\_\{i\}\}\(x,p\)lies in𝒢𝒱\\mathcal\{G\}\_\{\\mathcal\{V\}\}, and its online bias is exactly∑t∈Ii\(yt−γi\)​gv,τ,hi​\(xt,γi\)\\sum\_\{t\\in I\_\{i\}\}\(y\_\{t\}\-\\gamma\_\{i\}\)g\_\{v,\\tau,h\_\{i\}\}\(x\_\{t\},\\gamma\_\{i\}\), sincept=γip\_\{t\}=\\gamma\_\{i\}fort∈Iit\\in I\_\{i\}\. By[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)and[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)applied to this test,

SwapRegT⁡\(ℓv,τ,ϕ\)\\displaystyle\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{v,\\tau\},\\phi\)≤∑i\(2​C​ΛT​Di−2​\|γi−v\|​Di\)\+2​C​ΛT​\(N\+1\),\\displaystyle\\leq\\sum\_\{i\}\\left\(2C\\sqrt\{\\Lambda\_\{T\}D\_\{i\}\}\-2\|\\gamma\_\{i\}\-v\|D\_\{i\}\\right\)\+2C\\Lambda\_\{T\}\(N\+1\),whereCCis the constant of[Section˜3\.2](https://arxiv.org/html/2607.28856#S3.SS2)\. Since the buckets are disjoint and\|g\|≤1\|g\|\\leq 1,∑iDi≤T\\sum\_\{i\}D\_\{i\}\\leq T\. Apply[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)withR=2​C​ΛTR=2C\\sqrt\{\\Lambda\_\{T\}\}to bound the sum by2​C​2​ΛT​T\+C2​ΛT​N​HN2C\\sqrt\{2\\Lambda\_\{T\}T\}\+C^\{2\}\\Lambda\_\{T\}NH\_\{N\}, which proves \([35](https://arxiv.org/html/2607.28856#S5.E35)\) for a suitable universalC′C^\{\\prime\}\. ∎

### 5\.3From finitely many thresholds to every threshold

[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)controls only the finitely many thresholds in𝒱\\mathcal\{V\}, while[Section˜5\.1](https://arxiv.org/html/2607.28856#S5.SS1)represents a bounded proper loss using a threshold measure supported on all of\[0,1\]\[0,1\]\. Bridging this gap by approximating the continuum of thresholds with a uniformρ\\rho\-cover of the*loss*ℓv,τ\\ell\_\{v,\\tau\}does not work: for anyv≠v′v\\neq v^\{\\prime\}, takingppstrictly between them givesThv,τ⁡\(p\)≠Thv′,τ′⁡\(p\)\\operatorname\{Th\}\_\{v,\\tau\}\(p\)\\neq\\operatorname\{Th\}\_\{v^\{\\prime\},\\tau^\{\\prime\}\}\(p\), sosupp,y\|ℓv,τ​\(p,y\)−ℓv′,τ′​\(p,y\)\|\\sup\_\{p,y\}\|\\ell\_\{v,\\tau\}\(p,y\)\-\\ell\_\{v^\{\\prime\},\\tau^\{\\prime\}\}\(p,y\)\|is bounded away from0however closevvandv′v^\{\\prime\}are – the threshold is a discontinuity invv, not a Lipschitz parameter, so the V\-shaped family admits no finiteρ\\rho\-cover in this sense for anyρ<2\\rho<2\. Instead, we use the following assumption to control every threshold*exactly*, with no approximation at all\.

Only in this section, assume that there is a finite setΓℋ⊆\[0,1\]\\Gamma\_\{\\mathcal\{H\}\}\\subseteq\[0,1\]withh​\(𝒳\)⊆Γℋh\(\\mathcal\{X\}\)\\subseteq\\Gamma\_\{\\mathcal\{H\}\}for everyh∈ℋh\\in\\mathcal\{H\}, and writeK=\|Γℋ\|K=\|\\Gamma\_\{\\mathcal\{H\}\}\|\. Unlike the prediction gridΓN\\Gamma\_\{N\}, which is a modeling choice of the learner,Γℋ\\Gamma\_\{\\mathcal\{H\}\}constrains the comparator class itself; it is natural for quantized score classes but excludes classes with a continuum of possible outputs\. Let𝒮N=ΓN∪Γℋ\\mathcal\{S\}\_\{N\}=\\Gamma\_\{N\}\\cup\\Gamma\_\{\\mathcal\{H\}\}\.

###### Corollary 5\.7\(Every threshold from a finite range\)\.

Under the finite\-range assumption above, run[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)with𝒱=𝒮N×\{−1,1\}\\mathcal\{V\}=\\mathcal\{S\}\_\{N\}\\times\\\{\-1,1\\\}, so\|𝒱\|≤2​\(N\+1\+K\)\|\\mathcal\{V\}\|\\leq 2\(N\+1\+K\)\. Then, on the resulting event of probability at least1−δ1\-\\delta, \([35](https://arxiv.org/html/2607.28856#S5.E35)\) \(with𝒱=𝒮N×\{−1,1\}\\mathcal\{V\}=\\mathcal\{S\}\_\{N\}\\times\\\{\-1,1\\\}in the definition ofΛT\\Lambda\_\{T\}\) holds simultaneously for*every*v∈\[0,1\]v\\in\[0,1\],τ∈\{−1,1\}\\tau\\in\\\{\-1,1\\\}, and every swap comparator – not merely the pairs already in𝒱\\mathcal\{V\}\.

###### Proof of[Section˜5\.3](https://arxiv.org/html/2607.28856#S5.SS3)\.

Fixv∈\[0,1\]v\\in\[0,1\],τ∈\{−1,1\}\\tau\\in\\\{\-1,1\\\}, and a swap ruleϕ\\phiwithhi=ϕ​\(γi\)h\_\{i\}=\\phi\(\\gamma\_\{i\}\)\. Letvrepv\_\{\\mathrm\{rep\}\}be the smallest element of𝒮N\\mathcal\{S\}\_\{N\}withvrep≥vv\_\{\\mathrm\{rep\}\}\\geq v\(takingvrep=1v\_\{\\mathrm\{rep\}\}=1ifv\>max⁡𝒮Nv\>\\max\\mathcal\{S\}\_\{N\}\), and letτrep=τ\\tau\_\{\\mathrm\{rep\}\}=\\tauifvrep=vv\_\{\\mathrm\{rep\}\}=vandτrep=−1\\tau\_\{\\mathrm\{rep\}\}=\-1otherwise\. For everyz∈𝒮Nz\\in\\mathcal\{S\}\_\{N\},Thvrep,τrep⁡\(z\)=Thv,τ⁡\(z\)\\operatorname\{Th\}\_\{v\_\{\\mathrm\{rep\}\},\\tau\_\{\\mathrm\{rep\}\}\}\(z\)=\\operatorname\{Th\}\_\{v,\\tau\}\(z\): ifvrep=vv\_\{\\mathrm\{rep\}\}=vthis is immediate, and otherwise everyz∈𝒮Nz\\in\\mathcal\{S\}\_\{N\}satisfiesz<vrepz<v\_\{\\mathrm\{rep\}\}orz\>vrepz\>v\_\{\\mathrm\{rep\}\}\(there is no point of𝒮N\\mathcal\{S\}\_\{N\}strictly betweenvvandvrepv\_\{\\mathrm\{rep\}\}, by minimality ofvrepv\_\{\\mathrm\{rep\}\}\), soz<vrep⇔z≤v⇔z<vz<v\_\{\\mathrm\{rep\}\}\\Leftrightarrow z\\leq v\\Leftrightarrow z<v\(usingz≠vz\\neq vsincevrep≠vv\_\{\\mathrm\{rep\}\}\\neq vmeansv∉𝒮Nv\\notin\\mathcal\{S\}\_\{N\}\) givesThvrep,−1⁡\(z\)=Thv,τ⁡\(z\)\\operatorname\{Th\}\_\{v\_\{\\mathrm\{rep\}\},\-1\}\(z\)=\\operatorname\{Th\}\_\{v,\\tau\}\(z\)in both branches\.

Sinceγi∈ΓN⊆𝒮N\\gamma\_\{i\}\\in\\Gamma\_\{N\}\\subseteq\\mathcal\{S\}\_\{N\}and, by the finite\-range assumption,hi​\(xt\)∈Γℋ⊆𝒮Nh\_\{i\}\(x\_\{t\}\)\\in\\Gamma\_\{\\mathcal\{H\}\}\\subseteq\\mathcal\{S\}\_\{N\}for everytt, this givesgv,τ,hi​\(xt,γi\)=gvrep,τrep,hi​\(xt,γi\)g\_\{v,\\tau,h\_\{i\}\}\(x\_\{t\},\\gamma\_\{i\}\)=g\_\{v\_\{\\mathrm\{rep\}\},\\tau\_\{\\mathrm\{rep\}\},h\_\{i\}\}\(x\_\{t\},\\gamma\_\{i\}\)for everytt, so the two tests have identical realized bias and mass on this transcript\. Since\(vrep,τrep\)∈𝒱\(v\_\{\\mathrm\{rep\}\},\\tau\_\{\\mathrm\{rep\}\}\)\\in\\mathcal\{V\}, the guarantee of[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)for\(vrep,τrep\)\(v\_\{\\mathrm\{rep\}\},\\tau\_\{\\mathrm\{rep\}\}\)therefore controlsDi=∑t∈Iigv,τ,hi​\(xt,γi\)2D\_\{i\}=\\sum\_\{t\\in I\_\{i\}\}g\_\{v,\\tau,h\_\{i\}\}\(x\_\{t\},\\gamma\_\{i\}\)^\{2\}exactly as in that proof\. The remainder of the argument is unchanged: the exact drift identity of[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)for the*true*vv\(notvrepv\_\{\\mathrm\{rep\}\}\) gives

SwapRegT⁡\(ℓv,τ,ϕ\)≤∑i\(2​C​ΛT​Di−2​\|γi−v\|​Di\)\+2​C​ΛT​\(N\+1\),\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{v,\\tau\},\\phi\)\\leq\\sum\_\{i\}\\left\(2C\\sqrt\{\\Lambda\_\{T\}D\_\{i\}\}\-2\|\\gamma\_\{i\}\-v\|D\_\{i\}\\right\)\+2C\\Lambda\_\{T\}\(N\+1\),and[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2)applies verbatim for this arbitraryv∈\[0,1\]v\\in\[0,1\]\(it was already stated for arbitraryv∈\[0,1\]v\\in\[0,1\], not merelyv∈𝒮Nv\\in\\mathcal\{S\}\_\{N\}\), proving \([35](https://arxiv.org/html/2607.28856#S5.E35)\) for everyv,τ,ϕv,\\tau,\\phisimultaneously on the same event\. ∎

### 5\.4Assembling the bound

Because bounded proper losses are positive mixtures of V\-shaped basis losses, the finite\-threshold theorem transfers linearly to finite mixtures\.

###### Corollary 5\.8\(Positive mixtures of V\-shaped basis losses from[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)\)\.

Suppose

ℓ​\(p,y\)=c\+d​y\+∑j=1Jwj​ℓvj,τj​\(p,y\),wj≥0,∑jwj≤W\.\\ell\(p,y\)=c\+dy\+\\sum\_\{j=1\}^\{J\}w\_\{j\}\\ell\_\{v\_\{j\},\\tau\_\{j\}\}\(p,y\),\\qquad w\_\{j\}\\geq 0,\\quad\\sum\_\{j\}w\_\{j\}\\leq W\.On the event of[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6),

SwapRegT⁡\(ℓ,ℋ\)≤W​\(C′​ΛT​T\+C′​ΛT​N​HN\+C′​ΛT​\(N\+1\)\)\.\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)\\leq W\\left\(C^\{\\prime\}\\sqrt\{\\Lambda\_\{T\}T\}\+C^\{\\prime\}\\Lambda\_\{T\}NH\_\{N\}\+C^\{\\prime\}\\Lambda\_\{T\}\(N\+1\)\\right\)\.The same conclusion holds for a positive Borel mixture if second\-order multicalibration is known simultaneously for every basis loss in its support\.

###### Proof of[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)\.

The termc\+d​yc\+dycancels from regret\. For each fixed swap rule, integrate the basis\-loss regret inequalities against the nonnegative weights and then take the supremum over swap rules\. ∎

A uniform cover of the*loss*family, rather than of the test class, is also a useful tool – we record it here because it will be applied to a genuinely continuously\-parameterized loss family in[Section˜6](https://arxiv.org/html/2607.28856#S6), unlike the V\-shaped family above\.

###### Proposition 5\.9\(Uniform loss\-cover transfer\)\.

Supposeℒ~\\widetilde\{\\mathcal\{L\}\}is a uniformρ\\rho\-cover of a loss familyℒ\\mathcal\{L\}\. If one predictor satisfies

supℓ~∈ℒ~SwapAgn𝒟⁡\(ℓ~,ℋ\)≤R,\\sup\_\{\\widetilde\{\\ell\}\\in\\widetilde\{\\mathcal\{L\}\}\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\widetilde\{\\ell\},\\mathcal\{H\}\)\\leq R,then

supℓ∈ℒSwapAgn𝒟⁡\(ℓ,ℋ\)≤R\+2​ρ\.\\sup\_\{\\ell\\in\\mathcal\{L\}\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)\\leq R\+2\\rho\.The corresponding online statement has additive error2​T​ρ2T\\rho\.

###### Proof of[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)\.

For any prediction and any comparator prediction, replacingℓ\\ellby a uniformlyρ\\rho\-close loss changes their loss difference by at most2​ρ2\\rhoper example\. ∎

We now combine the finite basis theorem, its full\-range extension, and the positive\-mixture transfer to prove the main bounded\-loss theorem\.

###### Proof of[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)\.

By[Section˜5\.3](https://arxiv.org/html/2607.28856#S5.SS3), running[Theorem˜5\.6](https://arxiv.org/html/2607.28856#S5.Thmtheorem6)on𝒱=𝒮N×\{−1,1\}\\mathcal\{V\}=\\mathcal\{S\}\_\{N\}\\times\\\{\-1,1\\\}\(of size at most2​\(N\+1\+K\)2\(N\+1\+K\)\) controlsSwapRegT⁡\(ℓv,τ,ℋ\)\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{v,\\tau\},\\mathcal\{H\}\)simultaneously for*every*v∈\[0,1\]v\\in\[0,1\],τ∈\{−1,1\}\\tau\\in\\\{\-1,1\\\}, and swap comparator, on one event of probability at least1−δ1\-\\delta\. By[Section˜5\.2](https://arxiv.org/html/2607.28856#S5.SS2), every proper loss bounded in\[−1,1\]\[\-1,1\]is, up to the prediction\-independent affine term \(which cancels from swap regret\), a positive Borel mixture with total mass at most22of basis lossesℓv,τ\\ell\_\{v,\\tau\}withτ∈\{−1,1\}\\tau\\in\\\{\-1,1\\\}\. Since second\-order multicalibration is known simultaneously for every basis loss in this support,[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)applies directly, with no approximation of the threshold continuum needed, giving the displayed uniform bound after optimizing the grid at the scaleN≍T/ΛTN\\asymp\\sqrt\{T/\\Lambda\_\{T\}\}and absorbing the harmonic andlog⁡K\\log Kfactors intoO~​\(⋅\)\\widetilde\{O\}\(\\cdot\)\.

For the offline statement, run the same localized signed test class in the historical\-predictor conversion\. The distributional square\-root bound[Section˜3\.3](https://arxiv.org/html/2607.28856#S3.SS3.SSS0.Px3), combined with the same exact\-threshold\-matching argument as in the proof of[Section˜5\.3](https://arxiv.org/html/2607.28856#S5.SS3)\(the finite\-range assumption places every realizedγi\\gamma\_\{i\}andhi​\(xt\)h\_\{i\}\(x\_\{t\}\)in𝒮N\\mathcal\{S\}\_\{N\}exactly as before\) and[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4), gives the same calculation withTTreplaced bymmand regret normalized bymm\. ∎

### 5\.5Lower bounds

The square\-root rates in[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)are also unavoidable for broad bounded proper loss families\. The lower bounds already hold for one V\-shaped proper loss\.

###### Lemma 5\.11\(V\-shaped online lower bound\)\.

Let1≤d≤T/21\\leq d\\leq T/2\. There are a domain and a classℋ\\mathcal\{H\}with\|ℋ\|=2d\|\\mathcal\{H\}\|=2^\{d\}such that every randomized learner admits a deterministic sequence with

𝔼​SwapRegT⁡\(ℓ∨,ℋ\)≥148​d​T=Ω​\(T​log⁡\|ℋ\|\),\\mathbb\{E\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{\\vee\},\\mathcal\{H\}\)\\geq\\frac\{1\}\{48\}\\sqrt\{dT\}=\\Omega\\\!\\left\(\\sqrt\{T\\log\|\\mathcal\{H\}\|\}\\right\),where

ℓ∨​\(p,y\)=\{y−12,p≤12,12−y,p\>12\.\\ell\_\{\\vee\}\(p,y\)=\\begin\{cases\}y\-\\frac\{1\}\{2\},&p\\leq\\frac\{1\}\{2\},\\\\ \\frac\{1\}\{2\}\-y,&p\>\\frac\{1\}\{2\}\.\\end\{cases\}

###### Proof of[Section˜5\.5](https://arxiv.org/html/2607.28856#S5.SS5)\.

Take𝒳=\[d\]\\mathcal\{X\}=\[d\]andℋ=\{0,1\}\[d\]\\mathcal\{H\}=\\\{0,1\\\}^\{\[d\]\}\. Partition the rounds intoddblocksIjI\_\{j\}of sizes differing by at most one and setxt=jx\_\{t\}=jonIjI\_\{j\}\. Draw independent fair labels\. For any predictable learner prediction, the conditional expected V\-shaped loss is zero\. Let

Sj=∑t∈Ij\(2​Yt−1\)\.S\_\{j\}=\\sum\_\{t\\in I\_\{j\}\}\(2Y\_\{t\}\-1\)\.The cumulative losses of predictions0and11on blockjjareSj/2S\_\{j\}/2and−Sj/2\-S\_\{j\}/2, respectively\. Hence the best hypothesis has loss−12​∑j\|Sj\|\-\\frac\{1\}\{2\}\\sum\_\{j\}\|S\_\{j\}\|, and swap regret dominates external regret\. For a length\-nnRademacher sumSS, Paley–Zygmund applied toS2S^\{2\}gives𝔼​\|S\|≥n/\(12​2\)\\mathbb\{E\}\|S\|\\geq\\sqrt\{n\}/\(12\\sqrt\{2\}\)\. Since every block has size at leastT/\(2​d\)T/\(2d\),

𝔼​SwapRegT⁡\(ℓ∨,ℋ\)≥12​∑j𝔼​\|Sj\|≥148​d​T\.\\mathbb\{E\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{\\vee\},\\mathcal\{H\}\)\\geq\\frac\{1\}\{2\}\\sum\_\{j\}\\mathbb\{E\}\|S\_\{j\}\|\\geq\\frac\{1\}\{48\}\\sqrt\{dT\}\.Averaging over labels gives a deterministic realization with the same expected regret over the learner’s randomness\. ∎

###### Lemma 5\.12\(V\-shaped offline lower bound\)\.

For every1≤d≤m1\\leq d\\leq mthere are a domain, a classℋ\\mathcal\{H\}with\|ℋ\|=2d\|\\mathcal\{H\}\|=2^\{d\}, and a family of distributions such that every possibly randomized learner based onmmi\.i\.d\. samples satisfies

sup𝒟𝔼​SwapAgn𝒟⁡\(ℓ∨,ℋ\)≥c​dm=Ω​\(log⁡\|ℋ\|m\)\.\\sup\_\{\\mathcal\{D\}\}\\mathbb\{E\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell\_\{\\vee\},\\mathcal\{H\}\)\\geq c\\sqrt\{\\frac\{d\}\{m\}\}=\\Omega\\\!\\left\(\\sqrt\{\\frac\{\\log\|\\mathcal\{H\}\|\}\{m\}\}\\right\)\.

###### Proof of[Section˜5\.5](https://arxiv.org/html/2607.28856#S5.SS5)\.

Take𝒳=\[d\]\\mathcal\{X\}=\[d\]andℋ=\{0,1\}\[d\]\\mathcal\{H\}=\\\{0,1\\\}^\{\[d\]\}\. Forσ∈\{−1,\+1\}d\\sigma\\in\\\{\-1,\+1\\\}^\{d\}, letXXbe uniform on\[d\]\[d\]and

Y∣X=j∼Ber⁡\(12\+α​σj\),α=c0​dm,Y\\mid X=j\\sim\\operatorname\{Ber\}\\left\(\\frac\{1\}\{2\}\+\\alpha\\sigma\_\{j\}\\right\),\\qquad\\alpha=c\_\{0\}\\sqrt\{\\frac\{d\}\{m\}\},withc0c\_\{0\}small enough thatα≤1/4\\alpha\\leq 1/4\. Underℓ∨\\ell\_\{\\vee\}, only the side of1/21/2on which the learner predicts matters, and choosing the wrong side on coordinatejjcosts conditional excess2​α2\\alpha\. Swap excess dominates external excess to the best binary hypothesis\. Assouad’s lemma gives a universal lower bound on the expected fraction of incorrectly recovered signs because the KL divergence between neighboring parameters is at mostC​m​α2/d=O​\(1\)Cm\\alpha^\{2\}/d=O\(1\)\. Therefore the expected excess is at leastc​αc\\alpha, proving the claim\. ∎

## 6Convex11\-Lipschitz Proper Losses

This section gives the second basis reduction\. The first main statement is structural: every proper loss with convex11\-Lipschitz partial losses is a positive mixture of clipped\-ReLU proper losses, up to an affine term depending only on the outcome[Section˜6](https://arxiv.org/html/2607.28856#S6)\. The second main statement is algorithmic: this decomposition yields simultaneous online swap regret and offline swap\-agnostic learning guarantees for the whole convex Lipschitz family[Theorem˜6\.2](https://arxiv.org/html/2607.28856#S6.Thmtheorem2)\. The proof proceeds through the primitive identity[Section˜6](https://arxiv.org/html/2607.28856#S6), the BV curvature lemma[Section˜6](https://arxiv.org/html/2607.28856#S6), the interval layer\-cake lemma[Section˜6](https://arxiv.org/html/2607.28856#S6), and the finite cover in[Section˜6](https://arxiv.org/html/2607.28856#S6)\.

For0≤a≤b≤10\\leq a\\leq b\\leq 1, define the clipped\-ReLU feature

φa,b​\(z\)=\(z−a\)\+−\(z−b\)\+,\\varphi\_\{a,b\}\(z\)=\(z\-a\)\_\{\+\}\-\(z\-b\)\_\{\+\},\(36\)and the convex potential

Fa,b​\(p\)=12​\(p−a\)\+2−12​\(p−b\)\+2\.F\_\{a,b\}\(p\)=\\frac\{1\}\{2\}\(p\-a\)\_\{\+\}^\{2\}\-\\frac\{1\}\{2\}\(p\-b\)\_\{\+\}^\{2\}\.\(37\)Then

Fa,b′​\(p\)=φa,b​\(p\),Fa,b′′​\(p\)=𝟏​\{a<p<b\}F\_\{a,b\}^\{\\prime\}\(p\)=\\varphi\_\{a,b\}\(p\),\\qquad F\_\{a,b\}^\{\\prime\\prime\}\(p\)=\\mathbf\{1\}\\\{a<p<b\\\}almost everywhere\. Define the corresponding proper loss

ℓa,b​\(p,y\)=−Fa,b​\(p\)−\(y−p\)​φa,b​\(p\)\.\\ell\_\{a,b\}\(p,y\)=\-F\_\{a,b\}\(p\)\-\(y\-p\)\\varphi\_\{a,b\}\(p\)\.\(38\)
###### Proposition 6\.1\(Clipped\-ReLU decomposition of convex Lipschitz proper losses\)\.

For each0≤a≤b≤10\\leq a\\leq b\\leq 1, the lossℓa,b\\ell\_\{a,b\}is proper\. Moreover, ifℓ\\ellis proper and both partial losses are convex and11\-Lipschitz, then there are constantsc,d∈ℝc,d\\in\\mathbb\{R\}and a finite nonnegative Borel measureνℓ\\nu\_\{\\ell\}onℐ=\{\(a,b\):0≤a≤b≤1\}\\mathcal\{I\}=\\\{\(a,b\):0\\leq a\\leq b\\leq 1\\\}such that

ℓ​\(p,y\)=c\+d​y\+∫ℐℓa,b​\(p,y\)​𝑑νℓ​\(a,b\),\\ell\(p,y\)=c\+dy\+\\int\_\{\\mathcal\{I\}\}\\ell\_\{a,b\}\(p,y\)\\,d\\nu\_\{\\ell\}\(a,b\),\(39\)andνℓ​\(ℐ\)≤5\\nu\_\{\\ell\}\(\\mathcal\{I\}\)\\leq 5\.

The proposition reduces the loss family to a continuum of interval\-indexed primitive losses\. To obtain an offline learner, we control a finite cover of the corresponding clipped\-ReLU event class and then integrate the primitive swap\-agnostic bounds using the positive measure in the decomposition\.

###### Theorem 6\.2\(Convex Lipschitz proper losses\)\.

Letℋ\\mathcal\{H\}be finite and letℒcvx\\mathcal\{L\}\_\{\\mathrm\{cvx\}\}denote the class of proper losses with convex11\-Lipschitz partial losses\. There are choices of prediction grid and finite cover for the online algorithm and for the offline historical\-predictor procedure such that, with probability at least1−δ1\-\\delta,

supℓ∈ℒcvxSwapRegT⁡\(ℓ,ℋ\)=O~​\(T1/3​\(log⁡\|ℋ\|\)2/3\+log⁡1δ\)online, and\\sup\_\{\\ell\\in\\mathcal\{L\}\_\{\\mathrm\{cvx\}\}\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(T^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\+\\log\\frac\{1\}\{\\delta\}\\right\)\\quad\\text\{online, and\}with probability at least1−δ1\-\\deltaover the training sample and training randomization,

supℓ∈ℒcvxSwapAgn𝒟⁡\(ℓ,ℋ\)=O~​\(\(log⁡\|ℋ\|m\)2/3\+log⁡\(1/δ\)m\)offline\.\\sup\_\{\\ell\\in\\mathcal\{L\}\_\{\\mathrm\{cvx\}\}\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(\\left\(\\frac\{\\log\|\\mathcal\{H\}\|\}\{m\}\\right\)^\{2/3\}\+\\frac\{\\log\(1/\\delta\)\}\{m\}\\right\)\\quad\\text\{offline\.\}

###### Lemma 6\.3\(Clipped\-ReLU primitive\)\.

The lossℓa,b\\ell\_\{a,b\}is proper\. For everyp,q∈\[0,1\]p,q\\in\[0,1\]andy∈\{0,1\}y\\in\\\{0,1\\\},

ℓa,b​\(p,y\)−ℓa,b​\(q,y\)\\displaystyle\\ell\_\{a,b\}\(p,y\)\-\\ell\_\{a,b\}\(q,y\)=\(y−p\)​\[φa,b​\(q\)−φa,b​\(p\)\]−DFa,b​\(p,q\)\\displaystyle=\(y\-p\)\[\\varphi\_\{a,b\}\(q\)\-\\varphi\_\{a,b\}\(p\)\]\-D\_\{F\_\{a,b\}\}\(p,q\)\(40\)≤\(y−p\)​\[φa,b​\(q\)−φa,b​\(p\)\]−12​\[φa,b​\(q\)−φa,b​\(p\)\]2\.\\displaystyle\\leq\(y\-p\)\[\\varphi\_\{a,b\}\(q\)\-\\varphi\_\{a,b\}\(p\)\]\-\\frac\{1\}\{2\}\[\\varphi\_\{a,b\}\(q\)\-\\varphi\_\{a,b\}\(p\)\]^\{2\}\.\(41\)

###### Proof of[Section˜6](https://arxiv.org/html/2607.28856#S6)\.

Under true meanpp, the expected loss at predictionqqis

−Fa,b​\(q\)−\(p−q\)​Fa,b′​\(q\)\.\-F\_\{a,b\}\(q\)\-\(p\-q\)F\_\{a,b\}^\{\\prime\}\(q\)\.Subtracting the truthful value−Fa,b​\(p\)\-F\_\{a,b\}\(p\)givesDFa,b​\(p,q\)≥0D\_\{F\_\{a,b\}\}\(p,q\)\\geq 0, proving properness and \([40](https://arxiv.org/html/2607.28856#S6.E40)\)\. SinceFa,b′=φa,bF\_\{a,b\}^\{\\prime\}=\\varphi\_\{a,b\}is11\-Lipschitz,[Section˜4](https://arxiv.org/html/2607.28856#S4)gives

DFa,b​\(p,q\)≥12​\[φa,b​\(p\)−φa,b​\(q\)\]2,D\_\{F\_\{a,b\}\}\(p,q\)\\geq\\frac\{1\}\{2\}\[\\varphi\_\{a,b\}\(p\)\-\\varphi\_\{a,b\}\(q\)\]^\{2\},which proves \([41](https://arxiv.org/html/2607.28856#S6.E41)\)\. ∎

We next prove a positive representation theorem\. The key fact is that convexity of both partial losses forces the curvature density of the negative Bayes risk to have bounded variation\.

###### Lemma 6\.4\(Curvature of a convex Lipschitz proper loss\)\.

Supposeℓ\\ellis proper and both partial losses are convex and11\-Lipschitz\. ThenFℓF\_\{\\ell\}is continuously differentiable,Fℓ′F\_\{\\ell\}^\{\\prime\}is22\-Lipschitz, and there is a nonnegative functionwℓ∈B​V​\(\[0,1\]\)w\_\{\\ell\}\\in BV\(\[0,1\]\)such that

Fℓ′′​\(p\)=wℓ​\(p\)F\_\{\\ell\}^\{\\prime\\prime\}\(p\)=w\_\{\\ell\}\(p\)almost everywhere and

‖wℓ‖∞≤2,TV⁡\(wℓ\)≤6\.\\\|w\_\{\\ell\}\\\|\_\{\\infty\}\\leq 2,\\qquad\\operatorname\{TV\}\(w\_\{\\ell\}\)\\leq 6\.\(42\)

###### Proof of[Section˜6](https://arxiv.org/html/2607.28856#S6)\.

By the proof of[Section˜4](https://arxiv.org/html/2607.28856#S4)withL=1L=1,Fℓ′F\_\{\\ell\}^\{\\prime\}exists and is22\-Lipschitz\. Hence it is absolutely continuous, with a derivativewℓ=Fℓ′′w\_\{\\ell\}=F\_\{\\ell\}^\{\\prime\\prime\}almost everywhere\. Convexity ofFℓF\_\{\\ell\}and the Lipschitz bound give0≤wℓ≤20\\leq w\_\{\\ell\}\\leq 2\.

The canonical formulas for a proper loss generated byFℓF\_\{\\ell\}are

ℓ0​\(p\)=−Fℓ​\(p\)\+p​Fℓ′​\(p\),ℓ1​\(p\)=−Fℓ​\(p\)−\(1−p\)​Fℓ′​\(p\)\.\\ell\_\{0\}\(p\)=\-F\_\{\\ell\}\(p\)\+pF\_\{\\ell\}^\{\\prime\}\(p\),\\qquad\\ell\_\{1\}\(p\)=\-F\_\{\\ell\}\(p\)\-\(1\-p\)F\_\{\\ell\}^\{\\prime\}\(p\)\.Differentiating almost everywhere gives

ℓ0′​\(p\)=p​wℓ​\(p\),ℓ1′​\(p\)=−\(1−p\)​wℓ​\(p\)\.\\ell\_\{0\}^\{\\prime\}\(p\)=pw\_\{\\ell\}\(p\),\\qquad\\ell\_\{1\}^\{\\prime\}\(p\)=\-\(1\-p\)w\_\{\\ell\}\(p\)\.Sinceℓ0\\ell\_\{0\}is convex,u​\(p\)=p​wℓ​\(p\)u\(p\)=pw\_\{\\ell\}\(p\)has a nondecreasing representative; sinceℓ1\\ell\_\{1\}is convex,v​\(p\)=\(1−p\)​wℓ​\(p\)v\(p\)=\(1\-p\)w\_\{\\ell\}\(p\)has a nonincreasing representative\. The11\-Lipschitz assumption implies0≤u,v≤10\\leq u,v\\leq 1\.

On\[0,1/2\]\[0,1/2\],

wℓ​\(p\)=v​\(p\)1−p\.w\_\{\\ell\}\(p\)=\\frac\{v\(p\)\}\{1\-p\}\.The BV product inequality yields

TV\[0,1/2\]⁡\(wℓ\)≤‖11−p‖∞​TV⁡\(v\)\+‖v‖∞​TV⁡\(11−p\)≤2\+1=3\.\\operatorname\{TV\}\_\{\[0,1/2\]\}\(w\_\{\\ell\}\)\\leq\\left\\\|\\frac\{1\}\{1\-p\}\\right\\\|\_\{\\infty\}\\operatorname\{TV\}\(v\)\+\\\|v\\\|\_\{\\infty\}\\operatorname\{TV\}\\\!\\left\(\\frac\{1\}\{1\-p\}\\right\)\\leq 2\+1=3\.On\[1/2,1\]\[1/2,1\], writewℓ​\(p\)=u​\(p\)/pw\_\{\\ell\}\(p\)=u\(p\)/pto obtain the same bound\. The one\-sided limits at1/21/2agree: monotonicity ofuugivesw​\(1/2−\)≤w​\(1/2\+\)w\(1/2\-\)\\leq w\(1/2\+\), whereas monotonicity ofvvgives the reverse inequality\. Hence no additional jump occurs andTV⁡\(wℓ\)≤6\\operatorname\{TV\}\(w\_\{\\ell\}\)\\leq 6\. ∎

###### Lemma 6\.5\(Positive interval layer cake\)\.

Letw:\[0,1\]→\[0,∞\)w:\[0,1\]\\to\[0,\\infty\)be of bounded variation\. There is a finite nonnegative Borel measureν\\nuon

ℐ=\{\(a,b\):0≤a≤b≤1\}\\mathcal\{I\}=\\\{\(a,b\):0\\leq a\\leq b\\leq 1\\\}such that

w​\(z\)=∫ℐ𝟏​\{a<z<b\}​𝑑ν​\(a,b\)w\(z\)=\\int\_\{\\mathcal\{I\}\}\\mathbf\{1\}\\\{a<z<b\\\}\\,d\\nu\(a,b\)\(43\)for almost everyzz, and

ν​\(ℐ\)≤‖w‖∞\+12​TV⁡\(w\)\.\\nu\(\\mathcal\{I\}\)\\leq\\\|w\\\|\_\{\\infty\}\+\\frac\{1\}\{2\}\\operatorname\{TV\}\(w\)\.\(44\)

###### Proof of[Section˜6](https://arxiv.org/html/2607.28856#S6)\.

Fort≥0t\\geq 0, letEt=\{z:w​\(z\)\>t\}E\_\{t\}=\\\{z:w\(z\)\>t\\\}\. For almost everytt, the one\-dimensional finite\-perimeter setEtE\_\{t\}is, up to a null set, a finite union of disjoint intervals

Et=⋃j=1m​\(t\)\(at,j,bt,j\)\.E\_\{t\}=\\bigcup\_\{j=1\}^\{m\(t\)\}\(a\_\{t,j\},b\_\{t,j\}\)\.The one\-dimensional coarea formula gives

TV⁡\(w\)=∫0∞Per⁡\(Et\)​𝑑t\.\\operatorname\{TV\}\(w\)=\\int\_\{0\}^\{\\infty\}\\operatorname\{Per\}\(E\_\{t\}\)\\,dt\.A subset of\[0,1\]\[0,1\]withmminterval components satisfiesm≤1\+Per⁡\(Et\)/2m\\leq 1\+\\operatorname\{Per\}\(E\_\{t\}\)/2\. Defineν\\nuby

∫ℐΨ​\(a,b\)​𝑑ν​\(a,b\)=∫0‖w‖∞∑j=1m​\(t\)Ψ​\(at,j,bt,j\)​d​t\\int\_\{\\mathcal\{I\}\}\\Psi\(a,b\)\\,d\\nu\(a,b\)=\\int\_\{0\}^\{\\\|w\\\|\_\{\\infty\}\}\\sum\_\{j=1\}^\{m\(t\)\}\\Psi\(a\_\{t,j\},b\_\{t,j\}\)\\,dtfor every nonnegative BorelΨ\\Psi\. The scalar layer\-cake identity yields

∫ℐ𝟏​\{a<z<b\}​𝑑ν​\(a,b\)=∫0‖w‖∞𝟏​\{w​\(z\)\>t\}​𝑑t=w​\(z\)\\int\_\{\\mathcal\{I\}\}\\mathbf\{1\}\\\{a<z<b\\\}\\,d\\nu\(a,b\)=\\int\_\{0\}^\{\\\|w\\\|\_\{\\infty\}\}\\mathbf\{1\}\\\{w\(z\)\>t\\\}\\,dt=w\(z\)for almost everyzz\. Finally,

ν​\(ℐ\)\\displaystyle\\nu\(\\mathcal\{I\}\)=∫0‖w‖∞m​\(t\)​𝑑t\\displaystyle=\\int\_\{0\}^\{\\\|w\\\|\_\{\\infty\}\}m\(t\)\\,dt≤‖w‖∞\+12​∫0∞Per⁡\(Et\)​𝑑t,\\displaystyle\\leq\\\|w\\\|\_\{\\infty\}\+\\frac\{1\}\{2\}\\int\_\{0\}^\{\\infty\}\\operatorname\{Per\}\(E\_\{t\}\)\\,dt,which is \([44](https://arxiv.org/html/2607.28856#S6.E44)\)\. ∎

###### Proof of[Section˜6](https://arxiv.org/html/2607.28856#S6)\.

[Section˜6](https://arxiv.org/html/2607.28856#S6)proves that eachℓa,b\\ell\_\{a,b\}is proper\. Apply[Section˜6](https://arxiv.org/html/2607.28856#S6)to the curvature densitywℓw\_\{\\ell\}from[Section˜6](https://arxiv.org/html/2607.28856#S6)\. There is a nonnegative measureνℓ\\nu\_\{\\ell\}with

wℓ​\(z\)=∫ℐ𝟏​\{a<z<b\}​𝑑νℓ​\(a,b\)w\_\{\\ell\}\(z\)=\\int\_\{\\mathcal\{I\}\}\\mathbf\{1\}\\\{a<z<b\\\}\\,d\\nu\_\{\\ell\}\(a,b\)and

νℓ​\(ℐ\)≤2\+12⋅6=5\.\\nu\_\{\\ell\}\(\\mathcal\{I\}\)\\leq 2\+\\frac\{1\}\{2\}\\cdot 6=5\.Define

F~​\(p\)=Fℓ​\(0\)\+Fℓ′​\(0\)​p\+∫ℐFa,b​\(p\)​𝑑νℓ​\(a,b\)\.\\widetilde\{F\}\(p\)=F\_\{\\ell\}\(0\)\+F\_\{\\ell\}^\{\\prime\}\(0\)p\+\\int\_\{\\mathcal\{I\}\}F\_\{a,b\}\(p\)\\,d\\nu\_\{\\ell\}\(a,b\)\.ThenF~′′=wℓ=Fℓ′′\\widetilde\{F\}^\{\\prime\\prime\}=w\_\{\\ell\}=F\_\{\\ell\}^\{\\prime\\prime\}almost everywhere, andF~​\(0\)=Fℓ​\(0\)\\widetilde\{F\}\(0\)=F\_\{\\ell\}\(0\),F~′​\(0\)=Fℓ′​\(0\)\\widetilde\{F\}^\{\\prime\}\(0\)=F\_\{\\ell\}^\{\\prime\}\(0\)\. Absolute continuity therefore impliesF~=Fℓ\\widetilde\{F\}=F\_\{\\ell\}\.

The proper loss generated byFℓF\_\{\\ell\}is

ℓ​\(p,y\)=−Fℓ​\(p\)−\(y−p\)​Fℓ′​\(p\)\.\\ell\(p,y\)=\-F\_\{\\ell\}\(p\)\-\(y\-p\)F\_\{\\ell\}^\{\\prime\}\(p\)\.Substituting the representation ofFℓF\_\{\\ell\}, the affine potential contributes only an outcome\-dependent affine term, while eachFa,bF\_\{a,b\}contributesℓa,b\\ell\_\{a,b\}\. This proves \([39](https://arxiv.org/html/2607.28856#S6.E39)\)\. ∎

###### Proposition 6\.6\(Clipped\-ReLU cover\)\.

For alla,b,a′,b′a,b,a^\{\\prime\},b^\{\\prime\}andz∈\[0,1\]z\\in\[0,1\],

\|φa,b​\(z\)−φa′,b′​\(z\)\|≤\|a−a′\|\+\|b−b′\|\.\|\\varphi\_\{a,b\}\(z\)\-\\varphi\_\{a^\{\\prime\},b^\{\\prime\}\}\(z\)\|\\leq\|a\-a^\{\\prime\}\|\+\|b\-b^\{\\prime\}\|\.Moreover,

supp,y\|ℓa,b​\(p,y\)−ℓa′,b′​\(p,y\)\|≤2​\(\|a−a′\|\+\|b−b′\|\)\.\\sup\_\{p,y\}\|\\ell\_\{a,b\}\(p,y\)\-\\ell\_\{a^\{\\prime\},b^\{\\prime\}\}\(p,y\)\|\\leq 2\(\|a\-a^\{\\prime\}\|\+\|b\-b^\{\\prime\}\|\)\.Consequently, for a universal constantC1C\_\{1\}, the primitive parameter triangleℐ\\mathcal\{I\}admits aρ\\rho\-net of at most\(C1/ρ\)2\(C\_\{1\}/\\rho\)^\{2\}points, uniform both inφa,b\\varphi\_\{a,b\}and inℓa,b\\ell\_\{a,b\}\.

###### Proof of[Section˜6](https://arxiv.org/html/2607.28856#S6)\.

The mapa↦\(z−a\)\+a\\mapsto\(z\-a\)\_\{\+\}is11\-Lipschitz, and similarly forbb\. Gridaaandbbat spacing proportional toρ\\rho; the loss\-cover bound follows from the displayed Lipschitz bound onφa,b\\varphi\_\{a,b\}and the fact thatFa,b​\(p\)=∫0pφa,b​\(u\)​𝑑uF\_\{a,b\}\(p\)=\\int\_\{0\}^\{p\}\\varphi\_\{a,b\}\(u\)\\,du\. ∎

###### Proof of[Theorem˜6\.2](https://arxiv.org/html/2607.28856#S6.Thmtheorem2)\.

Take aρ\\rho\-net of the primitive parameter triangleℐ\\mathcal\{I\}\. Everyℓa,b\\ell\_\{a,b\}is a11\-Lipschitz proper loss: by \([38](https://arxiv.org/html/2607.28856#S6.E38)\),ℓa,b​\(p,0\)=−Fa,b​\(p\)\+p​φa,b​\(p\)\\ell\_\{a,b\}\(p,0\)=\-F\_\{a,b\}\(p\)\+p\\varphi\_\{a,b\}\(p\)andℓa,b​\(p,1\)=−Fa,b​\(p\)−\(1−p\)​φa,b​\(p\)\\ell\_\{a,b\}\(p,1\)=\-F\_\{a,b\}\(p\)\-\(1\-p\)\\varphi\_\{a,b\}\(p\), and differentiating usingFa,b′=φa,bF\_\{a,b\}^\{\\prime\}=\\varphi\_\{a,b\}andφa,b′=𝟏​\{a<z<b\}\\varphi\_\{a,b\}^\{\\prime\}=\\mathbf\{1\}\\\{a<z<b\\\}\(a\.e\.\) gives partial\-loss derivativesp​𝟏​\{a<p<b\}p\\mathbf\{1\}\\\{a<p<b\\\}and−\(1−p\)​𝟏​\{a<p<b\}\-\(1\-p\)\\mathbf\{1\}\\\{a<p<b\\\}, both bounded by11in absolute value\. By[Section˜6](https://arxiv.org/html/2607.28856#S6), the net has cardinality at most\(C1/ρ\)2\(C\_\{1\}/\\rho\)^\{2\}\.

*Online statement\.*Apply[Theorem˜4\.9](https://arxiv.org/html/2607.28856#S4.Thmtheorem9)withL=1L=1to this finite primitive family, giving, with probability at least1−δ1\-\\delta,

sup\(a,b\)​in the netSwapRegT⁡\(ℓa,b,ℋ\)=O~​\(T1/3​\(log⁡\|ℋ\|\)2/3\+log⁡1δ\)\.\\sup\_\{\(a,b\)\\text\{ in the net\}\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{a,b\},\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(T^\{1/3\}\(\\log\|\\mathcal\{H\}\|\)^\{2/3\}\+\\log\\frac\{1\}\{\\delta\}\\right\)\.The online loss\-cover transfer in[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)extends this bound from the finite net to the full triangleℐ\\mathcal\{I\}at an additive cost of2​T​ρ2T\\rhoswap regret\. Choosingρ≍T−2/3\\rho\\asymp T^\{\-2/3\}makes this cost, and the resulting growth of the net cardinality, lower order\. Since the termc\+d​yc\+dycancels from regret, and swap regret is linear in the loss, integrate the resulting uniform primitive bound against the nonnegative measure of[Section˜6](https://arxiv.org/html/2607.28856#S6): for every swap ruleϕ\\phiand everyℓ∈ℒcvx\\ell\\in\\mathcal\{L\}\_\{\\mathrm\{cvx\}\}with representing measureνℓ\\nu\_\{\\ell\},

SwapRegT⁡\(ℓ,ϕ\)=∫ℐSwapRegT⁡\(ℓa,b,ϕ\)​𝑑νℓ​\(a,b\)≤νℓ​\(ℐ\)​sup\(a,b\)∈ℐSwapRegT⁡\(ℓa,b,ℋ\),\\operatorname\{SwapReg\}\_\{T\}\(\\ell,\\phi\)=\\int\_\{\\mathcal\{I\}\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{a,b\},\\phi\)\\,d\\nu\_\{\\ell\}\(a,b\)\\leq\\nu\_\{\\ell\}\(\\mathcal\{I\}\)\\sup\_\{\(a,b\)\\in\\mathcal\{I\}\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell\_\{a,b\},\\mathcal\{H\}\),uniformly inϕ\\phi, andνℓ​\(ℐ\)≤5\\nu\_\{\\ell\}\(\\mathcal\{I\}\)\\leq 5\. This proves the online rate\.

*Offline statement\.*Apply[Theorem˜4\.9](https://arxiv.org/html/2607.28856#S4.Thmtheorem9)withL=1L=1to the same finite primitive net, giving

sup\(a,b\)​in the netSwapAgn𝒟⁡\(ℓa,b,ℋ\)=O~​\(\(log⁡\|ℋ\|m\)2/3\+log⁡\(1/δ\)m\)\.\\sup\_\{\(a,b\)\\text\{ in the net\}\}\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}\(\\ell\_\{a,b\},\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(\\left\(\\frac\{\\log\|\\mathcal\{H\}\|\}\{m\}\\right\)^\{2/3\}\+\\frac\{\\log\(1/\\delta\)\}\{m\}\\right\)\.The offline loss\-cover transfer in[Section˜5\.4](https://arxiv.org/html/2607.28856#S5.SS4)extends this bound from the finite net to the full triangleℐ\\mathcal\{I\}at an additive cost of2​ρ2\\rho\. Choosingρ=m−1\\rho=m^\{\-1\}makes this approximation lower order\. As above, integrate the resulting uniform primitive bound against the nonnegative measure of[Section˜6](https://arxiv.org/html/2607.28856#S6), whose total mass is at most five, to obtain the displayed offline rate\. ∎

## 7Beyond Proper Losses

We now evaluate the learner after best\-response postprocessing but leave the benchmark unchanged\. This asymmetry is essential: the learner incurs the loss of a best response to its probability forecast, while the comparator incurs the original loss of its chosen action\. We give an exact reduction from this benchmark to ordinary swap\-agnostic learning of a single proper loss\.[Section˜7](https://arxiv.org/html/2607.28856#S7)constructs, for any bounded binary loss, a*canonical properization*: a proper loss with redundant messages whose truthful message exactly recovers the learner’s postprocessed loss and whose comparator messages dominate every original action\. The price of this exact reduction is that the induced proper loss uses a message space with redundant messages, and the relevant comparator complexity is that of the loss slopes after composition withℋ\\mathcal\{H\}\.[Theorem˜7\.4](https://arxiv.org/html/2607.28856#S7.Thmtheorem4)uses the construction to transfer swap\-regret guarantees for the canonical proper loss back to the original loss, and[Theorem˜7\.6](https://arxiv.org/html/2607.28856#S7.Thmtheorem6)extends the transfer to families of losses\.

For a loss on an action space𝒜\\mathcal\{A\}and a classℋ⊆\{h:𝒳→𝒜\}\\mathcal\{H\}\\subseteq\\\{h:\\mathcal\{X\}\\to\\mathcal\{A\}\\\}, we write

SwapRegTbr⁡\(ℓ,ℋ\):=supϕ:𝒫→ℋ∑t=1T\[ℓ​\(kℓ​\(pt\),yt\)−ℓ​\(ϕ​\(pt\)​\(xt\),yt\)\],\\displaystyle\\operatorname\{SwapReg\}\_\{T\}^\{\\mathrm\{br\}\}\(\\ell,\\mathcal\{H\}\)=\\sup\_\{\\phi:\\mathcal\{P\}\\to\\mathcal\{H\}\}\\sum\_\{t=1\}^\{T\}\\left\[\\ell\(k\_\{\\ell\}\(p\_\{t\}\),y\_\{t\}\)\-\\ell\(\\phi\(p\_\{t\}\)\(x\_\{t\}\),y\_\{t\}\)\\right\],\(45\)where𝒫\\mathcal\{P\}is the set of prediction values used by the learner\. The distributional analogue, denotedSwapAgn𝒟br⁡\(ℓ,ℋ\)\\operatorname\{SwapAgn\}\_\{\\mathcal\{D\}\}^\{\\mathrm\{br\}\}\(\\ell,\\mathcal\{H\}\), is defined in the same way with expectation under\(X,Y\)∼𝒟\(X,Y\)\\sim\\mathcal\{D\}and with the learner playingkℓ​\(p​\(X\)\)k\_\{\\ell\}\(p\(X\)\)\.

###### Definition 7\.1\(Proper loss with redundant messages\)\.

Letℛ\\mathcal\{R\}be a message space and letλ:ℛ×\{0,1\}→\[0,1\]\\lambda:\\mathcal\{R\}\\times\\\{0,1\\\}\\to\[0,1\]\. We say thatλ\\lambdais proper with truth embeddingτ:\[0,1\]→ℛ\\tau:\[0,1\]\\to\\mathcal\{R\}if, for everyp∈\[0,1\]p\\in\[0,1\]and everyr∈ℛr\\in\\mathcal\{R\},

𝔼Y∼Ber⁡\(p\)​\[λ​\(τ​\(p\),Y\)\]≤𝔼Y∼Ber⁡\(p\)​\[λ​\(r,Y\)\]\.\\mathbb\{E\}\_\{Y\\sim\\operatorname\{Ber\}\(p\)\}\[\\lambda\(\\tau\(p\),Y\)\]\\leq\\mathbb\{E\}\_\{Y\\sim\\operatorname\{Ber\}\(p\)\}\[\\lambda\(r,Y\)\]\.Ordinary proper binary losses correspond toℛ=\[0,1\]\\mathcal\{R\}=\[0,1\]andτ​\(p\)=p\\tau\(p\)=p\.

Letℓ:𝒜×\{0,1\}→\[0,1\]\\ell:\\mathcal\{A\}\\times\\\{0,1\\\}\\to\[0,1\]be a bounded binary loss on an action space𝒜\\mathcal\{A\}\. Write

Lpℓ​\(a\)\\displaystyle L\_\{p\}^\{\\ell\}\(a\)=\(1−p\)​ℓ​\(a,0\)\+p​ℓ​\(a,1\),\\displaystyle=\(1\-p\)\\ell\(a,0\)\+p\\ell\(a,1\),\(46\)Δℓ​\(a\)\\displaystyle\\Delta\_\{\\ell\}\(a\)=ℓ​\(a,1\)−ℓ​\(a,0\),\\displaystyle=\\ell\(a,1\)\-\\ell\(a,0\),\(47\)sℓ​\(a\)\\displaystyle s\_\{\\ell\}\(a\)=−Δℓ​\(a\)\.\\displaystyle=\-\\Delta\_\{\\ell\}\(a\)\.\(48\)Assume that a best response is attained for everypp:

kℓ​\(p\)∈arg​mina∈𝒜⁡Lpℓ​\(a\)\.k\_\{\\ell\}\(p\)\\in\\operatorname\*\{arg\\,min\}\_\{a\\in\\mathcal\{A\}\}L\_\{p\}^\{\\ell\}\(a\)\.\(49\)
###### Lemma 7\.2\(Canonical properization of a bounded binary loss\)\.

Letℓ:𝒜×\{0,1\}→\[0,1\]\\ell:\\mathcal\{A\}\\times\\\{0,1\\\}\\to\[0,1\]satisfy \([49](https://arxiv.org/html/2607.28856#S7.E49)\)\. Define its negative Bayes envelope

Fℓ​\(p\)=−mina∈𝒜⁡Lpℓ​\(a\)\.F\_\{\\ell\}\(p\)=\-\\min\_\{a\\in\\mathcal\{A\}\}L\_\{p\}^\{\\ell\}\(a\)\.\(50\)Then

Fℓ​\(p\)=supa∈𝒜\{p​sℓ​\(a\)−ℓ​\(a,0\)\}\.F\_\{\\ell\}\(p\)=\\sup\_\{a\\in\\mathcal\{A\}\}\\\{p\\,s\_\{\\ell\}\(a\)\-\\ell\(a,0\)\\\}\.\(51\)
Let

Fℓ∗​\(s\)=supq∈\[0,1\]\{q​s−Fℓ​\(q\)\},𝒮ℓ=\{sℓ​\(a\):a∈𝒜\},F\_\{\\ell\}^\{\*\}\(s\)=\\sup\_\{q\\in\[0,1\]\}\\\{qs\-F\_\{\\ell\}\(q\)\\\},\\qquad\\mathcal\{S\}\_\{\\ell\}=\\\{s\_\{\\ell\}\(a\):a\\in\\mathcal\{A\}\\\},and, fors∈𝒮ℓs\\in\\mathcal\{S\}\_\{\\ell\}, let

Qℓ​\(s\)=arg​maxq∈\[0,1\]⁡\{q​s−Fℓ​\(q\)\}\.Q\_\{\\ell\}\(s\)=\\operatorname\*\{arg\\,max\}\_\{q\\in\[0,1\]\}\\\{qs\-F\_\{\\ell\}\(q\)\\\}\.The setQℓ​\(s\)Q\_\{\\ell\}\(s\)is nonempty\. Define

ℛℓ=\{\(q,s\):s∈𝒮ℓ,q∈Qℓ​\(s\)\},λℓ​\(\(q,s\),y\)=Fℓ∗​\(s\)−s​y\.\\mathcal\{R\}\_\{\\ell\}=\\\{\(q,s\):s\\in\\mathcal\{S\}\_\{\\ell\},\\ q\\in Q\_\{\\ell\}\(s\)\\\},\\qquad\\lambda\_\{\\ell\}\(\(q,s\),y\)=F\_\{\\ell\}^\{\*\}\(s\)\-sy\.\(52\)For everypp, put

sℓ,p=sℓ​\(kℓ​\(p\)\),τℓ​\(p\)=\(p,sℓ,p\)\.s\_\{\\ell,p\}=s\_\{\\ell\}\(k\_\{\\ell\}\(p\)\),\\qquad\\tau\_\{\\ell\}\(p\)=\(p,s\_\{\\ell,p\}\)\.Thenτℓ​\(p\)∈ℛℓ\\tau\_\{\\ell\}\(p\)\\in\\mathcal\{R\}\_\{\\ell\}and:

1. \(i\)λℓ\\lambda\_\{\\ell\}is a\[0,1\]\[0,1\]\-valued proper loss with truth embeddingτℓ\\tau\_\{\\ell\}\.
2. \(ii\)The learner’s canonical proper loss agrees exactly with the best\-response loss: λℓ​\(τℓ​\(p\),y\)=ℓ​\(kℓ​\(p\),y\)∀p,y\.\\lambda\_\{\\ell\}\(\\tau\_\{\\ell\}\(p\),y\)=\\ell\(k\_\{\\ell\}\(p\),y\)\\qquad\\forall p,y\.\(53\)
3. \(iii\)For every actiona∈𝒜a\\in\\mathcal\{A\}and every choiceqℓ​\(a\)∈Qℓ​\(sℓ​\(a\)\)q\_\{\\ell\}\(a\)\\in Q\_\{\\ell\}\(s\_\{\\ell\}\(a\)\), define ρℓ​\(a\)=\(qℓ​\(a\),sℓ​\(a\)\)\.\\rho\_\{\\ell\}\(a\)=\(q\_\{\\ell\}\(a\),s\_\{\\ell\}\(a\)\)\.Then λℓ​\(ρℓ​\(a\),y\)≤ℓ​\(a,y\)∀a,y\.\\lambda\_\{\\ell\}\(\\rho\_\{\\ell\}\(a\),y\)\\leq\\ell\(a,y\)\\qquad\\forall a,y\.\(54\)

###### Proof of[Section˜7](https://arxiv.org/html/2607.28856#S7)\.

For every actionaa,

−Lpℓ​\(a\)=−ℓ​\(a,0\)−p​\(ℓ​\(a,1\)−ℓ​\(a,0\)\)=p​sℓ​\(a\)−ℓ​\(a,0\)\.\-L\_\{p\}^\{\\ell\}\(a\)=\-\\ell\(a,0\)\-p\(\\ell\(a,1\)\-\\ell\(a,0\)\)=p\\,s\_\{\\ell\}\(a\)\-\\ell\(a,0\)\.Taking the supremum overaaproves \([51](https://arxiv.org/html/2607.28856#S7.E51)\)\. HenceFℓF\_\{\\ell\}is convex\. Since eachsℓ​\(a\)∈\[−1,1\]s\_\{\\ell\}\(a\)\\in\[\-1,1\], the affine functions in \([51](https://arxiv.org/html/2607.28856#S7.E51)\) are11\-Lipschitz, soFℓF\_\{\\ell\}is continuous on\[0,1\]\[0,1\]\. The maximum definingFℓ∗​\(s\)F\_\{\\ell\}^\{\*\}\(s\)is therefore attained\.

Fixpp\. Sincekℓ​\(p\)k\_\{\\ell\}\(p\)is a best response, its affine function is active atpp:

Fℓ​\(p\)=p​sℓ,p−ℓ​\(kℓ​\(p\),0\)\.F\_\{\\ell\}\(p\)=p\\,s\_\{\\ell,p\}\-\\ell\(k\_\{\\ell\}\(p\),0\)\.Thussℓ,p∈∂Fℓ​\(p\)s\_\{\\ell,p\}\\in\\partial F\_\{\\ell\}\(p\), equivalentlyp∈Qℓ​\(sℓ,p\)p\\in Q\_\{\\ell\}\(s\_\{\\ell,p\}\), soτℓ​\(p\)∈ℛℓ\\tau\_\{\\ell\}\(p\)\\in\\mathcal\{R\}\_\{\\ell\}\. Fenchel equality gives

Fℓ∗​\(sℓ,p\)=p​sℓ,p−Fℓ​\(p\)=ℓ​\(kℓ​\(p\),0\),F\_\{\\ell\}^\{\*\}\(s\_\{\\ell,p\}\)=p\\,s\_\{\\ell,p\}\-F\_\{\\ell\}\(p\)=\\ell\(k\_\{\\ell\}\(p\),0\),and therefore

λℓ​\(τℓ​\(p\),y\)=ℓ​\(kℓ​\(p\),0\)\+y​Δℓ​\(kℓ​\(p\)\)=ℓ​\(kℓ​\(p\),y\)\.\\lambda\_\{\\ell\}\(\\tau\_\{\\ell\}\(p\),y\)=\\ell\(k\_\{\\ell\}\(p\),0\)\+y\\Delta\_\{\\ell\}\(k\_\{\\ell\}\(p\)\)=\\ell\(k\_\{\\ell\}\(p\),y\)\.
For properness, let\(q,s\)∈ℛℓ\(q,s\)\\in\\mathcal\{R\}\_\{\\ell\}\. Fenchel–Young gives

𝔼Y∼Ber⁡\(p\)​\[λℓ​\(\(q,s\),Y\)\]=Fℓ∗​\(s\)−p​s≥−Fℓ​\(p\),\\mathbb\{E\}\_\{Y\\sim\\operatorname\{Ber\}\(p\)\}\[\\lambda\_\{\\ell\}\(\(q,s\),Y\)\]=F\_\{\\ell\}^\{\*\}\(s\)\-ps\\geq\-F\_\{\\ell\}\(p\),while the truthful message achieves equality by the previous paragraph\.

It remains to check boundedness and comparator domination\. Ifs=sℓ​\(a\)s=s\_\{\\ell\}\(a\), then \([51](https://arxiv.org/html/2607.28856#S7.E51)\) implies

Fℓ​\(q\)≥q​s−ℓ​\(a,0\)∀q,F\_\{\\ell\}\(q\)\\geq qs\-\\ell\(a,0\)\\qquad\\forall q,soFℓ∗​\(s\)≤ℓ​\(a,0\)≤1F\_\{\\ell\}^\{\*\}\(s\)\\leq\\ell\(a,0\)\\leq 1\. Similarly,Fℓ∗​\(s\)−s≤ℓ​\(a,1\)≤1F\_\{\\ell\}^\{\*\}\(s\)\-s\\leq\\ell\(a,1\)\\leq 1\. Evaluating the conjugate atq=0q=0andq=1q=1gives

Fℓ∗​\(s\)≥−Fℓ​\(0\)=mina′⁡ℓ​\(a′,0\)≥0,Fℓ∗​\(s\)−s≥−Fℓ​\(1\)=mina′⁡ℓ​\(a′,1\)≥0\.F\_\{\\ell\}^\{\*\}\(s\)\\geq\-F\_\{\\ell\}\(0\)=\\min\_\{a^\{\\prime\}\}\\ell\(a^\{\\prime\},0\)\\geq 0,\\qquad F\_\{\\ell\}^\{\*\}\(s\)\-s\\geq\-F\_\{\\ell\}\(1\)=\\min\_\{a^\{\\prime\}\}\\ell\(a^\{\\prime\},1\)\\geq 0\.Thusλℓ\\lambda\_\{\\ell\}is\[0,1\]\[0,1\]\-valued, and the two upper bounds are exactly \([54](https://arxiv.org/html/2607.28856#S7.E54)\)\. ∎

###### Example 7\.3\(Canonical properization of the0–11loss\)\.

Let𝒜=\{0,1\}\\mathcal\{A\}=\\\{0,1\\\}andℓ​\(a,y\)=𝟏​\{a≠y\}\\ell\(a,y\)=\\mathbf\{1\}\\\{a\\neq y\\\}\. ThenLp​\(0\)=pL\_\{p\}\(0\)=p,Lp​\(1\)=1−pL\_\{p\}\(1\)=1\-p, sokℓ​\(p\)=𝟏​\{p\>1/2\}k\_\{\\ell\}\(p\)=\\mathbf\{1\}\\\{p\>1/2\\\}andFℓ​\(p\)=−min⁡\{p,1−p\}F\_\{\\ell\}\(p\)=\-\\min\\\{p,1\-p\\\}\. Sincesℓ​\(0\)=−1s\_\{\\ell\}\(0\)=\-1andsℓ​\(1\)=1s\_\{\\ell\}\(1\)=1,𝒮ℓ=\{−1,1\}\\mathcal\{S\}\_\{\\ell\}=\\\{\-1,1\\\}, and

Fℓ∗​\(−1\)=0,Qℓ​\(−1\)=\[0,12\],Fℓ∗​\(1\)=1,Qℓ​\(1\)=\[12,1\]\.F\_\{\\ell\}^\{\*\}\(\-1\)=0,\\quad Q\_\{\\ell\}\(\-1\)=\\left\[0,\\tfrac\{1\}\{2\}\\right\],\\qquad F\_\{\\ell\}^\{\*\}\(1\)=1,\\quad Q\_\{\\ell\}\(1\)=\\left\[\\tfrac\{1\}\{2\},1\\right\]\.The canonical proper loss isλℓ​\(\(q,−1\),y\)=y\\lambda\_\{\\ell\}\(\(q,\-1\),y\)=yandλℓ​\(\(q,1\),y\)=1−y\\lambda\_\{\\ell\}\(\(q,1\),y\)=1\-y; it does not depend onqqat all\. This is exactly the redundancy named in[Section˜7](https://arxiv.org/html/2607.28856#S7): everyq∈\[0,12\]q\\in\[0,\\frac\{1\}\{2\}\]paired withs=−1s=\-1represents the same underlying decisiona=0a=0, and everyq∈\[12,1\]q\\in\[\\frac\{1\}\{2\},1\]paired withs=1s=1representsa=1a=1\. One checks directly thatλℓ​\(τℓ​\(p\),y\)=ℓ​\(kℓ​\(p\),y\)\\lambda\_\{\\ell\}\(\\tau\_\{\\ell\}\(p\),y\)=\\ell\(k\_\{\\ell\}\(p\),y\)for everyp,yp,y, and thatρℓ​\(0\)=\(q,−1\)\\rho\_\{\\ell\}\(0\)=\(q,\-1\)andρℓ​\(1\)=\(q,1\)\\rho\_\{\\ell\}\(1\)=\(q,1\), for anyqqin the corresponding interval, satisfyλℓ​\(ρℓ​\(a\),y\)=ℓ​\(a,y\)\\lambda\_\{\\ell\}\(\\rho\_\{\\ell\}\(a\),y\)=\\ell\(a,y\)with equality, since here𝒜\\mathcal\{A\}already coincides with the extreme actions of the decision problem\.

For a classℋ⊆\{h:𝒳→𝒜\}\\mathcal\{H\}\\subseteq\\\{h:\\mathcal\{X\}\\to\\mathcal\{A\}\\\}, define its canonical properization by

ρℓ∘ℋ=\{x↦ρℓ​\(h​\(x\)\):h∈ℋ\}\.\\rho\_\{\\ell\}\\circ\\mathcal\{H\}=\\\{x\\mapsto\\rho\_\{\\ell\}\(h\(x\)\):h\\in\\mathcal\{H\}\\\}\.For a proper loss with truth embeddingτ\\tau, write

SwapRegT⁡\(λ,𝒢;τ\)=supψ:𝒫→𝒢∑t=1T\[λ​\(τ​\(pt\),yt\)−λ​\(ψ​\(pt\)​\(xt\),yt\)\]\.\\operatorname\{SwapReg\}\_\{T\}\(\\lambda,\\mathcal\{G\};\\tau\)=\\sup\_\{\\psi:\\mathcal\{P\}\\to\\mathcal\{G\}\}\\sum\_\{t=1\}^\{T\}\\left\[\\lambda\(\\tau\(p\_\{t\}\),y\_\{t\}\)\-\\lambda\(\\psi\(p\_\{t\}\)\(x\_\{t\}\),y\_\{t\}\)\\right\]\.
###### Theorem 7\.4\(Fixed bounded\-loss transfer\)\.

Letℓ:𝒜×\{0,1\}→\[0,1\]\\ell:\\mathcal\{A\}\\times\\\{0,1\\\}\\to\[0,1\]be fixed and suppose that best responses are attained\. Let\(λℓ,τℓ,ρℓ\)\(\\lambda\_\{\\ell\},\\tau\_\{\\ell\},\\rho\_\{\\ell\}\)be its canonical properization from[Section˜7](https://arxiv.org/html/2607.28856#S7)\. Then, for every transcript,

SwapRegTbr⁡\(ℓ,ℋ\)≤SwapRegT⁡\(λℓ,ρℓ∘ℋ;τℓ\)\.\\operatorname\{SwapReg\}\_\{T\}^\{\\mathrm\{br\}\}\(\\ell,\\mathcal\{H\}\)\\leq\\operatorname\{SwapReg\}\_\{T\}\(\\lambda\_\{\\ell\},\\rho\_\{\\ell\}\\circ\\mathcal\{H\};\\tau\_\{\\ell\}\)\.\(55\)Consequently, any swap\-regret bound for the single proper lossλℓ\\lambda\_\{\\ell\}and transformed comparator classρℓ∘ℋ\\rho\_\{\\ell\}\\circ\\mathcal\{H\}gives the same bound for the original lossℓ\\ell, provided the learner playskℓ​\(p\)k\_\{\\ell\}\(p\)after forecastingpp\.

###### Proof of[Theorem˜7\.4](https://arxiv.org/html/2607.28856#S7.Thmtheorem4)\.

Fix a swap ruleϕ:𝒫→ℋ\\phi:\\mathcal\{P\}\\to\\mathcal\{H\}and defineϕ~​\(p\)=ρℓ∘ϕ​\(p\)\\widetilde\{\\phi\}\(p\)=\\rho\_\{\\ell\}\\circ\\phi\(p\)\. For every round,[Section˜7](https://arxiv.org/html/2607.28856#S7)gives

ℓ​\(kℓ​\(pt\),yt\)−ℓ​\(ϕ​\(pt\)​\(xt\),yt\)≤λℓ​\(τℓ​\(pt\),yt\)−λℓ​\(ϕ~​\(pt\)​\(xt\),yt\)\.\\ell\(k\_\{\\ell\}\(p\_\{t\}\),y\_\{t\}\)\-\\ell\(\\phi\(p\_\{t\}\)\(x\_\{t\}\),y\_\{t\}\)\\leq\\lambda\_\{\\ell\}\(\\tau\_\{\\ell\}\(p\_\{t\}\),y\_\{t\}\)\-\\lambda\_\{\\ell\}\(\\widetilde\{\\phi\}\(p\_\{t\}\)\(x\_\{t\}\),y\_\{t\}\)\.Summing and taking the supremum overϕ\\phiproves the claim\. ∎

###### Corollary 7\.5\(Finite\-class arbitrary losses from[Theorem˜7\.4](https://arxiv.org/html/2607.28856#S7.Thmtheorem4)\)\.

If\|ℋ\|=M<∞\|\\mathcal\{H\}\|=M<\\infty, then\|ρℓ∘ℋ\|≤M\|\\rho\_\{\\ell\}\\circ\\mathcal\{H\}\|\\leq M\. Hence any finite\-class proper\-loss guarantee forλℓ\\lambda\_\{\\ell\}transfers with the same logarithmic dependence onMMtoSwapRegTbr⁡\(ℓ,ℋ\)\\operatorname\{SwapReg\}\_\{T\}^\{\\mathrm\{br\}\}\(\\ell,\\mathcal\{H\}\)\.

###### Proof of[Section˜7](https://arxiv.org/html/2607.28856#S7)\.

The maph↦ρℓ∘hh\\mapsto\\rho\_\{\\ell\}\\circ his deterministic, so it cannot increase cardinality\. Apply[Theorem˜7\.4](https://arxiv.org/html/2607.28856#S7.Thmtheorem4)\. ∎

The transformed comparator class is governed by the scalar slope class

Δℓ∘ℋ=\{x↦Δℓ​\(h​\(x\)\):h∈ℋ\}⊆\[−1,1\]𝒳\.\\Delta\_\{\\ell\}\\circ\\mathcal\{H\}=\\\{x\\mapsto\\Delta\_\{\\ell\}\(h\(x\)\):h\\in\\mathcal\{H\}\\\}\\subseteq\[\-1,1\]^\{\\mathcal\{X\}\}\.\(56\)Indeed,λℓ​\(\(q,s\),y\)=Fℓ∗​\(s\)−s​y\\lambda\_\{\\ell\}\(\(q,s\),y\)=F\_\{\\ell\}^\{\*\}\(s\)\-sydepends on the message\(q,s\)∈ℛℓ\(q,s\)\\in\\mathcal\{R\}\_\{\\ell\}only throughss, so the swap regret ofλℓ\\lambda\_\{\\ell\}againstρℓ∘ℋ\\rho\_\{\\ell\}\\circ\\mathcal\{H\}equals the swap regret of the rescaled proper lossλ¯ℓ​\(p,y\):=Fℓ∗​\(2​p−1\)−\(2​p−1\)​y\\bar\{\\lambda\}\_\{\\ell\}\(p,y\):=F\_\{\\ell\}^\{\*\}\(2p\-1\)\-\(2p\-1\)y,p∈\[0,1\]p\\in\[0,1\], against the comparator class12​\(1−Δℓ∘ℋ\)⊆\[0,1\]𝒳\\tfrac\{1\}\{2\}\(1\-\\Delta\_\{\\ell\}\\circ\\mathcal\{H\}\)\\subseteq\[0,1\]^\{\\mathcal\{X\}\}: this relabels every message by itsss\-coordinate rescaled into\[0,1\]\[0,1\]and changes no loss value\. This identification is what lets a bounded\-proper\-loss guarantee for scalar\[0,1\]\[0,1\]\-valued comparators, such as[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2), act directly on the slope class in place of the redundant message spaceℛℓ\\mathcal\{R\}\_\{\\ell\}\.

###### Theorem 7\.6\(Uniform transfer from arbitrary losses\)\.

Letℒ\\mathcal\{L\}be a family of\[0,1\]\[0,1\]\-valued binary losses on the same action space𝒜\\mathcal\{A\}, each with attained best responses\. For eachℓ∈ℒ\\ell\\in\\mathcal\{L\}, let\(λℓ,τℓ,ρℓ\)\(\\lambda\_\{\\ell\},\\tau\_\{\\ell\},\\rho\_\{\\ell\}\)be its canonical properization\. Suppose a single probability\-valued forecasting algorithm produces a transcript for which, on an event of probability at least1−δ1\-\\delta,

SwapRegT⁡\(λℓ,ρℓ∘ℋ;τℓ\)≤RT​\(ℓ,ℋ,δ\)\\operatorname\{SwapReg\}\_\{T\}\(\\lambda\_\{\\ell\},\\rho\_\{\\ell\}\\circ\\mathcal\{H\};\\tau\_\{\\ell\}\)\\leq R\_\{T\}\(\\ell,\\mathcal\{H\},\\delta\)\(57\)simultaneously for everyℓ∈ℒ\\ell\\in\\mathcal\{L\}\. Then, on the same event,

supℓ∈ℒSwapRegTbr⁡\(ℓ,ℋ\)≤supℓ∈ℒRT​\(ℓ,ℋ,δ\)\.\\sup\_\{\\ell\\in\\mathcal\{L\}\}\\operatorname\{SwapReg\}\_\{T\}^\{\\mathrm\{br\}\}\(\\ell,\\mathcal\{H\}\)\\leq\\sup\_\{\\ell\\in\\mathcal\{L\}\}R\_\{T\}\(\\ell,\\mathcal\{H\},\\delta\)\.\(58\)
The relevant complexity is therefore the induced slope class

𝒮ℒ,ℋ=\{x↦−Δℓ​\(h​\(x\)\):ℓ∈ℒ,h∈ℋ\},\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}=\\\{x\\mapsto\-\\Delta\_\{\\ell\}\(h\(x\)\):\\ell\\in\\mathcal\{L\},\\ h\\in\\mathcal\{H\}\\\},\(59\)viewed, via the reparametrization above, as a single comparator class shared by everyℓ∈ℒ\\ell\\in\\mathcal\{L\}\.

###### Proof of[Theorem˜7\.6](https://arxiv.org/html/2607.28856#S7.Thmtheorem6)\.

Apply[Theorem˜7\.4](https://arxiv.org/html/2607.28856#S7.Thmtheorem4)to eachℓ∈ℒ\\ell\\in\\mathcal\{L\}and use the simultaneous event \([57](https://arxiv.org/html/2607.28856#S7.E57)\)\. ∎

Establishing \([57](https://arxiv.org/html/2607.28856#S7.E57)\) for a whole familyℒ\\mathcal\{L\}from a single run requires more than\|𝒮ℒ,ℋ\|<∞\|\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}\|<\\infty: the algorithm underlying[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)needs a finite range for its comparator’s predicted values, fixed*before*the online interaction begins, exactly as in the finite\-range hypothesis of that theorem \([Section˜5\.3](https://arxiv.org/html/2607.28856#S5.SS3)\)\. A bound on how many distinct behaviors𝒮ℒ,ℋ\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}can exhibit on a sample observed only after the fact does not supply such a range, since the representative slope values it counts are determined by the realized transcript and so cannot be fixed in advance of it\. We instead assume the range directly\.

###### Corollary 7\.7\(Finite arbitrary\-loss family with a shared finite slope range\)\.

Suppose\|ℒ\|=K\|\\mathcal\{L\}\|=K,\|ℋ\|=M\|\\mathcal\{H\}\|=M, and suppose further that, fixed before the online interaction, there is a finite setΓℒ⊆\[−1,1\]\\Gamma\_\{\\mathcal\{L\}\}\\subseteq\[\-1,1\]with−Δℓ​\(h​\(x\)\)∈Γℒ\-\\Delta\_\{\\ell\}\(h\(x\)\)\\in\\Gamma\_\{\\mathcal\{L\}\}for everyℓ∈ℒ\\ell\\in\\mathcal\{L\},h∈ℋh\\in\\mathcal\{H\}, andx∈𝒳x\\in\\mathcal\{X\}– the slope\-class analogue of the finite\-range assumptionΓℋ\\Gamma\_\{\\mathcal\{H\}\}in[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)\. WriteJ=\|Γℒ\|J=\|\\Gamma\_\{\\mathcal\{L\}\}\|\. Then\|𝒮ℒ,ℋ\|≤K​M\|\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}\|\\leq KM, and, on one event of probability at least1−δ1\-\\delta, simultaneously for everyℓ∈ℒ\\ell\\in\\mathcal\{L\},

SwapRegT⁡\(λℓ,ρℓ∘ℋ;τℓ\)=O~​\(T​\(log⁡\(K​M\)\+log⁡J\+log⁡1δ\)\)\.\\operatorname\{SwapReg\}\_\{T\}\(\\lambda\_\{\\ell\},\\rho\_\{\\ell\}\\circ\\mathcal\{H\};\\tau\_\{\\ell\}\)=\\widetilde\{O\}\\\!\\left\(\\sqrt\{T\\left\(\\log\(KM\)\+\\log J\+\\log\\frac\{1\}\{\\delta\}\\right\)\}\\right\)\.Consequently, by[Theorem˜7\.6](https://arxiv.org/html/2607.28856#S7.Thmtheorem6),

supℓ∈ℒSwapRegTbr⁡\(ℓ,ℋ\)=O~​\(T​\(log⁡\(K​M\)\+log⁡J\+log⁡1δ\)\)\.\\sup\_\{\\ell\\in\\mathcal\{L\}\}\\operatorname\{SwapReg\}\_\{T\}^\{\\mathrm\{br\}\}\(\\ell,\\mathcal\{H\}\)=\\widetilde\{O\}\\\!\\left\(\\sqrt\{T\\left\(\\log\(KM\)\+\\log J\+\\log\\frac\{1\}\{\\delta\}\\right\)\}\\right\)\.

###### Proof of[Section˜7](https://arxiv.org/html/2607.28856#S7)\.

The map\(ℓ,h\)↦−Δℓ​\(h​\(⋅\)\)\(\\ell,h\)\\mapsto\-\\Delta\_\{\\ell\}\(h\(\\cdot\)\)is deterministic on theK​MKMpairs, so\|𝒮ℒ,ℋ\|≤K​M\|\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}\|\\leq KM\. By assumption, every element of𝒮ℒ,ℋ\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}, viewed after the reparametrization above as a\[0,1\]\[0,1\]\-valued comparator, takes values in the rescaled finite set12​\(1\+Γℒ\)⊆\[0,1\]\\tfrac\{1\}\{2\}\(1\+\\Gamma\_\{\\mathcal\{L\}\}\)\\subseteq\[0,1\]of sizeJJ\. Running[Theorem˜5\.2](https://arxiv.org/html/2607.28856#S5.Thmtheorem2)with comparator class𝒮ℒ,ℋ\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}\(of size at mostK​MKM, in place ofℋ\\mathcal\{H\}\) and finite range12​\(1\+Γℒ\)\\tfrac\{1\}\{2\}\(1\+\\Gamma\_\{\\mathcal\{L\}\}\)\(of sizeJJ, in place ofΓℋ\\Gamma\_\{\\mathcal\{H\}\}\) therefore gives, on one event of probability at least1−δ1\-\\delta,

supℓ′:\|ℓ′\|≤1SwapRegT⁡\(ℓ′,𝒮ℒ,ℋ\)=O~​\(T​\(log⁡\(K​M\)\+log⁡J\+log⁡1δ\)\)\.\\sup\_\{\\ell^\{\\prime\}:\|\\ell^\{\\prime\}\|\\leq 1\}\\operatorname\{SwapReg\}\_\{T\}\(\\ell^\{\\prime\},\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}\)=\\widetilde\{O\}\\\!\\left\(\\sqrt\{T\\left\(\\log\(KM\)\+\\log J\+\\log\\frac\{1\}\{\\delta\}\\right\)\}\\right\)\.For eachℓ∈ℒ\\ell\\in\\mathcal\{L\}, restricting the supremum definingSwapRegT⁡\(λ¯ℓ,𝒮ℒ,ℋ\)\\operatorname\{SwapReg\}\_\{T\}\(\\bar\{\\lambda\}\_\{\\ell\},\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}\)to swap rules valued in the sub\-collection\{−Δℓ​\(h​\(⋅\)\):h∈ℋ\}⊆𝒮ℒ,ℋ\\\{\-\\Delta\_\{\\ell\}\(h\(\\cdot\)\):h\\in\\mathcal\{H\}\\\}\\subseteq\\mathcal\{S\}\_\{\\mathcal\{L\},\\mathcal\{H\}\}can only decrease it, so the display above boundsSwapRegT⁡\(λℓ,ρℓ∘ℋ;τℓ\)\\operatorname\{SwapReg\}\_\{T\}\(\\lambda\_\{\\ell\},\\rho\_\{\\ell\}\\circ\\mathcal\{H\};\\tau\_\{\\ell\}\)for everyℓ∈ℒ\\ell\\in\\mathcal\{L\}simultaneously, on the same event\. ∎

If the action space𝒜\\mathcal\{A\}itself is finite,Γℒ\\Gamma\_\{\\mathcal\{L\}\}is automatic: eachΔℓ\\Delta\_\{\\ell\}has domain𝒜\\mathcal\{A\}, soJ≤K​\|𝒜\|J\\leq K\|\\mathcal\{A\}\|with no separate assumption needed\. This does not make the hypothesis vacuous, only automatic –[Section˜7](https://arxiv.org/html/2607.28856#S7)below shows thatJJcan already be as large as\|𝒜\|\|\\mathcal\{A\}\|for a single hypothesis, so finiteness ofΓℒ\\Gamma\_\{\\mathcal\{L\}\}is not the same as smallness ofJJ\.

## 8Discussion and Open Problems

Several questions are left open by this paper\. The online algorithm here is deliberately finite\-class, and extending its guarantee to infinite classes – say, through sequential covers, offset sequential Rademacher complexity, or a second\-order online weak learner – remains open; a set of representatives chosen only after seeing the transcript is not enough, since the guarantee must hold uniformly over swap rules chosen after the fact\. The algorithm also maintains one weight for every bucket, test, sign, and learning rate, so making it oracle\-efficient – for instance by combining sparse approachability with a learner that directly optimizes the underlying offset objective,η​∑t\(yt−pt\)​gt−4​η2​∑tgt2\\eta\\sum\_\{t\}\(y\_\{t\}\-p\_\{t\}\)g\_\{t\}\-4\\eta^\{2\}\\sum\_\{t\}g\_\{t\}^\{2\}, since an ordinary first\-order agnostic learner loses the second\-order term needed here – is a natural next step\. Finally, the proper\-loss identity of[Section˜2\.3](https://arxiv.org/html/2607.28856#S2.SS3)has natural analogues for multiclass and vector\-valued outcomes, through subgradients of concave Bayes risks, and combining high\-dimensional approachability with these local curvature bounds to get rates that depend optimally on the outcome dimension is an appealing direction\.

In summary, this paper shows that a fixed proper loss’s own geometry is enough to make swap\-agnostic learning almost as easy as ordinary agnostic learning: rewarding a predictor whenever a proposed swap disagrees with it a lot, rather than penalizing disagreement at a uniform rate, turns the comparator’s own activity into the very quantity that controls it\. An approachability\-based algorithm produces this guarantee online with high probability, a standard online\-to\-batch argument carries it over to a randomized offline predictor, and finite covers then extend the offline guarantee from a single loss to broad loss families\. This one idea gives fast rates for Lipschitz and smooth proper losses, extends to bounded and convex Lipschitz families by writing them as positive combinations of simpler basis losses, and transfers exactly to postprocessed losses beyond the proper case through canonical properization\.

## References

- Blackwell \(1956\)David Blackwell\.An analog of the minimax theorem for vector payoffs\.*Pacific Journal of Mathematics*, 6\(1\):1–8, 1956\.
- Ardywibowo et al\. \(2025\)Randy Ardywibowo, Rakesh Sunki, Shin Tsz Lucy Kuo, and Sankalp Nayak\.BayesCNS: A unified Bayesian approach to address cold start and non\-stationarity in search systems at scale\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, 39\(1\):12–20, 2025\.
- Bartlett et al\. \(2006\)Peter L\. Bartlett, Michael I\. Jordan, and Jon D\. McAuliffe\.Convexity, classification, and risk bounds\.*Journal of the American Statistical Association*, 101\(473\):138–156, 2006\.
- Cesa\-Bianchi and Lugosi \(2006\)Nicolò Cesa\-Bianchi and Gábor Lugosi\.*Prediction, Learning, and Games*\.Cambridge University Press, 2006\.
- Collina et al\. \(2026\)Natalie Collina, Jiuyao Lu, Georgy Noarov, and Aaron Roth\.The sample complexity of multicalibration\.*arXiv preprint arXiv:2604\.21923*, 2026\.
- Consumer Financial Protection Bureau \(2024\)Consumer Financial Protection Bureau\.What is risk\-based pricing?Consumer Financial Protection Bureau, January 30, 2024\.
- Dawid \(1982\)A\. Philip Dawid\.The well\-calibrated Bayesian\.*Journal of the American Statistical Association*, 77\(379\):605–610, 1982\.
- Elkan \(2001\)Charles Elkan\.The foundations of cost\-sensitive learning\.In*International Joint Conference on Artificial Intelligence*, 2001\.
- Fishelson et al\. \(2025\)Maxwell Fishelson, Robert Kleinberg, Princewill Okoroafor, Renato Paes Leme, Jon Schneider, and Yifeng Teng\.Full swap regret and discretized calibration\.In*Proceedings of the 36th International Conference on Algorithmic Learning Theory*, volume 272 of*Proceedings of Machine Learning Research*, pages 444–480, 2025\.
- Foster and Vohra \(1998\)Dean P\. Foster and Rakesh V\. Vohra\.Asymptotic calibration\.*Biometrika*, 85\(2\):379–390, 1998\.
- Garg et al\. \(2024\)Sumegha Garg, Christopher Jung, Omer Reingold, and Aaron Roth\.Oracle efficient online multicalibration and omniprediction\.In*Proceedings of the 2024 Annual ACM\-SIAM Symposium on Discrete Algorithms*, pages 2725–2792, 2024\.
- Gibbs and Tibshirani \(2026\)Isaac Gibbs and Ryan J\. Tibshirani\.Sample\-efficient omniprediction for proper losses\.In*Proceedings of the 39th Annual Conference on Learning Theory*, volume 336 of*Proceedings of Machine Learning Research*, pages 2679–2719, 2026\.
- Gneiting and Raftery \(2007\)Tilmann Gneiting and Adrian E\. Raftery\.Strictly proper scoring rules, prediction, and estimation\.*Journal of the American Statistical Association*, 102\(477\):359–378, 2007\.
- Gopalan et al\. \(2022\)Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder\.Omnipredictors\.In*Innovations in Theoretical Computer Science*, 2022\.
- Gopalan et al\. \(2023\)Parikshit Gopalan, Michael P\. Kim, and Omer Reingold\.Swap agnostic learning, or characterizing omniprediction via multicalibration\.In*Advances in Neural Information Processing Systems*, 2023\.
- Hébert\-Johnson et al\. \(2018\)Úrsula Hébert\-Johnson, Michael P\. Kim, Omer Reingold, and Guy N\. Rothblum\.Multicalibration: Calibration for the \(computationally\-identifiable\) masses\.In*International Conference on Machine Learning*, 2018\.
- Grundy et al\. \(2019\)Scott M\. Grundy et al\.2018 guideline on the management of blood cholesterol\.*Journal of the American College of Cardiology*, 73\(24\):e285–e350, 2019\.
- Hu and Wu \(2024\)Lunjia Hu and Yifan Wu\.Predict to minimize swap regret for all payoff\-bounded tasks\.In*2024 IEEE 65th Annual Symposium on Foundations of Computer Science \(FOCS\)*, pages 244–263, 2024\.doi:10\.1109/FOCS61266\.2024\.00024\.
- Hu et al\. \(2026\)Lunjia Hu, Jon Schneider, and Yifan Wu\.Near\-optimal swap regret minimization for convex losses\.In*Proceedings of the 39th Annual Conference on Learning Theory*, volume 336 of*Proceedings of Machine Learning Research*, pages 3285–3313, 2026\.
- Hu et al\. \(2026a\)Lunjia Hu, Kevin Tian, and Chutong Yang\.Simultaneous Blackwell approachability and applications to multiclass omniprediction\.In*Proceedings of the 39th Annual Conference on Learning Theory*, volume 336 of*Proceedings of Machine Learning Research*, pages 3593–3634, 2026\.
- Hu et al\. \(2026b\)Lunjia Hu, Kevin Tian, and Chutong Yang\.Optimal recalibration of an online predictor\.*arXiv preprint arXiv:2607\.19689*, 2026\.
- Kim et al\. \(2019\)Michael P\. Kim, Amirata Ghorbani, and James Zou\.Multiaccuracy: Black\-box post\-processing for fairness in classification\.In*AAAI/ACM Conference on AI, Ethics, and Society*, 2019\.
- Kleinberg et al\. \(2023\)Robert Kleinberg, Renato Paes Leme, Jon Schneider, and Yifeng Teng\.U\-calibration: Forecasting for an unknown agent\.In*Conference on Learning Theory*, 2023\.
- Li et al\. \(2022\)Yingkai Li, Jason D\. Hartline, Liren Shan, and Yifan Wu\.Optimization of scoring rules\.In*Proceedings of the 23rd ACM Conference on Economics and Computation*, 2022\.
- Luo et al\. \(2024\)Haipeng Luo, Spandan Senapati, and Vatsal Sharan\.Optimal multiclass U\-calibration error and beyond\.In*Advances in Neural Information Processing Systems*, 2024\.
- Luo et al\. \(2025\)Haipeng Luo, Spandan Senapati, and Vatsal Sharan\.Improved bounds for swap multicalibration and swap omniprediction\.In*Advances in Neural Information Processing Systems*, 2025\.
- Luo et al\. \(2025b\)Haipeng Luo, Spandan Senapati, and Vatsal Sharan\.Simultaneous swap regret minimization via KL\-calibration\.In*Advances in Neural Information Processing Systems*, 2025\.
- Okoroafor et al\. \(2024\)Princewill Okoroafor, Robert Kleinberg, and Wen Sun\.Faster recalibration of an online predictor via approachability\.In*Proceedings of the 27th International Conference on Artificial Intelligence and Statistics*, volume 238 of*Proceedings of Machine Learning Research*, 2024\.
- Okoroafor et al\. \(2025\)Princewill Okoroafor, Robert Kleinberg, and Michael P\. Kim\.Near\-optimal algorithms for omniprediction\.In*2025 IEEE 66th Annual Symposium on Foundations of Computer Science \(FOCS\)*, pages 1595–1609, 2025\.doi:10\.1109/FOCS63196\.2025\.00084\.
- Reid and Williamson \(2010\)Mark D\. Reid and Robert C\. Williamson\.Composite binary losses\.*Journal of Machine Learning Research*, 11:2387–2422, 2010\.
- Shalev\-Shwartz and Ben\-David \(2014\)Shai Shalev\-Shwartz and Shai Ben\-David\.*Understanding Machine Learning: From Theory to Algorithms*\.Cambridge University Press, 2014\.
- Vapnik \(1998\)Vladimir N\. Vapnik\.*Statistical Learning Theory*\.Wiley, 1998\.