Robust Learning of Multi-index Models via Iterative Subspace Approximation

We study the task of learning Multi-Index Models (MIMs) in the presence of label noise under the Gaussian distribution. A K-MIM on R d is any function f that only depends on a K-dimensional subspace, i.e., f (x) = g(Wx) for a link function g on R K and a K × d matrix W. We consider a class of well-behaved MIMs with finite ranges that satisfy certain regularity properties. Our main contribution is a general noise-tolerant learning algorithm for this class whose complexity is qualitatively optimal in the Statistical Query (SQ) model. At a high-level, our algorithm attempts to iteratively construct better approximations to the defining subspace by computing low-degree moments of our function conditional on its projection to the subspace computed thus far, and adding directions with relatively large empirical moments. For wellbehaved MIMs, we show that this procedure efficiently finds a subspace V so that f (x) is close to a function of the projection of x onto V , which can then be found by brute-force. Conversely, for functions for which these conditional moments do not necessarily help in finding better subspaces, we prove an SQ lower bound providing evidence that no efficient algorithm exists.

As concrete applications of our general algorithm, we provide significantly faster noise-tolerant learners for two well-studied concept classes: • Multiclass Linear Classifiers A multiclass linear classifier is any function f : R d → [K] of the form f (x) = argmax i∈[K] (w (i) • x + t i ) , where w (i) ∈ R d and t i ∈ R. We give a constantfactor approximate agnostic learner for this class, i.e., an algorithm that achieves 0-1 error O(OPT) + ϵ. Our algorithm has sample complexity N = O(d) 2 poly(K/ϵ) and computational complexity poly(N ). This is the first constant-factor agnostic learner for this class whose complexity is a fixed-degree polynomial in d. In the agnostic model, it was previously known that achieving error OPT + ϵ requires time d poly(1/ϵ) , even for K = 2. Perhaps surprisingly, we prove an SQ lower bound showing that achieving error OPT + ϵ, for ϵ = 1/poly(K), incurs complexity d Ω(K) even for the simpler case of Random Classification Noise.

• Intersections of Halfspaces An intersection of K halfspaces is any function f : R d → ±1

such that there exist K halfspaces h i (x) with f (x) = 1 if and only if h i (x) = 1 for all i ∈ [K].

We give an approximate agnostic learner for this class achieving 0-1 error K Õ(OPT) + ϵ.

Our algorithm has sample complexity N = O(d 2 ) 2 poly(K/ϵ) and computational complexity poly(N ). This is the first agnostic learner for this class with near-optimal dependence on OPT in its error, whose complexity is a fixed-degree polynomial in d. Previous algorithms either achieved significantly worse error guarantees, or incurred d poly(1/ϵ) time (even for K = 2). Furthermore, we show that in the presence of random classification noise, the complexity of our algorithm is significantly better, scaling polynomially with 1/ϵ.