PaperlayerView exact revision on arXiv

Source-linked AI summary

The Sharp Tail of Uniform Stability

Pahan Dewasurendra

arXiv:2608.24098v1cs.LG

TL;DR

Whether bounded-loss uniformly stable learning algorithms can attain a generalization gap linear in log(1/δ) has been open. This paper constructs a single deterministic stable regression problem matching the sharp tail across confidence levels, establishing optimal dependence up to universal constants.

  • Problem

    Whether bounded-loss uniformly stable learning algorithms can realize a generalization gap linear in log(1/δ) remained unresolved beyond constant-probability lower bounds.

  • Method

    The paper uses multiscale rare Rademacher features, coordinatewise stable ramps, and an odd symmetrized maximum in bounded absolute-loss regression.

  • Results

    Ω(γ log(1/δ)) high-probability generalization gaps are achieved by one deterministic bounded-loss γ-uniformly stable learner across all confidence levels p ≤ cn.

  • Takeaways & Limitations

    Uniform stability and bounded loss alone cannot remove the γ log(1/δ) term from distribution-free high-probability guarantees.

  • Takeaways & Limitations

    The theorem covers the usual exponential generalization regime p ≤ cn; beyond it, the loss-range cap dominates and endpoint parameterization affects constants.

Abstract

from arXiv · show

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 $γ$-uniformly stable algorithm with loss in $[0,L]$ has generalization gap at most $O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right)$ with probability $1-δ$. Whether an actual bounded-loss learning algorithm can realize the linear dependence on $\log(1/δ)$ has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with $n$. The known learning lower bound holds only at constant probability. We close this gap. For every $n$, stability level $γ$, and loss bound $L$, we construct one deterministic $γ$-uniformly stable learning problem whose tail satisfies, simultaneously for $1\le p\le c n$, $\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge 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$ without 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.

1 INTRODUCTION

The paper closes the gap between logarithmic-free stability upper bounds and bounded-loss lower bounds by constructing one deterministic, uniformly stable regression problem whose generalization-gap tail matches the full confidence curve. Its multiscale rare-feature construction realizes the γp term while preserving bounded absolute loss and uniform stability over all replacement datasets.

  • Mechanism: Rare Rademacher features, coordinatewise stable ramps, and an odd symmetrized maximum convert a unique extreme crossing into a generalization gap of order γp.Geometrically spaced ramp widths place all scales in one learner, while sampling and memorization terms supply the remaining tail regimes.
  • Contribution: One finite-dimensional problem realizes the full tail curve simultaneously at confidence levels e^-p for 1 ≤ p ≤ cn.The construction is not a different learning problem selected separately for each p.
  • Motivation: Clipping the natural quadratic Rademacher construction at loss range L destroys the γp tail precisely when that term begins to dominate L.The prediction amplitude reaches the clipping threshold around p ≳ L^2/(γ^2n).
  • Contribution: Ω(γ log(1/δ)) is achieved by a bounded-loss uniformly stable learner, resolving the open small-failure-probability lower-bound question.Earlier bounded-loss learning lower bounds established only Ω(γ + L/√n) at constant probability.
  • Construction: The learner is deterministic, uses standard absolute-loss regression with constant labels, and is uniformly stable over every replacement dataset.The stability guarantee holds globally rather than only on the high-probability event.

2 SETUP AND RESULT

The theorem constructs a deterministic γ-uniformly stable bounded-loss regression problem whose lower tail matches the sharp γp + L√(p/n) dependence across p up to a constant fraction of n. Because one problem works simultaneously for all confidence levels, it also establishes moment sharpness and the minimax law up to universal constants.

  • Theorem 1: Sharp lower tail: The hard problem may depend on (n, L, γ), but crucially not on p or δ, enabling simultaneous guarantees across confidence levels.The regression labels are identically zero.
  • Corollary 2: Moment sharpness: The simultaneous lower-tail statement immediately yields moment sharpness for every p ∈ [2, c0n].The stated moment lower bound follows because the tail event contributes at least e^-1 times its displayed threshold to the Lp norm.
  • Minimax consequence: Combining moment sharpness with the logarithmic-free upper bound and the range bound determines the minimax law, with universal upper and lower constants.The supremum ranges over γ-stable algorithms with loss in [0, L].

3 THE MULTISCALE LEARNER

The multiscale learner uses independent Rademacher features organized across geometrically spaced scales to create one learning problem supporting all relevant p. It combines bounded absolute-loss regression with ramp amplitudes and a symmetrized maximum.

  • Random features: Independent Rademacher coordinates, a uniform scale index, and independent signs form the learner’s random input, with coordinates divided into geometrically indexed groups.All components are independent, and the feature dimension is partitioned by a geometric set of scales.
  • Scale selection: p_k = 16 · 4^k and r_k = 4^k, with p_k ≤ min{n/64, L/γ}, determine the attainable scale parameters.The construction uses the first attainable score s⋆ ≥ n/4 from a sum of n independent Rademacher signs.
  • Finite construction: The total feature dimension is finite and typically exponential in n because q⋆ = e^−Θ(n).A dummy zero-amplitude coordinate is used when the scale set is empty.
  • Predictor: The predictor collects coordinatewise ramp amplitudes into a(S) and applies the symmetrized maximum H_a.This aggregation is the mechanism used to combine the ramp outputs across the multiscale feature collection.
  • Bounded-loss problem: The regression label is zero, the loss is absolute error, and the predictor satisfies h_S ∈ [0, L], making the loss equal to h_S.Thus the construction is an ordinary bounded-loss regression problem with constant labels.

4 STABILITY AND CENTERING

The construction combines symmetrized-maximum Lipschitz properties with coordinatewise stability and centered fresh randomness. These properties preserve bounded loss while creating the exact centering identity that links rare features to generalization.

  • Symmetrized maximum: The symmetrized maximum is odd and satisfies |H_a(x)| ≤ 2∥a∥∞ and |H_a(x) − H_a′(x)| ≤ 2∥a − a′∥∞.These are the stated properties for nonnegative vectors and sign vectors.
  • Stability: γ: replacing one training point changes the ramp coefficients by at most γ, while the H/4 and memory terms each change by at most γ/2.The U term is sample-independent, so the total change proves the stability condition.
  • Bounded loss: 13L/32: the sample-dependent offset from L/2 is bounded by L/32 + L/8 + L/4.The bound uses the largest ramp cap, the symmetrized maximum, and the memory term.
  • Centering: Every sample has a centered fresh-feature contribution because fresh X is symmetric, while fresh Σ and U are centered.Conditioning on the training sample gives E H_a(S)(X) = 0.
  • Centering: The exact centering identity serves as the bridge from rare features to generalization.This is the stated role of the identity in the construction.

5 RARE EXTREMES CREATE THE LINEAR TAIL

Rare-extreme events isolate one unusually large feature at each geometric scale, while suppressing competing features in the same and larger groups. On these events, the exceptional coordinate reaches its cap and dominates smaller-scale contributions, producing the desired linear-tail mechanism.

  • Clean extreme: At scale k, event E_k requires exactly one coordinate to exceed s⋆ while all other coordinates in group k and larger groups remain below their thresholds.Coordinates in smaller groups are unrestricted.
  • Clean extreme: Lemma 4 establishes the clean-extreme event for every scale in (8).
  • Clean extreme: The geometric scale construction bounds the combined expected number of forbidden-threshold exceedances from group k upward below 0.021, yielding the clean-extreme probability result.The scales grow by four, and independence across coordinates plus a union bound completes the argument.
  • Dominance of the extreme: On E_k, the exceptional coordinate reaches cap a = γr_k, while smaller-group amplitudes are at most a/4 and competing coordinates in the same or larger groups vanish.
  • Dominance of the extreme: The geometric cap prevents smaller scales from reversing the exceptional feature’s contribution, proving the required lower-bound relation.Although smaller scales may fire, their amplitudes are too weak to dominate.
  • Probability budget: The event probability includes deliberate surplus, allowing E_k to be intersected with an independent sampling event needed later.The factor e^−p_k/2 provides more probability than the theorem requires.

6 PROOF OF THE SHARP TAIL

