論文の概要: Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence
- arxiv url: http://arxiv.org/abs/2006.09361v3
- Date: Mon, 22 Mar 2021 17:09:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-20 20:21:52.031435
- Title: Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence
- Title（参考訳）: 勾配自由最小値最適化:可変化と高速収束
- Authors: Tengyu Xu, Zhe Wang, Yingbin Liang, H. Vincent Poor
- Abstract要約: 本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
- 参考スコア（独自算出の注目度）: 120.9336529957224
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many important machine learning applications amount to solving minimax
optimization problems, and in many cases there is no access to the gradient
information, but only the function values. In this paper, we focus on such a
gradient-free setting, and consider the nonconvex-strongly-concave minimax
stochastic optimization problem. In the literature, various zeroth-order (i.e.,
gradient-free) minimax methods have been proposed, but none of them achieve the
potentially feasible computational complexity of $\mathcal{O}(\epsilon^{-3})$
suggested by the stochastic nonconvex minimization theorem. In this paper, we
adopt the variance reduction technique to design a novel zeroth-order variance
reduced gradient descent ascent (ZO-VRGDA) algorithm. We show that the ZO-VRGDA
algorithm achieves the best known query complexity of $\mathcal{O}(\kappa(d_1 +
d_2)\epsilon^{-3})$, which outperforms all previous complexity bound by orders
of magnitude, where $d_1$ and $d_2$ denote the dimensions of the optimization
variables and $\kappa$ denotes the condition number. In particular, with a new
analysis technique that we develop, our result does not rely on a diminishing
or accuracy-dependent stepsize usually required in the existing methods. To our
best knowledge, this is the first study of zeroth-order minimax optimization
with variance reduction. Experimental results on the black-box distributional
robust optimization problem demonstrates the advantageous performance of our
new algorithm.
- Abstract（参考訳）: 多くの重要な機械学習アプリケーションは、最小限の最適化問題を解決するためであり、多くの場合、勾配情報へのアクセスはなく、関数値のみである。
本稿では,このような勾配のない設定に着目し,非凸強凹ミニマックス確率最適化問題を考える。
文献では、様々なゼロ次(つまり勾配なし)のミニマックス法が提案されているが、確率的非凸最小化定理によって示唆される$\mathcal{o}(\epsilon^{-3}) の計算複雑性は実現できない。
本稿では,新しいゼロ次分散還元勾配降下法(zo-vrgda)の設計に分散低減法を適用した。
ZO-VRGDAアルゴリズムは、$\mathcal{O}(\kappa(d_1 + d_2)\epsilon^{-3})$の既知のクエリ複雑性を達成し、$d_1$と$d_2$は最適化変数の次元を表し、$\kappa$は条件番号を表す。
特に,我々が開発する新たな分析手法では,既存の手法で通常必要とされる段階化や精度依存の段階化には依存しない。
我々の知る限り、これは分散還元を伴うゼロ階極小最適化の最初の研究である。
ブラックボックス分布型ロバスト最適化問題の実験結果から,本アルゴリズムの有利な性能を示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Accelerated Gradient Algorithms with Adaptive Subspace Search for
Instance-Faster Optimization [6.896308995955336]
グラディエントベースのミニマックス最適アルゴリズムは、継続的最適化と機械学習の開発を促進する。
本稿では,勾配に基づくアルゴリズムの設計と解析を行う新しい手法を機械学習に直接応用する。
論文 参考訳（メタデータ） (2023-12-06T01:16:10Z) - Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex
Minimax Machine Learning [12.069630105460766]
AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。
本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-22T04:33:27Z) - Derivative-free Alternating Projection Algorithms for General
Nonconvex-Concave Minimax Problems [9.173866646584031]
本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。
また,非コンケーブミニマックス問題に対処できることを示す。
論文 参考訳（メタデータ） (2021-08-01T15:23:49Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - On Riemannian Gradient-Based Methods for Minimax Problems [24.199289678553896]
ミニマックス問題を解くためのリーマン的手法のクラスを提案する。
我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。
また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
論文 参考訳（メタデータ） (2020-10-13T00:54:00Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。