Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
arXiv:2605.18662v1 [cs.LG] 18 May 2026
Rita Adhikari Augusta University [email protected]
Shiwei Zeng Augusta University [email protected]
May 19, 2026
Abstract Noise-tolerant PAC learning of linear models has been of central interests in machine learning community since the last century. In recent years, many computationally-efficient algorithms have been proposed for the problem of learning linear threshold functions under multiple noise models. Yet, when the problem is considered under multiclass learning settings, i.e. when the number of classes k is at least 3, it is unknown whether there exist computationally-efficient PAC learning algorithms when the data sets are maliciously corrupted. In this paper, we consider that the marginal distribution is a mixture of bounded variance distributions and the data sets satisfy a margin condition at the same time. We show that there exists a computationally-efficient algorithm that PAC learns multiclass linear classifiers {hw : x 7→ arg maxy∈[k] wy · x, x ∈ Rd , w ∈ Rkd } using at most O(k 2 · (d log d + log k)) samples even under a constant rate of nasty noise. Our algorithm consists of two main ingredients: a cluster-based pruning scheme and a standard multiclass hinge loss minimization program. Even in the special case of binary setting, i.e. k = 2, our result is strictly stronger than all prior works.
1
Introduction
This paper revisits the problem of learning the multiclass linear classifiers (MLCs) under noise corruptions. Robust learning problems have been extensively studied under the binary learning scenarios. However, our understanding of when and how we can achieve algorithmic robustness under the multiclass learning settings, i.e. k > 2, is falling short. Notably, it was shown recently in [DMRT25] that distribution-free learning of multiclass linear classifiers under the random classification noise suffers from a super-polynomial statistical query lower bound, while the problem is polynomial-time learnable when k = 2 [BFKV98]. This gap shows that efficient robust learning in the multiclass settings differs drastically from that in the binary settings. Hence, it is natural to ask: Does there exist natural condition under which the algorithmic robustness established in binary settings carry over to the multiclass settings? We answer the above question in the affirmative by considering the conditions being investigated in recent work of [Tal20, She25]. That is, they have shown that if we incorporate two widely used distribution conditions, i.e. concentration and margin conditions, there exists computationally efficient algorithms that probably approximately correctly (PAC) learn the target halfspace even with a constant fraction of corruptions under the challenging malicious noise model [KL88]. This result ϵ is surprising as there exists known information-theoretical lower bound of 1+ϵ for distribution-free 1
learning of halfspaces under malicious noise corruptions. Even with concentration distributional conditions alone, the best known malicious noise tolerance was Θ(ϵ) for halfspaces [ABL17]. For learning of MLCs, a recent work of [DIKZ25] proposes an algorithm with noise tolerance of Θ(ϵ) under the Gaussian marginals in the presence of label noise. It is not clear whether significant improvements in noise tolerance are achievable without introducing new conditions or techniques. However, incorporating the concentration and the margin conditions can immediately improve the noise tolerance drastically to a constant rate for challenging noise models such as adversarial label noise [Tal20] and malicious noise [She25]. Moreover, the algorithmic design is simple, i.e. surrogate loss minimizaton with spectral filtering schemes, and the theoretical framework is elegant. In this work, we extend this framework to multiclass learning settings. Specifically, let X ⊆ Rd be the instance space, and Y = {1, 2, . . . , k} be the label space. We consider the class of MLCs H := {hW : x 7→ arg maxy∈Y Wy x, W ∈ Rk×d , y ∈ [k]} and assume that the marginal distribution DX is a mixture of bounded variance distributions or logconcaves. Moreover, we assume that any empirical sample set from the underlying distribution D over X × Y satisfies a margin condition. In our analysis, we focus on the most challenging nasty noise model. Definition 1 (PAC learning of MLCs with nasty noise). Let ϵ, δ ∈ (0, 1) be the target error rate and confidence parameter, respectively. A nasty adversary EXnas (DX , W ∗ , η) fixes DX , W ∗ and η ∈ (0, k1 ) throughout the learning process, takes a request from the learner, and first draws n instances independently from DX and labels them by W ∗ , forming a clean sample set SC = {(xi , arg maxy∈Y Wy∗ xi )}ni=1 . The adversary, fully aware of the learning algorithm, may then inspect the set SC and replace at most an η fraction of it with any instance-label pairs from X × Y. The resulting set S is returned to the learner. The goal of the learner is to output a multiclass linear c ∈ Rk×d such that with probability 1 − δ (over the randomness of the samples and all classifier W cy x ̸= arg maxy∈Y W ∗ x) ≤ ϵ. internal random bits of the learning algorithm), Prx∼DX (arg maxy∈Y W y
1.1
Main results
To ensure efficient learnability, we rely on the following structural assumptions regarding the margin and the marginal distribution. Note that the parameter K we used in Assumption 2 and 3 does not necessarily equal to the number of classes k. Assumption 1 (Multiclass γ-margin condition). There exists a vector w∗ ∈ Rkd with ∥w∗ ∥2 ≤ 1 and a margin γ > 0 such that for any clean sample (x, y) in the support of D: min
y ′ ∈Y\{y}
w∗ , Ψ(x, y) − Ψ(x, y ′ ) ≥ γ.
(1.1)
Assumption 2 (Mixtures of distributions). The marginal distribution DX is a mixture of K P distributions D1 , . . . , DK , i.e., DX = K1 K q D j=1 j j . Furthermore, for each component j ∈ [K], Dj is a distribution over X with mean µj = Ex∼Dj [x] and covariance matrix Σj = Ex∼Dj [(x − µj )(x − µj )⊤ ] satisfying Σj ⪯ σ 2 Id . Remark 2 (Generalization of assumptions). The prior works of [Tal20, She25] also assumed both the margin and mixture of logconcaves conditions. However, our setting is much more general with any parameter σ, as long as the margin parameter γ is made compatible to it. In contrast, their algorithm works only for σ = √1d . Though our algorithm and analysis work for any mixture of bounded covariance distributions, the assumption of logconcaves still contribute to a more favorable margin condition. 2
Assumption 3 (Mixture of logconcaves). Consider Assumption 2, we say that DX is a mixture of logconcave distributions if ∀j ∈ [K], Dj is a logconcave distribution with mean µj and Σj ⪯ σ 2 Id . We state our main results below. We show that obtaining PAC gaurentee for learning of MLCs while tolerant to a constant fraction of nasty noise is possible under the margin condition and the mixture of bounded covariance distributions. More importantly, we show that such guarantees can be achieved with computational efficiency and a sample complexity of at most Õ(k 2 d). Theorem 3 (Main theorem, mixture of bounded covariance). Let C > 0 be some universal constant. 1 Suppose Assumption 2 holds with α ∈ [ 0.6 k , k ], and Assumption 1 hold with some γ > max(4τ, 4Cσ), q k where τ = 2σ · kϵ . By taking at least Ω(k 2 · (d log d + log ϵδ )) samples from EXnas with η ≤ 2121k2 , Algorithm 1 returns a ŵ in polynomial time such that errDX (ŵ) ≤ ϵ with probability at least 1 − δ. p The above theorem shows that as long as the clean samples are separable with a Ω σ · k/ϵ margin, it is robustly learnable even under the nasty noise condition in polynomial time. We show that if additionally, the marginal distribution satisfies a mixture of logconcave condition, similar guarantees can be achieved for a smaller γ = Ω(σ · (log k/ϵ + 1)). Theorem 4 (Main theorem, mixture of logconcaves). Let C > 0 be some universal constant. Suppose 1 Assumption 3 holds with α ∈ [ 0.6 k , k ] and Assumption 1 hold with some γ > max(4τ, 4Cσ), where k k τ = 2σ(log ϵ + 1). By taking at least Ω(k 2 · (d log d + log ϵδ )) samples from EXnas with η ≤ 2121k2 , Algorithm 1 returns a ŵ in polynomial time such that errDX (ŵ) ≤ ϵ with probability at least 1 − δ. Remark 5 (Tail bounds). It is well known that bounded covariance distributions have much heavier probability tail bounds comparing to logconcaves. It is surprising that our main theorems achieve exactly the same sample complexity under both conditions. That means the heavy tails do not make learning of MLCs harder under only the mixture of bounded covariances and margin conditions in terms of statistical and computational results. The major difference is on the margin parameter γ, which is assumed to be larger than the empirical cluster radius (τ ). This is intuitive, as any empirical set from a bounded covariance distribution naturally has a larger radius than that from a logconcave. Remark 6 (Non-uniform weight mixtures). Prior works studying similar settings assume the marginal distribution to be a uniformly weighted mixture of distributions. In our work, due to the implementation of a strong noise-tolerant clustering algorithm of [DKLP25], our algorithm is able to learn under non-uniformly weighted mixtures. However, since the weights also perform as an active upper bound on the noise rate, in our setting, the interesting regime is still constant weights. Remark 7 (Implication for k = 2). Even for the binary case, our algorithm and analysis are still stronger than all existing results. Until this work, it was unknown whether the conditions can be utilized to learn with a constant rate of nasty noise. This is because previous analysis essentially relies on the existence of a set of uncorrupted i.i.d. samples, which is possible under the malicious noise model ([She25]). In this work, we incorporate a much more powerful outlier-removal scheme such that even the clean samples are no longer i.i.d., we are still able to recover essential properties for robust learning.
1.2
Overview of techniques
Algorithmic design. Our algorithm builds on two main ideas for robustly learning multiclass linear classifiers: pruning the mixture distribution using clustering techniques, and applying hinge 3
loss minimization on the dataset obtained after pruning. Algorithm 1 begins with a hard pruning subroutine, i.e. Algorithm 2, that returns clusters Bj such that each cluster has bounded empirical covariance with its mean close to the true cluster means, and at most a small fraction of points are misassigned. It is worth noting that the algorithm finishes with a filtered Voronoi partition, such that each Bj returned by it would satisfy a bounded empirical covariance condition. Next, we perform a cluster-wise label based pruning scheme, detecting the majority label inside each cluster and removing any points with labels that differ from it. As each cluster has the same label for each data point inside it, this property is later exploited for controlling the dirty samples. We then apply hinge loss minimization and analyze the gradient contributions from clean and corrupted samples relative to the program optimums. We bound the contribution coming from corrupted samples by using the bounded empirical covariance condition guaranteed by the filtered Voronoi partition of Algorithm 2. Gradient and subgradient analysis for multiclass. The multiclass hinge loss function is a strict generalization of the binary hinge loss. However, when handling k > 2 classes, the case is much more complicated than its binary counterpart (see Eq. (3.2)). Intuitively, the dirty samples can not only drag the optimizer towards an opposite class, but any of the remaining k − 1 classes. As the hinge loss carefully selects a label for which the loss function is maximized, our analysis needs also to be adapted based on that and make sure the algorithm is robust on all directions. Sample complexity for generalized conditions. In this paper, we have adapted the previous analysis on mixture of logconcaves with covariance parameter σ = √1d to any σ, as long as the margin parameter is made compatible with it. Moreover, it was unknown whether the algorithmic robustness still holds under only the bounded second-order moment conditions instead of logconcave. We show that comparable results can be established for bounded covariance with slightly worse margins.
2
Related Work
Multiclass linear classification (MLC) is learning problem in machine learning [SB14] and has been studied extensively in the batch, online and bandit settings, both theoretically and empirically [PCST99, TB07, KST08, BPS+ 19]. MLC can be solved efficiently by linear programming or the multiclass Perceptron with sample complexity O(dk/ϵ) [SB14] in the noiseless realizable setting. The corresponding linear program can be solved efficiently in the Statistical Query (SQ) model [Kea98]. The sample complexity of MLC under RCN is bounded by min{Õ(dk/(σϵ)), Õ(dk/ϵ2 )} samples via empirical risk minimization, as derived from [MN06], where H is noise matrix and ζ := mini̸=j Hii − Hij indictates the identifiability of the noise model [RW18]. This setting is related to ours by viewing the inner product between the weight vector and instance being Hii . [WS24] studied extensions of margin-based surrogate loss functions from binary to multiclass learning, and proposed multiclass SVM with maximizing minimum margin in [NHW24]. Prior research studies multiclass linear classifier under Random Classification Noise (RCN) from a number of criteria [KST08, LA10, PRM+ 17, LWS18, RW18, BPS+ 19, FKKT21, ZLA21]. Even for k = 2 [DKPZ21, DKR23], recent hardness results indicate that obtaining OPT + ϵ may require upto dpoly(1/ϵ) time, while our distributional setting yields an error at most ϵ under a constant rate nasty noise tolerance. While SQ lower bounds demonstrates that optimal error learning under RCN require dΩ(k) time. [DMRT25] proved super polynomial SQ hardness for distribution free MLC under RCN even when k = 3, [DIKZ25] provided a fixed degree polynomial time learner under Gaussian marginals gaining O(OPT) + ϵ error for k ≥ 3. When taken as a whole, these findings support the assumption that are robust enough to enable for effective learning but weaker than Gaussian
4
structure. Since the seminal works of [WW99, CS01] multiclass support vector machines and hinge loss minimization have been researched; expansions include GenSVM [BG16] and convex outlier ablation integrated into large margin training [XCS06]. In binary case closest prior work is [Tal20] that first proved vanilla hinge loss minimization achieves Ω(γ) malicious noise tolerance and Ω(1) adversarial label noise tolerance, under large-margin and distributional assumptions on mixtures of log-concave distributions, with the key idea of controlling the gradient norm of the hinge loss results robustness. [ZS23] focuses on attribute-efficiency for polynomial threshold functions under nasty noise. [FCG21] extended to the agnostic setting and showed the multiplicative factors on the best achievable error rate depend on a soft-margin condition. [She25] recently achieved constant malicious noise tolerance via reweighted hinge loss building on [Tal20].[ZS25] shows that attribute-efficient learning of sparse halfspaces is possible at a constant rate of malicious noise. Among most of existing clustering method needs stronger structure or do not offer the necessary robustness. For example, [CW07] considers log-concave mixtures with a nonparametric EM but lacks finite sample guarantees under separation or adversarial noise contamination. Similarly, other works obtain polynomial-time clustering guarantees using higher moments, Sum-of-Squares methods, Poincaré-type assumptions, Gaussian structure or spectral decompositions [HL18, KSS18, LL22, VW02]. These approaches are powerful, but they make stronger assumptions than ours, or are not designed robustly for hinge loss learning under noisy model. The closest to our setting is [DKLP25] which gives robust guarantees for clustering mixtures of distributions with bounded-covariance under √ the separation condition ∥µi − µj ∥2 ≳ (σi + σj )/ α. To our study, no previous work provides provable constant noise tolerance for multiclass hinge loss minimization under nasty noise for k ≥ 3. Under the binary case, recently [She25] has obtained constant noise tolerance under malicious noise using reweighted hinge loss minimization using soft outlier removal technique building on [Tal20]. Our work is the first to extend hinge loss minimization with constant noise tolerance to the multiclass setting under nasty noise, combined with clustering of mixture models under bounded variance, large margin assumptions and log-concave distributions. In addition to that our work considers for both uniform and arbitrary weight mixtures whereas previous work for binary case provide gaurentees only for uniform weight mixtures [Tal20, She25].
3
Preliminaries
Hinge loss minimization for multiclass linear classifiers is a textbook algorithm. In the following, we revisit [SB14] and formally define our notations. We use [k] to denote the indexes {1, . . . , k}. Denote by ⟨u, v⟩ the inner produce between two vectors u, v. Recall that W is a k × d matrix and we use Wy to denote the y-th row of it. For the ease of presentation, we vectorize W to a vector w ∈ Rkd and perform a feature mapping Ψ : X × Y → Rkd for any instance-label pair (x, y), such that Wy , x can be written as w, Ψ(x, y) . We use Wy and wy interchangeably. Feature mapping and predictors. We employ a class-sensitive feature mapping Ψ : X × Y → Rkd that projects an instance-label pair (x, y) into a k × d-dimensional feature vector in the following manner. The ((y − 1)d +1)-th element to (yd)-th element of Ψ(x, y) is a copy of x; while all remaining elements are set to zeros. In other words, hw (x) = arg max w, Ψ(x, y) = arg max Wy , x = hW (x). y∈Y
(3.1)
y∈Y
In other words, the two presentations are equivalent. Generalized hinge loss. We employ the hinge loss function with an extension to the multiclass setting. That is, denote by 1(·) the indication function. The generalized hinge loss is ℓ(w; (x, y)) := 5
maxy′ ∈Y 1(y ̸= y ′ ) − w, Ψ(x, y) − Ψ(x, y ′ ) . Note that if k = 2 and let Ψ(x, y) = yx 2 , this gives a standard hinge loss function for the binary case. To fit the program the setting of the margin condition, we will use a scaled version of the hinge loss as follows ! w ′ ′ ℓγ (w; (x, y)) := max 1(y ̸= y ) − , Ψ(x, y) − Ψ(x, y ) . (3.2) y ′ ∈Y γ We further define the loss over a sample set S as ℓγ (w; S) :=
X (x,y)∈S
max 1(y ̸= y ′ ) − ′ y ∈Y
! w , Ψ(x, y) − Ψ(x, y ′ ) . γ
(3.3)
We omit the subscript γ when it is clear in the context. The robustness of our algorithm essentially comes that the instances from one class lie close to each other, forming a region termed the dense pancake, which is defined as follows. Note that this definition is significantly changed from its prior works. Definition 8 (Multiclass pancake). Let (x, y) ∈ X × Y. Given a unit vector w ∈ Rkd and a parameter τ > 0, the multiclass pancake Pwτ (x, y) is defined as a set n o Pwτ (x, y) := (x′ , y ′ ) ∈ X × Y : y ′ = y ∧ ∀ȳ ∈ Y, wȳ , x′ − x ≤ τ . (3.4) We say that the pancake Pwτ (x, y) is ρ-dense with respect to a distribution D on X × Y if Pr(x′ ,y′ )∼D (x′ , y ′ ) ∈ Pwτ (x, y) ≥ ρ.
(3.5)
Let D1 , D2 be two distributions on X × Y. We say that the pair (D1 , D2 ) satisfies the (τ, ρ, β)-dense pancake condition if for any unit vector w ∈ Rkd , Pr(x,y)∼D2 Pwτ (x, y) is ρ-dense w.r.t. D1 ≥ 1 − β. (3.6) For the ease of presentation, we alternatively say that D1 satisfies (τ, ρ, β)-dense pancake condition with respect to D2 . Instead of measuring the density w.r.t. one direction, we require the pancake to be dense w.r.t. k different directions. Each direction wȳ is the weight vector for one class. In principle, all weight vectors in W ∗ should be quite different from each other, as otherwise the two classes can be seemed as one. Note that this is different from Eq. (3.6) that requires the density condition to hold for all w ∈ Bkd . This is because Eq. (3.6) measures not only one pancake, but any random pancake with respect to (x, y) drawn from D2 . Also note that, the sample complexity for achieve this multiclass pancake condition under the margin and mixture of distributions assumptions has changed. As a result, we have Theorem 17. Additional notations. We use µS and σS to denote the empirical mean and the empirical standard deviation of a set S. We slightly abuse the notation and use (x, y) ∼ S to denote drawing a sample uniformly at random from a set S. In this sense, S may also denote the uniform distribution on its elements. We denote by (DX , w∗ ) a distribution over X × Y where the instances are drawn from DX and then labeled by w∗ .
6
4
Algorithm
Our main algorithm consists of two subroutines. The first one is a cluster-based pruning algorithm that utilizes the mixture clustering techniques based on bounded covariance conditions with optimal separation [DKLP25]. The second ingredient is a standard multiclass hinge loss minimization over the pruned sample set. Due to the introduction of feature mapping Ψ, the program is a strict yx generalization of its binary counterpart, i.e. when Ψ(y, x) = 2 , ℓγ (w; (x, y)) = max 0, 1 − wγ · yx . Algorithm 1 Multiclass SVM Require: Training set S = {(x1 , y1 ), . . . , (xn , yn )} ⊆ X ×Y, parameter α ∈ (0, 1), margin parameter γ > 0, feature mapping Ψ : X × Y → Rdk . Ensure: A multiclass linear classifier hw . 1: {Bj ′ }j ′ ∈[m] ← Algorithm 2(S, α). 2: ∀j ′ ∈ [m], Bj′ ′ ← {(x, y) ∈ Bj ′ : y = maj(Bj ′ )}. 3: For j ∈ [k], let Bj = {(x, y) ∈ ∪j ′ ∈[m] Bj ′ : y = j}. b = ∪j∈[k] Bj . 4: Let S 5: Solve: D E X ′ ′ w min max 1(y = ̸ y ) − , Ψ(x , y ) − Ψ(x , y ) . (4.1) i i i i γ ′ w∈Rdk :∥w∥2 ≤1
y ∈Y
b (xi ,yi )∈S
6: Return hw (x) = argmaxy∈Y ⟨w, Ψ(x, y)⟩.
We first introduce the cluster-based pruning subroutine. We include it in Algorithm 2 for easy references. It performs robust clustering under the strong contamination model [DKLP25], which can be thought of as equivalent to the nasty noise model from the feature corruption point of view.
7
Algorithm 2 Clustering (Algorithm 1 of [DKLP25]) Require: Sample set S = {(xi , yi )}ni=1 , parameter α ∈ (0, 1). Ensure: Disjoint subsets Bj of S. 1: Generate a list Lstdev of candidate standard deviations. 2: Apply list-decodable mean estimation to {xi } for each σ̂ ∈ Lstdev and generate a list of candidate means Lmean . 3: Initialise L ← ∅. 4: For every s ∈ Lstdev in increasing order: (a) For every µ ∈ Lmean : √ (i) If ∥µ − µ̂∥2 > 99C σ̂/ α for all µ̂ ∈ L, decide the following convex feasibility program find qi ∈ [0, 1], i ∈ [n], n X s.t. qi (xi − µ)(xi − µ)⊤ i=1
n
(1/α)
≤
2C 2 σ̂ 2 X qi , α i=1
n X
qi ≥ 0.97αn.
i=1
(ii) If feasible, add µ to L. 5: Apply size-based pruning: iteratively remove any µ̂ ∈ L whose Voronoi cell in S has fewer than
0.96αn points, and recompute the partition after each removal. 6: Apply distance-based pruning: iteratively find any pair (µ̂j , µ̂j ′ ) in L whose filtered Voronoi √ means satisfy ∥µBj − µBj ′ ∥2 ≤ 4761C(σBj + σBj ′ )/ α and remove the less isolated one. 7: Let L′′ be the remaining candidate list. Compute the filtered Voronoi partition {B1 , . . . , Bj } ← FilteredVoronoi(L′′ , S) using Algorithm 3 of [DKLP25]. 8: return {Bj }. Let Sj be the samples whose instance is drawn from mixture component Dj . Algorithm 2 ensures that each component Sj is found except for a small portion. That is, the guarantees of Algorithm 2 from [DKLP25] ensures that there exists a union of elements in {Bj } that forms a set of samples Bj which include most of the elements of Sj . That makes Step 1 of Algorithm 1 favorable. Following that, in Algorithm 1, we then utilize the label information to identify each set Bj and remove potential outliers, i.e. the samples whose label disagrees with its neighbors. Step 2 ensures to fully exploit the information of uncorrupted samples that form large clusters. After that, taking union of subsets with agreeing labels (Step 3) helps to identify each Bj . In fact, we show that as long as the noise rate is carefully controlled, this step always returns correct clusters. After these steps, the boundary between clusters Bj becomes extremely clear, which benefits the effeciency and effectiveness of the subsequent hinge loss minimizatin program.
5
Analysis
Here we discuss the analysis of Algorithms 1. Our analysis is divided into three parts: (i) pointwise gradient analysis 5.1, (ii) analysis of Algorithm 5.2, and (iii) sample complexity 5.3. We first show the analysis for pointwise gradient, and then we show the analysis for Algorithm 1 and Algorithm 2, followed by the analysis of sample complexity to hold the dense pancake condition.
8
5.1
Pointwise Gradient Analysis
We start from the pointwise analysis for the gradient of hinge loss function. On a given point (x, y), if the pancake centered at it with width τ w.r.t. ŵ is ρ-dense, then any point in this pancake will contribute to a gradient that draws ŵ to w∗ . When this gradient is non-negligible, then ŵ cannot be the optimum. As a result, we use this fact to construct a contradiction and show that any optimum ŵ should correctly classify any significant point (x, y), i.e. whose pancake Pŵτ (x, y) is enough dense. This proof idea is similar to our prior works [Tal20, She25]. However, when considering the multiclass setting, the extension is not trivial. Recall that the margin condition for the multiclass case takes care of all (k − 1) classes other than the true class to which the instance belongs. Similarly, the dense pancake condition ensures that the instances lie close to each other not only in one direction, but in k different directions at the same time. These new conditions drastically change the analysis. Specifically, the following lemmas show that if (x, y) is misclassified by ŵ, then projecting any subgradient g ∈ ∂w ℓ(w; S) |w=ŵ onto some specific directions would give us quantities with large magnitudes, showing that the subgradients are significant. Let Ŝ = ŜC ∪ ŜD and define SP := ŜC ∩ Pŵτ (x, y). Lemma 9 (Gradient bound on w∗ direction). Let ŵ be an optimum returned by Eq.(4.1) in Algorithm 1. Suppose Assumption 1 holds with parameter γ. Assume that sample (x, y) is misclassified by ŵ. Consider pancake Pŵτ (x, y) with τ < γ/4, then √ 2Cσn η ∗ g, w ≤ −|SP | + , (5.1) γ Lemma 10 (Gradient bound on orthogonal direction). Let ŵ be an optimum returned by Eq.(4.1) ∗ −κŵ in Algorithm 1. Define w′ := w√1−κ , where κ := ⟨ŵ, w∗ ⟩, and assume that θ(ŵ, w∗ ) ∈ (0, π/2). 2 Suppose Assumption 1 holds with parameter γ. Assume that sample (x, y) is misclassified by ŵ. √ 2Cσn η |SP | τ Consider pancake Pŵ (x, y) with τ < γ/4, if 4 > , then γ √ g, w
′
≤−
5 |SP |. 4
(5.2)
√ 2Cσn η
It is easy to see that it is sufficient to choose |S4P | > for both Eq. (5.1) and (5.2) to be γ strictly less than 0. On the contrary, we utilize the KKT condition and prove that there always exists some g that make ⟨g, w∗ ⟩ or g, w′ equal to 0 depending on the optimality of ŵ, leading to a contradiction. Hence, (x, y) must be correctly classified by ŵ. We summarize in the following lemma. Lemma 11. Suppose Assumption 1 holds with parameter γ. Let (x, y) ∈ X × Y be a sample point. If √ 8Cσn η |SP | > , (5.3) γ then (x, y) is not misclassified by ŵ.
5.2
Analysis of Algorithms
In this section we show the detailed analysis of Algorithm 1 and Algorithm 2. Let Sj ⊆ S represent clean samples in S selected from the j-th component of DX and labeled by w∗ and let SC = ∪j∈[k] Sj . Similarly, Sˆj ⊆ Ŝ denotes the remaining clean samples after Step 4 of Algorithm 1. It is easy to see that ŜC = ∪j∈[k] Ŝj . 9
With a large enough sample size, the clean samples SC in S satisfy the dense pancake condition (Definition 8). However, under the nasty noise condition, the adversary is allowed to inspect and replace up to an η fraction of the samples. The following proposition shows that the dense pancake structure is preserved after the cluster-based pruning step. Proposition 12 (Empirical dense pancake). Consider Algorithm 1. Suppose that all j ∈ [k], the k component Sj is found by Algorithm 2. Let S be a set of samples of size at least Ω(k 2 · (d log d + ϵδ )) 3α ∗ from EXnas , then with probability at least 1 − δ, the set Ŝ is (τ, 20 , ϵ)-dense with respect to (DX , w ) 3α with appropriate τ ∈ (0, γ4 ). In addition, |Ŝ| ≥ |S| 2 and the 20 -density is contributed by ŜC . That is, we utilize results from [DKLP25] for Algorithm 2, where the clean samples are retained while dirty samples are removed with high probability. That means, if SC is (τ, ρ, ϵ)-dense, with high probability, after Step 1, ŜC is (τ, ρ′ , ϵ)-dense with a slightly smaller ρ′ . The analysis for this proposition includes some details in the proof for sample complexity in Section 5.3. In addition, Proposition 12 works for both the mixture of logconcaves and the mixture of bounded covariance. Specifically, we assume that DX is a mixture of logconcaves with pancake width τ = 2σ · (log kϵ + 1), or a mixture of bounded covariance distributions with pancake width q τ = 2σ · kϵ . By Theorem 15 (or 16 for bounded covariance), for each j ∈ [k], Sj is (τ, 1−ϵ 2 , ϵ)-dense ∗ with respect to (Dj , w ) and we ensure the sample size |S| is sufficiently large to satisfy the conditions for Algorithm 2 to perform effectively. As a result, the pruning algorithm ensures that for each Sj , a large quantity of clean samples is returned in Bj , leading to a dense pancake condition with ρ′ ≥ 3α 20 . 3α ∗ As a result, we have that Ŝ is (τ, 20 , ϵ)-dense with respect to (DX , w ). The detailed proof can be seen in Appendix B. It remains to derive the noise condition under which the dense pancake condition is preserved and the label information in each sub-cluster Bj ′ is effective for identifying to which Bj it belongs to. The following theorem shows that if Ŝ satisfies the dense pancake property (Proposition 12), then the error rate for the classifier ŵ returned by Program (4.1) is at most ϵ. Theorem 13 (Noise rate condition). Consider Algorithm 1 and its returned ŵ. Suppose Assumption 1 holds with some γ > 0 and Assumption2 holds with σ. Assume that γ4 > max(τ, Cσ) and η ≤ 2121k2 . γ 0.6 1 ∗ If set Ŝ is (τ, 3α 20 , ϵ)-dense with respect to (DX , w ) with appropriate τ ∈ (0, 4 ) for some α ∈ [ k , k ], |S| the 3α 20 -density is contributed by ŜC , and |Ŝ| ≥ 2 , then errDX (ŵ) ≤ ϵ. Using the result of Proposition 12, we first compute the density contributed by ŜC ≥ 3α 40 n. Together with the condition established by the pointwise gradient analysis (Lemma 11), when Assumption 1 holds with some γ > 0 and Assumption 2 holds with σ, then errDX (ŵ) ≤ ϵ is returned by Algorithm 1. We include the computational complexity for Algorithm 1 in the following lemma. It shows that the algorithm runs in polynomial time. For more details, see Appendix B. Lemma 14 (Polynomial runtime of Algorithm 1). Algorithm 1 runs in polynomial time. More 1 precisely, the total runtime is poly n, d, K, α . For completeness, we restate the main theorem. By Proposition 12 and Theorem 13, we show that the classifier ŵ returned by Algorithm 1 has error at most ϵ, with probability at least 1 − δ, k when it is given a sample of size Ω k 2 · (d log d + log ϵδ ) from EXnas .
10
5.3
Sample Complexity
In this section, we give the sample complexity for obtaining dense pancake conditions for both the mixture of logconcave distributions and that of the bounded covariance distributions. Below is the analysis of sample complexity of a single log-concave distribution and a single bounded covariance distribution. For more detailed analysis, see Appendix D. Theorem 15 (Sample complexity for a single log-concave distribution). Suppose that Assumption 1 is satisfied with parameter γ. Ifdistribution Dj is logconcave with mean µj and covariance Σj ⪯ 1 1 1 σId , then a set Sj of at least Ω 1−kβ · d log d + log kβ + log δ samples from (Dj , w∗ ) satisfies γ 1 ∗ (τ, 1−kβ 2 , kβ)-dense pancake condition with respect to (Dj , w ), for some τ = 2σ(log β + 1) ≤ 2 .
Theorem 16 (Sample complexity for a single bounded covariance distribution). Suppose that Assumption 1 is satisfied with parameter with mean µj and covariance γ. If Dj is a distribution 1 Σj ⪯ σId , then a set Sj of at least Ω ρ1 · d log d + log kβ + log 1δ samples from (Dj , w∗ ) satisfies γ ∗ √1 (τ, 1−kβ 2 , kβ)-dense pancake condition with respect to (Dj , w ), for some τ = 2σ · β ≤ 2 .
Observing that τ = 2σ(log β1 + 1) grows logarithmically in 1/β for the log-concave case, while √ under the bounded covariance, τ = 2σ/ β depends polynomially on 1/β. Hence, the width is much larger for mixture of bounded covariance distributions (especially for extremely small β), which makes the margin condition weaker since it forces to τ ≤ γ/2. However, it is worth noting that the sample complexity for both cases is the same. As a result, our result on the sample complexity for empirical dense pancakes shows that it is independent of the standard deviation σ or the tail bound. Conditioned on the above sample complexity for a single distribution component, we are able to obtain the total sample complexity by utilizing Theorem 17. We simply sum up the per cluster density to set S since each subset Sj , meets the dense pancake condition with respect to (Dj , w∗ ), and αρ the fact that each cluster weight qj ≥ α implies |Sj | ≥ α|S| 2 . As a result, S meets the (τ, 2 , β)-dense pancake condition with respect to the mixture (DX , w∗ ). Theorem 17 (Sample complexity for mixtures). Suppose that Assumption 2 is satisfied. If ∀j ∈ [K], a sample Sj of size |Sj | ≥ nj samples from (Dj , w∗ ) satisfies (τ, ρ, β)-dense P pancake condition with K 1 K ∗ respect to (Dj , w ), then by drawing a set S of size Ω samples from (DX , w∗ ) j=1 nj + α log δ ∗ satisfies (τ, αρ 2 , β)-dense pancake condition with respect to (DX , w ).
This shows that only with a small overhead in the sample complexity, the dense pancake is stable under the mixture of distributions. That is, when each component distribution has a weight qi lower bounded by α, the density is only reduced by a multiplicative factor of α/2.
6
Conclusion and Limitations
In this paper, we revisit the problem of learning multiclass linear classifiers and study the PAC guarantees under the nasty noise condition. We show that under both the mixture of bounded covariances and margin conditions, it is possible to design robust algorithms that are tolerant to a constant rate of nasty noise. Consider that under other well studied noise models, such as malicious noise, adversarial label noise, or random classification noise, the adversary is more restricted. Hence, it is natural that our algorithm and analysis can be adapted to more noisy settings.
11
In our analysis, the Euclidean norm of the sum of centered data points in SD is bounded by a term √ proportional to Cσn η. Because of this square-root dependence instead of the linear dependence on η, the noise tolerance becomes weaker, changing from order O(1/k) to O(1/k 2 ). Though this still gives a constant noise-rate bound, removing this dependence can significantly strengthen the robustness of the algorithm. This loss is one of the main limitations of second-order methods, and whether a bound of 1/k for malicious and nasty noise is achievable is still an open problem.
12
References [ABL17]
Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. J. ACM, 63:50:1–50:27, 2017. 2
[BFKV98] Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22:35–52, 1998. 1 [BG16]
Gerrit J.J. Van Den Burg and Patrick J.F. Groenen. Gensvm: A generalized multiclass support vector machine. Journal of Machine Learning Research, 17(224):1–42, 2016. 5
[BPS+ 19] Alina Beygelzimer, Dávid Pál, Balázs Szörényi, Devanathan Thiruvenkatachari, Chen-Yu Wei, and Chicheng Zhang. Bandit multiclass linear classification: Efficient algorithms for the separable case. In Proceedings of the 36th International Conference on Machine Learning, 2019. 4 [BV04]
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. 24
[CS01]
Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2:265–292, 2001. 5
[CW07]
George Chang and Guenther Walther. Custering with mixtures of log-concave distributions. Computational Statistics and Data Analysis, 2007. 5
[DIKZ25]
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, and Nikos Zarifis. Robust learning of multi-index models via iterative subspace approximation. In 66th Annual Symposium on Foundations of Computer Science, 2025. 2, 4
[DKLP25] Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, and Thanasis Pittas. Clustering mixtures of bounded covariance distributions under optimal separation. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025. 3, 5, 7, 8, 10, 24, 25 [DKPZ21] Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. The optimality of polynomial regression for agnostic learning under Gaussian marginals in the SQ model. In Proceedings of the 34th annual conference on Learning Theory, 2021. 4 [DKR23]
Ilias Diakonikolas, Daniel Kane, and Lisheng Ren. Near-optimal cryptographic hardness of agnostically learning halfspaces and ReLU regression under Gaussian marginals. In Proceedings of the 40th International Conference on Machine Learning, 2023. 4
[DMRT25] Ilias Diakonikolas, Mingchen Ma, Lisheng Ren, and Christos Tzamos. Statistical query hardness of multiclass linear classification with random classification noise. In Proceedings of the 42nd International Conference on Machine Learning, 2025. 1, 4 [FCG21]
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of halfspaces with gradient descent via soft margins. In Proceedings of the 38th International Conference on Machine Learning, 2021. 5
[FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Efficient algorithms for learning from coarse labels. In Proceedings of the 34th annual conference on Learning Theory, 2021. 4 13
[HL18]
Samuel B. Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018. 5
[Kea98]
Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45:983–1006, 1998. 4
[KL88]
Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 267– 280, 1988. 1
[KSS18]
Pravesh K. Kothari, Jacob Steinhardt, and David Steurer. Robust moment estimation and improved clustering via sum of squares. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035–1046. ACM, 2018. 5
[KST08]
Sham M. Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In Proceedings of the 25th International Conference on Machine Learning, 2008. 4
[LA10]
Philip M. Long and Rocco A. Random classification noise defeats all convex potential boosters. Mach. Learn., 78(3):287–304, 2010. 4
[LL22]
Allen Liu and Jerry Li. Clustering mixtures with almost optimal separation in polynomial time. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022. 5
[LWS18]
Zachary C. Lipton, Yu-Xiang Wang, and Alexander J. Smola. Detecting and correcting for label shift with black box predictors. In Proceedings of the 37th International Conference on Machine Learning, 2018. 4
[MN06]
Pascal Massart and Elodie Nedelec. Risk bounds for statistical learning. Annals of Statistics, 34:0090–5364, 2006. 4
[NHW24]
Feiping Nie, Zhezheng Hao, and Rong Wang. Multi-class support vector machine with maximizing minimum margin. In Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence, 2024. 4
[PCST99] John Platt, Nello Cristianini, and John Shawe-Taylor. Large margin dags for multiclass classification. In Proceedings of the 13th International Conference on Information Processing Systems, 1999. 4 [PRM+ 17] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Conference on Computer Vision and Pattern Recognition, 2017. 4 [RW18]
Brendan Van Rooyen and Robert C. Williamson. A theory of learning with corrupted labels. Journal of Machine Learning Research, 18(228):1–50, 2018. 4
[SB14]
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. 4, 5 14
[She25]
Jie Shen. Efficient PAC learning of halfspaces with constant malicious noise rate. In Proceedings of The 36th International Conference on Algorithmic Learning Theory. PMLR, 2025. 1, 2, 3, 5, 9, 16, 21
[Tal20]
Kunal Talwar. On the error resistance of hinge-loss minimization. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2020. 1, 2, 5, 9, 16, 25, 27
[TB07]
Ambuj Tewari and Peter L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8:1007–1025, 2007. 4
[VW02]
Santosh Vempala and Grant Wang. A spectral algorithm for learning mixtures of distributions. In 43rd Symposium on Foundations of Computer Science, 2002. 5
[WS24]
Yutong Wang and Clayton Scott. Unified binary and multiclass margin-based classification. Journal of Machine Learning Research, 25(143):1–51, 2024. 4
[WW99]
Jason Weston and Chris Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the 7th European Symposium on Artificial Neural Networks, 1999. 5
[XCS06]
Linli Xu, Koby Crammer, and Dale Schuurmans. Robust support vector machine training via convex outlier ablation. In AAAI, 2006. 5
[ZLA21]
Mingyuan Zhang, Jane H. Lee, and Shivani Agarwal. Learning from noisy labels with no change to the training process. In Proceedings of the 38th International Conference on Machine Learning, 2021. 4
[ZS23]
Shiwei Zeng and Jie Shen. Attribute-efficient PAC learning of low-degree polynomial threshold functions with nasty noise. In Proceedings of the 48th International Conference on Machine Learning, Proceedings Machine Learning Research, 2023. 5
[ZS25]
Shiwei Zeng and Jie Shen. Attribute-efficient PAC learning of sparse halfspaces with constant malicious noise rate. CoRR, abs/2505.21430, 2025. 5
15
A
Pointwise Gradient Analysis
Recall that the feature map Ψ : X × Y → Rkd has the y-th block equal to x and all others zero, i.e. w, Ψ(x, y) = wy , x . The multiclass hinge loss is ′ ′ 1 ℓ(w; xi , yi ) = max 1(y = ̸ y ) − w, Ψ(x , y ) − Ψ(x , y ) . (A.1) i i i i γ ′ y ∈Y
At the optimum ŵ, the subgradient of ℓ w.r.t. w is γ1 Ψ(xi , ŷi ) − Ψ(xi , yi ) , where we define a sudo-label for any i ŷi := arg max 1(yi′ ̸= yi ) − γ1 ŵ, Ψ(xi , yi ) − Ψ(xi , yi′ ) , (A.2) yi′ ∈Y
which is used in the optimization process. Therefore, taking subgradient of the ℓ(w; Ŝ) with respect to w yields X 1X g = ∂w ℓ(w; xi , yi ) = Ψ(xi , ŷi ) − Ψ(xi , yi ) . (A.3) γ w=ŵ i∈Ŝ
i∈Ŝ
In our proof, we will frequently discuss the inner product ⟨g, w⟩ =
1X 1X w, Ψ(x, y) − Ψ(x, y ′ ) = wy − w y ′ , x , γ γ i∈Ŝ
(A.4)
i∈Ŝ
which will be used interchangeably. Recall that for any set Ŝ, we can view it as a union of a subset of the clean samples and that of the dirty samples, i.e. Ŝ = ŜC ∪ ŜD . To perform pointwise gradient analysis, for any (x, y), we further partition the sample set Ŝ into three subsets Ŝ = SP ∪ SO ∪ SD . That is, given any point (x, y) and its pancake Pŵτ (x, y) := {(x′ , y ′ ) ∈ X × Y : ŵ, Ψ(x′ , y ′ ) − ŵ, Ψ(x, y) ≤ τ, y ′ = y}, define SP := ŜC ∩ Pŵτ (x, y),
SO := ŜC \ Pŵτ (x, y),
SD := ŜD .
(A.5)
Based on this partition, we can also split the total gradient into three parts, i.e. g = g1 + g2 + g3 , where 1 X g1 = Ψ(xi , ŷi ) − Ψ(xi , yi ) , γ i∈SP 1 X g2 = Ψ(xi , ŷi ) − Ψ(xi , yi ) , γ i∈SO 1 X g3 = Ψ(xi , ŷi ) − Ψ(xi , yi ) . γ i∈SD
Similar to our prior works, we will prove the robustness of the minimization program and its returned optimum ŵ using contradictions [Tal20, She25]. That is, assume an instance-label pair (x, y) is misclassified by ŵ, if (x, y) has a large amount of clean sample lying close to it, we are able to show that ŵ must not be the optimum. We include some proofs from the prior works if there are significant changes, and omit those which we can reuse. We remark that the structure of the proof might be similar to prior works, but many details for the multiclass learning setting (including the new pruning subroutine) can not be naively extended from the binary setting. 16
Lemma 18 (Restatement of gradient bound on w∗ direction). Let ŵ be an optimum returned by Eq.(4.1) in Algorithm 1. Suppose Assumption 1 holds with parameter γ. Assume that sample (x, y) is misclassified by ŵ. Consider pancake Pŵτ (x, y) with τ < γ/4 and define subsets as in Eq. (A.5), then √ 2Cσn η ∗ g, w ≤ −|SP | + , (A.6) γ Proof. We bound ⟨g1 , w∗ ⟩, ⟨g2 , w∗ ⟩, and ⟨g3 , w∗ ⟩ individually, and then combine the bounds. Part 1: ⟨g1 , w∗ ⟩ ≤ −|SP |. The term g1 sums the subgradients of the pancake clean samples SP : g1 , w∗ =
E 1 XD ∗ wŷi − wy∗i , xi . γ
(A.7)
i∈SP
For each i ∈ SP , we have that yi = y. Since (x, y) is misclassified, we have that y = ̸ y′ ← arg maxy′ ∈Y ŵy′ · x. In addition, due to the dense pancake condition (Definition 8) that for any ȳ, ŵ, Ψ(xi , ȳ) − Ψ(x, ȳ) ′ yi such that
≤ τ , we can show that ŷi ̸= yi for all i ∈ SP . In more details, there exists 1(yi′ ̸= yi ) − γ1 ŵ, Ψ(xi , yi ) − Ψ(xi , yi′ ) > 0,
and thus yi ̸= ŷi . It suffies to let yi′ = yi and show ŵ, Ψ(xi , yi ) − Ψ(xi , y ′ ) < γ. The above inequality holds because ŵ, Ψ(xi , yi ) − Ψ(xi , y ′ ) = ŵ, Ψ(xi , yi ) − Ψ(x, y) + Ψ(x, y) − ŵ, Ψ(xi , y ′ ) − Ψ(x, y ′ ) + Ψ(x, y ′ ) < ŵ, Ψ(xi , yi ) − Ψ(x, y) − ŵ, Ψ(xi , y ′ ) − Ψ(x, y ′ ) ≤ 2τ < γ,
(A.8)
− Ψ(x, y ′ ) < 0. Hence, we know that yˆi where the second transition is due to that D ŵ, Ψ(x, y) E
and yi are different. By Assumption 1, wy∗i − wŷ∗i , xi ≥ γ for any i ∈ ŜC , so each summand D E wŷ∗i − wy∗i , xi ≤ −γ. Summing over SP gives ⟨g1 , w∗ ⟩ ≤ −|SP |. Part 2: ⟨g2 , w∗ ⟩ ≤ 0. The term g2 sums the subgradients of the off-pancake clean samples: g2 , w∗ =
E 1 XD ∗ wŷi − wy∗i , xi . γ
(A.9)
i∈SO
D E For any i ∈ SO ⊆ ŜC , Assumption 1 again gives wŷ∗i − wy∗i , xi ≤ −γ for yˆi ̸= yi . However, as it is unknown whether yˆi = yi , each summand is ≤ 0. Therefore ⟨g2 , w∗ ⟩ ≤ 0 . √ Part 3: ⟨g3 , w∗ ⟩ ≤ −|SD | + η · Cσn. The term g3 sums the subgradients of the surviving dirty samples: E 1 XD ∗ g3 , w∗ = wŷi − wy∗i , xi . (A.10) γ i∈SD
For each i ∈ SD , write xi = µj + (xi − µj ) where µj is the true mean of the cluster Bj containing xi . Due to Step 2, (xi , yi ) should agree with (µj , yj ) where yj = maj(Bj ). Since each Bj is of significant
17
size 0.92αn, yj must agree with hw∗ (µj ). This gives E E XD E XD XD wŷ∗i − wy∗i , xi = wŷ∗i − wy∗i , µj + wŷ∗i − wy∗i , xi − µj i∈SD
i∈SD
=
(A.11)
i∈SD
XD
E XD E wŷ∗i − wy∗j , µj + wŷ∗i − wy∗i , xi − µj
i∈SD
(A.12)
i∈SD
X
≤ −γ|SD | + 2
(xi − µj ) .
(A.13)
i∈SD
where the second transition is due to that ∀i, wŷ∗i − wy∗i
2
≤ 2 since wy∗
2
≤ 1 from ∥w∗ ∥2 ≤ 1. To
bound the second term, we note that by applying the Step 7 (Filtered Voronoi), each return cluster Bj has bounded empirical covariance (Theorem 26). That is, 1 X (x − µj )(x − µj )⊤ ⪯ C 2 σ 2 Id . |Bj | x∈Bj
P P Then, we have that for any unit vector v ∈ Rd , i∈SD ∩Bj ((xi − µj ) · v)2 ≤ i∈Bj ((xi − µj ) · v)2 = P P v ⊤ i∈Bj (xi −µj )(xi −µj )⊤ v ≤ C 2 σ 2 |Bj |. As a result, i∈SD ((xi −µj )·v)2 ≤ C 2 σ 2 |Ŝ| (Theorem 26). Therefore, we can bound X i∈SD
xi − µ j ≤
X
max
v∈Rd ,∥v∥≤1
(xi − µj ) · v
i∈SD
s p ≤ |SD | ·
max
v∈Rd ,∥v∥≤1
X
((xi − µj ) · v)2
i∈SD
q √ ≤ ηn · Cσ |Ŝ| √ ≤ η · Cσn, where the second transition is due to Cauchy-Schwarz. As a result, we have that g3 , w∗ ≤ −|SD | +
2 √ · η · Cσn. γ
(A.14)
Combining. Adding the three parts and dropping the non-positive term −|SD |: g, w∗ = g1 , w∗ + g2 , w∗ + g3 , w∗ ≤ −|SP | +
2 √ · η · Cσn γ
(A.15)
which yields (5.1). Lemma 19 (Restatement of gradient bound on orthogonal w′ direction). Let ŵ be an optimum ∗ −κŵ returned by Eq.(4.1) in Algorithm 1. Define w′ := w√1−κ , where κ := ⟨ŵ, w∗ ⟩, and assume that 2 θ(ŵ, w∗ ) ∈ (0, π/2). Suppose Assumption 1 holds with parameter γ. Assume that sample (x, y) is misclassified√by ŵ. Consider pancake Pŵτ (x, y) with τ < γ/4 and define subsets as in Eq. (A.5), if 2Cσn η |SP | , then 4 > γ √ 5 ′ g, w ≤ − |SP |. (A.16) 4 18
Proof. We again bound each of g1 , w′ , g2 , w′ , g3 , w′ in turn. Now we consider the case used in the orthogonal-direction argument, θ(ŵ, w∗ ) ∈ (0, π/2). Since both ŵ and w∗ are normalized, we have ⟨ŵ, w∗ ⟩ = ∥ŵ∥2 ∥w∗ ∥2 cos θ(ŵ, w∗ ) = cos θ(ŵ, w∗ ). Because θ(ŵ, w∗ ) ∈ (0, π/2), it follows that 0 < cos θ(ŵ, w∗ ) < 1. Therefore, 0 < ⟨ŵ, w∗ ⟩ < 1. 1 Part 1: g1 , w′ ≤ − |SP |. The term g1 sums over the pancake clean samples SP : g1 , w′ = 2E D √ 1 P ′ − w ′ , x . For each i ∈ S , expanding w ′ = (w ∗ − κŵ)/ 1 − κ2 gives w i P yi i∈SP ŷi γ D
E wy∗i − wŷ∗i , xi − κ ŵyi − ŵŷi , xi √ . (A.17) wy′ i − wŷ′ i , xi = 1 − κ2 D E By Assumption 1 and the analysis in Lemma 9, yi ̸= ŷi and wy∗i − wŷ∗i , xi ≥ γ. Since ŷi is the active maximizer of the hinge loss ℓ(ŵ, xi , yi ), according to Eq. (A.8), we have that D
E
ŵ, Ψ(xi , yi ) − Ψ(xi , ŷi ) ≤ ŵ, Ψ(xi , yi ) − Ψ(xi , y ′ ) ≤ 2τ ≤
γ . 2
D E √ √ where y ′ is as defined in Eq. (A.8). Therefore, wy′ i − wŷ′ i , xi ≥ γ−κγ/2 = (1−κ/2)γ . Equivalently, 2 1−κ 1−κ2 D E (1−κ/2)γ wŷ′ i − wy′ i , xi ≤ − √1−κ2 . Summing over SP gives 1 1 − κ/2 |SP | ≤ − |SP |. g1 , w′ ≤ − √ 2 1 − κ2
(A.18)
Since optimizing over 0 < κ < 1 gives √ 1 − κ/2 3 1 √ ≥ ≥ . 2 2 1 − κ2
(A.19)
Part 2: g2 , w′ ≤ 0. The term g2 sums the subgradients of the off-pancake clean samples: g2 , w′ =
E 1 XD ′ wŷi − wy′ i , xi . γ
(A.20)
i∈SO
For any i ∈ SO ⊆ ŜC , we consider two cases. If ŷi = yi , then the active hinge label agrees with the true label, so this sample contributes 0 to g2 . If ŷi ̸= yi , then since ŷi is the hinge-active label and the hinge loss is normalized by 1/γ, we have 1 − γ1 ŵyi − ŵŷi , xi ≥ 0, and hence ŵyi − ŵŷi , xi ≤ γ. √ Using w′ = (w∗ − κŵ)/ 1 − κ2 , we get D E D E wy∗i − wŷ∗i , xi − κ ŵyi − ŵŷi , xi γ − κγ √ wy′ i − wŷ′ i , xi = ≥√ > 0. (A.21) 1 − κ2 1 − κ2 D E Therefore wŷ′ i − wy′ i , xi < 0. Thus, if ŷi = yi , the summand is 0, and if ŷi ̸= yi , the summand is negative. Hence each summand is ≤ 0, giving g2 , w′ ≤ 0. Part 3: g3 , w′ ≤ − 21 |SD | +
√ Cσn η . The term g3 sums over the surviving dirty samples: γ
g3 , w′ =
E 1 XD ′ wŷi − wy′ i , xi . γ i∈SD
19
(A.22)
∗
−κŵ , we have Using w′ = w√1−κ 2
g3 , w
′
E X D 1 ∗ ∗ = √ wŷi − wyi , xi − κ ŵŷi − ŵyi , xi . γ 1 − κ2 i∈S
(A.23)
D
For each i ∈ SD , write xi = µj + (xi − µj ), where µj is the true mean of the cluster Bj containing xi . Due to Step 2, (xi , yi ) agrees with (µj , yj ), where yj = maj(Bj ). Since each Bj is of significant size, yj agrees with hw∗ (µj ). Hence E E XD E XD XD wŷ∗i − wy∗i , xi = wŷ∗i − wy∗i , µj + wŷ∗i − wy∗i , xi − µj (A.24) i∈SD
i∈SD
=
i∈SD
XD
wŷ∗i − wy∗j , µj
i∈SD
E
+
XD
wŷ∗i − wy∗i , xi − µj
E
(A.25)
i∈SD
≤ −γ|SD | + 2
X
(xi − µj ) .
(A.26)
i∈SD
Here the second term is controlled exactly as in the w∗ -direction calculation. By applying Step 7 and using the bounded empirical covariance of each returned cluster, we get X
√ (xi − µj ) ≤ Cσn η.
(A.27)
i∈SD
Combining (A.26) and (A.27) gives the dirty-sample bound in the w∗ direction: √ E 2Cσn η 1 XD ∗ wŷi − wy∗i , xi ≤ −|SD | + . γ γ
(A.28)
i∈SD
Next, since ŷi is the active maximizer of the multiclass hinge loss, its hinge value is at least the correct-label value 0. Therefore, 1(ŷi ̸= yi ) − γ1 ŵyi − ŵŷi , xi ≥ 0. Hence ŵŷi − ŵyi , xi ≥ −γ. Since 0 < κ < 1, this implies −κ ŵŷi − ŵyi , xi ≤ κγ. Now substituting (A.28) into (A.23), we obtain √ 2Cσn η 1 1 κ g3 , w ′ ≤ − √ |SD | + √ · +√ |SD | 2 2 γ 1−κ 1−κ 1 − κ2 √ 2Cσn η 1−κ 1 |SD | + √ · ≤ −√ γ 1 − κ2 1 − κ2 √ 2Cσn η 1 1 ≤ − |SD | + √ · . 2 γ 1 − κ2 Combining. Adding the three parts, g, w′ = g1 , w′ + g2 , w′ + g3 , w′ . Using g1 , w′ ≤ − 21 |SP |, g2 , w′ ≤ 0, and after dropping the negative bad samples from ⟨g3 , w⟩ we get g3 , w′ ≤ √ Cσn η , hence γ
g, w
′
√ 2Cσn η 1 − κ/2 1 ≤ −√ |SP | + √ · . γ 1 − κ2 1 − κ2
20
(A.29)
Since |S4P | >
√ 2Cσn η , then γ
1 − κ/2 |SP | g, w′ ≤ − √ |SP | + √ 2 1−κ 4 1 − κ2 3/4 − κ/2 =− √ |SP |. 1 − κ2 3
−
κ
Since minκ∈(0,1) √41−κ2 2 =
(A.30) (A.31)
√
5 4 , we get
√ g, w
′
≤−
5 |SP |. 4
(A.32)
Following main deterministic result gives us the guarantee that satisfies all the required conditions Assumption 1,Assumption 3 and Defination 8, such that a point (x, y) will not be misclassified by the classifier ŵ. It follows the same structure as of theorem 11 of [She25], but we have included for the completeness. Lemma 20 (Restatement of Lemma 11). Suppose Assumption 1 holds with parameter γ. Let (x, y) ∈ X × Y be a sample point. If √ 8Cσn η |SP | > , (A.33) γ then (x, y) is not misclassified by ŵ. P Proof. Here ŵ ∈ arg min∥w∥2 ≤1 i∈Ŝ ℓ(w; xi , yi ) is the optimization problem. Assume for contradiction that (x, y) is misclassified by ŵ. By Lemma 9 and condition on Eq (5.3), ⟨g, w∗ ⟩ < 0 for all g ∈ ∂w ℓ(w; Ŝ)|w=ŵ . We analyze the conditions in two cases. Case 1 (∥ŵ∥2 < 1). ŵ is in the interior of the constraint set , For the optimization problem, first-order optimality gives 0 ∈ ∂w ℓ(w; Ŝ)|w=ŵ , so there exists g with ⟨g, w∗ ⟩ = 0, contradicting ⟨g, w∗ ⟩ < 0. Thus (x, y) cannot be misclassified. Case 2 (∥ŵ∥2 = 1). ŵ is on the boundary of the constraint set . By KKT(Karush–Kuhn–Tucker) condition , there exist a subgradient g ∈ ∂w ℓ(w; Ŝ)|w=ŵ and a multiplier λ ≥ 0 such that g + λŵ = 0.Taking inner product with w∗ gives λ ⟨ŵ, w∗ ⟩ = − ⟨g, w∗ ⟩. Since ⟨g, w∗ ⟩ < 0, we obtain λ ⟨ŵ, w∗ ⟩ > 0. Because the λ ≥ 0 this gives , ŵ, w∗ > 0, so the angle satisfies θ(ŵ, w∗ ) ∈ (0, π/2).Now define w′ as in Eq (10).By the orthogonal relation between ŵ and w′ w′ , ŵ = 0. Applying the KKT condition again g, w′ = −λ ŵ, w′ = 0. However, Lemma 10 with condition on Eq (5.3) suggests that , g, w′ < 0 for all valid g ∈ ∂w ℓ(w; Ŝ)|w=ŵ , which contradicts the previous equality. Thus (x, y) cannot be misclassified. Both cases gives a contradiction, so (x, y) is correctly classified by ŵ.
21
B
Analysis of Algorithm 1
Let Sj ⊆ S be the clean samples in S drawn from the j-th component of DX and labeled by w∗ . That is, ∪j∈[K] Sj = SC . Similarly, denote by Sˆj ⊆ Ŝ the remained clean samples after Step 4 of Algorithm 1. Similarly, ∪j∈[K] Ŝj = ŜC . Proposition 21 (Restatement of empirical dense pancake, Proposition 12). Consider Algorithm 1. k Let S be a set of samples of size at least Ω(k 2 · (d log d + ϵδ )) from EXnas , then with probability at 3α least 1 − δ, the set Ŝ is (τ, 20 , ϵ)-dense with respect to (DX , w∗ ) with appropriate τ ∈ (0, γ4 ). In 3α addition, |Ŝ| ≥ |S| 2 and the 20 -density is contributed by ŜC . Proof. Due to the choice of sample size and Theorem 17 together with Theorem 15 (for logconcaves) or 16 (for bounded covariance), the sample set SC is (τ, Θ(α(1−ϵ)), ϵ)-dense with respect to (DX , w∗ ). To see this, take logconcave as an example, let ϵ = kβ, Theorem 15 implies that it suffices to draw 1 1 ∗ nj ≥ Ω( 1−ϵ )) samples to ensure Sj to be (τ, 1−ϵ · (d log d + log ϵδ 2 , ϵ)-dense with respect to (Dj , w ). Applying Theorem 17, it suffices to choose k X 1 k |SC | ≥ Ω nj + log α δ j=1 ! k 1 1 k ≥Ω · d log d + log + log 1−ϵ ϵδ α δ ! k . ≥ Ω k · d log d + ϵδ Note that we adjust parameter τ based on the distribution assumption: if DX is a mixture of logconcaves, τ = 2σ · (log kϵ + 1); if DX is a mixture of bounded covariance distributions, then, q ∗ τ = 2σ · kϵ . Moreover, for each j ∈ [k], Sj is (τ, 1−ϵ 2 , ϵ)-dense with respect to (Dj , w ). In addition, k to ensure the conditions in Theorem 25 are satisfied, we also require |S| ≥ Ω(k 2 · (d log d + αδ )), resulting in the sample size defined in the proposition. By Lemma 23, all k clusters are found as Bj . Then, for all j ∈ [k], Ŝj = Sj ∩ Bj ≥
Sj − 0.045 Sj = 0.955 Sj (Theorem 25). Thus, if for some (x, y), it holds that X (xi ,yi )∈Sj
(1 − ϵ) · Sj 1 (xi , yi ) ∈ Pwτ (x, y) ≥ 2
then, (1 − ϵ) 1 (xi , yi ) ∈ Pwτ (x, y) ≥ · Sj − 0.045 Sj . 2
X (xi ,yi )∈Ŝj
Let the right hand side be ρ′ · Ŝj . We have that ρ′ =
(1−ϵ) 2 ·
Sj − 0.045 Sj
≥
Ŝj
22
(1 − ϵ) 9 ϵ − 0.045 ≥ − , 2 20 2
where the second transition is due to that Ŝj ≤ Sj . Hence, it is not hard to see that Sˆj is 9 (τ, 20 − 2ϵ , ϵ)-dense w.r.t. (Dj , w∗ ). We then check the union set Ŝ. Similar to the analysis in
Theorem 17 and let q̂i =
Ŝj |Ŝ|
be the empirical weight, we have that
X
Pr(x,y)∼(DX ,w∗ )
1 (xi , yi ) ∈ Pwτ (x, y) ≥ ρ′ · |Ŝj | ≥ q̂i (1 − ϵ),
(xi ,yi )∈Ŝj
which yields to
1 Pr(x,y)∼(DX ,w∗ ) |Ŝ|
X
1 (xi , yi ) ∈ Pwτ (x, y) ≥
(xi ,yi )∈Ŝj
ρ′ · |Ŝj | |Ŝ|
≥ q̂i (1 − ϵ).
For the density lower bound, we utilize results from Theorem 25. That is, |Ŝj | |Ŝ|
=
|Ŝj | |Bj | |Sj ∩ Bj | |Bj | 0.955|Sj | 0.92α|S| 3 · · · ≥ α, = ≥ |Bj | |Ŝ| |Bj | 1.105|Sj | |S| 4 |Ŝ|
where the third transition is due to that Sj ∩ Bj ≥ 0.955 Sj , Sj △Bj ≤ 0.045 Sj + 0.03α |S| ≤ 0.045 Sj + 0.06 Sj ≤ 0.105 Sj because α |S| ≤ 2 Sj , Bj ≥ 0.92α |S|, and Ŝ ≤ |S|. Hence, since it only makes sense to learn some model with error rate ϵ < 12 , we have that 3 3 9 ϵ 3 ′ α·ρ = α· − ≥ α. 4 4 20 2 20 Finally, summing over all clean sample subsets Ŝj yields ′ X ρ · |Ŝj | 1 1 (xi , yi ) ∈ Pwτ (x, y) ≥ Pr(x,y)∼(DX ,w∗ ) ≥ (1 − ϵ). |Ŝ| |Ŝ| (xi ,yi )∈ŜC
∗ As a result, we have that Ŝ is (τ, 3α 20 , ϵ)-dense with respect to (DX , w ). Note that since ∪j∈[k] Ŝj = ŜC , the probability density 3α by ŜC . 20 is all contributed P In addition, it is easy to see that |Ŝ| = j |Bj | ≥ k · 0.92α|S| ≥ 0.92k · 0.6 k |S| ≥ |S|/2. The proof is complete.
Theorem 22 (Noise rate condition). Consider Algorithm 1 and its returned ŵ. Suppose Assumption 1 holds with some γ > 0 and 2 holds with σ. Assume that γ4 > max(τ, Cσ) and η ≤ 2121k2 . If set Ŝ γ 0.6 1 ∗ is (τ, 3α 20 , ϵ)-dense with respect to (DX , w ) with appropriate τ ∈ (0, 4 ) for some α ∈ [ k , k ], the |S| 3α 20 -density is contributed by ŜC , and |Ŝ| ≥ 2 , then errDX (ŵ) ≤ ϵ. γ 3α ∗ Proof. If Ŝ is (τ, 3α 20 , ϵ)-dense with respect to (DX , w ) with τ < 4 and the 20 -density is contributed by ŜC , we know that there exists at least 1 − ϵ probability mass of (x, y) over the distribution (DX , w∗ ) such that 3α 3α |SP | = Pŵτ (x, y) ∩ ŜC ≥ · Ŝ ≥ · n. 20 40
23
√ 8Cσn η
From the condition established in Lemma 11, it suffices to choose some such that 3α . 40 · n > γ √ γ 3α 0.6 1 By assumption, 4 > Cσ. The sufficient condition is 40 > 2 η. Consider that α ∈ [ k , k ], then it suffices to choose η ≤ 2121k2 . Moreover, this bound also satisfy the condition of η ≤ 0.01α such that Algorithm 2 can successfully run. Lemma 23. Consider Step 3 of Algorithm 1. For all j ∈ [k], Bj satisfying the guarantees in Theorem 25 are found with probability 1 − δ ′ . Proof. Due to Theorem 25, after applying Algorithm 2, the indices [m] can be partitioned into k subsets each of which represents the true cluster Bj drawn from Dj . In other words, the returned set of clusters {Bj ′ } can be further merged into a correct Bj . In [DKLP25], identifying them is hard because it was in the unsupervised learning setting. However, in supervised learning with label information y’s, this becomes much easier. As a result, we show that even without the “no-large-sub-cluster” condition, we are still able to find each Bj correctly. That is, at Step 2 of Algorithm 1, we remove any dirty samples that disagree with the majority label within the same cluster Bj ′ . As we carefully control the noise rate such that the dirty samples can not form a majority, this step always removes dirty samples. Then, we merge the clusters using label information with Step 3. Any clusters with agreeing labels (with j) will be merged into Bj . Due to that the dirty samples can not corrupt the majority label of any cluster Bj ′ , we know that each Bj is correctly found. Lemma 24 (Restatement of Lemma 14 1). Algorithm 1 runs in polynomial time. More precisely, 1 the total runtime is poly n, d, K, α . Proof. First, Algorithm 2 runs in poly(nd/α) time. Both Lmean and Lstdev have size polynomial in n and 1/α, so L is also polynomial size. Each step removes at least one element from L until termination, so there are only polynomially many steps. Each step takes poly(nd/α) time. See [DKLP25] for details. Next, the label-pruning step Bj ← {(x, y) ∈ Bj : y = maj(Bj )} is done by scanning the clusters and keeping only the points with the majority label, so this step is polynomial in n and K. Finally, the optimization problem in Eq. (4.1) is a convex multiclass hinge-loss minimization problem over the Euclidean ball ∥w∥2 ≤ 1. Since the objective is a sum of maximums of affine functions in w, it is convex. Therefore Eq. (4.1) can be solved in polynomial time by convex optimization methods from book [BV04]. Combining the runtime of Algorithm 2, the label-pruning step, and the convex multiclass SVM 1 step, Algorithm 1 runs in poly n, d, K, α time.
C
Analysis of Algorithm 2
The following theorems present the guarantees for Algorithm 2, which we include for completeness and adapt to our notations as follows. Here C > 0 is some large enough universal constant. P Theorem 25 (Theorem 3.1 [DKLP25]). Consider a mixture of distribution on Rd , DX = ki=1 qj Dj with positive qj ≥ α for some known α ∈ (0, 1). Let µj and Σj be the unknown mean and covariance √ of Dj , and assume that Σj ⪯ σj2 · Id for all j ∈ [k] and µj1 − µj2 > C 2 (σj1 + σj2 )/ α. Let S be a corrupted set of samples from DX under the strong contamination model with noise rate no more than 0.01α. Let Sj be the samples from the j-th mixture component. Then, with probaiblity 1 − δ, if |S| ≥ Ω
1 1 · (d log d + log αδ ) α2
, then there exists an algorithm that takes S, α as input, runs in
1 poly( αd ), and outputs a collection of m ≤ 0.92α disjoint sets {Bj ′ }j ′ ∈[m] such that
24
1. Bj ′ ≥ 0.92α |S| for all j ′ ∈ [m]. 2. The indices [m] can be partitioned into k subsets {H1 , . . . , Hk } such that if Bj are defined as Bj = ∪j ′ ∈Hj Bj ′ , then it holds that (a) Sj \Bj ≤ 0.045 Sj for every j ∈ [k]. (b) Bj \Sj ≤ 0.03α |S| for every j ∈ [k]. (c) For any j ∈ [k] and any j ′ ∈ Hj , we have µBj ′ − µj ≤ Cσj (d) For any pair j1′ ̸= j2′ , we have that µBj ′ − µBj ′ 1
2
q
Sj / Bj ′ .
√ > 366C(σBj ′ + σBj ′ )/ α. 1
2
Theorem 26 (Filtered Voronoi, Fact 2.4 of [DKLP25]). By applying Algorithm 3 of [DKLP25], after the Voronoi partition and a filtering process, if all underlying component Sj is (C/10, ϵ)-stable 1 with respect to µj and σj for some C > 0 and ϵ ≤ 25 , then the returned sets {Bj } satisfies that for P √ 1 (x − µj )(x − µj )⊤ ⪯ C 2 σ 2 · Id . all j ∈ [m], µBj − µj ≤ Cσ ϵ and B | j | x∈Bj As a result, after performing the clustering step, i.e. Algorithm 2, we know that every cluster is well separated from other clusters with their empirical means away from each other by L2 distance 2σ at least 366C · √ . Moreover, by the last step of Filtered Voronoi algorithm, it is guaranteed that α P each returned cluster Bj ′ , B1 (x − µj )(x − µj )⊤ ⪯ C 2 σ 2 · Id . | j ′ | x∈Bj ′
D
Sample Complexity
In this section, we provide a tighter analysis for the sample complexity required for the dense pancake condition for a mixture of distributions. We remark that the existing statistical analysis in [Tal20] only works for an instance space residing in the unit ball, i.e. ∥x∥ ≤ 1. Even though it is possible to extend it to constant-radius balls in Rd , the analysis still fails in our setting where the L2 norm is strictly larger than a constant. Since we have used Sj to denote a clean instance set drawn from Dj , we use S j to denote a set of instance-label pairs drawn from Dj and then labeled by w∗ . The following theorem gives a sample complexity for a mixture of distributions, provided that the sample complexity of obtaining dense pancake condition for each mixture component is already available. We remark that this is different from Theorem 19 of [Tal20], which only guarantees the dense pancake condition from the distributional point of view. Theorem 27 (Restatement of Theorem 17). Suppose that Assumption 2 is satisfied. If ∀j ∈ [K], a sample Sj of size |Sj | ≥ nj samples from (Dj , w∗ ) satisfies (τ, ρ, β)-dense P pancake condition with K 1 K ∗ respect to (Dj , w ), then by drawing a set S of size Ω samples from (DX , w∗ ) j=1 nj + α log δ ∗ satisfies (τ, αρ 2 , β)-dense pancake condition with respect to (DX , w ).
Proof. Since for all j, Sj satisfies (τ, ρ, β)-dense pancake condition with respect to (Dj , w∗ ), by Definition 8 we have X 1 Pr(x,y)∼(Dj ,w∗ ) 1 y ′ = y ∧ ∀ȳ ∈ Y, wȳ , x′ − x ≤ τ ≥ ρ ≥ 1 − β. |Sj | ′ ′ (x ,y )∈Sj
25
Now consider the weighted mixture of distribution. Since for every j ∈ [K], the weight qj ≥ α, if |S| ≥ α8 · log Kδ is satisfied, we have that for all j, |Sj | ≥ α·|S| 2 . That means, X αρ 1 1 y ′ = y ∧ ∀ȳ ∈ Y, wȳ , x′ − x ≤ τ ≥ Pr(x,y)∼(qj Dj ,w∗ ) ≥ qj (1 − β). 2 |S| ′ ′ (x ,y )∈Sj
Summing over the above probability over all j gives X 1 Pr(x,y)∼(DX ,w∗ ) 1 y ′ = y ∧ ∀ȳ ∈ Y, wȳ , x′ − x |S| ′ ′
≤τ ≥
(x ,y )∈S
αρ ≥ 1 − β, 2
∗ which means that S is (τ, αρ 2 , β)-dense pancake condition with respect to (DX , w ).
We show the sample complexity for the dense pancake condition for a single log-concave distribution (a single mixture component in Assumption 3), and the proof for the mixture of bounded covariance distributions naturally follows. Theorem 28 (Restatement sample complexity for a single log-concave distribution 15). Suppose that Assumption 1 is satisfied with parameter γ. If distribution Dj is logconcave with mean µj and 1 1 covariance Σj ⪯ σId , then a set Sj of at least Ω 1−kβ · d log d + log kβ + log δ1′ samples from ∗ (Dj , w∗ ) satisfies (τ, 1−kβ 2 , kβ)-dense pancake condition with respect to (Dj , w ) with probability at γ 1 least 1 − δ, for some τ = 2σ(log β + 1) ≤ 2 .
Proof. We first show that (Dj , w∗ ) satisfies (2σ(log β1 + 1), 1 − kβ, kβ)-dense pancake condition. It is well known that for any vector w̄ ∈ Rd , ∥w̄∥ ≤ 1, any random vector from a logconcave distribution Dj satisfies that ! 1 ≥ 1 − β. (D.1) Prx∼Dj w̄ · (x − µj ) ≤ σ · log + 1 β This result immediately implies that ∀w ∈ Rkd , ∥w∥ ≤ 1
Prx∼Dj
1 ∀ȳ ∈ Y, wȳ · (x − µj ) ≤ σ · log + 1 β
! ≥ 1 − kβ.
That means, except for a β probability mass, wȳ∗ · (x − µj ) ≤ τ /2, ∀ȳ ∈ Y
(D.2)
In the following, we show that for any w∗ that satisfies Assumption 1 with γ, there is a large probablity mass of Dj that have the same label with its mean µj under the classification of w∗ . Note that an x may have a different label than yj = arg maxy∈Y wy∗ · µj under w∗ only when ∃y ′ ∈ Y\yj , wy∗′ · x ≥ wy∗j · x, wy∗′ · µj + wy∗′ · (x − µj ) ≥ wy∗j · µj + wy∗j · (x − µj ), (wy∗j − wy∗′ ) · µj + (wy∗j − wy∗′ )(x − µj ) ≤ 0 26
Since (wy∗j − wy∗′ ) · µj ≥ γ for any y ′ ∈ Y\yj , it can only happen when (wy∗j − wy∗′ ) · (x − µj ) ≤ −γ. However, due to Eq. (D.2), we know that for any yj , y ′ ∈ Y (wy∗j − wy∗′ ) · (x − µj ) ≤ wy∗j · (x − µj ) + wy∗′ · (x − µj ) ≤ τ. Hence, ∀y ′ ∈ Y\yj , (wy∗j − wy∗′ ) · (x − µj ) ≥ −τ ≥ −γ. That is, wy∗′ · x ≥ wy∗j · x can not happen and arg maxy∈Y wy∗ · x = yj . More formally, Pr(x,y)∼(Dj ,w∗ ) y = yj ∧ ∀ȳ ∈ Y, wȳ , x − µj ≤ τ /2 ≥ 1 − kβ. Moreover, Pr(x,y)∼(Dj ,w∗ ) Pr(x′ ,y′ )∼(Dj ,w∗ ) y ′ = y ∧ ∀ȳ ∈ Y, wȳ , x′ − x
≤ τ ≥ 1 − kβ ≥ 1 − kβ. (D.3)
We then show the sample complexity for obtaining an empirical set that satisfies a dense pancake condition for (Dj , w∗ ). For the ease of presentation, let ρ = 1 − kβ and β ′ = kβ, then for any w ∈ Rkd , ∥w∥ ≤ 1, Pr(x,y)∼(Dj ,w∗ ) Pwτ (x, y) is ρ-dense w.r.t.(Dj , w∗ ) ≥ 1 − β ′ , due to Definition 8. From now on, we use D instead of (Dj , w∗ ) to further ease the notation. The following part follows the idea of [Tal20], but we include for clarity and completeness. Now, fix a w. For any (x, y) ∈ S good := {(x, y) : Pwτ (x, y) is ρ-dense w.r.t.(Dj , w∗ )}, apply Chernoff bound (Lemma 31), X 1 ρn τ PrS∼Dn 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 ≤ exp − . n 8 i∈S
Then,
n o X 1 ρn good τ ES∼Dn Pr(x,y)∼D 1 (x, y) ∈ S ∧ . 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 ≤ exp − n 8
i∈S
Further take expectation over D gives n o X 1 ρn good τ , ES∼Dn ,(x,y)∼D 1 (x, y) ∈ S ∧ 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 ≤ exp − n 8 i∈S
which gives
X 1 ρn good τ ES∼Dn Pr(x,y)∼D (x, y) ∈ S ∧ 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 ≤ exp − . n 8
i∈S
By taking Markov’s inequality, we have X 1 1 ρn good τ ′ PrS∼Dn Pr(x,y)∼D (x, y) ∈ S ∧ 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 > β ≤ ′ ·exp − . n β 8 i∈S
27
Together with the samples in complement set of S good , which contributes to another β ′ probability mass, we have that X 1 1 ρn τ ′ PrS∼Dn Pr(x,y)∼D . 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 > 2β ≤ ′ · exp − n β 8 i∈S
It remains to show that the above inequality holds for any w ∈ Rkd , ∥w∥ ≤ 1. Note that due to the concentration bound of logconcave distribution, a probability mass of at least 1 − δ ′ /2, √ x − µj ≤ σ d · (log δ2′ − 1) =: b/2. Now, let us unfix the vector w. We note that it suffices to ′ include the pancake Pwτ (x, y) in a larger pancake of Pwτ +τ (x, y) with a different w′ . That is, we ′ require ∀(x′ y ′ ) ∈ Pwτ (x, y), w′ , Ψ(x′ , y ′ ) − Ψ(x, y) ≤ τ + τ ′ . Due to triangle inequality and since ∀(x′ y ′ ) ∈ Pwτ (x, y), w, Ψ(x′ , y ′ ) − Ψ(x, y) bound w′ − w, Ψ(x′ , y ′ ) − Ψ(x, y)
≤ τ , it suffices to
with τ ′ . Since (x′ , y ′ ) is in the pancake and y = y ′ , Ψ(x′ , y ′ ) − Ψ(x, y) ≤ b with high probability. ′ It suffices to construct a τb -net over the unit ball. Use standard geometric covering, the net is of ′ size exp(d · log d) since τb = Θ( √1d ). Together with the previous failure rate bound, we have that ∀w ∈ Rkd , ∥w∥ ≤ 1
X ρn 1 1 τ ′ + log ′ . 1 (xi , yi ) ∈ Pw (x, y) < ρ/2 > 2β ≤ exp d · log d − PrS∼Dn Pr(x,y)∼D n 8 β i∈S
Let the failure rate to be bounded by another δ ′ /2 gives that ! 1 1 1 n≥Ω · d log d + log + log ′ . ρ kβ δ
(D.4)
The proof for the sample complexity of dense pancake condition for a single distribution with q 1 2d bounded covriance is similar to the above, but with a worse τ = 2σ · √β and b = 2σ · β . That said, since the ratio τb is still the same as that in the proof for a single logconcave, the sample complexity stays the same. We leave it to interested readeres. To see that τ = 2σ · √1β , note that Prx∼Dj ( (x − µj ) · w̄ ≥ Let the right hand side be β and we obtain that
√ σ2 t) ≤ . t
√ t = σ 2 /β.
Theorem 29 (Restatement of sample complexity for a single bounded covariance distribution 16 ). Suppose that Assumption 1 is satisfied with parameter with mean µj γ. If Dj is a distribution 1 and covariance Σj ⪯ σId , then a set Sj of at least Ω ρ1 · d log d + log kβ + log δ1′ samples from ∗ (Dj , w∗ ) satisfies (τ, 1−kβ 2 , kβ)-dense pancake condition with respect to (Dj , w ) with probability at γ 1 ′ least 1 − δ , for some τ = 2σ · √β ≤ 2 .
28
E
Useful Lemmas
Definition 30 (Multivector feature map). Fix X = Rd and Y = [k]. The multivector (class-sensitive) feature map Ψ : X × Y → Rkd is Ψ(x, y) := x ⊗ ey = (0, . . . , 0, |{z} x , 0, . . . , 0).
(E.1)
y-th block
For any w ∈ Rkd , write w = (w1 , . . . , wk ) with wy ∈ Rd . Then w, Ψ(x, y)
=
wy , x .
(E.2)
Moreover, Ψ(x, y) 2 = ∥x∥2 for any y and Ψ(x, y ′ ) − Ψ(x, y) 2 =
√
2 ∥x∥2 for y ′ ̸= y.
Lemma 31 (Chernoff bounds). Let Z1 , Z2 , . . . , Zn be independent random variables taking values in {0, 1} and let n X Z = Zi . (E.3) i=1
If Pr(Zi = 1) ≤ η, then for any α ∈ [0, 1], Pr Z ≥ (1 + α)ηn
α2 ηn ≤ exp − 3
!
α2 ηn ≤ exp − 2
!
.
(E.4)
.
(E.5)
If Pr(Zi = 1) ≥ η, then for any α ∈ [0, 1], Pr Z ≤ (1 − α)ηn
Lemma 32 (Matrix Chernoff inequality). Let M1 , M2 , . . . , Mn be independent random self-adjoint matrices of dimension d. Assume Mi ⪰ 0 and λmax (Mi ) ≤ Λ almost surely. Let n X µmax = λmax E[Mi ] . (E.6) i=1
Then for all α ≥ 0, with probability at least 1−d we have
eα (1 + α)1+α
µmax /Λ ,
n X λmax Mi ≤ (1 + α)µmax .
(E.7)
(E.8)
i=1
Lemma 33 (Properties of isotropic log-concave distributions). Let D be an isotropic log-concave distribution over Rd . Then: (1) Orthogonal projections of D onto any subspace are isotropic log-concave. (2) For any unit vector u ∈ Rd and any α > 0, ≤ e−α+1 .
(E.9)
√ Prx∼D ∥x∥2 ≥ α d ≤ e−α+1 .
(E.10)
Prx∼D | ⟨u, x⟩ | ≥ α (3) For any α ≥ 0,
29