Gaussian Partitioning for Reliable Learning of Multi-Index Models

Ilias Diakonikolas; Giannis Iakovidis; Daniel M. Kane; Mingchen Ma

cs.DSNov 3, 2026

Gaussian Partitioning for Reliable Learning of Multi-Index Models

Authors: Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane, Mingchen Ma

Organizations: University of Wisconsin-Madison · University of California, San Diego

Abstract

We introduce Gaussian partitioning, an algorithmic primitive for distributions smooth with respect to a Gaussian. It partitions space into polyhedral regions so that almost all mass lies in thin strips restricting a few orthogonal directions. Within each strip, the conditional distribution approximately matches low-degree Gaussian moments in the unrestricted directions. Our construction builds on logconcave partitioning of Diakonikolas, Kane, and Ma (FOCS 2026). Under input marginals smooth with respect to the standard Gaussian, we obtain agnostic learners with error $(1+c)\mathrm{opt}+ε$ for broad classes of Boolean multi-index models, including functions of halfspaces, low-dimensional convex concepts, and low-dimensional polynomial threshold functions. For functions of $k$ halfspaces, both agnostic and testable agnostic learners achieve this error with dimension dependence $d^{\mathrm{poly}(k/c)}$ , improving the previous exponential dependence on $k/c$ in the agnostic exponent. For learning from positive examples with imperfect unlabeled data (PUI), we give algorithms and Statistical Query (SQ) lower bounds that qualitatively characterize complexity through Gaussian moment matching. For fixed smoothness and positive-mass parameters, we learn intersections of $k$ halfspaces with dimension dependence $d^{O(\log(k/ε))}$ and matching SQ lower bounds, improving the previous $d^{\mathrm{poly}(1/ε)}$ upper bound even for one halfspace. A general reduction from agnostic reliable learning to PUI yields negative reliable learners for these intersections with the same dimension dependence, for fixed smoothness. Finally, for PQ learning and testable learning with distribution shift, we prove qualitatively optimal SQ lower bounds of $d^{Ω(1/ε^2)}$ , even for intersections of two halfspaces with Gaussian training data and arbitrary test distributions.

Figures & tables

Concept class	Dimension dependence
Intersections of $k$ halfspaces	$d^{\widetilde{O}(k^{3}/c^{4})}$
Arbitrary Boolean functions of $k$ halfspaces	$d^{\widetilde{O}(k^{5}/c^{4})}$
Convex concepts of intrinsic dimension at most $K$	$d^{\widetilde{O}(K^{5}/c^{4})}$
Degree-at-most- $r$ PTFs of intrinsic dimension at most $K$	$d^{\widetilde{O}(r^{6}K^{5}/c^{4})}$

Table 1: Dimension dependence for

(1+c)

-approximate agnostic learning under marginals that are

(q,\sigma)

-smooth with respect to the standard Gaussian. For fixed class parameters,

q

, and

c

, the remaining factor is quasipolynomial in

1/(\sigma\epsilon)

Concept class	Dimension dependence
Intersections of $k$ halfspaces	$d^{O(\log(2k)+q\log(2q/(\sigma\epsilon p_{+})))}$
Convex concepts of intrinsic dimension $K$	$d^{O(K+q\log(2q/(\sigma\epsilon p_{+})))}$

Table 2: Dimension dependence of our PUI learners with a standard Gaussian reference. For each row, the sample complexity is

n=d^{m}\exp(m^{O(m)})

, with

m

a sufficiently large constant multiple of the quantity inside

O(\cdot)

in the displayed exponent. The running time is

\mathrm{poly}(n)

{(\ell_{*},\widehat{\mathbf{w}})\in\argmax_{\ell\in[k],\,\mathbf{w}\in\mathcal{C}}\left|\frac{1}{n}\sum_{s=1}^{n}(\mathbf{w}\cdot\mathbf{x}^{(s)})^{\ell}-\E_{Z\sim\mathcal{N}(0,1)}[Z^{\ell}]\right|.}

Algorithm 2 GaussianDiscrepancyFinder

Concept class	Complexity
$(\ell,K)$ -well-behaved MIMs	$d^{O(\ell(c^{\prime}c))}$
Intersections or unions of $k$ halfspaces	$d^{\widetilde{O}(k^{3}/c^{4})}$
Arbitrary Boolean functions of $k$ halfspaces	$d^{\widetilde{O}(k^{5}/c^{4})}$
Convex concepts of intrinsic dimension $K$	$d^{\widetilde{O}(K^{5}/c^{4})}$
Degree- $r$ PTFs of intrinsic dimension $K$	$d^{\widetilde{O}(r^{6}K^{5}/c^{4})}$

Table 3: Agnostic learning results. All results hold for marginal distributions that are

(q,\sigma)

-smooth with respect to the standard Gaussian. The displayed complexities have an additional factor quasi-polynomial in

1/(\sigma\epsilon)

for fixed class parameters,

q

, and

c

h(\mathbf{x})=\begin{cases}1,&\mathbf{x}\in\displaystyle\bigcup_{R\in\mathcal{G}}R,\\ -1,&\text{otherwise}.\end{cases}

