Pith. sign in

REVIEW 2 major objections 5 minor 50 references

Private List Learnability vs. Online List Learnability

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that private PAC list learning is strictly weaker than online list learning for k>1: a finite k-Littlestone dimension is necessary but not sufficient, witnessed by the class of (k+1)-labeled monotone functions over N.

desk verdict The separation result and k-monotone dimension are real contributions, but the proof of the k-Littlestone necessity theorem has an arithmetic error that invalidates the reduction; the main claim is unsupported as written. read the letter →

arxiv 2506.12856 v1 pith:ZJFUXQ2M submitted 2025-06-15 cs.LG cs.DS

Steve Hanneke , Shay Moran , Hilla Schefler , Iska Tsubari This is my paper · ORCID
classification cs.LGcs.DS MSC 68Q3268T0505D10
keywords k-listlearningdifferentialprivacyonlinePACk-Littlestonedimensionk-monotonemonotonefunctionsRamseytheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether the known equivalence between differential privacy and online learning in multiclass PAC classification extends to k-list learning, where a learner outputs a list of k labels and errs only if the true label is absent. It establishes one direction: any differentially private k-list learner must have finite k-Littlestone dimension, hence is online k-list learnable. It then breaks the converse. For every k>1, the class of (k+1)-labeled monotone functions on the natural numbers is online k-list learnable with mistake bound 1 but is not DP PAC k-list learnable. The separation is certified by a new parameter, the k-monotone dimension, which is finite in the multiclass setting exactly when the threshold dimension is but becomes an independent barrier for lists. The upshot is that private list learnability needs at least two incomparable combinatorial conditions, and a single-parameter characterization may not exist.

What carries the argument

Two combinatorial dimensions carry the argument. The k-Littlestone dimension is the depth of the deepest shattered (k+1)-ary mistake tree and characterizes online k-list learnability. The k-monotone dimension is the largest d such that the class restricted to d ordered points contains all monotone functions over k+1 ordered labels, generalizing the threshold dimension. The lower-bound proofs replace full comparison-based predictions with the weaker requirement of comparison-based loss, then reduce to the interior point problem; one reduction uses a Ramsey theorem for b-ary trees, the other uses classical hypergraph Ramsey to force approximately comparison-based marginal probabilities for the k+1 relevant labels.

What would settle it

A concrete DP PAC k-list learner for the (k+1)-labeled monotone functions over N for some k>1, for instance a 2-list learner for 3-labeled monotone functions with sample complexity o(log* n) on [n], would refute the main separation; alternatively, proving the PAC-to-empirical conversion fails for list learning would remove the lower bounds' reach over general PAC learners.

Watch

Extended reading notes

Core claim

For list learning, the multiclass equivalence between private learnability and online learnability holds in only one direction. The paper proves that finite k-Littlestone dimension is necessary for DP PAC k-list learnability, and separately that finite k-monotone dimension is also necessary. It then constructs two separating classes for k>1: the class of all (k+1)-labeled monotone functions on N has k-Littlestone dimension 1 and infinite k-monotone dimension, while the class of concepts realizing a single branch of an infinite (k+1)-ary tree has infinite k-Littlestone dimension and k-monotone dimension 1. The first class is online k-list learnable with at most one mistake yet not privately list learnable, so online learnability does not imply private learnability. Whether finite k-Littlestone dimension together with finite k-monotone dimension is sufficient for private k-list learnability remains open.

Load-bearing premise

The lower bound proofs start from a differentially private empirical list learner, and the step that converts any private PAC list learner into a private empirical one with only a constant factor sample blow-up is asserted to carry over from the multiclass case without proof, so if that conversion fails the impossibility might only hold for empirical learners.

Editorial extensions

