論文の概要: Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach
- arxiv url: http://arxiv.org/abs/2310.15411v2
- Date: Sat, 20 Jul 2024 00:01:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-24 05:26:51.575131
- Title: Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach
- Title（参考訳）: ツィバコフ雑音を伴う効率的な能動学習ハーフスペース:非凸最適化手法
- Authors: Yinan Li, Chicheng Zhang,
- Abstract要約: 本稿では,効率的な能動学習を計算的にラベル付けする問題について検討する。
本稿では, 近似値の証明を行う。
構造化された未ラベルデータセットの1階定常光点。
- 参考スコア（独自算出の注目度）: 28.518140532315776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of computationally and label efficient PAC active learning $d$-dimensional halfspaces with Tsybakov Noise~\citep{tsybakov2004optimal} under structured unlabeled data distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d (\frac{1}{\epsilon})^{\frac{8-6\alpha}{3\alpha-1}})$, under the assumption that the Tsybakov noise parameter $\alpha \in (\frac13, 1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting.
- Abstract（参考訳）: Tsybakov Noise~\citep{tsybakov 2004optimal} を用いた、構造化されていないデータ分布下での計算およびラベル付きPAC能動学習の課題について検討する。
ここでは, 滑らかな非凸損失関数の任意の1次定常点が, 過大な誤差の保証が低いハーフスペースとなることを証明した。
上記の構造的結果から、Tsybakovノイズパラメータ $\alpha \in (\frac13, 1]$ という仮定の下で、ラベル複雑性が $\tilde{O}(d (\frac{1}{\epsilon})^{\frac{8-6\alpha}{3\alpha-1}})$ となるような非凸最適化アルゴリズムを設計する。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Stochastic Nested Compositional Bi-level Optimization for Robust Feature
Learning [11.236838268731804]
ネストされた二段階最適化問題を解くアルゴリズムを開発し,解析する。
提案アルゴリズムは,行列複雑性やミニバッチに依存しない。
論文 参考訳（メタデータ） (2023-07-11T15:52:04Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results
and Construction [18.65143269806133]
我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。
古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
論文 参考訳（メタデータ） (2021-03-15T11:20:31Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - 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 Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。