論文の概要: Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
- arxiv url: http://arxiv.org/abs/2010.00539v2
- Date: Sun, 14 Feb 2021 02:20:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 07:42:59.244544
- Title: Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
- Title（参考訳）: ソフトマージンによるグラディエントDescentをもつハーフスペースの学習
- Authors: Spencer Frei and Yuan Cao and Quanquan Gu
- Abstract要約: 勾配降下は、分類誤差$tilde O(mathsfOPT1/2) + varepsilon$ in $mathrmpoly(d,1/varepsilon)$ time and sample complexity.
- 参考スコア（独自算出の注目度）: 92.7662890047311
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the properties of gradient descent on convex surrogates for the
zero-one loss for the agnostic learning of linear halfspaces. If $\mathsf{OPT}$
is the best classification error achieved by a halfspace, by appealing to the
notion of soft margins we are able to show that gradient descent finds
halfspaces with classification error $\tilde O(\mathsf{OPT}^{1/2}) +
\varepsilon$ in $\mathrm{poly}(d,1/\varepsilon)$ time and sample complexity for
a broad class of distributions that includes log-concave isotropic
distributions as a subclass. Along the way we answer a question recently posed
by Ji et al. (2020) on how the tail behavior of a loss function can affect
sample complexity and runtime guarantees for gradient descent.
- Abstract（参考訳）: 線形半空間の非依存学習における零点損失に対する凸置換体上の勾配降下特性を解析する。
もし$\mathsf{OPT}$がハーフ空間によって達成される最良の分類誤差であるなら、ソフトマージンの概念に訴えて、勾配降下が分類誤差$\tilde O(\mathsf{OPT}^{1/2}) + \varepsilon$ in $\mathrm{poly}(d,1/\varepsilon)$時間とサンプルの複雑さを、サブクラスとして対数の等方分布を含む広い分布のクラスに対して示せることを示すことができる。
最近Ji et al. (2020) が提起した、損失関数の尾の挙動がサンプルの複雑さと勾配勾配に対する実行時の保証にどのように影響するかについての質問に答える。
関連論文リスト
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
固定学習率$eta$の勾配降下はスムーズな関数を表す局所最小値しか見つからないことを示す。
また、$n$のデータポイントのサポートの厳密な内部で、$widetildeO(n-4/5)$のほぼ最適MSE境界を証明します。
論文 参考訳（メタデータ） (2024-06-10T22:57:27Z) - Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces
and ReLU Regression under Gaussian Marginals [43.0867217287089]
ガウス分布の下で半空間を不可知的に学習する作業について検討する。
この課題に対して,ほぼ最適計算硬度を証明した。
論文 参考訳（メタデータ） (2023-02-13T16:46:23Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Provable Robustness of Adversarial Training for Learning Halfspaces with
Noise [95.84614821570283]
ラベル雑音の存在下での敵対的ロバストなハーフスペースの特性を分析する。
我々の知る限りでは、これは敵の訓練がノイズの分類子を与えることを示す最初の研究である。
論文 参考訳（メタデータ） (2021-04-19T16:35:38Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Gradient Methods Never Overfit On Separable Data [31.714928102950584]
標準勾配法は分離可能なデータに過度に適合しないことを示す。
データセットに対するマージン違反数の非漸近的境界を示す。
論文 参考訳（メタデータ） (2020-06-30T18:01:46Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。