論文の概要: Agnostic Proper Learning of Halfspaces under Gaussian Marginals

• arxiv url: http://arxiv.org/abs/2102.05629v1
• Date: Wed, 10 Feb 2021 18:40:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-11 14:38:19.676811
• Title: Agnostic Proper Learning of Halfspaces under Gaussian Marginals
• Title（参考訳）: ガウスマージナルによる半空間のアグノスティック・プロパーラーニング
• Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
• Abstract要約: ガウスの下の半空間を不可知的に学習する問題を考察する。 我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
• 参考スコア（独自算出の注目度）: 56.01192577666607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of agnostically learning halfspaces under the Gaussian distribution. Our main result is the {\em first proper} learning algorithm for this problem whose sample complexity and computational complexity qualitatively match those of the best known improper agnostic learner. Building on this result, we also obtain the first proper polynomial-time approximation scheme (PTAS) for agnostically learning homogeneous halfspaces. Our techniques naturally extend to agnostically learning linear models with respect to other non-linear activations, yielding in particular the first proper agnostic algorithm for ReLU regression.
• Abstract（参考訳）: ガウス分布の下での非定型学習半空間の問題を研究する。 私たちの主な結果は、サンプルの複雑さと計算の複雑さが最もよく知られた不適切な学習者のものと質的に一致するこの問題のための「最初の適切な」学習アルゴリズムです。 この結果に基づいて、同種半空間を不可知的に学習するための最初の固有多項式時間近似スキーム(PTAS)を得る。 私たちの技術は、他の非線形アクティベーションに関して線形モデルを無知に学習し、特にReLU回帰のための最初の適切な非検出アルゴリズムをもたらします。

関連論文リスト

• Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing [7.143879014059895]
  ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。 我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2024-03-29T21:12:25Z)
• Regularization and Optimal Multiclass Learning [10.168670899305232]
  この研究は、経験的リスク最小化が失敗する最も単純な設定における正規化の役割を特徴づけることである。 ワンインクルージョングラフ(OIG)を用いて、試行錯誤アルゴリズムの原理に相応しい最適な学習アルゴリズムを示す。
  論文  参考訳（メタデータ） (2023-09-24T16:49:55Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
  論文  参考訳（メタデータ） (2022-09-01T11:05:26Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  そこで我々は,二元性LPを用いて,多種多様な問題に対するサンプルのハードファミリーを見つける手法を開発した。 L1$-regression は本質的には最適であり、概念クラスを学習する際の計算困難さは、クラスから任意の関数を近似するのに要する次数と密接に関連していることが示される。
  論文  参考訳（メタデータ） (2021-02-08T18:06:32Z)
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
  本研究では, サンプルの一定割合が逆向きに破壊されるような外乱条件下で, ドブルシンの条件を満たすIsingモデルの学習問題について検討する。 我々の主な成果は、ほぼ最適誤差保証を伴うこの問題に対して、計算効率のよい最初の頑健な学習アルゴリズムを提供することである。
  論文  参考訳（メタデータ） (2021-02-03T18:00:57Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。