論文の概要: On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition
- arxiv url: http://arxiv.org/abs/2402.02569v1
- Date: Sun, 4 Feb 2024 17:14:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-06 18:47:55.979196
- Title: On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition
- Title（参考訳）: polyak-{\l}ojasiewicz条件下における有限サムスムース最適化の複雑さについて
- Authors: Yunyan Bai, Yuxing Liu, Luo Luo
- Abstract要約: 本稿では、$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である。
- 参考スコア（独自算出の注目度）: 14.781921087738967
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper considers the optimization problem of the form $\min_{{\bf
x}\in{\mathbb R}^d} f({\bf x})\triangleq \frac{1}{n}\sum_{i=1}^n f_i({\bf x})$,
where $f(\cdot)$ satisfies the Polyak--{\L}ojasiewicz (PL) condition with
parameter $\mu$ and $\{f_i(\cdot)\}_{i=1}^n$ is $L$-mean-squared smooth. We
show that any gradient method requires at least
$\Omega(n+\kappa\sqrt{n}\log(1/\epsilon))$ incremental first-order oracle (IFO)
calls to find an $\epsilon$-suboptimal solution, where $\kappa\triangleq L/\mu$
is the condition number of the problem. This result nearly matches upper bounds
of IFO complexity for best-known first-order methods. We also study the problem
of minimizing the PL function in the distributed setting such that the
individuals $f_1(\cdot),\dots,f_n(\cdot)$ are located on a connected network of
$n$ agents. We provide lower bounds of
$\Omega(\kappa/\sqrt{\gamma}\,\log(1/\epsilon))$,
$\Omega((\kappa+\tau\kappa/\sqrt{\gamma}\,)\log(1/\epsilon))$ and
$\Omega\big(n+\kappa\sqrt{n}\log(1/\epsilon)\big)$ for communication rounds,
time cost and local first-order oracle calls respectively, where
$\gamma\in(0,1]$ is the spectral gap of the mixing matrix associated with the
network and~$\tau>0$ is the time cost of per communication round. Furthermore,
we propose a decentralized first-order method that nearly matches above lower
bounds in expectation.
- Abstract（参考訳）: 本稿では、パラメータ $\mu$ と $\{f_i(\cdot)\}_{i=1}^n f_i({\bf x})$ を持つ polyak--{\l}ojasiewicz (pl) 条件を満たす場合、$\min_{{\bf x}\in{\mathbb r}^d} f({\bf x})\triangleq \frac{1}{n}\sum_{i=1}^n f_i({\bf x})$ という形式の最適化問題を考える。
任意の勾配法において少なくとも$\omega(n+\kappa\sqrt{n}\log(1/\epsilon))$インクリメンタルファーストオーダーオラクル(ifo)は$\epsilon$-サブオプティマソリューションを見つけるために、$\kappa\triangleq l/\mu$ を問題の条件数とする。
この結果は、最もよく知られた一階法におけるIFO複雑性の上限にほぼ一致する。
また、分散環境でのPL関数の最小化の問題についても検討し、$f_1(\cdot),\dots,f_n(\cdot)$が$n$エージェントの接続ネットワーク上に置かれるようにした。
通信ラウンドは$\Omega(\kappa/\sqrt{\gamma}\,\log(1/\epsilon))$, $\Omega((\kappa+\tau\kappa/\sqrt{\gamma}\,)\log(1/\epsilon))$ and $\Omega\big(n+\kappa\sqrt{n}\log(1/\epsilon)\big)$ 通信ラウンド、時間コスト、局所一階オラクルコールの場合、$\gamma\in(0,1]$はネットワークに関連する混合行列のスペクトルギャップであり、$$$\tau>0は通信ラウンド当たりのコストである。
さらに,予測値よりも低い値にほぼ一致する分散一階法を提案する。
関連論文リスト
- 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) - 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) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳（メタデータ） (2022-02-01T16:06:20Z) - Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced
Convex-Concave Minimax Optimization [41.432757205864796]
本稿では,$min_bf xmax_yf(bfbf y)という形の凸-凸最小値問題の1次アルゴリズムを同時に検討する。
我々の手法は、より一般的な不均衡なミニマックス問題を解くために使用することができ、また、ほぼ最適である。
論文 参考訳（メタデータ） (2021-06-03T11:30:32Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。