Pith. sign in

REVIEW 2 major objections 4 minor 40 references

How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper claims that a new combinatorial measure, the domain shattering dimension, governs how many sampled domains are needed for domain generalization, up to a polylogarithmic factor.

desk verdict A real new measure with a clean upper bound and a solid VC connection, but the lower bound only holds for an augmented domain family, so the abstract's 'characterizes' overstates the proven scope. read the letter →

arxiv 2506.16704 v3 pith:ZJAEVJXF submitted 2025-06-20 cs.LG stat.ML

Cynthia Dwork , Lunjia Hu , Han Shao This is my paper · ORCID
classification cs.LGstat.ML MSC 68Q32
keywords domaingeneralizationshatteringdimensionsamplecomplexitymin-maxERMpartialconceptsVCuniformconvergencePAClearning
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 how many data distributions, or domains, a learner must sample in order to train a model that works on every seen and unseen domain in a given family. It introduces a new combinatorial measure, the domain shattering dimension, which captures the interaction between the hypothesis class and the family of domains. The paper shows that a min-max version of empirical risk minimization succeeds once the number of sampled domains passes this dimension times a polylogarithmic factor, and that no algorithm can succeed with asymptotically fewer domains in a mildly extended family. It also proves the dimension stays within a logarithmic factor of the classic VC dimension, so every standard PAC-learnable class is learnable for domain generalization, often from far fewer domains than data points.

What carries the argument

The central object is the domain shattering dimension (Definition 4.1). A set $S$ of domains is $\alpha$-shattered by $H$ at threshold $\tau$ if for every subset $E\subseteq S$ there is a hypothesis $h_E\in H$ with error below $\tau-\alpha$ on every domain in $E$ and error above $\tau$ on every domain outside $E$; the dimension is the largest such $S$. Unlike the fat-shattering dimension, it uses one fixed threshold $\tau$ for all domains, which keeps it small when every hypothesis is already acceptable on every domain. The proof maps each $h$ to a partial concept $f_h$ on the domain space and applies a uniform-convergence lemma for partial concept classes (Lemma 4.2), built on the generalized Sauer-Shelah-Perles lemma, to bound the error of min-max ERM on unseen domains.

What would settle it

A concrete check: take a family whose domains have mutually disjoint input marginals, as in the paper's own example in Section 4.2, compute its domain shattering dimension $d$, and observe that one hypothesis achieving the target error on every domain can be output without sampling any domain. If $d>0$ while zero domains suffice, the upper bound is not instance-wise tight; the remaining question is whether any family without a null distribution permits error $o(d/n)$, which would refute the characterization for unextended families.

Watch

Extended reading notes

Core claim

The paper's central claim is that the domain shattering dimension $Gdim(H,G,\tau,\alpha)$ characterizes the domain sample complexity up to a polylog factor: min-max ERM over $n$ observed domains achieves $Er_{P,\tau}(\hat h) = O((d\log^2 n + \log(1/\delta))/n)$ with $d = Gdim(H,G,\tau,\alpha)$ (Theorem 4.1), and any algorithm needs $\Omega((d+\log(1/\delta))/n)$ domains, up to polylog factors, when the family is augmented with a null distribution $D_0$ and mirror domains $D'_i$ as in equations (10)-(11) (Theorem 4.4). The paper further shows $Gdim(H,G,\tau,\alpha) = \Theta(d\log(1/\alpha))$ for a hypothesis class of VC dimension $d$ (Theorems 5.1 and 5.2), establishing that standard PAC learnability implies domain-generalization learnability and that the domain sample complexity can be much smaller than the ordinary sample complexity.

Load-bearing premise

The matching lower bound assumes a null distribution on which every hypothesis in the class has zero error, and it is proved only after adding that distribution and label-flipped mixtures to the domain family; without such a distribution, or without that augmentation, the lower bound does not cover the original family.

Editorial extensions

If this is right

  • Sampling about $Gdim/\gamma$ domains up to polylog factors and running min-max ERM guarantees that at most a $\gamma$ fraction of unseen domains suffer error above the threshold.
  • In the augmented setting, fewer than roughly $Gdim/\gamma$ domains make the task information-theoretically impossible, so the dimension serves as a certificate of necessity as well as sufficiency.
  • Every hypothesis class with finite VC dimension $d$ has domain shattering dimension $O(d\log(1/\alpha))$, so standard PAC learnability transfers to domain generalization.
  • When the domains are similar, the dimension stays small even for a complex hypothesis class, so a handful of domains can suffice even when each domain demands many examples.
  • The same min-max ERM algorithm and analysis apply to multi-class classification and regression, not only binary labels.