The proof combines a Rademacher lower-tail lemma with distinct-memory events and geometrically spaced ramps to establish the sharp tail simultaneously across confidence levels. These ingredients yield the required e^-p probability and complete Theorem 1.

  • Memory contribution: On the distinct-memory event F, each observed cell contains one sign, making the relevant middle term exactly c_mem.The proof defines F through distinct memory indices and uses this identity in the gap calculation.
  • Geometric scales: For p ∈ [16, c_0n] with c_0 ≤ 1/64, selecting the largest available geometric scale p_k ≤ p and intersecting the key events produces the desired lower-tail bound.The resulting event probability is bounded below by 6e^-p_k/2 · 15/16 · 1/8e^-p/8 ≥ e^-p.
  • Small and terminal regimes: When no scale is available or p < 16, the memory term supplies a constant fraction of min{L, γp}, while requiring no active ramp retains probability above e^-p.If L/γ < 16, then c_mem ≥ L/64; the no-ramp event has probability above 0.97.
  • Conclusion: The combined estimates establish the p/n term and prove Theorem 1.The argument covers the required regimes and completes the sharp-tail lower bound.

7 DISCUSSION

The construction makes the auxiliary lower bound realizable with bounded absolute-loss regression and shows that uniform-stability analyses must retain the γ log(1/δ) term. Geometric scales encode all confidence levels simultaneously, while exponential feature multiplicity is the construction’s price and the result applies throughout p ≤ cn.

  • Construction: Bounded ramps move large deviations into the feature index: fixed-point losses remain bounded while rare training coordinates create persistent empirical bias.This separates pointwise loss range from aggregate tail size and realizes the auxiliary lower-bound mechanism.
  • Construction: Geometric ramp scales match the full tail rather than one prescribed confidence level.Smaller ramps stay below one quarter of the target amplitude, while larger ramps are overwhelmingly inactive.
  • Implications: Uniform-stability-only guarantees must retain the γ log(1/δ) term; sharper optimizer-specific bounds require additional information.Suggested information includes curvature, data-dependent stability, algorithmic randomness, or representation constraints.
  • Limitations: e^-p failure probabilities require d ≥ e^-p/q⋆ ≥ e^(n/64) when p ≤ n/64 in the independent-threshold mechanism.Polynomial multiplicity cannot suffice there; exponential dimension is identified as the construction’s price for encoding all confidence levels.
  • Limitations: The lower-bound confidence range is p ≤ cn, the natural nondegenerate regime for bounded i.i.d. sampling.Beyond this range, the loss-range cap dominates and constants depend on the parameterization of the extreme endpoint.

REPRODUCIBILITY STATEMENT

The proof is finite and nonasymptotic, with omitted constants supplied in the supplement and three audit programs checking its calculations and inequalities.

  • REPRODUCIBILITY STATEMENT: The supplement provides every omitted constant calculation and three audit programs for binomial probabilities, multiscale case splits, and replacement inequalities.The programs are extreme_ramp_check.py, multiscale_check.py, and stability_bruteforce.py; they check the proof rather than serving as assumptions.

A DETAILED PROOFS … A.3 THE LEARNER IS STABLE AND BOUNDED

