論文の概要: On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions
- arxiv url: http://arxiv.org/abs/2002.03273v1
- Date: Sun, 9 Feb 2020 03:39:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 14:25:34.702740
- Title: On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions
- Title（参考訳）: 個々の関数の指標を用いない凸有限和の最小化の複雑さについて
- Authors: Yossi Arjevani, Amit Daniely, Stefanie Jegelka, Hongzhou Lin
- Abstract要約: 有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
- 参考スコア（独自算出の注目度）: 62.01594253618911
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent advances in randomized incremental methods for minimizing $L$-smooth
$\mu$-strongly convex finite sums have culminated in tight complexity of
$\tilde{O}((n+\sqrt{n L/\mu})\log(1/\epsilon))$ and $O(n+\sqrt{nL/\epsilon})$,
where $\mu>0$ and $\mu=0$, respectively, and $n$ denotes the number of
individual functions. Unlike incremental methods, stochastic methods for finite
sums do not rely on an explicit knowledge of which individual function is being
addressed at each iteration, and as such, must perform at least $\Omega(n^2)$
iterations to obtain $O(1/n^2)$-optimal solutions. In this work, we exploit the
finite noise structure of finite sums to derive a matching $O(n^2)$-upper bound
under the global oracle model, showing that this lower bound is indeed tight.
Following a similar approach, we propose a novel adaptation of SVRG which is
both \emph{compatible with stochastic oracles}, and achieves complexity bounds
of $\tilde{O}((n^2+n\sqrt{L/\mu})\log(1/\epsilon))$ and
$O(n\sqrt{L/\epsilon})$, for $\mu>0$ and $\mu=0$, respectively. Our bounds hold
w.h.p. and match in part existing lower bounds of
$\tilde{\Omega}(n^2+\sqrt{nL/\mu}\log(1/\epsilon))$ and
$\tilde{\Omega}(n^2+\sqrt{nL/\epsilon})$, for $\mu>0$ and $\mu=0$,
respectively.
- Abstract（参考訳）: l$-smooth $\mu$-strongly convex 有限和を最小化するランダム化インクリメンタルメソッドの最近の進歩は、$\tilde{o}((n+\sqrt{n l/\mu})\log(1/\epsilon))$ と $o(n+\sqrt{nl/\epsilon})$ という厳密な複雑さに到達している。
増分法とは異なり、有限和に対する確率的手法は、各反復において個々の関数が取り組まれているという明示的な知識に頼らず、少なくとも$O(1/n^2)$-最適解を得るためには$Omega(n^2)$繰り返しを実行する必要がある。
この研究では、有限和の有限ノイズ構造を利用して、グローバルオラクルモデルの下で一致する$o(n^2)$-upperバウンドを導出し、この下限が本当にタイトであることを示す。
同様のアプローチで、SVRG の新規な適応法を提案し、それぞれ $\mu>0$ と $\mu=0$ に対して $\tilde{O}((n^2+n\sqrt{L/\mu})\log(1/\epsilon))$ と $O(n\sqrt{L/\epsilon})$ の複雑性境界を実現する。
我々の境界は w.h.p. を保持し、既存の下界の $\tilde{\Omega}(n^2+\sqrt{nL/\epsilon)$ と $\tilde{\Omega}(n^2+\sqrt{nL/\epsilon})$ をそれぞれ $\mu>0$ と $\mu=0$ で一致させる。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。
我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文 参考訳（メタデータ） (2024-05-25T08:34:49Z) - On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文 参考訳（メタデータ） (2024-02-04T17:14:53Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。
非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文 参考訳（メタデータ） (2021-05-04T21:49:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。