On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries

We thank the reviewer for their appreciation and their valuable feedback! Below we address the weaknesses and questions.

Addressing the weakness: Thank you for pointing that out. We will add a more intuitive summary of the proof, especially how Equality $(25)$ is derived and how the Leap exponent appears in the RHS.

We define the null distribution as the distribution with matching marginals $(y,\boldsymbol{x})$ where the label only depends on the support of $\boldsymbol{x}$ discoverable with leap $k_*-1$. Hence, to make any progress, any new detectable set added to the support needs to contain at least $k_*$ new coordinates. In the second moment, to have a non-zero contribution, we need the permutation to map the support to a detectable subset, i.e. the permutation to map to a subset of size at least $k$, which has probability $d^{-k_*}$ over permutation.

Questions:

1. Yes, the characterization generalizes to any query class $\mathcal{Q}$ with the class specific system of detectable subsets, where the set of test functions $\Psi$ is simply defined as the set of $\\{ y \mapsto \phi (y,\boldsymbol{u}) : \phi \in \mathcal{Q}, \boldsymbol{u} \in \mathcal{X} \\}$. The lower bound is proved under this general setting. However, note that our upper bound uses that (13) can be obtained using a query $\phi \in \mathcal{Q}$. We can add a further property on the set $\mathcal{Q}$ so that it is the case (note that the lower bound in Theorem 5.1 is not achievable for all classes $\mathcal{Q}$, for example if $\mathcal{Q}$ only contains $\phi(y,\boldsymbol{x}) = y$. However, we consider these cases to be less interesting).

2. Yes, the general intuition behind the universality is correct. Roughly speaking, we need functions ($\mathcal{Y} \to \mathbb{R}$) of the form $\Psi_{\mathsf{DLQ}}$ for a loss $\ell$ mentioned in Eq (14) to be dense in $L^2(\mu_y)=\Psi_{\mathsf{SQ}}$ to match the $\mathsf{SQ}$ complexity for any link distribution. For the squared loss, $\Psi_{\mathsf{DLQ}}$ only contains affine functions, and thus are not dense in $L^2(\mu_y)$ (except for $y$ supported on two points where $\mathsf{SQ}=\mathsf{CSQ}$).

The intuition for Proposition 6.2.(c) is indeed similar: $\Psi_{\mathsf{DLQ}}$ is a set of polynomials and is not dense in $L^2(\mu_y)$ (except when the support of $y$ is finite and the dimension of the span of the polynomials in $\Psi_{\mathsf{DLQ}}$ is equal to the number of points in the support, i.e., all polynomials of degree is at most $P-1$, where $P$ is the support size). However, it is more powerful than $\Psi_{\mathsf{CSQ}}=\\{ y \mapsto y \\}$ which only contains identity, and there exist distributions such that the $\mathsf{DLQ}$ exponents will be strictly smaller than the $\mathsf{CSQ}$ exponents.

3. We do not quite understand the question on “$\mathsf{SQ/CSQ}$ provably not capturing SGD”. In general, the question of whether $\mathsf{SQ}$-type lower bounds capture the complexity of SGD algorithms (and other algorithms) is a subtle and difficult one. First, SQ lower bounds are proved under “adversarial noise” (worst case response in the tolerance interval $[-\tau,\tau]$) instead of statistical noise (when samples are used to evaluate the expectations). Second, $\mathsf{SQ}$-algorithms only constrain the access to the data distribution, and not on how the responses are combined to produce the next query and the output (for example, in Section 7, $\log d$ online SGD steps are enough to discover the support by looking at the gradient evaluations, however regular SGD will require $O(d)$ online SGD steps for the weights of the neural network to be updated and fit the target function).

In general, it is known that $\mathsf{SQ}$ cannot capture the complexity of learning algorithms that use samples (e.g., separation results between PAC and $\mathsf{SQ}$ learning), even for SGD on neural networks. Indeed, [Abbe et al. 2021b] shows that with enough machine precision and for any PAC algorithm, one can construct a neural network such that SGD emulates it by implementing sample extraction. However, such a neural network is highly irregular. It is however conjectured that $\mathsf{SQ}$ lower bounds capture the complexity of a large class of regular algorithms (e.g., regular neural networks such as fully connected neural networks). Note that proving general computational lower bounds is difficult, and researchers often only prove lower bounds against restricted classes of algorithms such as $\mathsf{SQ}$.

