論文の概要: On Finite-Step Convergence of the Non-Greedy Algorithm for $L_1$-Norm
PCA and Beyond
- arxiv url: http://arxiv.org/abs/2302.07712v1
- Date: Wed, 15 Feb 2023 15:17:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 14:38:57.046303
- Title: On Finite-Step Convergence of the Non-Greedy Algorithm for $L_1$-Norm
PCA and Beyond
- Title（参考訳）: L_1$-Norm PCAにおける非グレーディアルゴリズムの有限ステップ収束について
- Authors: Yuning Yang
- Abstract要約: アルゴリズムが生成した反復点は、少なくとも$leftlceil fracFmaxtau rightrceil$ steps以降は変更されない。
同様の有限ステップ収束は、最近、あるフルランクの仮定の下で、 citewanglinear で提案された PAMe のわずかな修正のためにも確立されている。
- 参考スコア（独自算出の注目度）: 0.685316573653194
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The non-greedy algorithm for $L_1$-norm PCA proposed in \cite{nie2011robust}
is revisited and its convergence properties are studied. The algorithm is first
interpreted as a conditional subgradient or an alternating maximization method.
By treating it as a conditional subgradient, the iterative points generated by
the algorithm will not change 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, it is proved
that the objective value will not change after at most $\left\lceil
\frac{F^{\max}}{\tau_0} \right\rceil$ steps. The stopping point satisfies
certain optimality conditions.
Then, a variant algorithm with improved convergence properties is studied.
The iterative points generated by the algorithm will not change after at most
$\left\lceil \frac{2F^{\max}}{\tau} \right\rceil$ steps and the stopping point
also satisfies certain optimality conditions given a small enough $\tau$.
Similar finite-step convergence is also established for a slight modification
of the PAMe proposed in \cite{wang2021linear} very recently under a certain
full-rank assumption. Such an assumption can also be removed when the
projection dimension is one.
- Abstract（参考訳）: \cite{nie2011robust} で提案された $l_1$-norm pca の非欲なアルゴリズムを再検討し、その収束特性について検討する。
このアルゴリズムはまず条件付き部分勾配あるいは交互極大化法として解釈される。
条件付き準次数として扱うことによって、アルゴリズムによって生成される反復点は、あるフルランクの仮定の下で有限個のステップで変化しない。
アルゴリズムを交互最大化として扱うことにより、目的値は少なくとも$\left\lceil \frac{F^{\max}}{\tau_0} \right\rceil$ steps以降は変化しないことが証明される。
停止点は一定の最適条件を満たす。
次に,収束特性を改良した変種アルゴリズムについて検討した。
アルゴリズムが生成する反復点は、最大$\left\lceil \frac{2f^{\max}}{\tau} \right\rceil$ ステップの後には変化せず、停止点は十分小さい$\tau$ の与えられた特定の最適条件を満たす。
同様の有限ステップ収束は、最近、あるフルランクの仮定の下で \cite{wang2021linear} で提案された PAMe のわずかな修正のためにも確立されている。
このような仮定は、射影次元が 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。