Reading between the lines

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

  • Editorial extension: the lower bound's reliance on a null distribution suggests that for families without a universally perfect labeled point, the true sample complexity may lie below $O(Gdim/n)$; a concrete family of that kind would test how much of the characterization is intrinsic to $G$ rather than to the augmentation.
  • Editorial extension: because standard pooled ERM fails while min-max ERM succeeds, the decisive algorithmic ingredient is worst-case aggregation of per-domain errors; benchmarking simple min-max ERM variants on public domain-generalization datasets could reveal whether this theoretical separation matters in practice.
  • Editorial extension: the tight relation $Gdim=\Theta(d\log(1/\alpha))$ yields a testable rule of thumb: for a fixed failure margin $\alpha$, the number of source domains should scale like the VC dimension times a logarithmic factor, which could be checked in synthetic experiments with known $d$ and $\alpha$.
  • Editorial extension: the open problem raised in Section 7, allowing unlabeled data from unseen domains to adapt the learned hypothesis, may escape the $\Omega(Gdim/n)$ lower bound entirely, since that bound assumes no information at all about unobserved domains.
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 / 4 minor

Summary. This paper introduces a PAC-style model of domain generalization in which a learner observes n domains drawn i.i.d. from a meta-distribution P over a fixed family G, together with finite data from each domain, and must output a hypothesis whose error exceeds τ on at most a γ fraction of future domains. The main object is the domain shattering dimension Gdim(H,G,τ,α), defined by requiring, for every subset E of a shattered set, a hypothesis with error < τ−α on E and > τ on its complement. The paper proves an upper bound via a min-max ERM algorithm and a new uniform-convergence lemma for partial concepts (Lemma 4.2, using Alon et al.'s quasipolynomial Sauer-Shelah lemma), proves a lower bound via a mixture construction with label-flipped domains (Theorem 4.4), and derives a tight VC-dimension comparison Gdim = Θ(d log(1/α)) (Theorems 5.1 and 5.2). The lower bound is stated for an augmented domain family G' = G ∪ {D0, D'_1, ..., D'_d} and assumes a null distribution D0 with zero error for all h in H.

Significance. The technical core is coherent and useful. The upper-bound proof is genuine: it reduces the problem to the VC dimension of a partial concept class and does not rely on fitted parameters. The lower-bound construction is also internally consistent for the augmented family. The VC-dimension comparison is a clean result and answers a natural question about how much larger Gdim can be than VCdim. These contributions would be of interest to a learning-theory audience. However, the advertised 'tight characterization' is currently conditional: the lower bound is for a different learning problem than the upper bound, and the authors' own Section 4.2 example shows that instance-wise characterization is false. The paper can be salvaged by a clear minimax or worst-case-extension formulation, but as written the headline claim overstates the theorems.

major comments (2)
  1. [Abstract and §1.1 vs Theorem 4.4, §4.2, §7] The abstract says the domain shattering dimension 'characterizes the domain sample complexity' and §1.1 says Theorem 4.1 and Theorem 4.4 'match up to a poly-logarithmic factor' for the same problem. This is not what Theorem 4.4 proves. The lower bound is established only for the augmented family G' = G ∪ {D0, D'_1, ..., D'_d} defined in Eqs. (10)–(11), under the existence of a null domain D0 (footnote 3), and it applies to algorithms that must succeed on every distribution over G', not necessarily on the original G. Moreover, §4.2 gives a disjoint-support example in which Gdim can be arbitrarily large while the domain sample complexity is zero, and §7 explicitly concedes that 'the lower bound does not apply to all domain families G.' The abstract and contribution section therefore state a theorem that the paper does not prove. Please either restrict the characterization to a formally defined worst-case or minimax sense, or make the abstract and §1.1 explicitly conditional on the augmentation and its null-domain assumption.
  2. [§4.2 and Theorem 4.4] Because Definition 3.2 fixes a pair (H,G) and allows the learner to use prior knowledge of G, augmenting G to G' changes the learning problem. Theorem 4.4's Ω((d + log(1/δ))/n) bound does not imply that Ω(Gdim(H,G,τ,α)/n) domains are needed for the original pair (H,G); a learner tailored to G may exploit its structure, as in the disjoint-support example immediately preceding the theorem. As a result, the manuscript's central claim is not an instance-wise characterization but at most a pessimistic statement over pairs whose Gdim is d, or over the augmented family. The authors should state the intended minimax statement explicitly, verify that the lower bound's sample space—including the role of D0 and the flipped domains—is the right one for that statement, and adjust the abstract and Section 1.1 accordingly.
minor comments (4)
  1. [§4.2, paragraph after Eq. (10)] The word 'Concretly' should be 'Concretely'.
  2. [§7, last paragraph] The word 'unlabled' should be 'unlabeled'.
  3. [§5.2, after Eq. (25)] The pair of indices 'h_j1,hj2' is missing an underscore; it should read 'h_{j_1}, h_{j_2}'.
  4. [Theorem 4.4 and §1.1] The lower bound is proven for the slightly more stringent threshold τ' ∈ (τ−α, τ), not for τ itself; the claim of matching bounds up to a polylog factor should mention this threshold shift as well as the polylog gap.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: the domain sample complexity bounds follow from external combinatorial results and explicit constructions, not from fitted inputs or load-bearing self-citation.

full rationale

The paper's central derivation is self-contained against external results. Definition 4.1 defines the domain shattering dimension Gdim(H,G,τ,α); the upper bound in Theorem 4.1 translates shattering into the VC dimension of an induced partial concept class F={f_h} and then invokes Lemma 4.2, which is proved using the external quasipolynomial Sauer-Shelah-Perles lemma for disambiguations of partial concepts due to Alon et al. (2022). This is a genuine reduction, not an equivalence-by-definition: the dimension is defined combinatorially and the uniform convergence lemma is proved independently. Theorem 4.4 is also a genuine lower bound: it constructs a family G' = G ∪ {D0, D'_1, ..., D'_d} via equation (10), sets λ = (τ−α)/(1−τ), builds random distributions P_b over G', and shows any algorithm succeeding with error γ must have γ = Ω((d+log(1/δ))/n). The construction is explicit and the argument does not assume the conclusion; the lower bound is for the augmented family G', and the paper itself flags this scope restriction in Section 7: 'the lower bound does not apply to all domain families G.' That mismatch between the abstract's unqualified 'characterization' and Theorem 4.4's augmented-family guarantee is a correctness or overclaim concern, not a circular derivation. Theorems 5.1 and 5.2 derive the VC-dimension relationship from the Sauer-Shelah-Perles lemma and an explicit construction, again without fitting parameters to the target conclusion. Self-citations (Deng et al. 2020, Hu and Peale 2023, Hu et al. 2022, Shao et al. 2022, Montasser et al. 2024, Duchi et al. 2022) appear in motivation, related work, and the discussion section, but none is load-bearing for the sample complexity theorems. The paper's upper and lower bounds are not constructed from their own conclusions, so no circular step is exhibited.

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

The paper's central claims rest on standard external results (Sauer-Shelah-Perles, and Alon et al.'s quasipolynomial disambiguation lemma for partial concepts), on the modeling assumption that a universally good hypothesis exists, and on the lower-bound-specific assumption of a null domain D0. No parameters are fitted to data. The only new entity is the domain shattering dimension itself, which is fully specified and whose usefulness is proven rather than postulated.

