論文の概要: Zeroth-Order Algorithms for Smooth Saddle-Point Problems
- arxiv url: http://arxiv.org/abs/2009.09908v2
- Date: Sat, 27 Feb 2021 19:13:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-16 05:44:27.844807
- Title: Zeroth-Order Algorithms for Smooth Saddle-Point Problems
- Title（参考訳）: Smooth Saddle-Point問題に対するゼロ次アルゴリズム
- Authors: Abdurakhmon Sadiev, Aleksandr Beznosikov, Pavel Dvurechensky,
Alexander Gasnikov
- Abstract要約: ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。
解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。
また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
- 参考スコア（独自算出の注目度）: 117.44028458220427
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Saddle-point problems have recently gained increased attention from the
machine learning community, mainly due to applications in training Generative
Adversarial Networks using stochastic gradients. At the same time, in some
applications only a zeroth-order oracle is available. In this paper, we propose
several algorithms to solve stochastic smooth (strongly) convex-concave
saddle-point problems using zeroth-order oracles and estimate their convergence
rate and its dependence on the dimension $n$ of the variable. In particular,
our analysis shows that in the case when the feasible set is a direct product
of two simplices, our convergence rate for the stochastic term is only by a
$\log n$ factor worse than for the first-order methods. We also consider a
mixed setup and develop 1/2th-order methods that use zeroth-order oracle for
the minimization part and first-order oracle for the maximization part.
Finally, we demonstrate the practical performance of our zeroth-order and
1/2th-order methods on practical problems.
- Abstract（参考訳）: サドルポイント問題は最近、確率的勾配を用いた生成的逆ネットワークの訓練への応用により、機械学習コミュニティから注目を集めている。
同時に、一部のアプリケーションでは、ゼロオーダーのoracleしか利用できない。
本稿では,ゼロ次オラクルを用いた確率的滑らか(強く)凸凸サドルポイント問題を解くアルゴリズムを提案し,その収束率とその変数の次元$n$依存性を推定する。
特に、我々の分析は、実現可能な集合が2つの単純集合の直積である場合、確率項の収束率は、一階法よりも悪い$\log n$因子によってのみ存在することを示している。
我々はまた,最小化部分ではゼロ次oracle,最大化部分ではファースト次oracleを使用する,混合セットアップと1/2次メソッドの開発も検討する。
最後に,実問題に対するゼロ次および1/2次法の実践的性能を示す。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully
First-Order Oracles [14.697733592222658]
1次法は2次法として最適に近い$tilde MathcalO(epsilon-2)$レートで収束可能であることを示す。
さらに,2次定常点を求めるために,類似の収束率を求める単純な1次アルゴリズムを導出する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without
Gradients [22.153544816232042]
関数評価のみにアクセス可能な非局所問題のサドル点の回避を検討する。
ゼロ階負曲率探索フレームワークを2つ提案する。
論文 参考訳（メタデータ） (2022-10-04T10:01:16Z) - A Projection-free Algorithm for Constrained Stochastic Multi-level
Composition Optimization [12.096252285460814]
合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。
提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
論文 参考訳（メタデータ） (2022-02-09T06:05:38Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-12T16:44:27Z) - Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities [21.13934071954103]
本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。
SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。
結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
論文 参考訳（メタデータ） (2020-01-22T00:05:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。