The Sharp Tail of Uniform Stability

# The Sharp Tail of Uniform Stability
Source: [https://arxiv.org/html/2608.24098](https://arxiv.org/html/2608.24098)
###### Abstract

Uniform stability controls how much one training example can change the loss at any test point\. A new logarithmic\-free upper bound shows that aγ\\gamma\-uniformly stable algorithm with loss in\[0,L\]\[0,L\]has generalization gap at most

O⁡\(γ​log⁡\(1/δ\)\+L​log⁡\(1/δ\)n\)O\\\!\\left\(\\gamma\\log\(1/\\delta\)\+L\\sqrt\{\\frac\{\\log\(1/\\delta\)\}\{n\}\}\\right\)with probability1−δ1\-\\delta\. Whether an actual bounded\-loss learning algorithm can realize the linear dependence onlog⁡\(1/δ\)\\log\(1/\\delta\)has remained open\. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows withnn\. The known learning lower bound holds only at constant probability\.

We close this gap\. For everynn, stability levelγ\\gamma, and loss boundLL, we construct one deterministicγ\\gamma\-uniformly stable learning problem whose tail satisfies, simultaneously for1≤p≤c​n1\\leq p\\leq cn,

ℙ⁡\(R⁡\(AS\)−RS​\(AS\)≥c′​min⁡\{L,γ​p\+L​p/n\}\)≥e−p\.\\mathbb\{P\}\\\!\\left\(R\(A\_\{S\}\)\-R\_\{S\}\(A\_\{S\}\)\\geq c^\{\\prime\}\\min\\\!\\left\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\right\\\}\\right\)\\geq e^\{\-p\}\.The construction is ordinary bounded absolute\-loss regression with constant labels\. Its key is a multiscale collection of rare Rademacher features\. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of orderγ​p\\gamma pwithout violating the loss bound\. Geometrically spaced ramps put all confidence levels into the same problem\. Together with the logarithmic\-free upper bound, this determines the optimal high\-probability and moment dependence of uniform stability up to universal constants\.

## 1Introduction

