論文の概要: 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 で計算できる。

関連論文リスト

• Variance-reduced first-order methods for deterministically constrained stochastic nonconvex optimization with strong convergence guarantees [1.2562458634975162]
  既存の方法は典型的には$epsilon$-stochasticの固定点を見つけることを目的としている。 多くの実践的応用において、制約がほぼ確実に満たされることが重要であり、そのような$epsilon$-stochasticの定常点が望ましくない可能性がある。
  論文  参考訳（メタデータ） (2024-09-16T00:26:42Z)
• 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)
• Estimating the minimizer and the minimum value of a regression function under passive design [72.85024381807466]
  最小値 $boldsymbolx*$ と最小値 $f*$ を滑らかで凸な回帰関数 $f$ で推定する新しい手法を提案する。 2次リスクと$boldsymbolz_n$の最適化誤差、および$f*$を推定するリスクについて、漸近的でない上界を導出する。
  論文  参考訳（メタデータ） (2022-11-29T18:38:40Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。