EUVIMEDEUVIMED entdecken
Crossref

Agnostically Learning Multi-Index Models with Queries

Ilias Diakonikolas, Daniel Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-435-FOCS24-486

DOI: 10.1137/24m1718135 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 13.07.2026. Verfasst von Ilias Diakonikolas und 4 weiteren Autor:innen. Die Arbeit nennt 93 Literaturangaben. Gefördert von: Defense Advanced Research Projects Agency, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the power of query access for the fundamental task of agnostic learning under the Gaussian distribution. In the agnostic model, no assumptions are made on the labels of the examples, and the goal is to compute a hypothesis that is competitive with the best-fit function in a known class; i.e., it achieves error [Formula: see text], where [Formula: see text] is the error of the best function in the class. We focus on a general family of multi-Index models (MIMs), which are [Formula: see text]-variate functions that depend only on a few relevant directions, i.e., have the form [Formula: see text] for an unknown link function [Formula: see text] and a [Formula: see text] matrix [Formula: see text]. MIMs cover a wide range of commonly studied function classes, including real-valued function classes, such as constant-depth neural networks with ReLU activations, and Boolean concept classes, such as intersections of halfspaces. Our main result shows that query access gives significant runtime improvements over random examples for agnostically learning both real-valued and Boolean-valued MIMs. Under standard regularity assumptions for the link function (namely, bounded variation or surface area), we give an agnostic query learner for MIMs with running time [Formula: see text]. In contrast, algorithms that rely only on random labeled examples inherently require [Formula: see text] samples and runtime, even for the basic problem of agnostically learning a single ReLU or a halfspace. As special cases of our general approach, we obtain the following results: [Formula: see text] For the class of depth-[Formula: see text], width-[Formula: see text] ReLU networks on [Formula: see text], our agnostic query learner runs in time [Formula: see text]. This bound qualitatively matches the runtime of an algorithm by Chen, Klivans, and Meka [ Learning deep ReLU networks is fixed-parameter tractable, 2022] for the realizable PAC setting with random examples. [Formula: see text] For the class of arbitrary intersections of [Formula: see text] halfspaces on [Formula: see text], our agnostic query learner runs in time [Formula: see text]. Prior to our work, no improvement over the agnostic PAC model complexity (without queries) was known, even for the case of a single halfspace. In both these settings, we provide evidence that the [Formula: see text] runtime dependence is required for proper query learners, even for agnostically learning a single ReLU or halfspace. Our algorithmic result establishes a strong computational separation between the agnostic PAC and the agnostic PAC + Query models under the Gaussian distribution for a range of natural function classes. Prior to our work, no such separation was known for any natural concept class, even for the case of a single halfspace, for which it was an open problem posed by Feldman [ On the power of membership queries in agnostic learning, 2008]. Our results are enabled by a general dimension-reduction technique that leverages query access to estimate gradients of (a smoothed version of) the underlying label function.

Förderung

  • Defense Advanced Research Projects Agency
  • National Science Foundation

Zitieren

APA

Diakonikolas, I., Kane, D., Kontonis, V., Tzamos, C., & Zarifis, N. (2026). Agnostically Learning Multi-Index Models with Queries. SIAM Journal on Computing, 55(5), FOCS24-435-FOCS24-486. https://doi.org/10.1137/24m1718135

Vancouver

Diakonikolas I, Kane D, Kontonis V, Tzamos C, Zarifis N. Agnostically Learning Multi-Index Models with Queries. SIAM Journal on Computing. 2026;55(5):FOCS24-435-FOCS24-486. doi:10.1137/24m1718135

BibTeX
@article{Diakonikolas2026,
  author = {Diakonikolas, Ilias and Kane, Daniel and Kontonis, Vasilis and Tzamos, Christos and Zarifis, Nikos},
  title = {Agnostically Learning Multi-Index Models with Queries},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--435--FOCS24--486},
  doi = {10.1137/24m1718135}
}
Kostenlos starten →