論文の概要: Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization
- arxiv url: http://arxiv.org/abs/2202.13328v1
- Date: Sun, 27 Feb 2022 09:41:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-01 17:46:49.955008
- Title: Thinking Outside the Ball: Optimal Learning with Gradient Descent for
Generalized Linear Stochastic Convex Optimization
- Title（参考訳）: ボールの外を考える:一般化線形確率凸最適化のためのグラディエントDescentを用いた最適学習
- Authors: Idan Amir, Roi Livni, Nathan Srebro
- Abstract要約: 我々は凸リプシッツ損失を伴う線形予測、あるいはより一般に一般化線型形式の凸最適化問題を考える。
この設定では、初期反復が明示的な正規化や投影を伴わずにグラディエント Descent (GD) を停止し、過大なエラーを最大$epsilon$で保証することを示した。
しかし、標準球における一様収束は、$Theta (1/epsilon4)$サンプルを用いた最適下界学習を保証できることを示しているが、分布依存球における一様収束に依存している。
- 参考スコア（独自算出の注目度）: 37.177329562964765
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider linear prediction with a convex Lipschitz loss, or more
generally, stochastic convex optimization problems of generalized linear form,
i.e.~where each instantaneous loss is a scalar convex function of a linear
function. We show that in this setting, early stopped Gradient Descent (GD),
without any explicit regularization or projection, ensures excess error at most
$\epsilon$ (compared to the best possible with unit Euclidean norm) with an
optimal, up to logarithmic factors, sample complexity of
$\tilde{O}(1/\epsilon^2)$ and only $\tilde{O}(1/\epsilon^2)$ iterations. This
contrasts with general stochastic convex optimization, where
$\Omega(1/\epsilon^4)$ iterations are needed Amir et al. [2021b]. The lower
iteration complexity is ensured by leveraging uniform convergence rather than
stability. But instead of uniform convergence in a norm ball, which we show can
guarantee suboptimal learning using $\Theta(1/\epsilon^4)$ samples, we rely on
uniform convergence in a distribution-dependent ball.
- Abstract（参考訳）: リプシッツ損失を伴う線形予測、あるいはより一般的には、一般化線形形式の確率凸最適化問題、すなわち、各瞬時損失が線形関数のスカラー凸関数である場合を考える。
この設定において、早く停止したグラディエント・ディクセント(GD)は、明示的な正則化や射影を持たず、過大なエラーを最大$\epsilon$(単位ユークリッドノルムと同等である)で、最適な対数的因子、サンプルの複雑さが$\tilde{O}(1/\epsilon^2)$および$\tilde{O}(1/\epsilon^2)$の繰り返しで保証する。
これは一般確率凸最適化とは対照的で、$\Omega(1/\epsilon^4)$ iterations are need Amir et al。
【2021b】
低いイテレーションの複雑さは、安定性よりも一様収束を利用することによって保証される。
しかし、$\theta(1/\epsilon^4)$サンプルを用いて準最適学習を保証できるノルム球内の一様収束の代わりに、分布依存球における一様収束に依存する。
関連論文リスト
- The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳（メタデータ） (2023-11-09T14:29:25Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Tight Nonparametric Convergence Rates for Stochastic Gradient Descent
under the Noiseless Linear Model [0.0]
このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。
特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
論文 参考訳（メタデータ） (2020-06-15T08:25:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。