論文の概要: An Optimal Algorithm for Strongly Convex Min-min Optimization
- arxiv url: http://arxiv.org/abs/2212.14439v1
- Date: Thu, 29 Dec 2022 19:26:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 17:44:24.589210
- Title: An Optimal Algorithm for Strongly Convex Min-min Optimization
- Title（参考訳）: 強い凸ミンミン最適化のための最適アルゴリズム
- Authors: Dmitry Kovalev, Alexander Gasnikov, Grigory Malinovsky
- Abstract要約: 既存の最適な一階法には$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,
- 参考スコア（独自算出の注目度）: 79.11017157526815
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we study the smooth strongly convex minimization problem
$\min_{x}\min_y f(x,y)$. The existing optimal first-order methods require
$\mathcal{O}(\sqrt{\max\{\kappa_x,\kappa_y\}} \log 1/\epsilon)$ of computations
of both $\nabla_x f(x,y)$ and $\nabla_y f(x,y)$, where $\kappa_x$ and
$\kappa_y$ are condition numbers with respect to variable blocks $x$ and $y$.
We propose a new algorithm that only requires $\mathcal{O}(\sqrt{\kappa_x} \log
1/\epsilon)$ of computations of $\nabla_x f(x,y)$ and
$\mathcal{O}(\sqrt{\kappa_y} \log 1/\epsilon)$ computations of $\nabla_y
f(x,y)$. In some applications $\kappa_x \gg \kappa_y$, and computation of
$\nabla_y f(x,y)$ is significantly cheaper than computation of $\nabla_x
f(x,y)$. In this case, our algorithm substantially outperforms the existing
state-of-the-art methods.
- Abstract（参考訳）: 本稿では,滑らかな凸最小化問題 $\min_{x}\min_y f(x,y)$ について検討する。
既存の最適一階法では、$\mathcal{o}(\sqrt{\max\{\kappa_x,\kappa_y\}} \log 1/\epsilon)$が$\nabla_x f(x,y)$と$\nabla_y f(x,y)$であり、ここで$\kappa_x$と$\kappa_y$は変数ブロックに対して条件数である$x$と$y$である。
我々は$\mathcal{O}(\sqrt{\kappa_x} \log 1/\epsilon)$の計算量$\nabla_x f(x,y)$と$\mathcal{O}(\sqrt{\kappa_y} \log 1/\epsilon)$の計算量$\nabla_y f(x,y)$の新しいアルゴリズムを提案する。
一部のアプリケーションでは、$\kappa_x \gg \kappa_y$と$\nabla_y f(x,y)$の計算は$\nabla_x f(x,y)$の計算よりもはるかに安価である。
この場合,本アルゴリズムは既存の最先端手法を実質的に上回っている。
関連論文リスト
- Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - 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) - Sharper Rates for Separable Minimax and Finite Sum Optimization via
Primal-Dual Extragradient Methods [39.87865197769047]
分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
論文 参考訳（メタデータ） (2022-02-09T18:57:47Z) - 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) - 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) - 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) - Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
本論文では,まず,対数因子の設計に適合した $tildeO(sqrtkappa_mathbf xkappa_mathbf)$ を提示する。
また、これらの設定における既存のメソッドを、複雑さの観点からマッチングまたは上回るアルゴリズムも提示する。
論文 参考訳（メタデータ） (2020-02-05T16:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。