Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models

We thank the reviewer for their time, effort, and positive evaluation of our work. We address the reviewer's question below.

The arxiv paper by [Damian et al., 2025] pointed out by the reviewer (arXiv:2506.05500) appeared online on June 5, three weeks after the NeurIPS submission deadline. As a result, we were unable to include a comparison in our submission.

We provide a brief comparison below, and we would be happy to incorporate it in the revised version of our paper.

At a high-level, while our work and [Damian et al., 2025] study qualitatively similar tasks (“learning multi-index models”), the two works address fundamentally different objectives:

• PAC Learning vs. Parameter Recovery: Our submission focuses on the PAC learning task, i.e., the task of obtaining a hypothesis with low prediction error (without requiring to identify the underlying subspace). In contrast, [Damian et al., 2025] focuses on parameter recovery, aiming to precisely estimate the underlying subspace. Note that PAC learning may be feasible in settings where parameter recovery is information-theoretically impossible. Specifically, it is possible to design very simple functions that admit accurate predictors even when the subspace is not identifiable. We mentioned this distinction in our submission, when we compared against the prior work [DBLP24] (which focused on single-index models); see lines 1406-1413.

• Agnostic Noise: Our submission provides conditions and provable guarantees for both the realizable/independent label noise and the agnostic settings. In contrast, the complexity measure introduced in [Damian et al., 2025] assumes a realizable, noiseless model.

Despite the above differences, when both works are restricted to a realizable setting and when parameter-recovery is possible, one can show that our Definition 1.3 and the “generative-leap exponent” of [Damian et al., 2025] are essentially equivalent. This can be shown by roughly the same analysis as presented in Appendix C.3 of our submission for the generative exponent (the single-index special case).

We thank the reviewer for their time, effort, and insightful questions. We address the reviewer's points below.

By the term “efficient learnability of MIMs”, we refer to the computational complexity of learning. Ignoring computational constraints, essentially tight bounds on the sample complexity of PAC learning follow easily from known techniques. On the other hand, prior to our work, no algorithm with runtime subexponential in the dimension $d$ was known (even for constant values of the parameters $L, K, \epsilon$.) We elaborate on these points in the following paragraphs.

Previously Known (Inefficient) PAC Learners for MIMs: Via standard uniform convergence arguments, it can be shown that for well-behaved MIMs (in fact, for any bounded‐variation $C^1$ class on $\mathbb{R}^d$) the Empirical Risk Minimizer (ERM) is an agnostic PAC learner with sample complexity linear in the dimension $d$ and polynomial in the parameters $L, K, 1/\epsilon$. Unfortunately, known implementations of the ERM require searching over an $\epsilon$–cover of the $K$-MIM Lipschitz functions, which takes time $2^{\Omega(d/\epsilon)}$. This runtime is exponential in the dimension $d$, even for constant values of the accuracy parameter. In contrast, the complexity of our algorithm is a fixed-degree polynomial in $d$ (with exponent roughly $m$, the degree of distinguishing moments in Definition 1.3).

Complexity of ERM vs. Our Algorithm: As explained above, while the sample complexity of ERM is near-optimal, its computational complexity is exponential in $d$ (even for constant $\epsilon$). Our SQ lower bound strongly suggests an information-computation gap for our learning problem: while the information-theoretically optimal sample complexity is $O(d)$ (times some function of the other parameters), to achieve runtime sub-exponential in the dimension, we need to draw more samples—namely $d^{\Omega(m)}$. Our algorithm qualitatively matches this lower bound (as a function of the dimension), by drawing $d^{O(m)}$ samples (times some function of the other parameters) and running in sample-polynomial time.

Intuition for the Moment Condition (Def 1.3): Our submission includes an intuitive explanation regarding this part of Definition 1.3: please see lines 54-56, and 165-178. As mentioned in lines 54–56, the “distinguishing low‑degree moment” condition measures how much improvement one can guarantee when the current subspace guess is off. Concretely, if the guess subspace yields large residual error, then a degree at most $m$ moment will detect that misfit and guide the next update—quantifying exactly how much progress one can make per iteration. If the reviewer has additional suggestions, we are happy to expand on this explanation in the revised version.

Dependence on Network Size vs. Lipschitz Constant: Regarding the dependence of Corollary 1.7 on the Lipschitz constant $L$, there are a few comments we would like to make. We first want to emphasize that the depth of the network and the Lipschitz constant are independent quantities. Specifically, it is possible to have a depth-one network with arbitrarily large Lipschitz constant; or a very deep network with arbitrarily small Lipschitz constant. While the dependence of our algorithm (establishing Corollary 1.7) on the parameter $L$ may not be optimal, some dependence on $L$ is information-theoretically necessary (since the target function can be supported on a set of probability mass $O(1/L)$). The main contribution of Corollary 1.7 over the prior work [CKM22] is that it completely removes the dependence on the network size (parameter $S$, see Line 97, which is bounded below by the depth and may be much larger) while having qualitatively similar dependence on the Lipschitz constant $L$.

