Robust learning of multi-index models under logconcave distributions

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

Machine Learning

Summary

Learning complex decision functions from data efficiently is a challenge, especially when the data follows specific mathematical shapes called logconcave distributions. The authors present a new way to combine simple, partial learners that only predict some of the data well, to build stronger, more reliable learners for these settings. Their method breaks the problem into parts where certain mathematical properties hold, making it possible to detect patterns and improve predictions faster than before. This approach enhances the understanding and efficiency of learning broad classes of models, including common types like linear classifiers.

What this means in practice

  • For machine learning engineers: Build faster and more robust classifiers for high-dimensional data with logconcave features using partial weak learners combined via boosting.
  • For data scientists in finance: Improve classification models on financial datasets that often follow logconcave distributions, enabling quicker identification of relevant patterns or risks.

Authors

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma

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.