Pith. sign in

REVIEW 3 major objections 5 minor 36 references

On the Learnability of Distribution Classes with Adaptive Adversaries

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Realizable distribution learning does not survive adaptive adversaries that add or delete an η-fraction of samples; adaptive additivity is strictly stronger than oblivious additivity.

desk verdict The paper plausibly resolves an open question about adaptive vs. oblivious additive adversaries, but the main theorem currently rests on a flawed TV decomposition in Lemma 5.5 that is likely repairable by a coupling argument. read the letter →

arxiv 2509.05137 v1 pith:QJSG5CJW submitted 2025-09-05 cs.LG

Tosca Lechner , Alex Bie , Gautam Kamath This is my paper · ORCID
classification cs.LG MSC 68Q32
keywords distributionlearningadaptiveadversariesadditivecorruptionrobustnessrealizablelearnabilityobliviousvstotalvariationdistanceuniversaladversary
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

Distribution learning normally assumes the learner receives i.i.d. samples from an unknown distribution in a known class. An oblivious adversary can change the underlying distribution but not the i.i.d. nature of the samples; an adaptive adversary sees each sample and can edit it before the learner does. The paper asks whether every class that is learnable without corruption stays learnable when an adaptive adversary may add or delete a small fraction of points. It answers no: there is a class C_g that is easy to learn, with sample complexity log(1/δ)g(1/ε), and yet for every α≥1 no learner can achieve error at most αη+ε against an adaptive adversary allowed to add an η-fraction of points. Since the same class is learnable against oblivious additive corruption, this gives a strict separation between oblivious and adaptive additive adversaries.

What carries the argument

The load-bearing objects are the class C_g, the subtractive adversary V_sub,η, and a reduction from indistinguishability to hardness. C_g is the family p_{i,j,g(j)} = (1−1/j)δ_{(0,0)} + (1/j − 1/g(j)) U_{B_i×{2j+1}} + (1/g(j)) δ_{(i,2j+2)}; the coordinate i identifies the distribution through a single indicator point. V_sub,η is the adaptive adversary that deletes as many indicator points (i,2j+2) as its budget allows, removing other points at random only when no indicators remain. The paper shows V_sub,η makes V_sub,η(p^m) and V_sub,η(|Q|^m) close in total variation, using birthday-paradox and Markov bounds, while p and every q in the support of Q are far apart. The engine converting this i

What would settle it

Fix g(n)=n log n and choose p, Q, and η exactly as in Lemma 5.5, then compute or tightly bound d_TV(V_sub,η(p^m), V_sub,η(|Q|^m)) for increasing m, say 10^2, 10^4, and 10^6. The proof requires this distance to be at most 1/8 for all m; if it is bounded well above that, the indistinguishability step fails and Theorem 4.1 loses its footing. A second falsifier: exhibit a learner that, for C_g with g(n)=n log n and some finite α, achieves d_TV(A(V_add(S)), p) ≤ αη+ε with probability at least 1−δ for every p∈C_g and every m.

Watch

Extended reading notes

Core claim

Theorem 4.1 constructs, for every superlinear function g, a class C_g of distributions over pairs of natural numbers for which a realizable learner exists with sample complexity m_re(ε,δ) ≤ log(1/δ) g(1/ε), yet no learner is α-robust against adaptive additive adversaries for any α ≥ 1. In fact there is a single additive adversary—a universal α-adversary—that defeats every learner, and the same holds for subtractive adversaries. The class C_g consists of mixtures supported on a heavy atom at (0,0), a uniform layer over a finite set B_i, and a single indicator point (i, 2j+2); the realizable learner only needs to see the indicator once. The adversary deletes indicators before the learner sees

Load-bearing premise

The entire lower-bound chain rests on Lemma 5.4, imported from the companion paper and not proved here: if an adversary can make samples from two far-apart distributions nearly indistinguishable, then every learner must fail on one of the two. The separation collapses if that lemma is false in the generality in which the paper applies it.

Editorial extensions

