Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Authors: Ilias Diakonikolas
Mingchen Ma
Lisheng Ren
Christos Tzamos
Venue: ICML 2025 oral (2025)
Keywords: Multiclass Linear Classification
Random Classification Noise
Statistical Query Learning
Primary area: theory->learning_theory
TL;DR: We prove the first sets of SQ lower bounds for multiclass linear classification under random classification noise.

Abstract: We study the task of Multiclass Linear Classification (MLC) 
in the distribution-free PAC model 
with Random Classification Noise (RCN). 
Specifically, the learner is given a set of 
labeled examples $(x, y)$, where $x$ is drawn 
from an unknown distribution on $R^d$ 
and the labels are generated by a 
multiclass linear classifier corrupted with RCN. 
That is, the label $y$ is flipped from $i$ to $j$ 
with probability $H_{ij}$ 
according to a known noise matrix $H$ with 
non-negative separation 
$\sigma: = \min_{i \neq j} H_{ii}-H_{ij}$. 
The goal is to compute a hypothesis with 
small 0-1 error. For the special case of two labels, 
prior work has given polynomial-time algorithms 
achieving the optimal error. 
Surprisingly, little is known about 
the complexity of this task even for three labels.
As our main contribution, we show that the complexity 
of MLC with RCN becomes drastically different 
in the presence of three or more labels. 
Specifically, we prove super-polynomial
Statistical Query (SQ) lower bounds for this problem. 
In more detail, even for three labels and 
constant separation, 
we give a super-polynomial lower bound 
on the complexity of any SQ algorithm achieving optimal error. 
For a larger number of labels  and smaller separation, 
we show a super-polynomial SQ lower bound even 
for the weaker goal of achieving any constant factor approximation to the optimal loss or even beating the trivial hypothesis.

Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise
Ilias Diakonikolas' Mingchen Ma"
Lisheng Ren
Christos Tzamos" *
Abstract
all i E [k]] (If the maximum is achieved by more than one indices, the tie is broken by taking the smallest index.). Mul- ticlass Linear Classification (MLC)-the task of learning an unknown linear classifier from random labeled examples- is a textbook machine learning problem SShalev-Shwart & Ben-David, 2014), which has been extensively studied both theoretically and empirically (Platt et al., 1999; Hsu & Lin, 2002; Aly, 2005; Duan & Keerthi, 2005; Tewari & Bartlett, 2007; Kakade et al., 2008; Huang et al., 201 1; Beygelzimer et al., 2019). MLC naturally arises in range of critical applications, including face recognition (Lihong et al., 2009), cancer diagnosis (Panca & Rustam, 2017), ecological indicators (Bourel & Segura, 2018) and more. In all these settings, the number of labels much larger than two-hence they cannot be modeled by binary linear classification. Moreover, MLC has important connections with modern deep learning architectures; the last layer of neural network is typically a softmax function layer- natural extension of MLC.
We study the task of Multiclass Linear Classifi- cation (MLC) in the distribution-free PAC model with Random Classification Noise (RCN). Specif- ically, the learner given a set of labeled exam- ples (ar, v). where x is drawn from an unknown distribution on Rd and the labels are generated by a multiclass linear classifier corrupted with RCN. That is, the label y is flipped from i to j with probability Hij according to a known noise matrix И with non non-negative separation o = minezz Hs H,j- The goal is to com- pute hypothesis with small 0-1 error. For the special case of two labels, prior work has given polynomial-time algorithms achieving the optimal error. Surprisingly, little is known about the com- plexity of this task even for three labels. As our main contribution, we show that the complexity of MLC with RCN becomes drastically different the presence of three or more labels. Specifically, prove super-polynomial Statistical Query (SQ) lower bounds for this problem. In more detail, even for three labels and constant separation, we give a super-polynomial lower bound on the com- plexity of any SQ algorithm achieving optimal error. For a larger number of labels and smaller separation, we show a super-polynomia SQ lower bound even for the weaker goal of achieving any constant factor approximation to the optimal loss or even beating the trivial hypothesis.
The sample complexity of MLC is fairly well-understood in the PAC model, even in the presence of noise. Specifi- cally, standard arguments, see, e.g., (Shalev-Shwartz & Ben- David, 2014), give that poly(d, (d, k. 1/c) samples information- theoretically suffice to achieve 0-1 error opt + where opt. is the optimal error achievable by any function in the class, Yet the computational complexity of this task has remained perplexing. In the realizable setting (i.c., in the presence of clean labels), the sample complexity of MLC is Ö(dk /c) and the problem solvable in polynomial-time via reduc- tion to linear programming (LP). Notably, the corresponding IP can be solved efficiently in the Statistical Query (SQ) model (Kearns, 1998), using a rescaled Perceptron algo- rithm (Dunagan & Vempala, 2004). Alas, the realizable setting is highly idealized in most practical applications, some form of partial label contamination is unavoidable. is thus natural to ask what is algorithmically possible in the presence of label noise.
1. Introduction
A multiclass linear classifier is any function f Rd + [k] of the form fxx = argmax;e (w: 1)), where w, Rd for
'Equal contribution 'Department of Computer Sciences, Uni- versity of Wisconsin-Madison. Madison, USA Univeersity of Athens and Archimedes AI, Athens, Greece. Correspondence to: Mingchen Ma <mingchen @es, eds,, Lisheng Ren <Iren29 wis..
If the label noise is adversarial (Haussler, 1992; Kearns et al., 1994) or even semi-random (Massart & Nédélec, 2006), strong computational hardness results are known even for binary linear classification, corresponding to k = (Daniely, 2016; Diakonikolas et al., 2022: Diakonikolas & Kane, 2022; Nasser & Tiegel, 2022; Diakonikolas et al.,
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

SQ Hardness of Multiclass Linear Classification with RCN
2023a; Tiegel, 2023). These hardness results, of course, earry over the multiclass setting.
tion (ERM). (Moreover, the ground truth f achieves the optimal 0-1 loss of opt.) This can be directly deduced from (Massart & Nédélec, 2006). Though the sample complexity of the problem is understood, its computational complexity has remained open even for the case of 3 labels.
Interestingly, if the label noise is the Random Classification Noise (RCN) model (Angluin & Laird, the binary linear classification task admits a polynomial-time algorithm. The first such algorithm was given in (Blum et al., 1998); see also (Dunagan & Vempala, 2004; Diakonikolas et al., 2021; 2023b; Kontonis et al., 2024). All these algorithms are known to fit the SQ model.
by
A long line of work (Wang et al., 2017; Patrini et al., 2017: Van Rooyen & Williamson, 2018; Lipton et al., 2018; Zhang et al., 2021) has focused on understanding MLC, and more general multiclass classification, with RCN from an algorith- mie perspective- both theoretically and empirically. The methods proposed and analyzed in these works require in- verting the noise matrix H during the training process, and achieve sample and time complexity scaling inverse polyno- mially with the minimum singular value of H. This quantity could be arbitrarily small or even zero- even if k 3 and separation o = 0.1. Hence, such approaches do not lead to an efficient algorithm in general.
The preceding discussion motivates the algorithmic study of MLC in the presence of RCN. A positive algorithmic result for the multiclass case with RCN would be of significant theoretical and practical interest. As our main contribution, we give strong evidence that such an efficient algorithm does not exist.
To formally state our contributions, we require the definition of multiclass classification with RCN that has been widely studied in prior works (Patrini et al.. 2017; Van Rooyen & Williamson, 2018; Ghosh et al., 2017).
For binary classífication, (Kearns, 1998) showed that any efficient SQ algorithm that succeeds in the realizable setting can be efficiently converted into an efficient SQ algorithm that solves the same problem in the presence of RCN. Unfor- tunately, no such result is known for the multiclass setting. This suggests that efficient algorithm for MLC with RCN would require novel techniques.
Definition 1.1 (Multiclass Classification with RCN). Let X be the space of examples and let Y = |k] be the label space. A multiclass classifier is any function f: X + Y. A noise matrix H E [0, 1| is row stochastic matrix such that for every i E [k)] Σÿ= Hij- = 1. An instance of multiclass classification with RCN is parameterized by (D, H), where f* is the ground truth multiclass classifier, H is the noise matrix, and D is joint distribution over X x Y such that each labeled example (z, v) ~ D is generated as follows. We have ~ Dx, where Dx is the marginal of D over X. The label y of æ is drawn from the distribution such that Pr(y = j | x) = H (x)j for j E [k).. The error of a hypothesis h: : X + Y is defined as err(h) == Pr (h(x) * y). Given set S of i.i.d. examples drawn from D, E (0, 1), and a function class F such that f" E F,a learner asked to output hypothesis h such that ehr(h) < opt + e, where opt == minjer err(f).
Perhaps surprisingly, here we provide strong evidence that such an efficient algorithm does not exist, even for the case of 3 labels. Formally, we establish the first super-polynomial SQ lower bounds for MLC with RCN, suggesting that the complexity of the problem dramatically changes for k 2 3.
SQ algorithms are class of algorithms that, instead of having direct access to samples, are allowed to query ex- pectations of bounded functions of the distribution (see Definition 3.1). The SQ model was introduced in (Kearns, 1998). Subsequently, the model has been extensively stud- ied in a variety of contexts (Feldman, 2016). The class of SQ algorithms is broad and is known to capture range of al algorithmic techniques (Feldman et al., 2017a:b)
We will also consider algorithms with approximate error guarantees, namely aiming for 0-1 error Copt + e, where C' is a universal constant. While the focus of this paper is on the setting that F is the class of multiclass linear classifiers, the broader class of multiclass polynomial classi- fiers will arise in our proof. A multiclass degree-m polyno- mial classifier fP= : Rd > [k] is characterized by a collec- tion P = (P). . ,k)), where p((x)) IRdd - R, E [k], a polynomial of degree at most m. For x Rd. fr(x)= argmax,ze[s] (z))). (If the maximum is achieved by more than one indices, the tie is broken by taking the smallest index.)
All our hardness results hold even if the noise matrix H is known and given as input to the learner. Our first main result pertains to the case of optimal error guarantee, and holds even if is a positive constant. In particular, we show:
Theorem 1.2 (Informal Statement of Theorem 6.1.. There is noise matrix H E [0, 1,3x3 with Ha: - H:j 2 0.1, Vi # j E [3], such that it is SQ-hard to learn an MLC problem on Rd, with RCN specified by H, up to error opt + c.
Given Theorem 1.2, it is natural to ask whether it is possible to approximately e efficiently learning MLC under RCN. A learner is said to be Caaaproximmaee if it outputs hypothesis h such that crr(h) N Copt + c, Ve E (0, 1), where C > 1. By considering larger values of l and small separation a,, we show that even approximate learning SQ-hard (even if
If a == minizj H - 2 0, MLC with RCN can be solved up to error opt + with sample complexity min (Ō(kk/oc) Ö(dk/()) via empirical risk minimiza-
2

---

SQ Hardness of Multiclass Linear Classification with RCN
the noise level is small). In more detail, we show:
one can reduce learning multiclass degree-m polynomial classifiers with RCN to learning linear classifiers with RCN using the Veronese mapping, defined as V(z) == (xz 1) 1)@m Therefore, it suffices for us to give a distribution D that is consistent with an instance of a multiclass polynomial
Theorem 1.3 (Informal Statement of Corollary 6.3). For any C' >> 1, there exists a noise matrix H [0]1, where k == =C") and = mins,. H Hi, = Q11/C), such that it is SQ-hard to learn an MLC problem on IC' with RCN specified by H up to error Copt, even opt = (1/C).
[V)x)} with RCN over RN instead. We remark that as we want to prove SQ hardness for MLC over I and d = NO(m), if m is large. then we need to prove stronger hardness result for the poly- nomial classification problem over RN, As we will discuss in Section 6, key towards proving our SQ-hardness result is to choose the correct value of m.
classifier f = argmax (v x),, ,..............
In fact, our final result shows that within the regime a = mingzs Hj - i > 0, it is even SQ-hard to learn a hypoth- esis with error 1 1/k o(1), even if opt O(1/k). That is, it is hard to even find hypothesis better than guessing the labels uniformly random. Specifically, even if we only add 1% RCN for an instance of MLC, it is hard to learn a hypothesis with error better than 99% for k- = 100.
Given the above discussion, it suffices to look at one- dimensional distributions along u. Our key observation, that leads to our SQ-hardness result, is that for noise matrix H, if the kth row h& can be written as convex combina- tion h2 [) hyhy of the other rows, then an exam- ple drawn from the marginal distribution a
Theorem 1.4 (Informal Statement of Corollary 6.4). For any k E Z+ with & 2 3. there is a noise matrix H e [0, 11 with a = min:.; Hi,- - Hs.j = (11/d) such that is SQ-hard to learn an MLC problem on E with RCN specified by H up to error 1 1/k o(1), even if opt ((1/k).
where p. the marginal distribution for x with f*(x) = j. will have observed label following the distribution hg. In- tuitively, if D has such a marginal distribution of x, then the conditional distribution on y E [k] should be a mixture of the base distributions pMA, As long as Ai, i E IK - 1] is close to N(, 1), this in turn can be shown to imply hardness result.
2. Technical Overview
At a high level, our proof leverages the SQ lower bound framework developed in (Diakonikolas et al., 2017) and tech- niques for constructing distributions that match Gaussian moments from (Diakonikolas & Kane, 2022) and (Nasser & Tiegel, 2022). We stress that while these ingredients are useful in our construction, employing them in our context requires novel conceptual ideas.
Such an intuition is useful but is not formally correct: in gen- eral, the conditional distribution is not exactly a mixture of the base distributions. We overcome this difficulty by mix- ing examples with (z) = é and f(xx) carefully to obtain A,, i E [k 1]. Specifically, we leverage techniques for constructing moment-matching distributions from (Di- akonikolas & Kane, 2022; Nasser & Tiegel, 2022). Roughly speaking, these works considered the following distribution. Let Gs.s be the distribution of 2 ~ .N(0, 1) conditioned on = E I, = 168 - i, + E] for E Z,4 i.e., conditioned on equally spaced intervals with width g. The distribution Go.s approximately matches moments up to degree 1/82 up to error 2 2-1(1 with N(0, 1) and its chi-squared norm is not too large for any & 2 2-1(1/8") We choose A = Go.g. Inspired by (Nasser & Tiegel, 2022), for i E [-m, m). if we make tiny shifts for Ai over these 4, k - 2 times to get k unions of disjoint intervals Jy.j E [k: 1). we obtain distributions A A&-1 that are close to N 1). Importantly, one can construct polynomials (=(=) > 0 if and only if E Jj.j E [k- - 1], and pa(2) > 0f and only if z & I, := U, J,. This implies that D is consistent with an instance of multiclass polynomial classification with degree (m).
Roughly speaking, prior work (Diakonikolas et al., 2017) and its generalization (Diakonikolas & Kane, 2022) give generic framework for proving SQ-hardness results for supervised learning problems. Consider distribution D a distribution consistent with an instance
over Rd x [ of a classification problem. Suppose that for E [k), the distribution of x conditioned on y has the form of Pd, for v a hidden direction in dRdd such that: (i) Ze, the projection of r on the direction, follows a one-dimensional distribution A, and (ii) xrt ~ ((, I). Moreover, suppose that the one-dimensional distribution A nearly matches the first moments of N (0, 1). within error v, and has chi-squared norm at most B. The any SQ algorithm that correctly distin- guishes between the case where (at, v) is drawn from such a D versus the case where the label y is generated indepen- dently of æ according to Dy, needs either to make 2 statistical queries or to make a query with tolerance 2/7, where - = 2 + 2 R()) B.
To leverage the aforementioned result, it suffices for us to construct a distribution D with the form discussed above that is consistent with an instance of MLC with RCN. Un- fortunately, constructing such a D directly is technically challenging. To overcome this obstacle, we first note that
Moreover, we show that the larger Pr(z E I(n) is con- structed, the better learning guarantee we can rule out. If we choose Pr(z E I.n) e, then we able to rule out
3

---

SQ Hardness of Multiclass Linear Classification with RCN
learning algorithms that achieve error opt + c. Moreover, by carefully designing the noise matrix H and choosing Pr(z E 4nn) = 1 - 1/poly(K) (k), we are additionally able to rule out algorithms with error better than 1 - l/k, even if opt = ((1/)).
4. From Hypothesis Testing to Learning
The usual way to prove an SQ-hardness result for a learning problem is show hardness for an appropriate hypothe- sis testing problem that efficiently reduces to the learning problem. In this section, explore the properties of multi- class classification problems and introduce the hypothesis testing problem. To start with, we give the following condi- tion, which will be used to create a hard hypothesis testing problem related to the multiclass classification problem.
3. Preliminaries and Notations
Let f X + Y be the ground truth hypothesis. For j E [k], denote by S {o (z) = 5} S Rd the set of examples with (x)
j. Let h X + Y be an arbitrary hypothesis. For j,j E [k], we denote by Sjz = fz fx)) = J. h(x)=()))))() = S Rd, the set of examples with ground truth label j. but on which h predicts i. this paper, we use gd-1 to denote the unit sphere in RR.. Let K C Rdd be any set; we denote by conv(K), the convex hull of K. For noise matrix H E [0, 1| we denote by h e [k]. the ith row vector of H.
Definition 4.1 (SQ-Hard to Distinguish Condition). Let I= (D, S H) be an instance of multiclass classification with RCN. We say that the instance I satisfies the hard-to- distinguish condition if it satisfies the following conditions:
1. There exist a; 2 0, i E [k- - 11. Et= = 1 such that h2 Σ k - a,hg
2. Vi E lk 11 Pr Pr (ar E S; + St.) 04--
3. H₂; H4s Vj, [k].
For a distribution D, we use Ex~n(z) to denote the expec- tation of D. Let D be a distribution of (z. over I& x [k:] We use Dx to denote the marginal distribution of D over Id and use D, to denote the marginal distribution of D over y. In this paper, we will use (O, I) to denote the standard Gaussian distribution over R and use (0, 1) to denote the standard one mi-dimensionnl normal distribution. For N0, 1), we use Gzz)) to denote its density function and use Ye, t E N, to denote its standard Ith moment (0.1) x..
We give some intuition behind Definition 4.1. Given a noise matrix H, the first condition, Item 1, implies that the kth row vector of H can be written as a convex combination of h2 i E [k- 1]. with convex coefficients 0;- Recall that an example with ground truth label has Hij prob- ability to be observed as label j. If the probability mass of 51,...,Sk-p are assigned proportionally to these con- vex coefficients (Item 2). then a random example drawn from these regions will have probability Has to have label i. Specifically, we draw a random example Dx then
Definition 3.1 (SQ Model), Let D be distribution over
X x Y. A statistical query is a bounded function q : X x Y + 1]. We define STAT(T) to be the ora- cle that given any such query q. outputs a value v such that |o- - (a (14 y)ll S 5, where > is the tolerance parameter of the query. A statistical query (SQ) algorithum an algorithm whose objective is to learn some information about an unknown distribution D by making adaptive calls to the corresponding STAT(T) oracle.
Pr (u = i) (x.g)~
Pr (x E Sx)) Et as + Pr (x E &Sk) H D>
=
D>Dx
Pr (x E Sa) + Pr (a Sc) -Hi- x>Dx
This implies that the marginal distribution Dy follows the discrete distribution hg. This suggests that given set of examples drawn i.i.d. from D, without exploring the struc- ture of the data, it is hard to tell whether the labels y are generated from an instance of multiclass classification or generated from the distribution hi independent of x.
Definition 3.2 (Pairwise Correlation). The pairwise corre- lation of two distributions with probability density func- Rd + I with respect to a distribu- tion with density D= Rdd + Rt, where the support of D contains the support of D1 and D2, is defined as (D,, D2)= = fge D2 (x) D(x)dx 1. Further- more, the x-squared divergence of D, D is defined as (D,, D) = (Di,
tion D1, D2
Motivated by this observation, we define the following test- ing problem, which we will show later to be hard to solve if some additional distributional assumptions are satisfied.
Definition 4.2 (Correlation Testing Problem). A correlation testing problem B(Dp, D) is defined by a distribution Do and a family of distributions D over X x Y. An algorithm is given SQ query access to some distribution D and noise matrix H, and is asked to distinguish whether D = Do or D E D. In particular, Do and 'D satisfy the following properties.
Organization The structure of this paper is as follows: In Section 4, we introduce an appropriate hypothesis testing problem and show how to efficiently reduce it to our learning problem. In Section 5, we construct the hard distribution for the testing problem. Finally, in Section 6, we prove the main results of this paper by carefully choosing the parameters and putting together the reduction of Section 4 and the hard distribution construction of Section 5.
1. Null hypothesis: x ~ (Do)x x for some known distri- bution (Do)x, where y is independent of such that
4

---

SQ Hardness of Multiclass Linear Classification with RCN
Pr (rg)(DD)) (y = = Ka, Vi E [k). 2. Alternative hypothesis: D& E D, where each distribu- tion D& E DD corresponds to a multiclass classification instance (D, H) that satisfies Definition 4.1.
to prove the hardness of the learning problem, it suffices for us to construct instances of multiclass classification problem that satisfies Definition 4.1 and 1 - Pr(Sx) is as large as the desired accuracy a. In particular, the larger - Pr(Sk) can be constructed, the stronger hardness result we are able to obtain. We defer the details to Section 5.
The correlation testing problem asks algorithm to test whether the distribution of y is generated according to instance of a multiclass classification problem or is gen- erated from a known distribution that is independent of J. In the rest of this section, we establish the connection between the testing problem of Definition 4.2 and the multi- class classification problem. We first present the following eror-deccmpooition lemma, that describes the error of any multiclass hypothesis h. We defer the proof of Lemma 4.3 to Appendix B.
5. Hardness of Hypothesis Testing
Given Lemma 4.4, we know that it suffices to construct correlation testing problem B Do: 'D) that is hard to solve. Notice that any multiclass polynomial classification prob- lem can be represented as a multiclass linear classification problem in a higher dimension via the kernel method. So, we will consider constructing a family of correlation testing problems B D) for multiclass polynomial classifica- tion problems. Consider instance I (D. f", .H) of multiclass polynomial classification problem with degree- m under the SQ-hard to distinguish condition, where f is characterized by k degree-m polynomials of the form pi (v z)..... Pp(U - z),, v E S Then the label y is com- pletely dependent on v, which implies that learner must look at examples close to in order to solve the testing problem. This motivates to look at the following hidden direction distribution that is frequently used in the literature of SQ lower bounds (Diakonikolas et al., 2017).
Lemma 4.3. Let (D.f"HH be any instance of multi- class classification with RCN. Let h X - Y be arbitrury multiclass hypothesis over X. Then, err(h) = E5-1 Pr(S,)(1-1) (1;))))) + Eigg (r(S Hji) In particular, if Hjj H3s 2 foror every j E [k], + j. then opt = eer(f*) = Eÿ (r(())(1-
Given Definition 4.2, the following lemma reduces the cor- relation testing problem to the classification problem.
Lemma 4.4. Let D be a family of distribution over X X Y such that each distribution D E 'D corresponds to a multi- class classification instance (D.f* .)) that satisfies Defi- nition 4.1. If there is an SQ learning algorithm A such that for every instance (D, H)), D E DD A makes q queries, each of tolerance т, and outputs a hypothesis h such that err(h) S opt where 2a= = ΣØ= Pr(S,) (H then there is an SQ algorithm A' that solves the correlation testing problem defined in Definition 4.2 by making q + queries, each of tolerance min(r, ax/2)
Definition 5.1 (Hidden Direction Distribution). Let A be a distribution over R. with probability density A(x) and v Rdd be unit vector. Define PA (z) A(u /2) /(xx)(d-1)/2 i... PA is
x) exp (v product distribution whose orthogonal projection onto v is A and onto the subspace orthogonal to e is the standard (d 1)- dimensioonll Gaussian distribution.
Based on the definition of the hidden direction distribution, we construct the family of hard distributions D as follows.
We defer the full proof of Lemma 4.4 to Appendix B.2 and give an overview of the proof below. Recall that the goal of the correlation testing problem is to tell whether the label y is generated according to the discrete distribution h2 independent of x (null hypothesis) or is generated ac- cording to some D from D (alternative hypothesis). In the former case, no hypothesis will have an error better than the constant hypothesis h(x))= = k, which has an error of 1- Hak. In the latter case, by Lemma 4.3, we can show that err(k) - opt 20. This implies that, if we can learn the multiclass classification problem up to error opt + a, then we only need to make a single query with tolerance a/2 to check whether the hypothesis h we learn has emror less than 1- H&* a/2 to solve the testing problem.
Definition 5.2 (Hidden Direction Distribution Family). Let H E [0, 1] 1 be noise matrix that satisfies (1), (3) in Definition 4.1 with the convex combination coefficients [0, - Let A = (A1.... AR-1) be list of k 1 base distributions, where for i E [R- 1]. A, is a one-dimensional distribution that satisfies the following conditions:
1. 3 a set of m disjoint intervals J4, i E [k- 1]. such that
(x > 0, for x E J, and (, = 0, for x E T \ Jo.
where Inn = U,eee-1 Jy.
2. Vz E R \ Lm. A,(x) =
E [k- 1].
We define the hidden direction distribution family D (DA.)) over Rd x [k] such that (x.y) DA.a is sampled as follows. With probability aj. x ~ p.", If x E Jj. sample y = i with probability H3s, otherwise, sample y = with probability Haa-
Given Lemma 4.4, we briefly explain how we will use it to prove the hardness results. Notice that if we choose H3j- - H 2 c, for some constant c >> and j E [R- -1, then a = (11 Pr(S))). Thus, Lemma 4.4 suggests that in this case,
5

---

SQ Hardness of Multiclass Linear Classification with RCN
A, pelynomiel polynomial Py
pdf of x|y=1
pdf of y
pdf of x x|y=
polynombal
polynomial p.
polynomial Pa
polynomial Pg
-78
-66
-56
-45
33
28
15
06
20
36
45
56
66
-76 -66 -50 -45 33
-10 05
16
20 36 45 55 66
Figure I: Illustration of base distributions for k = His- tograms that are colored in red (resp. blue) correspond to distribution A1 (resp. A2). P1. P2.Ps Ps colored in red, blue, and green are polynomials that characterize the target hy- pothesis f" (ress.. J2) are red (resp. blue) intervals within the range (-26, 20), where examples have ground truth label 1 (resp. 2). Examples outside J1 J/ have ground truth label
Illustration of (D yym for 1: 3. Pl. Pa colored in red, blue, green are polynomials that characterize the ground truth f". Histograms in red (resp. blue, green) correspond to distribution (DA.") (resp. (Da-"))==> (Dz""))p=>) For each i, (D. >yy= has many moments close to the moments of a standard normal.
Figure 2:
We summarize the key properties of hidden direction dis- tribution family in Theorem 5.3, the main theorem of this section. Due to space limitations, the full proof is deferred to Appendix C.2.
Jn 0, * j. we know that for each j [k: 1). if u x E Jj. then j = argmax(p1 (v z).... (s x) and if v 2 & Iin, k = argmax (v x).....,Pk Thus, D is consistent with an instance of multiclass poly- nomial classification with RCN (DA.., f H), where the marginal distribution is Σド= a,P." and the ground truth hypothesis f'(x) = argmax (pi (...)......P((.. (v-x))) This gives an overview of the first part of Theorem 5.3.
pa (v: x))
Theorem 5.3. Let B(Do, D) be a correlation testing prob- lem, where (Do)x = (O, 1) and D is a hidden direction distribution family. Suppose there exists v/ > 0 such that for & E E the family of one-dimensional distribution A1...., Ak-1 satisfies Ez~A, x² - rel S Then:
---1
We next focus on the second part of Theorem 5.3. To simplify the notation, for each E [kt]. we denote by D Dx y = i) in the rest of this section. The proof strategy here is use the standard SQ dimen- sion (Lemma A.4). It is well-known that for any small constant c, there exists at least (0.(d) many unit vectors u, v such that |u, vl S (see Fact A.5). Thus, to use Lemma A.4, we only need to bound XD (DA. DA."), where |u-e] v| S e as well as XD, (DA.a D..a). Since XD. (DA.a DA- = Σ.= HuXXN(O.)) (Di. D() it is equivalent to upper bounding XN(O, (Di, Dt). However, even though the base distributions P.A,, are all close to (0, I) (thus have a small pairwise correlation), in general, conditional on the label y = i, there no such guarantee for D Here, we make use of Item 2, in the construction of the distribution family. Under Item 2, every DÍ, is indeed a mixture of the distributions P.", .j E [A 1]. Formally, we have the following technical lemma (see Figure 2 for intuition), the proof of which is deferred to Appendix C.I.
1. Every distribution D E D is consistent with an in- stance of multiclass polynomial classification with RCN (D f with degree at most 2m that satisfies Def- inition 4.1.
For any small enough constant e maxis XN(o,1)(A;; As) and let == v2 + c. Any SQ algorithm that solves B(Do, D) must make a query with accuracy better than 2-/T or make 20((0T/B queries.
let 3
In the rest of this section, we give an overview of the con- struction of the hidden direction distribution family as well as the proof of Theorem 5.3.
Consider distribution DAA.a D (see Figure/ 1 for an example), where D is some hidden direction distribution family. Item in the construction of hidden direction distribution family is to ensure each D:1.0 is consistent with some multiclass polynomial classification problem with de- gree (mm). Since for each E [h: 1], J; is a set of m disjoint intervals, we know there is a degree-2m polynomial p:(1) RR-- + such that pt(t) > if and only if E J:. On the other hand, since 4m = conv UAEKK-1 Jn is a finite
Lemma 5,4 (Distribution Projection). Let D be a hidden direction distribution family over Rd and let D E D be a distribution that is consistent with an instance of multiclass polynomial classification with RCN (DA. f .H). For
interval, there is a d polynomial Pa (t) : R + IR
such that (t) > if and only if & T.n. Since
6

---

SQ Hardness of Multiclass Linear Classification with RCN
every i E [k:, D (z y i) = =
a, a, ( (z).
6. Hardness of Multiclass Linear Classification Under RCN
Hus
Given Lemma 5.4, to upper bound the pairwise correlation, it is equivalent to upper bound XNi, (P,",, Us- ing the correlation lemma developed in (Diakonikolas &
In this section, we present our main hardness results for MLC. The proofs in this section use Lemma 4.4 to reduce the correlation testing problem (Definition 4.2) to the MLC learning problem, and construct a hidden direction distribu- tion family (Definition 5.2) via the hard distribution defined in Definition 5.5 for the correlation testing problem. We will carefully choose the parameters for the hard distribution A1.... A&-1 to invoke Proposition 5.6 and Theorem 5.3 to get SQ lower bounds for different learning guarantees.
Kane, 2022), as long as each A, has many moments close to those of a standard normal distribution, XN(O.)) (P'",, Pd is small and we are able to prove hardness result using Lemma A.4. This gives an overview of the second part of Theorem 5.3.
Construction of Hard Distributions In the rest of the section, we will construct the family of hard distributions A1,..., - By Theorem 5.3, we require A Ak-1 to be supported in disjoint intervals and have many moments close to those of a standard normal distribution. The most natural construction of one such distribution is to restrict (0, 1) over a sequence of discrete intervals. Related ideas have been used in proving hardness result of various learning problems, such as (Bubeck et al., 2019; Diakonikolas & Kane, 2022; Nasser & Tiegel, 2022; Tiegel, 2024). By choosing such a distribution as A1. we are able to construct A2.... 1 by shifting the intervals constructed in A with different step sizes. Such a construction can be viewed as a generalization of the technique in (Nasser & Tiegel, 2022) for proving SQ-hardness of learning a halfspace under Massart noise. We present the formal construction of our hard distributions in Definition 5.5 and list its properties in Proposition 5.6. We defer the proof of Proposition 5.6 to Appendix C.3.
Here we first present the intuition behind the proof of our hardness results. As we discussed in Section 5, to prove the hardness result, it sufficient to construct a hidden di- rection distribution family D = {DA JUES" consistent with a multiclass polynomial classification instance in R such that the base distributions A A have many moments that are close to those of standard normal. Re- call that the construction of a hidden direction distribution family relies on a noise matrix H that satisfies the SQ-hard to distinguish condition (Definition 4.1). As an example, consider the noise matrix
0.6
0
0.4
H
0
0.6
0.4
0.3
0.3
0.4)
with k = 3, where ha (hr +22)/2. Therefore, we choose
base distributions A1, A2 constructed in Definition 5.5, a (1/2, 1/2) and fxxx) argmax (pr (2),,2(1)) (2(1)), lustrated in Figure 1. Recall that the goal of the correla- tion testing problem is to tell whether the label y is gen- crated according to the discrete distribution hş or is gen- erated by some D By Lemma 4.4, for every D E D H₃₃) Pr(S)), the
il-
Definition 5.5. For d > 0 such that d - 4(K-1)), 4(k- 1) < 1, we define
8 G(x) - E [nd - n, + E
GAE= = Σ nEZ 25
2o == (k) - opt = Σド probability mass of Lin. the intervals in the middle as shown in Figure 2, with respect to A1. This implies that the larger a is chosen, the better learning guarantee we can rule out. In particular, since Hjj Hjk, [k: 1h-1 1] is larger than some universal constant, a is proportional to Σラ= Pr(Sy)- By the construction of A1..... As-1, this quantity is exactly PRæ~A, (a E 4in) = Pr (2 e I., [12) < (m + 1)8). Since A₁ is an approximation of a standard normal, the parameters m, 5 of Ai are selected such that pr (12) S md) xx a. On the other hand, by Proposition 5.6, for a given pair of m, 8, by properly choosing small &, one can make the accuracy parameter T in Theorem 5.3 as small as exp(-poly(1/0) this does not imply that we can choose 8 arbitrarily small for the following reason: to solve the polynomial classifi- cation problem in RV-V we need to embed the instance to Rd d = N0(m), and solve it with an algorithm for MLC. Therefore, if is chosen too small, m could be too large to rule out any hardness result for MLC That is, a good
and G(n) = -Gs.// ||Gs/|ll.lll where G(x) is the density of (0, 1). We define (x = Glad and for i E [k- - 1). we define
A.(x) A1 + 4 - 1)E) |x| S md + (4i 3){
(1)) |x| > mō + (4i - 145-
where E Zz.
Proposition
5.6. The univariate distributions A Ak-1 constructed in Definition 5.5 satisfy
1. 3 a set of m disjoint intervals Jr i E [k- - 1] such that A,(x)= > 0, for x E J, and A₃(x) = 0, for x E Iin \
However,
Jz, Inn = conv U
2. Va E RR \ Lin, A,(x= Ay(x), Vi, E 111
3. For i E [K - 11, XN (4,, A,) < 0(6/E)2
4. For t E N and for E [k - 11. E x² rel= 1
O(t)) exp( (xp(-(((188)) + 4(k T) + 2m8)
7

---

Hardness of Approximation and Beating Random Guess Given the hardness result in Theorem 6.1 of getting error opt c,, one natural question is what kind of error guarantee we can efficiently achieve for MI.C. For larger values of i and small separation min H,; Hay. we show it is also hard to get any constant factor approximation, or even find a hypothesis with an error nontrivially better than random guess given opt = (l)/)). Formally, we first give the fol- lowing theorem, whose proof is deferred to Appendix D.2. SQ Hardness of Multiclass Linear Classification with RCN
tradeoff' between m, 8 is needed prove our hardness result.
Recall that for hidden direction distribution family D, errp (k: 1 - 1/k Ç. no matter if D Do D D. Thus, if we can learn a hypothesis with error 1 - 1/k o(1), we are able to solve the correlation testing problem. To make this possible, we need to make opt as small as possible. By our construction, if an x has ground truth label (*) E [k- 1], the probability that it is flipped is only 1/k + <. Thus, if we are able to choose > Zj=1 Pr(S,) = Pr(Im) = 1 11/poly(A)), then opt = ( By the tail bound of ((, 1), to make this hold, we choose mò = @(vlog k). Recall that we still need to make m. the degree of the polynomial we use, as small as possible. Here we choose super-polynomial SQ lower bound.
Hardness of Getting Error opt + e Recall that for binary linear classifiers, there is an algorithm that runs in time poly(d, 1/c) and outputs a hypothesis with er- ror opt + c. Moreover, the algorithm works even when minizy HR H 0. As it turns out, this is not the case for the multiclass case. Our first SQ-hardness result shows that even if k 3 and mins,j Ha Hij > for some constant e, to learn a hypothesis up to error opt + e, one needs super-polynone tablish the following Theorem 6.1, whose proof is deferred to Appendix D.I.
SQ complexity. Formally, we es-
O log k). which suffices to give
Theorem 6.1. There is a matrix H E [0. 1]3x3 with Hş; Hi 2 0.1, vi 4 j E [3], such that any algorithm A that distribution--ree learns multiclass linear classifiers with RCN specified by H on R2 error opt t, E (0. 1). requires either (a) at least (oog 2.05 (10))/ (d)/c2.26) queries, or (b)
Given Theorem 6.2, we immediately obtain two corollar- ies for the hardness of approximate leaning and beating a random guess hypothesis respectively in the setting of mul- ticlass linear classification. We defer the proof's of these two corollaries Appendix D.3.
a query of tolerance at most 1/d 1000 "5 (d)/e
Corollary 6.3 (SQ hardness of Approximate Learning). For any C > 1, there exists noise matrix H E [0, 1|kx,, with k = OC) and mins,3 HA, - Ha, (21/C) such that any SQ algorithm A that distribution-free learns multiclass linear classifiers on Rdd with RCN parameterized by H to error Copt given opt = ((1/C) either
The proof of Theorem 6.1 follows the above intuition. To show that learning up to error opt + e is hard, we choose parameters m, 8 such that Pr(Tin) x c. By the concentra- tion properties of N (O, 1), we only need to choose mó se e. In the proof, we show that m = evN suffices to give a super-polo soper-polyyomial lower bound.
(a) requires at least Mog d) queries, or
(b) requires a query of tolerance at most 1log 29 d),
Corollary 6.4 (SQ hardness of Beating Random Guess). For any k E 2 and k 2 3, there is a noise matrix H e [0, 1]k* with ming, Hes - Hi, = 1 /pooy(d) such that any SQ algorithm A that distribution-free learns multiclass linear classifiers on IRd with RCN parameterized by H to error 1 - 1/k - 1/poly (d) given opt O(1/k) either (a) requires at least d0 19 d) queries, or (b) requires a query of tolerance at most 1/ 1lo000 d)
Theorem 6.2. For any k. E. and k 2 there is noise matrix H E [0, 1](*k such that jaxi,j Hi,5-Hi Hag = { 0 and has the following property: For any sufficiently large E Z,, any SQ algorithm A that distribution-free learns multiclass linear classifiers with RCN specified by H on Rd to error 1 - 1/k - < - 22u requires either (a) at least q queries, or (b) a query of tolerance at most p. where min(g, 1/1²) = Afllog ".5 d). In particular, this holds even
It is worth noting that if we predict the label of an example with y E [k]] uniformly at random, then the error is always 1/k. Therefore, Corollary 6.4 implies that it is not possi- ble for an efficient SQ algorithm to output a hypothesis with error nontrivially better than a random guess hypothesis.
7. Conclusion
ofo 2 1/k + + 1/k3.
We conclude this paper with a conceptual implication of our results. Our SQ lower bounds exhibit the existence of very simple multi-index model that is easy to learn with perfect labels, but is hard to learn even with a small level of random label noise. Finally, we remark that the results of our work motivate several interesting directions, including the algorithmic study of MLC with more structured noise or structured marginal distributions.
Given le E 24 and 2 3, we construct the corresponding noise matrix H as
k-1
$ + 9
1-
E +
1
H
8

---

SQ Hardness of Multiclass Linear Classification with RCN
Acknowledgement
IEEE 58th Annual Symposium on Foundations of Com- puter Science (FOCS), pp- 73-84, 2017.
Ilias Diakonikolas was supported by NSF Medium Award CCF-2107079 and an H.I. Romnes Faculty Fellowship. Mingchen Ma and Christos Tzamos were supported by NSF Award CCF-2144298 (CAREER). Lisheng Ren sup- ported in part by NSF Medium Award CCF-2107079.
Diakonikolas, I., Kane, D., and Tzamos, C. Forster decom- position and learning halfspaces with noise. Advances in Neural Information Processing Systems, 34:7732-7744, 2021.
Diakonikolas, I., Kane, D., Manurangsi, P., and Ren, L. Cryptographic hardness of learning halfspaces with Mas- sart noise. Advances in Neural Information Processing Systems, 35:3624-3630 2022.
Impact Statement
This work is theoretical in nature and focuses on advanc- ing fundamental knowledge. As such, does not directly raise any societal ethical concerns that warrant special consideration.
Diakonikolas, I., Kane, D., and Ren, L. Near-optimal cryp- tographic hardness of agnostically learning halfspaces and relu regression under gaussian marginals. Interna- tional Conference on Machine Learning, pp. 7922-7938. PMLR, 2023a.
References
Aly, M. Survey on multiclass classification methods. Neural Netw, 19(1-))22 2005.
Diakonikolas, I., Tzamos, C., and Kane, D. M. A strongly polynomial algorithm for approximate forster transforms and its application to halfspace learning. In Proceed- ings of the 55th Annual ACM Symposium on Theory of Computing, pp. 1741 2023b.
Angluin, and Laird, P. Learning from noisy examples. Machine Learning, 2(4):343-31) 3700, 1988.
Beygelzimer, A., Pal, D., Szorenyi, B., Thiruvenkatachari, D., Wei, C.-Y., and Zhang, C. Bandit multiclass linear classification: Efficient algorithms for the separable case. In International Conference Machine Learning, pp- 624-633. PMLR, 2019.
Duan, K.-B. and Keerthi, S. S. Which is the best multi- class svm method? empirical study. In International workshop on multiple classifier systems, pp. 278-285. Springer, 2005.
Blum, A., Frieze, A., Kannan, R., and Vempala, S. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica, 22:35-52, 1998.
Dunagan, and Vempala, S. A simple polynomial time rescaling algorithm for solving linear programs. In Pro- ceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 315-320, 2004.
Bourel, M. and Segura, A. Multiclass classification methods in ecology. Ecological Indicators, 15:1012-1 2018.
Feldman, V. Statistical query learning. In Encyclopedia of Algorithms, pp. 2090-2095. 2016.
Brennan, M., Bresler, G., Hopkins, S., Li, J., and Schramm, T. Statistical query algorithms and low-degree tests are al- most equivalent, arXiv preprint arXiv:2009.0611
2020.
Feldman, V., Grigorescu, E., Reyzin, L.., Vempala, S., and Xiao, Y. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2):8118:377 2017a.
Bubeck, S., Lee, Y. T., Price, E., and Razenshteyn, I. Ad- versarial examples from computational constraints. In International Conference on Machine Learning, pp. 831- 840. PMLR, 2019.
Feldman, V., Guzman, C., and Vempala, S. S. Statistical query algorithms for mean vector estimation and stochas- tic convex optimization. In Klein, P. N. (ed.), Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 pp. 1265-1277. SIAM, 2017b.
Daniely, A. Complexity theoretic limitations on learning halfspaces. In Proceedings of the figth- annual ACM symposium on Theory of Computing, pp. 105-117, 2016.
Diakonikolas, I. and Kane, D. Near-optimal Statistical Query hardness of learning halfspaces with Massart noise. In Conference on Learning Theory, pp. 4258 4282. PMLR. 2022.
Ghosh, A., Kumar, H., and Sastry, P. S. Robust loss func- tions under label noise for deep neural networks. In Pro- ceedings of the AAAI conference artificial intelligence, volume 31, 2017.
Diakonikolas, I., Kane, D. M., and Stewart, A. Statisti- cal query lower bounds for robust estimation of high- dimensional gaussians and gaussian mixtures. In 2017
Haussler, D. Decision theoretic generalizations of the PAC model for neural net and other learning applications. In- formation and Computation, 100:78-1 -500 1992.

---

SQ Hardness of Multiclass Linear Classification with RCN
Hopkins, S. Statistical Inference and the Sum of Squares Method. PhD thesis, Cornell University, USA, 2018.
Panca, V. and Rustam, Z. Application of machine learning brain cancer multiclass classification. In AIP Confer- ence Proceedings, volume 1862. AIP Publishing, 2017.
Hopkins, S. B. and Steurer, D. Efficient bayesian estima- tion from few samples: Community detection and related problems. In 58th IEEE Annual Symposium on Founda- tions of Computer Science, FOCS, pp. 379-390, 2017.
Patrini, G., Rozza, A., Krishna Menon, A., Nock, R., and Qu, L. Making deep neural networks robust label noise: A loss correction approach. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1944-19959 2017.
Hopkins, S. B., Kothari, P. K., Potechin, A., Raghavendra, P. Schramm, T., and Steurer, The power of sum-of- squares for detecting hidden structures. In 58th IEEE Annual Symposium Foundations of Computer Science, FOCS, pp. 720-731. 2017.
Platt, J., Cristianini, N., and Shawe-Taylor, J. Large margin dags for multiclass classification. Advances neural information processing systems, 12, 1999.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory algorithms. Cambridge university press, 2014.
Hsu, C.-W. and Lin, C.-. A comparison of methods for multiclass support vector machines. IEEE transactions on Neural Networks, 13(2):415-425, 2002.
Tewari, A. and Bartlett, P. L.. On the consistency of multi- class classification methods. Journal of Machine Learn- ing Research, 8(5), 2007.
Huang, G.-B., Zhou, H., Ding. X., and Zhang, Extreme learning machine for regression and multiclass classifica- tion. IEFE Transactions on Systems, Man, and Cybernet- ics, Part B (Cybernetics), 42(2):513-529 2011.
Tiegel, S. Hardness of agnostically learning halfspaces from worst-case lattice problems. In The Thirty Sixth Annual Conference on Learning Theory, pp. 3029-3064. PMLR, 2023.
Kakade, S. M., Shalev-Shwartz, S., and Tewari, A. Effi- cient bandit algorithms for online multiclass prediction. In Proceedings of the 25th international conference on Machine learning. pp. 440 447, 2008
Tiegel, S. Improved hardness results for learning intersec- tions of halfspaces. arXiv preprint arXiv:2402.1599 15995, 2024.
Kearns, M., Schapire, R., and Sellie, L. Toward Efficient Agnostic Learning. Machine Learning, 155-41): 1994.
Van Rooyen, B. and Williamson, R. C. A theory of learn- ing with corrupted labels. Journal of Machine Learning Research, 18(228):1-50, 2018.
Kearns, M. J. Efficient noise-tolerant learning from sta- tistical queries. Journal of the ACM, 45(6):983-1006, 1998.
Wang, R., Liu, T., and Tao, D. Multiclass learning with
partially corrupted labels. IEEE transactions neural networks and learning systems, 29(6):2568-25 2580, 2017.
Kontonis, V., Ma, M., and Tzamos, C. Active classifica- tion with few queries under misspecification. The eighth Annual Conference Neural Information Processing Systems, 2024.
Zhang, M.. Lee, J., and Agarwal, S. Learning from noisy labels with change to the training process. In Interna- tional conference machine learning, pp. 12478. PMLR, 2021.
Lihong, 7., Ying, S., Yushi, 7., Cheng, 7., and Yi, 7.. Face recognition based on multi-class svm. In 2009 Chinese Control and Decision Conference, pp. 5871-5873. IEEE, 2009.
Lipton, 7.,, Wang, Y.-.., and Smola, A. Detecting and correcting for label shift with black box predictors. In International conference on machine learning, pp. 3122- 3130. PMLR. 2018.
Massart, P. and Nédélec, É. Risk bounds for statistical learning. 2006.
Nasser, R. and Tiegel, S. Optimal sq lower bounds for learning halfspaces with Massart noise. Conference on Learning Theory, pp. 1047-1074. PMLR, 2022.
10

---

SQ Hardness of Multiclass Linear Classification with RCN
Supplementary Material
Here we give an organization of the supplementary material. In Appendix A, we provide a complete list of preliminaries and notations and give more background about statistical query learning. In Appendix B, we present omitted proofs from Section 4. In Appendix C, we present omitted proofs from Section 5 and in Appendix D we give missing proof's in Section 6.
We want to remark that our SQ lower bound results have immediate implications to another well-studied restricted computational thael-that of low-degree polynomial tests (see (Hopkins & Steurer, 2017; Hopkins et al., 2017; Hopkins, 2018)). (Brennan et al., 2020) established that (under certain assumptions) an SQ lower bound also implies a qualitatively similar lower bound in the low-degree model. This connection can be used as a black-box box to deduce similar lower bounds for low-degree polynomials.
A. Complete Preliminaries and Notations
Let f*: : Xx + Y be the ground truth hypothesis. For j E [k)] denote by S; fxr (x) =
S Rd be the set of examples
with f*(x)= = j. Let h X - Y be an arbitrary hypothesis. For i, E [ke], we denote by Sys = f> (a) = j. h(z)
i S RR, the set of examples with ground truth label j. but on which predicts i. In this paper, we use gd-1 to denote the unit sphere in Rd Let K S I be any set, we denote by conv(K), the convex hull of K. For a noise matrix H E [0, 1|a we denote by h,, i E [b), the ith row vector of H.
For distribution D, we (x-n(()) to denote the expectation of D. Let D be a distribution of (s, y) over R4 x [k).. We use Dx to denote the marginal distribution of D over He and use D, to denote the marginal distribution of D over +1. In this paper, we will use N (0,, I) to denote the standard Gaussian distribution over Rd and use N0, 1) to denote the standard one-dimensional normal distribution. For (0, 1), we use G(z) to denote its density function and use Yr, t E N to denote its standard (th moment E Ez-)( x².
Definition A.1 (SQ Model), Let D be a distribution over X Y. A statistical query is a bounded function q : x Y - 1-11]. We define (T) to be the oracle that given any such query q. outputs a value v such that |u ((r.)))D(((z, v)]l S r, where 7 > is the tolerance parameter of the query. A statistical query (SQ) algorithm is an algorithm whose objective is to learn some information about unknown distribution D by making adaptive calls to the corresponding STAT(T) oracle.
Definition A.2 (Pairwise Correlation). The pairwise correlation of two distributions with probability density function Di, D2: Rd + R,, with respect to a distribution with density D Rd + R,, where the support of D contains the support of D1 and D2, is defined as (D( D2) == Sg Dx(x)Dx(x)/D(xx dx - 1. Furthermore, the X x-squared divergence of D to D is defined as x" (D,, D) = (D1,
Definition A.3 (Statistical Query Dimension). For 8, 7 > 0, decision problem B(D,D) where D is a fixed distribution and D is a family of distribution, let s be the maximum integer such that there exists finite set of distributions DD C D such that DD is (y, -coorealed relative to D and |Dpl 2 s. The Statistical Query dimension with pairwise correlations (7, B) of B is defined to be and denoted by = SD(B, n, B). We say that a set of s distribution {DI,... .D.,...,D.) over IR is (7, corrrllllt relative to a distribution D if x (D:, D₃) S y for all + j. and (D D2) S 3 for i j-
Lemma A.4 ((Feldman et al., 2017a)). Let B(D, D) be a decision problem, where is the reference distribution and D a class of distribution. For Fo > 0, let s = SD(B, 7, 3). For any of 0, any SQ algorithm for B requires queries of tolerance most /T + 7 or makes at least sn/ 7) queries.
Fact A.5 (Fact 31 from (Diakonikolas & Kane, 2022)). For any constant 0 < 1/2, there exists set V C Cgddl such that V = (d) and for any u, E V, lu ol S c.
B. Omitted Proofs from Section 4
In this section, we provide the omitted proofs in Section
B. Proof of Lemma 4.3
We provide the full proof of Lemma 4.3 here and restate Lemma 4.3 as Lemma B.1 for convenience.
Lemma B.I. Let (D, f*, H) be any instance of multiclass classification with RCN, Let h X - Y be an arbitrary

---

SQ Hardness of Multiclass Linear Classification with RCN
multiclass hypothesis over X. Then,
err(h) Σ (1(S))(1-H)) +
Pr(S,)(H)) Hz.)
In particular, if H3j Hss 2 for every j E [k], i + j. then
opt crr(f Σ (r(s)) -H3)
Proof of Lemma 4.3. For j, E [b), let a E Agi be any fixed example. Consider two cases, where j = i and j * i. In the first case, we have
Pr(M(x) + v(()) Pr(u(s) # = Hzs-
In the latter case, we have
Pr(h(x) # v(x)) = Pr(y(z) *
Hyc.
Thus, we have
err(h) Pr(S))) v(x) Szi)= = ΣΣ Pr(S -H Hz))
j=1
j=1
Pr(S H + Pr(S;) - -E Pr((s))
(1 (1-Hj)) H3))
(2)
j=1 زt
Σ (1 HH,) + ΣΣ Pr(S Hzd)
j=1
Here, in the second equation, we use the fact that Pr(S,) Pr(S,) - Eij Pr(Sx), Vj [k]. Since Pr(Sş) 2 0, V. E [k), we know from (2) that err(h) > Σ Pr(S,)(1 H33); HB H5 2 0, Vi,j E [k). particular, by (2),
err(f*) Σラ= Pr(S,)(1- Hzg), which concludes
opt crr(f*) Σ Pr(S,) Hjj).
B.2, Proof Lemma 4.4
present the full proof of Lemma 4.4. We restate Lemma 4.4 as Lemma B.2
Lemma B.2. Let D be a family of distribution over X x such that each distribution D E D corresponds to a multiclass classification instance (D, f", H) that satisfies Definition 4. If there is statistical query learning algorithm A such that for every instance (D, f H), D E D, A makes q queries and each of them has tolerance т, and outputs a hypothesis such that crr(h) S opt + where
2a Σ Pr(S))HH, Hyz),
then there is statistical learning algorithm A' that solves the correlation testing problem defined in Definition 4.2 by making q 1 queries and each of them has error tolearance aainT,.a//))
12

