Comparator certificate

Generalization error bounds for deep models · Sho Sonoda

Latest verification result

Lean default kernel accepts the solution / Your solution is okay!

Date
2026-11-15
Commit
3d4ae20 (branch main)
Theorems checked
69 (all of comparator/config.json)
Permitted axioms
propext, Quot.sound, Classical.choice
Toolchain
Lean v4.32.0, Mathlib v4.32.0, lean4export v4.32.0, fake-landrun (macOS)

Last three lines of the output of ./script/comparator.sh:

Running Lean default kernel on solution.
Lean default kernel accepts the solution
Your solution is okay!

What Comparator certifies

Comparator takes a challenge (theorem statements with the proofs replaced by sorry) and a solution (the same statements with proofs), exports both environments with lean4export and checks, for every theorem listed in the configuration, that:

Everything in the import closure of the challenge is the trusted vocabulary of the certificate. comparator/Challenge.lean imports only the definition modules of the library (LeanDeepgen.Setting.*, Profiles.Defs, Tradeoff.Defs, Growth.Defs) and the example modules holding the definitions of the worked examples; the general-purpose tools come from lean-rademacher (FoML.ToMathlib, FoML.ToFoML). The statements are the paper's theorems in their Lean form, that is, with the corrections and generalizations described in the README.

Configuration

comparator/config.json lists 69 theorems of LeanDeepgen.Challenge (challenge module Challenge, solution module Solution; both are Lake libraries with srcDir = "comparator") and the three permitted axioms. Each challenge statement is copied verbatim (binders, implicitness, hypothesis order, universe levels) from the library theorem; the open lines (and the local notation, where the source module has one) of each section reproduce the context of the source module so that both files elaborate to identical kernel terms. The one exception is thm_dudley_subgaussian, whose auxiliary definitions live in a theorem module and are therefore unfolded inline in the challenge.

Not included: the cited theorems thm:guivarch-bass, cor:nilpotent-entropy, thm:breuillard-large-balls (not formalized; P2 takes their conclusion as a hypothesis), the Φ∞ part of lem:cot-output, and the integral identity of lem:log-split (used inside the proofs of prop:profiles (ii)/(iv)).

Note (2026-09-26): thm:rad.decomp.ent.ent (both forms) and thm:caa are a different case — they are formalized and remain in the challenge, but the manuscript was pruned on 2026-09-26 and no longer prints the corresponding appendix sections (formerly App. E, “A deterministic entropy alternative to thm:hidden-decomp”, and App. P, “Compact-Domain Arzelà–Ascoli Principle for Self-Maps”, in the pre-2026-09-26 lettering — not to be confused with the current Appendix E, “The Sudakov-type converse”, a different section under the reorganized lettering A–M introduced later the same day). The Lean modules Bounds/EntropyDecomp, Bounds/EntropyDecompSample and Growth/ArzelaAscoli are unchanged.

Note (2026-09-26, appendix reorganization): the manuscript's appendix was further reorganized the same day into a fixed order and lettering A–M (see SUMMARY.md): A conventions/basic facts, B literature, C bias–variance, D hidden–output, E the Sudakov-type converse (thm:sudakov-type, cor:matching, cor:sudakov-rates, prop:global_scalar_observable, prop:linear-interpolation, cor:rkhs-readout), F growth mechanisms, G the layerwise envelope, H variance profiles, I the four regimes and balancing depths, J teacher–student/neural-operator/implementation examples (prop:implementation, proof now in J.3), K deep ReLU networks, L chain-of-thought symbolic computation, M unrolled iterative solvers and samplers. All Lean labels referenced in the table below are unchanged by this reorganization; only their location within the appendix moved.

Note (2026-11-15, revised manuscript): the five theorems lem_shatter_rademacher, lem_relu_sort_hold, prop_relu_shatter, prop_relu_shatter_entropy and lem_relu_reset_sample are the statements added in the revised manuscript (App. K, “Variance: lower bounds on a sample”). Each is one library theorem named after the paper label and stating the whole paper statement (all parts, as one conjunction); prop_relu_shatter_entropy is the consequence for the entropy integral stated in Remarks (1) of that subsection. The challenge imports the three example modules Examples/ReLUSortHold, Examples/ReLUShatter and Examples/ReLUResetSample, which hold the definitions of the blocks, sample points and success sets. With these five theorems the certificate covers 69 theorems (64 before).

Mapping: paper label → challenge theorem → library declaration

