Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper develops a new algorithmic framework for robust learning of multi-index models under logconcave distributions using weak partial learners, yielding significantly faster robust learners for fundamental concept classes like halfspaces and multiclass linear classifiers. It introduces a novel boosting approach that overcomes the challenge of non-logconcave conditioned distributions via a recursive moment-based partitioning procedure and an efficient discrepancy finder, providing substantial theoretical improvements over prior state-of-the-art methods.
Methodology
The paper introduces a novel algorithmic framework for robust learning of multi-index models (MIMs) under logconcave distributions. The core innovation is a boosting framework based on "weak partial learners," which allows for strong agnostic learning guarantees without requiring intractable distribution-free weak learners. A key technical contribution is a recursive moment-based partitioning procedure that handles the challenge of boosting under conditioned distributions that are not logconcave. The authors develop an efficient discrepancy finder using spectral analysis of moment tensors and isoperimetry for logconcave measures to identify low-dimensional subspaces capturing moment discrepancies. This enables the construction of weak hypotheses on convex regions where moments approximately match, which are then combined via boosting. The approach is theoretically rigorous, providing sample and computational complexity bounds that significantly improve upon prior state-of-the-art for learning halfspaces, functions of halfspaces, and multiclass linear classifiers under logconcave marginals.
Results & evaluation
As a theoretical computer science paper, it does not contain empirical experiments on real-world datasets. The "evaluation" consists of rigorous mathematical proofs establishing the correctness and complexity bounds of the proposed algorithms. The results are validated by comparing the derived bounds against known lower bounds and previous upper bounds in the literature, demonstrating significant improvements in efficiency and robustness.
Reproducibility
The paper provides detailed algorithmic descriptions and theoretical proofs. While no code is provided, the algorithms are described in sufficient detail for theoretical replication. The reliance on standard statistical query models and polynomial regression techniques makes the theoretical framework reproducible in a mathematical sense.
Limitations
The primary limitation is the theoretical nature of the work; there is no empirical validation on real-world data to confirm that the theoretical gains translate to practical performance improvements. The algorithms may have high constant factors or practical overheads not captured by the asymptotic analysis. The focus on logconcave distributions, while broad, excludes other common distributional assumptions.
Broader impact
This work contributes to the foundational understanding of efficient learning under distributional assumptions. It provides new tools (weak partial learners, moment discrepancy finders) that could be applicable to other learning problems beyond MIMs. The results advance the state of the art in robust learning, which is crucial for real-world applications where data is often noisy and distributional assumptions are only approximately true. The paper develops a new algorithmic framework for robust learning of multi-index models under logconcave distributions using weak partial learners, yielding significantly faster robust learners for fundamental concept classes like halfspaces and multiclass linear classifiers. It introduces a novel boosting approach that overcomes the challenge of non-logconcave conditioned distributions via a recursive moment-based partitioning procedure and an efficient discrepancy finder, providing substantial theoretical improvements over prior state-of-the-art methods.
Author of this paper? Send a correction.