論文の概要: Uniform Convergence and Generalization for Nonconvex Stochastic Minimax Problems

• arxiv url: http://arxiv.org/abs/2205.14278v1
• Date: Sat, 28 May 2022 00:18:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-31 15:27:03.355165
• Title: Uniform Convergence and Generalization for Nonconvex Stochastic Minimax Problems
• Title（参考訳）: 非凸確率ミニマックス問題に対する一様収束と一般化
• Authors: Siqi Zhang, Yifan Hu, Liang Zhang, Niao He
• Abstract要約: まず,経験的ミニマックス問題と集団ミニマックス問題との統一収束性を確立する。 極小最適化のための近似定常点を求めるのに必要な勾配複素量について光を当てた。
• 参考スコア（独自算出の注目度）: 25.959387499926162
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the uniform convergence and generalization bounds for nonconvex-(strongly)-concave (NC-SC/NC-C) stochastic minimax optimization. We first establish the uniform convergence between the empirical minimax problem and the population minimax problem and show the $\tilde{\mathcal{O}}(d\kappa^2\epsilon^{-2})$ and $\tilde{\mathcal{O}}(d\epsilon^{-4})$ sample complexities respectively for the NC-SC and NC-C settings, where $d$ is the dimension number and $\kappa$ is the condition number. To the best of our knowledge, this is the first uniform convergence measured by the first-order stationarity in stochastic minimax optimization. Based on the uniform convergence, we shed light on the sample and gradient complexities required for finding an approximate stationary point for stochastic minimax optimization in the NC-SC and NC-C settings.
• Abstract（参考訳）: 本稿では,非凸(強)-凹(NC-SC/NC-C)確率最小値最適化のための一様収束および一般化境界について検討する。 まず, 経験的ミニマックス問題と人口ミニマックス問題の間の一様収束を定め, $\tilde{\mathcal{o}}(d\kappa^2\epsilon^{-2})$ と $\tilde{\mathcal{o}}(d\epsilon^{-4})$ をそれぞれ nc-sc と nc-c の設定で示し, $d$ を次元数, $\kappa$ を条件数とする。 我々の知る限り、これは確率的ミニマックス最適化における一階定常性によって測定される最初の一様収束である。 この一様収束に基づいて,nc-sc および nc-c における確率的ミニマックス最適化のための近似定常点を求めるのに必要なサンプルと勾配の複雑度について考察した。

関連論文リスト

• Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees [14.301500851291989]
  合成ミニマックス問題は、機械学習において存在するが、このクラスの問題の収束に関してのみ確立されている。 本稿では,ミニマックス損失を合成構造で最適化するミニマックス問題の形式的定義を提案する。
  論文  参考訳（メタデータ） (2024-08-22T16:00:31Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。 我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。 アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
  論文  参考訳（メタデータ） (2022-10-31T17:59:29Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems [71.60601421935844]
  多くの機械学習問題は、GAN(Generative Adversarial Networks)のようなミニマックス問題として定式化できる。 ミニマックス問題に対するトレーニング勾配法から例を包括的に一般化解析する。
  論文  参考訳（メタデータ） (2021-05-08T22:38:00Z)
• A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
  分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。 本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。 総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
  論文  参考訳（メタデータ） (2021-02-09T02:44:24Z)
• Escaping Saddle-Points Faster under Interpolation-like Conditions [19.9471360853892]
  過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。 本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。 次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
  論文  参考訳（メタデータ） (2020-09-28T02:15:18Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Stochastic Subspace Cubic Newton Method [14.624340432672172]
  本稿では,高次元凸関数$f$を最小化するランダム化二階最適化アルゴリズムを提案する。 ミニバッチサイズが変化するにつれて、SSCNのグローバル収束速度は座標降下速度(CD)と立方正規化ニュートン速度とを補間することを示した。 注目すべきことに、SSCN の局所収束速度は、次数関数 $frac12 (x-x*)top nabla2f(x*)(x-x*)$ の最小化問題に適用される部分空間降下率と一致する。
  論文  参考訳（メタデータ） (2020-02-21T19:42:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。