論文の概要: ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
- arxiv url: http://arxiv.org/abs/2103.11333v1
- Date: Sun, 21 Mar 2021 08:14:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 14:10:20.634344
- Title: ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
- Title（参考訳）: ANITA: 最適ループレス加速分散誘導勾配法
- Authors: Zhize Li
- Abstract要約: 有限和最適化のための新しい加速分散還元法ANITAを提案する。
一般凸設定では、ANITA は収束結果 $Obig(nminbig1+logfrac1epsilonsqrtn) を達成する。
強い凸設定では、ANITA が最適収束結果 $OBig(big(n+sqrtfracnLmubig)logfracnLmubig)$ matching the lower bound $ を達成することも示している。
- 参考スコア（独自算出の注目度）: 17.259824817932294
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel accelerated variance-reduced gradient method called ANITA
for finite-sum optimization. In this paper, we consider both general convex and
strongly convex settings. In the general convex setting, ANITA achieves the
convergence result $O\big(n\min\big\{1+\log\frac{1}{\epsilon\sqrt{n}},
\log\sqrt{n}\big\} + \sqrt{\frac{nL}{\epsilon}} \big)$, which improves the
previous best result $O\big(n\min\{\log\frac{1}{\epsilon}, \log
n\}+\sqrt{\frac{nL}{\epsilon}}\big)$ given by Varag (Lan et al., 2019). In
particular, for a very wide range of $\epsilon$, i.e., $\epsilon \in
(0,\frac{L}{n\log^2\sqrt{n}}]\cup [\frac{1}{\sqrt{n}},+\infty)$, where
$\epsilon$ is the error tolerance $f(x_T)-f^*\leq \epsilon$ and $n$ is the
number of data samples, ANITA can achieve the optimal convergence result
$O\big(n+\sqrt{\frac{nL}{\epsilon}}\big)$ matching the lower bound
$\Omega\big(n+\sqrt{\frac{nL}{\epsilon}}\big)$ provided by Woodworth and Srebro
(2016). To the best of our knowledge, ANITA is the \emph{first} accelerated
algorithm which can \emph{exactly} achieve this optimal result
$O\big(n+\sqrt{\frac{nL}{\epsilon}}\big)$ for general convex finite-sum
problems. In the strongly convex setting, we also show that ANITA can achieve
the optimal convergence result
$O\Big(\big(n+\sqrt{\frac{nL}{\mu}}\big)\log\frac{1}{\epsilon}\Big)$ matching
the lower bound
$\Omega\Big(\big(n+\sqrt{\frac{nL}{\mu}}\big)\log\frac{1}{\epsilon}\Big)$
provided by Lan and Zhou (2015). Moreover, ANITA enjoys a simpler loopless
algorithmic structure unlike previous accelerated algorithms such as Katyusha
(Allen-Zhu, 2017) and Varag (Lan et al., 2019) where they use an inconvenient
double-loop structure. Finally, the experimental results also show that ANITA
converges faster than previous state-of-the-art Varag (Lan et al., 2019),
validating our theoretical results and confirming the practical superiority of
ANITA.
- Abstract（参考訳）: 本稿では,有限サム最適化のための新しい高速化分散分散勾配法anitaを提案する。
本稿では,一般凸設定と強凸設定の両方を考える。
一般凸設定において、anita は、収束結果 $o\big(n\min\big\{1+\log\frac{1}{\epsilon\sqrt{n}}, \log\sqrt{n}\big\} + \sqrt{\frac{nl}{\epsilon}} \big)$ を達成し、これまでの最良の結果 $o\big(n\min\{\log\frac{1}{\epsilon}, \log n\}+\sqrt{\frac{nl}{\epsilon}}\big)$ をvarag (lan et al., 2019) によって与えられる。
特に、非常に広い範囲の$\epsilon$に対して、$\epsilon \in (0,\frac{L}{n\log^2\sqrt{n}}]\cup [\frac{1}{\sqrt{n}},+\infty)$, where $\epsilon$ is the error tolerance $f(x_T)-f^*\leq \epsilon$ and $n$ is the number of data sample, ANITA can achieve the optimal convergence result $O\big(n+\sqrt {\frac{nL}{\epsilon}}\big)$ matching the lower bound $\Omega\big(n+\sqrt {\frac{n}{\epsilon}}\big)$.
私たちの知る限りでは、anita は \emph{first} 加速アルゴリズムであり、一般凸有限和問題に対してこの最適結果 $o\big(n+\sqrt{\frac{nl}{\epsilon}}\big)$ を達成することができる。
強凸設定では、anita は lan と zhou (2015) によって提供された下限 $o\big(\big(n+\sqrt{\frac{nl}{\mu}}\big)\log\frac{1}{\epsilon}\big)$ を満たす最適収束結果 $o\big(\big(n+\sqrt{\frac{nl}{\mu}}\big)\log\frac{1}{\epsilon}\big)$ を実現できることを示した。
さらにanitaは、katyusha (allen-zhu, 2017)やvarag (lan et al., 2019)のような以前の高速化アルゴリズムとは異なり、ループレスなアルゴリズム構造を楽しんだ。
最後に,ANITAは従来のVarag(Lan et al., 2019)よりも早く収束し,理論的な結果が検証され,ANITAの実用的優位性が確認された。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Faster Stochastic Algorithms for Minimax Optimization under
Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。
SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
論文 参考訳（メタデータ） (2023-07-29T02:26:31Z) - Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function
Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。
我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。
我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
論文 参考訳（メタデータ） (2023-06-12T02:56:09Z) - Faster Rates of Convergence to Stationary Points in Differentially
Private Optimization [31.46358820048179]
リプシッツの定常点と滑らかな関数を$(varepsilon,delta)$-differential privacy(DP)で近似する問題について検討する。
点 $widehatw$ は関数 $mathbbRdrightarrowmathbbR$ if $|nabla F(widehatw)|leq alpha$ の $alpha$-stationary point と呼ばれる。
我々は$tildeObig(big[)を見つける新しい効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-06-02T02:43:44Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Acceleration for Compressed Gradient Descent in Distributed and
Federated Optimization [31.066505042748826]
本稿では,最初の加速圧縮勾配降下法(ACGD)を提案する。
ACGD は$OBig( (1+omega)sqrtfracLmulog frac1epsilonBig)$ for $mu$-strongly convex problem。
また、ACGD(ADIANA)の分散変種を提案し、収束率を$widetildeOBig(+sqrtfracLmu+sqrtbig)$とする。
論文 参考訳（メタデータ） (2020-02-26T09:03:23Z) - Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。
高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
論文 参考訳（メタデータ） (2020-02-24T08:07:08Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。