- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper addresses the design of robust learning algorithms against a strong notion of corruptions of training data: It assumes that there exists an adversary that strategically corrupts a constant fraction of the training data. The setting under consideration is a variant of the classical agnostic learning, which also assumes arbitrary errors training data. However, the generalization measure on the learned model is somewhat different. The traditional framework focused more on instanced based optimality, and here the learner's classifier is measured by the prediction error on the original, uncorrupted data distribution.
The hypothesis classes focused on in this paper is the multiclass linear classifiers. Although some of the design might be extendable to other multiclass hypotheses.
The author(s) identify sufficient condition geometric (based on classification margin) and distributional (concentration of component distributions in mixture distributions, e.g., measure by covariance bound) assumptions of the underlying data that still guarantee efficient noise-tolerant PAC learning against such a strong malicious adversary who can process the original clean training set and forge a fraction of examples with arbitrary labeled data.
Critical strengths
The problems studied in this paper are well motivated, which extended previous work on malicious-noise guarantees from certain family of binary classification problems to multiclass learning problems. The sufficient geometric- and distribution- separation conditions for efficient robust learning are natural, and its handling of mixture of distribution and their outliers and robust clustering is carefully thought of.
Critical weaknesses
While the paper is technically sound and the sufficient guarantees for learning robustness are meaningful, these assumptions are rather strong. For example, the margin gap condition requires clean examples to be well separated, which is rarely the case for real datasets. In addition, while the paper contains some interesting algorithmic components, the assumption of linear hypothesis classes limits the scope of the result.
Questions for authors
(1) A better comparison your framework of malicious-noise framework with the classical agnostic learning framework will be beneficial to highlight your contribution.
(2) When the number of classes in the multiclass learning before large, the corruption tolerance will become poorer. Any characterization on how high can the tolerance be?
3 comments
Thanks for the expanded explanation which helped me to gain a better understanding of the paper. However, for now I will stay with my overall evaluation.
Thank you for your response! If you feel our response has addressed all your concerns, would you consider raising your score? If there is anything you need further clarification for, please let us know and we can address them during the discussion period.
Response to b8E5: Contributions, Assumptions, and Noise Tolerance
We thank Reviewer b8E5 for their evaluation. Our paper establishes the first efficient proper PAC learning algorithm for multiclass linear classifiers under nasty noise and our stated margin and mixture assumptions. Reviewer MGNu described the problem and nasty noise setting as realistic and well motivated, and efficient multiclass algorithms as important and challenging. Reviewer spbp highlighted the improved pruning step and certificate's potential use elsewhere. Reviewer KCzY identified the support-graph certificate as a distinct contribution and found the clean-reference, multiclass gradient, and sampling analyses convincing. These advances address the assessment of “little or nothing new.”
1. Realism of Margin Gap Assumption:
Combining a margin condition with concentrated mixture components models multi-modal distributions. Deep embeddings of distinct species, acoustic features for individual speakers, and biomarker profiles with pathological subtypes within a class motivate this mixture structure. Assumptions 1.2 and 1.3 allow overlapping same-label components and multiple components per class, without requiring pairwise separation of component means.
Classical results motivate additional structure: distribution-free halfspace learning has malicious-noise tolerance at most ϵ/(1+ϵ) (Kearns & Li, 1988), while efficient algorithms under isotropic logconcave marginals achieve tolerance proportional to ϵ (Awasthi et al., 2017). Our margin and mixture conditions permit tolerance 1/(4096k2) independent of ϵ for fixed k, subject to the required margin γ(ϵ).
Restriction to Linear Hypotheses:
While linear classifiers might appear structurally simple, efficient multiclass linear learning under noise presents severe computational barriers, as evidenced by super-polynomial Statistical Query (SQ) lower bounds even for three classes under random classification noise (Diakonikolas et al., 2025b; lines 172--174). Our core contribution lies in establishing the first polynomial-time proper PAC learning guarantees under adaptive nasty noise by constructing a pairwise support-graph certificate (Program 9, Proposition 5.8) that jointly controls all k−1 competing label directions per sample (Section 1.2, lines 144--152) and guarantees clean PAC error without requiring the algorithm to estimate component means or recover underlying mixture distributions (lines 187--190).
2. Comparison to Agnostic Learning:
Classical agnostic learning and nasty noise have different sampling models and benchmarks. Agnostic learning uses independent samples from Q and targets $ \operatorname{err}_Q(\widehat h)\le\mathrm{OPT}+\epsilon, $ where OPT=infg∈HerrQ(g). Under nasty noise (Definition 1.1; Bshouty et al., 1999; Blanc et al., 2026), an adversary inspects the clean sample S and replaces an η fraction with arbitrary feature-label pairs. Surviving clean points in T need not remain independent.
An empirical risk minimizer h over the target class on T satisfies the generic comparison errS(h)≤errT(h∗)+η≤2η. This upper bound alone does not establish error ϵ<η. Our SDP certificate and multiclass concentration analysis, building on binary results (Talwar, 2020; Shen, 2025), give clean error at most ϵ under the stated conditions. The Gaussian multiclass agnostic results cited in Section 2 allow outputs outside the linear class and measure observed-label error; they do not directly provide our guarantee under adaptive feature replacement.
3. Maximum Noise Tolerance vs. Class Count k:
Theorems 1.2 and 1.3 guarantee tolerance 1/(4096k2) for both distribution families. The tolerable corruption depends on component weights and the margin. Our analysis compares clean counts proportional to α with corrupted influence proportional to ση/γ. Using γ>4Cσ and α=Θ(1/k) gives the common 1/k2 threshold (Theorem B.2). The blockwise Cauchy–Schwarz argument avoids an additional factor of k (lines 434–436).
For 0<ϵ<1/2, the retained count in Eq. (69) permits a sixteenfold numerical improvement to η≤1/(256k2), retaining the other theorem conditions and optimization premise.
For K≥k, allowing 0<α≤1/k requires corresponding sample and margin conditions. Tracking α in the counting and feasibility arguments gives sufficient bounds n=O(kd/α),η≤α2/256, provided γ>max8σk/ϵ,8σ/α,4Cσ, again for 0<ϵ<1/2 with the optimization retained. For comparable weights, α=Θ(1/K), this gives O(kKd) samples and sufficient tolerance of order K−2.