論文の概要: Accelerated SGD for Non-Strongly-Convex Least Squares
- arxiv url: http://arxiv.org/abs/2203.01744v1
- Date: Thu, 3 Mar 2022 14:39:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-04 22:29:38.600482
- Title: Accelerated SGD for Non-Strongly-Convex Least Squares
- Title（参考訳）: 非ストロングリ凸最小方形に対する加速SGD
- Authors: Aditya Varre, Nicolas Flammarion
- Abstract要約: 非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 14.010916616909743
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider stochastic approximation for the least squares regression problem
in the non-strongly convex setting. We present the first practical algorithm
that achieves the optimal prediction error rates in terms of dependence on the
noise of the problem, as $O(d/t)$ while accelerating the forgetting of the
initial conditions to $O(d/t^2)$. Our new algorithm is based on a simple
modification of the accelerated gradient descent. We provide convergence
results for both the averaged and the last iterate of the algorithm. In order
to describe the tightness of these new bounds, we present a matching lower
bound in the noiseless setting and thus show the optimality of our algorithm.
- Abstract（参考訳）: 非強凸条件における最小二乗回帰問題に対する確率近似を考察する。
本稿では,問題の雑音依存性の観点から最適予測誤差率を達成する最初の実用的アルゴリズムを,初期条件の忘れ込みを$o(d/t^2)$に高速化しながら,$o(d/t)$とする。
我々の新しいアルゴリズムは、加速勾配勾配の簡単な修正に基づいている。
アルゴリズムの平均値と最後の反復値の両方について収束結果を提供する。
これらの新しい境界の厳密性を記述するために、ノイズのない設定で一致する下限を示し、アルゴリズムの最適性を示す。
関連論文リスト
- Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2022-02-07T21:23:17Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。