If this is right

  • Realizable learnability does not imply adaptive additive robustness: C_g is learnable with sample complexity log(1/δ)g(1/ε), yet no learner is α-robust for any α ≥ 1.
  • Adaptive additive robustness is strictly stronger than oblivious additive robustness: the same class is obliviously additive 3-robustly learnable but fails every adaptive additive guarantee.
  • The lower bound holds at every sample size, so no finite amount of data lets a learner win against the universal adversary for C_g.
  • Any general reduction from adaptive to oblivious adversaries must use a dataset whose size depends on the support size; the paper's unbounded-support example shows such a dependence is unavoidable for distribution learning.
  • The appendix extends the impossibility from linear allowances αη to arbitrary continuous monotone functions f with f(0)=0: for each such f there is a class that is realizable but not adaptively f-robustly learnable.

Reading between the lines

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

  • Because only the unique indicator point identifies members of C_g, I expect the same separation to transfer to any domain where distributions carry rare identifying tags, such as strings with a unique marker or structured families with distinguished atoms.
  • The additive adversaries are defined through conditional distributions given V_sub(S) and are not shown to be computable; making the attack efficient, or proving it cannot be made efficient, would determine whether the separation has practical implications beyond information theory.
  • The paper's indistinguishability bound of 1/8 is loose; following the birthday-paradox calculation with explicit constants could yield a finite-sample curve showing exactly how many added or deleted points break a given learner, turning the all-or-nothing lower bound into a quantitative one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies distribution learning in the presence of adaptive adversaries that can add or remove sample points after seeing the sample. It formalizes additive and subtractive adaptive adversaries with budgets, and defines adaptive α-robust learnability. The main result (Theorem 4.1) states that for every superlinear g there is a realizable distribution class C_g that is learnable with sample complexity O(log(1/δ) g(1/ε)), yet for every α ≥ 1 it is not adaptively additively or subtractively α-robustly learnable, and there are universal additive and subtractive α-adversaries. The proof introduces a general lower-bound framework (Theorem 5.2) based on indistinguishability of sample distributions, constructs a subtractive adversary V_sub,η for C_g (Lemma 5.5), converts subtractive hardness to additive hardness (Theorems 6.1 and 7.1), and concludes with Theorem 4.1 and Corollary 7.3, separating adaptive and oblivious additive robustness.

Significance. If the main result is correct, it resolves an open question from Ben-David et al. (2023) in the negative and establishes an infinite sample-complexity gap between adaptive and oblivious additive adversaries. The paper's strengths are its explicit constructions, the self-contained proof of Lemma 5.3, and a clean high-level scheme: indistinguishability lower bounds, subtractive-to-additive conversion, and universal adversaries. The lower-bound framework is parameter-free and, modulo the issue below, would be reusable. However, the proof of the key confusion condition for C_g contains a serious technical gap, and the formal status of the constructed additive adversaries needs clarification. The result is plausible and likely repairable, but the paper as written does not establish the central separation.