assumptions (4)
  • domain assumption There exists h* in H with err_D(h*) ≤ τ−α−2ε for every domain D in the support of P (Definition 3.1; assumption in Theorem 4.1).
    No domain generalization is possible without some hypothesis that is good on all domains; this is the realizability-type assumption of the model, stated in the problem setup.
  • domain assumption There exists a distribution D0 over X×{0,1} with err_{D0}(h)=0 for every h in H (Section 4.2, footnote 3).
    Required for the lower-bound construction; the paper notes it holds whenever some point x0 receives a common label from all h in H.
  • standard math Quasipolynomial Sauer-Shelah-Perles lemma for disambiguations of partial concepts: for any VC-dim-d partial concept class F and any n-point set S, there exists a total-concept disambiguation class of size n^{O(d log n)} (Theorem 4.3, cited from Alon et al. 2022).
    Used centrally in Lemma 4.2 to enumerate a small covering of partial concepts by total concepts; without it the uniform-convergence upper bound fails.
  • standard math Sauer-Shelah-Perles lemma: for a total concept class of VC dimension d, the number of dichotomies on any n-point set is at most (2 + en/d)^d (Theorem 5.4, Sauer 1972; Shelah 1972).
    Used in Theorem 5.2 to bound the domain shattering dimension by d log(1/α).