Another subtlety concerns the reuse of samples between different queries. [Dandi et al 2024] shows that by re-using samples, SGD on square loss can beat the $\mathsf{CSQ}$ lower bound. This requires choosing hyperparameters (batch size and step size) such that two gradient steps interact to transform two $\mathsf{CSQ}$ queries into one $\mathsf{SQ}$ query. In general, we expect that sample reuse will not be able to beat $\mathsf{SQ}$ lower bounds on regular architectures (as discussed above), while $\mathsf{CSQ}$ (and $\mathsf{DLQ}$) will capture online SGD or multi-pass SGD where the hyperparameters are not chosen carefully.

Many of these issues are open questions, which do not (yet) have satisfactory answers. We discuss some of them in the introduction and the discussion section (Section 8). We will expand these discussions in the revised version.

4. Yes, you are understanding correctly. Using Eq $(26)$ we get that there are two members from $\mathcal{H}^d_\mu$ whose query responses are compatible with the null $\nu_{\mathcal{S}_*}$ and hence also mutually compatible. This then establishes the failure of the learning algorithm.

We thank the reviewer for their appreciation and their valuable feedback! Below we address the weaknesses and questions.

Simulations:

Following the reviewer’s suggestion, we will include additional figures (beyond just the function $y_2$) in a separate section, as well as details on the architecture and algorithm used in the simulations. We will further improve their presentations to make them more striking. In all simulations, we use the two-layer neural network stated in Eq $(15)$, with a sigmoid activation function. We set the biases to 0 and train simultaneously $a_j$ and $w_j$ with vanilla one-pass SGD and stepsize $\propto 1/d$.

Only tackling sparse functions: In this paper, we focus on the setting of learning sparse functions (juntas). Note that learning juntas is a popular model in learning theory, and has been the testbed for many investigations on the power of different classes of algorithms. For example, learning sparse functions on the hypercube has been studied in the context of $\mathsf{SQ}$ [Kearns 1998], differentiable learning [Abbe et al. 2021b], and SGD on regular neural networks [Abbe et al. 2022, 2023, Telgarsky 2022, Margalit 2023].

[Abbe et al, 2023] considers both uniform on the hypercube and isotropic Gaussian data, which are associated to two symmetry groups: the permutation group and orthogonal group respectively. In this paper, we focus on the permutation group. However, compared to [Abbe et al, 2023], which only considers the hypercube and adaptive $\mathsf{CSQ}$, we vastly generalize their results by allowing: 1) general product measurable spaces, 2) general $\mathcal{Q}$-restricted $\mathsf{SQ}$ algorithms, including $\mathsf{SQ}$ and $\mathsf{DLQ}_{\ell}$, 3) both adaptive and nonadaptive algorithms. We show that in this general setting, the complexity of $\mathsf{SQ}$ algorithms is tightly captured by a leap and cover complexities. This demonstrates the generality of the leap complexity first introduced in [Abbe et al 2022, 2023]: it is induced by the permutation group structure rather than any other properties of the hypercube, and extends beyond $\mathsf{CSQ}$ to any $\mathcal{Q}$-restricted $\mathsf{SQ}$ algorithms by changing which subsets of coordinates can be detected.

We further emphasize that key takeaways from our paper are fully independent of [Abbe et al. 2022, 2023, Damian et al 2023, 2024]: (1) The introduction of $\mathcal{Q}$-restricted $\mathsf{SQ}$ algorithms, in particular $\mathsf{DLQ}$ that generalizes $\mathsf{CSQ}$ algorithms, which are novel to the best of our knowledge. (2) Functions with high $\mathsf{CSQ}$ Leap [Abbe et al 2023] can still be learned at much lower complexity by simply changing the loss function, with a tight characterization for a given loss function and target distribution using $\mathsf{DLQ}_\ell$, as well as in the mean-field regime for SGD on two-layer neural networks.

The other setting that was considered in the literature is the case of isotropic Gaussian data: isoLeap with multi-index functions and $\mathsf{CSQ}$ [Abbe et al, 2023], information exponent for single index and $\mathsf{CSQ}$ [Damian et al, 2023], and generative exponent for single index and $\mathsf{SQ}$ [Damian et al, 2024]. We believe that our results can be extended to this setting (and more general symmetry groups), and we are planning to report on these extensions in future work. See also the discussion in Section 8.

Finally, note that our results apply to isotropic Gaussian data where the multi-index function is coordinate aligned (e.g. when the coordinate system is known in advance).

Questions:

Theorem 5.1 shows algorithms that match the lower bounds for $\mathsf{SQ}, \mathsf{CSQ}$, and $\mathsf{DLQ}_\ell$. The algorithm is straightforward: in the definition of the detectable subgroups, the condition $(13)$ corresponds to one query evaluation. Then these queries can be combined following the leap and cover complexities. See also Remark 5.2 and the proof of the upper bound in Appendix B.4 which shows how to trade-off tolerance and number of queries (resulting in an extra $\log(d)$ factor). Further note that these upper bounds require the knowledge of the link function. However, this can be relaxed following a procedure similar to [Damian et al 2024b] (see Remark 5.3).

We thank the reviewer for their appreciation and their valuable feedback! Below we address the weaknesses/questions in order:

Intuition behind easily learnable functions: The simple characterization for the generative exponent in [Damian et al. 2024] is due to the setting they consider: 1) Gaussian data, 2) single-index model, 3) SQ algorithms. This allows them to define their generative exponent in terms of (one-dimensional) hermite coefficients of the Radon-Nikodym derivative. In our case, we have 1) generic product spaces, 2) multi-index functions, 3) $\mathcal{Q}$-restricted $\mathsf{SQ}$ algorithms. The generality of our setting doesn’t allow for such a simple characterization. We further believe that despite the generality of our results, the characterization remains surprisingly simple: the $\mathcal{Q}$ class of queries defined a system of detectable subsets, while the leap and cover complexities describe how to combine these subsets to achieve the optimal query complexity (similarly to [Abbe et al. 2023] for $\mathsf{CSQ}$ leap on the hypercube).

In the case of $\mathsf{SQ}$, $T(y)$ in $(13)$ can be replaced by the Radon-Nikodym derivative (see Proposition A.1) and an equivalent characterization can be obtained by looking at its decomposition in the tensor product basis (analogous to the Hermite polynomials in [Damian et al. 2024]). However, for general $\mathcal{Q}$-restricted $\mathsf{SQ}$, no such simplification exists. Because of this generality, no simple principle allows us to characterize the $\mathsf{DLQ}$ exponent besides Definitions 1 and 2. Hence, Theorem 5.1 should be thought of as a meta-theorem where one has to characterize detectable sets for each given setting (see below for illustrations and response to reviewer Grg1). But we again emphasize that this abstract characterization captures precisely the complexity of $\mathcal{Q}$-restricted algorithms for learning juntas.

As for the question on $\mathsf{SQ}$ vs $\mathsf{CSQ}$ for detectable sets being not too different on the hypercube data: unfortunately, this intuition is not correct. In particular, on the hypercube data, even with discrete outputs, there are functions with $Leap_{\mathsf{SQ}}=1$ but $Leap_{\mathsf{CSQ}}=P-1$, where $P$ is the support size, i.e. we can get arbitrarily large separations between these complexities even on the hypercube data. See for example the proof of Proposition 6.2.(c) for such an instance.

For $\mathsf{DLQ}$, we show an example that is strictly between $\mathsf{SQ}$ and $\mathsf{CSQ}$, when the loss function is a polynomial. However, for non-polynomial loss, we expect in general that $\mathsf{SQ}=\mathsf{DLQ}$ (see Proposition 6.2).

Let us add that for the example in Proposition 6.2.(c) proof, our results in Section 7 show that it can be learned in linear scaling by SGD with $\ell_1$ loss (or a smoothed version to satisfy our technical conditions) on a two-layer neural network, while we expect online SGD on the squared loss to require $d^{P-2}$ iterations. See response to Reviewer zev8.

Rotational symmetries and clarification $(q,\tau)$ relationship: Note that in [Damian et al. 2024], they can show an analogous lower bound $q/\tau^2 \geq d^{k/2}$, where $k$ is the generative exponent. They further show that if $\tau^2 > d^{-k/2}$, an exponential number of queries is required. However, one should be careful in interpreting lower bounds for SQ algorithms: for example, such an exponential lower bound exists for $\mathsf{CSQ}$ (i.e., with adversarial noise), while [Damian et al. 2023] presents an algorithm with a polynomial number of queries and $\tau = \Theta(1)$ with statistical noise (batch size $1$ online SGD). Interestingly, their second lower bound for low-degree polynomials shows that there is an information-to-computational gap in their model: $\Theta (d)$ samples is optimal information-theoretically, while $\Omega (d^{k/2})$ samples are necessary for a low-degree polynomial algorithm to succeeds. Such an information-to-computation gap does not appear in the axis-aligned case (permutation symmetry), even when considering Gaussian data (both are $\Theta (\log(d))$).

