acceptodds
Under review as a conference paper at ICLR 2027

Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers

Abstract

Noise-tolerant PAC learning of linear models has long been a central problem in machine learning. In this paper, we study the multiclass linear classfiers under the challenging nasty noise. We propose the first computationally-efficient algorithm under the assumption that the marginal distribution is a mixture of bounded variance distributions and the uncorrupted data sets satisfy a margin condition. Our algorithm consists of two main ingredients: a convex optimization program that prunes corrupted samples by bounding the pairwise squared distance, and a standard multiclass hinge loss minimization. We provide a multiclass gradient analysis and show that after the pruning, the hinge loss minimization naturally enjoys a strong robustness. Specially, we establish a deterministic condition that for any corrupted sample surviving the pruning, there exists a close-by reference point that enjoys the margin condition like a clean sample. As a result, we show that efficient PAC learning is possible with a sample complexity of , where hides logarithmic terms, for the class of multiclass linear classifiers under a significant amount of nasty noise.

Primary area:
learning theory
Keywords:
PAC Learning, Multiclass Linear Classification, Nasty Noise, Robust Learning, Outlier Removal

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_b8E5OpenReview ↗
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
AuthorsOpenReview ↗

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+ϵ)\epsilon/(1+\epsilon) (Kearns & Li, 1988), while efficient algorithms under isotropic logconcave marginals achieve tolerance proportional to ϵ\epsilon (Awasthi et al., 2017). Our margin and mixture conditions permit tolerance 1/(4096k2)1/(4096k^2) independent of ϵ\epsilon for fixed kk, subject to the required margin γ(ϵ)\gamma(\epsilon).

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−1k-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 QQ and targets $ \operatorname{err}_Q(\widehat h)\le\mathrm{OPT}+\epsilon, $ where OPT=inf⁡g∈Herr⁡Q(g)\mathrm{OPT}=\inf_{g\in\mathcal H}\operatorname{err}_Q(g). Under nasty noise (Definition 1.1; Bshouty et al., 1999; Blanc et al., 2026), an adversary inspects the clean sample SS and replaces an η\eta fraction with arbitrary feature-label pairs. Surviving clean points in TT need not remain independent.

An empirical risk minimizer h^\widehat h over the target class on TT satisfies the generic comparison err⁡^S(h^)≤err⁡^T(h∗)+η≤2η.\widehat{\operatorname{err}}_S(\widehat h)\le\widehat{\operatorname{err}}_T(h^*)+\eta\le2\eta. This upper bound alone does not establish error ϵ<η\epsilon < \eta. Our SDP certificate and multiclass concentration analysis, building on binary results (Talwar, 2020; Shen, 2025), give clean error at most ϵ\epsilon 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 kk:

Theorems 1.2 and 1.3 guarantee tolerance 1/(4096k2)1/(4096k^2) for both distribution families. The tolerable corruption depends on component weights and the margin. Our analysis compares clean counts proportional to α\alpha with corrupted influence proportional to ση/γ\sigma\sqrt\eta/\gamma. Using γ>4Cσ\gamma > 4C\sigma and α=Θ(1/k)\alpha=\Theta(1/k) gives the common 1/k21/k^2 threshold (Theorem B.2). The blockwise Cauchy–Schwarz argument avoids an additional factor of kk (lines 434–436).

For 0<ϵ<1/20 < \epsilon < 1/2, the retained count in Eq. (69) permits a sixteenfold numerical improvement to η≤1/(256k2)\eta\le1/(256k^2), retaining the other theorem conditions and optimization premise.

For K≥kK\ge k, allowing 0<α≤1/k0 < \alpha\le1/k requires corresponding sample and margin conditions. Tracking α\alpha in the counting and feasibility arguments gives sufficient bounds n=O~(kd/α),η≤α2/256,n=\widetilde O(kd/\alpha),\quad\eta\le\alpha^2/256, provided γ>max⁡8σk/ϵ,8σ/α,4Cσ,\gamma > \max\\{8\sigma\sqrt{k/\epsilon},8\sigma/\sqrt\alpha,4C\sigma\\}, again for 0<ϵ<1/20 < \epsilon < 1/2 with the optimization retained. For comparable weights, α=Θ(1/K)\alpha=\Theta(1/K), this gives O~(kKd)\widetilde O(kKd) samples and sufficient tolerance of order K−2K^{-2}.

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.

