論文の概要: Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise

• arxiv url: http://arxiv.org/abs/2201.09818v1
• Date: Mon, 24 Jan 2022 17:33:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-25 15:24:15.201859
• Title: Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise
• Title（参考訳）: マッサート雑音を伴う半空間学習のための最適sq下限
• Authors: Rajai Nasser, Stefan Tiegel
• Abstract要約: マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
• 参考スコア（独自算出の注目度）: 9.378684220920562
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give tight statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. In particular, suppose that all labels are corrupted with probability at most $\eta$. We show that for arbitrary $\eta \in [0,1/2]$ every SQ algorithm achieving misclassification error better than $\eta$ requires queries of superpolynomial accuracy or at least a superpolynomial number of queries. Further, this continues to hold even if the information-theoretically optimal error $\mathrm{OPT}$ is as small as $\exp\left(-\log^c(d)\right)$, where $d$ is the dimension and $0 < c < 1$ is an arbitrary absolute constant, and an overwhelming fraction of examples are noiseless. Our lower bound matches known polynomial time algorithms, which are also implementable in the SQ framework. Previously, such lower bounds only ruled out algorithms achieving error $\mathrm{OPT} + \epsilon$ or error better than $\Omega(\eta)$ or, if $\eta$ is close to $1/2$, error $\eta - o_\eta(1)$, where the term $o_\eta(1)$ is constant in $d$ but going to 0 for $\eta$ approaching $1/2$. As a consequence, we also show that achieving misclassification error better than $1/2$ in the $(A,\alpha)$-Tsybakov model is SQ-hard for $A$ constant and $\alpha$ bounded away from 1.
• Abstract（参考訳）: 半空間をマッサート雑音下で学習するために,stight statistical query (sq) 下限を与える。 特に、すべてのラベルが最大$\eta$の確率で腐敗していると仮定する。 任意の$\eta \in [0,1/2]$ に対して、$\eta$よりも誤分類エラーとなるsqアルゴリズムは、超多項精度または少なくとも超多項数のクエリを必要とする。 さらに、情報理論上の最適誤差 $\mathrm{OPT}$ が $\exp\left(-\log^c(d)\right)$ と同じくらい小さいとしても、$d$ は次元であり、$0 < c < 1$ は任意の絶対定数であり、例の圧倒的な分数はノイズのないものである。 我々の下限は、sqフレームワークで実装可能な既知の多項式時間アルゴリズムと一致する。 従来、このような下限は、エラー $\mathrm{opt} + \epsilon$ または$\omega(\eta)$ 以上のエラー、または$\eta$ が$/2$ に近い場合、$\eta - o_\eta(1)$ という単語が $d$ で一定であるが$\eta$ で 0 になるようなアルゴリズムを除外しただけだった。 その結果、$(A,\alpha)$-Tsybakovモデルにおける誤分類誤差が$(A,\alpha)$-Tsybakovモデルで 1 から 1 へ有界な$A$定数と $\alpha$ に対して SQ-hard であることが示される。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Memory-Sample Lower Bounds for Learning Parity with Noise [2.724141845301679]
  ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。 我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
  論文  参考訳（メタデータ） (2021-07-05T23:34:39Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。 任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
  論文  参考訳（メタデータ） (2021-03-17T00:59:33Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• Robust testing of low-dimensional functions [8.927163098772589]
  著者たちの最近の研究は、線型$k$-juntasがテスト可能であることを示した。 耐雑音性試験への関心が高まった後, 本論文では, 耐雑音性(あるいは頑健性)バージョンを実証する。 クエリ複雑性が$kO(mathsfpoly(log k/epsilon))$,$k$-halfspacesの交叉のクラスに対して完全耐雑音試験器を得る。
  論文  参考訳（メタデータ） (2020-04-24T10:23:12Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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