Relative Impact of the $2^{\mathrm{poly}(1/\epsilon)}$ vs. $d^m$ Terms: The focus and main contribution of our paper is to qualitatively characterize the complexity of PAC learning MIMs as a function of the dimension $d$. Specifically, our work establishes that the $d^m$ term in the complexity of our algorithm is qualitatively optimal in the SQ model (see lines 80-81). We did not make any claims about the optimality of our methods in terms of the other parameters.

Notably, prior to our work, no algorithm with sub-exponential dependence on $d$ was known in our setting, even for constant values of the parameters $\epsilon, L, K$. As the first algorithmic result in this setting, our primary goal was to establish the correct dimension‐dependence.

As pointed out by the reviewer, for $\epsilon$ very small, the $2^{\mathrm{poly}(1/\epsilon)}$ term may dominate the $d^m$ term. (It is worth pointing out here that, as mentioned in lines 75-76, the version of our algorithm for the case of independent noise has a $\mathrm{poly}(1/\epsilon)^K$ complexity.) Developing algorithms with polynomial dependence in all parameters is left as an interesting open problem.

We thank the reviewer for their time, effort, and insightful questions. We address the points and questions by the reviewer below.

Dependence on Network Size vs. Lipschitz Constant: Regarding the dependence of Corollary 1.7 on the Lipschitz constant $L$, there are a few comments we would like to make. We first want to emphasize that the depth of the network and the Lipschitz constant are independent quantities. Specifically, it is possible to have a depth-one network with arbitrarily large Lipschitz constant; or a very deep network with arbitrarily small Lipschitz constant.

While the dependence of our algorithm (establishing Corollary 1.7) on the parameter $L$ may not be optimal, some dependence on $L$ is information-theoretically necessary (since the target function can be supported on a set of probability mass $O(1/L)$). The main contribution of Corollary 1.7 over the prior work [CKM22] is that it completely removes the dependence on the network size (parameter $S$, see Line 97, which is bounded below by the depth and may be much larger) while having qualitatively similar dependence on the Lipschitz constant $L$.

Discrete Label Case: While the main results of [DIKZ25] could be morally viewed as a special case of ours, certain non-trivial technical differences between the settings make it difficult to conclude this immediately. Specifically, our paper uses the $L_2$ loss, rather than the $L_0$ loss (misclassification error) in [DIKZ25]. Consequently, our setting allows agnostic noise that produces output values not in the given discrete set.

We thank the reviewer for their careful reading of our work and for pointing out typos. We will fix these minor issues in the revised manuscript. We address the reviewer’s points and suggestions below.

Intuition for the Moment Condition (Def 1.3): We start by pointing out that our submission includes an intuitive explanation regarding this part of Definition 1.3: please see lines 54-56, and 165-178. As mentioned in lines 54–56, the “distinguishing low‑degree moment” condition measures how much improvement one can guarantee when the current subspace guess is off. Concretely, if the guess subspace yields large residual error, then a degree at most $m$ moment will detect that misfit and guide the next update—quantifying exactly how much progress one can make per iteration. If the reviewer has additional suggestions, we are happy to expand on this explanation in the revised version.

Comparison with [DBLP24]: As mentioned in lines 245-246 of our submission and pointed out by the reviewer, our Multi‑Index Model (MIM) results can be viewed as a generalization of analogous results for the case of Single‑Index Model (SIMs) studied in [DBLP24]. However, as we explain in our technical overview, the transition to the MIM setting introduces qualitatively new challenges—both in theoretical analysis and in algorithm design—which necessitate substantially novel techniques. Moreover, as reviewer xGhv also noted, our work handles both the noiseless (realizable) and agnostic settings; whereas [DBLP24] treated only the noiseless case. Finally, we emphasize that our focus has been on the task of PAC learning, i.e., computing a hypothesis with low prediction error, as opposed to parameter recovery (i.e., identifying the hidden subspace); see lines 243-245 and 1406-1413. The prior work [DBLP24] on SIMs had focused on identifying the hidden direction (in a setting where it is identifiable).

Comparison to [Damian et al. (2025)]: We thank the reviewer for pointing us to that arxiv manuscript (arXiv:2506.05500). That paper appeared online on June 5, 2025, i.e., three weeks after the NeurIPS submission deadline. As a result, we were unable to include a comparison in our submission. We are happy to provide a comparison in the revised version of our manuscript. Please see our response to reviewer AGEu for such a comparison.

Incorporating [TDD+24]: We appreciate the pointer to [TDD+24] as the first proportional‑regime generalization of the generative exponent to multi‑index models. We note that [TDD+24] is already cited in the supplementary material of our submission. We will include a detailed explanation and comparison in the revised version.

We would like to thank the reviewer for the appreciation of our work and for providing helpful feedback.