Reviewer_KCzYOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies proper learning of multiclass linear classifiers under adversarial replacement of both features and labels. Under hard-margin and bounded-covariance mixture assumptions, it combines label-aware SDP pruning with multiclass hinge-loss minimization, obtaining error ϵ\epsilon with O~(k2d)\widetilde{O}(k^2d) samples and noise tolerance 1/(4096k2)1/(4096k^2). Logconcavity improves the required margin dependence.

Critical strengths
  • The pairwise support-graph certificate is a distinct contribution: surviving corrupted points receive clean, same-label reference points whose aggregate directional deviations are controlled.
  • The result extends binary hinge-loss robustness to proper multiclass learning under adaptive feature-and-label corruption, without requiring bounded component means.
  • The clean-reference argument, multiclass gradient bounds, and uniform sampling analysis are convincing. Importantly, concentration is established before adaptive corruption; the proof does not incorrectly assume that surviving clean points remain independent.
  • The algorithm, structural assumptions, and proof architecture are clearly stated, with detailed proofs supplied.
Critical weaknesses

The polynomial-time implementation is not fully connected to the learning guarantee. The statistical analysis requires exactly feasible pruning weights and an exact hinge-loss minimizer. However, Remark D.5 establishes only approximate feasibility, while Appendix B.3 invokes standard convex optimization without specifying an optimization tolerance.

This distinction matters: the clean-reference certificate uses nonnegative weights and exact matrix constraints, while the classification proof invokes exact subgradient/KKT optimality. A quantitative argument is needed showing that suitably repaired approximate weights and an approximately optimal classifier preserve the stated error and noise guarantees. This is a completeness gap in the headline computational claim—not evidence that the statistical theorem is false.

An important scope qualification, rather than a proof error: for fixed finite γ/σ\gamma/\sigma, the stated sufficient conditions do not cover arbitrarily small ϵ\epsilon. Moreover, hard support-wide margin makes each logconcave component single-label, excluding ordinary full-support Gaussian mixtures. Thus, the constant-noise, vanishing-error interpretation depends on increasingly strong separation as accuracy increases.

Questions for authors

Could you explicitly delimit the fixed-γ/σ\gamma/\sigma accuracy regime and explain how the single-label implication for logconcave components affects the intended interpretation of the result?

3 comments
AuthorsOpenReview ↗

Response to KCzY: Numerical Precision, Accuracy Regimes, and Component Geometry

Thank you for acknowledging the certificate of support graph and the analysis under adaptive corruption.

1. Gap Between Exact Theory and Approximate Solvers:

We thank Reviewer KCzY for highlighting this operational detail. We agree that explicitly describing stopping criteria of solver adds value to the computational analysis.

Remark D.5 establishes the polynomial-time approximate feasibility for Program (9). We make the quantitative connection to the learning guarantee without altering the existing statistical proofs.

With all the theorem conditions remaining, including η≤1/(4096k2)\eta\le1/(4096k^2), and considering 0<ϵ<1/20<\epsilon<1/2, like Proposition C.4, we set the precision parameter in Remark D.5 as

\frac{C^2\sigma^2n} {32(1+\sum_{i<j}\\|x_i-x_j\\|_2^2)}\right\\}.$$ This coordinate dependent precision controls numerical error on the matrix constraint. With the pruning rule $a_i\ge1/2$, we define $a_{ij}^{+}=\max\\{a_{ij},0\\}$ for the proof to construct the clean same label reference points $\mu_{i,C}$. For each retained point, approximate constraints give $$\sum_{j\in S_C}a_{ij}^{+} \ge(1-4\eta/\alpha)a_i-\eta n\zeta \ge\frac7{16}.$$ These reference points satisfy the target margin $\gamma$ exactly, and the calculation in Proposition 5.8 gives $$\sum_{i\in\widehat S_D} (x_i-\mu_{i,C})(x_i-\mu_{i,C})^\top \preceq C^2\sigma^2nI_d.$$ The approximate weight bounds allow at most $\alpha n/4$ total deletion. On the clean sample count event, the surviving pancake size satisfies $$|S_P|\ge3\alpha n/8-\eta n-\alpha n/4 \ge7\alpha n/64.$$ Using Eqs. (29)--(32), the target classifier satisfies $$\ell_\gamma(w^*;\widehat S) \le\frac{2C\sigma n\sqrt\eta}{\gamma} <\frac{n}{64k}.$$ From Eq. (22), misclassifying an indicated center requires loss at least $$\frac{|S_P|}{2} \ge\frac{7\alpha n}{128} \ge\frac{21n}{640k}.$$ An approximate minimizer $\widehat w$ whose objective is within tolerance at most $n/(128k)$ satisfies $$\ell_\gamma(\widehat w;\widehat S) <\frac{n}{64k}+\frac{n}{128k} =\frac{15n}{640k}<\frac{21n}{640k},$$ hence correctly classifying all indicated centers, which cover at least $1-\epsilon$ clean mass. We will include the precision computation after Remark D.5 and the objective tolerance and numerical feasibility calculations in Appendix B.3. Those precisions only need polynomial bit length in the rational input, leaving the statistical bounds intact in the stated accuracy reigme. **2. Scope of Fixed-Margin vs. Target Accuracy Regimes:** For a fixed normalized margin ratio $r:=\gamma/\sigma>4C$, the accessible accuracy regimes derived from inverting the margin conditions of Theorems 1.2 and 1.3 are : $$\epsilon>\frac{64k}{r^2}\quad\text{(Theorem 1.2)},\qquad \epsilon>k\exp(1-r/8)\quad\text{(Theorem 1.3)}.$$ These inequalities specify the sufficient accuracy regimes certified by our upper bound analysis for a given $r$, but not ther information-theoretic lower bounds on achievable error. In these certified regimes, our noise tolerance $\eta\le1/(2^{12}k^2)$ remains constant and independent of $\epsilon$ for fixed $k$. Remark 1.4: In order to attain vanishing PAC error $\epsilon\to0$ one requires a larger margin separation of the form $r(\epsilon)=\Omega(\sqrt{k/\epsilon})$ or $\Omega(\log(k/\epsilon))$ in these certified regimes. We will explicitly state these inequalities in Remark 1.4 in the revision. **3. Interpretation of Component Geometry and Single Label Implications:** We emphasize that the algorithm and general framework (Theorem 1.2) does not rely on or necessitte convex support; bounded covariance components can be non-convex and overlapping across multiple labels. In Theorem 1.3, log-concavity refers to natural mathematical property of the log-concave component model(Lovász & Vempala, 2007). Log-concave probability densities have connected convex support, which means that any margin gap between two classes seperates two log-concave components, so log-concave components cannot straddle a decision boundary under margin separation (lines 1159--1165). Thus, log-concave components are single label under margin separation. Standard full-support Gaussians are not allowed by this margin seperation; standard tail truncation cannot provide the margin requirement. We will add these explicit structural clarifications in Remark 1.4 and Section 2 of the revision. We hope this addresses your concerns.

Thanks for addressing my concerns! I will maintain my rating.

Thank you for considering our clarifications on numerical optimization and the scope of our results. If you think we have addressed your concerns, would you consider strengthening your support for our paper? We are happy to address any remaining questions during the discussion period.

Reviewer_spbpOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies multiclass PAC learning with k classes of linear classifiers under "nasty noise" (one of the common noise models, the most adversarial, one could say). Under two assumptions (margin and that the distribution is a mixture of K = O(k) either bounded variance or even log-concave distributions) the authors provide a poly-time learner (with two different results for bounded variance vs log concave). Here a learner outputs a proper (i.e., from the target class) linear classifier that has error at most ϵ\epsilon under the uncorrupted distribution.

  1. with the more general bounded variance σ\sigma assumption the marign has to be roughly σk/ϵ\sigma\sqrt{k/\epsilon}
  2. in the more restricted log-concave assumption the margin has only satisfy the much weaker σlog⁡(k/ϵ)\sigma\log(k/\epsilon)
