論文の概要: Accelerated, Optimal, and Parallel: Some Results on Model-Based
Stochastic Optimization
- arxiv url: http://arxiv.org/abs/2101.02696v1
- Date: Thu, 7 Jan 2021 18:58:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-10 13:42:54.742623
- Title: Accelerated, Optimal, and Parallel: Some Results on Model-Based
Stochastic Optimization
- Title(参考訳): 加速・最適・並列:モデルに基づく確率最適化に関するいくつかの結果
- Authors: Karan Chadha, Gary Cheng, John C. Duchi
- Abstract要約: 凸最適化問題を解決するためのモデルベース手法の近似近位点(aProx)ファミリを拡張します。
我々は、非漸近収束保証と、ミニバッチサイズの線形スピードアップを提供する加速スキームを提供する。
我々は,「補間」問題に対する新しい基本定数を同定し,収束率の改善と下界の整合性を示す。
- 参考スコア(独自算出の注目度): 33.71051480619541
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We extend the Approximate-Proximal Point (aProx) family of model-based
methods for solving stochastic convex optimization problems, including
stochastic subgradient, proximal point, and bundle methods, to the minibatch
and accelerated setting. To do so, we propose specific model-based algorithms
and an acceleration scheme for which we provide non-asymptotic convergence
guarantees, which are order-optimal in all problem-dependent constants and
provide linear speedup in minibatch size, while maintaining the desirable
robustness traits (e.g. to stepsize) of the aProx family. Additionally, we show
improved convergence rates and matching lower bounds identifying new
fundamental constants for "interpolation" problems, whose importance in
statistical machine learning is growing; this, for example, gives a
parallelization strategy for alternating projections. We corroborate our
theoretical results with empirical testing to demonstrate the gains accurate
modeling, acceleration, and minibatching provide.
- Abstract(参考訳): 確率的部分次数、近位点、バンドル法を含む確率的凸最適化問題を解くためのモデルベース手法の近似近位点(aprox)ファミリーをミニバッチおよび高速化設定に拡張する。
そこで本研究では,すべての問題依存定数の次数最適である非漸近収束保証と,望ましいロバスト性特性を維持しつつミニバッチサイズの線形高速化を提供するためのモデルベースアルゴリズムと加速度スキームを提案する。
aProxファミリーの(ステップ化)。
さらに,統計的機械学習の重要性が増大している「補間」問題に対する新しい基本定数を同定する収束率と下限の一致を示す。
実験によって得られた理論結果を相関させて, 精度の高いモデリング, 加速度, ミニバッチ化を実証する。
関連論文リスト
- Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast
Evasion of Non-Degenerate Saddle Points [8.452349885923507]
グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。
最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。
非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
論文 参考訳(メタデータ) (2022-12-07T16:36:23Z) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳(メタデータ) (2022-03-18T05:49:13Z) - Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent
Flows [4.817429789586127]
本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。
提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
論文 参考訳(メタデータ) (2021-12-02T16:04:40Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳(メタデータ) (2021-06-29T09:48:46Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Minibatch and Momentum Model-based Methods for Stochastic Non-smooth
Non-convex Optimization [3.4809730725241597]
モデルベース手法に対する2つの重要な拡張を行う。
まず,各イテレーションのモデル関数を近似するために,サンプルの集合を用いる新しいミニバッチを提案する。
第二に、運動量法の成功により、新しい凸モデルを提案する。
論文 参考訳(メタデータ) (2021-06-06T05:31:57Z) - The Role of Momentum Parameters in the Optimal Convergence of Adaptive
Polyak's Heavy-ball Methods [12.93796690939018]
適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。
新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
論文 参考訳(メタデータ) (2021-02-15T02:57:14Z) - Acceleration Methods [87.07695512525717]
まず,二次最適化問題を用いて,モメンタムとネスト正則性最適化スキームという2つの主要な手法を導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
次に、emphCatalystとemphAccelerated Hybrid Proximal Extragradientフレームワークの中心にある加速度技術をカバーする。
論文 参考訳(メタデータ) (2021-01-23T17:58:25Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
本稿では,汎用凸あるいは非汎用機械目標の新しいモデルを提案する。
本稿では,各サブプロブレムの点レベルを徐々に緩和した制約を解くアルゴリズムを提案する。
我々は,新しい数値スケール問題の有効性を実証する。
論文 参考訳(メタデータ) (2020-10-23T05:24:05Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳(メタデータ) (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。