If this is right

  • Every DP PAC k-list learnable class is online k-list learnable, since finite k-Littlestone dimension is necessary.
  • For k=1 the two notions coincide, recovering the known multiclass equivalence.
  • For k>1 there are classes online k-list learnable with mistake bound 1 that are not DP PAC k-list learnable.
  • Both finite k-Littlestone dimension and finite k-monotone dimension are necessary for private list learning, and neither alone is sufficient.
  • Any private k-list learner for a class with k-Littlestone dimension d requires a sample complexity of Omega(log* d), and similarly for k-monotone dimension d.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The natural conjecture left by the paper is that finite k-Littlestone dimension plus finite k-monotone dimension is sufficient for DP k-list learnability; testing this on the two constructed separating classes would be a direct next step.
  • The separation uses the infinite domain N, so a finite-domain analogue would give a quantitative question: how large must the domain be before the sample-complexity gap between private and non-private list learning becomes visible.
  • The comparison-based loss relaxation may transfer to other structured prediction settings, such as partial concepts or list regression, where the full comparison-based prediction assumption is too strong.
  • The k-monotone dimension could interact with representation-based characterizations of pure differential privacy, suggesting that list learning may require a genuinely multi-parameter theory.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies k-list PAC learning under differential privacy and compares it with online k-list learning. The main claims are: (i) finite k-Littlestone dimension is necessary for private k-list learnability (Theorem 2 and Corollary A(i)); (ii) finite k-monotone dimension, a newly introduced generalization of threshold dimension, is also necessary (Theorem 4 and Corollary A(ii)); and (iii) for every k>1 these two dimensions are independent, yielding a class that is online k-list learnable but not privately k-list learnable (Theorem 5 and Corollary B). The paper thus claims the first separation between private and online learnability in the list-learning setting. The conceptual framework is interesting, and the proof of Theorem 5 is clean, but the proof of the necessity of finite k-Littlestone dimension contains a concrete arithmetic error in the interior-point reduction that invalidates the proof of Theorem 2 as written.

Significance. If the technical gaps are repaired, the paper would make a notable contribution: it identifies a natural setting where the classical equivalence between private and online learnability breaks down, and it introduces a new combinatorial dimension that is necessary but not sufficient for private list learnability. The separation itself, Corollary B(iii), does not depend on the flawed interior-point argument for Theorem 2; it uses Theorem 4 and Theorem 5, whose proofs appear essentially sound conditional on the unproved Lemma 8. The generalization of the tree Ramsey theorem of FHM+24 to (k+1)-ary trees is a useful methodological contribution. The paper is clearly written, with detailed proofs and an honest statement of the open question whether finiteness of both dimensions is sufficient.

major comments (2)
  1. [Section 5.2, Proposition 17 and Lemma 18] The claim that each of the five summands bounding the failure probability is smaller than 1/20 is arithmetically false for the first summand. With l = floor(log2 n), n * exp(-l/(8(k+1))) = exp(ln n - (log2 n + O(1))/(8(k+1))) = n^{1 - 1/(8(k+1) ln2) + o(1)}, which diverges for every fixed k >= 1; for k=1 it is roughly n^{0.91}. This is not a loose-constant artifact of the Chernoff bound: under the independence model used in the proof, the per-interval probability of an almost-correct interval below x_m is exp(-Theta(l/(k+1))), so the expected number of such intervals is n^{1 - Theta(1/(k+1))}, which is polynomial in n. Since Algorithm 1 outputs the deepest almost-correct interval, the presence of such intervals below x_m would place the output outside [d1, dm], so the utility guarantee of Proposition 17 fails. Consequently Lemma 14, Theorem 2, Corollary A(i), and Corollary B(i) are unsupported as written. A plausible repair is to take l = C(k) * floor(log2 n) with C(k) > 8(k+1) ln2 and to require, in Lemma 15, input spacing larger than l; the proof of Lemma 19 would then still find an interval inside S because consecutive inputs are spaced by more than l. This repair needs to be carried out in detail, including the constants in Lemmas 18 and 19 and the rescaling argument in Lemma 15.
  2. [Section 3.2, Lemma 8] The extension of Lemma 5.9 of BNSV15 from ordinary classification to k-list learning is asserted without proof: the paper says the proof 'also applies to more general settings, including the setting of list learning.' This step is load-bearing because both lower-bound proofs (Theorem 2 and Theorem 4) first convert a PAC learner into an empirical learner, and the impossibility results are then proved only for empirical learners. Please provide a proof, or a precise citation to a version of the subsampling argument that treats hypotheses mapping to k-element subsets. I expect a short appendix proof is feasible, since the standard subsampling-amplification argument does not appear to use the single-label nature of the output.
