On Local Population-Risk Certificates
arXiv:2606.19147v1 [stat.ML] 17 Jun 2026
Mingzhi Song∗
Abstract This paper develops local certificates for population-risk increments around a current model. For a local candidate set D, the certificate is a two-sided confidence band for P (ℓθ+v − ℓθ ) over v ∈ D. As an application, the upper endpoint of this band yields a risk-controlled update rule: an update is accepted only when its certified upper endpoint is nonpositive; otherwise the current model is retained.
1
Introduction
Let R(η) := P ℓη denote the population risk of a model indexed by η, where P is the target distribution and ℓη is the loss. A basic inferential problem is to determine, from data, the range of this risk on a local parameter set θ + D. Equivalently, for δv (z) := ℓθ+v (z) − ℓθ (z), one may study the local generalized-error map v 7−→ P δv = R(θ + v) − R(θ),
v ∈ D.
It describes how much the population risk can change in a neighborhood of a fixed model. This paper develops computable certificates for this local risk map. For a current parameter θ, a candidate set D ∋ 0, and a certification sample, the goal is to construct random functions b b θ,D such that Lθ,D and U n o b b P Lθ,D (v) ≤ P δv ≤ Uθ,D (v) for all v ∈ D ≥ 1 − α. If the loss is nonsmooth, standard Taylor expansions may fail exactly on the observations that determine the local change in risk. Least absolute-deviation, quantile, hinge-type, and active-set losses all have this feature: along the path θ + sv, an observation may cross an interface at which the active smooth formula changes. Ignoring such crossings gives an invalid expansion, while treating the entire increment class {δv : v ∈ D} by a single uniform-deviation bound can be too coarse for local certification. The construction in this paper separates these effects. Its deterministic starting point is a fixed-mask decomposition δv = Jv0 + Rv(m),◦ + Cv . The term Jv0 is the order-m Taylor increment computed with the smooth mask frozen at the (m),◦ base parameter. The term Rv is the ordinary Taylor remainder along paths that stay away ∗
[email protected], Department of Mathematics, The University of Hong Kong, Hong Kong.
1
from the nonsmooth interface. The term Cv is the correction contributed by observations that are initially near the interface or cross it along the path. One application of the band is risk-controlled local updating. After a candidate family D has been specified, possibly by an optimization or proposal stage, one may select an update b θ,D (v) ≤ 0. If no by minimizing the certified upper endpoint over D and accept it only when U such update is certified, the null update v = 0 is retained, whose population-risk increment is exactly zero. Relation to existing work. The empirical-process component uses standard uniformdeviation tools, including symmetrization, entropy bounds, local complexity, and concentration inequalities [VDVW96, BBM05, KOL06, Kos08, BLM13, Wai19]. The use of these tools here is local and modular: they control the fixed-mask Taylor class, while the nonsmooth interface contribution is isolated as a separate crossing process. Empirical-Bernstein inequalities provide one route to data-dependent one-sided radii [MP09]. The nonsmooth-interface phenomenon considered here overlaps with classical local expansions for nonsmooth M -estimation. In LAD and quantile regression, one must account for observations near the zero-residual interface [Pol91, Kni98, Koe05]. In margin-based classification with the ordinary hinge loss, the analogous interface is the margin boundary 1 − Y X ⊤ θ = 0, where the active affine piece of the loss changes. The objective here is different from these asymptotic analyses. We do not derive the limiting distribution of an estimator. Given a base parameter and a local candidate family, we construct finite-sample ranges for the corresponding population-risk increments. The update rule derived from the upper endpoint is related to high-confidence safe improvement and risk-control methods. Seldonian algorithms allow a learner to return no solution when a high-confidence constraint cannot be verified [TCdSB+ 19]; high-confidence policy improvement compares a candidate policy with a baseline policy [TTG15, GPC16, LTDC19]; and conformal or distribution-free risk-control methods use holdout data to obtain finite-sample risk guarantees [BAL+ 21, ABF+ 24]. The present paper studies a local inference problem: the baseline is a fixed parameter θ, the decision variable is a perturbation v, and the main statistical object is the band for P ℓθ+v − P ℓθ over v ∈ D. Section 2 gives the deterministic decomposition and the abstract certificate. Section 3 derives computable Taylor, remainder, and crossing budgets. Section 4 presents the no-split full-ball mode and the hinge-loss worked example.
2
Certificate Decomposition for Local Population Increments
We first isolate the deterministic identity on which all certificates rest. Let Z1 , . . . , Zn be i.i.d. with law P , and write n
1X Pn f := f (Zi ), n i=1
2
Z P f :=
f dP.
Fix a deterministic base point θ0 ∈ Θ and a deterministic set of candidate directions D ⊂ Rd such that θ0 + sv ∈ Θ for 0 ≤ s ≤ 1 and v ∈ D. For v ∈ D, define the local loss increment δv (z) := ℓ(θ0 + v, z) − ℓ(θ0 , z). The target throughout is an upper bound on P δv , uniformly over v ∈ D. Let Θ ⊂ Rd be the parameter space, let Z ⊂ Rp be the sample space, and set Q := Θ × Z. The loss family is ℓ : Q → R. The set Σ ⊂ Q collects points at which the loss may fail to be smooth, or at which the active formula may change. Away from Σ, the loss is assumed to be C q , for a fixed q ≥ 2. Throughout, when a base parameter θ ∈ Θ and a candidate set D ⊂ Rd are specified, we assume the feasibility condition θ + tv ∈ Θ,
for all v ∈ D and all t ∈ [0, 1].
Thus every parameter path considered below stays inside the domain of the loss. Definition 2.1 (Interface certificate system). An interface certificate system for Σ is a family A = {Aν }ν∈V , S such that Σ ⊂ ν∈V Zν , where Aν : Q → R and Zν := {y ∈ Q : Aν (y) = 0}. The number |Aν (y)| is the ν-margin. This definition provides deterministic coordinates for neighborhoods of the nonsmooth set. For a closed Σ, distance to Σ is one possible certificate. In applications, simpler certificates are usually available; in our example, the residual 1 − Y X ⊤ θ is the natural margin. Throughout the section, A = {Aν }ν∈V , θ0 , D, the Taylor order m, and the interface-tube radius r are deterministic. All functions below are assumed measurable, and the displayed integrals are assumed finite whenever they appear. Uniform probability statements may equivalently be read in the usual outer-probability sense.
2.1
Good paths, fixed masks, and Taylor terms
For y ∈ Q, define the aggregate interface margin certA (y) := inf |Aν (y)|, ν∈V
with the convention that the infimum over the empty set is +∞. For r ≥ 0, define the interface tube Tr := {y ∈ Q : certA (y) ≤ r}. Since A covers Σ, Σ ⊂ T0 ⊂ Tr . For v ∈ D, define bv (z) := 1 {∃s ∈ [0, 1] such that (θ0 + sv, z) ∈ Tr } ,
χv (z) := 1 − bv (z).
Thus bv (z) = 0 means that the whole segment stays outside the interface tube. The base masks are b0 (z) := 1{(θ0 , z) ∈ Tr }, χ0 (z) := 1 − b0 (z). 3
Because the path includes s = 0, b0 ≤ bv ,
χv ≤ χ0 ,
v ∈ D.
Since ℓ is C q on Q \ Σ, the partial derivatives Dθj ℓ, 1 ≤ j ≤ q, are well-defined there. We extend them to Σ by arbitrary measurable values, for instance by zero. These extensions serve only to define frozen jets on all samples; Taylor’s formula is applied only on good paths. Fix 1 ≤ m ≤ q − 1. For 1 ≤ k ≤ m, let Ik := {α ∈ Nd0 : |α| = k},
ek := |Ik |,
e≤m :=
m X
ek .
k=1
α For α ∈ Ik , use the standard notation α! := j αj !, v α := j vj j , and αk := k!/α!. Define s k α ak,α (v) := v , ak (v) := (ak,α (v))α∈Ik ∈ Rek . α Q
Q
Then ∥ak (v)∥2 = ∥v∥2k . Define the normalized Taylor jet by ξk,α (θ0 , z) := Then
∂θα ℓ(θ0 , z) √ , k!α!
ξk (θ0 , z) := (ξk,α (θ0 , z))α∈Ik .
1 k Dθ ℓ(θ0 , z)[v k ] = ⟨ξk (θ0 , z), ak (v)⟩. k!
Set Ξm (θ0 , z) := (ξ1 (θ0 , z), . . . , ξm (θ0 , z)),
a≤m (v) := (a1 (v), . . . , am (v)).
The Taylor increment is Jv (z) :=
m X 1
k! k=1
Dθk ℓ(θ0 , z)[v k ] = ⟨Ξm (θ0 , z), a≤m (v)⟩,
and the base-mask Taylor increment is JD0,m := {Jv0 : v ∈ D}.
Jv0 (z) := χ0 (z)Jv (z),
Define the good-path Taylor residual and the crossing correction by Rv(m),◦ (z) := χv (z){δv (z) − Jv (z)}, Cv (z) := bv (z)δv (z) − {χ0 (z) − χv (z)}Jv (z). Then the pointwise decomposition is exact: δv = Jv0 + Rv(m),◦ + Cv .
(1)
We also write Qv := δv − Jv . Since χ0 − χv = bv − b0 , Cv = b0 δv + (bv − b0 )Qv . 4
(2)
Equivalently, b0 = 0, bv = 0, 0, Cv = Qv , b0 = 0, bv = 1, δv , b0 = 1, bv = 1. No absolute value is taken in (2); the signs in these three cases are retained by the certificate. Define the good-path Taylor envelope sup Dθm+1 ℓ(θ0 + sv, z)[v m+1 ] , bv (z) = 0, ◦ Hm+1 (v; z) := 0≤s≤1 0, bv (z) = 1, and put hv (z) := rem◦m (v; z) :=
1 H ◦ (v; z), (m + 1)! m+1
Rem◦m (v) := P hv .
Proposition 2.2 (Fixed-mask population reduction). For every v ∈ D and every probability measure T for which the terms are finite, T Jv0 − T hv + T Cv ≤ T δv ≤ T Jv0 + T hv + T Cv . In particular, P Jv0 − Rem◦m (v) + P Cv ≤ P δv ≤ P Jv0 + Rem◦m (v) + P Cv . (m),◦
Proof. The identity δv = Jv0 + Rv + Cv is pointwise. If bv (z) = 0, the path s 7→ ℓ(θ0 + sv, z) m+1 is C on [0, 1], and Taylor’s theorem gives Z 1 1 (1 − s)m Dθm+1 ℓ(θ0 + sv, z)[v m+1 ] ds. δv (z) − Jv (z) = m! 0 (m),◦
(m),◦
(m),◦
Hence |Rv (z)| ≤ hv (z). If bv (z) = 1, then Rv (z) = 0. Therefore −T hv ≤ T Rv T hv . Applying T to the decomposition gives both displayed inequalities.
2.2
≤
Direct local risk certificates
After Proposition 2.2, three quantities remain to be certified: the upper fluctuation of Jv0 , the population size of the good-path remainder, and the crossing correction Cv . Definition 2.3 (Fixed-mask Taylor fluctuation certificates). A pair of measurable maps 0,+
0,−
[ D , Good [ D : D → R ∪ {+∞} Good − is a valid high-probability signed Taylor fluctuation certificate at levels (t+ J , tJ ) if 0,+ + + 0 [ P (P − Pn )Jv ≤ GoodD (v; tJ ), v ∈ D ≥ 1 − e−tJ ,
5
and
0,− [ D (v; t− ), P (Pn − P )Jv0 ≤ Good J
− v ∈ D ≥ 1 − e−tJ .
The pair is a valid expected signed Taylor fluctuation certificate if 0,+
[ D (v)} ≤ 0, E sup{(P − Pn )Jv0 − Good v∈D
and
0,−
[ D (v)} ≤ 0. E sup{(Pn − P )Jv0 − Good v∈D
d ◦ : D → [0, +∞] is a valid Definition 2.4 (Remainder certificate). A measurable map Rem m high-probability remainder certificate at level t if, with probability at least 1 − e−t , d ◦ (v; t), P hv ≤ Rem m
v ∈ D.
It is a valid expected remainder certificate if d ◦ (v)} ≤ 0. E sup{P hv − Rem m v∈D
Definition 2.5 (Empirical signed crossing budgets). A pair of measurable maps −
+
[ D : D → R ∪ {+∞}, Cross
[ D : D → R ∪ {−∞} Cross
− is a valid high-probability signed crossing budget at levels (t+ C , tC ) if + [ D (v; t+ ), v ∈ D ≥ 1 − e−t+C , P P Cv ≤ Cross C
and
−
[ D (v; t− ), P P Cv ≥ Cross C
−
v ∈ D ≥ 1 − e−tC .
The pair is a valid expected signed crossing budget if +
[ D (v)} ≤ 0, E sup{P Cv − Cross v∈D
and
−
[ D (v) − P Cv } ≤ 0. E sup{Cross v∈D
For later reference, define the upper direct local risk certificate 0,+
+
b D (v; tJ , tR , tC ) := Pn J 0 + Good d ◦ (v; tR ) + Cross [ D (v; tJ ) + Rem [ D (v; tC ), U v m
(3)
and, when lower certificates are also computed, define the lower endpoint −
0,−
b d ◦ (v; tR ) + Cross [ D (v; tJ ) − Rem [ D (v; tC ). LD (v; tJ , tR , tC ) := Pn Jv0 − Good m 6
(4)
b D and b LD be Theorem 2.6 (Local population-risk upper and interval certificates). Let U defined by (3) and (4). Define the upper-side event 0,+ + 0 [ (P − P )J ≤ Good (v; t ), n v D J ◦ d EU := for all v ∈ D . P hv ≤ Remm (v; tR ), + + [ P Cv ≤ CrossD (v; tC ), On EU , b D (v; t+ , tR , t+ ), P δv ≤ U J C
v ∈ D.
+ Consequently, if the three upper-side component certificates are valid at levels t+ J , tR , tC , then n o b D (v; t+ , tR , t+ ) for all v ∈ D ≥ 1 − e−t+J − e−tR − e−t+C . P P δv ≤ U J C
If, in addition, the lower-side event 0,− − 0 [ (Pn − P )Jv ≤ GoodD (v; tJ ), d ◦ (v; tR ), EL := P hv ≤ Rem m − [ D (v; t− ), P Cv ≥ Cross C
for all v ∈ D
also holds, then on EU ∩ EL , + + − b b LD (v; t− J , tR , tC ) ≤ P δv ≤ UD (v; tJ , tR , tC ),
v ∈ D.
− + − Consequently, if the upper- and lower-side component certificates are valid at levels t+ J , tJ , tR , tC , tC , then n o + − + − − + + b P b LD (v; t− , t , t ) ≤ P δ ≤ U (v; t , t , t ) for all v ∈ D ≥ 1−e−tJ −e−tJ −e−tR −e−tC −e−tC . v D J R C J R C
Proof. On EU , Proposition 2.2 gives, uniformly over v ∈ D, 0,+
+
d ◦ (v; tR ) + Cross [ D (v; t+ ) + Rem [ D (v; t+ ). P δv ≤ P Jv0 + P hv + P Cv ≤ Pn Jv0 + Good m J C This is the asserted upper bound. The high-probability statement follows by the union bound. For the lower endpoint, work on EU ∩ EL . The lower side of Proposition 2.2 gives 0,−
◦
−
d (v; tR ) + Cross [ D (v; t− ) − Rem [ D (v; t− ). P δv ≥ P Jv0 − P hv + P Cv ≥ Pn Jv0 − Good m J C Together with the upper bound already proved, this yields the interval band. The probability bound is again the union bound.
7
3
Computable Population-Risk Certificates
Theorem 2.6 reduces the problem to three components. Once the required range, moment, or envelope inputs are available, these components are sample-computable. The fixed-mask Taylor term is controlled by a one-sided empirical-process bound for (P − Pn )Jv0 . The good-path remainder requires an upper bound on P hv . The crossing term requires an upper confidence bound for P Cv , obtained from observed crossing increments together with entropy or Rademacher radius. Throughout this section, CEB is the numerical constant in the empirical-Bernstein inequalities below. If Φ : T → (F, d∞ ) is LΦ -Lipschitz, then N (ε, Φ(T ), d∞ ) ≤ N (ε/LΦ , T, ∥ · ∥2 ). The displayed certificates in this section are written under deterministic boundedness and oscillation assumptions. Specifically, Bernstein certificates require the indicated range bounds, and high-probability Rademacher certificates require the indicated oscillation bounds. If a displayed boundedness condition fails but a suitable 1 + η moment certificate is available, the usual truncation replacement may be used: truncate the relevant function class at level κ, apply the bounded certificate to the truncated class, and add the tail term controlled by the moment certificate. To keep the formulas readable, the tail correction is not carried in the subsections below.
3.1
Empirical-Bernstein and Rademacher templates
We start with two reusable concentration templates. The empirical-Bernstein version adapts to the empirical variance, while requiring a usable d∞ -covering number for the function class. For a measurable class F, write n X b n (F) := Eε sup 1 R εi f (Zi ) . f ∈F n i=1
For a class G satisfying |g| ≤ 1, define HG (t) := 1 + inf t + log 2 max{1, N (ε, G, d∞ )} + nε . 0<ε≤1
For bounded measurable f , set sbn (f ) := {Pn (f − Pn f )2 }1/2 . Lemma 3.1 (Finite empirical Bernstein inequality). Assume n ≥ 2. There is a universal constant CEB such that, for every finite |F| < ∞ with |f | ≤ 1, with probability at least 1 − e−u , " # r u + log(2|F|) u + log(2|F|) |(P − Pn )f | ≤ CEB sbn (f ) + ∀f ∈ F. n n
8
Proof. We use Maurer–Pontil’s finite empirical-Bernstein bound [MP09, Corollary 5]. Since our functions are [−1, 1]-valued, apply the displayed bound to A = (1 + f )/2 : f ∈ F ∪ (1 − f )/2 : f ∈ F . Then |A| ≤ 2|F|. Taking δ = e−u gives A := log(|A|/δ) ≤ u + log(2|F|). The element (1 + f )/2 controls P f − Pn f , while (1 − f )/2 controls Pn f − P f ; hence the one-sided Maurer–Pontil inequality gives a two-sided bound for f . It remains to translate the variance convention. If sb2n (f ) = Pn (f − Pn f )2 , then Maurer– Pontil’s variance satisfies n Vn (1 ± f )/2 = sb2 (f ), 4(n − 1) n P P using i<j (xi − xj )2 = n i (xi − x̄)2 . Therefore, for both signs, r 2A 14A |(P − Pn )f | ≤ sbn (f ) + . n−1 3(n − 1) Since n ≥ 2, replacing n − 1 by n only changes the numerical constant. Enlarging the universal constant gives the asserted inequality. Lemma 3.2 (Entropy-net empirical Bernstein inequality). Assume n ≥ 2. There is a universal constant CEB such that, for every |g| ≤ 1 class G, with probability at least 1 − e−t , " # r HG (t) HG (t) |(P − Pn )g| ≤ CEB sbn (g) + ∀g ∈ G. n n Proof. Fix 0 < ε ≤ 1 and take a deterministic d∞ -net Γε of G with |Γε | ≤ N (ε, G, d∞ ). Put Aε := t + log 2 max{1, N (ε, G, d∞ )} . By Lemma 3.1, with probability at least 1 − e−t , " r |(P − Pn )γ| ≤ CEB sbn (γ)
Aε Aε + n n
# ∀γ ∈ Γε .
On this event, fix any g ∈ G and choose πg ∈ Γε with ∥g − πg∥∞ ≤ ε. Then |(P − Pn )g| ≤ |(P − Pn )πg| + |(P − Pn )(g − πg)| ≤ |(P − Pn )πg| + 2ε, because both |P (g − πg)| and |Pn (g − πg)| are at most ε. Also sbn (πg) ≤ sbn (g) + sbn (πg − g) ≤ sbn (g) + ε, since empirical standard deviation is a seminorm after centering and is bounded by the sup norm. Hence " # r r Aε Aε Aε |(P − Pn )g| ≤ CEB sbn (g) + + CEB ε + 2ε. n n n 9
Let Bε = Aε + nε. Since 0 < ε ≤ 1, r Aε Aε ε2 Bε ε ≤ + ≤ , n 2n 2 n
2ε ≤ 2
Bε . n
After increasing the universal constant, "
r
|(P − Pn )g| ≤ CEB sbn (g)
Bε Bε + n n
# ∀g ∈ G.
Finally choose ε deterministically, before the probability bound is applied, within one unit of the infimum in the definition of HG (t). Then Bε ≤ HG (t), and the displayed inequality gives the claim. If the relevant covering number is infinite, the bound is interpreted as trivial. Lemma 3.3 (Rademacher comparison inequality). If osc(F) := supf ∈F supz,z′ |f (z)−f (z ′ )| ≤ B, then, with probability at least 1 − e−u , r b n (F) + 3B u + log 2 . sup |(P − Pn )f | ≤ 2R 2n f ∈F Moreover, b n (F). E sup |(P − Pn )f | ≤ 2ER f ∈F
Proof. We first prove the expected bound. Let Z1′ , . . . , Zn′ be an independent ghost sample with the same law as Z1 , . . . , Zn . By the usual symmetrization argument, n
1X E sup |(P − Pn )f | ≤ E sup {f (Zi′ ) − f (Zi )} f ∈F f ∈F n i=1 n
1X = E sup εi {f (Zi′ ) − f (Zi )} f ∈F n i=1 b n (F), ≤ 2ER where the second line uses the symmetry of (f (Zi′ ) − f (Zi ))ni=1 , and the last line uses the triangle inequality after conditioning on the two samples. For the high-probability bound, put Y (Z1 , . . . , Zn ) := sup |(P − Pn )f |, f ∈F
b n (F). R(Z1 , . . . , Zn ) := R
If one sample point Zi is replaced by Zi′ , then, for every f ∈ F, 1 1 B f (Zi ) − f (Zi′ ) ≤ , n n n because osc(F) ≤ B. Hence Y changes by at most B/n. The same bounded-difference constant holds for R: for fixed Rademacher signs, 1X 1X 1 B εj f (Zj ) − sup εj f (Zj ) + εi f (Zi′ ) ≤ , n n f ∈F n j f ∈F n j̸=i
sup
10
and averaging over ε preserves the bound. By the bounded-differences inequality [BLM13, Theorem 6.2], for every s > 0, with probability at least 1 − e−s , r s Y ≤ EY + B , 2n and with probability at least 1 − e−s , r R ≥ ER − B
s . 2n
Intersect these two events and set s = u + log 2. The failure probability is at most 2e−s = e−u . On this intersection, r r r s s s Y ≤ EY + B ≤ 2ER + B ≤ 2R + 3B . 2n 2n 2n This is the asserted high-probability inequality. For an indexed class F = {fv : v ∈ D}, suppose first that deterministic range scales Bv < ∞ are available with |fv | ≤ Bv . Define f¯v = fv /Bv when Bv > 0, set f¯v = 0 otherwise, and put F̄ := {f¯v : v ∈ D}. Set # " r (t) (t) H H F̄ c F (v; t) := CEB Bv sbn (f¯v ) + F̄ . EB n n Let BF ,∗ := sup Bv . v∈D
When BF ,∗ < ∞, the expected-valid Bernstein map is c av (v; t) := EB c F (v; t) + 2BF ,∗ e−t . EB F The Rademacher maps below do not require the deterministic range scales. Define the expected Rademacher map d av := 2R b n (F), Rad F whenever the right-hand side is finite. When BF ,osc := osc(F) < ∞, define the high-probability version r d F (t) := 2R b n (F) + 3BF ,osc t + log 2 . Rad 2n Proposition 3.4 (Bounded-class Bernstein/Rademacher template). Assume n ≥ 2. For c F (·; t) is a the Bernstein assertions, assume the range scales above have been fixed. Then EB c av (·; t) valid high-probability two-sided fluctuation certificate at level t. If BF ,∗ < ∞, then EB F d av is a valid expected two-sided fluctuation certificate. If E supv∈D |fv (Z)| < ∞, then Rad F d F (t) is a valid is a valid expected two-sided fluctuation certificate. If BF ,osc < ∞, then Rad high-probability two-sided fluctuation certificate at level t. 11
Proof. We first prove the Bernstein high-probability certificate. If Bv = 0, then |fv | ≤ Bv implies fv = 0, so the claim is trivial. If Bv > 0, then fv = Bv f¯v , with |f¯v | ≤ 1. Applying Lemma 3.2 to F̄ gives, with probability at least 1 − e−t , " # r HF̄ (t) HF̄ (t) |(P − Pn )f¯v | ≤ CEB sbn (f¯v ) + n n simultaneously for all v ∈ D. Multiplying by Bv gives c F (v; t), |(P − Pn )fv | ≤ EB
v ∈ D.
The absolute-value bound controls both signs P − Pn and Pn − P . Now assume BF ,∗ < ∞. Let n o c F (v; t) for all v ∈ D . Et := |(P − Pn )fv | ≤ EB The preceding paragraph gives P(Etc ) ≤ e−t . Put c := 2BF ,∗ e−t . On Et , n o c sup |(P − Pn )fv | − EBF (v; t) − c ≤ −c. v∈D
c F (v; t) ≥ 0, On Etc , since |fv | ≤ BF ,∗ and EB n o c F (v; t) − c ≤ 2BF ,∗ − c. sup |(P − Pn )fv | − EB v∈D
Therefore n o av c E sup |(P − Pn )fv | − EBF (v; t) ≤ −c P(Et ) + (2BF ,∗ − c)P(Etc ) v∈D
= −c + 2BF ,∗ P(Etc ) ≤ 0. av
c (·; t) is a valid expected two-sided fluctuation certificate. Thus EB F Under the stated integrability condition, the usual symmetrization inequality [VDVW96, Section 2.3.1] gives d av . b n (F) = ERad E sup |(P − Pn )fv | ≤ 2ER F v∈D
d av is constant in v, this is equivalent to Since Rad F n o d av ≤ 0. E sup |(P − Pn )fv | − Rad F v∈D
If BF ,osc < ∞, Lemma 3.3 gives, with probability at least 1 − e−t , r d F (t). b n (F) + 3BF ,osc t + log 2 = Rad sup |(P − Pn )fv | ≤ 2R 2n v∈D This proves the proposition. 12
3.2
Fixed-mask Taylor fluctuation certificates on D
This subsection controls the smooth fixed-mask fluctuation (P − Pn )Jv0 . Write X(z) := Ξm (θ0 , z) ∈ Re≤m ,
X0 (z) := χ0 (z)X(z),
a(v) := a≤m (v),
so that Jv0 (z) = ⟨X0 (z), a(v)⟩. In the explicit formulas below we assume the bounded jet condition ∥X0 (z)∥ ≤ κJ
for all z,
(5)
with a known deterministic κJ < ∞. The unbounded case can be handled by truncating X0 and appending the tail correction described at the beginning of Section 3; to keep the certificates readable, we do not carry that correction in the displays. Whenever a range scale that appears in a denominator is zero, the corresponding normalized function and radius are interpreted as zero. Direct Rademacher certificate. Let JD0 := {Jv0 : v ∈ D},
BJ,osc := osc(JD0 ).
When BJ,osc < ∞, define 0,Rad
[D Good
r b n (J 0 ) + 3BJ,osc (v; t) := 2R D
0,Rad,av
[D Good
t + log 2 , 2n
b n (J 0 ). (v) := 2R D
(6) (7)
Both maps are constant in v. The first is a high-probability two-sided Taylor fluctuation radius; the second is an expected two-sided Taylor fluctuation radius under the usual symmetrization integrability condition. Localized Rademacher certificate. The global Rademacher radius can be localized in the Taylor-feature space so that its leading term is close to the fluctuation of the target direction itself. Put n 1X Sε := εi X0 (Zi ), rbn (v) := Eε |⟨Sε , a(v)⟩| . n i=1 Let {cℓ }ℓ∈L be a finite ρ-net of a(D) := {a(v) : v ∈ D}, and define Dℓ := {u ∈ D : ∥a(u) − cℓ ∥ ≤ ρ}, Jℓ0 := {Ju0 : u ∈ Dℓ }. P Choose weights πℓ > 0 with ℓ∈L πℓ = 1. Applying Lemma 3.3 to each localized class with failure level t + log(1/πℓ ), and then taking a union bound, gives with probability at least 1 − e−t , simultaneously for all v ∈ D, ( ) r t + log(1/π ) + log 2 ℓ b n (J 0 ) + 3BJ,ℓ,osc (P − Pn )Jv0 ≤ inf 2R , ℓ ℓ:v∈Dℓ 2n 13
where BJ,ℓ,osc := osc(Jℓ0 ). Moreover, if v ∈ Dℓ , then every u ∈ Dℓ satisfies ∥a(u) − a(v)∥ ≤ 2ρ, and hence b n (J 0 ) = Eε sup |⟨Sε , a(u)⟩| ≤ rbn (v) + 2ρ Eε ∥Sε ∥. R ℓ u∈Dℓ
Consequently, the leading localized Rademacher term can be made arbitrarily close to the fixed-direction term rbn (v), up to the patch diameter error 2ρEε ∥Sε ∥. Empirical-Bernstein certificate. For v ∈ D, define ⟨X0 (z), a(v)⟩ , a(v) ̸= 0, 0 κJ ∥a(v)∥ GJ0 := {gv0 : v ∈ D}. gv (z) := 0, a(v) = 0, Then |gv0 | ≤ 1. Put sb0J (v) := {Pn (gv0 − Pn gv0 )2 }1/2 ,
σ bJ0 (v) := κJ ∥a(v)∥b s0J (v),
and define the normalized entropy budget HJ0 (t) := 1 + inf t + log 2 max{1, N (ε, GJ0 , d∞ )} + nε . 0<ε≤1
(8)
Let AD,m := sup ∥a(v)∥,
BJ,∗ := κJ AD,m .
v∈D
The high-probability empirical-Bernstein Taylor radius is # " r 0 0 0,EB H (t) (t) H J [ D (v; t) := CEB σ + κJ ∥a(v)∥ J , Good bJ0 (v) n n
(9)
and the corresponding expected-valid version obtained from the same event is 0,EB,av
[D Good
0,EB
[D (v; t) := Good
(v; t) + 2BJ,∗ e−t .
(10)
At any v with a(v) = 0, the high-probability radius (9) is interpreted as zero. Polar entropy for m = 1 and m = 2. Let E ⊂ Rd be a linear subspace, let SE := {ω ∈ E : ∥ω∥ = 1}, and set dE := dim(E). For D ⊂ E ∩ B2 (ρ), define Qm (D) := {0} ∪ {qm (v) : v ∈ D, a(v) ̸= 0} ,
qm (v) :=
a(v) . ∥a(v)∥
Because ∥X0 ∥/κJ ≤ 1, d∞ (gv0 , gu0 ) ≤ ∥qm (v) − qm (u)∥, and the extra point 0 covers the null direction. 14
a(v) ̸= 0, a(u) ̸= 0,
For m = 1, a(v) = v. Hence q1 (sω) = ω for s > 0, and the radial coordinate disappears. By the standard volumetric covering bound for Euclidean balls, whose same upper bound also applies to the unit Euclidean sphere [Ver25, Section 4.2], applied in the dE -dimensional subspace E, dE 2 N (ε, SE , ∥ · ∥2 ) ≤ +1 , 0 < ε ≤ 1. ε Together with the Lipschitz pullback d∞ (gv0 , gu0 ) ≤ ∥q1 (v) − q1 (u)∥, this gives dE 2 0 N (ε, GJ , d∞ ) ≤ +1 + 1, 0 < ε ≤ 1. ε
(11)
For m = 2, it is useful to make the degree-two feature map explicit. For x ∈ Rd , write √ a2 (x) := (x2i )1≤i≤d , ( 2 xi xj )1≤i<j≤d , q up to a fixed ordering of the coordinates. Equivalently, a2 (x) = ( α2 xα )|α|=2 . This normalization gives ⟨a2 (x), a2 (y)⟩ = ⟨x, y⟩2 ,
∥a2 (x)∥ = ∥x∥2 .
Now write v = sω, where s = ∥v∥ and ω ∈ SE . Since √ ∥a≤2 (rω)∥ = s 1 + s2 ,
a≤2 (sω) = (sω, s2 a2 (ω)), we have
(ω, sa2 (ω)) q2 (sω) = √ . 1 + s2
Put ϑ = arctan s. Then q2 (sω) = (cos ϑ ω, sin ϑ a2 (ω)),
ϑ ∈ [0, arctan ρ].
(12)
For ω, η ∈ SE , ∥a2 (ω) − a2 (η)∥2 = 2{1 − ⟨ω, η⟩2 } ≤ 2∥ω − η∥2 . Therefore, for s1 , s2 > 0, ω, η ∈ SE , and ϑ = arctan s1 , φ = arctan s2 , ∥q2 (s1 ω) − q2 (s2 η)∥ ≤ ∥(cos ϑ ω, sin ϑ a2 (ω)) − (cos ϑ η, sin ϑ a2 (η))∥ + ∥(cos ϑ η, sin ϑ a2 (η)) − (cos φ η, sin φ a2 (η))∥ ≤ 2∥ω − η∥ + |ϑ − φ| = 2∥ω − η∥ + | arctan s1 − arctan s2 |. Thus an ε/4-net of SE and an ε/2-net of [0, arctan ρ] give an ε-net for the nonzero part of Q2 (D). By the standard volumetric covering bound for the unit Euclidean sphere [Ver25, Section 4.2], applied in the dE -dimensional subspace E, dE 8 N (ε/4, SE , ∥ · ∥2 ) ≤ +1 , 0 < ε ≤ 1. ε 15
The interval [0, arctan ρ] has an ε/2-net of cardinality at most 1 + 2 arctan(ρ)/ε. Adding the zero direction, gives dE 8 2 arctan(ρ) 0 +1 , 0 < ε ≤ 1. (13) N (ε, GJ , d∞ ) ≤ 1 + 1+ ε ε The appearance of arctan ρ, rather than ρ, is a consequence of the angular parametrization s 7→ ϑ = arctan s in (12). This is the origin-stable replacement for a Euclidean Lipschitz constant of v 7→ a(v)/∥a(v)∥, which would blow up near v = 0. It is convenient to record the corresponding entropy budgets. For m = 1, we may take DJE,1 (t) := 2 + t + log 2 1 + (2n + 1)dE . For m = 2, we may take DJE,2 (t; ρ) := 2 + t + log 2 1 + (8n + 1)dE {1 + 2n arctan(ρ)} . Indeed, these choices follow from the entropy budget HJ0 (t) = 1 + inf t + log 2 max{1, N (ε, GJ0 , d∞ )} + nε , 0<ε≤1
by taking ε = 1/n. Examples. The next examples give the Taylor component to be inserted into (3) and (4). The same Taylor radius is used on the upper and lower side. For the direction-adaptive localized Rademacher alternatives, define n
1X Sε := εi X0 (Zi ), n i=1
rbJ (v) := Eε |⟨Sε , a(v)⟩| ,
cJ := Eε ∥Sε ∥. M
Thus rbJ (v) is the fixed-direction empirical Rademacher fluctuation of Jv0 . For D ⊂ B2 (ρ), also write !1/2 m X La,m (ρ) := q 2 ρ2q−2 , q=1
so that ∥a(u) − a(v)∥ ≤ La,m (ρ)∥u − v∥ on B2 (ρ). Finite list. Let V = {v1 , . . . , vK }. Define BJ,list,∗ := κJ max ∥a(vj )∥.
DJ,list (t) := 1 + t + log(2K),
1≤j≤K
For j = 1, . . . , K, the empirical-Bernstein Taylor radii are # " r 0,EB D (t) D (t) J,list J,list [ list (vj ; t) := CEB σ , Good bJ0 (vj ) + κJ ∥a(vj )∥ n n 0,EB,av
[ list Good
0,EB
[ list (vj ; t) + 2BJ,list,∗ e−t . (vj ; t) := Good 16
(14) (15)
If BJ,list,osc := osc{Jv0j : 1 ≤ j ≤ K} < ∞, the global Rademacher alternatives are *
0,Rad
[ list (vj ; t) := 2Eε max Good
1≤ℓ≤K
0,Rad,av
[ list Good
* (vj ) := 2Eε max
1≤ℓ≤K
n
1X εi X0 (Zi ), a(vℓ ) n i=1 n
1X εi X0 (Zi ), a(vℓ ) n i=1
+
r + 3BJ,list,osc
t + log 2 , 2n
(16)
+ .
(17)
The direction-adaptive finite-list alternative is obtained by applying the Rademacher comparison inequality to each singleton class {Jv0j } and then taking a union bound. Let BJ,j,osc := osc{Jv0j } ≤ 2κJ ∥a(vj )∥. Then, with probability at least 1 − e−t , simultaneously for j = 1, . . . , K, 0,locRad
[ list (P − Pn )Jv0j ≤ Good where
(vj ; t),
r
t + log K + log 2 . (18) 2n The same radius may be used for the lower-side fluctuation. Continuous candidate sets. Let E0 ⊂ Rd be a linear subspace with d0 := dim(E0 ), let R > 0, and suppose D ⊂ E0 ∩ B2 (R). 0,locRad
[ list Good
(vj ; t) := 2b rJ (vj ) + 3BJ,j,osc
This template covers both the finite-hull and k-ball examples. For a finite hull D = conv{v1 , . . . , vM }, take E0 = EH := span{v1 , . . . , vM },
d0 = dH := dim(EH ),
R = ρH := max ∥vj ∥. j
For a k-ball D = E ∩ B2 (ρ), take E0 = E,
d0 = k,
R = ρ.
For m = 1 or m = 2, set ( DJE0 ,1 (t), m = 1, DJ,ld,m (t; E0 , R) := J DE0 ,2 (t; R), m = 2. Also put Ald,m := sup ∥a(v)∥,
BJ,ld,∗ := κJ Ald,m .
v∈D
For v ∈ D, the empirical-Bernstein Taylor radii are " # r 0,EB D (t; E , R) D (t; E , R) J,ld,m 0 J,ld,m 0 [ ld (v; t) := CEB σ + κJ ∥a(v)∥ , Good bJ0 (v) n n 17
(19)
0,EB,av
[ ld Good
0,EB
[ ld (v; t) + 2BJ,ld,∗ e−t . (v; t) := Good
(20)
If BJ,ld,osc := osc{Jv0 : v ∈ D} < ∞, then the global Rademacher alternatives are + * n r X 0,Rad t + log 2 1 [ ld (v; t) := 2Eε sup εi X0 (Zi ), a(u) + 3BJ,ld,osc , Good n i=1 2n u∈D + * n X 0,Rad,av 1 [ ld εi X0 (Zi ), a(u) . Good (v) := 2Eε sup n i=1 u∈D
(21) (22)
For the direction-adaptive localized Rademacher alternative, fix a Taylor-feature localization radius δa > 0. Let !1/2 m X δa La,m (R) := j 2 R2j−2 , ra := . L (R) a,m j=1 By the standard volumetric covering bound for Euclidean balls [Ver25, Section 4.2], applied in the d0 -dimensional subspace E0 , there exist points w1 , . . . , wNld ∈ E0 ∩ B2 (R) such that E0 ∩ B2 (R) ⊂
N ld [
B2 (wℓ , ra ),
ℓ=1
with
d 2RLa,m (R) 0 Nld ≤ Nld (δa ; E0 , R) := 1 + . δa Define the localized patches Dℓ := D ∩ B2 (wℓ , ra ),
(23)
ℓ = 1, . . . , Nld .
Then for every u ∈ Dℓ , ∥a(u) − a(wℓ )∥ ≤ La,m (R)∥u − wℓ ∥ ≤ δa . Hence, if v ∈ Dℓ , then sup ∥a(u) − a(v)∥ ≤ 2δa . u∈Dℓ
Consequently, b n ({J 0 : u ∈ Dℓ }) ≤ rbJ (v) + 2δa M cJ , R u and osc{Ju0 : u ∈ Dℓ } ≤ 2κJ {∥a(v)∥ + 2δa }. Applying the Rademacher comparison inequality on every patch and taking a union bound gives, with probability at least 1 − e−t , uniformly over v ∈ D, 0,locRad
[ ld (P − Pn )Jv0 ≤ Good 18
(v; t, δa ),
where r
t + log Nld (δa ; E0 , R) + log 2 . 2n (24) The same localized radius may be used for the lower-side fluctuation. Thus the global Rademacher supremum is replaced by the fixed-direction term rbJ (v), at the price of the localization error δa and the covering penalty log Nld (δa ; E0 , R). 0,locRad
[ ld Good
3.3
cJ + 6κJ {∥a(v)∥ + 2δa } (v; t, δa ) := 2b rJ (v) + 4δa M
Computable remainder bounds
Recall hv (z) = rem◦m (v; z) =
1 H ◦ (v; z), (m + 1)! m+1
Rem◦m (v) = P hv ,
and hv ≥ 0. In computations we may use a single nonnegative sample-computable envelope for the (m + 1)-st derivative, rather than a separate remainder majorant for each direction. Let T (θ0 , D) := {θ0 + sv : v ∈ D, 0 ≤ s ≤ 1} be the parameter tube swept out by the candidate set. Assume that there is a measurable function Γm+1 : Z → [0, ∞] such that, whenever the (m + 1)-st derivative exists, sup
sup Dθm+1 ℓ(θ, z)[um+1 ] ≤ Γm+1 (z).
(25)
∥v∥m+1 2 . (m + 1)!
(26)
θ∈T (θ0 ,D) ∥u∥2 ≤1
Then, for every v ∈ D, hv (z) ≤ αm (v)Γm+1 (z),
αm (v) :=
◦ Indeed, if bv (z) = 1, then Hm+1 (v; z) = 0. If bv (z) = 0, the whole path stays in the smooth region, and (25) gives ◦ Hm+1 (v; z) ≤ ∥v∥m+1 Γm+1 (z). 2
Deterministic and empirical certificates. Assume first that 0 ≤ Γm+1 (z) ≤ BΓ
(27)
with a deterministic constant BΓ < ∞. Then P hv ≤ αm (v)P Γm+1 ≤ αm (v)BΓ , so
d env (v) := αm (v)BΓ Rem D
is a deterministic high-probability and expected remainder certificate.
19
(28)
For sharper empirical certificates, set ( Γm+1 /BΓ , BΓ > 0, Γ̄m+1 := sbΓ := {Pn (Γ̄m+1 −Pn Γ̄m+1 )2 }1/2 , 0, BΓ = 0,
DΓ (t) := 1+t+log 2.
Define the empirical-Bernstein upper confidence bound for P Γm+1 by # " r D (t) D (t) Γ Γ + , µ bEB bΓ Γ (t) := Pn Γm+1 + CEB BΓ s n n
(29)
with the convention that the second term is zero when BΓ = 0. The resulting high-probability remainder certificate is d EB (v; t) := αm (v)b Rem µEB (30) D Γ (t). Indeed, on the event P Γm+1 ≤ µ bEB Γ (t), one has uniformly over v ∈ D, P hv ≤ αm (v)P Γm+1 ≤ αm (v)b µEB Γ (t). When AR := sup αm (v) < ∞, v∈D
the corresponding expected-valid empirical-Bernstein remainder certificate is −t d EB,av (v; t) := αm (v)b Rem µEB D Γ (t) + 2AR BΓ e .
(31)
To see this, let bEB EtEB := {P Γm+1 ≤ µ Γ (t)}. The empirical-Bernstein inequality gives P((EtEB )c ) ≤ e−t . On EtEB , o n EB,av d sup P hv − RemD (v; t) ≤ −2AR BΓ e−t . v∈D
µEB On (EtEB )c , since 0 ≤ P hv ≤ AR BΓ and αm (v)b Γ (t) ≥ 0, n o d EB,av (v; t) ≤ AR BΓ − 2AR BΓ e−t . sup P hv − Rem D v∈D
Therefore n o EB,av d E sup P hv − RemD (v; t) ≤ −2AR BΓ e−t + AR BΓ P((EtEB )c ) ≤ 0. v∈D
A Rademacher alternative for the same single envelope is n
1X µ bRad (t) := P Γ + 2E εi Γm+1 (Zi ) + 3BΓ n m+1 ε Γ n i=1
r
t + log 2 . 2n
(32)
The resulting high-probability remainder certificate is d Rad (v; t) := αm (v)b Rem µRad D Γ (t). 20
(33)
When AR < ∞, the corresponding expected-valid Rademacher remainder certificate is −t d Rad,av (v; t) := αm (v)b Rem µRad Γ (t) + 2AR BΓ e . D
(34)
Indeed, by applying Lemma 3.3 to the singleton class {Γm+1 }, the event bRad EtRad := {P Γm+1 ≤ µ Γ (t)} has probability at least 1 − e−t . The same good-event/bad-event argument as above gives n o d Rad,av (v; t) ≤ 0. E sup P hv − Rem D v∈D
3.4
Empirical crossing-increment certificates
The crossing term is Cv = b0 δv + (bv − b0 )Qv ,
Qv = δv − Jv .
Unlike the fixed-mask Taylor class, Cv contains the path indicator bv . We therefore separate two cases. If the candidate set used by the final certification sample is finite, the crossing correction is evaluated direction by direction. If the candidate set is genuinely continuous, the exact crossing class is replaced by a smooth sandwich −Sv ≤ Cv ≤ Sv . Finite crossing class. Let V = {v1 , . . . , vK } be fixed before the certification sample is used. In this finite case the crossing increment is evaluated exactly for each listed direction; no crossing majorant or minorant is needed. For each certification observation z and each vj , compute δj (z) := ℓ(θ0 + vj , z) − ℓ(θ0 , z),
Jj (z) := Jvj (z),
Qj (z) := δj (z) − Jj (z),
and the two masks b0 (z) := 1{(θ0 , z) ∈ Tr },
bj (z) := 1{∃s ∈ [0, 1] : (θ0 + svj , z) ∈ Tr }.
Since the path includes s = 0, b0 ≤ bj . The exact signed crossing increment is therefore the sample-computable quantity b0 (z) = 0, bj (z) = 0, 0, Cvj (z) := b0 (z)δj (z) + {bj (z) − b0 (z)}Qj (z) = Qj (z), b0 (z) = 0, bj (z) = 1, (35) δj (z), b0 (z) = 1. Thus the finite-list crossing budget is a concentration bound for the exact finite class {Cvj : 1 ≤ j ≤ K}. Assume deterministic absolute range bounds |Cvj | ≤ BC (vj ),
j = 1, . . . , K,
21
known before the concentration inequality is applied. Put DC,list (t) := 1 + t + log(2K),
BC,list,∗ := max BC (vj ), 1≤j≤K
and define the normalized variables ( Cvj /BC (vj ), BC (vj ) > 0, cj := 0, BC (vj ) = 0. The upper finite crossing certificates are "
+,EB
r
[ list (vj ; t) := Pn Cvj + CEB BC (vj ) sbn (cj ) Cross +,EB,av
[ list Cross
# DC,list (t) DC,list (t) + , n n
+,EB
[ list (vj ; t) + 2BC,list,∗ e−t . (vj ; t) := Cross
(36) (37)
The lower finite crossing certificates are "
−,EB
r
[ list (vj ; t) := Pn Cvj − CEB BC (vj ) sbn (cj ) Cross −,EB,av
[ list Cross
#
DC,list (t) DC,list (t) + , n n
−,EB
[ list (vj ; t) − 2BC,list,∗ e−t . (vj ; t) := Cross
(38) (39)
If the exact finite crossing class has finite oscillation BC,list,osc := osc{Cvj : 1 ≤ j ≤ K}, then the Rademacher finite crossing alternatives are +,Rad
[ list Cross
n
1X (vj ; t) := Pn Cvj + 2Eε max εi Cvℓ (Zi ) + 3BC,list,osc 1≤ℓ≤K n i=1
+,Rad,av
[ list Cross
−,Rad
[ list Cross [ list Cross
t + log 2 , 2n
(40)
n
1X εi Cvℓ (Zi ) , 1≤ℓ≤K n i=1
(vj ) := Pn Cvj + 2Eε max
n
1X εi Cvℓ (Zi ) − 3BC,list,osc (vj ; t) := Pn Cvj − 2Eε max 1≤ℓ≤K n i=1
−,Rad,av
r
(41) r
t + log 2 , 2n
(42)
n
1X (vj ) := Pn Cvj − 2Eε max εi Cvℓ (Zi ) . 1≤ℓ≤K n i=1
(43)
Continuous crossing class via inflated finite covers. For a continuous candidate set, the exact map v 7→ Cv need not be Lipschitz, because the path indicator bv can jump when the path first intersects the interface tube. A smooth global sandwich such as |δv | + |Jv | is always valid, but it can be much too conservative: it penalizes observations even when the whole path stays far from the interface. The construction below keeps the crossing indicator, replacing the exact continuous class by a finite collection of inflated crossing envelopes. 22
Assume D ⊂ E0 ∩ B2 (R),
d0 := dim(E0 ),
and let w1 , . . . , wNη be an η-net of D in ∥ · ∥2 . Define Dℓ := {v ∈ D : ∥v − wℓ ∥2 ≤ η},
ℓ = 1, . . . , Nη .
For example, by the standard Euclidean covering bound, one may take d 2R 0 . Nη ≤ 1 + η
(44)
Assume the aggregate interface certificate has the first-order stability bound |certA (θ0 + sv, z) − certA (θ0 + su, z)| ≤ ΓA (z)∥v − u∥2 ,
u, v ∈ D, s ∈ [0, 1].
(45)
For instance, (45) follows if ΓA (z) ≥ sup
sup
∥∇θ Aν (θ, z)∥2 ,
ν∈V θ∈T (θ0 ,D)
with the gradient replaced by a Lipschitz modulus when the certificates are only Lipschitz. For each cover center define the inflated path mask b+ ℓ,η (z) := 1 {∃s ∈ [0, 1] : certA (θ0 + swℓ , z) ≤ r + ηΓA (z)} .
(46)
Then, for every v ∈ Dℓ , b0 (z) ≤ bv (z) ≤ b+ ℓ,η (z).
(47)
Indeed, if bv (z) = 1, then for some s ∈ [0, 1], certA (θ0 + sv, z) ≤ r. By (45) and ∥v − wℓ ∥2 ≤ η, the same s satisfies certA (θ0 + swℓ , z) ≤ r + ηΓA (z). The inequality b0 ≤ b+ ℓ,η follows because the path for wℓ includes s = 0. Next assume the loss increment and the Taylor error are first-order stable on D: |δv (z) − δu (z)| ≤ Lδ ∥v − u∥2 ,
(1 − b0 (z))|Qv (z) − Qu (z)| ≤ LQ ∥v − u∥2 .
(48)
A sufficient condition is a uniform increment Lipschitz bound |ℓ(θ0 + v, z) − ℓ(θ0 + u, z)| ≤ Lℓ,1 ∥v − u∥2 , together with (5). In that case one may take Lδ = Lℓ,1 ,
LQ = Lℓ,1 + κJ La,m (R),
La,m (R) :=
m X
!1/2 q 2 R2q−2
.
q=1
The factor (1 − b0 ) is enough because the Qv -part of the crossing correction is multiplied by bv − b 0 . Write x+ := max{x, 0} and x− := max{−x, 0}. For each cover center set + Cℓ,η (z) := b0 (z){δwℓ (z) + Lδ η} + {b+ ℓ,η (z) − b0 (z)}{(Qwℓ (z))+ + LQ η},
(49)
− Cℓ,η (z) := b0 (z){δwℓ (z) − Lδ η} − {b+ ℓ,η (z) − b0 (z)}{(Qwℓ (z))− + LQ η}.
(50)
23
Combining (47) with (48) gives the pointwise sandwich − + Cℓ,η (z) ≤ Cv (z) ≤ Cℓ,η (z),
v ∈ Dℓ .
(51)
Thus the continuous crossing problem has been reduced to the two finite classes − Cη− := {Cℓ,η : 1 ≤ ℓ ≤ Nη }.
+ Cη+ := {Cℓ,η : 1 ≤ ℓ ≤ Nη },
If |δwℓ | ≤ Bδ (R) and |Qwℓ | ≤ BQ (R) on the relevant sample space, one may use the common absolute bound BC,η := Bδ (R) + BQ (R) + (Lδ + LQ )η (52) + − + + − − for both Cℓ,η and Cℓ,η . More generally, let |Cℓ,η | ≤ Bℓ,η and |Cℓ,η | ≤ Bℓ,η be deterministic bounds. Define ( ( + + + − − − C /B , B > 0, ℓ,η ℓ,η ℓ,η e+ := e− := Cℓ,η /Bℓ,η , Bℓ,η > 0, C C ℓ,η ℓ,η + − 0, Bℓ,η = 0, 0, Bℓ,η = 0.
Put DC,η (t) := 1 + t + log(2Nη ).
(53)
The empirical-Bernstein radii are "
# D (t) D (t) C,η C,η e+ ) b+,EB (t) := CEB B + sbn (C A + , ℓ,η ℓ,η ℓ,η n n # " r D (t) D (t) C,η C,η b−,EB (t) := CEB B − sbn (C e− ) A + . ℓ,η ℓ,η ℓ,η n n r
The inflated-cover empirical-Bernstein crossing certificates are n o +,ηEB + b+,EB (t) , [D Cross (v; t) := inf Pn Cℓ,η +A ℓ,η ℓ:v∈Dℓ n o −,ηEB − b−,EB (t) . [D Cross (v; t) := sup Pn Cℓ,η −A ℓ,η
(54) (55)
(56) (57)
ℓ:v∈Dℓ
+,∗ −,∗ + − If BC,η := maxℓ Bℓ,η and BC,η := maxℓ Bℓ,η , the expected-valid EB versions obtained from the same event are +,ηEB,av
[D Cross
−,ηEB,av
[D Cross
+,ηEB
+,∗ −t (v; t) + 2BC,η e ,
(58)
−,ηEB
−,∗ −t (v; t) − 2BC,η e .
(59)
[D (v; t) := Cross [D (v; t) := Cross
A Rademacher alternative is obtained by applying Lemma 3.3 to the finite envelope classes. Define n
1X + εi Cℓ,η (Zi ) , 1≤ℓ≤Nη n i=1
b + := Eε max R C,η
24
n
1X − εi Cℓ,η (Zi ) . 1≤ℓ≤Nη n i=1
b − := Eε max R C,η If
− BC,η,osc := osc(Cη− ) < ∞,
+ BC,η,osc := osc(Cη+ ) < ∞,
then the global Rademacher crossing certificates are r
t + log 2 , ℓ:v∈Dℓ 2n r −,ηRad t + log 2 − − − b − 3B [D Cross (v; t) := sup Pn Cℓ,η − 2R . C,η C,η,osc 2n ℓ:v∈Dℓ +,ηRad
[D Cross
+ b + + 3B + (v; t) := inf Pn Cℓ,η + 2R C,η C,η,osc
(60) (61)
The corresponding expected-valid Rademacher versions omit the square-root terms: +,ηRad,av
[D Cross
(62)
− b− . (v) := sup Pn Cℓ,η − 2R C,η
(63)
ℓ:v∈Dℓ
−,ηRad,av
[D Cross
+ b+ , (v) := inf Pn Cℓ,η + 2R C,η
ℓ:v∈Dℓ
A patch-local Rademacher version can be used in place of the global one. Let n
+ rbℓ,η := Eε
n
1X + εi Cℓ,η (Zi ) , n i=1
− rbℓ,η := Eε
1X − εi Cℓ,η (Zi ) , n i=1
± ± ± and let Bℓ,η,osc := supz,z′ |Cℓ,η (z) − Cℓ,η (z ′ )|. Then, with a union bound over ℓ, the highprobability patch-local radii are r t + log Nη + log 2 + + b+,locRad (t) := 2b A rℓ,η + 3Bℓ,η,osc , (64) ℓ,η 2n r t + log Nη + log 2 −,locRad − − b A . (65) (t) := 2b rℓ,η + 3Bℓ,η,osc ℓ,η 2n
This gives +,ηlocRad
n o + b+,locRad (t) , Pn Cℓ,η +A ℓ,η ℓ:v∈Dℓ n o −,ηlocRad b−,locRad (t) . [ Cross (v; t) := sup Pn C − − A
[D Cross
D
4
(v; t) := inf
ℓ:v∈Dℓ
ℓ,η
ℓ,η
(66) (67)
Safe-Update Algorithms and Low-Dimensional Certified Search
The certificate has two algorithmic uses. This section focuses on the one used in the numerical experiments: a no-split full-ball mode. When the search space is a low-dimensional Euclidean ball, the aggregate endpoint (3) can be constructed uniformly over the whole ball 25
and then minimized on the same sample. The step is therefore selected after seeing the data, but the selection is still covered by the uniform event in Theorem 2.6. This is the regime in which the theory most closely resembles a local optimization method. The comparison with SGD should be made on reliability rather than speed. A standard gradient method may continue to move after the population descent signal has reached the sampling-noise scale. The certified full-ball method is more conservative: it updates only when the Section 3 endpoint proves a nonpositive population-risk increment. Its intended advantage is therefore fewer harmful accepted updates, smaller upward jumps in population risk, less oscillation near the noise floor, and safer stopping. It is not meant to have lower per-iteration cost than SGD. The second use is a split continuous-family release gate. A proposal sample may construct a low-dimensional continuum of possible updates, such as a local subspace ball, or a hull of recent directions. A separate certification sample then builds a uniform Taylor–crossing endpoint over that continuum and releases the minimizer only if the endpoint is negative. The point of splitting is not to certify a finite menu of candidates; when only one or a few fixed candidates remain, a direct holdout comparison is usually the simpler statistical tool. Splitting is useful when the final certification sample must optimize over a continuous family without invalid post-selection inference. Problem 4.1 (Baseline-safe local update). Given an incumbent parameter θ, a feasible candidate family D ∋ 0, and a failure probability δ, return either an updated parameter θ+ = θ + v or the incumbent θ+ = θ such that, with probability at least 1 − δ, L(θ+ ) ≤ L(θ),
L(ϑ) := P ℓϑ .
A margin version requires L(θ+ ) ≤ L(θ) − γ for an accepted update, where γ ≥ 0. For a feasible direction v, write δθ,v (z) := ℓθ+v (z) − ℓθ (z). The incumbent is the mathematical baseline because δθ,0 ≡ 0. A certified algorithm is therefore allowed to abstain: if the data do not prove a nonpositive population-risk increment, the correct output is the incumbent.
4.1
No-split local-ball search
Let E ⊂ Rd be a fixed or previously selected subspace with k = dim(E) ≪ N , and let Bρ (θ, E) := {v ∈ E : ∥v∥2 ≤ ρ, θ + sv ∈ Θ for 0 ≤ s ≤ 1}. For a radius ρ, construct the aggregate upper endpoint 0,+
+
b ρ (v) := PN J 0 + Good d ◦ (v; tR ) + Cross [ B (v; tJ ) + Rem [ B (v; tC ), U v m ρ ρ
v ∈ Bρ (θ, E),
(68)
using the computable components from Section 3. By Theorem 2.6, with failure probability at most e−tJ + e−tR + e−tC , b ρ (v), P δθ,v ≤ U
v ∈ Bρ (θ, E). 26
b ρ over the full ball: the selected Consequently, the same sample may be used to minimize U minimizer is one of the directions covered by the uniform event. Algorithm 1 No-split full-ball certified step Require: Incumbent θ, sample S, subspace E, radius ρ > 0, margin γ ≥ 0, failure budgets. 1: Set D = Bρ (θ, E), with 0 ∈ D. b in (68) on D. 2: Build the Section 3 endpoint U b 3: Compute v b ∈ arg minv∈D U(v), up to numerical tolerance. b 4: if U(b v ) ≤ −γ then 5: return θ+ = θ + vb. 6: end if 7: return the incumbent θ + = θ. On the validity event for a fixed incumbent, every accepted step from Algorithm 1 satisfies L(θ+ ) ≤ L(θ) − γ, while rejection leaves the risk unchanged. The numerical experiments below deliberately use the same fixed training sample at every update, matching the usual way SGD is run. This repeated-sample protocol is the right empirical comparison with SGD, but it should not be read as a theorem-level pathwise guarantee: after the center θt has been chosen adaptively from the same observations, the one-step certificate is being reused. A formal multi-step guarantee under repeated reuse would require an endpoint uniform over the entire adaptive path, or an adaptive-data-analysis correction [DFH+ 15]. The experiment therefore evaluates the stability profile of the Section 3 score under the same fixed-data protocol as the gradient baselines.
4.2
Worked example: hinge loss
The numerical experiments use the ordinary hinge loss rather than the squared-hinge loss. This choice fixes two points at once. First, the boundary 1 − Y X ⊤ θ = 0 is a genuine first-order nonsmooth interface for the hinge loss. Second, the certificate uses Taylor order m = 1, so its fixed-mask Taylor term is the same empirical first-order descent signal used by SGD. The purpose of the example is therefore to show that the Taylor–crossing endpoint is computable for a continuous search ball while keeping the comparison with gradient methods first-order. Let Y ∈ {−1, 1}, X ∈ Rd , U = Y X, and ℓθ (X, Y ) = (1 − U ⊤ θ)+ . Fix an incumbent θ, define R = 1 − U ⊤ θ,
Hv = U ⊤ v,
and search over Bρ = E ∩ {v : ∥v∥2 ≤ ρ},
k := dim(E),
with the full-dimensional case obtained by taking E = Rd . The local increment is δv = (R − Hv )+ − R+ . 27
(69)
The interface certificate is A(ϑ, Z) = 1 − Y X ⊤ ϑ, and we take interface-tube radius r = 0. Hence the path mask is bv = 1 min |R − sHv | = 0 , b0 = 1{R = 0}, χ0 = 1 − b 0 . 0≤s≤1
Fixed-mask first-order Taylor component. On R > 0, the hinge loss has gradient −U ; on R < 0, it has gradient 0. With the interface point excluded by χ0 , the first-order fixed-mask Taylor increment is Jv0 = −1{R > 0}Hv = ⟨−1{R > 0}U, v⟩.
(70)
Assume ∥U ∥2 ≤ B. Then the normalized first-order jet satisfies ∥ − 1{R > 0}U ∥2 ≤ B, so one may take κJ = B. For v ̸= 0, define gv0 = Jv0 /(B∥v∥2 ), and put g00 = 0. Let 1/2 sb0J (v) = PN (gv0 − PN gv0 )2 . Since m = 1, the normalized class only depends on the direction v/∥v∥2 . The low-dimensional entropy budget from (11) gives DJ,1 (t; k) := 2 + t + log 2 1 + (2N + 1)k . (71) Thus the empirical-Bernstein Taylor fluctuation radius is # " r 0,EB D (t ; k) D (t ; k) J,1 J J,1 J [ ρ (v; tJ ) = CEB B∥v∥2 sb0J (v) + B∥v∥2 . Good N N
(72)
Good-path remainder. On every path that does not hit the interface, the sign of R − sHv is fixed. The hinge loss is affine on each such region. Therefore the first-order Taylor expansion is exact on good paths, and d ◦ (v; tR ) = 0. Rem (73) 1 Inflated-cover crossing component. For w ∈ Bρ , define δw by (69), Jw0 by (70), and Qw = δw − Jw0 . The exact crossing correction is Cv = b0 δv + (bv − b0 )Qv . When b0 = 0, it reduces to Hv − R, R > 0 and Hv ≥ R, Cv = R − Hv , R < 0 and Hv ≤ R, 0, otherwise. At observations exactly on the interface, R = 0, one has Cv = δv = (−Hv )+ . Thus the crossing term is the computable correction that accounts for observations whose margin changes sign along the candidate path. Let w1 , . . . , wNη be an η-net of Bρ . For the hinge interface, the aggregate interface certificate is |R|, and ΓA (Z) = ∥U ∥2 in (45). The inflated mask (46) is therefore + ⊤ bℓ,η (Z) = 1 min |R − sU wℓ | ≤ η∥U ∥2 . (74) 0≤s≤1
28
The hinge loss is B-Lipschitz in θ, and the first-order Taylor term is also B-Lipschitz in v. Hence a valid choice in (48) is Lδ = B,
LQ = 2B.
(75)
The inflated upper crossing envelope (49) becomes + Cℓ,η = b0 {δwℓ + Bη} + {b+ ℓ,η − b0 }{(Qwℓ )+ + 2Bη}.
(76)
A simple deterministic range bound is obtained from |δwℓ | ≤ Bρ and |Qwℓ | ≤ 2Bρ: + |Cℓ,η | ≤ BC,η := 3Bρ + 3Bη.
(77)
e+ = C + /BC,η when BC,η > 0, and set it to zero otherwise. Put Define C ℓ,η ℓ,η DC (tC ; Nη ) := 1 + tC + log(2Nη ). The empirical-Bernstein crossing radius from (54) is " # r D (t ; N ) D (t ; N ) C C η C C η +,EB b e+ ) A bN (C + . ℓ,η (tC ) = CEB BC,η s ℓ,η N N The corresponding continuous-ball crossing budget is n o +,ηEB + b+,EB (tC ) . [ρ Cross (v; tC ) = inf PN Cℓ,η +A ℓ,η
(78)
(79)
ℓ:∥v−wℓ ∥2 ≤η
Endpoint optimized in the fixed-data experiments. Combining (68), (72), (73), and (79), the computed endpoint is 0,EB
bρhinge,1 (v) = PN Jv0 + Good [ρ U
+,ηEB
[ρ (v; tJ ) + Cross
(v; tC ),
v ∈ Bρ .
(80)
bρhinge,1 (v) uniformly With probability at least 1 − e−tJ − e−tC , this endpoint satisfies P δv ≤ U over v ∈ Bρ . The certified step is b hinge,1 (v), vbρ ∈ arg min U ρ v∈Bρ
bρhinge,1 (b and it is released only if U vρ ) ≤ −γ. The loss values enter the certificate through the 0 computable quantities δwℓ , Jwℓ , and Qwℓ at the inflated-cover centers. This is the part of the example that demonstrates computability of the Taylor–crossing endpoint over a continuous search ball.
29
Algorithm 2 First-order full-ball certified hinge-loss update Require: Incumbent θ, sample S, subspace E, radius grid ρ1 > · · · > ρR , cover scales ηr , margin γ, and failure budgets. 1: for each radius ρr do 2: Set Bρr = E ∩ {v : ∥v∥2 ≤ ρr }. 3: Compute Ri = 1 − Yi Xi⊤ θ, Ui = Yi Xi , and the first-order fixed-mask Taylor values 0 Jv,i = −1{Ri > 0}Ui⊤ v. 0,EB [ρ 4: Build the Taylor radius Good using (72). r 5: Construct an ηr -net {wℓ } of Bρr , the inflated masks (74), the crossing envelopes (76), and the crossing budget (79). b hinge,1 (v) in (80) over v ∈ Bρr . 6: Numerically minimize U ρr 7: end for 8: Let v b be the minimizer with the smallest endpoint value over all radii. 9: if the smallest endpoint is at most −γ then 10: return θ+ = θ + vb. 11: else 12: return the incumbent θ+ = θ. 13: end if Fixed-proposal certificate gate The full-ball update in Algorithm 2 uses the certificate as a search objective over a local candidate set. We also use a simpler mode in the numerical experiments: the certificate is applied as a release gate to a fixed externally supplied proposal. This mode is useful for isolating the stabilizing effect of the certificate, because the proposal itself can be kept identical to the SGD proposal. Let At be a proposal rule which, at the current iterate θt , returns a candidate direction prop vt . The fixed-proposal gate evaluates the same Taylor–crossing endpoint as above, but only at the single proposed direction. The update is released if the certified upper bound on the one-step population-risk increment is nonpositive; otherwise the null update is returned. Algorithm 3 Fixed-proposal certificate gate Require: Incumbent θt , sample St , proposal rule At , margin γ ≥ 0, failure budgets. prop 1: Compute the proposal vt = At (θt , St ). bt (vtprop ) on St . 2: Build the Taylor–crossing upper endpoint U bt (vtprop ) ≤ −γ then 3: if U 4: return θt+1 = θt + vtprop . 5: else 6: return θt+1 = θt . 7: end if In the stochastic experiment below, the proposal rule is the SGD proposal 1 X vtsgd = −ηgIt (θt ), gIt (θt ) = −1{1 − Yi Xi⊤ θt > 0}Yi Xi . |It | i∈I t
We call the resulting method Certified-SGD. 30
4.3
Numerical experiments
Data-generating model and evaluation. The experiments use the ordinary hinge loss from Section 4.2 with d = 2. The raw features are generated from a two-class Gaussian model with separation parameter 0.6, followed by symmetric label noise at rate 0.25. Each training set has n = 1200 observations. Coordinates are √ standardized using the training sample and then clipped to satisfy ∥X∥2 ≤ B, with B = 2 d. All reported risk values are oracle Monte Carlo estimates of the population hinge risk, computed on an independent sample of size 105 drawn from the same population. This population sample is used only for evaluation, not for selecting or certifying updates. Each experiment uses T = 60 update steps and 12 independent seeds. The SGD learning rate is η = 1.2. The certificate margin is γ = 0, and the release rule uses the calibrated empirical-Bernstein multiplier λcert = 0.15 on the empirical-Bernstein radii. This multiplier controls the empirical conservativeness of the release rule; it should not be interpreted as the theorem-level universal empirical-Bernstein constant. The experiments use a calibrated score for empirical comparison. The concentration budgets are tJ = tC = 1. Methods. The experiment compares three methods over mini-batch sizes b ∈ {16, 32, 64, 128, 256, 512}. For each seed and each b, all three methods use the same training set, the same populationevaluation sample, and the same mini-batch schedule I0 , . . . , IT −1 . Raw SGD always releases the stochastic proposal vtsgd . Certified-SGD Gate evaluates the Taylor–crossing endpoint at the same proposal and releases it only if the endpoint is nonpositive. This paired design isolates the effect of the release gate under the same stochastic first-order information. Certified Full-Ball instead searches over the finite polar grid Dgrid = {0} ∪ {ρ(cos aj , sin aj ) : ρ ∈ {0.02, 0.05, 0.10, 0.20, 0.40}, aj = 2πj/64, j = 0, . . . , 63}. bt (v) for every grid candidate, Thus |Dgrid | = 321. At each step, the method computes U selects the minimizer, and releases it only if the smallest endpoint is nonpositive. Since the implemented search set is finite, the computation should be read as a grid approximation to the continuous full-ball search rather than as exact continuous optimization. Stability metrics. For a population-risk trajectory L(θt ), define N↑ =
T −1 X
∆+ max = max[L(θt+1 ) − L(θt )]+ ,
1{L(θt+1 ) > L(θt )},
t
t=0
V
+
=
T −1 X
[L(θt+1 ) − L(θt )]+ .
t=0
We also record accepted steps and unsafe releases. An unsafe release is a released update whose certified upper endpoint is positive and whose independent population-risk increment is positive by more than 10−3 . These are empirical stability diagnostics, not formal multi-step coverage guarantees under adaptive data reuse. 31
Batch-size results. Figure 1 summarizes the batch-size sweep. Raw SGD releases every stochastic proposal and therefore exhibits substantial upward variation and many unsafe releases, especially at smaller and moderate batch sizes. Certified-SGD Gate is the most conservative method: it nearly eliminates upward movement but accepts very few proposals. Certified Full-Ball is less conservative because it searches over the certificate score on a local grid; it retains low upward variation while accepting more updates than the fixed-proposal gate.
(a) Total upward variation.
(b) Unsafe certificate-violating releases.
Figure 1: Batch-size sweep for the three methods. Raw SGD always releases its stochastic proposal. Certified-SGD Gate filters the same proposal through the certificate. Certified Full-Ball minimizes the same certificate over a 321-point polar grid and releases the selected update only when its certified upper bound is nonpositive. Error bars are standard errors over 12 seeds.
Representative trajectory and b = 64 summaries. We use b = 64 as the representative batch size for trajectory plots. At this batch size, Raw SGD and Certified Full-Ball have comparable final population risk, while the two certified methods sharply reduce upward variation. Table 1 reports the corresponding aggregate summaries. Raw SGD has mean final risk 0.8408, but it has 28.00 upward jumps and total upward variation V + = 0.2237. Certified-SGD Gate is conservative: it accepts only 1.83 updates on average, has no upward jumps, and has no unsafe releases. Certified Full-Ball attains the lowest mean final risk, 0.8394, while reducing upward variation to 0.0160 and producing no unsafe releases. Unlike the fixed-proposal gate, it can still have a few upward population-risk moves because it searches over a finite grid and can occasionally select a candidate whose mini-batch certificate score is optimistic. Overall, the two certified modes show complementary uses of the same local populationrisk certificate. The fixed-proposal gate isolates the reliability effect: when the stochastic SGD proposal is noisy, the gate suppresses upward population-risk excursions by rejecting endpoint-positive proposals. The full-ball search uses the certificate as an optimization objective; in the present two-dimensional hinge experiment, the grid-approximated search attains slightly lower final risk than Raw SGD while retaining much lower upward variation. 32
(a) Mean population-risk trajectory.
(b) Released-update certificate score.
Figure 2: Population-risk and released-certificate trajectories at b = 64. The left panel shows the oracle-MC population risk averaged over 12 seeds. The right panel shows the certificate score of the released update. For rejected gate proposals, the released update is the null update and the released score is recorded as zero.
(a) Representative population-risk trajectory.
(b) Pairwise crossing rates over seeds.
Figure 3: Pathwise comparison at b = 64. The representative trajectory uses a pre-specified median-crossing seed. The crossing-rate panel reports the fraction of seeds for which Raw SGD is above each certified method at each step. This event-based plot is useful because mean risk trajectories can average out pathwise upward excursions. Table 1: Population-risk and stability summaries at b = 64, averaged over 12 seeds. Parentheses give standard deviations. Certified-SGD Gate is the fixed-proposal release gate; Certified Full-Ball is the 321-point polar-grid search. Method
Final risk
Raw SGD 0.8408 (0.0080) Certified-SGD Gate 0.8530 (0.0170) Certified Full-Ball 0.8394 (0.0051)
N↑
V+
Unsafe releases
Accepted steps
28.00 (3.13) 0.00 (0.00) 3.33 (2.02)
0.2237 (0.0610) 0.0000 (0.0000) 0.0160 (0.0140)
24.58 (3.09) 0.00 (0.00) 0.00 (0.00)
60.00 (0.00) 1.83 (0.72) 11.50 (3.26)
33
References [ABF+ 24]
Anastasios Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. In International conference on learning representations, volume 2024, pages 55198–55218, 2024.
[BAL+ 21]
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1–34, 2021.
[BBM05]
Peter L BARTLETT, Olivier BOUSQUET, and Shahar MENDELSON. Local rademacher complexities. Annals of statistics, 33(4):1497–1537, 2005.
[BLM13]
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford, 2013.
[DFH+ 15]
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 349(6248):636–638, 2015.
[GPC16]
Mohammad Ghavamzadeh, Marek Petrik, and Yinlam Chow. Safe policy improvement by minimizing robust baseline regret. Advances in Neural Information Processing Systems, 29, 2016.
[Kni98]
Keith Knight. Limiting distributions for l 1 regression estimators under general conditions. Annals of statistics, pages 755–770, 1998.
[Koe05]
Roger Koenker. Quantile regression [m]. Econometric Society Monographs, Cambridge University Press, Cambridge, 2005.
[KOL06]
VLADIMIR KOLTCHINSKII. Rejoinder: Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2697– 2706, 2006.
[Kos08]
Michael R Kosorok. Introduction to empirical processes and semiparametric inference. Springer, 2008.
[LTDC19]
Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International conference on machine learning, pages 3652–3661. PMLR, 2019.
[MP09]
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740, 2009.
[Pol91]
David Pollard. Asymptotics for least absolute deviationregression estimators. Econometric Theory, 7(2):186–199, 1991.
34
[TCdSB+ 19] Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468):999–1004, 2019. [TTG15]
Philip Thomas, Georgios Theocharous, and Mohammad Ghavamzadeh. High confidence policy improvement. In International Conference on Machine Learning, pages 2380–2388. PMLR, 2015.
[VDVW96]
Aad W Van Der Vaart and Jon A Wellner. Weak convergence. In Weak convergence and empirical processes: with applications to statistics, pages 16–28. Springer, 1996.
[Ver25]
Roman Vershynin. High-dimensional probability, 2025.
[Wai19]
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
35