論文の概要: Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization
- arxiv url: http://arxiv.org/abs/2201.07427v1
- Date: Wed, 19 Jan 2022 05:56:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-20 14:01:46.055939
- Title: Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization
- Title（参考訳）: 双線形結合スムース最小最適化のためのリフテッドプリマル双対法
- Authors: Kiran Koshy Thekumparampil, Niao He, Sewoong Oh
- Abstract要約: 双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
- 参考スコア（独自算出の注目度）: 47.27237492375659
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the bilinearly coupled minimax problem: $\min_{x} \max_{y} f(x) +
y^\top A x - h(y)$, where $f$ and $h$ are both strongly convex smooth functions
and admit first-order gradient oracles. Surprisingly, no known first-order
algorithms have hitherto achieved the lower complexity bound of
$\Omega((\sqrt{\frac{L_x}{\mu_x}} + \frac{\|A\|}{\sqrt{\mu_x \mu_y}} +
\sqrt{\frac{L_y}{\mu_y}}) \log(\frac1{\varepsilon}))$ for solving this problem
up to an $\varepsilon$ primal-dual gap in the general parameter regime, where
$L_x, L_y,\mu_x,\mu_y$ are the corresponding smoothness and strongly convexity
constants.
We close this gap by devising the first optimal algorithm, the Lifted
Primal-Dual (LPD) method. Our method lifts the objective into an extended form
that allows both the smooth terms and the bilinear term to be handled optimally
and seamlessly with the same primal-dual framework. Besides optimality, our
method yields a desirably simple single-loop algorithm that uses only one
gradient oracle call per iteration. Moreover, when $f$ is just convex, the same
algorithm applied to a smoothed objective achieves the nearly optimal iteration
complexity. We also provide a direct single-loop algorithm, using the LPD
method, that achieves the iteration complexity of
$O(\sqrt{\frac{L_x}{\varepsilon}} + \frac{\|A\|}{\sqrt{\mu_y \varepsilon}} +
\sqrt{\frac{L_y}{\varepsilon}})$. Numerical experiments on quadratic minimax
problems and policy evaluation problems further demonstrate the fast
convergence of our algorithm in practice.
- Abstract（参考訳）: 双線型結合ミニマックス問題:$\min_{x} \max_{y} f について検討する。
(x) + y^\top A x - h
(y)$ の場合、$f$ と $h$ は共に強い凸滑らかな函数であり、一階勾配オラクルを許容する。
驚くべきことに、既知の一階法アルゴリズムでは、この問題を解決するために$\omega((\sqrt{\frac{l_x}{\mu_x}} + \frac{\|a\|}{\sqrt{\mu_x \mu_y}} + \sqrt{\frac{l_y}{\mu_y}}) \log(\frac1{\varepsilon})) $\varepsilon$primal-dual gap という一般パラメータ系において、$l_x, l_y,\mu_x,\mu_y$ は対応する滑らか性と強い凸定数である。
最初の最適化アルゴリズムであるLifted Primal-Dual (LPD) を考案することで、このギャップを埋める。
提案手法は目的を拡張形式に引き上げ,スムーズな項と双線形項の両方を同じ原始双対の枠組みで最適かつシームレスに扱えるようにした。
最適性に加えて、この手法は1イテレーションあたりの勾配oracle呼び出しのみを使用する、望ましくは単純なシングルループアルゴリズムをもたらす。
さらに、$f$ がちょうど凸であるとき、滑らかな目的に適用される同じアルゴリズムは、ほぼ最適な反復複雑性を達成する。
また、LPD法を用いて直接単ループアルゴリズムを提供し、$O(\sqrt {\frac{L_x}{\varepsilon}} + \frac{\|A\|}{\sqrt{\mu_y \varepsilon}} + \sqrt{\frac{L_y}{\varepsilon}})$の反復複雑性を実現する。
二次ミニマックス問題と政策評価問題に関する数値実験により,本アルゴリズムの高速化が実証された。
関連論文リスト
- A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
我々は、$f(hat x)$ ができるだけ小さいような点 $hat xin barmathcal X$ を返すアルゴリズムを構築している。
この方法は、$f(hat x) - min_xin barmathcal X f(x)$ が、多対数項まで$d2/sqrtn$ より小さい順序であることを証明する。
論文 参考訳（メタデータ） (2024-06-26T18:19:10Z) - A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳（メタデータ） (2023-11-17T22:07:18Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。