invented entities (1)
  • Domain shattering dimension Gdim(H,G,τ,α) independent evidence
    purpose: Combinatorial measure defined in Definition 4.1 to characterize the number of sampled domains needed for domain generalization; it captures the interaction between hypothesis class H and domain family G at a fixed error threshold.
    The measure is rigorously defined and its characterizing power is proven in Theorem 4.1 (upper bound) and Theorem 4.4 (lower bound); its relationship to VC dimension (Theorems 5.1, 5.2) provides an external anchor to a known quantity, so it is not a speculative postulate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension." pith.science (2026). https://pith.science/paper/ZJAEVJXF

@misc{pith2026250616704,
  author       = {Pith},
  title        = {Pith review of: How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZJAEVJXF}},
  note         = {Machine review of arXiv:2506.16704}
}
read the original abstract

We study a fundamental question of domain generalization: given a family of domains (i.e., data distributions), how many randomly sampled domains do we need to collect data from in order to learn a model that performs reasonably well on every seen and unseen domain in the family? We model this problem in the PAC framework and introduce a new combinatorial measure, which we call the domain shattering dimension. We show that this dimension characterizes the domain sample complexity. Furthermore, we establish a tight quantitative relationship between the domain shattering dimension and the classic VC dimension, demonstrating that every hypothesis class that is learnable in the standard PAC setting is also learnable in our setting.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 25 canonical work pages

  1. [1]

    Metalearning with very few samples per task

    Maryam Aliakbarpour, Konstantina Bairaktari, Gavin Brown, Adam Smith, Nathan Srebro, and Jonathan Ullman. Metalearning with very few samples per task. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 46--93. PMLR, 30 Jun--03 Jul 2024. URL h...

    work page 2024

  2. [2]

    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 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658--671. IEEE, 2022

    work page 2021

  3. [3]

    On the ERM Principle in Meta-Learning

    Yannay Alon, Steve Hanneke, Shay Moran, and Uri Shalit. On the ERM principle in meta-learning. arXiv preprint arXiv:2411.17898, 2024

    work page Pith review arXiv 2024

  4. [4]

    Invariant risk minimization

    Martin Arjovsky, L \'e on Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02893, 2019

    arXiv 1907

  5. [5]

    Open problem: The sample complexity of multi-distribution learning for VC classes

    Pranjal Awasthi, Nika Haghtalab, and Eric Zhao. Open problem: The sample complexity of multi-distribution learning for VC classes. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5943--5949. PMLR, 12--15 Jul 2023. URL https://proceedings.m...

    work page 2023

  6. [6]

    A theory of learning from different domains

    Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79: 0 151--175, 2010

    2010

  7. [7]

    Generalizing from several related classification tasks to a new unlabeled sample

    Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. Advances in neural information processing systems, 24, 2011

    work page 2011

  8. [8]

    Collaborative PAC learning

    Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao. Collaborative PAC learning. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips.cc/paper_files/paper/2017/file/186a...

    work page 2017

