SQ Lower Bounds for Learning Mixtures of Linear Classifiers
Authors: Ilias Diakonikolas
Daniel Kane
Yuxin Sun
Venue: NeurIPS 2023 poster (2023)
Keywords: mixtures models
linear classifier
Statistical Query model
spherical designs
TL;DR: We give nearly tight SQ lower bounds for learning mixtures of linear classifiers under Gaussian covariates.

Abstract: We study the problem of learning mixtures of linear classifiers under Gaussian covariates.
Given sample access to a mixture of $r$ distributions on $\mathbb{R}^n$ of the form $(\mathbf{x},y_{\ell})$, $\ell \in [r]$,
where $\mathbf{x}\sim\mathcal{N}(0,\mathbf{I}_n)$ and

$y_\ell=\mathrm{sign}(\langle\mathbf{v}_{\ell},\mathbf{x}\rangle)$

for an unknown unit vector $\mathbf{v}_{\ell}$,

the goal is to learn the underlying distribution in total variation distance. Our main result is a Statistical Query (SQ) lower bound suggesting that known algorithms for this problem are essentially best possible,
even for the special case of uniform mixtures.
In particular, we show that the complexity of any SQ algorithm for the problem is $n^{\mathrm{poly}(1/\Delta) \log(r)}$,
where $\Delta$ is a lower bound on the pairwise $\ell_2$-separation between the $\mathbf{v}_{\ell}$'s.
The key technical ingredient underlying our result is a new construction of spherical designs on the unit sphere that may be of independent interest.

SQ Lower Bounds for Learning Mixtures of Linear Classifiers
Maias Diakonikolas University of Wisconsin- Madison ilias@cs. wisc. edu
Daniel M. Kane
University of California, San Diego dakane@cs ucsd. edu
Yuxin Sun
University of Wisconsin-Madison yxsunccs. wisc.edu
Abstract
We study the problem of learning mixtures of linear classifiers under Gaussian covariates. Given sample access mixture of r distributions on R" of the form (x, ye), [r]. where x ~ NO I,) and y = sign((ve, x))) for an unknown unit vector Vz, the goal is to learn the underlying distribution in total variation distance. Our main result is Statistical Query (SQ) lower bound suggesting that known algorithms for this problem are essentially best possible, even for the special case of uniform mixtures. In particular, we show that the complexity of any SQ algorithm for the problem (1oly(1/A) log(r), where pairwise fz-separation between the vy's. The key technical ingredient underlying our result new construction spherical designs that may be of independent interest.
a lower bound on the
Introduction
The motivation behind this work is to understand the computational complexity of learning high- dimensional latent variable (aka mixture) models. The task of learning various mixture models has a long history in statistics with an early focus on sample efficiency, starting with the pioneering work of Karl Pearson [Pea94] on learning Gaussian mixtures. During the past decades, an extensive line of work in machine learning and theoretical computer science has made significant progress on the computational aspects of this general question for a range of mixture models, including mixtures of
high-dimensional Gaussians (Das99 AKOI VW02 AM05
KSV08 BV08 MV1O RV17 HLI8
DKSI8), mixtures of linear regressions [SA 6 LL18
CLS20 DK20 and more generally mixtures
of experts [194 XA09 ME14 MVKO19 HYJ22
this paper, we focus on mixtures of linear classifiers, a classical supervised probabilistic model that has been intensely investigated from both statistical and algorithmic standpoints [SIM14] LLYH17 GMP20 CDV22). A linear classifier (or halfspace) is any Boolean function RR" R" is known univariate function sign is defined by sign(() = for I. 2 0 and sign(!) = -1 otherwise. For formally describe r-mixture of linear classifiers. The parameters with Σ unit vectors V....., V, R random sample is drawn from the underlying distribution D y) as follows: the sample oracle selects the index é E [r] with probability wy. and we then receive a random point (x, y) R {+1} where x (O, I,) and = sign((ve, x))). The goal to approximately estimate the model either by learning the underlying distribution D(x, y) in total variation distance (density estimation), or by approximately recovering the hidden parameters, i.e.
{+1) of the form hxx) sign((v. x)), where
the weight vector and the
integer r 2 2, we
of the model contain r unknown positive weights Wi....,
1, and unknown
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

we and Ve, E [r] (parameter estimation). An algorithm for parameter estimation can be used for density estimation (because closeness in parameters can be shown to imply closeness in total variation distance). In that sense, parameter estimation is a harder problem.
Before we proceed to describe prior algorithmic work, we provide basic background the sample complexity of the problem. We start by noting that density estimation for r-mixtures of linear classifiers on I8"h is pnaemmttooo-thooeticaalll solvable using poly(n,7) samples (with the optimal bound being @ for total variation error <) without any assumptions on the components. In contrast, for parameter estimation to be information theiiinnnterreticllllyll solvable with polynomial sample complexity, some further assumptions are needed. The typical assumption involves some kind of pairwise separation between the component vectors and lower bound on the mixing weights. Let
[22] > 0 be the pairwise separation between the components and Wmin be the minimum mixing weight. Under these assumptions, the parameter estimation problem is solvable using poly(n, 1 1/ /Wiiin 1/c) samples to achieve parameter error of c. In both cases, solvable" is used to mean that a sample-efficient algorithm exists, without any constraints on computational efficiency. The main question addressed in this paper is to what extent a computationally efficient learning algorithm exists.
def m (I|v; - Vol12.
the term
On the algorithmic front, [CDV22] gave provable parameter estimation algorithms un- Specifically, [CDV22 provided two algorithms with different complexity guarantees. Their first algorithm has sample and computational complexity poly(nO(loger)/4 1/umin, 1/e). while their second algorithm has complexity poly((m/A),,,/ 1/Wmin: 1/e). Here we focus on settings where the number of components r is large and cannot be viewed as a constant. For the sake of intuition, it is instructive to simplify these upper bounds for the regime of uniform mixtures (corresponding to the special case that wyy = 1/r for all l E [r]) and is not too small. For this regime, the complexity upper bound achieved in [CDV22 (n/A) ))))))) Concretely, if the separation A is 21(1) or even l/polylog(r). the first term yields a quasi polusi-plyyoomial upper bound. On the other hand, for A = O(L/r"), for a constant с > 0, the resulting upper bound is n. In both regimes, we observe a super- polynomial gap between the information-thent
der A-separation assumption.
min (log()))))
sample complexity which is poly(n, r, A)
and the sample complexity of the [CDV22 algorithms. It is thus natural to ask if this gap is inherent.
What is the complexity of learning mixtures of linear classifiers?
Is there an algorithm with significantly better sample-time tradeoff?
We study these questions in well-studied restricted model of computation, known as the Statistical Query (SQ) model [Ke99]] (and, via (BBH+20) 20), also for low-degree polynomial tests). Our main result that in both of these models the complexity of the monve-een algorithms is essentially best possible. Along the way. we establish new results on the existence of spherical designs on the unit sphere that may be of independent interest.
1.1 Our Results
Basics on SQ Model SQ algorithms are a class of algorithms that, instead of having direct access to samples, are allowed query expectations of bounded functions of the distribution. Formally, an SQ algorithm has access to the following standard oracle.
Definition 1.1 (STAT Oracle). Let D be a distribution on R Statistical Query is a bounded function f R + []. For r > 0, the STAT(T) oracle responds to the query f with a value v such that jv- [x-n[[(x)]] < r. A Statistical Query (SQ) algorithm is an algorithm whose objective is to learn an unknown distribution D by making adaptive calls to the STAT(T) oracle.
The SQ model was introduced in [Kea98] Subsequently, the model has been extensively studied in range of contexts (Fel16]). The class of SQ algorithms is broad and captures a range of known supervised learning algorithms. More broadly, several known algorithmic techniques in machine learning are known to be implementable using SQs [FGR+17 FGV17].
Our main result is a near-optimal SQ lower bound for mixtures of linear classifiers that applies even for the uniform case. Specifically, we establish the following:
Theorem 1.2 (Main Result: SQ Lower Bound for Uniform Mixtures). Let 6 S eD/r for some universal constant > 0 sufficiently small. Then, any SQ algorithu that learns a uniform mixture of
2

---

