論文の概要: Efficient Robust Learning at the Information-Theoretic Limit
- arxiv url: http://arxiv.org/abs/2609.17655v1
- Date: Tue, 15 Sep 2026 17:56:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:53.481659
- Title: Efficient Robust Learning at the Information-Theoretic Limit
- Title（参考訳）: 情報理論におけるロバスト学習の効率化
- Abstract要約: 任意の定数$varepsilon$に対して、限界誤差$+varepsilon$に対してハーフスペースを頑健に学習するアルゴリズムを与える。
意外なことに、我々の技術は様々な種類のノンレグレット学習者を利用しています。
- 参考スコア（独自算出の注目度）: 21.44837239448483
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifier achieving the optimal error of $η+ \varepsilon$ where $η$ is the noise rate. In contrast, it is well known that deterministic hypotheses cannot achieve error less than $2η+ \varepsilon.$ Blanc's algorithm is computationally inefficient, and the main problem left open in his work is to find a polynomial-time algorithm given access to an oracle for empirical risk minimization (ERM). In this paper, we resolve this problem and give such an algorithm. Perhaps surprisingly, our techniques make crucial use of various types of no-regret learners. Additionally, we give an efficient algorithm (no ERM oracle required) for robustly learning any function class that admits sandwiching polynomials with respect to hypercontractive distributions. As one consequence, we give the first polynomial-time algorithm for robustly learning a halfspace with respect to Gaussian marginals that achieves error $η+ \varepsilon$ for any constant $\varepsilon$.
- Abstract（参考訳）: 最近の重要な研究において、Branc (2026) は、(ランダム化された)分類器を出力し、$η+ \varepsilon$ の最適誤差を達成し、$η$ がノイズレートであるような、ブールの概念クラスを頑健に学習するアルゴリズムを与えた。
対照的に、決定論的仮説が2η+ \varepsilon未満の誤差を達成できないことはよく知られている。
ブランのアルゴリズムは計算的に非効率であり、彼の研究で残された主な問題は、経験的リスク最小化(ERM)のためのオラクルへのアクセスを与えられた多項式時間アルゴリズムを見つけることである。
本稿では,この問題を解き,そのようなアルゴリズムを提案する。
意外なことに、我々の技術は様々な種類のノンレグレット学習者を利用しています。
さらに、超収縮分布に対してサンドイッチ多項式を許容する任意の関数クラスを頑健に学習する効率的なアルゴリズム(ERMオラクルを必要としない)を与える。
結果として、任意の定数 $\varepsilon$ に対して誤差 $η+ \varepsilon$ を達成するガウス極限に対するハーフスペースを頑健に学習する最初の多項式時間アルゴリズムを与える。
関連論文リスト
- Learning to Play Against Unknown Opponents [9.346742321348366]
本研究では,学習エージェントが非学習に制約されない場合に,最適な学習アルゴリズムを効率的に構築する方法を示す。
これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
論文 参考訳（メタデータ） (2024-12-24T09:05:06Z) - 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) - Agnostic proper learning of monotone functions: beyond the black-box
correction barrier [6.47243430672461]
2tildeO(sqrtn/varepsilon)$ 未知関数 $f:pm 1n rightarrow pm 1$ の一様ランダムな例を与えられたとき、我々のアルゴリズムは仮説 $g:pm 1n rightarrow pm 1$ を出力する。
また,2tildeO(sqrt)の実行時間を用いて,未知関数$f$からモノトンへの距離を加算誤差$varepsilon$まで推定するアルゴリズムも提供する。
論文 参考訳（メタデータ） (2023-04-05T18:52:10Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。