Pith. sign in

REVIEW 2 major objections 5 minor 29 references

Disagreement on unlabeled data certifies any model's true risk

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 20:26 UTC pith:HUIOS2FS

load-bearing objection Fixed-surrogate disagreement bounds are real, tight, and worth building on; the 'simultaneous over all h' step covering the distillation experiments is not valid as written, and the protocol needs to state clearly that U is independent of the target. the 2 major comments →

arxiv 2602.23128 v2 pith:HUIOS2FS submitted 2026-02-26 cs.LG

Bound to Disagree: Generalization Bounds via Certifiable Surrogates

Mathieu Bazinet , Valentina Zantedeschi , Pascal Germain This is my paper
classification cs.LG MSC 68T05
keywords disagreement boundsgeneralization certificatessurrogate modelsunlabeled dataPAC-Bayessample compressionmodel compressionzero-one loss
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper claims that the true risk of any predictor can be bounded by the sum of a surrogate's certified risk and a computable disagreement penalty, measured on unlabeled data alone. The key result, Theorem 4, says that the risk gap between two classifiers is at most the inverted binomial tail of their empirical disagreement rate. Because the target model is never modified and no architectural assumptions enter, the bound applies to any deep network, transformer, or quantized model. Experiments show non-vacuous certificates on MNIST, CIFAR-10, and large language models, where classical norm- and partition-based bounds fail.

Core claim

The central discovery is a family of disagreement-based certificates. For the zero-one loss, Theorem 4 gives, with probability at least 1-δ over an i.i.d. unlabeled sample U, R_D(f) ≤ R_D(h) + Bin(m d^{0-1}_U(f,h), m, δ), where d^{0-1}_U is the empirical disagreement rate and Bin(k,m,δ) is the binomial tail inversion. This bound is derived from the identity |R_D(f)-R_D(h)| ≤ E[I[argmax f(x) ≠ argmax h(x)]], so the true risk gap is controlled by an expectation that a finite sample can pin down. The same scheme extends to Lipschitz losses (Theorem 5), using a Chernoff bound on the L1 difference of softmax outputs, and to general losses (Theorem 6) at the price of a labeled set. Combined with a

What carries the argument

The machinery is the disagreement measure d^{0-1}_U(f,h) = (1/m) Σ_i I[argmax f(x_i) ≠ argmax h(x_i)] paired with the binomial tail inversion Bin(k,m,δ). The load-bearing identity is |R_D(f)-R_D(h)| ≤ E_{(x,y)~D} I[argmax f(x) ≠ argmax h(x)], which converts an unobservable risk gap into an expectation of a bounded indicator; the sample analogue is exactly the disagreement rate. For Lipschitz losses, the same role is played by the L1 distance between softmax outputs, ‖σ(f(x))-σ(h(x))‖_1, with the Chernoff/kl^{-1} bound replacing the binomial inversion.

Load-bearing premise

The unlabeled set on which disagreement is measured must be sampled independently of both the target and the surrogate; when the disagreement set is carved from the same data that trained the target, the high-probability guarantee in the theorems does not follow.

What would settle it

