論文の概要: On Finite-Step Convergence of the Non-Greedy Algorithm and Proximal Alternating Minimization Method with Extrapolation for $L_1$-Norm PCA

• arxiv url: http://arxiv.org/abs/2302.07712v3
• Date: Wed, 22 Mar 2023 09:57:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-23 23:55:17.575524
• Title: On Finite-Step Convergence of the Non-Greedy Algorithm and Proximal Alternating Minimization Method with Extrapolation for $L_1$-Norm PCA
• Title（参考訳）: l_1$-norm pcaの補間を伴う非欲アルゴリズムと近位交互最小化法の有限ステップ収束について
• Authors: Yuning Yang
• Abstract要約: The non-dygree (NGA) and the recently proposed proximal alternating method with PCA (PAMe) for $L_1-norm。 修正アルゴリズムによって生成された反復点は、少なくとも$leftlceilfracFmaxtau rightrceil$ steps以降は変化しない。 PAMe の場合、符号変数は有限個のステップの後に一定であり、アルゴリズムは一定の最適条件を満たすことができる。
• 参考スコア（独自算出の注目度）: 0.685316573653194
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical non-greedy algorithm (NGA) and the recently proposed proximal alternating minimization method with extrapolation (PAMe) for $L_1$-norm PCA are revisited and their finite-step convergence are studied. It is first shown that NGA can be interpreted as a conditional subgradient or an alternating maximization method. By recognizing it as a conditional subgradient, we prove that the iterative points generated by the algorithm will be constant in finitely many steps under a certain full-rank assumption; such an assumption can be removed when the projection dimension is one. By treating the algorithm as an alternating maximization, we then prove that the objective value will be fixed after at most $\left\lceil\frac{F^{\max}}{\tau_0} \right\rceil$ steps, where the stopping point satisfies certain optimality conditions. Then, a slight modification of NGA with improved convergence properties is analyzed. It is shown that the iterative points generated by the modified algorithm will not change after at most $\left\lceil\frac{2F^{\max}}{\tau} \right\rceil$ steps; furthermore, the stopping point satisfies certain optimality conditions if the proximal parameter $\tau$ is small enough. For PAMe, it is proved that the sign variable will remain constant after finitely many steps and the algorithm can output a point satisfying certain optimality condition, if the parameters are small enough and a full rank assumption is satisfied. Moreover, if there is no proximal term on the projection matrix related subproblem, then the iterative points generated by this modified algorithm will not change after at most $\left\lceil \frac{4F^{\max}}{\tau(1-\gamma)} \right\rceil$ steps and the stopping point also satisfies certain optimality conditions, provided similar assumptions as those for PAMe. The full rank assumption can be removed when the projection dimension is one.
• Abstract（参考訳）: 古典的非利他的アルゴリズム(nga)と最近提案された補間付き近交互最小化法(pame)を再び検討し,その有限ステップ収束について検討した。 まず, NGA を条件付き次亜次法あるいは交互最大化法と解釈できることを示した。 これを条件次数として認識することにより、あるフルランクの仮定の下でアルゴリズムによって生成される反復点が有限個のステップで一定となることを証明し、射影次元が 1 であるときにそのような仮定を除去することができる。 アルゴリズムを交互に最大化として扱うことにより、目的値が少なくとも$\left\lceil\frac{F^{\max}}{\tau_0} \right\rceil$ stepsの後に固定されることが証明される。 そして, 収束特性が向上したNGAの微修正を解析した。 修正アルゴリズムによって生成された反復点は、最大$\left\lceil\frac{2f^{\max}}{\tau} \right\rceil$ ステップの後には変化しないことが示された。 pameの場合、符号変数は有限個のステップの後に定数であり、アルゴリズムはパラメータが十分小さくフルランクの仮定を満たす場合、一定の最適条件を満たす点を出力することができることが証明される。 さらに、プロジェクション行列関連の部分プロブレムに近項が存在しない場合、この修正アルゴリズムによって生成される反復点は、少なくとも$\left\lceil \frac{4F^{\max}}{\tau(1-\gamma)} \right\rceil$ steps 以降は変化せず、停止点も特定の最適条件を満たす。 射影次元が 1 の場合、全ランク仮定は取り除くことができる。

関連論文リスト

• On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation [13.813242559935732]
  両レベル最適化問題の1次解法について述べる。 特に,ペナルティ関数と超目的物との間に強い関連性を示す。 その結果,O(epsilon-3)$とO(epsilon-5)$が改良された。
  論文  参考訳（メタデータ） (2023-09-04T18:25:43Z)
• Variance reduction techniques for stochastic proximal point algorithms [5.374800961359305]
  そこで本研究では,近点アルゴリズムにおける分散低減手法の統一化研究を提案する。 我々は,SVRG,SAGA,およびそれらの変種の近位バージョンを提供するために特定可能な,汎用的近位アルゴリズムを提案する。 本実験は, 勾配法よりも近似分散還元法の利点を実証する。
  論文  参考訳（メタデータ） (2023-08-18T05:11:50Z)
• On the Linear Convergence of Policy Gradient under Hadamard Parameterization [4.182089296199263]
  本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。 すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
  論文  参考訳（メタデータ） (2023-05-31T05:51:15Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
  本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。 このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。 本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
  論文  参考訳（メタデータ） (2020-08-13T08:56:24Z)
• 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)

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

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