major comments (3)
  1. [Appendix A.3 (Lemma 5.5)] The proof asserts the equality dTV(V_sub,η(p^m), V_sub,η(|Q|^m)) = dTV(constants marginals) + dTV(odds marginals) + dTV(ind marginals). This is not valid: total variation of a joint distribution is not the sum of total variations of its marginals, since two distributions can have identical marginals yet be perfectly anti-correlated. The subsequent bound dTV ≤ 1/8, and hence the (γ,ζ)-confusion condition for C_g, rest on this step. Via Theorem 5.2, Corollary 6.2, and Corollary 7.2, this gap undermines Theorem 4.1 as written. The claimed bound may be recoverable: couple constants, couple odds except when repeats occur, and couple indicator counts except when the indicator budget is exceeded; under the complement of these four events, the two output distributions coincide, giving dTV ≤ sum of the four failure probabilities. The proof should be rewritten around such a coupling instead of the
  2. [Section 3.2 and Theorems 6.1 / 7.1] The formal model defines an adaptive adversary as a (randomized) function V: X* → X*. The additive adversaries in Theorems 6.1 and 7.1 are defined as V_add,r(S) = V^{-1}_{sub,r}(V_sub(S)) ∪ (S \ V_sub(S)), where r is p^m or |Q|^m. Thus the strategy depends on the distributions p and Q, not merely on the input sample. Footnote 5 states that knowledge of the underlying generating distribution p is omitted and that the main result is stronger. As written, the universal-additive-adversary claim in Theorem 4.1 is not aligned with the formal model. Please clarify: either (a) extend the definition to allow adversaries that depend on p and Q, or (b) argue that for C_g one can hardcode the m-dependent pair (p_m,Q_m) from Lemma 5.5, producing a single sample-to-sample function independent of the actual ground-truth distribution. Corollary 7.2 currently does neither.
  3. [Appendix A.2 (Theorem 5.2)] The proof of Theorem 5.2 is hard to follow because it introduces δ' and ε' without definition, and it states δ = min{1−ζ/2, δ'} while later writing 1/2 − ζ/2 = δ. The intended argument is clear — choose δ = (1−ζ)/2 and invoke Lemma 5.3 — but as written the proof is not correct. This is fixable locally, but it is a load-bearing lower-bound step and should be cleaned.
minor comments (5)
  1. [Throughout] There are several typos, e.g., 'oblivous' in the introduction; 'distributons' in Section 3.1; and the budget function type in Section 3.2 is malformed ('budget : X* X* × N → [0,1]' should presumably be a map from adversaries and sample sizes).
  2. [Appendix A.4 (Theorem 6.1)] The integral manipulations contain repeated s' variables and the first displayed equality in the TV computation writes the same integrand on both sides; the second term should involve V_add,|Q|^m(p^m). These typos make an already intricate proof difficult to verify.
  3. [Appendix A.3 (Lemma 5.5)] The derivation of the choice n ≥ m/(1−(1−1/32)^{1/m}) is compressed; please spell out the birthday bound calculation. Also the expression '2/g(j)·32/g(j)' is ambiguous; it should be 2/(g(j)η) = 1/16.
  4. [Theorem 4.1] The statement says 'for every superlinear function g:R→R', but the class C_g is defined for g:N→N and the sample complexity uses g(1/ε). Please state the intended extension (e.g., monotone envelope) or adjust notation.
  5. [Lemma 5.4] Lemma 5.4 is cited from Ben-David and Lechner (2025), an unpublished preprint co-authored by the first author. Since Lemma 5.3 is proved in the appendix, the application is self-contained, but the dependence on an unpublished source should be explicitly acknowledged.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central lower-bound derivation is self-contained (Lemma 5.3 is proved in Appendix A.1), and the cited prior results are independent inputs rather than re-statements of the target theorem.

full rationale

The paper's main separation (Theorem 4.1) does not reduce by construction to its own inputs. The learnability upper bound for Cg is imported from Ben-David et al. (2023), a published prior paper with overlapping authors; this is independent external support, not a self-referential derivation of the current theorem. The lower-bound machinery rests on Theorem 5.2, which is proved from Lemma 5.3. Lemma 5.3 is not merely cited: its full proof is given in Appendix A.1 and is self-contained, using only the definition of (γ,ζ)-confusion, total variation transfer, and a triangle-inequality argument. Lemma 5.4 from Ben-David & Lechner (2025) is cited as background, but the paper does not rely on it in the proof chain; even if it were relied upon, it is a parameter-free general hardness lemma whose assumptions do not include the target separation, so it would not make the argument circular under the rules. The construction of additive adversaries from subtractive ones (Theorem 6.1 and Theorem 7.1) is an explicit transformation, not a renaming or fitted input. No parameter is fitted to a subset of data and then called a prediction, and no uniqueness theorem is imported from the authors' prior work to forbid alternatives. The main caveat in the manuscript is a correctness gap, not circularity: the proof of Lemma 5.5 in Appendix A.3 decomposes the total variation of a joint distribution as the sum of total variations of three marginal distributions (constants, odds, indicators), which is invalid in general; joint TV can be large even when marginals agree. This threatens the claimed 1/8 confusion bound and hence the lower bound as written, but it is a proof gap, not an equivalence of the theorem to its inputs. The derivation chain is therefore not circular, though it is not fully sound as written.

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

The central claim rests on one unproved cited lemma (Lemma 5.4), two published results about Cg and oblivious robustness, and two proof constants (η, γ') chosen to satisfy required inequalities. No new entities (particles, forces, dimensions) are introduced. The main uncertainty in the ledger is Lemma 5.4 and the sample-only-versus-p-aware adversary modeling.

free parameters (3)
  • η (subtractive adversary budget) = 32/g(j) for a chosen index j
    Chosen in Lemma 5.5 to make confusion probabilities small. The choice depends on α through the requirement g(j) ≥ 1024αj. It is an adversary-chosen constant, not fit to data.
  • γ' (confusion slack) = α/g(j)
    Introduced ad hoc in Lemma 5.5 to satisfy the TV lower bound dTV(p,q) ≥ 4αη + 4γ'. It is a proof constant, not an empirical parameter.
  • j (class index) = any j with g(j) ≥ 1024αj
    The construction of p and Q in Lemma 5.5 depends on picking j large enough so that the indicator mass 1/g(j) is small relative to 1/j; superlinearity of g guarantees such j exists.
assumptions (4)
  • domain assumption Lemma 5.4 (Ben-David and Lechner 2025): if classes C1 and C2 have dTV(p,q) > γ for all p,q and a meta-distribution Q over C1 and p in C2 satisfy dTV(|Q|^m, p^m) < ζ, then every learner fails on one of the classes with probability at least 1/2 − ζ/2.
    This is the central reduction from sample indistinguishability to learning hardness. It is quoted from a self-authored unpublished preprint and is not proved in the present paper. All of Theorem 5.2 and the main lower bound rely on it.
  • standard math Lemma 4.2 (Ben-David et al. 2023): for every monotone g, the class Cg is realizably learnable with sample complexity log(1/δ) g(1/ε).
    Used to establish the realizable learnability side of Theorem 4.1. This is a published result from a prior NeurIPS paper.
  • standard math Theorem 1.5 of Ben-David et al. (2023): every realizably learnable class is obliviously additive 3-robustly learnable.
    Used in Corollary 7.3 to establish the separation between oblivious and adaptive additive robustness.
  • domain assumption The additive adversaries constructed in Sections 6 and 7 may depend on the ground-truth distributions p and Q (via the reverse maps V^{-1}_{sub,pm} and V^{-1}_{sub,|Q|m}).
    Definition 3.2 defines an adversary as a sample-to-sample function, but Theorems 6.1 and 7.1 build adversaries that use p and Q. The paper acknowledges this only in a footnote, making the formal model and the theorem statements slightly mismatched.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Learnability of Distribution Classes with Adaptive Adversaries." pith.science (2026). https://pith.science/paper/QJSG5CJW

@misc{pith2026250905137,
  author       = {Pith},
  title        = {Pith review of: On the Learnability of Distribution Classes with Adaptive Adversaries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QJSG5CJW}},
  note         = {Machine review of arXiv:2509.05137}
}
read the original abstract

We consider the question of learnability of distribution classes in the presence of adaptive adversaries -- that is, adversaries capable of intercepting the samples requested by a learner and applying manipulations with full knowledge of the samples before passing it on to the learner. This stands in contrast to oblivious adversaries, who can only modify the underlying distribution the samples come from but not their i.i.d.\ nature. We formulate a general notion of learnability with respect to adaptive adversaries, taking into account the budget of the adversary. We show that learnability with respect to additive adaptive adversaries is a strictly stronger condition than learnability with respect to additive oblivious adversaries.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 34 canonical work pages

  1. [1]

    J., Liaw, C., Mehrabian, A., and Plan, Y

    Ashtiani, H., Ben-David, S., Harvey, N. J., Liaw, C., Mehrabian, A., and Plan, Y. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM, 67 0 (6): 0 32:1--32:42, 2020

    work page 2020

  2. [2]

    M., Kothari, P

    Bakshi, A., Diakonikolas, I., Jia, H., Kane, D. M., Kothari, P. K., and Vempala, S. S. Robustly learning mixtures of k arbitrary G aussians. In Proceedings of the 54th Annual ACM Symposium on the Theory of Computing, STOC '22, pp.\ 1234--1247, New York, NY, USA, 2022. ACM

    work page 2022

  3. [3]

    and Lechner, T

    Ben-David, S. and Lechner, T. Lower bounds for distribution learning, 2025

    work page 2025

  4. [4]

    Distribution learnability and robustness

    Ben-David, S., Bie, A., Kamath, G., and Lechner, T. Distribution learnability and robustness. In Advances in Neural Information Processing Systems, volume 36, pp.\ 52732--52758, 2023

    work page 2023

  5. [5]

    Adaptive and oblivious statistical adversaries are equivalent

    Blanc, G. and Valiant, G. Adaptive and oblivious statistical adversaries are equivalent. arXiv preprint arXiv:2410.13548, 2024

    work page Pith review arXiv 2024

  6. [6]

    On the power of adaptivity in statistical adversaries

    Blanc, G., Lange, J., Malik, A., and Tan, L.-Y. On the power of adaptivity in statistical adversaries. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pp.\ 5030--5061, 2022

    work page 2022

  7. [7]

    B., Li, J., Liu, A., and Narayanan, S

    Canonne, C., Hopkins, S. B., Li, J., Liu, A., and Narayanan, S. The full landscape of robust mean testing: Sharp separations between oblivious and adaptive contamination. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science, FOCS '21, pp.\ 2159--2168. IEEE Computer Society, 2023

    work page 2023

  8. [8]

    and Wagner, D

    Carlini, N. and Wagner, D. A. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017 , pp.\ 39--57. IEEE Computer Society, 2017

    work page 2017

Show all 36 references
  1. [9]

    A., Paleka, D., Pearce, W., Anderson, H

    Carlini, N., Jagielski, M., Choquette - Choo, C. A., Paleka, D., Pearce, W., Anderson, H. S., Terzis, A., Thomas, K., and Tram \` e r, F. Poisoning web-scale training datasets is practical. In IEEE Symposium on Security and Privacy, SP 2024, San Francisco, CA, USA, May 19-23, ...

    2024

  2. [10]

    O., Diakonikolas, I., Servedio, R

    Chan, S. O., Diakonikolas, I., Servedio, R. A., and Sun, X. Learning mixtures of structured distributions over discrete domains. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, pp.\ 1380--1394, Philadelphia, PA, USA, 2013. SIAM

    2013

  3. [11]

    O., Diakonikolas, I., Servedio, R

    Chan, S. O., Diakonikolas, I., Servedio, R. A., and Sun, X. Efficient density estimation via piecewise polynomial approximation. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, STOC '14, pp.\ 604--613, New York, NY, USA, 2014 a . ACM

    2014

  4. [12]

    O., Diakonikolas, I., Servedio, R

    Chan, S. O., Diakonikolas, I., Servedio, R. A., and Sun, X. Near-optimal density estimation in near-linear time using variable-width histograms. In Advances in Neural Information Processing Systems 27, NIPS '14, pp.\ 1844--1852. Curran Associates, Inc., 2014 b

    2014

  5. [13]

    Targeted backdoor attacks on deep learning systems using data poisoning, 2017

    Chen, X., Liu, C., Li, B., Lu, K., and Song, D. Targeted backdoor attacks on deep learning systems using data poisoning, 2017. URL https://arxiv.org/abs/1712.05526

    2017 arXiv

  6. [14]

    and Lugosi, G

    Devroye, L. and Lugosi, G. Combinatorial methods in density estimation. Springer, 2001

    2001

  7. [15]

    Learning structured distributions

    Diakonikolas, I. Learning structured distributions. In B \"u hlmann, P., Drineas, P., Kane, M. J., and van der Laan, M. J. (eds.), Handbook of Big Data, pp.\ 267--283. Chapman and Hall/CRC, 2016

    2016

  8. [16]

    and Kane, D

    Diakonikolas, I. and Kane, D. Algorithmic High-Dimensional Robust Statistics. Cambridge University Press, 2022

    2022

  9. [17]

    M., Li, J., Moitra, A., and Stewart, A

    Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Robust estimators in high dimensions without the computational intractability. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS '16, pp.\ 655--664, Washingto...

    2016

  10. [18]

    M., Li, J., Moitra, A., and Stewart, A

    Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Being robust (in high dimensions) can be practical. In Proceedings of the 34th International Conference on Machine Learning, ICML '17, pp.\ 999--1008. JMLR, Inc., 2017

    2017

  11. [19]

    M., Li, J., Moitra, A., and Stewart, A

    Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Moitra, A., and Stewart, A. Robustly learning a G aussian: Getting optimal error, efficiently. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, Philadelphia, PA, USA, 2018. SIAM

    2018

  12. [20]

    M., Li, J., Steinhardt, J., and Stewart, A

    Diakonikolas, I., Kamath, G., Kane, D. M., Li, J., Steinhardt, J., and Stewart, A. Sever: A robust meta-algorithm for stochastic optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML '19, pp.\ 1596--1606. JMLR, Inc., 2019

    2019

  13. [21]

    Decision theoretic generalizations of the PAC model for neural net and other learning applications

    Haussler, D. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100 0 (1): 0 78--150, 1992

    1992

  14. [22]

    Hopkins, S. B. and Li, J. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, STOC '18, pp.\ 1021--1034, New York, NY, USA, 2018. ACM

    2018

  15. [23]

    Huber, P. J. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35 0 (1): 0 73--101, 1964

    1964

  16. [24]

    K., and Vempala, S

    Jia, H., Kothari, P. K., and Vempala, S. S. Beyond moments: Robustly learning affine transformations with asymptotically optimal error. arXiv preprint arXiv:2302.12289, 2023

    2023 arXiv

  17. [25]

    E., and Sellie, L

    Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R. E., and Sellie, L. On the learnability of discrete distributions. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, STOC '94, pp.\ 273--282, New York, NY, USA, 1994. ACM

    1994

  18. [26]

    Robust moment estimation and improved clustering via sum of squares

    Kothari, P., Steinhardt, J., and Steurer, D. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, STOC '18, pp.\ 1035--1046, New York, NY, USA, 2018. ACM

    2018

  19. [27]

    A., Rao, A

    Lai, K. A., Rao, A. B., and Vempala, S. Agnostic estimation of mean and covariance. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS '16, pp.\ 665--674, Washington, DC, USA, 2016. IEEE Computer Society

    2016

  20. [28]

    and Schmidt, L

    Li, J. and Schmidt, L. Robust proper learning for mixtures of G aussians via systems of polynomial inequalities. In Proceedings of the 30th Annual Conference on Learning Theory, COLT '17, pp.\ 1302--1382, 2017

    2017

  21. [29]

    and Moitra, A

    Liu, A. and Moitra, A. Settling the robust learnability of mixtures of gaussians. In Proceedings of the 53nd Annual ACM Symposium on the Theory of Computing, STOC '21, pp.\ 518--531, New York, NY, USA, 2021. ACM

    2021

  22. [30]

    and Moitra, A

    Liu, A. and Moitra, A. Learning GMM s with nearly optimal robustness guarantees. In Proceedings of the 35th Annual Conference on Learning Theory, COLT '22, pp.\ 2815--2895, 2022

    2022

  23. [31]

    Resilience: A criterion for learning in the presence of arbitrary outliers

    Steinhardt, J., Charikar, M., and Valiant, G. Resilience: A criterion for learning in the presence of arbitrary outliers. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCS '18, pp.\ 45:1--45:21, Dagstuhl, Germany, 2018. Schloss Dagstuhl-...

    2018

  24. [32]

    On adaptive attacks to adversarial example defenses

    Tram \` e r, F., Carlini, N., Brendel, W., and Madry, A. On adaptive attacks to adversarial example defenses. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020

    2020

  25. [33]

    Tukey, J. W. A survey of sampling from contaminated distributions. Contributions to Probability and Statistics: Essays in Honor of Harold Hotelling, pp.\ 448--485, 1960

    1960

  26. [34]

    Valiant, L. G. A theory of the learnable. Communications of the ACM, 27 0 (11): 0 1134--1142, 1984

    1984

  27. [35]

    Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16 0 (2): 0 264--280, 1971

    1971

  28. [36]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

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