論文の概要: A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm
- arxiv url: http://arxiv.org/abs/2202.09688v1
- Date: Sat, 19 Feb 2022 22:12:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-25 16:11:03.212945
- Title: A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm
- Title（参考訳）: 分散還元型確率的加速原始双対アルゴリズム
- Authors: Bugra Can, Mert Gurbuzbalaban, Necdet Serhat Aybat
- Abstract要約: このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。
高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。
提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
- 参考スコア（独自算出の注目度）: 3.2958527541557525
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we consider strongly convex strongly concave (SCSC) saddle
point (SP) problems
$\min_{x\in\mathbb{R}^{d_x}}\max_{y\in\mathbb{R}^{d_y}}f(x,y)$ where $f$ is
$L$-smooth, $f(.,y)$ is $\mu$-strongly convex for every $y$, and $f(x,.)$ is
$\mu$-strongly concave for every $x$. Such problems arise frequently in machine
learning in the context of robust empirical risk minimization (ERM), e.g.
$\textit{distributionally robust}$ ERM, where partial gradients are estimated
using mini-batches of data points. Assuming we have access to an unbiased
stochastic first-order oracle we consider the stochastic accelerated primal
dual (SAPD) algorithm recently introduced in Zhang et al. [2021] for SCSC SP
problems as a robust method against gradient noise. In particular, SAPD
recovers the well-known stochastic gradient descent ascent (SGDA) as a special
case when the momentum parameter is set to zero and can achieve an accelerated
rate when the momentum parameter is properly tuned, i.e., improving the $\kappa
\triangleq L/\mu$ dependence from $\kappa^2$ for SGDA to $\kappa$. We propose
efficient variance-reduction strategies for SAPD based on Richardson-Romberg
extrapolation and show that our method improves upon SAPD both in practice and
in theory.
- Abstract（参考訳）: この研究では、強い凸(scscsc)saddle point (sp)問題$\min_{x\in\mathbb{r}^{d_x}}\max_{y\in\mathbb{r}^{d_y}}f(x,y)$ ここで$f$は$l$-smooth、$f(.,y)$は$y$ごとに$\mu$-strongly convex、$f(x,.)$は$x$ごとに$\mu$-strongly concaveである。
このような問題は、例えば$\textit{distributionally robust}$ ERMのように、ロバストな経験的リスク最小化(ERM)の文脈で機械学習において頻繁に発生する。
偏りのない確率的一階のオラクルにアクセスできると仮定すると、zhangらによって最近導入された確率的加速原始双対(sapd)アルゴリズムを考える。
勾配雑音に対する頑健な手法としてのSCSC SP問題に対する[2021]。
特にSAPDは、運動量パラメータが 0 に設定されたときの特別なケースとして有名な確率勾配勾配上昇(SGDA)を回復し、運動量パラメータが適切に調整されたときの加速率、すなわち、$\kappa \triangleq L/\mu$依存を SGDA に対して $\kappa^2$ から $\kappa$ に改善できる。
我々はリチャードソン・ロームバーグ外挿に基づくSAPDの効率的な分散還元戦略を提案し、本手法がSAPDの実際と理論の両方において改善されていることを示す。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients [0.196629787330046]
目的関数の部分的な2次情報を組み込むことで、分散還元勾配法のミニバッチサイズに対するロバスト性を劇的に向上させることができることを示す。
本稿では,この現象をプロトタイプNewton(textttMb-SVRN$)アルゴリズムで示す。
論文 参考訳（メタデータ） (2024-04-23T05:45:52Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization [52.25843977506935]
有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
論文 参考訳（メタデータ） (2022-11-03T14:41:46Z) - On Acceleration of Gradient-Based Empirical Risk Minimization using
Local Polynomial Regression [0.491574468325115]
最近提案された局所多項式補間法(LPIGD)による近似解経験的リスク問題(ERM)の高速化について検討した。
我々は条件数$sigma$と強く凸で滑らかな損失関数にフォーカスする。
LPI-GDに基づく問題を高速化する2つの手法を提案し,その複雑さを$tildeOleft(sqrtsigma md log (1/varepsilon)$とする。
論文 参考訳（メタデータ） (2022-04-16T02:39:45Z) - Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
論文 参考訳（メタデータ） (2021-10-21T19:22:14Z) - What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。
本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。
1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
論文 参考訳（メタデータ） (2021-10-13T17:50:46Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Non-Euclidean Differentially Private Stochastic Convex Optimization [15.302167005107135]
雑音勾配降下法(SGD)アルゴリズムは低次元状態において最適過大なリスクを達成できることを示す。
私たちの作品は、規則性、均一凸性、均一な平滑性の概念など、規範空間の幾何学から概念を導き出します。
論文 参考訳（メタデータ） (2021-03-01T19:48:44Z) - 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) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。