論文の概要: A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise

• arxiv url: http://arxiv.org/abs/2501.09691v1
• Date: Thu, 16 Jan 2025 17:44:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-17 15:11:03.962034
• Title: A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
• Title（参考訳）: マスアート雑音を伴う有理半空間学習のための準最適アルゴリズム
• Authors: Ilias Diakonikolas, Nikos Zarifis,
• Abstract要約: 我々は、マスアートノイズの存在下で、PACが$gamma$-marginハーフスペースを学習する際の問題について検討する。 我々のアルゴリズムは単純で実用的であり、慎重に選択された凸損失の列にオンラインSGDを頼っている。
• 参考スコア（独自算出の注目度）: 36.29182619215646
• License:
• Abstract: We study the problem of PAC learning $\gamma$-margin halfspaces in the presence of Massart noise. Without computational considerations, the sample complexity of this learning problem is known to be $\widetilde{\Theta}(1/(\gamma^2 \epsilon))$. Prior computationally efficient algorithms for the problem incur sample complexity $\tilde{O}(1/(\gamma^4 \epsilon^3))$ and achieve 0-1 error of $\eta+\epsilon$, where $\eta<1/2$ is the upper bound on the noise rate. Recent work gave evidence of an information-computation tradeoff, suggesting that a quadratic dependence on $1/\epsilon$ is required for computationally efficient algorithms. Our main result is a computationally efficient learner with sample complexity $\widetilde{\Theta}(1/(\gamma^2 \epsilon^2))$, nearly matching this lower bound. In addition, our algorithm is simple and practical, relying on online SGD on a carefully selected sequence of convex losses.
• Abstract（参考訳）: 我々は,Massartノイズの存在下でのPAC学習の課題について検討する。 計算的な考慮がなければ、この学習問題のサンプル複雑性は$\widetilde{\Theta}(1/(\gamma^2 \epsilon))$であることが知られている。 従来の計算効率のよい計算アルゴリズムでは、入出力サンプルの複雑さを$\tilde{O}(1/(\gamma^4 \epsilon^3)$とし、0-1の誤差を$\eta+\epsilon$とする。 最近の研究は情報計算のトレードオフの証拠を与え、計算効率の良いアルゴリズムには1/\epsilon$に対する二次的依存が必要であることを示唆している。 我々の主な成果は、サンプル複雑性を持つ計算効率の良い学習者 $\widetilde{\Theta}(1/(\gamma^2 \epsilon^2)$ であり、この下界にほぼ一致する。 さらに,本アルゴリズムは単純かつ実用的であり,厳選された凸損失の列にオンラインSGDを頼っている。

関連論文リスト

• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Efficient active learning of sparse halfspaces with arbitrary bounded noise [34.406103025985445]
  我々は,同種$s$スパース半空間の非ラベルデータ分布が等方性対数凹であるような条件下で,$mathbbRd$におけるアクティブラーニングを研究する。 高レベルのラベルノイズの下では、計算効率のよいアルゴリズムによって達成されるラベルの複雑さ境界ははるかに悪化する。 これは、この設定で$frac11-2eta$にラベル複雑性を持つ最初の効率的なアルゴリズムである。
  論文  参考訳（メタデータ） (2020-02-12T08:28:24Z)

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

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