linear classifiers with directions Vi....,V, E S²-1 satisfying min - -vyl22 Iv, + vyll2 2 (AA) for some r-1110 < A < 1, within error in total variation distance must either use queries of tolerance n logo, or make at least 2 queries.
Informally speaking, Theorem 1.2] shows that no SQ algorithm can perform density estimation for uniform mixtures of linear classifiers to small accuracy with a sub-exponential in n ((2) many queries, unless using queries of very small tolerance - that would require at least 1 log samples to simulate. This result can be viewed as near-optimal anformation-computttiin tradcoff for the problem, within the class of SQ algorithms. In more detail, for = 22(1, we obtain a quasi- polynomial SQ lower bound n (2 r); while for A = 1/r", for some constant 0 < c < 1/2, we obtain an SQ lower bound of poly(()) In both cases, our SQ lower bounds qualitatively match the previously known algorithmic guarantees [CDV22] (that are easily implementable in the SQ model).
conceptual implication Theorem 1.2 is that the uniform (i.e., equal mixing weights) case essentially as hard as the general case for density estimation of these mixtures. In contrast, for related mixture models, specifically for mixtures of Gaussians, there is recent evidence that restricting the weights may make the problem computationally easier [BS2]]
Remark 1.3. We note that the condition A 2 r- " for some constant 0 < c < 1, is necessary in the statement Theorrm 1.2 for the following reason: the algorithmic result of [CDV22] has sam- ple and computational complexity min(n (llog(r)/²²) (n/A) A))()) which will be (n/A)((r) <<
(oly(1/A) logr if A is sufficiently small by inverse polynomial in
Remark 1.4. Our SQ lower bound result has immediate implications to another well-studied re-
stricted computational model - that of low-degree polynomial tests [HS17] HKP+17 Hop18]. [BBH+20 established that (under certain assumptions) an SQ lower bound also implies a qualita- tively similar lower bound the low-degree model. This connection can be used as a black-box to show similar lower bound for low-degree polynomials.
The key technical ingredient required for our SQ lower bound is a theorem establishing the existence of spherical designs with appropriate properties. The definition of spherical design follows.
Definition 1.5 (Spherical Design). Let be an odd integer. set of points xI, X,, E S
is called spherical t-design if E[p(x)] = E p(x;) holds for every homogeneous n- nariiaate polynomial p of degree t, where the expectation is taken over the uniform distribution on the unit sphere 8m
We note that this definition differs slightly from the usual definition of spherical design, which requires that the equation in Definition 1.5 holds for all polynomials p of degree most t. However, by multiplying by powers of [| we note that our definition implies that the equation holds for every odd polynomial of degree most f, and it is sufficient for the requirement of establishing our SQ lower bound.
Spherical designs have been extensively studied in combinatorial design theory and a number of efficient constructions are known, see, e.g., [9an79] DGS91 GPT1 BRV13 K5n Wom
However, none of the known constructions seem to be compatible with our separation assumptions. We establish the following result that may be of independent interest in this branch of mathematics.
Theorem 1.6 (Efficient Spherical Design). Let t be odd integer and r 2 ("+22-1)) Let
YI....,yr Yr be uniform random vectors over S=-1, Then, with probability at least 99/100, there exist unit vectors 2; E @=-1 very close to y; such that (Zi...., form a spherical I-design.
We mention here that the optimal sample complexity for the existence of spherical t-design (for even t) is r = (((*+))) and our result matches this within a polynomial factor. Theorem 1.6 essential for our construction of moment- matching. Roughly speaking, the resulting mixture matches moments in the sense we require if and only if the weight vectors (V1,..., vy.....,,) form a spherical design. We mention that the closeness between z, and y; is necessary since this leads to the separation of the hidden weight vectors in the mixture of linear classifiers. In order to guarantee the pairwise separation of the weight vectors v,'s, we note that with high probability the y, are pairwise separated and therefore if z, is sufficiently close to y, they will be too.
3

---

1.2 Technical Overview
Our starting point is the SQ lower bound technique of [DKS17 and its generalization in [DKPZ21 In particular, our overall strategy to find a mixture of homogeneous halfspaces in some "small" number m of dimensions that matches its first k moments with the distribution on (x, y), where is independent of x. By appropriately embedding this low-dimensional construction into I" via a random projection of IR" + IR" the SQ lower bound machinery of [DKPZ21] can be shown to imply that learning the projection requires either 2 20)) queries or some query of accuracy n -0(()) This generic step reduces our problem to finding an appropriate m-dimensional construction. Such a construction the main technical contribution of this work.
Note that specifying a mixture of halfspaces is equivalent to specifying a probability distribu- tion with support consisting of at most r unit vectors and specifying the orthogonal vectors of the halfspaces. It is not hard to see that the resulting mixture matches moments in the sense we require if and only if these vectors form spherical k-design [DGS9]]: namely, that for any odd polynomial p of degree less than k that the average value of p over our distribution is the same as the average value of p over the unit sphere (namely, equal to zero). The bulk of our problem now reduces to finding constructions of weighted designs, where: (1) The support size of the design is relatively small. (2) The points in the design are pairwise separated. (3) For equally weighted mixtures, we require that the weight of each vector in the design is uniform.
In m two dimensions, there is relatively simple explicit construction that can be given. In particular, if we take k evenly spaced points over the unit circle for some odd k, this matches the first - moments and has separation (1//k). (This is similar an SQ construction in [DKKZ20] for a different setting.) Unfortunately. we cannot obtain better separation in two dimensions. since any & unit vectors in two dimensions will necessarily have some pair separated by at most O(1/k). Therefore, if we want constructions with greater separation, we will need to pick larger values of m. Indeed, we show (Proposition 3.2) that a random collection of approximately m ((k) points can form the support of an appropriate design. This can be proved by applying linear programming duality. Unfortunately, this argument does not allow us to control the mixing weights. Specifically, it may be the case that the minimum weight is exponentially small which seems unnatural in practice.
The case of equal weights requires a significantly more sophisticated argument. In this case, need find spherical design with uniform weight. Indeed, merely selecting random sup- port will no longer work. Although there is an extensive literature on finding efficient spherical designs [Ban79 DGS91 GPIT BRV13 Kan15 Wom18), none of the known constructions seem to be compatible with our separation assumptions. In particular, [RRV13] proves that for each 2 hm, there exists spherical k-design, where C. is constant depending only on the di- mension m. Although it is plausible that their construction can be adapted to satisfy our separation requirement, their sample complexity has a potentially bad dependence on the dimension m. On the other hand, [Kan15] achieves the optimal sample complexity up to polynomials for all m and k. However, the construction in [Kan15] definitely does not satisfy our separation requirement. We note that the sample complexity r = O( (((=*t)) should be optimal, and our results are polynomial in this bound. In conclusion, to establish our SQ lower bound, we need to prove a new technical result. Our starting point to that end will be the work of [RVV33. The basic plan here will be to to
select random unit vectors y1. .2.... y, E RR", and then applying topological techniques show that there is some small perturbation set X2. x, E IR" that spherical design. In particular, we will find a continuous function F mapping degree-k odd polynomials to sets of unit vectors such that, for all unit-norm polynomials p. if F(y) = (Z)...., 2,)) then Σx= p(z,) > O. Given this statement, a standard fixed point theorem (CC06) will imply that our design can be found as F(q) for some q with norm less than one. To construct the mapping F. we start with the points .i....,y, Yr and perturb each y; in the direction of V Vop(y:) in order to try to increase the average value of p. where Vop(y:) is the component of Vp(y;) orthogonal to the direction yt. Intuitively, this construction should work because with high probability the average value of p(y.) is already small (since the empirical average should approximate the true average), the average gradient of p(y:) is not too small, and the contributions to p(z,) coming from higher-order terms will not be large as long as z; is sufficiently close to y;. These facts can all be made precise with some careful analysis of spherical harmonics [Lemma 4.5).
Finally, we need to show that the hardness of learning the appropriate projection implies hard- ness of learning the mixture. By standard facts, it suffices to show that mixtures of linear classifiers

---

are far from the distribution (x. y), where the uniform label y is independent of x. in total variation distance. To show this, we prove that the total variation distance between any projection and the distribution where is independent of x is at least ((4/r) (Lemma 3.8).
2 Preliminaries
For n. E Σ.,, we denote [n]] def
For two distributions p. over a probability space Q let dpv q) supsço (p(S) ((S) denote the total variation distance between p and q. In this article, we typically use small letters to denote random variables and vectors. For a real random variable x,
E[æ;] denote the expectation. We use Pr[E] and I[E] for the probability and the indicator of event 3. Le, denote the standard n--dimensional Gaussian distribution and / denote the standard univariate Gaussian distribution. Let 8 {x IR" ||x||2 = 1} denote the n- dimensional unit sphere. For a subset C RR, we will use (S) to denote the uniform distribution over S. We will small boldface letters for vectors and capital boldface letters for matrices. Let ||x|| be the f2-norm of the vector x E IR.. For vectors u, v E IR", we use (u, v) to denote their inner product. We denote by (R ,nn) the function space of all functions f I2" + R such that ExEN. [f2 < 00. The usual inner product for this space is EzeN, ( (z))
to be its spectral norm and Frobenius norm respectively. For tensor A E (R")@k, let || la denote its spectral norm and ||||| denote its Frohenius norm. We will use Aij....i to denote tuple (f1...., ).). The inner product between k-tensors is defined by thinking of tensors as vectors with n coordinates. We use the framework of Statistical Query (SQ) algorithms for problems over distributions [FGR 17) and require the following standard definition.
For matrix P E IR=x", we denote |P 12, |P||
coordinate of the k-tensor indexed by the k-
Definition 2.1 (Decision/Testine Problem over Distributions). Let D be distribution and DD be family of distributions over IR.. We denote by ((D, D) the decision (or hypothesis testing) problem in which the input distribution D' is promised satisfy either (a) D' D or (b) D' D, and the goal of the algorithm is to distinguish between these two cases.
Basics on VC-Inequality We recall the definition of VC dimension for a set system.
Definition 2.2 (VC-Dimension). For class C of boolean functions on set X, the VC-dimension of C is the largest integer d such that there exist d points 21...., Id E X such that for any boolean function g {x1,...;
[1,, there exists an C satisfying (xx; = g(x)), sis d.
We will use the following probabilistic inequality.
Lemma 2.3 (VC inequality, see, e.g., (er18)). Let C be class of boolean functions on X with VC-dimension d, and let X be a distribution on X. Let O and let N be an integer at least sufficiently large constant multiple of d/e.. Then, if X1, X2......, XN are i...d. samples from X, we have that:
ΣS f(X,) E[((X)) exp(-2((Ne)
Pr
sup fEC
N
To apply the VC inequality in our context, we additionally need the following fact which gives the VC-dimension of the class of bounded-degree polynomial threshold functions (PTFs).
Fact 2.4. Let C2 denote the class of degree-k polynomial threshold functions (PTFs) "h namely the collection of functions of the form fxx sign(p(xx p(x)) for some degree at most real polynomial Then, the VC-dimension of C2 is VC(Ca) = ( k
3 Warmup: SQ Lower Bounds for General Weight Mixtures
SQ Lower Bound Machinery. prove our SQ hardness result.
We start by defining the family of distributions that we will use to
Definition 3.1 (DKPZ21). Given function R + [-1, +11+1 we define D, to be the class of distributions over RR (+1) of the form (x, y) such that x N₂ and Ely x = z] g (2)),
where U E gmxn with UUT = In-
5

---

The following proposition states that if has zero low-degres moments, then distinguishing Do from the distribution (x. y) with Nn y ~ (({=1}) is hard in the SQ model.
Proposition 3.2 (IDKPZII). Let g: _ + [-1, 1] be such that Ex-Nm, (x))))(((()(() - O, for every polynomial p IR" - R of degree less than k. and Dy be the class of distributions from Defini- tion 3.7 Then, if m I n²,, for some constant < 1/2, any SQ algorithm that solves the decision problem B(D (U{+)])) must either use queries of tolerance -Q()) or make at least 2 (0) queries.
2
We will apply Proposition 3.2 to establish our SQ lower bound for learning mixtures of linear classifiers. The main lechnical contribution required to achieve this is the construction of a class of distributions Dg. where each element in Dg represents distribution of mixture of linear classifiers. In particular, we will carefully choose some appropriate unit vectors Vi...., V E R and non- negative weights Wi,...,, Wr with Σi= Wy 1, such that Vi pairwise separated by A > 0.
Let g(z) = =E wisign(v] z), E R For an arbitrary matrix U R=*x" with UUT = Ims we denote by Du the insaance of mixture of linear classifiers with weight vectors U UTv, and weights wi,..., Wy. In this way, we have that
E(x,))DolM x 2)
wesign ((UT:))(
Σ Pessig(vv]Uu = g(Uz), 2 E RR.
3.1 Low-degree Moment Matching
The following proposition shows that there exist unit vectors Vi,..., V, and non-negative weights wI....; W, with Ei=1 Wy- = 1 such that Vi are pairwise separated by some parameter A >> 0 and the low-degree moments of vanish. Note that since g is odd (as the sign function is odd), we only require Eze [z)) = for every odd polynomial p of degree less than k.
and 1.99 S c S a universal con- stant. Let be a positive integer such that r 2 C( for some constant C sufficiently large. & There exist vectors V1....,Y, over the unit sphere Sm-1 and non-negative weights W1, wi..... Wr with Eiz we 1, such that
Proposition 3.3. Let m log(1/A) where 1-100 S A
clogr
0 holds for every odd polynomial p of degree less than k, where g(z) Em wesign(v!2)
||v, + vvlla, llv, - vylla 2 (()) Si Si<j
The proof proceeds as follows: We uniformly sample unit vectors Vi, V, E gm-1, We will prove by the probabilistic method that both statements in Proposition 3.3 hold with high probability. We begin by showing that Pr Prfminggssjs fllv -vslz, v; + v O()) small. By symme- try, it suffices to bound Pr Primingsisjsr [ v < O())] Let = min arccos (V. vy)-
We require the following facts:
Fact 3.4 (Proposition 3.5 in 1B)+ Pr O 1 yr 221
Rm-1 m-1 where Kim =
r((m+1/2)
m+1
mVF[(m//2
m
2
Applying Fact 3.4 by taking 7
and
yields that
50kmm
50Km Amm-
Pr(e 2 A] 2 99/100. Given some fixed random vectors Vi,..., Vr E gm-1 we will prove that with high probability there exist non-negative weights w1,-.., Wy with Σi=1 Wy such that E E2-Ax,.9(z)p((2) [z(z)((z)) = O holds for every odd polynomial p of degree less than k, where g(z)= -Ei= wysign( v22). Noting that Ez-A... [g(z)p(z)] Ei WpEz~NN.. (p(z)sign(v]2)) suffices to bound the probability that there exist non negative weights Wi...., W, with E wy 0 holds for every odd polynomial p of degree less than k. Our main technical lemma is the following:
such that En= W/ Ez- [p(z)sign(v]2z
Lemma 3.5. Let p m + R be polynomial of degree less than &o and S E (RR.N). Let E gm-1 be a unit vector. We have that Exz,.., (p(z) (VTz)) is a polynomial in v of degree less than k.

---

The proof proceeds by analyzing p and f as Hermite expansions. For complete- we can write =>i= We) for some odd polynomial of degree less than (since sign is odd). In this way, suffices to show that with high probability there exist non- negative weights wi,...,, Wr with E Pf=1 Wy such that > We](Ve) = 0 for all odd polyno- mials q of degree less than k. To prove this, we leverage the following lemma:
ness, we defer the proof of Lemma 3.3 Appendix B From Lemma 3.5
Ei= WxEx-NN, [p(z)sign(v3 [v]] 2
Lemma 3.6. The following two statements are equivalent.
1. There exist non-negative weights wi...., Wrr with E = such that Ei=1 weg(ve) = 0 for all odd polynomials q of degree less than k.
There does not exist any odd polynomial q of degree less than such that q(ve) > 0,15 S
The proof of Lemma 3.6 follows via careful application of LP duality; see Appendix B
Proof of Proposition 3.3 Let θ
min minigisjsr arccos vv, V2). Applying Fact 3.4 by taking
yields Pr(O 2 A] Pr
99/100 (since our choice of m will
50mm
imply
1/ 50km A )
This will imply that
Pr
min {llv Vslle, |V; + vylle) 2 2(2)] 2 99/100. ISKSSS
We then show that there exist non-negative weights wh...., with Ei=1 Egn.N.. (g(z) (((z)((z] 0 holds for every odd polynomial p with degree less than k. where g(z) Ei=1 wesign(v v2z). By Lemma 3.5, it suffices to show that there exist non-negative weights WI,.... Wr with Σin me = such that Et= Weg(vz) = 0 for all odd polynomials of de- gree less than k. By Fact 2.4, we have that r r C (m**)) = CVC(Cx) for some sufficiently large constant > O. Note that for any odd polynomial q in m variables degree less than k, we have that (( v)] = O. Therefore, by the VC-inequalityy (Lemma 2.3). we have that
1 Wy = 1 such that
Pr odd polynomial of degree less than k such that g(ve) > 011s
f(ve) =
f(ve) -Ef([v]] 21
< Pr
sup SECA-1
< Pr
sup fECz
$ expl (-((r)) S 1/100.
Finally, applying Lemma 3.6 completes our proof.
3.2 Proof SQ Lower Bound for General Weights
Let be a positive integer such that r 2 C( (m++k) for some constant C' sufficiently large. Let
&
m = clogr [o](1/a) where r -1/10 < A < 1 and 1.99 I < 2. By Proposition 3.3 there exist unit _ such that
vectors Vi.
There exist neg-nigtt weights wi,..., Wy with Σ -t We = 1 such that Ex- [z(z)p(z)) = holds for every odd polynomial with degree less than k, where g(z) = Σr_ wesign (v]z).
||v: + Vyl1a, ||v - v,l1a 2 ((A),II Si < S for some > 0.
For an arbitrary matrix U E mR with UUT = I,., denote by Du the instance of mixture of linear classifiers with weight vectors UTV1..... UTv, and weights Wi.... Wr- Let D3 = [Du U e Iv. + -v 2 2 Q(A), i
Rmxn
and = Σi= wysign [z) = (UZ), E R". By Proposition 3.2 any SQ algorithm for the decision problem BD,,,,N, x (({+1})) must either
UUT ].
J. We have that ||UT, - UTv
E E by x z] = E (Ssiin((UTv,))))
queries of tolerance -R(R) make at least 2n00)) queries. The last step is to reduce the decision problem B(D,. x ({{+1})) to the problem of learning mixture linear classifiers.
Claim 3.7 (see, e.g., Lemma 8.5 (K23)). Suppose there exists an SQ algorithm to learn an unknown distribution in a family D to total variation distance e using at most N statistical queries
7

---

of tolerance т. Suppose furthermore that for each D' E 'D we have that drv D') > 2(T + e). Then there exists an SQ algorithm that solves the testing problem B(D, D) using at most queries of tolerance т.
To apply Claim 3.7 we need to show that the distribution Du in the class Dg is sufficiently far from the null hypothesis Do = Nn x (({+1}) in total variation distance.
Lemma 3.8. Ler U E Rmx* with UUT = Im- We have that drv (Du. Do) 2 9(A/r).
We briefly sketch the proof idea and defer the proof details to Appendix We consider wysign(v]3 a halfspacc of heaviest weight in Du, and pick points z and z close to the defining hyperplane that are mirrors of each other over it. We note that under Do the expectations y conditioned on being 2 or z are both O, whereas under Du they likely (in particular, unless they are also on opposite sides of another halfspace) differ by least Wig.
SQ Lower Bound for Uniform Mixtures via Spherical Designs
In this section, we prove our SQ lower bound for mixture of linear classifiers with uniform weights, thereby establishing Theorem 1.2, Our basic lower bound technique essentially the same as the previous section, but need construct spherical design with uniform weight.
Proposition 4.1. Let m log(1/A)' be an odd integer such that (m+) There exist vectors Vi....,,, V, g such that:
and 1.99 S c S 2 a constant. Let clogr where 1/10 < <
EanNon m [z())((2)] = O holds for every odd polynomial with degree less than k; where g(z) Ee= sign(v
1|v, + vylla, lv. - volla ((A) ((4) (m 11o+2kk111 2k
Miskijn
By Lemma 3.5 we can write Ei=1 Ez-N [p(z)sign(v/2>]
((ve) for some odd poly-
nomial 9 of degree less than k. Therefore, it suffices to show that with high probability there exist unit vectors Vi...., Vr such that Ee= ((ve) holds for every odd polynomial q of degree less than k. To achieve this, we will leverage some techniques from [RVI33
4.1 Spherical Design Construction
Notation. We start by introducing some additional notations we will use throughout this section. Let pd denote the set of homogeneous polynomials in d variables of some odd degree t. For any For any p E Prl define ||p||3 (p.p). We denote by Ne.a (" to be the dimension of Pp and Ω {p E P llellz 5 1]. Let ang denote the boundary of 2z, i.c., anf = {o E Pd llpllz = 1}. In the remaining part of this section, we will assume that the underlying distribution (over the expectation) is (1(
P. 3 E Pid we consider the inner product (p. q) = E (xx_uss=_,)(((x)))))>
The following theorem- - a more detailed version of Theorem 1.6 establishes the existence of spherical f-design of size poly(Ng (N2r,a) with the desired pairwise separation properties.
Theorem 4.2 (Spherical Design Construction). Let be an odd integer and r 2 N Let
yI....,' Yr be uniform random vectors over gd-1, Then, with probability at least 99/100, there exist unit vectors 21,...,2, v Sd-1 such that ||z, yıll2 O(1/Nn,,)) [r), and (Z), 2r) form a spherical I-design.
To prove Theorem 4.2, we will start from the following result.
Theorem 4.3 (BRVI3). If there exists continuous mapping F: Pd. - (Sd-1y such that for all
p E and E (p)) > 0, where F(p) = (x1 (x)(p)... xx())) then there exists a polynomial p" E D such that E[p(x)) = I (xxx("))) holds for every polynomial Pdd
To apply Theorem 4.3, need to find continuous function F mapping Pd to (gd-ly" such that for any p 2.,, Ei p(z:) > O, where F(p) (Zi...., z,). We will construct the mapping
8

---

F as follows: we sample : .r uniformly over the unit sphere S and then try to make the value of p(y;) larger by moving each point y; in the direction of the gradient. In particular, we let z, 1o V++VVo for some > 0 sufficiently small, where V.p(y) is the component of Vply) orthogonal to the direction y. We will prove that with high probability, for any E any p(z.) O. Intuitively, this works because of two facts:
1.
With high probability over the choice of yı, for all E St the average value of p(y) is already close to zero.
Moving in the direction of voply.) increases p(y.) by a notable amount.
Lemma 4.4. Let P be subspace of polynomials in d variables with mean zero. Let N be the dimension of St. Let X1...., X, be i.idd. random vectors over gd-1, Then, with probability at least 1 19 we have that for any p E 2 1(=1p((s)) S n11ppl2.
N
take an orthonormal basis P1..... PN E S and define p(x) [pi (x)..... PN [x]]". Noting that pxx)
To prove Lemma 4.4,
random vector with mean zero and covariance iden- tity, applying Markov's inequality will yield the result. We defer the proof details to Appendix C
Lemma 4.5. Let y E gd-1 and O < 6 S 1/N2, For any p E and let
y+5V.p(y) a++ov.Ply)l We I| 2 for some universal constant 0 < c<1.
have that p(z) - p(y) 2
follows by Taylor expansion, where the contributions to p(z) coming from higher-order terms will be large as long as z is sufficiently close to y. We defer the proof details to Appendix C By applying the above two lemmas, we establish the following:
The proof of Lemma 4.5
Theorem 4.6. Let y .yr be i.i.d. random vectors over Sd-1, Let 5 1/N2, and 2 N
We consider the mapping F Pl + (Sd-1) as follows: for any p E PHA let
+ 8V V.p(y.)
ly: + 8V.8.V&....... ol(ys)l22
where V Voply) is the component of ply) orthogonal to the direction Let F(p) = (Zi, (ZI....,Z,,) zr). Then, with probability at least 99/100, we have that for any p E Ung Σ. p(z,) > 0.
To prove Theorem 4.6
consider ply) = + C5( V (Py
E where
C, 5 comes from Lemma 4.5) Noting that Elp(y)]= = 0 and ply) is a polynomial containing only
monomials of degree 27, 27. 2, O we are able apply Lemma 4.4 to obtain the desired result.
See Appendix for the proof.
We now prove our main technical result, Theorem 4.2
Proof of Theurem 4.2
Let 6 = 1/N2 2t.d- We consider the mapping F: Pd > (gd-1yr as follows:
for any p Pd let z;
Iy. +. ply.) where V.p(y) is the component of Vp(y) orthogonal to the direction y. By Theorem 4.6 with probability at least 99/100, we have that for any p ang Theorem
Y.+&V ,Py..)
11-1((2, > 0. Applying Theorem 4.3 yields that there exists some p" E d such that F(p")= = 2 2, form a / Furthermore, we can show that || - -ylll S O(1/N2.4 by elementary calculation (see Appendix C).
4.2 Proof of Theorem 1.2
We first prove Proposition 4.1 based construction of spherical t-design. To achieve this, it suffices to show that with high probability there exist Vi,...,
V, E gm--1 such that
Vi,..., v, is spherical k-design.
|| + vy Iv, vylla 2 9 ((A), s for some A > 0.
Proof of Proposition 4./ Let = mill arccos y,), Applying Fact 3.4 by taking =
yields Pr( 2 A > Pr θ -i -= 2 99/100. This will give
50mmm-1
Pr
min 18<j$r
{lly: y, 112, ly: + + ( Z 99/100,

---

since our choice of m will imply that = 1/v 50mm-1Am By Theorem 4.2 with probability at least 99/100, there exist unit vectors zi...., 2 E -m such that || yyle & ((1/N2x.m)) [r]
and (zj ........ z,) form spherical k-design. Therefore, for any odd homogeneous polynomial p in
m variables of odd degree < k, we have that
r p(z;)
p(z]) p(z)) E [ - p(z) =0,
which implies that Σi=1 ((2,) = holds for any polynomial in m variables of degree less than k. In addition, for every 1 S <. S r, we have that
| + zzll2
Ilyy: y;) (z) y:) + (z) y,)lla 2 Iyy + y ||2 -vil2 1|2] Vzll2
2 ly: + y (1/NN2H,)
This completes the proof.
Proof of Theorem 1.2
Let m = clogr log(1/A]: where -1/10 < A < and 1.99 < c S 2 a constant.
Let d' [1/e)[/A)//0)) and k cmm (0/e)(//A)v000 -1)cl1) In this way, will have 2log(1/A]
that r 2 2m (see Appendix C for calculation details). Therefore, by Proposition 4.1 there exist 5th such that
vectors
En [z))p((z] 0 holds for every odd polynomial p of degree less than k, where g(z) Li=1 sign(v v2]
lIv. + vy 12,, ll, - vylla 2 ((4)
-
For an arbitrary matrix U E m=x" with UUT = Im. denote by Do the instance of mixture of linear classifiers with weight vectors U UTv, Let Dg {Du U E gmxn UUT
I.]. By definition, we have that E
x z] E sign(
! sign
g((U)) z RR, and U = I|v, (A
r. since 22 ((1/A) (/19)).89)) (see Appendix forr the calculation details). Therefore by Proposi- [ion 3.2 any SQ algorithm that solves the decision problem B(D x ({{+1))) must either use queries of tolerance n -Q((), or make at least 2 queries. Lemma 3.8 for any U E RM* with UUT = I.. we have that drv (Du, Do) 2 M(A/r) 2 2(n (((-)) +e), where Dn= = N, x){+ Therefore, by Claim 3.7] any SQ algorithm that learns a distribution in D, within error in total variation distance must either use queries of tolerance n -S((logr((A (/(G) log(1/A))) or make at least 2n queries. This completes the proof.
5 Conclusion
This work establishes a near-optimal Statistical Query (SQ) lower bound for learning uniform mix- tures of linear classifiers under the Gaussian distribution. Our lower bound nearly matches prior algorithmic work on the problem (CDV22]. Our result applies for the simplest (and well-studied) distributional setting where the covariates drawn from the standard Gaussian distribution. This directly implies similar drawn from a more general distribution family (e.g., unknown subgaussian or log-concave distri- bution) that includes the standard normal.
tradeoff's for the setting that the covariates are
From technical perspective, we believe that signs is mathematical contribution of independent interest that could be used to establish SQ lower bounds for other related latent variable models (e.g., various mixtures of experts). natural di- rection to establish coomattioncoompuaaioon tradeoffs for a fixed non-Gaussian distribution on covariates (e.g., the uniform distribution over the Boolean hypercube), for which different hard- ness construction needed.
efficient construction of spherical de-
10

---

References
[AK01] S. Arora and R. Kannan. Learning mixtures of arbitrary Gaussians. In Proceedings of the 33rd Symposium Theory of Computing. pages 247-257, 2001.
[AM05] D. Achlioptas and F. McSheny. On spectral learning of mixtures of distributions. In Proceedings of the Eighteenth Annual Conference on Learning Theory (COLT), pages 458-469, 2005.
[Ban79] E. Bannai. On tight spherical designs. Journal of Combinatorial Theory, Series A, 26(1):38 47, 1979.
[BBH+20] M. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm. Statistical query algo- rithms and low-degree tests are almost equivalent. arXiv preprint 0rXiv:2009.06107, 2020. In 34th Annual Conference on Learning Theory (COLT 2021).
[BRS+ 18) S. Brauchart, A. B. Reznikov, E. B. Saff, H. Sloan, Y. G. Wang, and R. S. Wom- ersley. Random point sets on the sphere-hool hole radii, covering, and separation. Experi- mental Mathematics, 27(1):62-81, 2018.
[RVV13] A. Bondarenko, D. Radchenko, and M. Viazovska. Optimal asymptotic bounds for spherical designs. Annals of mathematics, pages 443 443-452, 2013.
[BS21] R. Buhai and D. Steurer. Beyond parallel pancakes: Quasi-poly Duasi-polynommal time guaran- tees for non-spherical gaussian mixtures. CoRR, abs/2112.05445, 2021.
[BV08] S. C. Brubaker and S. Vempala. Isotropic PCA and Affine-Invariant Clustering, In Proc. 49th IEEE Symposium on Foundations of Computer Science, pages 551-560, 2008.
[CC06] Y. J. Cho and Y. Q. Chen. Topological degree theory and applications. CRC Press, 2006.
(CDV22) A. Chen, A. De, and A. Vijayaraghavan. Algorithms for learning a mixture of linear classifiers. In International Conference on Algorithmic Learning Theory, pages 205- 226. PMLR, 2022.
[CLS20] S. Chen, J. Li, and Z. Song. Learning mixtures of linear regressions in subexponential time via fourier moments. In Proceedings of the 52nd Annual ACM SIGACT Sympo- sium Theory of Computing, pages 587-600, 2020.
[Das99] Dasgupta. Learning mixtures of Gaussians. Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 644, 1999.
[DGS91] P. Delsarte, Goethals, and J. Seidel. Spherical codes and designs. In Geometry and Combinatorics, pages 68-93. Elsevier, 1991.
[DK20] I. Diakonikolas and D. M. Kane. Small covers for near-zero sets of polynomials and learning latent variable models. In Proceedings of the 61 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), 2020.
[DK23] I. Diakonikolas and D. M. Kane. Algorithmic High--Dienssonal Robust Statistics. Cambridge university press, 2023.
[DKKZ20] I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and SQ lower bounds for PAC learning one-hidden-layer relu networks. In Conference on Learning Theory, COLT 2020, volume 125 Proceedings of Machine Learning Research, pages 1514-1539. PMLR, 2020.
[DKPZ21] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality polynomial re- gression for agnostic learning under gaussian marginals in the SQ model. In Conference on Learning Theory, 20212021, volume 134 of Proceedings of Machine Learning Re- search, pages 1552-1584. PMLR, 2021.

---

[DKS17] I. Diakonikolas, D. M. Kane, and A. Stewart. Statistical query lower bounds for robust estimation of high- diheeeiieniii gaussians and gaussian mixtures. In 58th IEEE Anmual Symposium on Foundations of Computer Science, FOCS 20/7, pages 73- 84, 2017. Full version http://arxiv.org/abs/// 1611101411....
[DKS18] I. Diakonikolas, D. M. Kane, and A. Stewart. List-decodable robust mean estimation and learning mixtures of spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1047-1060, 2018. Full version available at https:/aarivaar//bs///11111111
[Fel16] V. Feldman. Statistical query learning. In Encyclopedia of Algorithmm, pages 2090-
2095. Springer New York, 2016.
[FGR+17] 17] Feldman, E. Grigorescu, L. Reyzin, Vempala, and Y. Xiao. Statistical algorithms and lower bound for detecting planted cliques. J. ACM, 64(2):8:1-8:37, 2017.
[FGV17] V. Feldman, C. Guzman, and S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages SIAM, 2017.
[GMP20] V. Gandikota, A. Mazumdar, and S. Pal. Recovery of sparse linear classifiers from mixture of responses. Advances in Neural Information Processing Systems, 33:14688- 14698, 2020.
[GP11] M. Gräf and D. Potts. On the computation of spherical designs by new optimiza- tion approach based on fast spherical fourier transforms. Numerische Mathematik, 1 119(4):699-77)) 2011.
[HKP* 17] S. Hopkins, P. K. Kothari, A. Potechin, P. Raghavendra, T. Schramm, and D. Steurer. The power of uum-or-squares for detecting hidden structures. In 58th IEEE Anmual Symposium Foundations of Computer Science, FOCS 2017, pages 720-731. IEFE Computer Society, 2017
[HL18] S. B. Hopkins and J. Li. Mixture models, robustness, and sum of squares proofs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1021-1034, 2018.
[Hop18] S. B. Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018
[HS17] S. B. Hopkins and Steurer. Efficient bayesian estimation from few samples: Com- munity detection and related problems. In 58th IEEE Anmual Symposium on Foun- dations of Computer Science, FOCS 2017, pages 379-390. IEEE Computer Society, 2017.
[HYJ22] N. Ho, C. Yang, and M. I. Jordan. Convergence rates for gaussian mixtures of experts. The Journal of Machine Learning Research, 23(1):1552-11463,, 2022.
[J194] M. Jordan and R. A. Jacobs. Hicrarchical mixtures of experts and the em algorithm. Neural computation, 6(2):181-216 1994.
[Kan15] D. M. Kane. Small designs for path-connected spaces and path-connected homoge- neous spaces. Transactions of the American Mathematical Society, 367(9)63877-411 2015.
[Kea98] M. J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983-1066, 1998.
[KSV08] R. Kannan, H. Salmasian, and S. Vempala. The spectral method for general mixture models. SIAM Comput., 38(3):1141 116511661-1 2008
[LL18] Li and Liang. Learning mixtures of linear regressions with nearly optimal com- plexity. In Conference On Learning Theory, pages 1 115-1114, PMLR, 2018.
12

---

[LLYH17] W. Li, P. Liang, X. Yuan, and J. Hu. Non-local information for mixture of multiple linear classifiers. In 2017 International Joint Conference on Neural Networks (IJCN)) pages 3741-3746. IEFE, 2017.
[MB14] S. Masoudnia and R. Ebrahimpour. Mixture of experts: literature survey. The Artifi- cial Intelligence Review, 42(2):275, 2014.
[MV10] A. Moitra and G. Valiant. Settling the polynomial learnability of mixtures of Gaussians. In FOCS, pages 102, 2010.
[MVK019] A. Makkuva, Viswanath, S. Kannan, and S. Oh. Breaking the gridlock mixture-of- experts: Consistent and efficient algorithms. In International Conference on Machine Learning, pages 4304-4313, PMLR, 2019.
[Pea94] K. Pearson.
Contribution to the mathematical theory of evolution. Phil. Trans. Roy. Soc. A, 185:71-110, 1894.
[RV17] O. Regev and A. Vijayaraghavan. On learning mixtures of well-separated gaussians. 58th IEEE Anmual Symposium on Foundations of Computer Science, FOCS 2017, pages 25-9.,2017
[SIM14] Sun, S. loannidis, and A. Montanari. Learning mixtures of linear classifiers. In International Conference on Machine Learning, pages 721-729. PMLR, 2014.
[SJA16] H. Sedghi, M. Janzamin, and A. Anandkumar. Provable tensor methods for learning mixtures of generalized linear models. In Artificial Intelligence and Statistics, pages 1231. PMLR, 2016.
[Ver18] R. Vershynin. High-dimensional probability: probaabbbii An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[VW02] S. Vempala and G. Wang. A spectral algorithm for learning mixtures of distributions. In Proceedings of the 43rd Annual Symposium Foundations of Computer Science, pages 113-122, 2002.
[Wom18] R. S. Womersley. Efficient spherical designs with good geometric properties. Con- lemporary computational mathematics-A celebration of the 80th birthday of lan Sloan, pages 1243-1285, 2018.
[XA09] L. Xu and S. Amari. Combining classifiers and learning clopedia of artificial intelligence, pages 318-326. IGI Global, 2009.
In Ency-
13


Reviews:
[{"review_id": "DFK1swTtUk", "reviewer": "Reviewer_TFYT", "summary": "The authors study the problem of learning mixture of linear classifiers with Gaussian covariates. Their primary result is a near-optimal SQ lower bound which applies even for the uniform mixture case. Moreover, as a purely mathematical result, they construct an efficient spherical design (under a stronger definition of the structure) with sample complexity within a polylogarithmic factor of the optimum. ", "questions": "What is the relation of the given problem to that of sparse recovery?\n\nDoes the spherical design technique used to prove your main result extend well beyond simple linear classifiers?\n\nHow can the novel techniques discussed here be applied more broadly outside of the presented problem instance?\n\n", "limitations": "na", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well motivated and introduced succinctly. The strongest portion of the submission are the first two sections which nicely introduce the problem, its inherent difficulties, and a discussion of the papers approach. I thought the technical overview was especially helpful to highlight the problem and challenges in proving the major results.", "weaknesses": "The paper predominantly lacks in presentation of the mathematical results. Namely the major theoretical results presented in the main text are somewhat obtuse and hard to parse / verify the theoretical claims. This may be due my unfamiliarity with the surrounding literature, however the second half of the paper is difficult to follow in the logic of the proofs. While the technical overview helps to introduce the complexities of the analysis, these final sections are entirely non-intuitive. I would suggest to the authors to reduce the number of theorem / lemma statements in the main text and instead more carefully chose results (in line with the major points of Section 1.2). A more expansion on these results with more fleshed out proofs (or proof sketches) would make the paper considerably more readable within the short page limit of the conference. Additionally, it is somewhat hard to tell where the current result fits in with the prior works on the topic. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and effort. \nWe start by addressing the concerns within the review in order:\n\n1. Mathematical Contributions and Presentation.\n\nOur main technical contribution is a novel construction of a spherical $t$-design, which leads to a nearly-optimal SQ lower bound for learning uniform mixtures of linear classifiers (see lines 159 and 160). To achieve this, we leverage ideas and results (Theorem 4.3) from the pure mathematics literature [BRV13]. Although the original theorem in [BRV13] is sophisticated and perhaps non-intuitive for a non-expert, we have distilled and simplified the statement so that it can resonate with ML researchers with theoretical background. In order to help the reader follow the proof idea of our spherical $t$-design construction (Theorem 1.5), we provide high-level explanations in the technical review session (Section 1.2), and also break down our technical results in Section 4 into several short lemmas (see Lemmas 4.4, 4.5 and Theorem 4.6), followed by intuitive prose and proof sketches. We would welcome additional concrete suggestions by the reviewer. \n\n2. Regarding the reviewer’s point:\n“Additionally, it is somewhat hard to tell where the current result fits in with the prior works on the topic.”\n\nIn addition to the mathematical topic of spherical designs, the problem of learning mixtures of linear classifiers is important and fundamental from an ML theory viewpoint. In lines 23 and 24, we clearly state the related algorithmic results for this problem. Previous work [CDV22] gave an algorithm with sample and computational complexity $n^{O(\\log r/\\Delta^2)}$ for the problem, where $\\Delta$ is the minimum separation between linear classifiers. In our work, we provide a nearly optimal SQ lower bound of $n^{\\mathrm{poly}(1/\\Delta)\\log r}$. \n\n\nWe now proceed by addressing the reviewer’s questions below:\n\n1. What is the relation of the given problem to that of sparse recovery?\n\nThe problem we study (learning mixtures of linear classifiers) and the associated techniques in our work are orthogonal to the problem of sparse recovery.\n\n2. Does the spherical design technique used to prove your main result extend well beyond simple linear classifiers?\n\nYes. Our technique works for any odd function in the space $L^2(\\mathbb{R},\\mathcal{N})$, not only for linear classifiers (corresponding to the $\\mathrm{sign}$ function).\n\n3. How can the novel techniques discussed here be applied more broadly outside of the presented problem instance?\n\nWe believe that our new efficient construction of spherical $t$-designs itself is a mathematical contribution of independent interest that could be used to establish SQ lower bounds for other related mixture models (e.g., for mixtures of experts). That said, the focus of our work has been the fundamental problem of learning mixtures of linear classifiers.\n\nReferences:\n\n[BRV13] A. Bondarenko, D. Radchenko, and M. Viazovska. Optimal asymptotic bounds for spherical designs. Annals of mathematics, pages 443-452, 2013.\n\n[CDV22] A. Chen, A. De, and A. Vijayaraghavan. Algorithms for learning a mixture of linear 416 classifiers. In International Conference on Algorithmic Learning Theory, pages 205-226. PMLR, 2022.\n"}, {"review_id": "dSkGrYy6F2", "reviewer": "Reviewer_Jk98", "summary": "The authors prove a lower bound for the number of queries needed in the statistical query model for learning a mixture of linear classifiers. The statistical query model essentially makes oracle queries with a polynomial f(x) and the oracle responds with a value v such that: |v-E[f(x)]\\le t, for some threshold t (the accuracy of the oracle). The main result in the paper is Theorem 1.2 which roughly states that to learn a n-dimensional mixture of linear classifiers within TV distance  \\eps any algorithm must use queries with accuracy 1/poly(n) or must make 2^poly(n) statistical queries.", "questions": "In Theorem 1.2, is it possible to have \\Delta not depend upon r i.e., can the dependence \\Delta > 1/r^10 be eliminated?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The lower bounds are claimed to be tight. \n- The problem of learning a mixture of linear classifiers is simple and elegant and thus important from a learning theory viewpoint.\n- The technical results in the paper leading to Thm 4.2 synthesize ideas from topology and analysis. From a technical perspective the proof is indeed interesting and informative.", "weaknesses": "- The authors claim the lower bound is \"qualitatively match\" previous results by Chen et al. 2022. It would be good to reduce the Che et al result to the SQ model or vice versa. Otherwise the lower bound loses some of its significance.", "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 their effort and positive assessment of our work.\n\n1. Regarding the reviewer’s point:\n“The authors claim the lower bound is \"qualitatively match\" previous results by Chen et al. 2022. It would be good to reduce the Che et al result to the SQ model or vice versa. Otherwise the lower bound loses some of its significance.”\n\nThe algorithm in [CDV22] can be implemented in the Statistical Query(SQ) model efficiently. In fact, the class of SQ algorithms is rather broad and captures a range of known supervised learning algorithms. More broadly speaking, several known algorithmic techniques in machine learning are known to be efficiently implementable using SQ algorithms. These include spectral techniques, moment and tensor methods, local search (e.g., Expectation Maximization), and many others (see, e.g., [FGR+17, FGV17]).\n\nWe respond to the reviewer’s question below:\n\n1. In Theorem 1.2, is it possible to have $\\Delta$ not depend upon $r$ i.e., can the dependence $\\Delta \\ge r^{-1/10}$ be eliminated?\n\n\nOur lower bound proof requires the assumption that $\\Delta\\ge r^{-c}$ for some absolute constant $0<c<1$. We note that this parameter setting is arguably the most interesting in practical settings. \nIn our technical proof, the lower bound comes from Proposition 3.2 [DKPZ21], where it requires the low dimension $m \\ge2$. In particular, to apply the techniques in our setting, we randomly sample $r$ $\\Delta$-separated unit vectors over the $m$-dimensional unit sphere with sufficiently small error guarantees. This is impossible without the dependence on $\\Delta$. In addition, by taking $\\Delta=r^{-c}$, we do provide a lower bound for small $\\Delta$. However, since the algorithmic result of [CDV22] has sample and runtime complexity $\\min(n^{O(\\log r/\\Delta^2)},(n/\\Delta)^{O(r)})$, which will be $(n/\\Delta)^{O(r)}$ if $\\Delta$ is sufficiently small.\nThis provides strong evidence that we are not able to obtain near-optimal hardness results without the assumption on $\\Delta$.\n\nReferences:\n\n[CDV22] A. Chen, A. De, and A. Vijayaraghavan. Algorithms for learning a mixture of linear 416 classifiers. In International Conference on Algorithmic Learning Theory, pages 205-226. PMLR, 2022.\n\n[DKPZ] I. Diakonikolas, D. M. Kane, T. Pittas, and N. Zarifis. The optimality of polynomial re435 gression for agnostic learning under gaussian marginals in the SQ model. In Conference 436 on Learning Theory, COLT 2021, volume 134 of Proceedings of Machine Learning Re437 search, pages 1552-1584. PMLR, 2021.\n\n[FGR+17] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2):8:1-8:37, 2017.\n\n[FGV17] V. Feldman, C. Guzman, and S. S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1265-1277. SIAM, 2017. \n"}, {"review_id": "RGJQziYpBy", "reviewer": "Reviewer_vDTe", "summary": "The paper provides statistical query lower bounds for learning mixture of linear classifier.\n\nIn the problem of learning mixture of linear classifier, there are $r$ linear classifier $v_1, \\ldots ,v_r \\in \\mathbb{R}^{n}$. The input feature $x\\in \\mathbb{R}^{n}$ is draw from gaussian, the label $y = \\mathsf{sign}(v_\\ell^\\top x)$, where the index $\\ell$ is chosen with probability $w_{\\ell}$ (one has $w_1 +\\cdots +w_{r} = 1$). Previous work [CDV'22] give an algorithm of sample complexity $n^{\\log(r)/\\Delta^2}$ where $\\delta$ is the minimum separation between classifiers. The major contribution of this paper is to give an almost matching lower bound of $n^{\\log (r) \\cdot \\mathsf{poly}(\\Delta^{-1})}$, under the SQ model.\n\nFrom a high level, the paper follows the framework of [DKS'17] and reduces the problem to sphere design. The major technical contribution of this paper is to provide a spherical design and find a set of vector from unit ball that satisfies (1) none trivial pairwise distance and (2) the correlation with any low degree polynomial equal $0$. They obtain the spherical design using a topological argument inspired from [BRV'13].\n\n\n----------------------\nI have read the rebuttal and I would keep my positive evaluation of the paper.", "questions": "(1) I have some concern with Lemma 3.5. In the statement, it is only required that $f \\in L^2(R, N)$, but it seems not true for every such function, right? If I understand correctly, the proof only requires $f = sign$ (i.e., only need to work for sign function), but even for sign function, the claim is sloppy, because $E_{z\\sim N_m} [p(z)f(v^\\top z)]$ scaling invariant with $v$, which seems not true for polynomial?\nPlease clarify this point.\n\n\n(2) Is the algorithm of [CDV'22] falls into the SQ framework? ", "limitations": "no", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper gives an almost matching SQ lower bound for learning mixture linear classifier, the technique is novel and could have broad applications.", "weaknesses": "There is no major weakness, though I have a few minor questions (to be specified later)", "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 their effort and positive assessment of our work. \n\nWe respond to the reviewer’s questions below:\n\n1. I have some concern with Lemma 3.5. In the statement, it is only required that $f\\in L^2(\\mathbb{R},\\mathcal{N})$, but it seems not true for every such function, right? If I understand correctly, the proof only requires $f = \\mathrm{sign}$  (i.e., only need to work for $\\mathrm{sign}$ function), but even for $\\mathrm{sign}$ function, the claim is sloppy, because $\\mathbf{E}_{z\\sim \\mathcal{N}_m}[p(\\mathbf{z})f(\\mathbf{v}^\\intercal\\mathbf{z})]$ scaling invariant with $\\mathbf{v}$, which seems not true for polynomial? Please clarify this point.\n\nWe thank the reviewer for pointing this out. The statement of Lemma 3.5 requires the assumption that $\\mathbf{v}$ is a unit vector (or, more generally, a non-zero vector of fixed $L_2$-norm). \nPlease note that we only invoke this lemma for $\\mathbf{v}$ being a unit vector. Without this assumption, the conclusion is not true (as the reviewer pointed out). Under the assumption that $\\mathbf{v}$ is a unit vector, Lemma 3.5 holds as stated, i.e., for any function $f$ in the space $L^2(\\mathbb{R},\\mathcal{N})$ (not only for the $\\mathrm{sign}$ function).\n\n\nLooking at the proof of Lemma 3.5 in the appendix, we also want to point out that Claim B.1 requires the assumption that both $\\mathbf{U}$ and $\\mathbf{V}$ are projection matrices (i.e., $\\mathbf{U}\\mathbf{U}^{\\intercal}=I_{n_1}$, and $\\mathbf{V}\\mathbf{V}^\\intercal=I_{n_2}$), because the equations in line 576 hold only if both $\\mathbf{U}$ and $\\mathbf{V}$ are projection matrices.\n\n2. Is the algorithm of [CDV22] falls into the SQ framework?\n\nThe algorithm in [CDV22] can be implemented in the Statistical Query(SQ) model efficiently. In fact, the class of SQ algorithms is rather broad and captures a range of known supervised learning algorithms. More broadly speaking, several known algorithmic techniques in machine learning are known to be efficiently implementable using SQ algorithms. These include spectral techniques, moment and tensor methods, local search (e.g., Expectation Maximization), and many others (see, e.g., [FGR+17, FGV17]).\n\nReferences:\n\n[CDV22] A. Chen, A. De, and A. Vijayaraghavan. Algorithms for learning a mixture of linear 416 classifiers. In International Conference on Algorithmic Learning Theory, pages 205-226. PMLR, 2022.\n\n[FGR+17] V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao. Statistical algorithms and a lower bound for detecting planted cliques. J. ACM, 64(2):8:1-8:37, 2017.\n\n[FGV17] V. Feldman, C. Guzman, and S. S. Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1265-1277. SIAM, 2017. \n"}, {"review_id": "5Iuy0RI1w2", "reviewer": "Reviewer_Azis", "summary": "A statistical query (SQ) algorithm is an algorithm that attempts to learn the data distribution $D$ by querying $f$ to the oracle who responses with $v$ such that $\\lvert v - E_{x\\sim D} f(x) \\rvert$ is small. In this paper, the authors study the problem of finding an SQ lower bound for learning a mixture of linear classifiers. The main ingredients are \n\n1. a result in [DKPZ21], which establishes an SQ lower bound on testing a distribution of $(x,y)\\in \\mathbb{R}^n\\times \\{-1,1\\}$ where $x$ is normal, $E[y \\vert x = z]=g(Uz)$ for some function $g$ with zero low-degree moments and some matrix $U$.\n2. Authors' construction of well-separated _spherical design_, that is, unit vectors $v_1,\\ldots,v_r$ such that $g(z) = \\frac1{r}\\sum_{\\ell=1}^r\\text{sign} (v_{\\ell}^Tz)$ has zero low-degree moments, as required in 1.\n\nAnd the last step is to turn the testing problem into the problem of learning the mixture of linear classifiers. The proof of the main theorem is presented in the main paper, whereas those of several lemmas are postponed to the appendix.\n\n", "questions": "1. the authors have mentioned that the main result provides \"a near-optimal information-computation tradeoff for the problem\". Does this mean that the problem of finding an optimal tradeoff is still open.\n2. Related to 1., are there any open problems introduced, or related to this work?\n3. The idea of using spherical designs could be used to find SQ lower bound of other learning problems in which $g$ is an odd function. Are there any other learning problems that the authors have in mind?\n4. Can the result be extended to non-normal data?", "limitations": "The authors should include a section on discussion, or limitations of the main results. For example, I have already mentioned the case where the data is non-normal. \n\nAlso, am I correct in assuming that the result only applies when $r$ is already known. Is there anything we can do when $r$ is not known?", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors have established a new SQ lower bound which matches the algorithmic guarantees in some cases [CDV22].\n- The idea of designing and using spherical designs to obtain the lower bound is interesting and can be applied to other learning problems.\n- The writing is well-organized and it is easy to see the high-level idea of the proof.", "weaknesses": "My only minor concern is that there is a lack of discussion of the main result. See Questions below for some questions that I have in mind.\n\n", "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 their effort and positive assessment of our work.\n\nWe start by addressing the reviewer’s concerns in the “Limitations” sections below:\n\n1. “Also, am I correct in assuming that the result only applies when $r$ is already known. Is there anything we can do when $r$ is not known?”\n\nIn our work, we prove a lower bound for known $r$, which automatically establishes the hardness for the (more challenging) setting where $r$ is unknown. On the other hand, we do not know any algorithmic result for unknown $r$.\n\n\n2. “The authors should include a section on discussion, or limitations of the main results.”\n\nAfter the statement of our main Theorem 1.2, we include a section (line 89 - line 105) to discuss the implications of our result. Our understanding is that a “Limitations” section is not required at NeurIPS’23. If this is not accurate, we will be happy to include one in the revised version. \n\nWe now proceed by addressing the reviewer’s questions below:\n\n1. The authors have mentioned that the main result provides \"a near-optimal information-computation tradeoff for the problem\". Does this mean that the problem of finding an optimal tradeoff is still open.\n\nOur SQ lower bound qualitatively matches the best known algorithm in the sense that both the upper and the lower bound are of the form $n^{\\mathrm{poly}(1/\\Delta)\\log(r)}$. On the other hand, the degree of the polynomials in the exponent do not exactly match. Specifically, in our SQ lower bound, the exponent on $(1/\\Delta)$ is around $1/10$, which is strictly smaller than the one for the algorithmic result of [CDV22].\n\n2. Are there any open problems introduced, or related to this work?\n\nAn interesting research direction is to understand if our techniques can be leveraged to obtain SQ lower bounds for other mixture models (e.g., for other mixtures of experts). In addition to SQ lower bounds, it would also be interesting to establish reduction-based hardness for such problems, starting, e.g., from cryptographic assumptions. A more concrete open problem is to obtain sharper lower bounds for this particular problem (matching the constant in the exponent as well). \n\n3. The idea of using spherical designs could be used to find SQ lower bound of other learning problems in which $g$ is an odd function. Are there any other learning problems that the authors have in mind?\n\nWhile the focus of our work has been on learning mixtures of linear classifiers, we believe that a similar approach ought to apply for other “mixtures of experts” problems. We leave this as a direction for future work.\n\n\n4. Can the result be extended to non-normal data?\n\nThe main point of our work is that we establish a hardness result (SQ lower bound), even for the arguably simplest (and well-studied) setting where the covariates are drawn from the standard Gaussian distribution. This implies similar SQ lower bounds, e.g., when the covariates are drawn from a more general distribution family (e.g., an unknown subgaussian or log-concave distribution) that includes the standard normal. If one wants to establish SQ lower bounds for a non-Gaussian fixed distribution on covariates, a different construction is needed.\n\nReferences:\n\n[CDV22] A. Chen, A. De, and A. Vijayaraghavan. Algorithms for learning a mixture of linear 416 classifiers. In International Conference on Algorithmic Learning Theory, pages 205-226. PMLR, 2022.\n"}, {"review_id": "nx6ieRc7La", "reviewer": "Reviewer_n8Pi", "summary": "This paper studies the problem of learning mixtures of linear classifiers under Gaussian sampling. The paper provides a stastical query lower bound which demonstrates that known algorithms for the problem in the literature are essentially best possible, even for the special case of learning uniform mixtures. It further establishes the complexity of any SQ algorithm.", "questions": "The paper is well written and easy to follow. There are some notation issues. For example, in the abstract, \"y=sign(<v_\\ell,x>))\" where y shall be y_\\ell right? This also appeared in several places in the paper. Plus, one right parenthesis ) shall be removed.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "+) Statistical query complexity of learning mixtures of linear classifiers\n+) Efficient spherical designs to fullfill the required separation assumptions for the results to hold", "weaknesses": "This paper is primarily a theoretical work. The assumptions, problem setup, and results are only of theoretical interest. I am not sure if the results and technical tools are interesting to the broad machine learning systems society.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and effort. We will address the typos pointed out in the revision.\n\nThe reviewer’s stated weakness of our work is the fact that it is “primarily a theoretical work”. \nWe respectfully point out that theoretical research in machine learning (“learning theory”) is well within the scope of NeurIPS’23 and explicitly mentioned in the call for papers. We request that our submission is judged on its merits according to the specified criteria in the call for papers.\n\nSpecifically, the problem that we study (learning mixtures of linear classifiers) is a classical problem in machine learning and understanding its computational complexity is a question of fundamental importance. Our work provides near-optimal SQ lower bounds for this problem, suggesting that known algorithms are essentially best possible. In the process, our work develops novel constructions of spherical designs that are of independent interest. In summary, we believe that our contributions are of significant interest to the theoretical ML community that has a strong presence at NeurIPS.\n\n"}]

Author rebuttal:
We thank the reviewers for their time and effort in providing feedback. We are encouraged by the positive comments from reviewers (**Jk98**,**vDTe**,**Azis**) for the following:
(i) the importance of the problem we study (learning mixtures of linear classifiers) 
and the tightness of our SQ lower bound (**Jk98**,**vDTe**,**Azis**), (ii) the novelty and potentially broader applicability of our technique (**Jk98**,**vDTe**,**Azis**), and (iii) well-organized writing (**Azis**).


The main contribution of our paper is theoretical. Specifically, we establish a near-optimal Statistical Query (SQ) lower bound for learning uniform mixtures of linear classifiers. Our lower bound applies even for the simplest distributional setting where the covariates are drawn from the standard Gaussian. Our SQ lower bound nearly matches prior algorithms for this problem that can be efficiently implemented in the SQ model (line 96). In the process, we give a new efficient construction of spherical designs that is of independent interest.

We will address the individual questions and comments by the reviewers separately.


Meta-review: The authors prove a statistical query lower bound for the problem of learning mixtures of linear classifiers, using a new construction of spherical designs. 

Given the technical nature of the topic, some reviewers found it too theoretical or hard to follow. Nevertheless, the reviewers were generally positive about the paper.

I recommend acceptance.
Decision: Accept (poster)