If we consider a rotational equivariant algorithm to learn a sparse function on the hypercube, the issue is subtle. [Margalit 2023] (and generalizations of their results) show that the information-theoretic threshold becomes $\Theta(d)$ (instead of $\Theta (\log (d))$). However, we believe that an information-to-computation gap does not appear: one can use the input $\boldsymbol{x}$ to first learn the axis (which requires $O(d)$ samples) and then fit a sparse function on these coordinates (which requires $O(\log d)$ samples). An open problem would be to show that a regular equivariant algorithm, such as SGD on a two-layer neural network, cannot emulate this axis-alignment first stage and would inherit the information-to-computation gap from Gaussian data.

Clarification on Assumption 2.1: Indeed this assumption requires a longer discussion which we will include in the revised version. In short, Assumption 2.1 is necessary for our results to hold in the case of continuous functions, as argued in [Vempala, Wilmes, 2019]: with a finite and noiseless class of functions $\mathcal{H}$, it turns out that $\log |\mathcal{H}|$ queries are sufficient with $\tau^2 = \Theta (1)$ under a weak “non-degeneracy” assumption. Hence, enough noise in the link function is required to prevent these algorithms (that require highly non-regular measurable functions). Intuitively, Assumption 2.1 is a quantitative measure for “enough noise in the concepts”. E.g., it is easy to check that Assumption 2.1 will always be satisfied for the link of the form $y=f_*(\boldsymbol{z})+\varepsilon$, for any bounded $f_*$ and $\varepsilon \sim \mathsf{N}(0,\sigma^2)$ as soon as $\sigma>0$, for arbitrary product measure on $\mathcal{X}^d$.

We continue in common rebuttal space for the last point.

Another clarification regarding Assumption 2.1 which some reviewers were concerned about:

We phrased the assumption this way since we wanted to be as general as possible while maintaining rigor. The Assumption always holds for $y=f_*(\boldsymbol{z})+\mathsf{N}(0,\sigma^2)$, with $\sigma^2>0$, which is a more restricted continuous model of perhaps the greatest interest--we will emphasize this better in the paper. We note that an alternative proof, that we will include in the final version, can avoid this assumption for $\mathsf{DLQ}$ with analytic loss (including $\mathsf{CSQ}$), but not for general $\mathsf{SQ}$ or $\mathsf{DLQ}$, as noted in Valiant [2012], Song et al. [2017], Vempala and Wilmes [2019], Andoni et al. [2014].

Essentially all related $\mathsf{SQ}$ lower bounds require this assumption (i) sometimes implicitly [Damian et al. 2024, Feldman et al. 2018] (ii) or by the virtue of $\mathcal{X}$ being discrete [Diakonikolas et al. 2022, Feldman et al. 2017, Abbe et al. 2023] or only considering $\mathsf{CSQ}$ [Damian et al. 2023, Abbe et al. 2023] (iii) or by restricting to $y=f_*(\boldsymbol{z})+$ noise [Abbe et al. 2023]. Even more generally in hypothesis testing literature, see [Hopkins 2018, Kunisky et al. 2019] for low degree lower bound and [Perry et al., 2018] for contiguity lower bounds.

Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and juntas. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 11–20. IEEE, 2012.

Le Song, Santosh Vempala, John Wilmes, and Bo Xie. On the complexity of learning neural networks. Advances in neural information processing systems, 30, 2017.

Santosh Vempala and John Wilmes. Gradient descent for one-hidden-layer neural networks: Poly- nomial convergence and sq lower bounds. In Conference on Learning Theory, pages 3115–3117. PMLR, 2019.

Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang. Learning sparse polynomial functions. In Proceedings of the twenty-fifth annual ACM- SIAM symposium on Discrete algorithms, pages 500–510. SIAM, 2014.

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64 (2):1–37, 2017.

I Diakonikolas, D Kane, L Ren, Y Sun. SQ lower bounds for learning single neurons with Massart noise. Advances in Neural Information Processing Systems, 2022.

Samuel Hopkins. Statistical inference and the sum of squares method. PhD thesis, Cornell University, 2018.

Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pages 1–50. Springer, 2019.

Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra. Optimality and sub- optimality of pca i: Spiked random matrix models. The Annals of Statistics, 46(5):2416–2451, 2018.