Algorithmic stability explains generalization through the behavior of the learning rule rather than through uniform convergence over a hypothesis class\. A learning algorithmAAisγ\\gamma\-uniformly stable when replacing one training example changes its loss at every test point by at mostγ\\gamma\([Bousquet and Elisseeff, 2002](https://arxiv.org/html/2608.24098#bib.bib1)\)\. This property underlies guarantees for regularized empirical risk minimization, gradient methods, and stochastic optimization\([Shalev\-Shwartz et al\., 2010](https://arxiv.org/html/2608.24098#bib.bib2);[Hardt et al\., 2016](https://arxiv.org/html/2608.24098#bib.bib3)\)\. Its expectation guarantee is simple and sharp:\|𝔼⁡\[R⁡\(AS\)−RS​\(AS\)\]\|≤γ\|\\mathbb\{E\}\[R\(A\_\{S\}\)\-R\_\{S\}\(A\_\{S\}\)\]\|\\leq\\gamma\. Obtaining the correct high\-probability guarantee took a longer sequence of results\.

The classical bounded\-differences argument gives a deviation term of orderγ​n​log⁡\(1/δ\)\\gamma\\sqrt\{n\\log\(1/\\delta\)\}\([Bousquet and Elisseeff, 2002](https://arxiv.org/html/2608.24098#bib.bib1)\)\.[Feldman and Vondrák \(2018\)](https://arxiv.org/html/2608.24098#bib.bib4)replaced the factorγ​n\\gamma\\sqrt\{n\}byγ​L\\sqrt\{\\gamma L\}, and[Feldman and Vondrák \(2019\)](https://arxiv.org/html/2608.24098#bib.bib5)obtained a nearly optimal bound with logarithmic overhead innn\.[Bousquet et al\. \(2020\)](https://arxiv.org/html/2608.24098#bib.bib6)reduced the learning problem to a moment inequality for weakly interacting functions\. Their result left one factorlog⁡n\\log nin the stability term\. Very recently,[Nguyen\-Cung and Nguyen \(2026\)](https://arxiv.org/html/2608.24098#bib.bib8)removed that factor and proved

‖R⁡\(AS\)−RS​\(AS\)‖p≤33​p​γ\+L​2​pn,p≥2\.\\\|R\(A\_\{S\}\)\-R\_\{S\}\(A\_\{S\}\)\\\|\_\{p\}\\leq 33p\\gamma\+L\\sqrt\{\\frac\{2p\}\{n\}\},\\qquad p\\geq 2\.\(1\)The trivial range bound then caps the right side byLL\. Equation \([1](https://arxiv.org/html/2608.24098#S1.E1)\) gives the clean tail scale

min⁡\{L,γ​log⁡\(1/δ\)\+L​log⁡\(1/δ\)n\}\.\\min\\\!\\left\\\{L,\\gamma\\log\(1/\\delta\)\+L\\sqrt\{\\frac\{\\log\(1/\\delta\)\}\{n\}\}\\right\\\}\.\(2\)
The lower\-bound side has not matched this progress\.[Bousquet et al\. \(2020\)](https://arxiv.org/html/2608.24098#bib.bib6)constructed weakly interacting functions withppth momentΩ⁡\(p​n​γ\+L​p​n\)\\Omega\(pn\\gamma\+L\\sqrt\{pn\}\)\. Their functions have pointwise magnitude of ordern​γn\\gamma, so the construction does not come from a learning algorithm with a uniform loss boundLL\. They explicitly asked whether the same behavior is possible for the functions induced by a uniformly stable learner\.[Liu and Lu \(2020\)](https://arxiv.org/html/2608.24098#bib.bib7)later constructed a bounded\-loss learner with gapΩ⁡\(γ\+L/n\)\\Omega\(\\gamma\+L/\\sqrt\{n\}\)at constant probability, and left the dependence on small failure probability open\. The new upper\-bound paper also separates its result from exactly this learning lower\-bound question\([Nguyen\-Cung and Nguyen, 2026](https://arxiv.org/html/2608.24098#bib.bib8)\)\. Our lower\-bound theorem and proof are independent of that preprint\. Equation \([1](https://arxiv.org/html/2608.24098#S1.E1)\) is used only to identify the matching upper scale\.

We show that every term in \([2](https://arxiv.org/html/2608.24098#S1.E2)\) is necessary\. More strongly, one finite\-dimensional problem realizes the full curve at all confidence levelse−pe^\{\-p\}withp≤c​np\\leq cn\. This is not a different problem chosen for eachpp\.

#### Why the obvious quadratic construction fails\.

LetX1,…,XnX\_\{1\},\\ldots,X\_\{n\}be Rademacher signs,T=∑iXiT=\\sum\_\{i\}X\_\{i\}, and let a learner predict with amplitudeγ​T\\gamma T\. A linear loss has generalization gapγ​T2/n\\gamma T^\{2\}/n, whoseppth scale isγ​p\\gamma p\. The prediction amplitude at that event isγ​n​p\\gamma\\sqrt\{np\}\. Clipping it to the loss rangeLLactivates whenp≳L2/\(γ2​n\)p\\gtrsim L^\{2\}/\(\\gamma^\{2\}n\)\. This is exactly where the termγ​p\\gamma pbegins to dominateL​p/nL\\sqrt\{p/n\}\. Thus clipping destroys the part of the tail that needs to be proved\.

#### The new mechanism\.

We replace one feature by many independent Rademacher features\. At a chosen scale, exponentially many coordinates are placed just below a fixed large\-deviation threshold\. A ramp of widthΘ⁡\(p\)\\Theta\(p\)gives amplitudeΘ⁡\(γ​p\)\\Theta\(\\gamma p\)only when one coordinate crosses that threshold\. The ramp is coordinatewiseγ\\gamma\-stable regardless of the number of coordinates\. The loss reads the coordinates through the odd function

Ha​\(x\)=maxj⁡aj​xj−maxj⁡\(−aj​xj\)\.H\_\{a\}\(x\)=\\max\_\{j\}a\_\{j\}x\_\{j\}\-\\max\_\{j\}\(\-a\_\{j\}x\_\{j\}\)\.\(3\)It is centered under a symmetric population and is22\-Lipschitz inaaunder the sup norm\. When there is one dominant coordinate, its empirical average is bounded away from zero, so it contributesΘ⁡\(γ​p\)\\Theta\(\\gamma p\)to the gap\. Coordinates with smaller ramps can be present without changing the sign of the effect\. Coordinates with larger ramps are absent on the clean extreme event\.

We use geometrically spaced ramp widths\. The event at scalepkp\_\{k\}has probability much larger thane−pke^\{\-p\_\{k\}\}, which leaves enough probability to intersect it with an ordinary sampling\-deviation event\. A separate stable memorization term handles constant confidence and the range\-saturated regime\. All components are combined in a scalar predictor under absolute loss\.

Feature bank
dk≍e−pk/2/q⋆d\_\{k\}\\asymp e^\{\-p\_\{k\}/2\}/q\_\{\\star\}independent signs⟹\\LongrightarrowRare crossing
one score≥s⋆\\geq s\_\{\\star\}probability≳e−pk/2\\gtrsim e^\{\-p\_\{k\}/2\}⟹\\LongrightarrowStable readout
rampγ​pk\\gamma p\_\{k\}odd maximum⟹\\LongrightarrowFull gap
γ​pk\+L​p/n\\gamma p\_\{k\}\+L\\sqrt\{p/n\}probability≥e−p\\geq e^\{\-p\}Figure 1:The multiscale mechanism\. Reciprocal\-probability feature replication makes a rare large\-deviation crossing visible\. A coordinatewise stable ramp and the odd maximum turn that crossing into empirical bias\. Independent memory and sampling terms fill the constant\-confidence and square\-root parts of the tail\. Geometric choices ofpkp\_\{k\}put everyp≤c​np\\leq cnin one learner\.
#### Contributions\.

- •We give the first bounded\-loss uniformly stable learner with anΩ⁡\(γ​log⁡\(1/δ\)\)\\Omega\(\\gamma\\log\(1/\\delta\)\)high\-probability generalization gap\.
- •A single problem realizesΩ⁡\(min⁡\{L,γ​p\+L​p/n\}\)\\Omega\(\\min\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\\}\)simultaneously for all1≤p≤c​n1\\leq p\\leq cn\. Consequently, the moment upper bound in \([1](https://arxiv.org/html/2608.24098#S1.E1)\) is sharp for actual learning algorithms\.
- •The construction uses deterministic learning and standard absolute regression loss\. We prove uniform stability over all replacement datasets, not only on the high\-probability event\.

#### Related extensions\.

Several recent lines change the assumptions rather than the worst\-case lower\-bound question\.[Klochkov and Zhivotovskiy \(2021\)](https://arxiv.org/html/2608.24098#bib.bib9)obtain faster excess\-risk rates under a Bernstein condition\.[Zhou et al\. \(2023\)](https://arxiv.org/html/2608.24098#bib.bib12)derive PAC\-Bayes bounds for randomized uniformly stable algorithms under a sub\-exponential condition on their random stability parameter\.[Yuan and Li \(2022\)](https://arxiv.org/html/2608.24098#bib.bib10)use subbagging to boost confidence for randomized algorithms under the weaker, distribution\-dependent notion ofL2L\_\{2\}stability\.[Fan and Lei \(2024\)](https://arxiv.org/html/2608.24098#bib.bib11)introduce pointwise uniform stability and derive function\-value and gradient generalization bounds, with applications to SGD\. In a complementary 2026 direction,[Lei et al\. \(2026\)](https://arxiv.org/html/2608.24098#bib.bib13)replace bounded differences by finite\-LpL\_\{p\}replace\-one envelopes and obtain Gaussian\-plus\-polynomial upper tails for unbounded losses\. These results provide sharper conclusions from additional structure or modified algorithms\. They do not give a high\-probability lower bound for the ordinary deterministic uniform\-stability condition \([4](https://arxiv.org/html/2608.24098#S2.E4)\)\. Our result concerns exactly that worst\-case condition and the bounded\-loss minimax gap left open by[Bousquet et al\. \(2020\)](https://arxiv.org/html/2608.24098#bib.bib6),[Liu and Lu \(2020\)](https://arxiv.org/html/2608.24098#bib.bib7), and[Nguyen\-Cung and Nguyen \(2026\)](https://arxiv.org/html/2608.24098#bib.bib8)\.

## 2Setup and result

LetS=\(Z1,…,Zn\)∼PnS=\(Z\_\{1\},\\ldots,Z\_\{n\}\)\\sim P^\{n\}\. An algorithmAAmapsSSto a predictorASA\_\{S\}\. For a lossℓ\\ellwith values in\[0,L\]\[0,L\], define

R⁡\(AS\)=𝔼Z∼P​ℓ​\(AS,Z\),RS​\(AS\)=1n​∑i=1nℓ⁡\(AS,Zi\),GS=R⁡\(AS\)−RS​\(AS\)\.R\(A\_\{S\}\)=\\mathbb\{E\}\_\{Z\\sim P\}\\ell\(A\_\{S\},Z\),\\qquad R\_\{S\}\(A\_\{S\}\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\ell\(A\_\{S\},Z\_\{i\}\),\\qquad G\_\{S\}=R\(A\_\{S\}\)\-R\_\{S\}\(A\_\{S\}\)\.The algorithm isγ\\gamma\-uniformly stable if, wheneverSSandS′S^\{\\prime\}differ in one coordinate,

supz\|ℓ⁡\(AS,z\)−ℓ⁡\(AS′,z\)\|≤γ\.\\sup\_\{z\}\|\\ell\(A\_\{S\},z\)\-\\ell\(A\_\{S^\{\\prime\}\},z\)\|\\leq\\gamma\.\(4\)
Our theorem is stated with unspecified universal constants\. The appendix tracks concrete constants for the construction\.

###### Theorem 1\(Sharp lower tail\)\.

There are universal constantsc0,c1\>0c\_\{0\},c\_\{1\}\>0andn0∈ℕn\_\{0\}\\in\\mathbb\{N\}with the following property\. For everyn≥n0n\\geq n\_\{0\},L\>0L\>0, and0≤γ≤L0\\leq\\gamma\\leq L, there are a finite input space, a distributionPP, and one deterministicγ\\gamma\-uniformly stable absolute\-loss regression algorithm with loss in\[0,L\]\[0,L\]such that, simultaneously for every realp∈\[1,c0​n\]p\\in\[1,c\_\{0\}n\],

ℙS∼Pn​\(GS≥c1​min⁡\{L,γ​p\+L​p/n\}\)≥e−p\.\\mathbb\{P\}\_\{S\\sim P^\{n\}\}\\\!\\left\(G\_\{S\}\\geq c\_\{1\}\\min\\\!\\left\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\right\\\}\\right\)\\geq e^\{\-p\}\.\(5\)The regression labels are identically zero\.

The problem may depend on\(n,L,γ\)\(n,L,\\gamma\), as is standard for a minimax lower bound\. Crucially, it does not depend onpporδ\\delta\. The simultaneous statement immediately gives moment sharpness\.

###### Corollary 2\(Moment sharpness\)\.

For the problem in Theorem[1](https://arxiv.org/html/2608.24098#Thmtheorem1)and everyp∈\[2,c0​n\]p\\in\[2,c\_\{0\}n\],

‖GS‖p≥c2​min⁡\{L,γ​p\+L​p/n\}\\\|G\_\{S\}\\\|\_\{p\}\\geq c\_\{2\}\\min\\\!\\left\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\right\\\}\(6\)for a universalc2\>0c\_\{2\}\>0\.

Indeed, \([5](https://arxiv.org/html/2608.24098#S2.E5)\) implies‖GS‖p≥e−1\\\|G\_\{S\}\\\|\_\{p\}\\geq e^\{\-1\}times its displayed threshold\. Combining Corollary[2](https://arxiv.org/html/2608.24098#Thmtheorem2)with \([1](https://arxiv.org/html/2608.24098#S1.E1)\) and the range bound yields the minimax law

sup\(P,A,ℓ\)‖GS‖p≍min⁡\{L,γ​p\+L​p/n\},2≤p≤c0​n,\\sup\_\{\(P,A,\\ell\)\}\\\|G\_\{S\}\\\|\_\{p\}\\asymp\\min\\\!\\left\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\right\\\},\\qquad 2\\leq p\\leq c\_\{0\}n,\(7\)where the supremum is overγ\\gamma\-stable algorithms with loss in\[0,L\]\[0,L\]\. The upper and lower constants in \([7](https://arxiv.org/html/2608.24098#S2.E7)\) are universal\.

## 3The multiscale learner

We now define the single problem used for everypp\. A training input is

Z=\(X,J,Σ,U\)\.Z=\(X,J,\\Sigma,U\)\.All components are independent\. The vectorXXconsists of independent Rademacher coordinates,JJis uniform on\[D\]\[D\], andΣ,U\\Sigma,Uare Rademacher signs\. The dimension ofXXis divided into groups indexed by a geometric set of scales\.

Let

pk=16⋅4k,rk=pk/16=4k,pk≤min⁡\{n/64,L/γ\},p\_\{k\}=16\\cdot 4^\{k\},\\qquad r\_\{k\}=p\_\{k\}/16=4^\{k\},\\qquad p\_\{k\}\\leq\\min\\\{n/64,L/\\gamma\\\},\(8\)whereL/0=\+∞L/0=\+\\infty\. LetBnB\_\{n\}be a sum ofnnindependent Rademacher signs\. Choose the first attainable scores⋆≥n/4s\_\{\\star\}\\geq n/4and set

q⋆=ℙ⁡\(Bn≥s⋆\),dk=⌊8e−pk/2q⋆⌋,tk=s⋆−2​rk\.q\_\{\\star\}=\\mathbb\{P\}\(B\_\{n\}\\geq s\_\{\\star\}\),\\qquad d\_\{k\}=\\left\\lfloor\\frac\{8e^\{\-p\_\{k\}/2\}\}\{q\_\{\\star\}\}\\right\\rfloor,\\qquad t\_\{k\}=s\_\{\\star\}\-2r\_\{k\}\.\(9\)Groupkkcontainsdkd\_\{k\}independent coordinates\. For a sample, writeSk​j=∑i=1nXi,k​jS\_\{kj\}=\\sum\_\{i=1\}^\{n\}X\_\{i,kj\}and define the ramp amplitude

ak​j​\(S\)=min⁡\{γ​rk,γ2​\(Sk​j−tk\)\+\}\.a\_\{kj\}\(S\)=\\min\\left\\\{\\gamma r\_\{k\},\\frac\{\\gamma\}\{2\}\(S\_\{kj\}\-t\_\{k\}\)\_\{\+\}\\right\\\}\.\(10\)If the set of scales is empty,XXhas one dummy coordinate with amplitude zero\. The total feature dimension is finite and typically exponential innnbecauseq⋆=e−Θ⁡\(n\)q\_\{\\star\}=e^\{\-\\Theta\(n\)\}\. Section[7](https://arxiv.org/html/2608.24098#S7)explains why this multiplicity is used\.

The memory component usesD=8​n2D=8n^\{2\}cells\. Let

bj\(S\)=cmemsgn\(∑i:Ji=jΣi\),cmem=min\{γ/4,L/8\},b\_\{j\}\(S\)=c\_\{\\rm mem\}\\,\\operatorname\{sgn\}\\\!\\left\(\\sum\_\{i:J\_\{i\}=j\}\\Sigma\_\{i\}\\right\),\\qquad c\_\{\\rm mem\}=\\min\\\{\\gamma/4,L/8\\\},\(11\)withsgn⁡\(0\)=0\\operatorname\{sgn\}\(0\)=0\. Collect all ramp amplitudes in a vectora⁡\(S\)a\(S\)and use the symmetrized maximumHaH\_\{a\}from \([3](https://arxiv.org/html/2608.24098#S1.E3)\)\. The predictor is

hS​\(X,J,Σ,U\)=L2−14​Ha⁡\(S\)​\(X\)−bJ​\(S\)​Σ−L4​U\.h\_\{S\}\(X,J,\\Sigma,U\)=\\frac\{L\}\{2\}\-\\frac\{1\}\{4\}H\_\{a\(S\)\}\(X\)\-b\_\{J\}\(S\)\\Sigma\-\\frac\{L\}\{4\}U\.\(12\)The regression label is zero and the loss is absolute error\. We will show thathS∈\[0,L\]h\_\{S\}\\in\[0,L\], so the loss equalshSh\_\{S\}itself\.

The four pieces in \([12](https://arxiv.org/html/2608.24098#S3.E12)\) have distinct roles\. The centerL/2L/2enforces a valid loss range\. The symmetrized maximum produces theγ​p\\gamma ptail\. The cell memory produces a constant\-order stability gap and handles scales below1616or aboveL/γL/\\gamma\. The last sign produces the ordinaryL​p/nL\\sqrt\{p/n\}sampling tail\.

## 4Stability and centering

Two elementary Lipschitz properties make the construction work\.

###### Lemma 3\(Symmetrized maximum\)\.

For nonnegative vectorsa,a′a,a^\{\\prime\}and every sign vectorxx,

Ha​\(−x\)\\displaystyle H\_\{a\}\(\-x\)=−Ha​\(x\),\\displaystyle=\-H\_\{a\}\(x\),\|Ha​\(x\)\|\\displaystyle\|H\_\{a\}\(x\)\|≤2​‖a‖∞,\\displaystyle\\leq 2\\\|a\\\|\_\{\\infty\},\|Ha​\(x\)−Ha′​\(x\)\|\\displaystyle\|H\_\{a\}\(x\)\-H\_\{a^\{\\prime\}\}\(x\)\|≤2​‖a−a′‖∞\.\\displaystyle\\leq 2\\\|a\-a^\{\\prime\}\\\|\_\{\\infty\}\.\(13\)

The proof applies theℓ∞\\ell\_\{\\infty\}Lipschitz property of a maximum twice\. Replacing one training point changes every scoreSk​jS\_\{kj\}by at most two\. Hence \([10](https://arxiv.org/html/2608.24098#S3.E10)\) gives‖a⁡\(S\)−a⁡\(S′\)‖∞≤γ\\\|a\(S\)\-a\(S^\{\\prime\}\)\\\|\_\{\\infty\}\\leq\\gamma\. TheH/4H/4term changes by at mostγ/2\\gamma/2\. At a fixed memory cell, a replacement can changebjb\_\{j\}from−cmem\-c\_\{\\rm mem\}tocmemc\_\{\\rm mem\}, so the memory term changes by at most2​cmem≤γ/22c\_\{\\rm mem\}\\leq\\gamma/2\. TheUUterm does not depend on the sample\. This proves \([4](https://arxiv.org/html/2608.24098#S2.E4)\)\.

The largest ramp cap is at mostL/16L/16\. Lemma[3](https://arxiv.org/html/2608.24098#Thmtheorem3)gives\|Ha\|≤L/8\|H\_\{a\}\|\\leq L/8\. Together withcmem≤L/8c\_\{\\rm mem\}\\leq L/8, the sample\-dependent offset fromL/2L/2in \([12](https://arxiv.org/html/2608.24098#S3.E12)\) is at most

L/32\+L/8\+L/4=13​L/32\.L/32\+L/8\+L/4=13L/32\.ThushS∈\[3​L/32,29​L/32\]⊂\[0,L\]h\_\{S\}\\in\[3L/32,29L/32\]\\subset\[0,L\]\.

Conditional on the training sample, a freshXXis symmetric\. Lemma[3](https://arxiv.org/html/2608.24098#Thmtheorem3)therefore gives𝔼​Ha⁡\(S\)​\(X\)=0\\mathbb\{E\}H\_\{a\(S\)\}\(X\)=0\. A freshΣ\\Sigmaand a freshUUare centered as well, so

R⁡\(AS\)=L/2R\(A\_\{S\}\)=L/2\(14\)for every sample\. Consequently,

GS=14​n​∑i=1nHa⁡\(S\)​\(Xi\)\+1n​∑i=1nbJi​\(S\)​Σi\+L4​n​∑i=1nUi\.G\_\{S\}=\\frac\{1\}\{4n\}\\sum\_\{i=1\}^\{n\}H\_\{a\(S\)\}\(X\_\{i\}\)\+\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}b\_\{J\_\{i\}\}\(S\)\\Sigma\_\{i\}\+\\frac\{L\}\{4n\}\\sum\_\{i=1\}^\{n\}U\_\{i\}\.\(15\)This exact identity is the bridge from rare features to generalization\.

## 5Rare extremes create the linear tail

For each scalekk, letEkE\_\{k\}be the event that exactly one coordinate in groupkkhas score at leasts⋆s\_\{\\star\}, and every other coordinate in groupkkor a larger groupℓ\>k\\ell\>khas score strictly below its thresholdtℓt\_\{\\ell\}\. Smaller groups are unrestricted\.

###### Lemma 4\(Clean extreme\)\.

For every scale in \([8](https://arxiv.org/html/2608.24098#S3.E8)\),

ℙ\(Ek\)≥6e−pk/2\.\\mathbb\{P\}\(E\_\{k\}\)\\geq 6e^\{\-p\_\{k\}/2\}\.\(16\)OnEkE\_\{k\},

1n​∑i=1nHa⁡\(S\)​\(Xi\)≥332​γ​rk=3512​γ​pk\.\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}H\_\{a\(S\)\}\(X\_\{i\}\)\\geq\\frac\{3\}\{32\}\\gamma r\_\{k\}=\\frac\{3\}\{512\}\\gamma p\_\{k\}\.\(17\)

We give the main argument because it contains the new idea\. Hoeffding’s inequality yieldsq⋆≤e−n/32q\_\{\\star\}\\leq e^\{\-n/32\}\. Sincepk≤n/64p\_\{k\}\\leq n/64, the floor in \([9](https://arxiv.org/html/2608.24098#S3.E9)\) is negligible at the required constant scale and

dkq⋆≥7e−pk/2\.d\_\{k\}q\_\{\\star\}\\geq 7e^\{\-p\_\{k\}/2\}\.\(18\)Moving the threshold down byrkr\_\{k\}binomial steps multiplies its upper tail by at most\(rk\+1\)​2rk≤4rk<epk/8\(r\_\{k\}\+1\)2^\{r\_\{k\}\}\\leq 4^\{r\_\{k\}\}<e^\{p\_\{k\}/8\}\. Therefore, the expected number of coordinates in groupkkat or above the forbidden thresholdtkt\_\{k\}, and similarly in every larger group, is at most

8e−pk/2\+pk/8=8e−3pk/8\.8e^\{\-p\_\{k\}/2\+p\_\{k\}/8\}=8e^\{\-3p\_\{k\}/8\}\.\(19\)The scales grow by four, so the sum of these expectations from groupkkupward is below0\.0210\.021\. Independence across coordinates and a union bound with \([18](https://arxiv.org/html/2608.24098#S5.E18)\) prove \([16](https://arxiv.org/html/2608.24098#S5.E16)\)\.

OnEkE\_\{k\}, the exceptional coordinate reaches its capa=γ​rka=\\gamma r\_\{k\}\. Every coordinate in a smaller group has amplitude at mosta/4a/4, while every other coordinate in the same or a larger group has amplitude zero\. Letxi⋆x\_\{i\}^\{\\star\}be the exceptional coordinate\. Ifxi⋆=1x\_\{i\}^\{\\star\}=1, thenHa​\(Xi\)≥a−a/4H\_\{a\}\(X\_\{i\}\)\\geq a\-a/4\. Ifxi⋆=−1x\_\{i\}^\{\\star\}=\-1, thenHa​\(Xi\)≥−aH\_\{a\}\(X\_\{i\}\)\\geq\-a\. Since∑ixi⋆≥s⋆≥n/4\\sum\_\{i\}x\_\{i\}^\{\\star\}\\geq s\_\{\\star\}\\geq n/4, summing these inequalities gives

1n​∑iHa​\(Xi\)≥a⁡\(14−1\+1/48\)=3​a32\.\\frac\{1\}\{n\}\\sum\_\{i\}H\_\{a\}\(X\_\{i\}\)\\geq a\\left\(\\frac\{1\}\{4\}\-\\frac\{1\+1/4\}\{8\}\\right\)=\\frac\{3a\}\{32\}\.This proves \([17](https://arxiv.org/html/2608.24098#S5.E17)\)\. The smaller scales may fire, but the geometric cap makes them too weak to reverse the contribution of the exceptional feature\.

The role of the factore−pk/2e^\{\-p\_\{k\}/2\}is deliberate\. It is more probability than the theorem needs\. We spend the surplus by intersectingEkE\_\{k\}with the independent sampling event below\.

## 6Proof of the sharp tail

We use a standard one\-sided anti\-concentration fact\. A self\-contained block proof from the Paley–Zygmund inequality is included in Appendix[A\.6](https://arxiv.org/html/2608.24098#A1.SS6)\.

###### Lemma 5\(Rademacher lower tail\)\.

For all sufficiently largenn, every Rademacher sumTnT\_\{n\}and1≤p≤n1\\leq p\\leq nsatisfy

ℙ\(Tn≥164n​p\)≥18e−p/8\.\\mathbb\{P\}\\\!\\left\(T\_\{n\}\\geq\\frac\{1\}\{64\}\\sqrt\{np\}\\right\)\\geq\\frac\{1\}\{8\}e^\{\-p/8\}\.\(20\)For1≤p<161\\leq p<16, the probability on the left is at least0\.450\.45\.

The constants are elementary\. Paley–Zygmund and symmetry giveℙ⁡\(Vm≥m/2\)≥1/24\\mathbb\{P\}\(V\_\{m\}\\geq\\sqrt\{m/2\}\)\\geq 1/24for a Rademacher block sum\. Forp≥32​log⁡24p\\geq 32\\log 24, split the signs intoq=⌊p/\(16​log⁡24\)⌋q=\\lfloor p/\(16\\log 24\)\\rfloorblocks and require this event in every block, with a nonnegative leftover\. The resulting threshold is at leastn​p/64\\sqrt\{np\}/64and the probability is at least\(1/2\)24−q≥\(1/8\)e−p/8\(1/2\)24^\{\-q\}\\geq\(1/8\)e^\{\-p/8\}\. One block handles16≤p<32​log⁡2416\\leq p<32\\log 24\. Forp<16p<16, the maximum binomial atom boundn−1/2n^\{\-1/2\}gives the stated0\.450\.45\. Appendix[A\.6](https://arxiv.org/html/2608.24098#A1.SS6)records the arithmetic\.

LetFFbe the event that the memory indicesJ1,…,JnJ\_\{1\},\\ldots,J\_\{n\}are distinct\. SinceD=8​n2D=8n^\{2\},

ℙ⁡\(F\)≥1−n⁡\(n−1\)2​D≥1516\.\\mathbb\{P\}\(F\)\\geq 1\-\\frac\{n\(n\-1\)\}\{2D\}\\geq\\frac\{15\}\{16\}\.\(21\)OnFF, each observed cell contains one sign\. HencebJi​\(S\)=cmem​Σib\_\{J\_\{i\}\}\(S\)=c\_\{\\rm mem\}\\Sigma\_\{i\}and the middle term in \([15](https://arxiv.org/html/2608.24098#S4.E15)\) is exactlycmemc\_\{\\rm mem\}\.

Fixp∈\[16,c0​n\]p\\in\[16,c\_\{0\}n\], wherec0≤1/64c\_\{0\}\\leq 1/64\. If a scale is available, choose the largest availablepk≤pp\_\{k\}\\leq p\. In particular, this is the terminal scale whenppexceeds the largest constructed scale\. The geometric spacing gives

pk≥14​min⁡\{p,L/γ\}\.p\_\{k\}\\geq\\frac\{1\}\{4\}\\min\\\{p,L/\\gamma\\\}\.\(22\)On the independent intersection ofEkE\_\{k\},FF, and the event in Lemma[5](https://arxiv.org/html/2608.24098#Thmtheorem5)for∑iUi\\sum\_\{i\}U\_\{i\}, equations \([15](https://arxiv.org/html/2608.24098#S4.E15)\) and \([17](https://arxiv.org/html/2608.24098#S5.E17)\) give

GS≥c​min⁡\{L,γ​p\}\+c​L​p/n\.G\_\{S\}\\geq c\\min\\\{L,\\gamma p\\\}\+cL\\sqrt\{p/n\}\.\(23\)Its probability is at least

6e−pk/2⋅1516⋅18e−p/8≥e−p\.6e^\{\-p\_\{k\}/2\}\\cdot\\frac\{15\}\{16\}\\cdot\\frac\{1\}\{8\}e^\{\-p/8\}\\geq e^\{\-p\}\.The inequality usespk≤pp\_\{k\}\\leq pandp≥16p\\geq 16\.

If no scale is available, thenL/γ<16L/\\gamma<16\. In that casecmem≥L/64c\_\{\\rm mem\}\\geq L/64, which already gives a constant fraction ofmin⁡\{L,γ​p\}\\min\\\{L,\\gamma p\\\}\. Forp<16p<16, the same memory term gives a constant fraction ofmin⁡\{L,γ​p\}\\min\\\{L,\\gamma p\\\}\. We additionally require that no ramp is active\. Equation \([19](https://arxiv.org/html/2608.24098#S5.E19)\) shows that this event has probability above0\.970\.97\. A constant\-scale version of Lemma[5](https://arxiv.org/html/2608.24098#Thmtheorem5), together with \([21](https://arxiv.org/html/2608.24098#S6.E21)\), leaves probability abovee−pe^\{\-p\}and gives the requiredL​p/nL\\sqrt\{p/n\}term\. This proves Theorem[1](https://arxiv.org/html/2608.24098#Thmtheorem1)\.

## 7Discussion

#### The auxiliary lower bound is now realizable\.

The construction of[Bousquet et al\. \(2020\)](https://arxiv.org/html/2608.24098#bib.bib6)produces the quadratic Rademacher chaosγ⁡\(Tn2−n\)\\gamma\(T\_\{n\}^\{2\}\-n\), which has the right moments but arises from functions whose pointwise range isΘ⁡\(n​γ\)\\Theta\(n\\gamma\)\. The ramps in our construction move the large deviation into the feature index\. At any fixed test point, the loss reads a maximum and remains bounded\. At the training sample, a rare coordinate carries a persistent empirical bias\. This separates pointwise range from aggregate tail size\.

#### All confidence levels require multiple scales\.

A single ramp can match one prescribedpp, which would prove a pointwise minimax lower bound\. The geometric family is stronger\. Smaller ramps have at most one quarter of the target amplitude, while larger ramps are inactive with overwhelming probability\. This scale separation is why the same learner matches the full tail rather than a confidence level fixed in advance\.

#### Implication for stability\-based analyses\.

A common analysis of an optimizer first proves a uniform stability constant and then invokes a distribution\-free generalization theorem that sees only\(γ,L\)\(\\gamma,L\)\. Our lower bound shows that this black\-box second step must retain theγ​log⁡\(1/δ\)\\gamma\\log\(1/\\delta\)term\. A sharper guarantee for a particular optimizer must use more information, such as curvature, data\-dependent stability, algorithmic randomness, or representation constraints\.

#### The loss is standard, the learner is adversarial\.

Our predictor is scalar and is evaluated by absolute loss against the constant label zero\. The construction is nonetheless a worst\-case learner with exponentially many Rademacher features\. This multiplicity is deliberate\. A coordinate has upper\-tail probabilityq⋆=e−Θ⁡\(n\)q\_\{\\star\}=e^\{\-\\Theta\(n\)\}, and using on the order of1/q⋆1/q\_\{\\star\}independent coordinates makes one crossing occur at a controlled probability\. Within an independent\-threshold bank of this form, the union bound shows that polynomial multiplicity cannot suffice\. Probabilitye−pe^\{\-p\}requiresd≥e−p/q⋆≥en/64d\\geq e^\{\-p\}/q\_\{\\star\}\\geq e^\{n/64\}whenp≤n/64p\\leq n/64\. We do not claim that exponential dimension is necessary outside this mechanism\. It is the price paid by this construction to encode all confidence levels in one problem\. This is appropriate for determining what uniform stability alone can guarantee because that condition places no restriction on dimension\. Additional structure, such as convex optimization, a fixed low\-dimensional representation, or distributional stability, may yield smaller tails\. The theorem shows that such improvements cannot follow from uniform stability and bounded loss by themselves\.

#### Confidence range\.

The intervalp≤c​np\\leq cnis the natural nondegenerate range for bounded i\.i\.d\. sampling\. It is also the range in which the weak\-dependence lower bound of[Bousquet et al\. \(2020\)](https://arxiv.org/html/2608.24098#bib.bib6)has its two\-level form\. Beyond it, the loss\-range cap dominates and constants depend on how the extreme endpoint is parameterized\. Theorem[1](https://arxiv.org/html/2608.24098#Thmtheorem1)covers every confidence level used in the usual exponential generalization regime\.

## Reproducibility statement

The proof is finite and nonasymptotic\. The supplement gives every omitted constant calculation\. It also provides three short audit programs:extreme\_ramp\_check\.pyevaluates the exact binomial probabilities,multiscale\_check\.pychecks every scale and case split, andstability\_bruteforce\.pyexhausts the replacement inequalities on small instances\. These computations check the proof and are not used as assumptions\.

## References

- Bousquet and Elisseeff \(2002\)O\. Bousquet and A\. ElisseeffStability and generalization\.Journal of Machine Learning Research2,pp\. 499–526\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.p1.1),[§1](https://arxiv.org/html/2608.24098#S1.p2.1)\.
- Bousquetet al\.\(2020\)O\. Bousquet, Y\. Klochkov, and N\. ZhivotovskiySharper bounds for uniformly stable algorithms\.InProceedings of the 33rd Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.125,pp\. 610–626\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2608.24098#S1.p2.1),[§1](https://arxiv.org/html/2608.24098#S1.p3.1),[§7](https://arxiv.org/html/2608.24098#S7.SS0.SSS0.Px1.p1.1),[§7](https://arxiv.org/html/2608.24098#S7.SS0.SSS0.Px5.p1.1)\.
- Fan and Lei \(2024\)J\. Fan and Y\. LeiHigh\-probability generalization bounds for pointwise uniformly stable algorithms\.Applied and Computational Harmonic Analysis70,pp\. 101632\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1)\.
- Feldman and Vondrák \(2018\)V\. Feldman and J\. VondrákGeneralization bounds for uniformly stable algorithms\.InAdvances in Neural Information Processing Systems,Vol\.31,pp\. 9770–9780\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.p2.1)\.
- Feldman and Vondrák \(2019\)V\. Feldman and J\. VondrákHigh probability generalization bounds for uniformly stable algorithms with nearly optimal rate\.InProceedings of the 32nd Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.99,pp\. 1270–1279\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.p2.1)\.
- Hardtet al\.\(2016\)M\. Hardt, B\. Recht, and Y\. SingerTrain faster, generalize better: stability of stochastic gradient descent\.InProceedings of the 33rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.48,pp\. 1225–1234\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.p1.1)\.
- Klochkov and Zhivotovskiy \(2021\)Y\. Klochkov and N\. ZhivotovskiyStability and deviation optimal risk bounds with convergence rateO⁡\(1/n\)O\(1/n\)\.InAdvances in Neural Information Processing Systems,Vol\.34\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1)\.
- Leiet al\.\(2026\)Q\. Lei, S\. Bonnerjee, Y\. Han, and W\. B\. WuStability beyond bounded differences: sharp generalization bounds under finiteLpL\_\{p\}moments\.arXiv preprint arXiv:2606\.06855\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1)\.
- Liu and Lu \(2020\)Q\. Liu and Z\. LuA tight lower bound for uniformly stable algorithms\.arXiv preprint arXiv:2012\.13326\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2608.24098#S1.p3.1)\.
- Nguyen\-Cung and Nguyen \(2026\)T\. Nguyen\-Cung and B\. T\. NguyenLogarithmic\-free moment and generalization bounds for uniformly stable algorithms\.arXiv preprint arXiv:2608\.09870\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2608.24098#S1.p2.1),[§1](https://arxiv.org/html/2608.24098#S1.p3.1)\.
- Shalev\-Shwartzet al\.\(2010\)S\. Shalev\-Shwartz, O\. Shamir, N\. Srebro, and K\. SridharanLearnability, stability and uniform convergence\.Journal of Machine Learning Research11,pp\. 2635–2670\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.p1.1)\.
- Yuan and Li \(2022\)X\. Yuan and P\. LiBoosting the confidence of generalization forL2L\_\{2\}\-stable randomized learning algorithms\.arXiv preprint arXiv:2206\.03834\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1)\.
- Zhouet al\.\(2023\)S\. Zhou, Y\. Lei, and A\. KabánToward better PAC\-Bayes bounds for uniformly stable algorithms\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 29602–29614\.Cited by:[§1](https://arxiv.org/html/2608.24098#S1.SS0.SSS0.Px4.p1.1)\.

## Appendix ADetailed proofs

This appendix proves the claims in the main text with one concrete choice of the scale constants\. No optimization of numerical constants is intended\.

### A\.1Notation and elementary bounds

Letε1,…,εn\\varepsilon\_\{1\},\\ldots,\\varepsilon\_\{n\}be independent Rademacher signs andBn=∑iεiB\_\{n\}=\\sum\_\{i\}\\varepsilon\_\{i\}\. Define

k⋆=⌈5​n8⌉,s⋆=2​k⋆−n,q⋆=ℙ⁡\(Bn≥s⋆\)\.k\_\{\\star\}=\\left\\lceil\\frac\{5n\}\{8\}\\right\\rceil,\\qquad s\_\{\\star\}=2k\_\{\\star\}\-n,\\qquad q\_\{\\star\}=\\mathbb\{P\}\(B\_\{n\}\\geq s\_\{\\star\}\)\.Then

14≤s⋆n≤14\+2n\.\\frac\{1\}\{4\}\\leq\\frac\{s\_\{\\star\}\}\{n\}\\leq\\frac\{1\}\{4\}\+\\frac\{2\}\{n\}\.\(24\)Hoeffding’s inequality gives

q⋆≤exp\(−s⋆22​n\)≤e−n/32\.q\_\{\\star\}\\leq\\exp\\\!\\left\(\-\\frac\{s\_\{\\star\}^\{2\}\}\{2n\}\\right\)\\leq e^\{\-n/32\}\.\(25\)
Forr≤n/1024r\\leq n/1024, put

q⁡\(r\)=ℙ⁡\(Bn≥s⋆−2​r\)\.q\(r\)=\\mathbb\{P\}\(B\_\{n\}\\geq s\_\{\\star\}\-2r\)\.The event on the right contains the upper tail atk⋆k\_\{\\star\}and at mostrradditional binomial levels\. Moving down one level multiplies the point mass by

kn−k\+1≤5​n/8\+13​n/8−r<2\\frac\{k\}\{n\-k\+1\}\\leq\\frac\{5n/8\+1\}\{3n/8\-r\}<2for all sufficiently largenn\. Sinceq⋆q\_\{\\star\}is at least the mass atk⋆k\_\{\\star\}, we obtain

q⁡\(r\)q⋆≤\(r\+1\)​2r≤4r\.\\frac\{q\(r\)\}\{q\_\{\\star\}\}\\leq\(r\+1\)2^\{r\}\\leq 4^\{r\}\.\(26\)The last inequality holds for every integerr≥1r\\geq 1\.

### A\.2The symmetrized maximum

###### Proof of Lemma[3](https://arxiv.org/html/2608.24098#Thmtheorem3)\.

WriteMa​\(x\)=maxj⁡aj​xjM\_\{a\}\(x\)=\\max\_\{j\}a\_\{j\}x\_\{j\}\. Then

Ha​\(x\)=Ma​\(x\)−Ma​\(−x\)\.H\_\{a\}\(x\)=M\_\{a\}\(x\)\-M\_\{a\}\(\-x\)\.This immediately givesHa​\(−x\)=−Ha​\(x\)H\_\{a\}\(\-x\)=\-H\_\{a\}\(x\)\. Since eachaj​xja\_\{j\}x\_\{j\}lies in\[−‖a‖∞,‖a‖∞\]\[\-\\\|a\\\|\_\{\\infty\},\\\|a\\\|\_\{\\infty\}\], the range bound follows\. Finally,

\|Ma​\(x\)−Ma′​\(x\)\|≤maxj⁡\|\(aj−aj′\)​xj\|≤‖a−a′‖∞\.\|M\_\{a\}\(x\)\-M\_\{a^\{\\prime\}\}\(x\)\|\\leq\\max\_\{j\}\|\(a\_\{j\}\-a^\{\\prime\}\_\{j\}\)x\_\{j\}\|\\leq\\\|a\-a^\{\\prime\}\\\|\_\{\\infty\}\.Applying this inequality atxxand−x\-xand using the triangle inequality proves the final claim\. ∎

### A\.3The learner is stable and bounded

We verify the claims around \([12](https://arxiv.org/html/2608.24098#S3.E12)\)\. SupposeSSandS′S^\{\\prime\}differ at observationii\. For every ramp coordinate,

\|Sk​j−Sk​j′\|=\|Xi,k​j−Xi,k​j′\|≤2\.\|S\_\{kj\}\-S^\{\\prime\}\_\{kj\}\|=\|X\_\{i,kj\}\-X^\{\\prime\}\_\{i,kj\}\|\\leq 2\.The scalar map in \([10](https://arxiv.org/html/2608.24098#S3.E10)\) isγ/2\\gamma/2\-Lipschitz\. Therefore

‖a⁡\(S\)−a⁡\(S′\)‖∞≤γ\.\\\|a\(S\)\-a\(S^\{\\prime\}\)\\\|\_\{\\infty\}\\leq\\gamma\.\(27\)Lemma[3](https://arxiv.org/html/2608.24098#Thmtheorem3)implies that theH/4H/4term changes by at mostγ/2\\gamma/2at every test point\.

Only the old and new memory cells can change\. At either cell,bjb\_\{j\}takes values in\{−cmem,0,cmem\}\\\{\-c\_\{\\rm mem\},0,c\_\{\\rm mem\}\\\}, so

\|bj​\(S\)−bj​\(S′\)\|≤2​cmem≤γ/2\.\|b\_\{j\}\(S\)\-b\_\{j\}\(S^\{\\prime\}\)\|\\leq 2c\_\{\\rm mem\}\\leq\\gamma/2\.\(28\)For a fixed test point, only its own cell is read\. Adding \([27](https://arxiv.org/html/2608.24098#A1.E27)\) and \([28](https://arxiv.org/html/2608.24098#A1.E28)\) provesγ\\gamma\-uniform stability\.

If the scale set is nonempty, its largest element satisfiespK≤L/γp\_\{K\}\\leq L/\\gamma\. Thus

‖a⁡\(S\)‖∞≤γ​rK=γ​pK16≤L16\.\\\|a\(S\)\\\|\_\{\\infty\}\\leq\\gamma r\_\{K\}=\\frac\{\\gamma p\_\{K\}\}\{16\}\\leq\\frac\{L\}\{16\}\.\(29\)The same bound is trivial if there are no ramps\. Lemma[3](https://arxiv.org/html/2608.24098#Thmtheorem3)gives\|Ha​\(X\)\|/4≤L/32\|H\_\{a\}\(X\)\|/4\\leq L/32\. Since\|bJ​Σ\|≤L/8\|b\_\{J\}\\Sigma\|\\leq L/8and\|L​U/4\|=L/4\|LU/4\|=L/4,

3​L/32≤hS​\(Z\)≤29​L/32\.3L/32\\leq h\_\{S\}\(Z\)\\leq 29L/32\.This proves the range claim\. With regression label zero, absolute loss is exactlyhS​\(Z\)h\_\{S\}\(Z\)\.

For a fresh input,X​=𝑑−XX\\overset\{d\}\{=\}\-X, and Lemma[3](https://arxiv.org/html/2608.24098#Thmtheorem3)gives𝔼⁡\[Ha⁡\(S\)​\(X\)∣S\]=0\\mathbb\{E\}\[H\_\{a\(S\)\}\(X\)\\mid S\]=0\. The fresh signsΣ\\SigmaandUUare independent ofSSand centered\. This proves \([14](https://arxiv.org/html/2608.24098#S4.E14)\) and \([15](https://arxiv.org/html/2608.24098#S4.E15)\)\.

### A\.4Probability of a clean extreme

We prove the probability part of Lemma[4](https://arxiv.org/html/2608.24098#Thmtheorem4)\. For a scalepk=16​rk≤n/64p\_\{k\}=16r\_\{k\}\\leq n/64, equation \([25](https://arxiv.org/html/2608.24098#A1.E25)\) gives

q⋆≤e−2​pk\.q\_\{\\star\}\\leq e^\{\-2p\_\{k\}\}\.\(30\)By the definition ofdkd\_\{k\},

dk​q⋆\\displaystyle d\_\{k\}q\_\{\\star\}≥8e−pk/2−q⋆≥7e−pk/2,\\displaystyle\\geq 8e^\{\-p\_\{k\}/2\}\-q\_\{\\star\}\\geq 7e^\{\-p\_\{k\}/2\},dk​q⋆\\displaystyle d\_\{k\}q\_\{\\star\}≤8e−pk/2\.\\displaystyle\\leq 8e^\{\-p\_\{k\}/2\}\.\(31\)In particular,dk≥2d\_\{k\}\\geq 2\.

The clean event forbids every nonexceptional coordinate whose score is at leasttk=s⋆−2​rkt\_\{k\}=s\_\{\\star\}\-2r\_\{k\}\. Equations \([26](https://arxiv.org/html/2608.24098#A1.E26)\) and \([31](https://arxiv.org/html/2608.24098#A1.E31)\) show

dkq\(rk\)≤8e−pk/24rk≤8e−3pk/8,d\_\{k\}q\(r\_\{k\}\)\\leq 8e^\{\-p\_\{k\}/2\}4^\{r\_\{k\}\}\\leq 8e^\{\-3p\_\{k\}/8\},\(32\)because4rk=e\(log⁡4\)​pk/16<epk/84^\{r\_\{k\}\}=e^\{\(\\log 4\)p\_\{k\}/16\}<e^\{p\_\{k\}/8\}\. The same inequality holds at every larger scale\. Sincepk\+j=4j​pkp\_\{k\+j\}=4^\{j\}p\_\{k\},

∑ℓ≥kdℓ​q​\(rℓ\)≤8​∑j≥0exp⁡\(−38​4j​pk\)<0\.021\\sum\_\{\\ell\\geq k\}d\_\{\\ell\}q\(r\_\{\\ell\}\)\\leq 8\\sum\_\{j\\geq 0\}\\exp\\\!\\left\(\-\\frac\{3\}\{8\}4^\{j\}p\_\{k\}\\right\)<0\.021\(33\)forpk≥16p\_\{k\}\\geq 16\.

Choose which coordinate in groupkkis the exceptional one\. Independence of all Rademacher coordinates gives

ℙ⁡\(Ek\)\\displaystyle\\mathbb\{P\}\(E\_\{k\}\)=dk​q⋆​\(1−q⁡\(rk\)\)dk−1​∏ℓ\>k\(1−q⁡\(rℓ\)\)dℓ\\displaystyle=d\_\{k\}q\_\{\\star\}\(1\-q\(r\_\{k\}\)\)^\{d\_\{k\}\-1\}\\prod\_\{\\ell\>k\}\(1\-q\(r\_\{\\ell\}\)\)^\{d\_\{\\ell\}\}\(34\)≥dk​q⋆​\(1−∑ℓ≥kdℓ​q​\(rℓ\)\)\\displaystyle\\geq d\_\{k\}q\_\{\\star\}\\left\(1\-\\sum\_\{\\ell\\geq k\}d\_\{\\ell\}q\(r\_\{\\ell\}\)\\right\)\(35\)≥7e−pk/2\(1−0\.021\)≥6e−pk/2\.\\displaystyle\\geq 7e^\{\-p\_\{k\}/2\}\(1\-0\.021\)\\geq 6e^\{\-p\_\{k\}/2\}\.\(36\)The second line is the union bound applied to all forbidden coordinates\. This proves \([16](https://arxiv.org/html/2608.24098#S5.E16)\)\.

### A\.5Gap on the clean extreme event

OnEkE\_\{k\}, let\(k,j⋆\)\(k,j\_\{\\star\}\)denote the exceptional coordinate and puta=γ​rka=\\gamma r\_\{k\}\. Its score is at leasts⋆=tk\+2​rks\_\{\\star\}=t\_\{k\}\+2r\_\{k\}, so its ramp reaches the capaa\. Every other coordinate in groupkkor a larger group has amplitude zero\. Every smaller scale has cap at mosta/4a/4\.

Writexi⋆=Xi,k​j⋆x\_\{i\}^\{\\star\}=X\_\{i,kj\_\{\\star\}\}and letn\+n\_\{\+\}andn−n\_\{\-\}count its positive and negative signs\. There is at least one zero\-amplitude coordinate becausedk≥2d\_\{k\}\\geq 2\. Ifxi⋆=1x\_\{i\}^\{\\star\}=1, the first maximum inHHisaaand the second is at mosta/4a/4, so

Ha⁡\(S\)​\(Xi\)≥3​a/4\.H\_\{a\(S\)\}\(X\_\{i\}\)\\geq 3a/4\.\(37\)Ifxi⋆=−1x\_\{i\}^\{\\star\}=\-1, the second maximum isaaand the first is at least zero, so

Ha⁡\(S\)​\(Xi\)≥−a\.H\_\{a\(S\)\}\(X\_\{i\}\)\\geq\-a\.\(38\)Letρ=\(n\+−n−\)/n\\rho=\(n\_\{\+\}\-n\_\{\-\}\)/n\. Equations \([37](https://arxiv.org/html/2608.24098#A1.E37)\) and \([38](https://arxiv.org/html/2608.24098#A1.E38)\) imply

1n​∑iHa⁡\(S\)​\(Xi\)\\displaystyle\\frac\{1\}\{n\}\\sum\_\{i\}H\_\{a\(S\)\}\(X\_\{i\}\)≥3​a4​1\+ρ2−a​1−ρ2=a⁡\(78​ρ−18\)\.\\displaystyle\\geq\\frac\{3a\}\{4\}\\frac\{1\+\\rho\}\{2\}\-a\\frac\{1\-\\rho\}\{2\}=a\\left\(\\frac\{7\}\{8\}\\rho\-\\frac\{1\}\{8\}\\right\)\.\(39\)OnEkE\_\{k\},ρ≥s⋆/n≥1/4\\rho\\geq s\_\{\\star\}/n\\geq 1/4\. The right side of \([39](https://arxiv.org/html/2608.24098#A1.E39)\) is increasing inρ\\rho, so it is at least3​a/323a/32\. Substitutinga=γ​rk=γ​pk/16a=\\gamma r\_\{k\}=\\gamma p\_\{k\}/16proves \([17](https://arxiv.org/html/2608.24098#S5.E17)\)\.

### A\.6Rademacher anti\-concentration

We give an elementary block proof of Lemma[5](https://arxiv.org/html/2608.24098#Thmtheorem5)\. IfVmV\_\{m\}is a sum ofmmindependent Rademacher signs, then

𝔼​Vm2=m,𝔼​Vm4=3​m2−2​m≤3​m2\.\\mathbb\{E\}V\_\{m\}^\{2\}=m,\\qquad\\mathbb\{E\}V\_\{m\}^\{4\}=3m^\{2\}\-2m\\leq 3m^\{2\}\.Paley–Zygmund applied toVm2V\_\{m\}^\{2\}therefore gives

ℙ⁡\(\|Vm\|≥m/2\)≥112\.\\mathbb\{P\}\\\!\\left\(\|V\_\{m\}\|\\geq\\sqrt\{m/2\}\\right\)\\geq\\frac\{1\}\{12\}\.\(40\)By symmetry, either one\-sided event has probability at least1/241/24\.

Partition the firstq​mqmsigns ofTnT\_\{n\}intoqqblocks of sizem=⌊n/q⌋m=\\lfloor n/q\\rfloor, leaving at mostq−1q\-1signs\. If every block sum is at leastm/2\\sqrt\{m/2\}and the leftover sum is nonnegative, then, wheneverq≤n/2q\\leq n/2,

Tn≥q​m/2≥12​n​q\.T\_\{n\}\\geq q\\sqrt\{m/2\}\\geq\\frac\{1\}\{2\}\\sqrt\{nq\}\.\(41\)The event has probability at least

12​24−q\.\\frac\{1\}\{2\}\\,24^\{\-q\}\.\(42\)We now track constants\. First suppose1≤p<161\\leq p<16\. The largest atom ofTnT\_\{n\}is at mostn−1/2n^\{\-1/2\}by the central binomial coefficient bound\. Positive attainable values are spaced by two, so there are at mostn/32\+1\\sqrt\{n\}/32\+1of them belown/16\\sqrt\{n\}/16\. Symmetry gives

ℙ⁡\(Tn≥n/16\)≥12−12​n−\(132\+1n\)=1532−32​n≥0\.45\\mathbb\{P\}\(T\_\{n\}\\geq\\sqrt\{n\}/16\)\\geq\\frac\{1\}\{2\}\-\\frac\{1\}\{2\\sqrt\{n\}\}\-\\left\(\\frac\{1\}\{32\}\+\\frac\{1\}\{\\sqrt\{n\}\}\\right\)=\\frac\{15\}\{32\}\-\\frac\{3\}\{2\\sqrt\{n\}\}\\geq 0\.45\(43\)for all sufficiently largenn\. Sincep<16p<16, the threshold is at leastn​p/64\\sqrt\{np\}/64\.

For16≤p<32​log⁡2416\\leq p<32\\log 24, use one block\. Equations \([40](https://arxiv.org/html/2608.24098#A1.E40)\) and symmetry give

ℙ\(Tn≥n/2\)≥1/24≥\(1/8\)e−p/8,\\mathbb\{P\}\(T\_\{n\}\\geq\\sqrt\{n/2\}\)\\geq 1/24\\geq\(1/8\)e^\{\-p/8\},andn/2≥n​p/64\\sqrt\{n/2\}\\geq\\sqrt\{np\}/64\. Finally, suppose32​log⁡24≤p≤n32\\log 24\\leq p\\leq nand take

q=⌊p16​log⁡24⌋\.q=\\left\\lfloor\\frac\{p\}\{16\\log 24\}\\right\\rfloor\.Thenp/\(32​log⁡24\)≤q≤p/\(16​log⁡24\)p/\(32\\log 24\)\\leq q\\leq p/\(16\\log 24\)andq≤n/2q\\leq n/2\. Equations \([41](https://arxiv.org/html/2608.24098#A1.E41)\) and \([42](https://arxiv.org/html/2608.24098#A1.E42)\) yield

Tn≥12​32​log⁡24​n​p≥164​n​pT\_\{n\}\\geq\\frac\{1\}\{2\\sqrt\{32\\log 24\}\}\\sqrt\{np\}\\geq\\frac\{1\}\{64\}\\sqrt\{np\}with probability at least

1224−q≥12e−p/16≥18e−p/8\.\\frac\{1\}\{2\}24^\{\-q\}\\geq\\frac\{1\}\{2\}e^\{\-p/16\}\\geq\\frac\{1\}\{8\}e^\{\-p/8\}\.The three ranges prove Lemma[5](https://arxiv.org/html/2608.24098#Thmtheorem5)with no asymptotic normal approximation\.

### A\.7Small scales, saturation, and simultaneity

We fill in the cases abbreviated in the main proof\. First, the memory indices are distinct with probability at least15/1615/16by \([21](https://arxiv.org/html/2608.24098#S6.E21)\)\. On this event,

1n​∑ibJi​\(S\)​Σi=cmem\.\\frac\{1\}\{n\}\\sum\_\{i\}b\_\{J\_\{i\}\}\(S\)\\Sigma\_\{i\}=c\_\{\\rm mem\}\.\(44\)
Suppose1≤p<161\\leq p<16\. Ifγ≤L/2\\gamma\\leq L/2, thencmem=γ/4c\_\{\\rm mem\}=\\gamma/4and

cmem≥164​min⁡\{L,γ​p\}\.c\_\{\\rm mem\}\\geq\\frac\{1\}\{64\}\\min\\\{L,\\gamma p\\\}\.Ifγ\>L/2\\gamma\>L/2, thencmem=L/8c\_\{\\rm mem\}=L/8and the same inequality is immediate\. The probability that any ramp is active is at most the sum in \([33](https://arxiv.org/html/2608.24098#A1.E33)\), hence below0\.0210\.021\. By the compact\-interval part of Lemma[5](https://arxiv.org/html/2608.24098#Thmtheorem5), the sampling event can be chosen to have probability at least0\.450\.45while still giving a universal multiple ofL​p/nL\\sqrt\{p/n\}\. The three events are independent, and0\.979⋅\(15/16\)⋅0\.45\>e−10\.979\\cdot\(15/16\)\\cdot 0\.45\>e^\{\-1\}\. Their intersection therefore exceedse−pe^\{\-p\}\. This proves \([5](https://arxiv.org/html/2608.24098#S2.E5)\) forp<16p<16\.

Now supposep≥16p\\geq 16butL/γ<16L/\\gamma<16\. Thenγ\>L/16\\gamma\>L/16and

cmem=min⁡\{γ/4,L/8\}≥L/64\.c\_\{\\rm mem\}=\\min\\\{\\gamma/4,L/8\\\}\\geq L/64\.\(45\)Thus memory alone supplies a constant fraction of the saturated stability term\. Intersecting \([44](https://arxiv.org/html/2608.24098#A1.E44)\) with Lemma[5](https://arxiv.org/html/2608.24098#Thmtheorem5)proves the result\.

It remains to justify \([22](https://arxiv.org/html/2608.24098#S6.E22)\)\. LetP=min⁡\{n/64,L/γ\}P=\\min\\\{n/64,L/\\gamma\\\}\. IfP≥16P\\geq 16, the largest geometric scale belowPPis greater thanP/4P/4\. For a queryp≤c0​n≤n/64p\\leq c\_\{0\}n\\leq n/64, the largest available scale not exceedingpp, or the terminal scale ifp\>Pp\>P, therefore obeys

pk≥14​min⁡\{p,L/γ\}\.p\_\{k\}\\geq\\frac\{1\}\{4\}\\min\\\{p,L/\\gamma\\\}\.The construction of all groups uses only\(n,L,γ\)\(n,L,\\gamma\)\. It is completed beforeppis chosen\. Thus the proof supplies the probability statement for allppusing the same distribution and algorithm\. This establishes the simultaneity claimed in Theorem[1](https://arxiv.org/html/2608.24098#Thmtheorem1)\.

Finally, on the intersection used in the proof,

GS\\displaystyle G\_\{S\}≥14​3​γ​pk512\+cmem\+c​L4​p/n\\displaystyle\\geq\\frac\{1\}\{4\}\\frac\{3\\gamma p\_\{k\}\}\{512\}\+c\_\{\\rm mem\}\+\\frac\{cL\}\{4\}\\sqrt\{p/n\}\(46\)≥c′​\(min⁡\{L,γ​p\}\+L​p/n\)\\displaystyle\\geq c^\{\\prime\}\\left\(\\min\\\{L,\\gamma p\\\}\+L\\sqrt\{p/n\}\\right\)\(47\)≥c′​min⁡\{L,γ​p\+L​p/n\}\.\\displaystyle\\geq c^\{\\prime\}\\min\\\!\\left\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\right\\\}\.\(48\)This also makes clear that every term is one\-sided and no cancellation is used\.

### A\.8Moment consequence

Let

up=c1​min⁡\{L,γ​p\+L​p/n\}\.u\_\{p\}=c\_\{1\}\\min\\\!\\left\\\{L,\\gamma p\+L\\sqrt\{p/n\}\\right\\\}\.Theorem[1](https://arxiv.org/html/2608.24098#Thmtheorem1)givesℙ⁡\(GS≥up\)≥e−p\\mathbb\{P\}\(G\_\{S\}\\geq u\_\{p\}\)\\geq e^\{\-p\}\. Hence

‖GS‖pp≥upp​e−p,‖GS‖p≥e−1​up\.\\\|G\_\{S\}\\\|\_\{p\}^\{p\}\\geq u\_\{p\}^\{p\}e^\{\-p\},\\qquad\\\|G\_\{S\}\\\|\_\{p\}\\geq e^\{\-1\}u\_\{p\}\.This proves Corollary[2](https://arxiv.org/html/2608.24098#Thmtheorem2)\. The upper direction of \([7](https://arxiv.org/html/2608.24098#S2.E7)\) is \([1](https://arxiv.org/html/2608.24098#S1.E1)\) combined with\|GS\|≤L\|G\_\{S\}\|\\leq L\. The lower direction is the corollary\.

## Appendix BAI Use

LLM\-based tools were used to assist with proofs and language editing\.

## Appendix CExact computational audits

The construction contains only binomial probabilities and maximum inequalities\. We nevertheless performed three audits\.

#### Exact clean\-event probabilities\.

For eachn∈\{4096,8192,16384,32768,65536\}n\\in\\\{4096,8192,16384,32768,65536\\\}and every geometric scale belown/64n/64, we evaluatedq⋆q\_\{\\star\}, each lowered tailq⁡\(rk\)q\(r\_\{k\}\), the floor indkd\_\{k\}, and the exact product in \([36](https://arxiv.org/html/2608.24098#A1.E36)\) in log space\. Table[1](https://arxiv.org/html/2608.24098#A3.T1)shows representative results\. The final column divides the rigorous clean\-event lower bound bye−pk/2e^\{\-p\_\{k\}/2\}\. The analytic proof uses the weaker constant66\.

Table 1:Exact audit of the multiscale event\.
#### Exhaustive stability audit\.

Forn=d=3n=d=3, we enumerated every Rademacher dataset, every one\-point replacement, and every test input\. We separately enumerated every memory dataset with three cells\. Withγ=0\.2\\gamma=0\.2, the largest ramp loss change was0\.10\.1, the largest memory loss change was0\.10\.1, and their sum was exactly0\.20\.2\. The maximum coordinate\-amplitude change was exactlyγ\\gamma\. This checks the sharp cases of \([27](https://arxiv.org/html/2608.24098#A1.E27)\) and \([28](https://arxiv.org/html/2608.24098#A1.E28)\)\.

The audit scripts use exact enumeration for stability and double\-precision log binomial masses for the probability calculation\. The displayed margins are several orders of magnitude larger than floating\-point error\.