論文の概要: Faster Stochastic Algorithms for Minimax Optimization under
Polyak--{\L}ojasiewicz Conditions
- arxiv url: http://arxiv.org/abs/2307.15868v1
- Date: Sat, 29 Jul 2023 02:26:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-01 19:06:58.126072
- Title: Faster Stochastic Algorithms for Minimax Optimization under
Polyak--{\L}ojasiewicz Conditions
- Title（参考訳）: polyak--{\l}ojasiewicz条件下でのミニマックス最適化のための高速確率アルゴリズム
- Authors: Lesi Chen, Boyuan Yao, Luo Luo
- Abstract要約: 我々は、$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 を見つけることができる。
- 参考スコア（独自算出の注目度）: 12.459354707528819
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers stochastic first-order algorithms for minimax
optimization under Polyak--{\L}ojasiewicz (PL) conditions. We propose
SPIDER-GDA for solving the finite-sum problem of the form $\min_x \max_y
f(x,y)\triangleq \frac{1}{n} \sum_{i=1}^n f_i(x,y)$, where the objective
function $f(x,y)$ is $\mu_x$-PL in $x$ and $\mu_y$-PL in $y$; and each
$f_i(x,y)$ is $L$-smooth. We prove SPIDER-GDA could find an $\epsilon$-optimal
solution within ${\mathcal O}\left((n + \sqrt{n}\,\kappa_x\kappa_y^2)\log
(1/\epsilon)\right)$ stochastic first-order oracle (SFO) complexity, which is
better than the state-of-the-art method whose SFO upper bound is ${\mathcal
O}\big((n + n^{2/3}\kappa_x\kappa_y^2)\log (1/\epsilon)\big)$, where
$\kappa_x\triangleq L/\mu_x$ and $\kappa_y\triangleq L/\mu_y$. For the
ill-conditioned case, we provide an accelerated algorithm to reduce the
computational cost further. It achieves $\tilde{{\mathcal
O}}\big((n+\sqrt{n}\,\kappa_x\kappa_y)\log^2 (1/\epsilon)\big)$ SFO upper bound
when $\kappa_y \gtrsim \sqrt{n}$. Our ideas also can be applied to the more
general setting that the objective function only satisfies PL condition for one
variable. Numerical experiments validate the superiority of proposed methods.
- Abstract（参考訳）: 本稿では,polyak--{\L}ojasiewicz (PL)条件下での最小最適化のための確率的一階アルゴリズムについて考察する。
目的関数 $f(x,y)$ は$x$ で$\mu_x$-pl、$y$で$\mu_y$-plであり、$f_i(x,y)$は$l$-smoothである。
spider-gda は${\mathcal o}\left((n + \sqrt{n}\,\kappa_x\kappa_y^2)\log (1/\epsilon)\right)$ stochastic first-order oracle (sfo) の複雑さより優れた${\mathcal o}\big(n + n^{2/3}\kappa_x\kappa_y^2)\log (1/\epsilon)\big)$、ここで $\kappa_x\triangleq l/\mu_x$ と $\kappa_y\triangleq l/\mu_x$ は${\mathcal o}\big(n + n^{2/3}\kappa_x\kappa_y^2)\log (1/\epsilon)\big)$である。
非条件の場合、計算コストをさらに削減するための高速化アルゴリズムを提供する。
これは$\tilde{{\mathcal O}}\big((n+\sqrt{n}\,\kappa_x\kappa_y)\log^2 (1/\epsilon)\big)$ SFO upper bound when $\kappa_y \gtrsim \sqrt{n}$である。
我々のアイデアは、目的関数が1つの変数のpl条件のみを満たすというより一般的な設定にも適用できる。
数値実験により提案手法の優位性を検証した。
関連論文リスト
- 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) - 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) - An Optimal Algorithm for Strongly Convex Min-min Optimization [79.11017157526815]
既存の最適な一階法には$mathcalO(sqrtmaxkappa_x,kappa_y log 1/epsilon)$nabla_x f(x,y)$と$nabla_y f(x,y)$の両方の計算が必要である。
我々は$mathcalO(sqrtkappa_x log 1/epsilon)$nabla_x f(x,
論文 参考訳（メタデータ） (2022-12-29T19:26:12Z) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-11T17:33:07Z) - 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) - Finding Second-Order Stationary Point for Nonconvex-Strongly-Concave
Minimax Problem [16.689304539024036]
本稿では,ミニマックス問題の2階定常点を求める非同相的挙動について考察する。
高次元問題に対して、降下とチェビシェフ展開による勾配の立方体部分確率を解く2階オラクルのコスト対費用について提案する。
論文 参考訳（メタデータ） (2021-10-10T14:54:23Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。