論文の概要: Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization

• arxiv url: http://arxiv.org/abs/2006.10281v4
• Date: Sun, 7 Mar 2021 18:03:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-19 14:16:20.876943
• Title: Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization
• Title（参考訳）: 有限和最適化のための加速デュアル平均化による分散低減
• Authors: Chaobing Song, Yong Jiang and Yi Ma
• Abstract要約: 本稿では,VRADA (Accelerated Dual Averaging) による EmphVariance Reduction という,有限サム凸最適化の簡略化と統一手法を提案する。 一般凸設定と強凸設定の両方において、VRADAは$O(nloglog n)$で$Obig(frac1nbig)$-accurateソリューションを得ることができる。
• 参考スコア（独自算出の注目度）: 39.32047621531731
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we introduce a simplified and unified method for finite-sum convex optimization, named \emph{Variance Reduction via Accelerated Dual Averaging (VRADA)}. In both general convex and strongly convex settings, VRADA can attain an $O\big(\frac{1}{n}\big)$-accurate solution in $O(n\log\log n)$ number of stochastic gradient evaluations which improves the best-known result $O(n\log n)$, where $n$ is the number of samples. Meanwhile, VRADA matches the lower bound of the general convex setting up to a $\log\log n$ factor and matches the lower bounds in both regimes $n\le \Theta(\kappa)$ and $n\gg \kappa$ of the strongly convex setting, where $\kappa$ denotes the condition number. Besides improving the best-known results and matching all the above lower bounds simultaneously, VRADA has more unified and simplified algorithmic implementation and convergence analysis for both the general convex and strongly convex settings. The underlying novel approaches such as the novel initialization strategy in VRADA may be of independent interest. Through experiments on real datasets, we show the good performance of VRADA over existing methods for large-scale machine learning problems.
• Abstract（参考訳）: 本稿では,VRADA(Accelerated Dual Averaging)と呼ばれる有限サム凸最適化の簡易かつ統一的な手法を提案する。 一般的な凸設定と強い凸設定の両方において、vradaは$o(n\log\log n)$で$o\big(\frac{1}{n}\big)$-accurateの解を得ることができ、最もよく知られた結果である$o(n\log n)$がサンプル数である。 一方、vrada は $\log\log n$ まで設定された一般凸の下限と一致し、両方のレジームにおける下限である $n\le \theta(\kappa)$ と $n\gg \kappa$ に一致し、ここで $\kappa$ は条件数を表す。 最もよく知られた結果の改善と上記のすべての下位境界の同時マッチングに加えて、VRADAは一般的な凸と強い凸設定の両方に対してより統一的で単純化されたアルゴリズムの実装と収束解析を行う。 VRADAにおける新しい初期化戦略のような新しいアプローチは、独立した関心を持つかもしれない。 実データセットの実験を通じて、大規模機械学習問題に対する既存の手法よりも優れたVRADA性能を示す。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
  ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。 本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。 最後に,提案手法に適用可能な最終収束率を導出する。
  論文  参考訳（メタデータ） (2023-12-02T07:12:00Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。 我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
  論文  参考訳（メタデータ） (2023-06-03T23:31:27Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• A globally convergent fast iterative shrinkage-thresholding algorithm with a new momentum factor for single and multi-objective convex optimization [0.0]
  提案手法はまた,任意の$(a,b)$に対して,大域収束率$O(1/k2)$を持つことを示す。 様々な$(a,b)$で数値結果を報告し、これらの選択のいくつかが古典的な運動量因子よりも良い結果をもたらすことを示す。
  論文  参考訳（メタデータ） (2022-05-11T04:26:00Z)
• Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums [23.55868673358398]
  機械学習アプリケーションに広く現れる構造化非平滑凸有限和最適化について検討する。 本稿では,emphVariance Reducing by Primal-Dual Accelerated Dual Averaging (vrpda)を提案する。
  論文  参考訳（メタデータ） (2021-02-26T18:40:58Z)

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

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