minor comments (5)
  1. [Section 2.1] The first sentence says 'we outline the proof of Theorem 4', but this section is about the k-Littlestone dimension lower bound and should refer to Theorem 2.
  2. [Section 3.1] In the paragraph defining the k-Littlestone dimension, 'Littlestione dimension' is a typo for 'Littlestone dimension'.
  3. [Definition 12] The type set is written as {0,1}^{m+1}; since the tree has arity k+1, it should be {0,...,k}^{m+1}.
  4. [Lemma 22] The accuracy parameter is written as 1/200k(k+), which appears to be a typo for 1/(200k(k+1)), matching the statement of Theorem 4.
  5. [Appendix B] There are unresolved 'See ??' references in the proof of Theorem 11; these placeholders should be filled or removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central arguments are derived from first principles with cited, published external theorems.

full rationale

The paper's derivation chain is not circular. The two main lower-bound results (Theorem 2 and Theorem 4) are proven from first principles within the manuscript: Lemma 13 is established using a Ramsey theorem for trees, whose b-ary generalization is proved in Appendix B rather than merely imported; Lemma 14 gives a self-contained reduction from the interior point problem using the external BNSV15 lower bound; and Lemma 22/25 develop their own packing and comparison-based arguments with proofs in Appendices A.3 and A.4. The citations to MSTY23 for the k-Littlestone characterization and to FHM+24 for the tree Ramsey theorem involve overlapping authors, but these are published theorems with proofs and are not fitted to this paper's conclusions, nor are they used as a black-box uniqueness premise that forbids alternatives. The explicit online learner for Mk(N) in Section 4 independently demonstrates online k-list learnability, and the necessity results do not presuppose the equivalence they disprove. Lemma 8's extension of the BNSV15 empirical-learner conversion to list learning is asserted without proof, and Proposition 17's utility calculation appears to contain a genuine arithmetic error: the first summand n * exp(-floor(log2 n)/(8(k+1))) grows as n^{1-c} rather than being smaller than 1/20 for large n. However, these are correctness risks, not circularity: no prediction is equivalent by construction to a fitted input, no definition is defined in terms of the target result, and no load-bearing step reduces to a self-citation that itself is unverified. The honest finding is therefore no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper's theorems are derived from standard results in Ramsey theory, differential privacy (interior point lower bound), and online learning (k-Littlestone characterization). The main unproved input is the extension of the empirical-learner conversion lemma to list learning.

assumptions (4)
  • domain assumption The proof of BNSV15 Lemma 5.9 (private PAC to empirical learner conversion) extends to list learning.
    Invoked in Lemma 8 remark (Section 3.2) to justify transforming any DP PAC k-list learner into a DP empirical k-list learner with constant factor sample complexity increase; the authors state this extension without proof.
  • standard math Finiteness of the k-Littlestone dimension characterizes online k-list learnability (MSTY23).
    Used in Section 4 to conclude that M_k(N) with mistake bound 1 has LD_k = 1, and to derive Corollary B from Theorem 5.
  • standard math Interior point problem lower bound of BNSV15 (Theorem 9).
    Used in Lemma 15 and the reductions in Sections 5 and 6 to derive sample complexity lower bounds.
  • standard math Ramsey theorem for hypergraphs (Erdos-Rado) and Ramsey theorem for trees (FHM+24, generalized to b-ary trees).
    Used in Lemmas 13 and 24 to obtain comparison-based structure on large subtrees or subsets.
