論文の概要: A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
- arxiv url: http://arxiv.org/abs/2010.01705v1
- Date: Sun, 4 Oct 2020 22:19:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 03:31:10.555840
- Title: A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
- Title（参考訳）: チバコフ雑音による半空間学習のための多項式時間アルゴリズム
- Authors: Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos,
Nikos Zarifis
- Abstract要約: 本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
- 参考スコア（独自算出の注目度）: 55.45544638410858
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of PAC learning homogeneous halfspaces in the presence
of Tsybakov noise. In the Tsybakov noise model, the label of every sample is
independently flipped with an adversarially controlled probability that can be
arbitrarily close to $1/2$ for a fraction of the samples. {\em We give the
first polynomial-time algorithm for this fundamental learning problem.} Our
algorithm learns the true halfspace within any desired accuracy $\epsilon$ and
succeeds under a broad family of well-behaved distributions including
log-concave distributions. Prior to our work, the only previous algorithm for
this problem required quasi-polynomial runtime in $1/\epsilon$.
Our algorithm employs a recently developed reduction \cite{DKTZ20b} from
learning to certifying the non-optimality of a candidate halfspace. This prior
work developed a quasi-polynomial time certificate algorithm based on
polynomial regression. {\em The main technical contribution of the current
paper is the first polynomial-time certificate algorithm.} Starting from a
non-trivial warm-start, our algorithm performs a novel "win-win" iterative
process which, at each step, either finds a valid certificate or improves the
angle between the current halfspace and the true one. Our warm-start algorithm
for isotropic log-concave distributions involves a number of analytic tools
that may be of broader interest. These include a new efficient method for
reweighting the distribution in order to recenter it and a novel
characterization of the spectrum of the degree-$2$ Chow parameters.
- Abstract（参考訳）: 本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
ツィバコフ雑音モデルでは、各サンプルのラベルは独立に逆制御された確率で反転し、サンプルのごく一部に対して任意に1/2$に近い値となる。
この基本学習問題に対して,最初の多項式時間アルゴリズムを与える。
当社のアルゴリズムは,任意の精度で真半空間を学習し,ログ凹凸分布を含む多種多様な分布の下で成功する。
我々の研究の前には、この問題に対する唯一の以前のアルゴリズムは、$/\epsilon$の準多項ランタイムでした。
提案アルゴリズムは,最近開発されたリミット{DKTZ20b} を用いて,候補ハーフスペースの非最適性を証明する。
この先行研究は多項式回帰に基づく準多項時間証明アルゴリズムを開発した。
現在の論文の主な技術的貢献は、最初の多項式時間証明アルゴリズムである。
} 非自明なウォームスタートから始めると、アルゴリズムは新たな"ウィン-ウィン"反復プロセスを実行し、各ステップで有効な証明書を見つけるか、現在のハーフスペースと真の証明書の角度を改善する。
等方性対数凸分布に対するウォームスタートアルゴリズムには、幅広い興味を持つ可能性のある解析ツールが多数含まれている。
これらには、より最新のものにするために分布を再重み付けする新しい効率的な方法と、2$Chowパラメータのスペクトルの新たな特徴が含まれる。
関連論文リスト
- Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time [8.419603619167813]
所望のテレビ距離内において,$d$次元空間にマージンを持つ高次元半空間を学習するためのガウス時間アルゴリズムを提案する。
我々のアルゴリズムはラベルを必要とせず、隠れたハーフスペースのユニークな(そして効率的な)識別性を確立する。
超ポリノミカルな既存のモーメントバウンド保証の代わりに、トータル変分(TV)距離に基づくポリタイム保証を提供することにより、この問題を改善する。
論文 参考訳（メタデータ） (2023-11-02T17:51:10Z) - A Strongly Polynomial Algorithm for Approximate Forster Transforms and
its Application to Halfspace Learning [56.86097988183311]
フォースター変換(フォースターりゅう、英: Forster transform)は、データセットを放射等方性位置に配置し、その性質のいくつかを維持しながら、データセットを正規化する方法である。
論文 参考訳（メタデータ） (2022-12-06T14:32:02Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文 参考訳（メタデータ） (2022-11-14T13:09:12Z) - Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
ガウスの下の半空間を不可知的に学習する問題を考察する。
我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
論文 参考訳（メタデータ） (2021-02-10T18:40:44Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。