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

Ilias Diakonikolas; Daniel M. Kane; Mingchen Ma

cs.LGOct 30, 2026

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

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

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

Abstract

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.

Figures & tables

Result	Function Class	Distribution	Time Complexity	Error	Notes
Theorem 7.9	$L_{1}$ -sandwiching $K$ -MIMs	Logconcave	$d^{O(\ell(c))}2^{\mathrm{polylog}_{K,c}(1/\epsilon)}$	$(1+c)\mathrm{opt}+\epsilon$	Partial, Testable
[ KKMS08 ]	$L_{1}$ -Approximable Classes	General	$d^{O(\ell(\epsilon))}$	$\mathrm{opt}+\epsilon$
Theorem 7.12	Functions of $K$ Halfspaces	Logconcave	$\mathrm{poly}_{K,c}(d)2^{\mathrm{polylog}_{K,c}(1/\epsilon)}$	$(1+c)\mathrm{opt}+\epsilon$	Partial, Testable
[ KKM13 ]	Functions of $K$ Halfspaces	Logconcave	$d^{2^{\mathrm{poly}(K/\epsilon)}}$	$\mathrm{opt}+\epsilon$
[ Vem10b ]	Intersections of $K$ Centered Halfspaces	Isotropic Logconcave	$O(dK/\epsilon)^{K}$	$\epsilon$	Realizable
[ DKS18 ]	Intersections of $K$ General Halfspaces	Gaussian	$\mathrm{poly}(dK/\epsilon)+(K/\epsilon)^{O(K^{2})}$	$\tilde{O}(K^{4/11}\mathrm{opt}^{1/11})+\epsilon$

Table 1: Summary and comparison of some of our results on agnostic learning under logconcave distributions. All our theorems listed in the table have sample complexity polynomial in

d/\epsilon

with degree depending on

K,c,

\ell(c)

Panel of Figure 1 — Figure 1: Overview of the proof structure and dependencies. Directed edges indicate logical dependencies: an arrow $A\to B$ means that the result at $B$ relies on or invokes the result at $A$ .

Figure 3: Generic Geometric Concept Class

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 604 papers

Gaussian Partitioning for Reliable Learning of Multi-Index Models
Nov 3, 2026Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1Agnostic Learning Multi-Index Models
University of Wisconsin-Madison · University of California, San Diego
Efficient Robust Learning at the Information-Theoretic Limit
Sep 15, 2026Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1Boolean Function Learning Learning with Noisy Labels
UT Austin · Institute for Advanced Study · Aarhus University
Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals
Nov 3, 2026Zhijie ZhengHalfspace Learning Statistical Learning Theory
Peking University

Nov 3, 2026J/K move · Enter open · S save

Gaussian Partitioning for Reliable Learning of Multi-Index Models

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

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

Agnostic Learning Multi-Index Models Halfspace Learning

Open paper AskPDF arXiv

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.

Abstract

Statistical Learning Theory

Explore similar work

Gaussian Partitioning for Reliable Learning of Multi-Index Models

Efficient Robust Learning at the Information-Theoretic Limit

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals