論文の概要: Sharper Analysis for Minibatch Stochastic Proximal Point Methods:
Stability, Smoothness, and Deviation
- arxiv url: http://arxiv.org/abs/2301.03125v1
- Date: Mon, 9 Jan 2023 00:13:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-10 16:24:19.213880
- Title: Sharper Analysis for Minibatch Stochastic Proximal Point Methods:
Stability, Smoothness, and Deviation
- Title（参考訳）: ミニバッチ確率的近位点法のシャープ解析 : 安定性, 滑らか性, 偏差
- Authors: Xiao-Tong Yuan and Ping Li
- Abstract要約: 我々は,凸複合リスク最小化問題の解法として,近位点法(M-SPP)のミニバッチ変種について検討した。
ミニバッチサイズが$n$で二次数が$T$のM-SPPは、予想外収束の速さを楽しむことを示す。
小さい$n$-large-$T$設定では、この結果はSPP型アプローチの最もよく知られた結果を大幅に改善する。
- 参考スコア（独自算出の注目度）: 41.082982732100696
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The stochastic proximal point (SPP) methods have gained recent attention for
stochastic optimization, with strong convergence guarantees and superior
robustness to the classic stochastic gradient descent (SGD) methods showcased
at little to no cost of computational overhead added. In this article, we study
a minibatch variant of SPP, namely M-SPP, for solving convex composite risk
minimization problems. The core contribution is a set of novel excess risk
bounds of M-SPP derived through the lens of algorithmic stability theory.
Particularly under smoothness and quadratic growth conditions, we show that
M-SPP with minibatch-size $n$ and iteration count $T$ enjoys an in-expectation
fast rate of convergence consisting of an
$\mathcal{O}\left(\frac{1}{T^2}\right)$ bias decaying term and an
$\mathcal{O}\left(\frac{1}{nT}\right)$ variance decaying term. In the
small-$n$-large-$T$ setting, this result substantially improves the best known
results of SPP-type approaches by revealing the impact of noise level of model
on convergence rate. In the complementary small-$T$-large-$n$ regime, we
provide a two-phase extension of M-SPP to achieve comparable convergence rates.
Moreover, we derive a near-tight high probability (over the randomness of data)
bound on the parameter estimation error of a sampling-without-replacement
variant of M-SPP. Numerical evidences are provided to support our theoretical
predictions when substantialized to Lasso and logistic regression models.
- Abstract（参考訳）: 確率的近位点法 (SPP) は確率的最適化において近年注目されており、強い収束保証と古典的確率的勾配勾配勾配法 (SGD) に対する優れた頑健性は計算オーバーヘッドのコストをほとんど、あるいは全く加えていない。
本稿では, コンベックス複合リスク最小化問題の解法として, SPP のミニバッチ変種 M-SPP について検討する。
コアコントリビューションは、アルゴリズム安定性理論のレンズから導かれるM-SPPの新たな過剰リスク境界の集合である。
特に、滑らかで二次的な成長条件下では、ミニバッチサイズ$n$と反復数$T$のM-SPPが、$\mathcal{O}\left(\frac{1}{T^2}\right)$バイアス減衰項と$\mathcal{O}\left(\frac{1}{nT}\right)$分散崩壊項からなる、予想できない収束率を楽しむことを示す。
小型の$-large-$T$設定において、この結果は収束率に対するモデルのノイズレベルの影響を明らかにすることにより、SPP型アプローチの最もよく知られた結果を大幅に改善する。
相補的な小$T$-large-$n$レジームでは、M-SPPの2相拡張を提供し、同値収束率を達成する。
さらに、m-sppのサンプリング無置換変種におけるパラメータ推定誤差にバインドされた(データのランダム性よりも)密接な高確率を求める。
ラッソおよびロジスティック回帰モデルに実質化されると、理論的予測を支持する数値的な証拠が提供される。
関連論文リスト
- Stochastic Polyak Step-sizes and Momentum: Convergence Guarantees and Practical Performance [10.11126899274029]
我々はヘビーボール法(SHB)の更新規則に適した新しいポリアク型変種を提案し,検討する。
MomSPS$_max$ に対して、(仮定なしで)凸および滑らかな問題に対する解の近傍に SHB の保証を提供する。
その他の2つの変種である MomDecSPS と MomAdaSPS は、SHB の最初の適応的なステップサイズであり、事前の知識なしに正確な最小値への収束を保証する。
論文 参考訳（メタデータ） (2024-06-06T15:08:06Z) - A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。
本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
論文 参考訳（メタデータ） (2024-05-24T21:09:19Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
楽観的勾配法はミニマックス最適化問題に対処するのに有用である。
従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
論文 参考訳（メタデータ） (2024-01-26T01:16:59Z) - Efficiently Escaping Saddle Points for Non-Convex Policy Optimization [40.0986936439803]
政策勾配(PG)は、拡張性と優れた性能のために強化学習に広く用いられている。
本稿では,ヘッセンベクトル積 (HVP) の形で二階情報を用いた分散還元二階法を提案し,サンプルの複雑さを$tildeO(epsilon-3)$とする近似二階定常点 (SOSP) に収束する。
論文 参考訳（メタデータ） (2023-11-15T12:36:45Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reduction [2.048226951354646]
弱凸, 複合最適化問題に対する実装可能な近位点(SPP)法を開発した。
提案アルゴリズムは分散低減機構を組み込んでおり、その結果の更新は不正確なセミスムース・ニュートン・フレームワークを用いて解決される。
論文 参考訳（メタデータ） (2022-04-01T13:08:49Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Estimation in Tensor Ising Models [5.161531917413708]
N$ノード上の分布から1つのサンプルを与えられた$p$-tensor Isingモデルの自然パラメータを推定する問題を考える。
特に、$sqrt N$-consistency of the MPL estimate in the $p$-spin Sherrington-Kirkpatrick (SK) model。
我々は、$p$-tensor Curie-Weiss モデルの特別な場合における MPL 推定の正確なゆらぎを導出する。
論文 参考訳（メタデータ） (2020-08-29T00:06:58Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。