SQ Lower Bounds for Learning Mixtures of Linear Classifiers

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.

Strengths

+) Statistical query complexity of learning mixtures of linear classifiers +) 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.

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.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

NA

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 1. 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$. 2. 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. And 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.

Strengths

- The authors have established a new SQ lower bound which matches the algorithmic guarantees in some cases [CDV22]. - The idea of designing and using spherical designs to obtain the lower bound is interesting and can be applied to other learning problems. - 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.

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. 2. Related to 1., are there any open problems introduced, or related to this work? 3. 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? 4. Can the result be extended to non-normal data?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

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. 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?

Summary

The paper provides statistical query lower bounds for learning mixture of linear classifier. In 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. From 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]. ---------------------- I have read the rebuttal and I would keep my positive evaluation of the paper.

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)

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? Please clarify this point. (2) Is the algorithm of [CDV'22] falls into the SQ framework?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

no

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.

Strengths

- The lower bounds are claimed to be tight. - The problem of learning a mixture of linear classifiers is simple and elegant and thus important from a learning theory viewpoint. - 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.

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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

NA

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.

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.

Questions

What is the relation of the given problem to that of sparse recovery? Does the spherical design technique used to prove your main result extend well beyond simple linear classifiers? How can the novel techniques discussed here be applied more broadly outside of the presented problem instance?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

na

Thanks for clarification.

Thanks for the clarification. Please consider adding the assumptions on $v$ to the theorem statement.

Response

I am satisfied with the authors' answers. A comment: > 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. My suggestion is that the authors can add their rebuttal to a "future direction" section; for example: > While 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. > If one wants to establish SQ lower bounds for a non-Gaussian fixed distribution on covariates, a different construction is needed.

Thanks for the rebuttal!

Thanks the authors for the rebuttal and for addressing the issues. After reading the rebuttal and other reviewers' comments, I am updating thescore to Borderline accept.