Algorithm 4 GaussianPUILearner

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Concept class	Dimension dependence
$(\ell,K,A,\Lambda)$ -testable well-behaved MIMs	$d^{O(\ell_{c})}$
Intersections of $k$ halfspaces	$d^{\widetilde{O}(k^{3}/c^{4})}$
Boolean functions of $k$ halfspaces	$d^{\widetilde{O}(k^{5}/c^{4})}$

Appendix

Table 4: Testable learning under

\mathcal{D}_{q,\sigma}

to error

(1+c)\mathrm{opt}_{D}(\mathcal{F})+\epsilon

with confidence

99\%

. The table displays the dependence on

d

in the sample complexity and running time; the remaining factors are given in Theorem F.2 . Here

\ell_{c}=\ell(c/C)

, and the general class is assumed to be testable well-behaved.

Agnostic Learning

See all 18 papers

May 26, 2026

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over

\mathbb{R}^d \times \{\pm 1\}

whose marginal on

\mathbb{R}^d

is Gaussian, the goal is to output a hypothesis from a target class

\mathcal{F}

whose 0-1 loss is within

ε

of that of the best classifier in

\mathcal{F}

. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of

K

halfspaces under Gaussian marginals. Our algorithm runs in time

d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}

. Prior to our work, the only known algorithm for

K \geq 2

was brute-force search, with run-time exponential in

d

. Moreover, the dependence of our run-time on the dimension

d

matches that of the best known improper learning algorithm, namely

d^{\widetilde{O}(K^2/ε^2)}

. For the special case of a single halfspace (

K=1

), the best previous run-time was

d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}

. Our algorithm improves this to

d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}

. Once again, the dependence on

d

matches that of the best known improper algorithm, namely

d^{O(1/ε^2)}

. Furthermore, the dependence of our run-time on the dimension

d

is essentially optimal in the statistical query model.

Sergei Tikhonov, Arsen Vasilyan

UT Austin

Agnostic Learning Boolean Function Learning Statistical Learning Theory Halfspace Learning

Ask PDF

Feb 24, 2026

Statistical Query Lower Bounds for Smoothed Agnostic Learning

We study the complexity of smoothed agnostic learning, recently introduced by~\cite{CKKMS24}, in which the learner competes with the best classifier in a target class under slight Gaussian perturbations of the inputs. Specifically, we focus on the prototypical task of agnostically learning halfspaces under subgaussian distributions in the smoothed model. The best known upper bound for this problem relies on

L_1

-polynomial regression and has complexity

d^{\tilde{O}(1/σ^2) \log(1/ε)}

, where

σ

is the smoothing parameter and

ε

is the excess error. Our main result is a Statistical Query (SQ) lower bound providing formal evidence that this upper bound is close to best possible. In more detail, we show that (even for Gaussian marginals) any SQ algorithm for smoothed agnostic learning of halfspaces requires complexity

d^{Ω(1/σ^{2}+\log(1/ε))}

. This is the first non-trivial lower bound on the complexity of this task and nearly matches the known upper bound. Roughly speaking, we show that applying

L_1

-polynomial regression to a smoothed version of the function is essentially best possible. Our techniques involve finding a moment-matching hard distribution by way of linear programming duality. This dual program corresponds exactly to finding a low-degree approximating polynomial to the smoothed version of the target function (which turns out to be the same condition required for the

L_1

-polynomial regression to work). Our explicit SQ lower bound then comes from proving lower bounds on this approximation degree for the class of halfspaces.

Ilias Diakonikolas, Daniel M. Kane

University of Wisconsin-Madison · University of California, San Diego

Halfspace Learning Statistical Learning Theory

Ask PDF

Oct 30, 2026

Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners

We develop a new algorithmic framework for learning Boolean concept classes under logconcave distributions. Our framework applies to broad families of multi-index models and yields significantly faster robust learners than were previously known in these settings. It extends to partial classification and testable learning. Consequently, we obtain improved learners for several fundamental concept classes, including functions of halfspaces and multiclass linear classifiers, under logconcave marginals. Our starting point is a new boosting framework based on weak partial learners. Classical boosting approaches require often-intractable distribution-free weak learners or yield weak approximation guarantees. We show instead that weak learners for partial classification, where labels may be undefined on part of the domain, suffice for strong agnostic learning. The key challenge is that boosting requires a weak learner that succeeds under conditioned distributions that are not guaranteed to be logconcave. To address this, we develop a recursive moment-based partitioning procedure: given a logconcave distribution

X

and a conditional version

X'

, we partition the space into polynomially many convex regions so that, on most regions, the low-degree moments of

X

and

X'

approximately agree. On each good region, a well-behaved multi-index model correlates with a low-degree polynomial, giving a weak hypothesis. Combining these hypotheses yields the required weak learner. A key ingredient of our approach is an efficient method for detecting moment discrepancy. Specifically, we show how to find a low-dimensional subspace that captures any non-trivial discrepancy between

X

and

X'

, if one exists. Our approach combines spectral analysis of moment tensors with recent progress on isoperimetry for logconcave measures. This discrepancy-finding procedure may be of independent interest.

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma

University of Wisconsin-Madison · University of California, San Diego

Statistical Learning Theory Classification Robust Classification Agnostic Learning Multi-Index Models Ensemble Learning

Ask PDF

Abstract

Agnostic Learning

Explore similar work

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

Statistical Query Lower Bounds for Smoothed Agnostic Learning

Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners