Fugu-MT 論文翻訳(概要): Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums

論文の概要: Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums

arxiv url: http://arxiv.org/abs/2102.13643v1
Date: Fri, 26 Feb 2021 18:40:58 GMT
ステータス: 処理完了
システム内更新日: 2021-03-01 13:40:42.687245
Title: Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
Title（参考訳）: 非平滑凸有限要素の一次二重加速二重平均化による分散低減
Authors: Chaobing Song, Stephen J. Wright and Jelena Diakonikolas
Abstract要約: 機械学習アプリケーションに広く現れる構造化非平滑凸有限和最適化について検討する。本稿では,emphVariance Reducing by Primal-Dual Accelerated Dual Averaging (vrpda)を提案する。
参考スコア（独自算出の注目度）: 23.55868673358398
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study structured nonsmooth convex finite-sum optimization that appears widely in machine learning applications, including support vector machines and least absolute deviation. For the primal-dual formulation of this problem, we propose a novel algorithm called \emph{Variance Reduction via Primal-Dual Accelerated Dual Averaging (\vrpda)}. In the nonsmooth and general convex setting, \vrpda~has the overall complexity $O(nd\log\min \{1/\epsilon, n\} + d/\epsilon )$ in terms of the primal-dual gap, where $n$ denotes the number of samples, $d$ the dimension of the primal variables, and $\epsilon$ the desired accuracy. In the nonsmooth and strongly convex setting, the overall complexity of \vrpda~becomes $O(nd\log\min\{1/\epsilon, n\} + d/\sqrt{\epsilon})$ in terms of both the primal-dual gap and the distance between iterate and optimal solution. Both these results for \vrpda~improve significantly on state-of-the-art complexity estimates, which are $O(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\epsilon)$ for the nonsmooth and general convex setting and $O(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\sqrt{\epsilon})$ for the nonsmooth and strongly convex setting, in a much more simple and straightforward way. Moreover, both complexities are better than \emph{lower} bounds for general convex finite sums that lack the particular (common) structure that we consider. Our theoretical results are supported by numerical experiments, which confirm the competitive performance of \vrpda~compared to state-of-the-art.
Abstract（参考訳）: 我々は、サポートベクターマシンと最小絶対偏差を含む、機械学習アプリケーションで広く現れる構造化された非平滑凸有限和最適化を研究します。この問題の原始的双対定式化のために、プリマル双対加速双対平均化 (\vrpda)} による \emph{Variance Reduction と呼ばれる新しいアルゴリズムを提案する。 nonsmooth と general convex の設定では、\vrpda~ は全複雑性 $o(nd\log\min \{1/\epsilon, n\} + d/\epsilon )$ を持ち、ここでは$n$ はサンプル数、$d$ は原始変数の次元、$\epsilon$ は所望の精度を表す。非滑らかかつ強凸設定において、 \vrpda~ の全体的な複雑性は、主双対ギャップと反復と最適解の間の距離の両方の観点から $O(nd\log\min\{1/\epsilon, n\} + d/\sqrt{\epsilon})$ となる。これらの結果はいずれも、非スムースおよび一般凸集合に対して$o(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\epsilon)$、より単純かつ強い凸設定に対して$o(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\sqrt{\epsilon})$である。さらに、両方の複素性は、我々が考える特定の(共通な)構造を持たない一般凸有限和に対する \emph{lower} 境界よりも優れている。我々の理論結果は数値実験によって支持され、最新技術と比較された \vrpda の競合性能を確認した。

関連論文リスト

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)
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)
The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文参考訳（メタデータ） (2023-11-09T14:29:25Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文参考訳（メタデータ） (2023-06-30T20:36:44Z)
Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文参考訳（メタデータ） (2023-02-13T00:22:28Z)
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文参考訳（メタデータ） (2023-01-10T20:43:29Z)
Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。 Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文参考訳（メタデータ） (2022-01-19T05:56:19Z)
The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
論文参考訳（メタデータ） (2021-03-29T18:53:57Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)

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

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