論文の概要: Quasi-Newton Methods for Saddle Point Problems
- arxiv url: http://arxiv.org/abs/2111.02708v1
- Date: Thu, 4 Nov 2021 09:34:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-05 20:25:56.718173
- Title: Quasi-Newton Methods for Saddle Point Problems
- Title（参考訳）: サドルポイント問題に対する準ニュートン法
- Authors: Chengchang Liu, Luo Luo
- Abstract要約: 我々は,不定値超線型Obig-frac1nkappa2bigに対して,Greedy Broydenファミリー更新法を提案する。
また,BFG型SR1型で局所収束速度が速いブロイデン系アルゴリズムを2種類提案する。
- 参考スコア（独自算出の注目度）: 15.11757597288305
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies quasi-Newton methods for solving
strongly-convex-strongly-concave saddle point problems (SPP). We propose a
variant of general greedy Broyden family update for SPP, which has explicit
local superlinear convergence rate of ${\mathcal
O}\big(\big(1-\frac{1}{n\kappa^2}\big)^{k(k-1)/2}\big)$, where $n$ is
dimensions of the problem, $\kappa$ is the condition number and $k$ is the
number of iterations. The design and analysis of proposed algorithm are based
on estimating the square of indefinite Hessian matrix, which is different from
classical quasi-Newton methods in convex optimization. We also present two
specific Broyden family algorithms with BFGS-type and SR1-type updates, which
enjoy the faster local convergence rate of $\mathcal
O\big(\big(1-\frac{1}{n}\big)^{k(k-1)/2}\big)$.
- Abstract（参考訳）: 本稿では, 強凸強凸サドルポイント問題(spp)を解くための準ニュートン法について述べる。
そこで我々は,spp に対する greedy broyden family update の変種を提案する。これは,${\mathcal o}\big(\big(1-\frac{1}{n\kappa^2}\big)^{k(k-1)/2}\big)$,$n$ が問題の次元であり,$\kappa$ が条件数であり、$k$ が反復数であるような局所超線形収束率を持つ。
提案アルゴリズムの設計と解析は、凸最適化における古典的な準ニュートン法とは異なる不定値ヘッセン行列の二乗推定に基づいている。
また、BFGS型とSR1型のアップデートを持つブロイデン族アルゴリズムを2種類提案し、より高速な局所収束速度を$\mathcal O\big(\big(1-\frac{1}{n}\big)^{k(k-1)/2}\big)$とする。
関連論文リスト
- Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - Differentially Private Algorithms for the Stochastic Saddle Point
Problem with Optimal Rates for the Strong Gap [12.446156563700482]
凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。
また、安定性と精度の間には根本的なトレードオフがあることも示している。
論文 参考訳（メタデータ） (2023-02-24T21:50:02Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - 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) - 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) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳（メタデータ） (2022-02-01T16:06:20Z) - Regularized Newton Method with Global $O(1/k^2)$ Convergence [10.685862129925729]
目的が強く凸している場合,本手法は超直線的に収束することを示す。
我々の手法はニュートン法の最初の変種であり、安価な反復と証明可能な高速な大域収束の両方を持つ。
論文 参考訳（メタデータ） (2021-12-03T18:55:50Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。