論文の概要: Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded
Geometric Penalties
- arxiv url: http://arxiv.org/abs/2305.16186v2
- Date: Mon, 30 Oct 2023 08:18:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 02:31:55.156415
- Title: Accelerated Methods for Riemannian Min-Max Optimization Ensuring Bounded
Geometric Penalties
- Title(参考訳): 境界幾何学的罰則を保証するリーマン最小最適化の高速化法
- Authors: David Mart\'inez-Rubio, Christophe Roux, Christopher Criscitiello,
Sebastian Pokutta
- Abstract要約: 我々は$min_x max_y f(x, y) という形式で、$mathcalN$ は Hadamard である。
我々は、勾配収束定数を減少させることにより、グローバルな関心が加速されることを示す。
- 参考スコア(独自算出の注目度): 21.141544548229774
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work, we study optimization problems of the form $\min_x \max_y f(x,
y)$, where $f(x, y)$ is defined on a product Riemannian manifold $\mathcal{M}
\times \mathcal{N}$ and is $\mu_x$-strongly geodesically convex (g-convex) in
$x$ and $\mu_y$-strongly g-concave in $y$, for $\mu_x, \mu_y \geq 0$. We design
accelerated methods when $f$ is $(L_x, L_y, L_{xy})$-smooth and $\mathcal{M}$,
$\mathcal{N}$ are Hadamard. To that aim we introduce new g-convex optimization
results, of independent interest: we show global linear convergence for
metric-projected Riemannian gradient descent and improve existing accelerated
methods by reducing geometric constants. Additionally, we complete the analysis
of two previous works applying to the Riemannian min-max case by removing an
assumption about iterates staying in a pre-specified compact set.
- Abstract(参考訳): 本研究では, 積リーマン多様体上の $f(x, y)$ が定義されるような $\min_x \max_y f(x, y)$ という形式の最適化問題について検討し, $x$ と $\mu_y$-strongly geodesically convex (g-convex) が $y$,$\mu_x, \mu_y \geq 0$ に対して $\mu_x$-strongly g-concave in $y$ について検討する。
我々は、$f$が$(l_x, l_y, l_{xy})$-smoothと$\mathcal{m}$, $\mathcal{n}$がhadaardである場合、高速化メソッドを設計する。
そこで我々は, 計量計画付きリーマン勾配降下に対する大域的線形収束を示すとともに, 幾何学定数を減少させることにより, 既存の高速化手法を改善した。
さらに、リーマン min-max の場合に適用する2つの以前の研究を、あらかじめ特定されたコンパクト集合に留まる反復に関する仮定を除去して解析する。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳(メタデータ) (2024-08-21T20:14:54Z) - 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) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳(メタデータ) (2023-05-10T01:12:11Z) - 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) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$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次アルゴリズムは知られていない。
論文 参考訳(メタデータ) (2022-01-19T05:56:19Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳(メタデータ) (2021-10-28T14:19:30Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳(メタデータ) (2021-10-21T18:43:00Z) - Minimax Optimal Regression over Sobolev Spaces via Laplacian
Regularization on Neighborhood Graphs [25.597646488273558]
非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。
ラプラシアン滑らか化が多様体適応であることを証明する。
論文 参考訳(メタデータ) (2021-06-03T01:20:41Z) - Convergence Rate of the (1+1)-Evolution Strategy with Success-Based
Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
1+1)-進化戦略(ES)と成功に基づくステップサイズ適応を一般凸二次関数で解析する。
1+1)-ES の収束速度は、一般凸二次函数上で明示的に厳密に導かれる。
論文 参考訳(メタデータ) (2021-03-02T09:03:44Z) - Unconstrained optimisation on Riemannian manifolds [0.0]
本稿では, (Local-) Backtracking Gradient Descent と New Q-Newton の手法について記述する。
また、対称正方行列の最小固有値を計算するための明示的な計算を行う。
論文 参考訳(メタデータ) (2020-08-25T15:10:21Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳(メタデータ) (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。