The appendix establishes the construction’s key properties through binomial-tail estimates, symmetrized-maximum identities, and direct stability and range checks. The learner is shown to be γ-uniformly stable, bounded, and equivalent to absolute loss with zero regression labels.

  • A.1 NOTATION AND ELEMENTARY BOUNDS: Hoeffding’s inequality bounds the relevant Rademacher/binomial upper tail, with the event containing the level k⋆ tail and at most r additional levels.The proof also compares successive binomial point masses and notes the resulting inequality holds for every integer r ≥1.
  • A.2 THE SYMMETRIZED MAXIMUM: The symmetrized maximum is odd, satisfying Ha(−x) = −Ha(x), while its range follows from each ajxj lying in [−∥a∥∞, ∥a∥∞].Applying the defining inequality at x and −x and using the triangle inequality proves the final claim.
  • A.3 THE LEARNER IS STABLE AND BOUNDED: γ/2 bounds the change in the H/4 term at every test point when datasets differ in one observation.This is obtained from Lemma 3 for every ramp coordinate.
  • A.3 THE LEARNER IS STABLE AND BOUNDED: Only the old and new memory cells can change, and each bj takes values in {−cmem, 0, cmem}.The proof uses this restricted cellwise range to control the memory contribution to sensitivity.
  • A.3 THE LEARNER IS STABLE AND BOUNDED: Adding the ramp and memory bounds proves γ-uniform stability because each fresh test point reads only its own cell.The argument explicitly combines inequalities (27) and (28).
  • A.3 THE LEARNER IS STABLE AND BOUNDED: pK ≤L/γ bounds the largest scale when the scale set is nonempty, while the no-ramp case is handled trivially.The resulting range estimate also uses |Ha(X)|/4 ≤L/32, |bJΣ| ≤L/8, and |LU/4| = L/4.
  • A.3 THE LEARNER IS STABLE AND BOUNDED: The range claim follows, and with regression label zero, absolute loss is exactly hS(Z).The proof also uses centered fresh signs and E[Ha(S)(X) | S] = 0 to establish the stated expectation identities.

A.4 PROBABILITY OF A CLEAN EXTREME … A.8 MOMENT CONSEQUENCE

The appendix establishes the clean-extreme probability and converts it into a one-sided generalization gap, while proving the needed Rademacher anti-concentration without asymptotic approximation. It also handles small scales and saturation, shows simultaneity over all queried p, and derives the moment consequence.

  • A.4 PROBABILITY OF A CLEAN EXTREME: A.4 PROBABILITY OF A CLEAN EXTREME: The clean-event argument proves the required probability bound for an exceptional coordinate at each scale.
  • A.5 GAP ON THE CLEAN EXTREME EVENT: A.5 GAP ON THE CLEAN EXTREME EVENT: 3a/32 is a lower bound for the gap contribution, with a = γr_k = γp_k/16.The exceptional ramp reaches cap a, while larger-scale coordinates vanish and smaller scales have cap at most a/4.
  • A.6 RADEMACHER ANTI-CONCENTRATION: A.6 RADEMACHER ANTI-CONCENTRATION: 1/8e^-p/8 is a probability lower bound obtained in the intermediate p range.The three ranges prove the lemma without using an asymptotic normal approximation.
  • A.7 SMALL SCALES, SATURATION, AND SIMULTANEITY: A.7 SMALL SCALES, SATURATION, AND SIMULTANEITY: 0.979 · (15/16) · 0.45 > e^-1 ensures the intersected events prove the result for p < 16.For larger p with L/γ < 16, memory supplies a constant fraction of the saturated stability term.
  • A.7 SMALL SCALES, SATURATION, AND SIMULTANEITY: A.7 SMALL SCALES, SATURATION, AND SIMULTANEITY: The construction depends only on (n, L, γ), so one distribution and algorithm establish the probability statement simultaneously for all p.The geometric scales are completed before p is chosen.
  • A.8 MOMENT CONSEQUENCE: A.8 MOMENT CONSEQUENCE: The upper direction follows from (1) combined with |G_S| ≤ L, while the lower direction is the corollary.

C EXACT COMPUTATIONAL AUDITS

The paper validates its construction through exact probability calculations and exhaustive stability enumeration. These audits confirm the sharp stability cases and report numerical margins safely above floating-point error.

  • Exact clean-event probabilities: Exact probability audits evaluated q⋆, lowered tails, floor values, and clean-event products for five n values across geometric scales.The calculations used log space, and the rigorous lower bound was compared with e^(-p_k/2), while the proof uses the weaker constant 6.
  • Exhaustive stability audit: Exhaustive enumeration at n = d = 3 found maximum ramp and memory loss changes of 0.1 each, summing exactly to γ = 0.2.The maximum coordinate-amplitude change was exactly γ, checking the sharp cases of (27) and (28).
  • Audit implementation: The audits used exact enumeration for stability and double-precision log binomial masses for probability calculations.Displayed margins were several orders of magnitude larger than floating-point error.
Loading 2608.24098v1…