Paper labelLeanDeepgen.Challenge.Library theorem (LeanDeepgen.)Module
thm:bv-generalthm_bv_generalbv_generalBounds/BiasVariance
thm:bv-general (gap)thm_bv_general_gapbv_general_gapBounds/BiasVariance
thm:bvthm_bvbvBounds/BiasVariance
thm:bv (gap)thm_bv_gapbv_gapBounds/BiasVariance
thm:hidden-decomp (= thm:mixed-sg)thm_hidden_decomphidden_decompBounds/HiddenOutput
thm:hidden-decomp (depth k)thm_hidden_decomp_depthhidden_decomp_depthBounds/HiddenOutput
prop:hilbert-sgprop_hilbert_sghilbert_sgBounds/HiddenOutput
prop:finite-lipschitz-sgprop_finite_lipschitz_sgfinite_lipschitz_sgBounds/HiddenOutput
thm:sudakov-type (= thm:sudakov)thm_sudakov_typesudakov_typeBounds/Sudakov
cor:sudakov-rates (i)cor_sudakov_ratessudakov_rates_expBounds/Sudakov
cor:sudakov-rates (ii)cor_sudakov_rates_polysudakov_rates_polyBounds/Sudakov
cor:matching (i)cor_matchingmatching_expBounds/Sudakov
cor:matching (ii)cor_matching_polymatching_polyBounds/Sudakov
thm:rad.decomp.ent.ent
(not printed in the current manuscript; kept in the library — formerly App. E of the ICLR draft)
thm_rad_decomp_ent_entrad_decomp_ent_entBounds/EntropyDecomp
thm:rad.decomp.ent.ent (sample)
(not printed in the current manuscript; kept in the library — formerly App. E of the ICLR draft)
thm_rad_decomp_ent_ent_samplerad_decomp_ent_ent_sampleBounds/EntropyDecompSample
thm:caa
(not printed in the current manuscript; kept in the library — formerly App. P of the ICLR draft)
thm_caatotallyBounded_unifMaps_iff_equicontinuousGrowth/ArzelaAscoli
cond:p1 (1)cond_p1cond_p1_of_totallyBoundedGrowth/Saturation
cond:p1 (2a)cond_p1_2acond_p1_of_equicontinuousGrowth/Saturation
cond:p1 (2b)cond_p1_2bcond_p1_of_uniformLipschitzGrowth/Saturation
cond:p1 (2c)cond_p1_2ccond_p1_of_nonexpandingGrowth/Saturation
cond:p1-ucontcond_p1_ucontcond_p1_ucontGrowth/Saturation
cond:p2-nilpcond_p2_nilpcond_p2_nilpGrowth/Polynomial
cond:e1-free-isocond_e1_free_isocond_e1_free_isoGrowth/Exponential
cond:e1p-theoremCcond_e1pcond_e1p_theoremCGrowth/Exponential
cond:e2-pingpongcond_e2_pingpongcond_e2_pingpongGrowth/Exponential
cond:e3cond_e3cond_e3Growth/MemoryExpansion
cor:superexpcor_superexpcor_superexpGrowth/MemoryExpansion
cor:doubleexpcor_doubleexpcor_doubleexpGrowth/MemoryExpansion
lem:log-split (inequality)lem_log_splitlog_one_add_div_leProfiles/LogSplit
prop:profiles (i)prop_profiles_iprofile_saturationProfiles/Profiles
prop:profiles (ii)prop_profiles_iiprofile_poly_boundedProfiles/Profiles
prop:profiles (iii)prop_profiles_iiiprofile_exp_boundedProfiles/Profiles
prop:profiles (iv)prop_profiles_ivprofile_poly_linearProfiles/Profiles
prop:profiles-finiteprop_profiles_finiteprofile_finiteProfiles/Profiles
tab:tradeoff PPthm_tradeoff_ppTradeoff.tradeoff_PPTradeoff/Regimes
tab:tradeoff EPthm_tradeoff_epTradeoff.tradeoff_EPTradeoff/Regimes
tab:tradeoff ELthm_tradeoff_elTradeoff.tradeoff_ELTradeoff/Regimes
tab:tradeoff PLthm_tradeoff_plTradeoff.tradeoff_PLTradeoff/Regimes
prop:implementation (a)prop_implementation_aprop_implementation_aExamples/Implementation
prop:implementation (b)prop_implementation_bprop_implementation_bExamples/Implementation
prop:implementation (c)prop_implementation_cprop_implementation_cExamples/Implementation
prop:global_scalar_observableprop_global_scalar_observableglobal_scalar_observableExamples/Readout
prop:linear-interpolationprop_linear_interpolationlinear_interpolationExamples/Readout
cor:rkhs-readoutcor_rkhs_readoutrkhs_readoutExamples/Readout
lem:cot-append-growthlem_cot_append_growthcot_append_growthExamples/ChainOfThought
lem:cot-branch-growthlem_cot_branch_growthcot_branch_growthExamples/ChainOfThought
lem:cot-output (window Φ_L)lem_cot_outputlipschitzWith_windowFeatureExamples/ChainOfThought
prop:cot-appendprop_cot_appendprop_cot_appendExamples/ChainOfThought
lem:fp-contractionlem_fp_contractionfp_contractionExamples/ODE
lem:ode-saturationlem_ode_saturationode_saturationExamples/ODE
lem:ode-euler-errorlem_ode_euler_erroreuler_global_errorExamples/ODE
prop:ode-fixedpointprop_ode_fixedpointprop_ode_fixedpointExamples/ODE
prop:ode-horizonprop_ode_horizonprop_ode_horizonExamples/ODE
prop:envelope (= prop:envelope-restated)prop_envelopeprop_envelopeGrowth/Envelope
cor:envelope-profiles (a), (b)cor_envelope_profilescor_envelope_profilesGrowth/Envelope
lem:reachable-radiuslem_reachable_radiuslem_reachable_radiusGrowth/Envelope
lem:ode-scheme-entropy (distance, covering)lem_ode_scheme_entropylem_ode_scheme_entropyExamples/ODE
lem:ode-scheme-entropy-profileequalSchemeClass_profileequalSchemeClass_profileExamples/ODE
lem:cot-branch-samplelem_cot_branch_samplelem_cot_branch_sampleExamples/ChainOfThought
lem:relu-layer-coveringlem_relu_layer_coveringlem_relu_layer_coveringExamples/ReLU
prop:relu-regimes (i)–(iii), upper boundsprop_relu_regimesprop_relu_regimesExamples/ReLU
prop:relu-regimes (iii), lower bound (E2)prop_relu_regimes_iii_lowerprop_relu_regimes_iii_lowerExamples/ReLU
lem:shatter-rademacher
(a class bounded on the sample that realizes every two-valued labeling has R̂S(G) ≥ (a1 − a0)/2)
lem_shatter_rademacherlem_shatter_rademacherBounds/Shatter
lem:relu-sort-hold (i)–(iii)
(sort–hold blocks: membership in FΛ, the word written on the sample, dS(fu,fv)² = Ham(u,v)/(16k), R̂S ≥ R/8)
lem_relu_sort_holdlem_relu_sort_holdExamples/ReLUSortHold
prop:relu-shatter (i)–(iii)
(load–count–sort blocks: membership in FΛ, shattering of k1B points at depth k1 + B + 1, R̂S ≥ R/16)
prop_relu_shatterprop_relu_shatterExamples/ReLUShatter
prop:relu-shatter, Remarks (1)
(entropy integral, Vk(S) ≥ √n/192 − √2/12)
prop_relu_shatter_entropyprop_relu_shatter_entropyExamples/ReLUShatter
lem:relu-reset-sample (i)–(ii)
(expand-and-reset maps: closed form off the success sets, disjoint success sets, covering bound and Vk(S) bound on every sample)
lem_relu_reset_samplelem_relu_reset_sampleExamples/ReLUResetSample
thm:bernoulli-sudakov (bonus)thm_bernoulli_sudakovFoML.ToFoML.bernoulli_sudakov (lean-rademacher)FoML/ToFoML/BernoulliSudakov
thm:dudley-subgaussian (bonus, inlined)thm_dudley_subgaussianFoML.ToFoML.dudley_subgaussian_finite_space (lean-rademacher)FoML/ToFoML/DudleySubGaussian

How to reproduce

git clone https://github.com/shosonoda/lean-deepgen.git
cd lean-deepgen
lake exe cache get && lake build

# once: Comparator and lean4export (for this project's Lean version) in ../comparator-tools/
mkdir -p ../comparator-tools && cd ../comparator-tools
git clone https://github.com/leanprover/comparator.git && (cd comparator && lake build comparator)
git clone --branch v4.32.0 https://github.com/leanprover/lean4export.git lean4export-v4.32.0 && (cd lean4export-v4.32.0 && lake build)
cd -

./script/comparator.sh   # about two minutes; ends with "Your solution is okay!"

The script builds Challenge and Solution, exports them and runs the checker on comparator/config.json. On Linux it uses landrun for sandboxing when available and Comparator's fake-landrun shim otherwise (always on macOS). The tool locations can be overridden with COMPARATOR_TOOLS, COMPARATOR_BIN, COMPARATOR_LEAN4EXPORT and COMPARATOR_LANDRUN.