With a fixed unlabeled set U of size m, enumerate all 2^m labelings of U as candidate surrogates and train one to match the target's labels on U (zero disagreement). Equation (4)'s bound then certifies the target's risk with no complexity penalty; for any target with nontrivial true risk, some other labeling in the family will violate the certificate, showing that the simultaneous union bound cannot hold without a complexity term.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Any target model—regardless of architecture, activation, loss, or optimizer—can receive a non-vacuous certificate once a close surrogate with a tight bound is available.
  • The certificate is closed-form and fully computable from an unlabeled sample and the two models' predictions; no norms, universal constants, or intractable complexity terms appear.
  • Quantized, distilled, or compressed variants of a model can be certified for deployment by bounding the true-risk gap against the original model.
  • The surrogate can be trained on unlabeled pseudo-labels to minimize disagreement, tightening the certificate (use case #2) for large language models.
  • The approach inherits the tightness of the surrogate's bound, so improving any single surrogate class immediately improves the target certificate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the disagreement rate is the only quantity carrying the bound, one could design probe sets—fixed, public unlabeled pools—to certify models at deployment time without any training data, as long as the probe is representative of the data distribution.
  • The independence requirement suggests a practical safeguard: reserve a fresh unlabeled set before any training, or use guarantees on public data drawn separately, before applying the theorem.
  • The same disagreement identity could be extended to distribution-shift detection: a change in disagreement rate on a fixed probe set between two temporal snapshots of a model would give a computable upper bound on true-risk drift.
  • The bound's form allows targeted minimization: optimizing the surrogate to minimize the right-hand side directly, rather than test accuracy, could yield certificates that approach the test-set bound without needing a held-out labeled set.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes a framework for bounding the true risk of an arbitrary target classifier f by combining (i) a risk bound for a 'surrogate' h that comes from an existing certification framework (sample compression, model compression, PAC-Bayes) and (ii) a concentration inequality on the disagreement between f and h measured on an unlabeled set U. Three disagreement bounds are stated: Theorem 4 for the 0-1 loss using Langford's binomial test-set bound; Theorem 5 for Lipschitz losses using a Chernoff/kl bound; and Theorem 6 for bounded non-Lipschitz losses using a labeled held-out set. The paper describes three use cases (fixed surrogate, surrogate selected/trained on U, and risk-gap certificate) and reports experiments on MNIST, CIFAR-10, and Amazon polarity, claiming tighter non-vacuous bounds than norm-based and partition-based baselines. The central claim is that the resulting certificates are fully computable, non-vacuous, and apply to any predictor without modifying its architecture or training procedure.

Significance. The decomposition idea is attractive and, if the technical gaps were repaired, would be a useful contribution: it decouples the complexity of the target from the certificate and reduces the problem to finding a close, certifiable surrogate. Theorems 4-6 are short, correct applications of standard concentration inequalities for a fixed surrogate independent of U, and the paper's breadth—three surrogate frameworks, three datasets, and released code—is a genuine strength. However, the invalid uniform bound in Eq. (4) and the unresolved independence of U from the target in Section 4.1 currently prevent the paper from substantiating its strongest claims. I regard these as fixable within the scope of a revision, not as fatal flaws.

major comments (2)
  1. [§3, Use case #2, Eq. (4)] The claimed 'simultaneously for all h∈H' bound is not derivable by the stated union bound. H is the unrestricted continuous-parameter hypothesis class of networks, and Theorem 5 contains no complexity, prior, or countable-cover term. A union bound requires a countable family or a data-independent prior Q(h) with ∑_h Q(h)≤1 and per-h failure probability δQ(h). As written, Eq. (4) is unsupported: for the class of all binary classifiers and a non-atomic D, for any f and any finite U there exists an h that agrees with f on U but has true disagreement 1/2, so the uniform statement cannot hold. Since §4.2 trains/selects the SubLoRA surrogate on U and relies on Eq. (4), the distillation results (Table 6, Table S4) are not covered by the stated theorems.
  2. [§4.1, experimental protocol] The independence of U from f is not established. The text states the target models are 'trained on the whole training set', while the experimental protocol carves a validation set and a disagreement set out of the same training set. If U contains training examples of f, the events in Theorem 4 (and Theorem 6's labeled set L) are not sampled independently of f, and the high-probability guarantees do not apply. Theorem 6 explicitly requires L to be removed before training f. The authors must clarify the actual data split; if the target is trained on the complement of U and the validation set, the phrase 'whole training set' is wrong, and if it is not, Tables 2–5 are not covered. This is load-bearing for all Section 4.1 certificates.
minor comments (5)
  1. [Eq. (2)] The left side of Eq. (2) should read L_D(h), not L_D(f). As printed, Eq. (2) would already bound the target's risk without any disagreement term, which contradicts the surrounding text.
  2. [Section 4, smoothed softmax bound] The text says the cross-entropy loss is bounded by ln(10^3/C), approximately 9.21 for C=10; from Definition S2 the bound is ln(C/α)=ln(10^4)≈9.21 with α=10^-3. The displayed formula appears to contain a typo.
  3. [Abstract] Minor grammar: 'and evaluating our disagreement bound on an unlabeled dataset' should be 'and evaluate' or 'by evaluating'.
  4. [§3, Bound Sketch] The 'BOUND SKETCH' block is not a formal theorem; consider labeling it as an informal schematic to avoid confusion with Theorems 4–6.
  5. [Eq. (4)] The notation δQ(h) is never defined. If Q is a distribution over H, clarify that Q(h) is a prior mass and that this requires a countable support or a prior measure; otherwise the notation is misleading.

Circularity Check

1 steps flagged

Use case #2 evaluates the disagreement certificate on the same unlabeled set used to train the surrogate; the asserted uniform union bound in Eq. (4) is not derivable for the unrestricted class H, so the distillation bounds in §4.2 are in-sample fits rather than independent predictions.

specific steps
  1. fitted input called prediction [Section 3, Use case #2 (Eq. 4); Section 4.2]
    "We obtain this result by applying Eq. (1) with a union bound over all h∈H, followed by a union bound with Eq. (3). ... Using the target models, we create pseudo-labels for the unlabeled disagreement set and train the surrogate models on both the labeled set S and the unlabeled set U. ... As the model is trained on both datasets, the bound holds simultaneously for all possible models, following Eq. (4)."

    Eq. (4) promises a simultaneous guarantee over all h∈H by 'a union bound over all h∈H', but H is uncountable and no summable prior Q(h) or countability condition is stated, so no such uniform concentration holds. In §4.2 the surrogate h⋆ is trained on U (distillation with pseudo-labels from f) to minimize the disagreement, and the certificate then evaluates DU(f,h⋆) on that same U. The disagreement term is therefore the training objective evaluated in-sample; without the missing uniform bound, the reported bound is not an out-of-sample prediction but a fitted value.

full rationale

For a fixed surrogate (use case #1), the decomposition is not circular: Theorem 4 combines the triangle-inequality bound |RD(f)−RD(h)|≤E I[fmax≠hmax] with the binomial test-set bound on an independent unlabeled set U, and the surrogate's own risk is certified by external frameworks (sample compression, model compression, PAC-Bayes). The self-citation to Bazinet et al. [2025] supplies a published sample-compression bound and is not the source of the disagreement argument, so it does not make the core derivation circular. The circularity is confined to use case #2: the paper trains the surrogate on U to minimize exactly the disagreement term that later appears in the certificate, and Eq. (4)'s 'union bound over all h∈H' cannot justify this for the unrestricted, uncountable hypothesis class H because no prior/complexity penalty is given. Separately, the experimental protocol in §4.1 carves U out of the training set while the target is described as trained on 'the whole training set', which violates the U⊥f independence needed by Theorem 4; this is a correctness/independence concern that further weakens the reported certificates but is not itself a by-construction equivalence. Overall, the central fixed-predictor theory is self-contained, but the distillation experiments of §4.2 reduce the claimed certificate to an in-sample fit, so the paper is partially circular.

Axiom & Free-Parameter Ledger

6 free parameters · 5 axioms · 0 invented entities

No new physical entities or model classes are introduced. The free parameters are experimental and loss-definition choices that directly influence the tightness of the reported certificates. The central derivation is otherwise self-contained, modulo the unproven uniform-bound assumption in Eq. (4).

free parameters (6)
  • softmax smoothing α = 1e-3
    Defines the bounded smoothed/clamped cross-entropy loss; selected by ablation on MNIST/CIFAR10 (Section D.4.1) and used in all cross-entropy tables.
  • Huber loss δ_H = 0.2
    Sets the Lipschitz constant K_ℓ=δ_H and the loss upper bound δ_H - (1/2)δ_H^2 in the distillation experiments (Section 4.2).
  • disagreement set size m = 20% MNIST/CIFAR10; 85% Amazon polarity
    Chosen by hand; directly controls the tightness of the Binomial/Chernoff concentration terms.
  • pretraining fractions = 20% MNIST, 50% CIFAR10 (model compression); 60/70% CIFAR10 (PAC-Bayes)
    Selected by hand; strongly affects surrogate test error and bound tightness.
  • SubLoRA subspace dimension / quantization levels / LoRA rank = e.g. 100/500/1000; 5/20; 0/2/4
    Hyperparameters searched to minimize the model-compression certificate.
  • Monte Carlo sample count V = 2000 (MNIST), 5000 (CIFAR10)
    Used in the PAC-Bayes Monte Carlo estimation of the bound; chosen by hand.
axioms (5)
  • domain assumption Data are i.i.d. from an unknown distribution D, and the unlabeled set U is sampled i.i.d. from the marginal of D and is independent of the target model f.
    Used by all theorems (Section 2); if the target is trained on the disagreement set, this fails, and the Section 4 protocol is ambiguous about it.
  • ad hoc to paper The disagreement bound can be made uniform over all h∈H by a union bound without adding any complexity or prior term.
    Eq. (4), Section 3 'Use case #2'; not proven and false as stated for infinite H; required for training surrogates on U.
  • standard math Prior surrogate certificates (sample compression Theorem 1, model compression Theorem 2, PAC-Bayes Theorem 3) are valid and computable as stated.
    Lifted from Bazinet et al. 2025, Lotfi et al. 2024, McAllester 2003/Maurer 2004.
  • standard math Yang et al.'s inequality |R_D(f)-R_D(h)| ≤ E[I[fmax(x)≠hmax(x)]] (Eq. 7).
    Proved in Theorem 4 via triangle inequality and a truth table; used throughout.
  • standard math Concentration inequalities: Langford's binomial test-set bound and Foong et al.'s Chernoff bound for unit-interval variables.
    Used as black-box tools in Theorems 4, 5 and 6.

pith-pipeline@v1.3.0-alltime-deepseek · 30883 in / 18951 out tokens · 163212 ms · 2026-08-02T20:26:36.594893+00:00 · methodology

0 comments
read the original abstract

Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset.We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and PAC-Bayes theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.

Figures

Figures reproduced from arXiv: 2602.23128 by Mathieu Bazinet, Pascal Germain, Valentina Zantedeschi.

Figure 1
Figure 1. Figure 1: Generalization bounds. Comparison between bounds from the literature (Norm-based and Partition-based) and our new disagreement-based bounds, using surrogates from sample compression (SC), model compression (MC) and PAC-Bayes (PB) theory. most bounds are vacuous when applied to medium-to-large neural networks or apply only to a modified version of the model rather than the original predictor. A recent line … view at source ↗
Figure 1
Figure 1. Figure 1: Unlike Hsu et al. [2021] and Suzuki et al. [2020], our [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the behavior of our disagreement bounds on MNIST using sample-compression methods. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Behavior of the disagreement bound according to [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 8 linked inside Pith

  1. [1]

    We now extend this result and upperbound the disagreement

    Equation 7 is not computable because it requires knowledge of the true data distributionD. We now extend this result and upperbound the disagreement. To do so, we start by applying the binomial test-set bound of Langford (2005) (see Theorem S8) on the right hand side of Eq. (7), withp=E (x,y)∼D I[f max(x)̸=h max(x)]. 1−δ≤P U∼D m E (x,y)∼D I[f max(x)̸=h ma...

    2005

  2. [2]

    , Xn bei.i.d.random variables Xi ∈ {0,1}and p=E[X i]

    Theorem S6(Test set bound of Langford [2005]).Let X1, . . . , Xn bei.i.d.random variables Xi ∈ {0,1}and p=E[X i]. Then, with probability at least1−δ, we have p≤ Bin nX i=1 Xi, n, δ ! , withBin(k, m, p) =Pk i=0 ( m i )pi(1−p) m−i and Bin(k, m, δ) = argsupp∈[0,1]{Bin(k, m, p)≥δ}. Theorem S7(Chernoff bound of Foong et al. [2022]).Let X1, . . . , Xn bei.i.d.r...

    2005

  3. [6]

    Com- parative generalization bounds for deep neural networks

    Tomer Galanti, Liane Galanti, and Ido Ben-Shaul. Com- parative generalization bounds for deep neural networks. Transactions on Machine Learning Research, 2023a. Tomer Galanti, Mengjia Xu, Liane Galanti, and Tomaso Poggio. Norm-based generalization bounds for sparse neural networks. InThirty-seventh Conference on Neural Information Processing Systems, 2023...

    2009

  4. [8]

    Theorem S20.For any distribution D over X × Y, for any predictorf∈ H, for any setH of predictors h:X → Y, for any loss ℓ:R C × Y →[0,1], for any dataset-independent prior distributionP on H, for any δ∈(0,1] , with probability at least 1−4δ over the draw of S∼ Dn, L∼ Dm and a set of 2V predictors h1, . . . , h2V ∼Q , where Q is a dataset-dependent posterio...

    2009

  5. [9]

    Generalization bounds for convolutional neural networks.arXiv preprint arXiv:1910.01487,

    Shan Lin and Jingwei Zhang. Generalization bounds for convolutional neural networks.arXiv preprint arXiv:1910.01487,

    Pith/arXiv arXiv 1910

  6. [11]

    A note on the pac bayesian theorem.arXiv preprint cs/0411099,

    Andreas Maurer. A note on the pac bayesian theorem.arXiv preprint cs/0411099,

    Pith/arXiv arXiv

  7. [14]

    Pick-to-learn for systems and con- trol: Data-driven synthesis with state-of-the-art safety guarantees.arXiv preprint arXiv:2512.04781,

    Dario Paccagnan, Daniel Marks, Marco C Campi, and Simone Garatti. Pick-to-learn for systems and con- trol: Data-driven synthesis with state-of-the-art safety guarantees.arXiv preprint arXiv:2512.04781,

    arXiv

  8. [16]

    Sample compression bounds for decision trees

    Mohak Shah. Sample compression bounds for decision trees. InMachine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007, volume 227 ofACM International Conference Proceeding Series, pages 799–806. ACM,

    2007

  9. [17]

    Non-vacuous generalization bounds for deep neural networks without any modification to the trained models.arXiv preprint arXiv:2503.07325,

    Khoat Than and Dat Phan. Non-vacuous generalization bounds for deep neural networks without any modification to the trained models.arXiv preprint arXiv:2503.07325,

    Pith/arXiv arXiv

  10. [18]

    Transformers: State-of-the-art natural language processing

    Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chau- mond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. Transformers: State-of-the-art ...

    2020

  11. [19]

    Character- level convolutional networks for text classification

    Xiang Zhang, Junbo Jake Zhao, and Yann LeCun. Character- level convolutional networks for text classification. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 649–657,

    2015

  12. [22]

    By definition,Z≤1 , which means that 1 Z 2−lC(ˆh)2−2 log2 lC(ˆh) ≥2 −lC(ˆh)2−2 log2 lC(ˆh) =⇒ Bin κ, n,1 Z 2−lC(ˆh)2−2 log2 lC(ˆh)δ ≤ Bin κ, n,2−lC(ˆh)2−2 log2 lC(ˆh)δ

    and the union bound, we get ∀ˆh∈ HC :R D(ˆh)≤ Bin κ, n,1 Z 2−lC(ˆh)2−2 log2 lC(ˆh)δ .(6) The binomial tail inversion is decreasing with respect toδ, as a smallerδ means a looser bound. By definition,Z≤1 , which means that 1 Z 2−lC(ˆh)2−2 log2 lC(ˆh) ≥2 −lC(ˆh)2−2 log2 lC(ˆh) =⇒ Bin κ, n,1 Z 2−lC(ˆh)2−2 log2 lC(ˆh)δ ≤ Bin κ, n,2−lC(ˆh)2−2 log2 lC(ˆh)δ . Th...

    2021

  13. [24]

    The second inequality comes from theKℓ-Lipschitz continuity ofℓ

    The first inequality stems from the triangular inequality. The second inequality comes from theKℓ-Lipschitz continuity ofℓ. The 1-norm of the difference of two softmax distribution is always positive and always bounded by2, which can easily be proven using triangle inequality. ∥σ(f(x))−σ(h(x))∥ 1 ≤ ∥σ(f(x))∥1 +∥σ(h(x))∥ 1 ≤2. From Chernoff’s bound for ran...

    2022

  14. [25]

    To use Chernoff’s bound, we need a loss in the unit interval, so we normalize it

    LD(f)−E h∼Q LD(h) = E h∼Q [LD(f)− LD(h)] = E h∼Q E (x,y)∼D ℓ(f(x), y)−E (x,y)∼D ℓ(h(x), y) = E h∼Q E (x,y)∼D [ℓ(f(x), y)−ℓ(h(x), y)] ≤E h∼Q E (x,y)∼D |ℓ(f(x), y)−ℓ(h(x), y)| =E (x,y)∼D E h∼Q |ℓ(f(x), y)−ℓ(h(x), y)| The inequality stems from the triangular inequality. To use Chernoff’s bound, we need a loss in the unit interval, so we normalize it. 0≤ |ℓ(f...

    2022

  15. [28]

    We consider 5 different seeds for the random clusters

    MNIST CIFAR10 Train set cluster Disagreement set cluster Random Cluster 86.53±0.10 90.29±0.17 86.55±0.53 90.58±0.47 137.97±0.55 111.11±0.08 90 100 110 120 130 (a) Zero-one loss MNIST CIFAR10 Train set cluster Disagreement set cluster Random Cluster 7.9529±0.0079 8.3171±0.0152 7.9546±0.0475 8.3437±0.0431 12.6901±0.0510 10.2348±0.0070 8 9 10 11 12 (b) Smoot...

    2025

  16. [29]

    and the subspace compression approach implemented by Lotfi et al. [2022]. This SubLoRA model is then trained on the remaining datapoints, where the bound is also computed. Hyperparameters for MNIST • Portion of training set for pretraining : 20% • Number of pretraining epochs : 100 • Pretraining learning rate :10 −3 • Dropout probability : 0.0 • Optimizer...

    2022

  17. [1958]

    Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.ArXiv preprint, abs/1910.01108,

    Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.ArXiv preprint, abs/1910.01108,

    Pith/arXiv arXiv 1910

  18. [2001]

    Margin-Sparsity Trade-Off for the Set Covering Machine

    François Laviolette, Mario Marchand, and Mohak Shah. Margin-Sparsity Trade-Off for the Set Covering Machine. InMachine Learning: ECML 2005, volume 3720, pages 206–217. Springer Berlin Heidelberg,

    2005

  19. [2003]

    On the perceptron’s compression

    Shay Moran, Ido Nachum, Itai Panasoff, and Amir Yehuday- off. On the perceptron’s compression. InBeyond the Hori- zon of Computability: 16th Conference on Computability in Europe, CiE 2020, Fisciano, Italy, June 29–July 3, 2020, Proceedings 16, pages 310–325. Springer,

    2020

  20. [2005]

    The set covering machine with data-dependent half-spaces

    Mario Marchand, Mohak Shah, John Shawe-Taylor, and Marina Sokolova. The set covering machine with data-dependent half-spaces. InMachine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pages 520–527. AAAI Press,

    2003

  21. [2012]

    Gintare Karolina Dziugaite and Daniel M. Roy. Data- dependent pac-bayes priors via differential privacy. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 8440–8450,

    2018

  22. [2018]

    Sample compression for self certified continual learning.arXiv preprint arXiv:2503.10503,

    Jacob Comeau, Mathieu Bazinet, Pascal Germain, and Cem Subakan. Sample compression for self certified continual learning.arXiv preprint arXiv:2503.10503,

    arXiv

  23. [2019]

    Bound to Disagree: Generalization Bounds via Certifiable Surrogates (Supplementary Materials) Mathieu Bazinet1 Valentina Zantedeschi1,2 Pascal Germain1 1Département d’informatique et génie logiciel, Université Laval, Québec, Qc, Canada 2ServiceNow Research, Montreal, Qc, Canada A DEFINITIONS AND THEORETICAL RESULTS FROM THE LITERATURE Definition S1(Pérez-...

    2021

  24. [2020]

    A coreset selection of coreset selection literature: Introduction and recent advances.arXiv preprint arXiv:2505.17799,

    Brian B Moser, Arundhati S Shanbhag, Stanislav Frolov, Fed- erico Raue, Joachim Folz, and Andreas Dengel. A coreset selection of coreset selection literature: Introduction and recent advances.arXiv preprint arXiv:2505.17799,

    arXiv

  25. [2021]

    A note on the chernoff bound for random variables in the unit interval.ArXiv preprint, abs/2205.07880,

    Andrew YK Foong, Wessel P Bruinsma, and David R Burt. A note on the chernoff bound for random variables in the unit interval.ArXiv preprint, abs/2205.07880,

    Pith/arXiv arXiv

  26. [2022]

    Statistical learning with lipschitz and convex loss functions.arXiv preprint arXiv:1810.01090,

    Geoffrey Chinot, Guillaume Lecué, and Matthieu Lerasle. Statistical learning with lipschitz and convex loss functions.arXiv preprint arXiv:1810.01090,

    Pith/arXiv arXiv

  27. [2024]

    Adversarial active learning for deep networks: a margin based approach

    Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach. arXiv preprint arXiv:1802.09841,

    Pith/arXiv arXiv

  28. [2025]

    Distilling the knowledge in a neural network.arXiv preprint arXiv:1503.02531,

    Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network.arXiv preprint arXiv:1503.02531,

    Pith/arXiv arXiv

  29. [4090]

    Finally, the PAC-Bayesian experiments and the model distillation experiments were computed with Python 3.12.4 and a NVidia A100 SXM4

    The coreset experiments and the model compression experiments were computed with Python 3.12.4 and a NVidia H100 SXM5. Finally, the PAC-Bayesian experiments and the model distillation experiments were computed with Python 3.12.4 and a NVidia A100 SXM4. Libraries.All libraries used can be found within the code. Notably, we use DeepCore [Guo et al., 2022] (...

    2022