論文の概要: Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization
- arxiv url: http://arxiv.org/abs/2211.01851v1
- Date: Thu, 3 Nov 2022 14:41:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-04 14:30:45.931495
- Title: Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization
- Title(参考訳): 非凸有限サム最小化に対する適応確率的分散低減
- Authors: Ali Kavis, Stratis Skoulakis, Kimon Antonakopoulos, Leello Tadesse
Dadi, Volkan Cevher
- Abstract要約: 有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
- 参考スコア(独自算出の注目度): 52.25843977506935
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose an adaptive variance-reduction method, called AdaSpider, for
minimization of $L$-smooth, non-convex functions with a finite-sum structure.
In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan
& Streeter, 2010], but a fairly distinct, adaptive step-size schedule with the
recursive stochastic path integrated estimator proposed in [Fang et al., 2018].
To our knowledge, Adaspider is the first parameter-free non-convex
variance-reduction method in the sense that it does not require the knowledge
of problem-dependent parameters, such as smoothness constant $L$, target
accuracy $\epsilon$ or any bound on gradient norms. In doing so, we are able to
compute an $\epsilon$-stationary point with $\tilde{O}\left(n +
\sqrt{n}/\epsilon^2\right)$ oracle-calls, which matches the respective lower
bound up to logarithmic factors.
- Abstract(参考訳): 有限サム構造をもつ非凸関数である$L$-smooth を最小化するための適応分散還元法 AdaSpider を提案する。
本質的に、adaspider はadagrad にインスパイアされた [duchi et al., 2011, mcmahan & streeter, 2010] を組み合わせるが、[fang et al., 2018] で提案された再帰的確率的経路統合推定子とかなり異なる適応的なステップサイズスケジュールを組み合わせる。
我々の知る限り、Adaspiderはスムーズネス定数$L$、目標精度$\epsilon$、勾配ノルム上の任意の境界といった問題依存パラメータの知識を必要としないという意味で、最初のパラメータフリーな非凸分散還元法である。
そうすることで、$\epsilon$-stationary point を $\tilde{O}\left(n + \sqrt{n}/\epsilon^2\right)$ oracle-calls で計算できる。
関連論文リスト
- Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
基礎となるオラクルが一様有界であれば,本手法は全体のオラクル複雑性が$tildeO(varepsilon-5)$であることを示す。
平均報酬と割引報酬を決定するための新しい同期アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-19T01:07:35Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。
推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
論文 参考訳(メタデータ) (2023-01-17T18:44:41Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual
Balancing and Iteration Complexity Analysis [28.575516056239575]
PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。
PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
論文 参考訳(メタデータ) (2022-09-22T07:12:48Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳(メタデータ) (2022-02-09T06:05:38Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。