Critical strengths

A nice strength I see, which could be interesting also in other settings, is the improved pruning step in the algorithm and the corresponding deterministic certificate. Beyond that this is an important problem to study in an interesting line of work (poly-time learning of linear classifiers under noise).

Critical weaknesses

I believe the paper mainly lacks a lot of context for a reader (even one from learning theory) who is not too familiar with this efficient learning of linear classifiers (under different marginals, noise types, ...) line of work. See also questions.

  • while you briefly discuss the different noise models it is not clear in which of them and under which additional distributional assumptions (multiclass-) learning becomes polynomial time. I see that it is many different combinations and variants but perhaps an overview table would be nice: what is known in each noise models, distributional assumptions, binary vs multiclass. This is presented somewhat unstructured throughout the paper and the related work section.
  • For example, in a simpler noise model (not nasty) are there known multiclass poly-time results (for potentially broader families of distributions etc.).
  • in general guiding a reader who is not too familiar with this line of work would be nice. E.g., why are SQ lower bounds relevant here
  • In a similar way justifying the assumptions would help: something like removing any makes it "hard" or unlikely to work given these other papers where it also failed (or is already believed to fail for the binary case etc.).

Moreover, a broader discussion of the necessity for the assumptions and lower bounds would strengthen this work. However, I see that in a computational setting unconditional (or similarly general) lower bounds are hard to get. Please argue why you believe that your sample complexity upper bounds are near-optimal.

Questions for authors
  • The log⁡(1/ϵ)\log(1/\epsilon) in the sample complexity seems a bit surprising to me. From realizable PAC I'd expect O(1/ϵ)O(1/\epsilon) and from agnostic PAC O(1/ϵ2)O(1/\epsilon^2) (and perhaps in some of the noise models with level η\eta something like O(1/(ϵη))O(1/(\epsilon\eta)). It seems to me this happens due to your margin assumption, which might hide a lot of complexity. Can you comment?
  • Can you generalize your log-concave result (2nd theorem) to the broader and more interesting family of subexponential marginals?
  • The implicit assumption of having a mixture only over K=O(k)K = O(k) distributions seems quite limiting to me. Is this unavoidable? Is say K=poly(k)K=poly(k) possible? Why is an extremely large KK probably infeasible (or would you just get a dependence on KK in the sample complexity)
  • why do standard reductions (e.g., poly-time ERM yields poly-time learnability here or something, reductions among the different noise models etc.) not apply?

Minor question:

  • Is the 1/2121/2^{12} improvable? It would be great to see the algorithm to work for a wider noise range (even though clearly having some constant here is the crucial part!).
3 comments

Thank you for appreciating our technical contributions and providing insightful feedback.

1. Literature overview. Unlike prior work, our noise tolerance remains constant as target error ϵ→0\epsilon \to 0. To clarify problem settings, runtimes, noise bounds, and marginal assumptions, we will include the summary table below in our revision.

WorkLabel SpaceNoise ModelToleranceAssumption
Awasthi et al. (2017)BinarymaliciousO(ϵ)O(\epsilon)isotropic logconcave
Shen (2025)k=2k=2maliciousO(1)O(1)margin and mixtures
Diakonikolas et al. (2026)k=3k=3agnostic labelO(ϵ)O(\epsilon)isotropic Gaussian
Diakonikolas et al. (2026)k≥3k\geq3agnostic labelOk(ϵ2)O_k(\epsilon^2)isotropic Gaussian
This workk≥3k\geq3nastyOk(1)O_k(1)margin and mixtures

Table 1 : Noise Tolerance in Linear Classification.

We can see from this table that combining margin and bounded-covariance mixture assumptions breaks the O(ϵ)O(\epsilon) PAC noise barrier.

