論文の概要: Learning Halfspaces with Tsybakov Noise

• arxiv url: http://arxiv.org/abs/2006.06467v1
• Date: Thu, 11 Jun 2020 14:25:02 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-22 13:41:34.309782
• Title: Learning Halfspaces with Tsybakov Noise
• Title（参考訳）: トシバコフ雑音による半空間学習
• Authors: Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
• Abstract要約: テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
• 参考スコア（独自算出の注目度）: 50.659479930171585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the efficient PAC learnability of halfspaces in the presence of Tsybakov noise. In the Tsybakov noise model, each label is independently flipped with some probability which is controlled by an adversary. This noise model significantly generalizes the Massart noise model, by allowing the flipping probabilities to be arbitrarily close to $1/2$ for a fraction of the samples. Our main result is the first non-trivial PAC learning algorithm for this problem under a broad family of structured distributions -- satisfying certain concentration and (anti-)anti-concentration properties -- including log-concave distributions. Specifically, we given an algorithm that achieves misclassification error $\epsilon$ with respect to the true halfspace, with quasi-polynomial runtime dependence in $1/\epsilin$. The only previous upper bound for this problem -- even for the special case of log-concave distributions -- was doubly exponential in $1/\epsilon$ (and follows via the naive reduction to agnostic learning). Our approach relies on a novel computationally efficient procedure to certify whether a candidate solution is near-optimal, based on semi-definite programming. We use this certificate procedure as a black-box and turn it into an efficient learning algorithm by searching over the space of halfspaces via online convex optimization.
• Abstract（参考訳）: Tsybakovノイズの存在下でのハーフスペースの効率的なPAC学習性について検討する。 ツィバコフ雑音モデルでは、それぞれのラベルは独立して、敵によって制御される確率で反転される。 このノイズモデルは、サンプルのごく一部に対して、旋回確率を任意に1/2$にすることで、マッサートノイズモデルを大幅に一般化する。 私たちの主な結果は、ログコンケーブ分布を含む特定の濃度と(反)反集中特性を満たす、構造化分布の幅広いファミリーの下で、この問題に対する最初の非自明なpac学習アルゴリズムです。 具体的には、準多項式のランタイム依存を1/\epsilin$とする、真のハーフスペースに関する誤分類誤差を$\epsilon$とするアルゴリズムを与えられた。 対数凹分布の特別な場合でさえ、この問題の以前の上限は1/\epsilon$で2倍に指数関数的であった。 提案手法は,半定値プログラミングに基づいて,候補解が最適に近いかどうかを証明するための新しい計算効率の手法に依存する。 我々は,この証明手続きをブラックボックスとして使用し,オンライン凸最適化によるハーフスペースの空間を探索することで,効率的な学習アルゴリズムに変換する。

関連論文リスト

• Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach [28.518140532315776]
  本稿では,効率的な能動学習を計算的にラベル付けする問題について検討する。 本稿では, 近似値の証明を行う。 構造化された未ラベルデータセットの1階定常光点。
  論文  参考訳（メタデータ） (2023-10-23T23:55:28Z)
• 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)
• Boosting in the Presence of Massart Noise [49.72128048499074]
  マスアートノイズを伴う(分布に依存しない)PACモデルにおいて、弱い学習者の精度を高める問題について検討する。 我々の主な成果は、Massartノイズの存在下で最初の計算効率の良いブースティングアルゴリズムである。 正の結果の簡単な応用として、高次元矩形の和に対して、第一に効率的なMassart学習者を与える。
  論文  参考訳（メタデータ） (2021-06-14T22:21:25Z)
• Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise [29.890039126644776]
  我々は,Massart noisecitepmassart2006riskとTsybakov noiseciteptsybakov 2004を許容できる$d$次元同質半空間に対するPAC能動学習アルゴリズムを開発した。 より難易度の高いツィバコフ雑音条件の下では、2つの雑音条件のサブファミリを同定し、その下でアルゴリズムは計算効率を達成し、ラベルの複雑さを保証する。
  論文  参考訳（メタデータ） (2021-02-10T08:17:17Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance [21.76197397540397]
  本稿では,雑音下でのmathbbRd$における等質スパース半空間の計算的学習について述べる。 サンプルの複雑さは$tildeObig(frac 1 epsilon s2 log5 d big)$であり、属性効率も楽しめます。
  論文  参考訳（メタデータ） (2020-06-06T04:57:39Z)
• Efficiently Learning Adversarially Robust Halfspaces with Noise [69.01459748050453]
  本研究では,分布に依存しない環境下で,逆向きに頑健なハーフスペースを学習する問題について検討する。 実現可能な設定では、ハーフ空間が効果的に学習可能な対向摂動集合に対して必要かつ十分な条件を提供する。
  論文  参考訳（メタデータ） (2020-05-15T17:13:54Z)
• Learning Halfspaces with Massart Noise Under Structured Distributions [46.37328271312332]
  分布特異的PACモデルにおいて,マスアートノイズを伴う学習空間の問題を解く。 対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対
  論文  参考訳（メタデータ） (2020-02-13T17:02:37Z)

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

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