論文の概要: Gradient-Free Methods for Saddle-Point Problem
- arxiv url: http://arxiv.org/abs/2005.05913v4
- Date: Sun, 11 Sep 2022 14:38:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 19:53:19.338839
- Title: Gradient-Free Methods for Saddle-Point Problem
- Title（参考訳）: サドルポイント問題の勾配なし解法
- Authors: Aleksandr Beznosikov, Abdurakhmon Sadiev, Alexander Gasnikov
- Abstract要約: 我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
- 参考スコア（独自算出の注目度）: 125.99533416395765
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the paper, we generalize the approach Gasnikov et. al, 2017, which allows
to solve (stochastic) convex optimization problems with an inexact
gradient-free oracle, to the convex-concave saddle-point problem. The proposed
approach works, at least, like the best existing approaches. But for a special
set-up (simplex type constraints and closeness of Lipschitz constants in 1 and
2 norms) our approach reduces $\frac{n}{\log n}$ times the required number of
oracle calls (function calculations). Our method uses a stochastic
approximation of the gradient via finite differences. In this case, the
function must be specified not only on the optimization set itself, but in a
certain neighbourhood of it. In the second part of the paper, we analyze the
case when such an assumption cannot be made, we propose a general approach on
how to modernize the method to solve this problem, and also we apply this
approach to particular cases of some classical sets.
- Abstract（参考訳）: 本稿ではガスニコフらのアプローチを一般化する。
2017年、不正確な勾配のないオラクルで凸最適化問題を凸凹点問題に解けるようになった。
提案されたアプローチは,少なくとも既存の最善のアプローチと同じように動作する。
しかし、特別なセットアップ(1ノルムと2ノルムにおけるリプシッツ定数の複素型制約と閉性)に対して、我々のアプローチは要求されるオラクル呼び出しの数(関数計算)の2倍の$を下げる。
本手法は有限差分による勾配の確率近似を用いる。
この場合、関数は最適化セット自身に限らず、特定の近傍で指定されなければならない。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案し、また、いくつかの古典的集合の特定のケースに本手法を適用する。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。
この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
論文 参考訳（メタデータ） (2023-11-04T11:12:24Z) - Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。
有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
論文 参考訳（メタデータ） (2023-04-23T20:05:09Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳（メタデータ） (2020-10-22T22:54:54Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。