invented entities (1)
  • k-monotone dimension (MD_k)
    purpose: A combinatorial parameter conjectured to be necessary (and possibly part of a sufficient characterization) for DP k-list learnability; generalizes the threshold dimension.
    New definition (Definition 3); the paper proves necessary-condition theorems about it but provides no independent falsifiable handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Private List Learnability vs. Online List Learnability." pith.science (2026). https://pith.science/paper/ZJFUXQ2M

@misc{pith2026250612856,
  author       = {Pith},
  title        = {Pith review of: Private List Learnability vs. Online List Learnability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZJFUXQ2M}},
  note         = {Machine review of arXiv:2506.12856}
}
abstract

This work explores the connection between differential privacy (DP) and online learning in the context of PAC list learning. In this setting, a $k$-list learner outputs a list of $k$ potential predictions for an instance $x$ and incurs a loss if the true label of $x$ is not included in the list. A basic result in the multiclass PAC framework with a finite number of labels states that private learnability is equivalent to online learnability [Alon, Livni, Malliaris, and Moran (2019); Bun, Livni, and Moran (2020); Jung, Kim, and Tewari (2020)]. Perhaps surprisingly, we show that this equivalence does not hold in the context of list learning. Specifically, we prove that, unlike in the multiclass setting, a finite $k$-Littlestone dimensio--a variant of the classical Littlestone dimension that characterizes online $k$-list learnability--is not a sufficient condition for DP $k$-list learnability. However, similar to the multiclass case, we prove that it remains a necessary condition. To demonstrate where the equivalence breaks down, we provide an example showing that the class of monotone functions with $k+1$ labels over $\mathbb{N}$ is online $k$-list learnable, but not DP $k$-list learnable. This leads us to introduce a new combinatorial dimension, the \emph{$k$-monotone dimension}, which serves as a generalization of the threshold dimension. Unlike the multiclass setting, where the Littlestone and threshold dimensions are finite together, for $k>1$, the $k$-Littlestone and $k$-monotone dimensions do not exhibit this relationship. We prove that a finite $k$-monotone dimension is another necessary condition for DP $k$-list learnability, alongside finite $k$-Littlestone dimension. Whether the finiteness of both dimensions implies private $k$-list learnability remains an open question.

Figures

Figures reproduced from arXiv: 2506.12856 by the authors.

Figure 1
Figure 1. The 3-chain C = {∅, 0, 02} is of type ⃗t(C) = (0, 2). The 3-chain C˜ = {1, 100, 1002} has the same type as C. Assume now that T is a Littlestone tree, with internal vertices from a domain X , and edges from a label space Y. To ease the notations, from this point we will assume that the b distinct labels on the outgoing edges of each internal vertex are {0, 1, . . . , b − 1} where by writing “i”, we mean the label on… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 46 canonical work pages

  1. [1]

    Angelopoulos and Stephen Bates

    Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification. CoRR , abs/2107.07511, 2021

    arXiv 2021

  2. [2]

    Private and online learnability are equivalent

    Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. J. ACM , 69(4):28:1--28:34, 2022

    work page 2022

  3. [3]

    A theory of PAC learnability of partial concept classes

    Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of PAC learnability of partial concept classes. In Proc.\ 62nd Symp.\ Foundations of Computer Science (FOCS) , pages 658--671, 2021

    work page 2021

  4. [4]

    Abernethy, Elad Hazan, and Alexander Rakhlin

    Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT , pages 263--274. Omnipress, 2008

    work page 2008

  5. [5]

    Private PAC learning implies finite littlestone dimension

    Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Proc.\ 51st Symp.\ Theory of Computing (STOC) , pages 852--860, 2019

    work page 2019

  6. [6]

    A unified characterization of private learnability via graph theory, 2023

    Noga Alon, Shay Moran, Hilla Schefler, and Amir Yehudayoff. A unified characterization of private learnability via graph theory, 2023

    work page 2023

  7. [7]

    Of dice and games: A theory of generalized boosting, 2024

    Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen. Of dice and games: A theory of generalized boosting, 2024

    work page 2024

  8. [8]

    A characterization of multiclass learnability

    Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In Proc.\ 63rd Symp.\ Foundations of Computer Science (FOCS) , pages 943--955. IEEE, 2022

    work page 2022

