Metraipolis › archive › dc_802c65b5a5aa

Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners — arXiv:2610.41961

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41961
License (as archived)
CC0-1.0
Archived
2026-11-02T04:52:30.034Z
SHA-256 of the archived text
aa28687899b68585d8fa861717024bd61040bb2582cad179facbce19bf0c670b
Stable URL of this page
https://metraipolis.com/documento/dc_802c65b5a5aa

How to cite

Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners — arXiv:2610.41961 — arXiv (en), https://arxiv.org/abs/2610.41961 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_802c65b5a5aa (Metraipolis archive dc_802c65b5a5aa, sha256 aa28687899b68585d8fa861717024bd61040bb2582cad179facbce19bf0c670b)
BibTeX
@misc{dc802c65b5a5aa,
  title = {Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners — arXiv:2610.41961},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41961},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_802c65b5a5aa; sha256 aa28687899b68585d8fa861717024bd61040bb2582cad179facbce19bf0c670b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41961. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.41961 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:45:12.916Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).