Simpler noise models Distribution-free proper multiclass linear learning (k≥3k \ge 3) faces super-polynomial SQ lower bounds even under RCN (Diakonikolas et al., 2025b), while Gaussian models yield only improper non-linear classifiers measuring error on corrupted distributions (Diakonikolas et al., 2025a, 2026).

SQ lower bound SQ lower bounds prove that without structural assumptions, efficient robust multiclass learning is computationally impossible. Thus, SQ bounds justify why our paper introduces margin and mixture assumptions. We will make this explicit in Section 2.

Necessity of assumptions Combining margin and log-concave mixture assumptions is essential to break the long-standing Θ(ϵ)\Theta(\epsilon) noise barrier (even in binary settings). Without a margin (γ>0\gamma > 0), feature corruption under nasty noise restricts noise tolerance to a vanishing rate η=O(ϵ)\eta = O(\epsilon) as target error ϵ→0\epsilon \to 0 (Kearns & Li, 1988; Awasthi et al., 2017). With margin alone, the best known noise tolerance was Ω(ϵγlog⁡(1/γ))\Omega(\epsilon\gamma\sqrt{\log(1/\gamma)}). The margin condition together with concentration directly overcomes this theoretical barrier, yielding the first efficient multiclass PAC guarantee with constant noise tolerance η=Ω(1/k2)\eta = \Omega(1/k^2) independent of ϵ\epsilon. See also Table 1 of Shen (2025).

Sample complexity. Our sample complexity of O~(k2d)\tilde{O}(k^2 d) (Theorems 1.2 and 1.3) maintains linear scaling in dd. For k=2k=2, our bound reduces to O~(d)\tilde{O}(d).

2. Margin Assumption & Sample Complexity Scaling: Using our assumptions, n=O~(k2dlog⁡(1/ϵ))n = \tilde{O}(k^2 d \log(1/\epsilon)) need only ensure ϵ\epsilon-dense pancakes via an ϵ\epsilon-net cover (Eq. 60; Thms 5.9--5.11), bypassing standard O(1/ϵ)O(1/\epsilon) or O(1/ϵ2)O(1/\epsilon^2) bounds. Target accuracy ϵ\epsilon is encoded into margin γ(ϵ)\gamma(\epsilon) (Ω(σk/ϵ)\Omega(\sigma\sqrt{k/\epsilon}) in Thm 1.2; Ω(σlog⁡(k/ϵ))\Omega(\sigma\log(k/\epsilon)) in Thm 1.3) rather than inflating sample complexity (Remark 1.4), isolating clean data beyond distance γ\gamma. Because boundary tail mass is inherently corruption-vulnerable, expanding γ(ϵ)\gamma(\epsilon) as ϵ→0\epsilon \to 0 restricts the spatial volume available for an adversary to distort decision hyperplanes.

3. Subexponential marginals. Yes, under a uniform projection-tail condition: every component satisfies Pr⁡(∣⟨w,X−μj⟩∣≥tσ)≤2e−t/B\Pr(|\langle w,X-\mu_j\rangle|\ge t\sigma)\le2e^{-t/B} for every unit ww and t>0t>0, with fixed B≥1B\ge1. Taking t=Blog⁡(2k/ϵ)t=B\log(2k/\epsilon) gives probability at most ϵ/k\epsilon/k. Extending the same-label counting and label-exclusion arguments gives O~(k2d)\widetilde O(k^2d) samples with γ=Ω(Bσlog⁡(k/ϵ))\gamma=\Omega(B\sigma\log(k/\epsilon)), retaining covariance, weight, and γ>4Cσ\gamma>4C\sigma conditions. We will include these arguments in Appendices C-D.

4. Extension to K=poly(k)K = \text{poly}(k): Theorem 5.11 and Proposition D.2 fully support extending to K=poly(k)K = \text{poly}(k) in polynomial runtime with sample complexity n=O~(kKd)n = \tilde{O}(kKd) for minimum component weight α≈1/K\alpha \approx 1/K. However, as KK increases, the noise tolerance scales as η≤α2/256=O(1/K2)\eta \le \alpha^2 / 256 = O(1/K^2) and becomes negligible; thus, we focus on the K≤5k/3=O(k)K \le 5k/3 = O(k) regime in the paper to guarantee a constant noise tolerance rate η=Ω(1/k2)\eta = \Omega(1/k^2).

5. Inadequacy Standard Reductions: For original sample SS, corrupted sample TT, and an empirical error minimizer h^\widehat h on TT, err^S(h^)≤err^T(h∗)+η≤2η\widehat{\mathrm{err}}_S(\widehat h)\le\widehat{\mathrm{err}}_T(h^*)+\eta\le2\eta. This does not establish our possible ϵ<η\epsilon<\eta guarantee. Random label-noise results do not cover adaptive feature replacement. C.4 establishes concentration before corruption; 5.8 controls retained corruptions.

6. Tight Noise Tolerance Constant: Using clean pancake density (Eq. 69) tightens the numerical constant 16-fold from η≤1/(4096k2)\eta\le1/(4096k^2) to η≤1/(256k2)\eta\le1/(256k^2).

We hope this addresses your concerns.

Thanks for the clarifications. I keep my score.

Thank you for considering our response. If our clarifications have addressed your concerns, would you consider strengthening your support for our paper? We are happy to address any remaining questions during the discussion period.

Reviewer_MGNuOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work studies the problem of multiclass linear classification when the examples and labels are corrupted. There exists a ground truth linear classification function f(x) = \argmax_{y=1,...,k} W_y^* \cdot x. An adversary first generates labeled examples (x, y) as usual where x is drawn from some feature distribution and y is given by the ground truth f(x). After that the adversary can inspect the learning algorithm and decide how to change an \eta-fraction of the examples. The adversary can alter both x and the corresponding label of the chosen \eta fraction (they can introduce both label and feature noise). The learner then receives the dataset (with at most \eta-fraction of corrupted points) and their goal is to find a classifier h(x) that achieves \epsilon classification error when compared to the ground-truth f(x) over the original (clean) examples.

The authors present 2 main algorithmic results in this setting.

First they assume that the feature distribution of the examples is a mixture of K distributions each of which has bounded covariance and that all points x satisfy a geometric margin assumptions with respect to the ground truth f(x), that is the top1 minus top2 logits should have difference bigger than \gamma. Assuming that \gamma is larger than the covariance \sigma * \sqrt{k/\epsilon} (this means that each component of the mixture is not very likely to cross classification decision boundary) and that the fraction of corrupted examples is less than 1/k^2 (k is the number of classes), they give a proper learning algorithm with polynomial (in number of classes k and dimension d) runtime and sample complexity.

Their second result assumes that the components of the mixture feature distribution are log-concave (more structured family of distributions with stronger concentration and anti-concentration structure, Gaussian for example is log-concave). Under this more structured class they show that the margin \gamma has to be larger than roughly \sigma * \log(k/\epsilon) (significantly better dependence on k and epsilon than in their first result).

Critical strengths
  1. I think that the studied problem and the nasty noise setting is realistic and well-motivated with a lot of prior works in this area. Efficient algorithms for multiclass learning with nasty noise are important and challengingto develop.
Critical weaknesses
  1. It seems to me that the range of parameters that this work operates in is rather limiting: the margin has to be much larger than \sigma \sqrt{k/\epsilon} or (\sigma \log(k/\epsilon)). This suggests a connection to clustering-based approaches. I thinki it would be helpful to clarify whether existing robust clustering or filtering methods can exploit this structure, and which remaining difficulty necessitates the proposed method. The authors mention that they conjecture such a dependence is unavoidable in Remark 1.4 and while they motivate those limitations based on their concentration proof, they don't give convincing formal evidence for this claim.

  2. Beyond the assumptions on the margin, they also require the noise rate to be smaller than 1/k^2 (k is the number of classes). This means that with more classes the fraction of points that the adversary controls has to decay to zero significantly fast. On top of those they also require a lower bound on the weights of the mixture distribution of the features (to be roughly larger than 0.6/k). These additional parameter dependences limit the results and makes it harder to understand how interesting the provided algorithms are.

Questions for authors

The authors seems to focus on proper learning in their definition 1.1 (that is the learner has to output a linear classification weight matrix W). In general, for this task I think even non-proper learning (producing any hypothesis with small classification error) is interesting and open. Is it easier to have a non-proper learning algorithm in this setting? Would it require the same set of strong margin and noise rate assumptions?

Also please see weaknesses. Thank you!

3 comments
AuthorsOpenReview ↗

Clarifying Our Assumptions, Noise Tolerance, and Learning Guarantees

We thank the reviewer MGNu for recognizing the importance of multiclass learning under nasty noise. We address each concern below.

1. Margin Scale vs. Robust Clustering/Filtering Capabilities:

The cited clustering and filtering guarantees (e.g., Peng & Wei, 2007; Steinhardt et al., 2017) do not directly imply our classification guarantee for two core reasons. First, guarantees for recovering separated components require Euclidean mean separation (∥μi−μj∥≥Δ\|\mu_i-\mu_j\|\ge\Delta), whereas we impose no pairwise component-mean separation assumption on same-label components; their means can coincide. The margin does imply separation between means of different classes. Second, clustering and variance control alone do not supply the clean same-label support required by Proposition 5.8. Our SDP (Program 9) leverages same-label supervision to prune directional corruptions without estimating mixture means.

Evidence for γ(ϵ)\gamma(\epsilon) Margin Scaling: Regarding the margin dependence γ(ϵ)\gamma(\epsilon) (Remark 1.4), Chebyshev's inequality under bounded covariance (Assumption 1.2) shows that a unit projection deviating by >σk/ϵ> \sigma\sqrt{k/\epsilon} has probability ≤ϵ/k\le \epsilon/k. Dense-pancake analysis (Appendix C) and Lemma 5.3 require γ>4τ\gamma > 4\tau, where τ=2σk/ϵ\tau = 2\sigma\sqrt{k/\epsilon} (Theorem 1.2) or 2σ(1+log⁡(k/ϵ))2\sigma(1+\log(k/\epsilon)) for log-concave components (Assumption 1.3, Theorem 1.3).

To give formal evidence under bounded covariance, set k=d=2k=d=2 with masses 1−q1-q and qq at (γ,0)(\gamma,0) and (0,γ)(0,\gamma), where q=4ϵ≤η/4<1/8q=4\epsilon\le\eta/4 < 1/8. Let W0,W1W_0, W_1 have first rows (1,1)/2(1,1)/2 and (1,−1)/2(1,-1)/2, respectively, and second rows equal to their negatives. Both satisfy ∥Wi∥F=1\|W_i\|_F=1 and clean margin γ\gamma. This single component has covariance norm σ2=2q(1−q)γ2\sigma^2=2q(1-q)\gamma^2. Coupling feature draws and learner randomness, the disagreement count NN satisfies Pr⁡(N>ηn)≤q/η≤1/4\Pr(N > \eta n)\le q/\eta\le1/4. Relabeling disagreements to label 1 under W1W_1 when permitted yields identical received samples with probability ≥3/4\ge 3/4, while PAC error sum to at least q>2ϵq > 2\epsilon. Thus, at least one target has failure probability ≥3/8\ge 3/8, holding even for improper learners. Since γ/σ=Θ(ϵ−1/2)\gamma/\sigma=\Theta(\epsilon^{-1/2}), this supplies explicit lower-bound evidence for accuracy dependence under bounded covariance, though not optimality in kk or the log-concave rate.

2. Noise Tolerance Decay (η<1/k2\eta < 1/k^2) for Large Class Count kk:

The threshold η≤1/(4096k2)\eta\le1/(4096k^2) is a sufficient guarantee for kk-class learning, not a claimed maximum. An η\eta global corruption rate concentrated in one balanced class of weight 1/k1/k equals an η⋅k\eta\cdot k relative corruption. The blockwise Cauchy--Schwarz argument avoids an additional factor of kk (lines 434--436). The stated threshold follows by comparing clean counts of order α\alpha with corrupted influence of order ση/γ\sigma\sqrt{\eta}/\gamma. Notably, Diakonikolas et al. (2025b) proved SQ hardness for k≥3k\ge3 even under benign RCN, making our polynomial-time guarantee under nasty noise the first positive result of its kind.