Show all 50 references
  1. [9]

    Multiclass boosting: Simple and intuitive weak learning criteria

    Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: Simple and intuitive weak learning criteria. In NeurIPS , 2023

    2023

  2. [10]

    Stability is stable: Connections between replicability, privacy, and adaptive generalization

    Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In STOC , pages 520--527. ACM , 2023

    2023

  3. [11]

    Improper multiclass boosting

    Nataly Brukhim, Steve Hanneke, and Shay Moran. Improper multiclass boosting. In COLT , volume 195 of Proceedings of Machine Learning Research , pages 5433--5452. PMLR , 2023

    2023

  4. [12]

    Proper learning, helly number, and an optimal SVM bound

    Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal SVM bound. In COLT , volume 125 of Proceedings of Machine Learning Research , pages 582--609. PMLR , 2020

    2020

  5. [13]

    An equivalence between private classification and online prediction

    Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In FOCS , pages 389--402. IEEE , 2020

    2020

  6. [14]

    Characterizing the sample complexity of private learners

    Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In ITCS . ACM, 2013

    2013

  7. [15]

    Characterizing the sample complexity of pure private learners

    Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learners. Journal of Machine Learning Research , 20(146):1--33, 2019

    2019

  8. [16]

    Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. Differentially private release and learning of threshold functions. In Proc.\ 56th Symp.\ Foundations of Computer Science (FOCS) , pages 634--649, 2015

    2015

  9. [17]

    New Separations in the Complexity of Differential Privacy

    Mark Bun. New Separations in the Complexity of Differential Privacy. PhD thesis, Harvard University, Graduate School of Arts & Sciences, 2016

    2016

  10. [18]

    Local borsuk-ulam, stability, and replicability

    Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff. Local borsuk-ulam, stability, and replicability. In STOC , pages 1769--1780. ACM , 2024

    2024

  11. [19]

    Probably approximately precision and recall learning

    Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao. Probably approximately precision and recall learning. CoRR , abs/2411.13029, 2024

    2024

  12. [20]

    Stability and replicability in learning

    Zachary Chase, Shay Moran, and Amir Yehudayoff. Stability and replicability in learning. In FOCS , pages 2430--2439. IEEE , 2023

    2023

  13. [21]

    A characterization of list learnability

    Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In STOC , pages 1713--1726. ACM , 2023

    2023

  14. [22]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Proc.\ 3rd Conf.\ Theory of Cryptography (TCC) , volume 3876, pages 265--284, 2006

    2006

  15. [23]

    The algorithmic foundations of differential privacy

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9(3-4):211--407, 2014

    2014

  16. [24]

    Erd\"os and R

    P. Erd\"os and R. Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London Mathematical Society , 3(2):417--439, 1952

    1952

  17. [25]

    Ramsey theorems for trees and a general 'private learning implies online learning' theorem

    Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari. Ramsey theorems for trees and a general 'private learning implies online learning' theorem. In FOCS , pages 1983--2009. IEEE , 2024

    1983

  18. [26]

    Sample complexity bounds on differentially private learning via communication complexity

    Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. SIAM Journal on Computing , 44(6):1740--1764, 2015

    2015

  19. [27]

    Sample-efficient proper PAC learning with approximate differential privacy

    Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy. In STOC , pages 183--196. ACM , 2021

    2021

  20. [28]

    Introduction to online convex optimization

    Elad Hazan. Introduction to online convex optimization. Found. Trends Optim. , 2(3-4):157--325, 2016

    2016

  21. [29]

    Online learning with simple predictors and a combinatorial characterization of minimax in 0/1 games

    Steve Hanneke, Roi Livni, and Shay Moran. Online learning with simple predictors and a combinatorial characterization of minimax in 0/1 games. In COLT , volume 134 of Proceedings of Machine Learning Research , pages 2289--2314. PMLR , 2021

    2021

  22. [30]

    List sample compression and uniform convergence

    Steve Hanneke, Shay Moran, and Tom Waknine. List sample compression and uniform convergence. In COLT , volume 247 of Proceedings of Machine Learning Research , pages 2360--2388. PMLR , 2024

    2024

  23. [31]

    A shorter model theory

    Wilfrid Hodges. A shorter model theory . Cambridge University Press, 1997

    1997

  24. [32]

    Reproducibility in learning

    Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In STOC , pages 818--831. ACM , 2022

    2022

  25. [33]

    On the equivalence between online and private learnability beyond binary classification

    Young Hun Jung, Baekjin Kim, and Ambuj Tewari. On the equivalence between online and private learnability beyond binary classification. In Proc.\ 33rd Conf.\ Adv.\ Neural Information Processing Systems (NeurIPS) , 2020

    2020

  26. [34]

    On communication complexity of classification problems

    Daniel Kane, Roi Livni, Shay Moran, and Amir Yehudayoff. On communication complexity of classification problems. In COLT , volume 99 of Proceedings of Machine Learning Research , pages 1903--1943. PMLR , 2019

    1903

  27. [35]

    Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D

    Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can we learn privately? SIAM J. Comput. , 40(3):793--826, 2011

    2011

  28. [36]

    Adam Tauman Kalai and Santosh S. Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci. , 71(3):291--307, 2005

    2005

  29. [37]

    A limitation of the pac-bayes framework

    Roi Livni and Shay Moran. A limitation of the pac-bayes framework. In NeurIPS , 2020

    2020

  30. [38]

    On agnostic learning with \ 0, *, 1\ -valued and real-valued hypotheses

    Philip Long. On agnostic learning with \ 0, *, 1\ -valued and real-valued hypotheses. In Proc.\ 14th Conf.\ Learning Theory (COLT) , 2001

    2001

  31. [39]

    The unstable formula theorem revisited

    Maryanthe Malliaris and Shay Moran. The unstable formula theorem revisited. CoRR , abs/2212.05050, 2022

    2022 arXiv

  32. [40]

    The bayesian stability zoo

    Shay Moran, Hilla Schefler, and Jonathan Shafer. The bayesian stability zoo. In NeurIPS , 2023

    2023

  33. [41]

    List online classification

    Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili. List online classification. In COLT , volume 195 of Proceedings of Machine Learning Research , pages 1885--1913. PMLR , 2023

    1913

  34. [42]

    Finite littlestone dimension implies finite information complexity

    Aditya Pradeep, Ido Nachum, and Michael Gastpar. Finite littlestone dimension implies finite information complexity. In ISIT , pages 3055--3060. IEEE , 2022

    2022

  35. [43]

    A characterization of list regression

    Chirag Pabbaraju and Sahasrajit Sarmasarkar. A characterization of list regression. CoRR , abs/2409.19218, 2024

    2024 arXiv

  36. [44]

    Multiclass versus binary differentially private PAC learning

    Satchit Sivakumar, Mark Bun, and Marco Gaboardi. Multiclass versus binary differentially private PAC learning. In Proc.\ 34th Conf.\ Adv.\ Neural Information Processing Systems (NeurIPS) , pages 22943--22954, 2021

    2021

  37. [45]

    S. Shelah. Classification theory and the number of nonisomorphic models. J. Symbolic Logic , 47(3):694--696, 1982

    1982

  38. [46]

    A primal-dual perspective of online learning algorithms

    Shai Shalev - Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Mach. Learn. , 69(2-3):115--142, 2007

    2007

  39. [47]

    A tutorial on conformal prediction

    Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research , 9(12):371--421, 2008

    2008

  40. [48]

    Salil P. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography , pages 347--450. Springer International Publishing, 2017

    2017

  41. [49]

    Leslie G. Valiant. A theory of the learnable. Commun. ACM , 27(11):1134--1142, 1984

    1984

  42. [50]

    V. Vovk, A. Gammerman, and G. Shafer. Algorithmic Learning in a Random World . Springer US, 2005

    2005

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.