---

SQ Hardness of Multiclass Linear Classification with RCN
Proof of Lemma 4, The algorithm A' works as follows. We run over D to get hypothesis h X Y. Given h, we make statistical query y estimate err(h) with tolerance a:/2. Denote by eir(h) the returned answer of q. We reject the null hypothesis cir(h) < H a/2 and accept the null hypothesis otherwise. The SQ complexity the algorithm directly follows its definition. In the rest of the proof, we prove its correctness.
If D Do. since the label is drawn independently from and Pr(y k) -.k Pr(y = Huj. Vj + k. any hypothesis h X + Y has
err(h) 2 err(k) = Pr(y *) H4k-
This implies that, eir(A) 2 1 HRR a/2 and A' will not reject the null hypothesis.
In the rest of the proof, we will show that if D E D, the algorithm A'' will reject the null hypothesis. To start with, we will show that opt is 2a far from 1 HaK- On the one hand, by Lemma 4.3, we have
err(k)= (r(S,)(1 Hzz)
Σ
Pr(S)))(Hs) Hsa)
j=1
1
Pr(S,)(1 - -Hx) + Pr(Sa)(1 - HRK)
5=1
Pr(S,)
= (1 Pr(Sk))
[1 Pr(Sk)) (1 Hsk) + Pr(Sk)( HKK)
(1 - Pr(St)
a5(1 Hzx)+ + Pr(Sk(( HRA) Σ Pr(S;)(1 HEs) 1 HRK-
Here, the second equation holds because by the definition of the constant hypothesis S₁ = =Skk: Vj E [k] and the fourth and the fifth equations are followed by Definition 4.1. On the other hand, by Lemma 4.3, opt Ei Pr(S,) 11zi). Thus,
1- Ha opt err(k) opt
Σ Pr(S))(1 H1g) + Σ Pr(A,)) HJN) Σ Pr(S,)(1 - H33) 2a,
5=1
which gives us that opt = 1 - Hks 2a. Given any hypothesis h output by with err(h) S opt + a, we have
err(h) < H&s a. Thus, eir(h) 2 HES 20x/2 and A' will reject the null hypothesis. This concludes the proof of Lemma 4.4.
C. Omitted Proofs from Section
C.1. Proof of Lemma 5.4
In this section, we present the proof of Lemma 5.4. For convenience, we restate Lemma 5.4 as Lemma C.I. Lemma C.1 (Distribution Projection). Let D be a hidden direction distribution family over Rdd and let D E D be a distribution that is consistent with an instance of multiclass polynomial classification with RCN (DAa, ff" H). For every i [k).
aj (x)()).
D (I
( y = =
H
1=1
Proof of Lemma 5.4. We consider the density function of D at fixed point (a, i),
カ-1 1
(z,( i) =
aj P. (r)
j=1
13

---

SQ Hardness of Multiclass Linear Classification with RCN
By Definition 5.2, we consider two cases for æ. In the first case, v. Je for some E 1]. By construction of the distribution family
= A ) P. (z) = 0, * Thus,
D (x, (x,
Σ j=1
aj ayP (1) (x)HH
a.P (x) Ea)Po
Σ ==1
aj P. (z)
j$l
In the second case, Lin and thus f*(x) k. In this case,
k-1 Σas (x) Hz) (c) (x,
k-1
k-1
= P. (z) HKi = PA Σ Hy = Σ ( j=1
Here, the second and the last equation holds because P. (a) is the same for every j E [k]] The third equation holds because
h2 = E}= hy. Since (D f H) satisfies Definition 4.1, we know that Pr(y = i) = Hig. Thus, Vo Rd.
a Hy (x) Haa
(x (r y= = i) =
Ø=1
C.2. Proof of Theorem 5.3
In this section, we present the proof of Theorem 5.3. For convenience, we restate Theorem 5.3 as follows.
Theorem C.2. Let B(Do, D) be correlation testing problem, where (Dn) = N(0, 1) and 'D is a hidden direction distribution family. Suppose there exists some >> such that for l S t E E4, the family of one-dimensional distribution A A satisfies EznA, x² Yeel= S v. Then,
1. every distribution a E D is consistent with instance of multiclass polynomial classification with RCN (DAa, H) with degree at most 2m that satisfies Definition 4.1.
2. for any small enough constant > O, let B = maxi, XN (As, Az) and let T == v22 + c.B. Any statistical query algorithm that solves B(Do, D) must make a query with accuracy better than 2 make ( queries.
Proof of Theorem 5.3. We first prove Item in Theorem 5.3.
Since for each i E [K- - 1]. J; is set of m disjoint intervals, we know there is degree-2m polynomial p:(() R - R such that (t) > 0 if and only if t E J;. On the other hand, since In, conv UjE(k-1] J is finite interval, there is degree-2 polynomial (t) R + R such that (t) > if and only if & I.n- Since J, J, 0. vi + We know that for each j [k- if v-r Jj. then j argmax [p: (v.z),... Pa (v-x)) and if v-x & lin. k = argmax (v- .... Pk (v-x)) in particular, Pr(u- x E I U, = 0 by the construction of the hidden direction distribution family. Thus. D. is consistent with an instance of multiclass polynomial classification with RCN (DA-a, f HH), where the marginal distribution is Σドー1 1 a, and the ground truth hypothesis (x) argmna((1) (v- (u-x),... x).... .D),..,,P.,, (v(u x)}. In particular, by the definition of (DA. 1 HT), it satisfies Definition 4.1.
Next, we prove Item 2 in Theorem 5.3. Our proof strategy is to make use of Lemma A.4. To do this, we will bound XD, (D D for E S for pair of unit vectors v. For convenience, we mention the following lemma that will be used in the proof.
Lemma C.3 (Lemma 13 in (Diakonikolas & Kane, 2022)). Suppose there exists some such that for E < < Z,, univariate distribution A satisfies EZzA d "i v. then for every u, v Rdd with Iu vl less than a sufficiently small constant, we have
XN (PA, Pd) & Ju w1f X2, 1)) +
14

---

SQ Hardness of Multiclass Linear Classification with RCN
We start by upper-bounding the pairwise correlation XD. (DA Da.a). By Lemma 5.4, we know that for each i [k]]
agllيi pad (x) = Pe P Mhi
As
D
Hki
2=1
Since for each j E [/ 1), E x² rel S and
Σj=1
a;His Hai
1, we know that,
E
x²
YV
$ 14
2~ x~ Y==
My A3
for & S Thus, we obtain
k Xn. (D Daaa) = Σ HaIXDolV=i (DA-(xx 1yy = 8), (3t 1y 1)) = Σ
k
HAXXN(L.) (Di, D.)
i=1
k
نزلازة Aj, N(..1)
Hai
1² 12+10.01 x²
Hhi
1m1
agH Has
2² + 10 ull
H
Aj, N(0.
< 2 + 11 ul" B.
Here the first inequality holds because of Lemma C.3, and the last inequality holds as follows
ayHa Hui
H,
Az(x)
E
He Ae
A,, NO. =
j=
Hus
Hyi
dx
G(x)
a
H
ayHa
(,()) dx -1)
HEi
G(z)
h
agHic
(N(0.1) (Ai, S B.
HRi
HEs
Thus, for every u, u E gd-1 such that vo S c, we have Xo, (DA.a DA.0) s +ck =
Similarly, we upper bound x" (D4=), NO,,,),((O,)))) I)) as follows.
x2 (DA. (DA.,,N (N(,
( (x Ax y DA
1)
Haxx ((,,1)) Σ H
U Hui
A,, ...
s.B.
By Fact A.5, for any small constant e > O, there exists set S of (dc()) unit vectors such that for every u, U. E S, lu v Sc.
Thus, SD(B, 7, 8)- = 2P.(d) By Lemma A.4, we conclude the proof.
15

---

SQ Hardness of Multiclass Linear Classification with RCN
C.3. Proof of Proposition 5.6
In this section, we present the full proof of Proposition 5.6. For convenience, we restate Proposition 5.6 as Proposition C.4. Proposition C.4. The univariant distributions A...... Ak-1 constructed in Definition 5.5 satisfies
1. 3 a set of m disjoint intervals Jz, i [k- 1] such that A((x)) O, for Jg and A₃(x) 0, for Ten \ Jr, Iin conv UsE[k-1] Jj-
2. Vo E Imn A(x)) = A,(1), Vi,j [k- 1].
3. For i,j [ XNT0.1) (As A,) < ((8/E)²
4. For E and i [k- - 11. EE x² -ml S ((()))xx((-(p))) (xp(()(()(((())) + 4(A 1)E(1 + 2md)
Before presenting the proof, will be convenient to recall the following property proved by (Nasser & Tiegel, 2022).
Fact C.5. For ó, E > 0, |||Gs,ell+ - 1| s exp (-90(1699) [Gaaell 1 - 0(1) exp (-S((188)).
Proof of Proposition 5.6. We first prove the first two properties. For E [k: 1]. we define Jj == U- Ind - (4i
3)C, nō (4i [] Notice that Lin = conv Uj J = [-mó (4k - 7)5. mā E.. By construction, (x) = A)(x)
Iin- A1( > 0 if and only if x E J1. By construction for i E [k: - 1] and x E in. Ax(x) > 0 if and only if (x + 4(i - 1))g E J1, which equivalent to x E Jr. Since > 4(k 1).. we know that Jr n J3 = 0, A j. This implies that for every E [A: 1]. and x 4n (z > 0 if E J, and A₃ = =0
& Inn On the other hand, consider E Iin. For i = 1, and
a E Jj-
We next prove the third property. It is convenient to mention the fact that (A1(s),, 1)) 0 proved in (Nasser & Tiegel, 2022). For any pair of i, [k- 1]. we have
A,(z)A((z) dx - 1 / (2xx) dx + f A((x)A((1) G(
XN(0.)) (A,
dr
12 G(x)
Johnn
G(x)
A,())A((z)
S (A)))
dæ
ZETn G(x)
A,)))
dr.
G(z)
JaEln
Notice that i + j, then for each a E Lin, (x))A)(() = 0, which implies that
[ Jaehn G(z))
A,)))
dr
remains consider the case where j.. In this case, we have
(Z(z)
(4i- 5)E
A²(x)
(2)
m66-44i-5))
518
62 + 4(i - 1)E)
dr 2
Σ
dx 2
dr
G(x)
OSnSm no 11-044--0)) 3)8 G(z)
Gralll
G(x)
oSnsm no 118-(4i-36
n (Ai-5)E 1
(xr + 4(i 1)8)2
2
exp
E
||G&E oSnsm nó- (1i-3)
2T
2
1
1
(xr + 4(i - 1)E)2
<
2
|[Gs.lll JOER v
2n
exp
2
exp((4(i- s 0(1)
Here, the last inequality holds when g $ 1/k. Thus, for i E lh 1), XN(O.1) (Ai, 5
S ((6/E)2.
16

---

SQ Hardness of Multiclass Linear Classification with RCN
Finally, we prove the last property. It is convenient to mention the fact that [ENAA x² - 7il S O(I)) exp( exp(-)(116))), proved in (Nasser & Tiegel, 2022), which implies that it suffices to upper bound [Eznd x² E x² We have
E A
x²
E z~
x.
x x'd - SSE... x'dA,(a)
JEEE
=
1/
x'dAi(z)- - JEEl (xr - 10:-4(111-5 (1))))
DELI
((x - 4(i 1)E)( -x") 1 Σ (2) (4(k: -1)))1))) S $4(1= - 1)5 Σ (1)
( x'-
S sup zELu
1=1
< 4(k 1) + |z|)* & 4(k - 11) + 2mm)².
This concludes the proof of Proposition 5.6.
D. Omitted Proofs from Section 6
In this section, we provide the omitted proofs in Section 6.
D.1. Proof of Theorem 6.1
We present the full proof of Theorem 6.1. For convenience, we restate Theorem 6.1 below.
Theorem D.1. There is a matrix H E [o, 113x3 with Hü; H₂j 2 0.1, + j E [3] such that any algorithm A
that distribution learns multiclass linear classifier with random classification noise specified by H on R to error opt + c, E (0, 1) either
(a) requires at least (0og "8 (d)/c".0)) queries, or
(b) requires a query of accuracy at least d d00 (d)/e)
Proof. Consider following noise matrix,
0.6
0
0.4
H
0
0.6
0.4
0.3
0.3
0.4)
Notice that one can reduce learning polynomial classifiers with RCN to MLC with RCN using the Veronese mapping. Suppose we have an algorithm .A for solving multiclass linear classification problems. Then given an input distribution D of (x., over N [k:] consistent with an instance of multiclass degree-m polynomial classification problem. We apply the Veronese mapping V(x)= (I,, 1) 1)@m on x. The distribution of (V(x),,) v) over R( ((N+1))(() x [k]] is consistent with an instance of MLC with RCN specified by H. Therefore, to get an SQ lower bound for MLC over RR it suffices for us to give an SQ lower bound for learning degree-m polynomial classifiers over R.N, where d = N0
Furthermore, by Lemma 4.4, to get the SQ lower bound for learning polynomial classifiers, suffices for us to give an SQ lower bound on corresponding testing problem. Therefore, we construct a distribution family of joint distributions of (a, v) over R [k] such that each distribution in D is consistent with multiclass polynomial classification problem with RCN (D, f*, H) required by Lemma 4.4.
The construct D the hidden direction distribution family defined in Definition 5.2. We choose An and Ag as specified in Definition 5.5, a = (1/2, 1/2). Since the noise matrix H satisfies h13 = (h, + h2)/2, by Theorem 5.3, we know that each distribution is consistent with an instance of multiclass polynomial classification problem with degree-O(m) with RCN specified by H. To make use of Theorem 5.3 to get an SQ lower bound, it remains to choose parameters for A1, Ag such that it is hard solve B(D,, D).
Fix any small enough constant >> 0. We choose the parameters m, 8 such that mo By Proposition 5.6, we know that for every E N, we have
E B~
x 70 O(t)) exp (-1((188)) + 12 + 2md)*
5 0L)) (exp (og)() 2((18))) + exp((et))
17

---

SQ Hardness of Multiclass Linear Classification with RCN
We choose 8 1/VN, Nv and { exp(-2220.p)) For any 1 No.99, have
E x² BMdd
I (exp (t (og(() 2(1/62)) + exp((t)
S {exp(-A(NN) + exp( 2N + Nu.000 = exp( exp(-I((NU.0)) =; V.
By Lemma 4.4, we know that any statistical query learning algorithm that learns , ,f, H)) up to error opt + where 1 H33) Pr(S}) can solve B(Do, D). By the construction of D and H,
m8+5 8 1
0.1 Pr E Im) 0.1 gndd
E
G(z)dr
no-E & E|GGs
má+e
5 G 2 2(1)
2 1()
Σ
E -mEnsm
2E( G((mm) 2 (21)(2m + 1) 2(())
n5-g
Here, the first inequality holds because of Fact C.5, the second inequality holds because G(z) is decreasing with respect to |x|] and the last inequality holds because e = md. This implies that any statistical learning algorithm that learns the multiclass polynomial classification problem (DA.e, f", H), E S up to error opt + (c) must make at least 20(N) statistical queries or a query with accuracy better than exp(=9((No.00).
Finally, conclude the proof of Theorem 6.1 by embedding the multiclass polynomial classification problem (DA-e, ft, H), E SN-1 into Rd, d = O(N*) multiclass linear classification problem via choosing properly. By choosing m ev N, we obtain that
log(d) (m lo)))) = (lg)))og(NN).
log(N)).
any statistical learning algorithm that learns the multiclass linear classification problem over IR up to error opt + O(c) must make least
exp(0((0000)) 000N00000000000000000000000 (lg(d)) df0llogg 08 (d)/e" 1.00
statistical queries or a query with accuracy better than exp(-9((N0.00) d [i(log 36 (1)/
D.2. Proof of Theorem 6.2
We give the proof of Theorem 6.2 below. For convenience, we state Theorem 6.2 Theorem D.2.
Theorem D.2. For any ls E 24 and l 2 3, there is a noise mutrix H E [0, 1j such that maxi. H HA, = Ç and has the following property: For any sufficiently large d Z.,, any algorithm A that distribution learns multiclass linear classifier with random classification noise specified by H on Bd error 1 1/k C S-2p. 2p either
(a) requires at least q queries, or
(b) requires a query of tolerance at most p.
where min (q. 1/12)) = Alogg 0.99 d), In particular, this holds even opt < 1/k + < 1/K3.
Proof of Theorem 6.2. Given & E Z, and k: 2 3, we construct the corresponding noise matrix H as
(k 1)/k -
0 (k: - 1)/k - -C
1/k + 5 1/k + C
H
1/k c/(k-/
1/k c/(k 1)
1/k+C)
18

---

SQ Hardness of Multiclass Linear Classification with RCN
Namely, for all E [k - 1,, the ith row is defined as Ha, = (k- - 1)/k H4, 1/k Ç and H4s 0 for any j such that j # and j * k. Then the kth row is defined as HR,A = 1/k + < and Hk.j 1//: C/k for any j * k.
Given the noise matrix H, we will construct a hidden direction distribution family D over IN that is consistent with a family of multiclass polynomial classification problems with RCN (DA.a,
using polynomials of degree (m)) for some m to be determined later and prove the SQ hardness for these multiclass polynomial classification problems. Given the hardness, the hard instance of multiclass linear classification problems with RCN, would be an instance in I& where = (O(m)) of the form (z). y), (I. y) DA.a, where (z) RN + R defined as M = [x, 1] 118m is the degree-m Veronese mapping that maps a vector x' E R to monomials of degree at most m.
To start with, we construct the hidden direction distribution family D using the distributions AI,..., Ak- constructed in Definition 5.5. Notice that H satisfies Definition 4.1 because hą- = Eie(k-1] azh, where 0; = 1/(k 1) for all i. We know from Theorem 5.3 that for every A (a,....,AA-1). where A1....: AR-1 are one dimension distributions constructed in Definition 5.5, D (DA.a) Jues==1 is a hidden direction distribution family consistent with family of multiclass polynomial classification problems with RCN (DA,,, ,f", H) using polynomials of degree O(m). Now, we
choose parameters for Al,..., A such that it is hard to solve , D).
We will choose d = 1/VN. & = exp(-N0.99 log k) and m = [CV//o K/07, where C' is a sufficiently large constant. By Proposition 5.6, we know that for every t E N, we have
E A~
x²
-
Yt
S (tt) exp (-1(1188)) + +12E(1 + +mm))*
s 0 exp (epp (1lo(()) - 22) + (exp((v/ogkk)
Therefore, we get for any S N7.90
E x² A-
78 S 0 (xxp (tlog( - 2((162)) + E exp(tt/log k:)
S <ex((-((N)) + exp(-No.0 log k No.98 v log k) exp(- exp(-S((NV.900)
By Proposition 5.6, we know that
B = max (N (A:, A,) 0(8/E)² = exp(O log k)).
This implies that (we take the constant in Lemma C.3 as c_ > k10
T 22 + c < expp(2Q(NO)) + exp( exp(-2((v0.90 log k)) = exp(- cxp(-9((v0.00))
By Theorem 5.3, we know that to solve the correlation testing problem B(Do, D). one need at least 20e(N) = (N) (given N is at least a sufficiently large constant depending on N) statistical queries or query with accuracy better than Furthermore, since N is at least a sufficiently large constant depending on kt the lower bound on
2/T = exp( (( the number of queries is (Nx(N) 2 20(N")) where we simply take No.01 2 c(k) and c(k) is the constant factor in (N) that depends on k.
Notice that by Lemma 4.3, for any D D. we have
opt = -11/ + 5) Pr It E mo]] + ((k- - 1)/k- - 5) Pr It (-oo, -mo - -8/2] U [mo + 5/2, oc) I~G8.
<(1/k + () + Pr EL -mo 6/2] U |mn + 0/2, [c)]
-md
INGG.
lô+E (t.g(t)dt
+() Σ
15-5
<(1/k + ()+ + 2 Pr
It 2 mō) = (1/k +) + 1/poly(k).
On the other hand, if the input distribution is Do, then every hypothesis h has an error
D (h) 2 (1/h + () 1/k C.
19

---

SQ Hardness of Multiclass Linear Classification with RCN
Therefore, any algorithm for learning multiclass polynomial classification with RCN matrix H and achieving an error better than 1 - 1/k Ç 2μ be used solve B Po; D) with one more query with accuracy 2μ. Thus, any such algorithm must either uses q queries or a query of tolerance at most μ4, where = 1/p- = 20(A4.000)
Finally, we conclude the proof of Theorem 6.1 by embedding the multiclass polynomial classification problem (DA-", H), e into Rd d ON as multiclass linear classification problem and rewrite. Given d O(N"), we get that 20(A4
, 69 /m) / 49 /(e/log k)) 2 _ 2 d " 2 d d)..), Therefore, any statisti-
cal learning algorithm that learns the multiclass linear classification problem over IR to error (1/k + () 1/k - (even given opt & 1/k + Ç + 1/poly(k)) must make at least d(((Igg))))) statistical queries or query with accuracy better than d' (((o d)
D.3. Proof of Corollary 6.3 and Corollary 6.4
We present the proof of Corollary 6.3 and Corollary 6.4. For convenience, restate Corollary 6.3 and Corollary 6.4 as Corollary D.3 and Corollary D.4 respectively.
Corollary D.3 (SQ hardness of approximate learning). For any C > 1, there exists a noise matrix H [0, 1| where k= O(C) and mins.j H - Hi, = Q(1/C) that has the following property: For any d E Z+ that is at least sufficiently large constant depending on o, any algorithm A that distribution-free learns multiclass linear classifier on Bd with RCN parameterized by H to error Copt given opt = 2201000(1/) (C)/C) either
2.90 90 d) queries, or (a) requires at least (logg
(b) requires a query of tolerance at most 1/000og0.00 d),
Proof. This directly follows from Theorem 6.2, where we take h = [3C] and Ç 1/(100k). Then we have opt 1/k+ = /k + 1/k², An algorithm that achieves error aopt given opt O(1/C) will in this case, output a hypothesis with error aopt I (k/3)opt $ 2/3. Notice that the SQ lower bound in Theorem 6.2 holds against any algorithm that outputs a hypothesis with error at most 1 - 1/k - S 1/poly(dd) = 1 - 1/k - 0.01/k /k 1/poly(d) 2 2/3. This completes the proof.
Corollary D.4 (SQ hardness of beating random guess). For any k E N and k 2 3, there is a noise matrix H E [o, 1| that mins.j H.,- Hi, = ((/d)) and has the following property: For any d E Z, that is at least sufficiently large constant depending on k; any algorithm A that distribution-free learns multiclass linear classifier on Bdd with RCN parameterized by H error 1 1/k 11 (/) given opt (1/kk) either
(a) requires at least (llg.. d) queries, or
(b) requires a query of tolerance at most 11a00002000 d)
Proof. This directly follows from Theorem 6.2. Suppose that there is an algorithm achieving error 1/k 1/d" for any c 0. Then take -= 1/(2d)) Given d is a sufficiently large constant depending on k. it is easy to check that opt 1/k + 1/k3 = 1/k + 1/2d" + 1/k.3 O(1/k). Furthermore, the SQ lower bound holds against any algorithm that outputs a hypothesis with error at most 1 1/k < 1 1/poly (d) = 1 1/k: C - 27 2 1 - 1/k 1/d", where the last inequality follows from - (Boggg 09 This completes the proof.
Remark D.S. We want remark that in Corollary 6.4, to rule out an efficient learning algorithm that has a better error guarantee than 1 1/k, any choice of ( = o& (1) is sufficient, and the separation minigj Hü; Hig of H is in fact O()).
20


Reviews:
[{"review_id": "Irl3iEyHbU", "reviewer": "Reviewer_8DF6", "summary": "The paper studies linear multiclass classification under random classification noise within the statistical query (SQ) model. It considers a setting with positive noise separation, meaning that for a given labeled pair $(x, f^{\\star}(x))$ under the ground truth labeling hypothesis, the probability of correctly observing the label $y = f^{\\star}(x)$ is strictly greater than the probability of observing any incorrect label $y \\neq f^{\\star}(x)$. The paper establishes a superpolynomial lower bound on the number of queries required for any SQ learner. Additionally, when the number of labels is large, it provides a superpolynomial lower bound for approximate SQ learners or SQ learners that outperform random guessing.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for appreciating our theoretical results and for pointing out typos in the manuscript. We next respond to the comments from the reviewer as follows.\n\n>Definition of $H$ in the proof of Theorem 6.2: \n\nWe want to thank the reviewer for pointing out this typo in the submission. The correct definition is as follows: the last row of H is defined as $H_{ki} = 1/k - \\zeta/(k-1)$ for $i<k$ and $H_{kk} = 1/k+\\zeta$. \nWe will fix this minor issue in the revised version of the manuscript.\n\nImportantly, we want to emphasize that this typo does not affect the correctness of Theorem 6.2 and its corollaries for the following reasons. \n\nFirst, for any noise matrix $H$ that satisfies the SQ-hard to distinguish condition (Definition 4.1), we construct a family of hypothesis testing problems in a black-box way. The lower bound on the running time (number of SQ queries) for such a hypothesis-testing problem only depends on the parameters of the hard distributions defined for this hypothesis testing problem (Theorem 5.3). The choice of the parameter $\\zeta$ only affects the final error guarantee that can be ruled out by our hardness result—but does not affect the lower bound on running time for the corresponding hypothesis testing problem. So, even setting $\\zeta=0$ does not affect any proof; moreover, the big-O notation does not have any hidden dependence on $1/\\zeta$. Specifically, in Theorem 5.3, the lower bound is $\\Omega_c(N) = C(c) N$, where $C(c)$ is a number that only depends on the parameter $c$ used to calculate $\\tau$ in the statement of Theorem 5.3. Using Theorem 5.3 we prove Theorem 6.2. Importantly, in doing this, no matter which $\\zeta$ we choose in the definition of $H$, we always choose the constant $c=1/poly(k)$. This gives us an SQ lower bound of $2^{\\Omega_k(N)}>2^{\\Omega(N^{0.99})}$ when $N^{0.01}$ is larger than $C(k)$ in the hidden constant. In summary, the proof of the lower bound is correct as is. Second, as we mentioned earlier, the choice of $\\zeta$ only affects the final error guarantee that we can rule out. In particular, either opt or the error guarantee is calculated with respect to $1-H_{ii}$, as we did in line 1031 and line 1043. Luckily, despite the typos for $H_{ki}$ for i<k in the definition of H, the values of the diagonal elements $H_{ii}$ are correct. In summary, the final error guarantee we rule out remains correct as is.\n\n>Possible positive results on MLC with RCN:\n\nWe first want to point out that although our paper is the first paper that establishes a computational hardness result for MLC with RCN, as mentioned in the introduction of our paper, there exist many prior works that study this problem both empirically and theoretically from an algorithmic perspective. Specifically, when the noise matrix H is invertible, one can invert the noise matrix H and reduce the problem back to MLC in the realizable setting. These methods work well if H is well-conditioned; for example, when $H_{ii}>2/3$, inverting $H$ is easy and will not affect the learning task by much. However, these methods fail if H is ill-conditioned; in fact, we show that in the distribution-free setting the problem is provably computationally hard. As we point out in the conclusion section, there are several interesting directions that can be explored with respect to positive results. These include MLC with RCN under well-behaved marginal distributions, and MLC with RCN for more structured noise matrices. Positive results in these directions are beyond the scope of this paper.\n\n>Phase transition for $\\sigma$:\n\nWe start by pointing out the following: since the choice of $\\sigma=0.1$ gives a hard noise matrix for $k=3$, one can easily obtain a hard noise matrix with $\\sigma=0.1$ for any $k>3$. Specifically, this can be done by concatenating this $H$ (for $k=3$) with an identity matrix with size $k-3$. That is, it is not the case that the separation needs to be small in order to make the hardness result work for large $k$. On the other hand, we believe that there is a threshold $\\sigma$ such that this phase transition happens. For example, if $\\sigma=2/3$, then $H$ is well-conditioned (i.e., has no small eigenvalues), and (as was pointed out in prior work and mentioned above) \nwe can invert $H$ to get a computationally efficient algorithm. However, the actual running time of such algorithms scales polynomially with the inverse of the smallest singular value of $H$ instead of the separation parameter. It would be interesting to understand this phase transition phenomenon more deeply \nand precisely characterize this threshold–namely, whether $H$ is not invertible for some $\\sigma$, but we are still able to solve the problem efficiently.", "claims_and_evidence": "Possible issue with Theorem 6.2. See theoretical claims below.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Yes, I went through Theorem 6.2, Corollary 6.3, and Corollary 6.4 at a high level. \n\nI may be overlooking something, but I think there might be an issue in Theorem 6.2. Specifically, the sum of the entries in the $k$-th row of the noise matrix $H$ does not seem to add up to $1$. Instead, it sums to  \n\n$$ 1+ \\zeta - \\frac{(k-1)}{k} \\zeta = 1+\\frac{\\zeta}{k}. $$  \n\nThis defines a valid matrix only if $\\zeta = 0$. I believe the intended definition of $H$ was  \n\n$$ H_{kj} = \\frac{1}{k} -\\frac{\\zeta}{k-1} \\quad \\forall j < k, \\quad \\text{ and } \\quad H_{kk} = \\frac{1}{k} + \\zeta. $$  \n\nI briefly reviewed the proof of Theorem 6.2 and did not see any immediate step where division by $\\zeta$ would cause the proof to break. However, given that the proof involves asymptotic bounds with $O(\\cdot)$ and $\\Omega(\\cdot)$ notation, it is unclear whether some of the hidden constants depend on $1/\\zeta$. I would appreciate it if the authors could verify whether this issue has a straightforward fix or if it presents a more fundamental problem.  \n\nAt the very least, it is evident that Corollaries 6.3 and 6.4 do not hold for $\\zeta = 0$, as those proofs explicitly assume $\\zeta$ is a nonzero constant.\n\n\n\n\n\n$\\textbf{Given this issue, I am recommending a rejection. However, I am happy to engage with the authors during the rebuttal and change my recommendation if a minor fix is provided. }$", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "There is a growing body of research showing that the statistical landscape of multiclass learning can differ significantly from binary classification, especially as the number of labels increases. This paper contributes to this literature by highlighting a key difference that also considers the computational landscape.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I think this is a strong paper that establishes several interesting results. And the paper does a good job of conveying the intuition behind some of the constructions used in their lower bound proofs.  \n\nAs for potential weaknesses, given that this appears to be the first work studying linear multiclass classification with random noise from an efficiency perspective, it would have been valuable to include some positive results as well. See the questions below for further discussion on this point. But this is just a personal opinion, so I won't take this into account in my judgement of the paper.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "*(This question is only relevant if the concern I raised earlier about the proof has a minor fix.)*  \n\nIn the introduction, the authors mention prior work proposing methods whose time complexity scales inverse polynomially with the minimum singular value of $H$. In their intuitive discussion of the proof, they describe a matrix $H$ in Equation (1) with linearly dependent columns and a separation of $\\sigma = 0.1$. Based on this example, it seems that such a large separation is feasible only for $k = 3$, and as $k$ increases the separation has to grow progressively smaller for the lower bound to hold.\n\n\nThis suggests a possibility of a phase transition. Specifically, for each $k$, there might exist a threshold $\\sigma$—a function of $k$—such that if the separation is at least $\\sigma$, a polynomial-time bound is achievable. For sufficiently large $\\sigma$, it might be possible to establish a fixed lower bound on the smallest singular value in terms of $\\sigma$, which, combined with the existing results cited in the introduction, would imply the existence of an efficient algorithm.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fFrRuVtzEV", "reviewer": "Reviewer_Y6KY", "summary": "This paper is concerned with the task of multiclass linear classification (MLC) with $k$ labels under random classification noise (RCN). The problem parameters are a $k \\times k$ row-stochastic noise matrix $H$, and a target linear classifier $f^\\star$ that maps $\\mathbb{R}^d$ to $[k]$ as $f^\\star(x)=argmax_{i \\in [k]}(w \\cdot x)$ for some ground truth vector $w \\in \\mathbb{R}^d$. There is a joint distribution $D$ over $\\mathbb{R}^d \\times [k]$, such that a sample is drawn as follows: first, we draw $x \\sim D_x$ where $D_x$ is the marginal of $D$ on $\\mathbb{R}^d$, and then, we draw $y$ from the conditional distribution $\\Pr[y=j|x]=H_{f^\\star(x), j}$. Namely, the label $y$ should ideally have been $f^\\star(x)$ with no noise; but now, we perturb the label according to $f^\\star(x)^{\\text{th}}$ row of $H$. Given iid draws from this distribution, and $\\epsilon \\in (0,1)$, the task in MLC with RCN is to output a classifier that has error at most $\\epsilon$ larger than the error of the optimal classifier in some class.\n\nThe sample complexity of this task is known. This paper is concerned with the computational complexity of the task. In particular, for $k=2$, computationally efficient algorithms (that furthermore fit into the SQ model of algorithms) are known. One of the main results in the paper (Theorem 1.2) is an SQ lower bound for the case when $k=3$. This is surprising, and establishes a separation between what can be achieved computationally efficiently for $k=2$ versus $k=3$. The authors also establish certain other results, which rule out SQ-based algorithms to even approximate the optimal error upto a multiplicative constant factor (Theorem 1.3), and also an instance that is hard to output a hypothesis better than random guessing in an efficient manner (Theorem 1.4).\n\nThe results are accomplished by combining prior SQ-lower bound constructions in the literature due to Diakonikolas and others. In particular, the authors first show how a certain hypothesis testing problem that distinguishes cases where the labels are independent of $x$, versus the case where the labels are drawn according to a specialized MLC with RCN instance (see Definition 4.1), reduces to the learning problem of MLC with RCN (Lemma 4.4). So, the main task then becomes showing that this testing problem is hard. For this, the authors use a construction based on so-called \"hidden direction distributions\" (Definition 5.1) inspired from prior work. This construction appears to be standard in the SQ lower bound literature, but massaging it to the present context of MLC with RCN appears to require novel conceptual bridges. Finally, all the aforemenetioned hardness results for MLC under RCN follow (Section 6) from the hardness of distinguinging in the above testing problem.\n\n## update after rebuttal\nI thank the authors for the clarifications. It would be definitely be useful to include this discussion (as the authors deem appropriate) in the revised version of the paper. I maintain my evaluation of the paper, and my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the appreciation and useful feedback. \n\n>Technical Contributions: \n\nWe point out that our proof cannot be viewed as a simple modification of a previously developed SQ lower bound. As explained in the submission, the generic framework follows the moment-matching approach for Non-Gaussian Component analysis of [DKS17] and its generalization [DK22]. More precisely, we require a “relativized” version of that framework that is appropriate for supervised learning. Importantly, in order to be able to use this framework for our learning task, we need to construct novel low-dimensional moment-matching distributions that correspond to instances of MLC with RCN. This is our main contribution that requires significant conceptual and technical work. \n\nSpecifically, to achieve this, we carefully map an instance of MLC to a polynomial classification problem and derive a new “hardness” condition (Definition 4.1), under which (after the mapping) the conditional distribution of the polynomial classification problem coincides with a modified discrete Gaussian. Prior to our work, it was unclear how a hard instance of MLC with RCN would look like (or whether such a hard instance exists). While the use of the modified version of a discrete Gaussian is inspired by prior works (such as [NT22]), reaching this step requires novel technical insights for MLC with RCN. \nIn particular:\n\n1. A key novelty of our paper is to identify the “correct” condition (Definition 4.1) under which we are able to relate our problem with the existing framework for proving SQ lower bounds. Identifying such a condition is highly non-trivial for the following reasons. Conceptually speaking, algorithms developed in prior works fail when the noise matrix $H$ is non-invertible. However, not all non-invertible matrices $H$ can be used to obtain hard instances. Specifically, for a generic non-invertible $H$, we can only guarantee that one row of $H$ can be written as a linear combination of the other rows of $H$; and the coefficients of the linear combination could be negative. Natural attempts to construct hard instances for a generic $H$ fail. Specifically, they may require mapping MLC to a polynomial classification problem with very high degree, which will not lead to a super-polynomial lower bound for the original problem (as explained in Section 6). On the other hand, using our SQ hard-to-distinguish condition (Definition 4.1), we are able to map MLC with RCN to a polynomial classification problem in a clean and novel way (Theorem 5.3); together with the modification of a discrete Gaussian (Definition 5.5) these rule out any efficient SQ learning algorithm for this problem.\n\n2.\nAdditionally, recognizing the hardness of MLC with RCN itself is already rather surprising, given the well-known efficient learners for halfspaces with RCN; and learning MLC in the realizable setting. Before our work, it seemed plausible that a similar result could hold for MLC with RCN, at least when $f^*$ is Bayes optimal. In fact, prior works have shown that when $H$ is well-conditioned, this is indeed possible. Our results settle the complexity of the problem by showing a surprising computational separation between MLC with RCN and binary classification with RCN.\n\n>LP formulation for MLC in the realizable setting:\n\nThis reduction follows the definition of MLC. Instead of considering $k$ vectors in $R^d$, we can consider one vector $w$ in $R^{kd}$ (the concatenation of $w_1,..,w_k$) such that for every example $x$ with label $i$, we have $w_i.x-w_j.x \\ge 0$ for every $j \\neq i$ (see Definition 1 of [BPSTWZ19] for example). \n\n>Realizable v.s. Non-realizable:\n\nFrom the phrasing in the review, we understood that the question is the following: what is the difference between the case where $f^*$ is the Bayes optimal classifier (realizable) and the case where $f^*$ is not the Bayes optimal classifier (non-realizable). In case we misunderstood your question, please let us know and we will respond to the clarification. \n\nIf the probability that the label of an example is unchanged is strictly larger than the probability that it is flipped to another label, then $f^*$ always achieves 0-1 error opt and is the Bayes optimal classifier. In the binary classification setting, this condition on the error probabilities is equivalent to saying that the probability the label of an example is flipped is less than $1/2$. On the other hand, if this condition does not hold, then $f^*$ may not be the hypothesis in the class that achieves error opt. However, in both cases, we always want to compete with the hypothesis in the class that achieves the optimal error (we do not want to compete with hypotheses not in the class). In binary classification, no matter whether $f^*$ achieves error opt or not, we are always able to learn a hypothesis with an error arbitrarily close to opt in polynomial time.\n\nThe references are included in the response to Reviewer 4NDD.", "claims_and_evidence": "The claims and evidence appear convincing to me.", "methods_and_evaluation_criteria": "NA", "theoretical_claims": "I only glanced over the proofs, and did not verify calculations line-by-line. They appear correct to me, and the progression in the overall analysis checks out to me.", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "A lot of statistical learning theory is concerned with analyzing the number of samples that are information-theoretically sufficient and necessary to output an accurate classifier. The computational complexity of generating these accurate classifiers however also demands study. The present result establishes a separation in the computational complexity of linear classification under noise when the number of labels increases from 2 to 3. This is conceptually a surprising result, and suggests that standard algorithmic paradigms (namely, SQ algorithms) do not suffice for the seemingly natural extension for learning tasks from binary to multiclass, and more powerful algorithmic primitives provably become necessary.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "To me, the primary strength of the paper is the conceptual conclusion---within the class of computationally efficient algorithms, SQ algorithms suffice for binary classification with RCN, but provably do not for multiclass problems even with 3 classes. This conclusion is indeed intriguing to me. I believe this the conclusion would inspire future inquiry into the specifics of what can be achieved efficiently for MLC under RCN\n\nTo establish the result, the authors do rely on heavy-weight machinery on SQ lower bounds from prior literature. I do not necessarily view this as a weakness, since as i mentioned, massaging prior literatrure into the present context does appear to require technical work, and the final conclusion is satisfying and important.", "other_comments_or_suggestions": "I would really encourage the authors to be more specific with particular lemmas/theorems/chapters when you refer to textbooks (e.g. the SSS-SBD textbook). Simply citing a textbook in my opinion is quite lazy and entirely useless.", "questions_for_authors": "1) Could you, in a brief paragraph, summarize the techincal conceptual novelty that is required in massaging the standard hidden distribution SQ lower bounds to the present context? While the overview in section 2 is helpful, I was not able to fully appreciate what parts in the overview were specifically novel and challenging for the present result.\n\n2) What is the reference to the LP result for the realizable settingin lines 35-37?\n\n3) I am a little confused about what the difference even is in non-realizable vs realizable learning under RCN. Since the labels are always perturbed by noise, and the error is measured with respect to the best classifier in a class, what does it mean to be realizable? Does the non-realizable case simply refer to the case where $f^\\star$ is not in the class, so opt is no longer $f^\\star$? If so, for the binary case, what is known about the difference between these two settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "PZ9YIVuw1t", "reviewer": "Reviewer_4NDD", "summary": "This paper studies the problem of learning multiclass linear classifiers of form $\nf_w(x) := \\arg\\max_{i} \\\\{\\langle w_i, x \\rangle\\\\},$\nunder random classification noises with known noise channel. The paper shows that, unlike the binary classification case where efficient SQ algorithm is possible,  the case with even 3 classes is SQ-hard with query complexity superpolynomial w.r.t. the input dimension.\n\nThe main proof technique is based on reducing the hardness to a composite hypothesis testing problem. The difficulty lies in constructing the hypothesis testing distributions consistenting with certain multiclass polynomial classifiers (which future reduces to linear classifiers with a larger input dimention). This is achieved by leveraging the hidden direction distributions from Diakonikolas & Kane (2022) and Nasser & Tiegel (2022), with a more careful design for the distributions on the \"hidden direction\". The final SQ lower bound then follows by tuning the degree of the polynomials.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our theoretical results and for providing useful feedback. We next respond to the comments from the reviewer as follows.\n\n>Classification v.s. Regression:\n\nWe thank the reviewer for drawing our attention to the multi-class regression setting. In that respect, we want to point out that 0-1 loss is a standard benchmark for studying classification problems and for linear classification in particular. Specifically, the computational difficulty of the problem does not arise from using the 0-1 loss per se, but from the added noise. As we mentioned in the introduction (and also see our response to reviewer Y6KY), in the realizable setting the MLC problem can be written as a linear program and can therefore be solved efficiently (and with an SQ algorithm). Furthermore, if $H$ is well-conditioned, the problem is also efficiently solvable with respect to the 0-1 loss. In particular, the scale of the ground truth W has no effect on the 0-1 loss. That is, the use of the 0-1 loss is not the reason that makes the problem hard. \n\nOn the other hand, the logistic regression problem studied in https://arxiv.org/pdf/2110.03960 is not comparable to the classification setting studied in our paper. In fact, under the logistic loss, even the ground truth hypothesis W* could have a very large loss in the realizable setting—while under the 0-1 loss in the realizable setting W* has 0-1 loss equal to 0. This means that, without reasonable distributional assumptions, we cannot hope to use logistic regression to learn a hypothesis with a good 0-1 loss, which is what we believe is most desirable in practice. Furthermore, the use of logistic regression depends on the magnitude of W, while in 0-1 loss the magnitude of W does not affect the learnability of the problem. For two W’s with the same prediction under 0-1 loss, their logistic losses can be very different. In fact, the regret bound obtained in https://arxiv.org/pdf/2110.03960 actually depends on this magnitude (which can blow up when W is large). Based on these observations, we believe that the results for logistic regression are somewhat orthogonal to our results and their future potential impact. In summary, we believe that the hardness results obtained in our paper may motivate subsequent algorithmic work under additional structural assumptions (please also see the conclusions of our paper).\n\n>Technical Novelty:\n\nGiven the efficient learnability of halfspaces with RCN and MLC in the realizable setting, prior to our work, it was considered plausible that MLC with RCN is also efficiently learnable. As mentioned in the introduction, MLC with RCN has been widely studied in prior work both empirically and theoretically (by different communities), and efficient learning algorithms have been developed when $H$ is well-conditioned. \nRather surprisingly, we show a strong computational separation between the binary and the ternary cases.  \nFurthermore, we want to emphasize that although parts of our proof are built over the standard NGCA framework developed by [DKS17, DK22] and leverage modifications of the discrete Gaussian inspired by [NT22], formulating MLC to fit in these frameworks requires novel ideas, such as: identifying the correct condition, under which the hardness holds; and mapping MLC to a polynomial classification problem without using polynomials with very high degree. We refer the reviewer to our response to Y6KY’s similar question for more details. \n\n\n>Reference:\n\n[BPSTWZ19]Beygelzimer, A., Pal, D., Szorenyi, B., Thiruvenkatachari, D., Wei, C.-Y., and Zhang, C. Bandit multiclass linear classification: Efficient algorithms for the separable case. In International Conference on Machine Learning, pp. 624–633. PMLR, 2019.\n\n[DV04]Dunagan J, Vempala S. A simple polynomial-time rescaling algorithm for solving linear programs. InProceedings of the thirty-sixth annual ACM symposium on Theory of computing 2004 Jun 13 (pp. 315-320)\n\n[DKS17]Diakonikolas, I., Kane, D. M., and Stewart, A. Statistical query lower bounds for robust estimation of highdimensional gaussians and gaussian mixtures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73–84, 2017. doi: 10.1109/ FOCS.2017.16. \n\n[DK22]Diakonikolas, I. and Kane, D. Near-optimal statistical query hardness of learning halfspaces with massart noise. In Conference on Learning Theory, pp. 4258–4282. PMLR, 2022.\n\n[NT22]Nasser, R. and Tiegel, S. Optimal sq lower bounds for learning halfspaces with massart noise. In Conference on Learning Theory, pp. 1047–1074. PMLR, 2022.", "claims_and_evidence": "The claims are clear, and the proofs are convincing.", "methods_and_evaluation_criteria": "This is a purely theoretical paper. The proof technique is sound and based on prior literature.", "theoretical_claims": "I checked most of the proofs necessary for the main claims, though I didn't verify every single detail. As far as I can see, the overall proof idea is clean and correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper advances the understanding of the computational complexity of linear classification under RCN beyond binary labels.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Other Weaknesses:**\n\n1. Although this is clearly a solid theoretical paper with novel ideas, I'm skeptical about its broad impact on the community. It seems to me that the difficulty mainly arises from the use of 0-1 loss, which is known to be hard in many other settings.\n\n2. A more practically relevant setting (as also pointed out by the authors) is to consider softmax regression, \n   $\n   p_w(i \\mid x) = \\frac{e^{\\langle w_i, x\\rangle}}{\\sum_{j=1}^{k} e^{\\langle w_j, x\\rangle}},\n   $\n   and optimize under the log-loss. This is known to admit computationally efficient algorithms even in the adversarial online setting (which reduces to the batch setting through online-to-batch conversion); see:  \n   [https://arxiv.org/pdf/2110.03960](https://arxiv.org/pdf/2110.03960).\n\n3. The proof techniques largely follow from Diakonikolas & Kane (2022) and Nasser & Tiegel  (2022), which is not particularly surprising.", "other_comments_or_suggestions": "**Writing Suggestions:**\n\n1. The notation $C\\text{opt}$ is confusing, consider using $C \\cdot \\text{opt}$.\n2. In Definition 4.1, item 2 should be $x \\not\\in S_k$.\n3. Definition 5.2 is quite confusing:\n   - it would be better to explicitly say that \"$J_i$ is a union of $m$ disjoint intervals.\" I only understood this after reading your construction in Definition 5.5.\n   - did you miss $\\textbf{conv}$ in the definition of $I_{\\text{in}}$? Moreover, it is better to write $I_{\\text{in}}$ instead of $I_{in}$, as one might confuse \"in\" with $i \\cdot n$.\n4. The distributions $h_i$s are confusing with the hypothesis, consider using $H_j$s.", "questions_for_authors": "I list some comments in the \"Other Strengths and Weaknesses\" section, which will not impact my recommendation for acceptance.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the fundamental problem of robustly learning multiclass linear models in the presence of random classification noise. It is shown that even for a problem with three classes, PAC learning is computationally hard by any SQ algorithm. In addition, such SQ-hardness remains even when we relax the PAC guarantee to constant approximation. All together, these results are significant for understanding the multiclass PAC learning problem. The paper is clearly written.
Decision: Accept (oral)