Minimum Component Weight Constraint (α≥0.6/k\alpha\ge0.6/k):

The condition α≥0.6/k\alpha\ge0.6/k ensures sufficient clean sample counts and is not an algorithmic limit. Tracking α\alpha in the counting and feasibility arguments gives n=O~(kd/α)n=\widetilde O(kd/\alpha) and η≤α2/256\eta\le\alpha^2/256 for 0<ϵ<1/20 < \epsilon < 1/2 and 0<α≤1/k0 < \alpha\le1/k, provided γ>max⁡{8σk/ϵ,8σ/α,4Cσ}\gamma > \max\{8\sigma\sqrt{k/\epsilon},8\sigma/\sqrt{\alpha},4C\sigma\} and the theorem's optimization premise is retained. For comparable component weights, α=Θ(1/K)\alpha=\Theta(1/K), this gives O~(kKd)\widetilde O(kKd) samples and noise tolerance of order K−2K^{-2}. Thus K=poly(k)K=\mathrm{poly}(k) is possible under these conditions. We focus on α≥0.6/k\alpha\ge0.6/k in the main text to highlight a constant noise rate for fixed kk.

3. Proper vs. Improper Learning under Nasty Noise:

Our algorithm is PROPER—it outputs a linear weight matrix W^∈Rk×d\widehat{W}\in\mathbb{R}^{k\times d}. Whether improper learning permits weaker margin or noise conditions remains unresolved by our analysis. The construction above gives identical received samples for different targets, even for improper learners. Distribution free multiclass classification faces super-polynomial SQ lower bounds for achieving optimal error even for improper algorithms within the SQ model (Diakonikolas et al., 2025b). While improper Gaussian algorithms (Diakonikolas et al., 2025a, 2026) output non-linear partitions evaluated on noisy distributions, our proper linear classifier achieves vanishing PAC error ≤ϵ\le\epsilon using O(kd)O(kd) arithmetic operations per prediction and retaining linear interpretability.

We hope this addresses your concerns.

Thanks for the detailed response. I am still concerned about the restrictive parameter regime (the required margin increases as the target error decreases and the noise tolerance decreases as 1/k^2). Explaining how these conditions arise in the analysis is helpful, but does not show why the parameter ranges are inherent (maybe they are for this specific approach). The lower bound that the author mentioned provides some evidence for some accuracy dependence but does not explain why such restrictive assumptions are necessary. I will be maintaining my score for now.

AuthorsOpenReview ↗

Official Comment by Authors

We thank the reviewer for responding to our rebuttal.

Regarding the restriction of parameters, we remark that prior work in this line has already had such dependence, i.e. margin γ\gamma on error ϵ\epsilon, and malicious noise tolerance η\eta on 1/k21/k^2. While Shen (2025) has conjectured that incorporating active learning techniques may resolve the dependence of γ\gamma on ϵ\epsilon, that falls outside the study of this work. In this paper, we mainly extend the prior techniques in the multiclass setting. We propose a novel filtering technique that can efficiently remove outliers when label space ∣Y∣≥3\lvert Y \rvert \ge 3, and achieve a strong noise tolerance in the more challenging nasty noise setting. This algorithm and its guarantees remain valid in its binary counterpart. For the dependence of $ \eta = O(1/k^2)$, we conjecture that it is inherent due to the second moment analysis (see also Shen 2025 and Zeng-Shen 2026). To further improve the dependence, incorporating higher-order moments will be a promising direction. We leave this as our future work.

While the assumption of both margin and mixture is relatively new in this field compared to a long list of work that depends on the isotropic Gaussian/logconcave marginals, it is also the only one in its kind that can tolerate a noise rate even larger than the error rate.

References:

Shen 2025: Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate, ALT 2025

Zeng-Shen 2026: Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate, NeurIPS 2026

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.