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

Nov 3, 2026

Gaussian Partitioning for Reliable Learning of Multi-Index Models

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.

Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1

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

Agnostic Learning Multi-Index Models Halfspace Learning

Ask PDF

Sep 15, 2026

Efficient Robust Learning at the Information-Theoretic Limit

In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of

η+ \varepsilon

where

η

is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than

2η+ \varepsilon.

Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error

η+ \varepsilon

for any constant

\varepsilon

Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1

UT Austin · Institute for Advanced Study · Aarhus University

Boolean Function Learning Learning with Noisy Labels Halfspace Learning Robust Classification

Ask PDF

Nov 3, 2026

Proper Agnostic Learning of Affine Halfspaces under Log-Concave Marginals

We give a proper constant-factor agnostic learner for affine halfspaces under full-dimensional log-concave marginals. For arbitrary binary labels, the algorithm uses independent labeled samples and returns a single affine halfspace with error at most

C\mathrm{OPT}+\varepsilon

. Its sample and real-arithmetic complexity are polynomial in dimension, inverse accuracy, and the logarithm of the reciprocal failure probability. The mean and covariance of the marginal need not be known, and the sample complexity can be made linear in this logarithmic confidence factor. The main geometric result compares global disagreement with disagreement on a balanced restriction: for a minority halfspace of mass

p

, global disagreement is within universal constant factors of

p

times conditional disagreement, provided the latter is sufficiently small. To construct the restriction from noisy labels, we estimate the minority cap's mean and covariance robustly, approximately minimize the classical zonoid-depth dual objective, and expand a superlevel set to a marginal quantile. The disagreement comparison cancels the noise amplification caused by conditioning and allows the learned halfspace to be used on the entire space. The analysis combines degree-four sum-of-squares moment bounds for log-concave laws with a translation-based reduction from balanced affine learning to homogeneous halfspace learning.

Zhijie Zheng

Peking University

Halfspace Learning Statistical Learning Theory

Ask PDF

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