論文の概要: Two trust region type algorithms for solving nonconvex-strongly concave
minimax problems
- arxiv url: http://arxiv.org/abs/2402.09807v1
- Date: Thu, 15 Feb 2024 09:13:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-16 16:15:55.639915
- Title: Two trust region type algorithms for solving nonconvex-strongly concave
minimax problems
- Title(参考訳): 非凸凸凸最小値問題の2つの信頼領域型アルゴリズム
- Authors: Tongliang Yao and Zi Xu
- Abstract要約: 我々は,ミニマックストラスト領域 (MINIMAX-TR) アルゴリズムと,非強いミニマックス問題を解くための契約アルゴリズムを提案する。
どちらのアルゴリズムも、よく知られた$epsilon$epsilon-1.5の繰り返しを見つけることができる。
- 参考スコア(独自算出の注目度): 0.5801621787540265
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a Minimax Trust Region (MINIMAX-TR) algorithm and a
Minimax Trust Region Algorithm with Contractions and Expansions(MINIMAX-TRACE)
algorithm for solving nonconvex-strongly concave minimax problems. Both
algorithms can find an $(\epsilon, \sqrt{\epsilon})$-second order stationary
point(SSP) within $\mathcal{O}(\epsilon^{-1.5})$ iterations, which matches the
best well known iteration complexity.
- Abstract(参考訳): 本稿では, ミニマックス・トラスト領域法(MINIMAX-TR) アルゴリズムと, 契約・拡張を伴うミニマックス・トラスト領域法(MINIMAX-TRACE) アルゴリズムを提案する。
どちらのアルゴリズムも $(\epsilon, \sqrt{\epsilon})$-second order stationary point(SSP) を $\mathcal{O}(\epsilon^{-1.5})$ iterations 内で見つけることができる。
関連論文リスト
- Extending the Reach of First-Order Algorithms for Nonconvex Min-Max
Problems with Cohypomonotonicity [20.710343135282123]
我々は$fracKMLotonicity が弱MVrhon$coords または弱MVrhonLotonicity または弱MVrhonKML$ を保証することを予想する。
また、同じ範囲の$$の場合には、アルゴリズムや複雑性の保証も提供します。
論文 参考訳(メタデータ) (2024-02-07T18:22:41Z) - Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for
Nonconvex Minimax Problems with Coupled linear Constraints [3.898056433020865]
線形制約付きミニマックス問題に対する2つのゼロ階正則複雑性アルゴリズムを提案する。
我々の知る限りでは、彼らは最初の2つのゼロオーダーのアルゴリズムであり、非局所的な複雑さに最適である。
論文 参考訳(メタデータ) (2024-01-26T11:22:13Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳(メタデータ) (2023-02-08T01:42:45Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳(メタデータ) (2023-01-11T09:12:28Z) - Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth
Nonconvex Minimax Problems with Coupled Linear Constraints [5.142024994067472]
近年,機械学習や信号処理の分野では,非数学的ミニマックス問題に注目が集まっている。
線形制約を用いた非ミニマックス点数問題の解法として,複雑性保証付き2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-12-09T05:32:30Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳(メタデータ) (2021-08-01T15:23:49Z) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳(メタデータ) (2020-02-20T17:52:18Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳(メタデータ) (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。