論文の概要: Robust Regression of General ReLUs with Queries
- arxiv url: http://arxiv.org/abs/2606.11130v1
- Date: Tue, 09 Jun 2026 17:24:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-10 15:40:58.63828
- Title: Robust Regression of General ReLUs with Queries
- Title（参考訳）: クエリによる一般ReLUのロバスト回帰
- Authors: Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma,
- Abstract要約: 受動的学習環境では、最近の研究は、$poly(d,1/)$ラベル付き例を使用する計算効率の良いアルゴリズムを提供した。
ここでは、学習者がラベルのないサンプルのラベルにある種のクエリアクセスを行う対話的な設定に焦点を当てる。
我々の主な成果は、$d polylog(1/)+tildeO(min1/p, 1/)$ black-box label queryを使用する最初の計算効率の高い学習者である。
- 参考スコア（独自算出の注目度）: 44.66700509667053
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses $poly(d,1/ε)$ labeled examples and outputs a hypothesis with error $O(opt)+ε$, where $opt$ is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses $d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\})$ black-box label queries, where $p$ is the bias of the target function, and achieves error $O(opt)+ε$. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires $\tildeΩ(d/ε)$ labels, unless it draws a super-polynomial number of unlabeled examples.
- Abstract（参考訳）: ガウス分布における一般(同種とは対照的に)ReLUを正方形損失に関して不可知的に学習するタスクについて検討する。
受動的学習環境では、最近の研究は、$poly(d,1/ε)$ラベル付き例を使い、エラー$O(opt)+ε$で仮説を出力する計算効率の良いアルゴリズムを与えた。
ここでは,学習者がラベルのないサンプルのラベルにある種のクエリアクセスを行う,インタラクティブな設定に焦点を当てる。
我々の主な成果は、$d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\})$ black-box label query, where $p$ is the bias of the target function, and achieves error $O(opt)+ε$。
我々は,クエリの複雑性境界が定性的にほぼ最適であることを示し,計算制約を無視したアルゴリズム結果を補完する。
最後に、受動的学習のラベル複雑さを改善するために、問合せアクセスが本質的に必要であることを示す。
具体的には、プールベースのアクティブラーニングでは、どんなアクティブラーニングでも$\tildeΩ(d/ε)$ラベルを必要とする。
関連論文リスト
- Near-Polynomially Competitive Active Logistic Regression [6.600655187282174]
能動的学習は受動的学習と比較して指数関数的に少ないラベルクエリを必要とすることはよく知られている。
入力毎に最適なアルゴリズムと競合する最初のアルゴリズムを示す。
我々のアルゴリズムは効率的なサンプリングに基づいており、より一般的な関数のクラスを学習できるように拡張することができる。
論文 参考訳（メタデータ） (2025-03-07T23:31:58Z) - Active Learning of General Halfspaces: Label Queries vs Membership Queries [35.41111301965335]
アクティブな学習者は、$tildeOmega(d/(log(m)epsilon)$というラベルの複雑さを必要とする。
クエリ複雑性が$tildeO(min1/p, 1/epsilon + dcdot polylog (1/epsilon))$$O(opt)+epsilon$のエラー保証を実現する。
論文 参考訳（メタデータ） (2024-12-31T15:40:48Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。