論文の概要: Threshold Phenomena in Learning Halfspaces with Massart Noise

• arxiv url: http://arxiv.org/abs/2108.08767v1
• Date: Thu, 19 Aug 2021 16:16:48 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-20 14:36:33.545749
• Title: Threshold Phenomena in Learning Halfspaces with Massart Noise
• Title（参考訳）: マスアートノイズを伴うハーフスペース学習における閾値現象
• Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
• Abstract要約: ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
• 参考スコア（独自算出の注目度）: 56.01192577666607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of PAC learning halfspaces on $\mathbb{R}^d$ with Massart noise under Gaussian marginals. In the Massart noise model, an adversary is allowed to flip the label of each point $\mathbf{x}$ with probability $\eta(\mathbf{x}) \leq \eta$, for some parameter $\eta \in [0,1/2]$. The goal of the learner is to output a hypothesis with missclassification error $\mathrm{opt} + \epsilon$, where $\mathrm{opt}$ is the error of the target halfspace. Prior work studied this problem assuming that the target halfspace is homogeneous and that the parameter $\eta$ is strictly smaller than $1/2$. We explore how the complexity of the problem changes when either of these assumptions is removed, establishing the following threshold phenomena: For $\eta = 1/2$, we prove a lower bound of $d^{\Omega (\log(1/\epsilon))}$ on the complexity of any Statistical Query (SQ) algorithm for the problem, which holds even for homogeneous halfspaces. On the positive side, we give a new learning algorithm for arbitrary halfspaces in this regime with sample complexity and running time $O_\epsilon(1) \, d^{O(\log(1/\epsilon))}$. For $\eta <1/2$, we establish a lower bound of $d^{\Omega(\log(1/\gamma))}$ on the SQ complexity of the problem, where $\gamma = \max\{\epsilon, \min\{\mathbf{Pr}[f(\mathbf{x}) = 1], \mathbf{Pr}[f(\mathbf{x}) = -1]\} \}$ and $f$ is the target halfspace. In particular, this implies an SQ lower bound of $d^{\Omega (\log(1/\epsilon) )}$ for learning arbitrary Massart halfspaces (even for small constant $\eta$). We complement this lower bound with a new learning algorithm for this regime with sample complexity and runtime $d^{O_{\eta}(\log(1/\gamma))} \mathrm{poly}(1/\epsilon)$. Taken together, our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
• Abstract（参考訳）: 我々は,gaussian marginals 下でマスアートノイズを伴う$\mathbb{r}^d$ 上のpac学習ハーフスペースの問題について検討する。 massartノイズモデルでは、あるパラメータ$\eta \in [0,1/2]$ に対して、逆者は確率$\eta(\mathbf{x}) \leq \eta$ で各点$\mathbf{x}$ のラベルをひっくり返すことができる。 学習者の目標は、ミス分類エラー$\mathrm{opt} + \epsilon$, ここで、$\mathrm{opt}$はターゲットハーフスペースのエラーである。 以前の研究では、対象の半空間が均質であり、パラメータ$\eta$が厳密に1/2$より小さいと仮定してこの問題を研究した。 これらの仮定のどちらかが取り除かれたとき、問題の複雑さがどのように変化するのかを考察し、以下のしきい値の現象を確立する: $\eta = 1/2$ に対して、同次半空間に対しても成り立つ問題に対する統計的クエリ (SQ) アルゴリズムの複雑さについて$d^{\Omega (\log(1/\epsilon))} の下界を証明する。 正の面では、サンプル複雑性と実行時間 $o_\epsilon(1) \, d^{o(\log(1/\epsilon))} を持つこの方法で、任意の半空間に対する新しい学習アルゴリズムを与える。 d^{\Omega(\log(1/\gamma))}$の低い境界は、問題のSQ複雑性に基づいて成立し、$\gamma = \max\{\epsilon, \min\{\mathbf{Pr}[f(\mathbf{x}) = 1], \mathbf{Pr}[f(\mathbf{x}) = -1]\} \}$と$f$は対象ハーフ空間である。 特にこれは、任意のMassart半空間を学ぶための$d^{\Omega (\log(1/\epsilon) )}$のSQ下界を意味する(小さな定数$\eta$に対しても)。 この下界は、サンプルの複雑さと実行時の$d^{O_{\eta}(\log(1/\gamma))} \mathrm{poly}(1/\epsilon)$で新しい学習アルゴリズムで補う。 その結果,Massartモデルにおける学習ハーフスペースの複雑さを質的に特徴づけた。

関連論文リスト

• SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
  この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。 重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
  論文  参考訳（メタデータ） (2023-10-18T10:56:57Z)
• 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)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。 我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
  論文  参考訳（メタデータ） (2022-07-28T17:50:53Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• 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)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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