Show all 40 references
  1. [9]

    Tight bounds for collaborative PAC learning via multiplicative weights

    Jiecao Chen, Qin Zhang, and Yuan Zhou. Tight bounds for collaborative PAC learning via multiplicative weights. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran As...

    2018

  2. [10]

    Exploiting shared representations for personalized federated learning

    Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai. Exploiting shared representations for personalized federated learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings o...

    2021

  3. [11]

    Representation via representations: Domain generalization via adversarially learned invariant representations

    Zhun Deng, Frances Ding, Cynthia Dwork, Rachel Hong, Giovanni Parmigiani, Prasad Patil, and Pragya Sur. Representation via representations: Domain generalization via adversarially learned invariant representations. arXiv preprint arXiv:2006.11478, 2020

    2006 arXiv

  4. [12]

    Kakade, Jason D

    Simon Shaolei Du, Wei Hu, Sham M. Kakade, Jason D. Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=pW2Q2xLwIMD

    2021

  5. [13]

    Subspace recovery from heterogeneous data with non-isotropic noise

    John C Duchi, Vitaly Feldman, Lunjia Hu, and Kunal Talwar. Subspace recovery from heterogeneous data with non-isotropic noise. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 585...

    2022

  6. [14]

    Learn to expect the unexpected: Probably approximately correct domain generalization

    Vikas Garg, Adam Tauman Kalai, Katrina Ligett, and Steven Wu. Learn to expect the unexpected: Probably approximately correct domain generalization. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and ...

    2021

  7. [15]

    On-demand sampling: Learning optimally from multiple distributions

    Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 406--419. Curra...

    2022

  8. [16]

    Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes

    Lunjia Hu and Charlotte Peale. Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes . In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (L...

    2023 doi

  9. [17]

    Metric entropy duality and the sample complexity of outcome indistinguishability

    Lunjia Hu, Charlotte Peale, and Omer Reingold. Metric entropy duality and the sample complexity of outcome indistinguishability. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings of The 33rd International Conference on Algorithmic Learning Theory, volume 167 of Proce...

    2022

  10. [18]

    Efficient distribution-free learning of probabilistic concepts

    Michael J Kearns and Robert E Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48 0 (3): 0 464--497, 1994

    1994

  11. [19]

    Universal adaptability: Target-independent inference that competes with propensity scoring

    Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. Universal adaptability: Target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119 0 (4): 0 e2108097119, 2022

    2022

  12. [20]

    Meta-learning for mixed linear regression

    Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Researc...

    2020

  13. [21]

    Derandomizing multi-distribution learning

    Kasper Green Larsen, Omar Montasser, and Nikita Zhivotovskiy. Derandomizing multi-distribution learning. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 94246--94...

    2024

  14. [22]

    Learning adversarially fair and transferable representations

    David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel. Learning adversarially fair and transferable representations. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine...

    2018

  15. [23]

    The benefit of multitask representation learning

    Andreas Maurer, Massimiliano Pontil, and Bernardino Romera-Paredes. The benefit of multitask representation learning. Journal of Machine Learning Research, 17 0 (81): 0 1--32, 2016. URL http://jmlr.org/papers/v17/15-242.html

    2016

  16. [24]

    Agnostic federated learning

    Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 4615-...

    2019

  17. [25]

    Transformation-invariant learning and theoretical guarantees for OOD generalization

    Omar Montasser, Han Shao, and Emmanuel Abbe. Transformation-invariant learning and theoretical guarantees for OOD generalization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=u2gzfXRLaN

    2024

  18. [26]

    Domain generalization via invariant feature representation

    Krikamol Muandet, David Balduzzi, and Bernhard Sch \"o lkopf. Domain generalization via invariant feature representation. In International conference on machine learning, pages 10--18. PMLR, 2013

    2013

  19. [27]

    Improved algorithms for collaborative PAC learning

    Huy Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative PAC learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL...

    2018

  20. [28]

    The sample complexity of multi-distribution learning

    Binghui Peng. The sample complexity of multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 4185--4204. PMLR, 30 Jun--03 Jul 2024. URL ...

    2024

  21. [29]

    On the density of families of sets

    N Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13 0 (1): 0 145--147, 1972. ISSN 0097-3165. doi:https://doi.org/10.1016/0097-3165(72)90019-2. URL https://www.sciencedirect.com/science/article/pii/0097316572900192

    1972

  22. [30]

    A theory of PAC learnability under transformation invariances

    Han Shao, Omar Montasser, and Avrim Blum. A theory of PAC learnability under transformation invariances. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 13989--14001. Curran Asso...

    2022

  23. [31]

    A combinatorial problem; stability and order for models and theories in infinitary languages

    Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41 0 (1): 0 247--261, 1972

    1972

  24. [32]

    Sample efficient linear meta-learning by alternating minimization

    Kiran Koshy Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Sample efficient linear meta-learning by alternating minimization. arXiv preprint arXiv:2105.08306, 2021

    2021 arXiv

  25. [33]

    On the theory of transfer learning: The importance of task diversity

    Nilesh Tripuraneni, Michael Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7852--7862. Cu...

    2020

  26. [34]

    Provable meta-learning of linear representations

    Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representations. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10434...

    2021

  27. [35]

    L. G. Valiant. A theory of the learnable. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC '84, page 436–445, New York, NY, USA, 1984. Association for Computing Machinery. ISBN 0897911334. doi:10.1145/800057.808710. URL https://doi.org/10.1145/...

    1984

  28. [36]

    V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16 0 (2): 0 264--280, 1971. doi:10.1137/1116025. URL https://doi.org/10.1137/1116025

    1971 doi

  29. [37]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  30. [38]

    Generalizing to unseen domains: A survey on domain generalization

    Jindong Wang, Cuiling Lan, Chang Liu, Yidong Ouyang, Tao Qin, Wang Lu, Yiqiang Chen, Wenjun Zeng, and Philip S Yu. Generalizing to unseen domains: A survey on domain generalization. IEEE transactions on knowledge and data engineering, 35 0 (8): 0 8052--8072, 2022

    2022

  31. [39]

    Optimal multi-distribution learning

    Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S Du, and Jason D Lee. Optimal multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 5220--5...

    2024

  32. [40]

    Domain generalization: A survey

    Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization: A survey. IEEE transactions on pattern analysis and machine intelligence, 45 0 (4): 0 4396--4415, 2022

    2022

Pith tools

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