Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise

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.

Classification v.s. Regression:

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

On 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).

Technical Novelty:

Given 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. Rather surprisingly, we show a strong computational separation between the binary and the ternary cases.
Furthermore, 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.

Reference:

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

[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)

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

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

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

We thank the reviewer for the appreciation and useful feedback.

Technical Contributions:

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

Specifically, 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. In particular:

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

Additionally, 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.

LP formulation for MLC in the realizable setting:

This 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).

Realizable v.s. Non-realizable:

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

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

The references are included in the response to Reviewer 4NDD.

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.

Definition of $H$ in the proof of Theorem 6.2:

We 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$. We will fix this minor issue in the revised version of the manuscript.

Importantly, we want to emphasize that this typo does not affect the correctness of Theorem 6.2 and its corollaries for the following reasons.

First, 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.

Possible positive results on MLC with RCN:

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

Phase transition for $\sigma$:

We 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) we 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 and precisely characterize this threshold–namely, whether $H$ is not invertible for some $\sigma$, but we are still able to solve the problem efficiently.