論文の概要: Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold
- arxiv url: http://arxiv.org/abs/2303.09261v1
- Date: Thu, 16 Mar 2023 12:25:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-17 15:40:18.705860
- Title: Orthogonal Directions Constrained Gradient Method: from non-linear
equality constraints to Stiefel manifold
- Title（参考訳）: 直交方向制約付き勾配法:非線形等式制約からスティフェル多様体へ
- Authors: Sholom Schechtman, Daniil Tiapkin, Michael Muehlebach, Eric Moulines
- Abstract要約: 直交方向制約法(ODCGM)という新しいアルゴリズムを提案する。
ODCGMはベクトル空間へのプロジェクションのみを必要とする。
以上より, ODCGMは, ほぼ最適のオラクル複合体を呈することを示した。
- 参考スコア（独自算出の注目度）: 16.099883128428054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of minimizing a non-convex function over a smooth
manifold $\mathcal{M}$. We propose a novel algorithm, the Orthogonal Directions
Constrained Gradient Method (ODCGM) which only requires computing a projection
onto a vector space. ODCGM is infeasible but the iterates are constantly pulled
towards the manifold, ensuring the convergence of ODCGM towards $\mathcal{M}$.
ODCGM is much simpler to implement than the classical methods which require the
computation of a retraction. Moreover, we show that ODCGM exhibits the
near-optimal oracle complexities $\mathcal{O}(1/\varepsilon^2)$ and
$\mathcal{O}(1/\varepsilon^4)$ in the deterministic and stochastic cases,
respectively. Furthermore, we establish that, under an appropriate choice of
the projection metric, our method recovers the landing algorithm of Ablin and
Peyr\'e (2022), a recently introduced algorithm for optimization over the
Stiefel manifold. As a result, we significantly extend the analysis of Ablin
and Peyr\'e (2022), establishing near-optimal rates both in deterministic and
stochastic frameworks. Finally, we perform numerical experiments which shows
the efficiency of ODCGM in a high-dimensional setting.
- Abstract（参考訳）: 滑らかな多様体 $\mathcal{M}$ 上の非凸函数を最小化する問題を考える。
本稿では,ベクトル空間への射影計算のみを必要とする新しいアルゴリズム,Orthogonal Directions Constrained Gradient Method (ODCGM)を提案する。
ODCGM は実現不可能であるが、イテレートは常に多様体へ向けられ、ODCGM の $\mathcal{M}$ への収束を保証する。
ODCGMは、リトラクションの計算を必要とする古典的な手法よりも実装がずっと簡単である。
さらに, odcgm は, 決定論的および確率的ケースでそれぞれ $\mathcal{o}(1/\varepsilon^2)$ と $\mathcal{o}(1/\varepsilon^4)$ をそれぞれ示している。
さらに,提案手法は射影距離の適切な選択の下で,最近導入されたスティーフェル多様体上の最適化アルゴリズムであるAblin and Peyr\'e (2022) の着地アルゴリズムを復元する。
その結果、Ablin と Peyr\e (2022) の分析を著しく拡張し、決定論と確率論の両方のフレームワークにおいて、ほぼ最適のレートを確立した。
最後に,ODCGMの高次元環境における効率を示す数値実験を行った。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Riemannian Bilevel Optimization [35.42472057648458]
特に,2次情報を回避することを目的とした,バッチおよび勾配に基づく手法に着目する。
本稿では,一階勾配情報を活用する手法である$mathrmRF2SA$を提案し,分析する。
様々な設定の下で、$epsilon$-stationary 点に達するための明示的な収束率を提供する。
論文 参考訳（メタデータ） (2024-05-22T20:49:01Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Low-complexity subspace-descent over symmetric positive definite
manifold [9.346050098365648]
対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。
提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
論文 参考訳（メタデータ） (2023-05-03T11:11:46Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳（メタデータ） (2021-07-01T06:43:11Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Block majorization-minimization with diminishing radius for constrained
nonconvex optimization [9.907540661545328]
BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。
凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
論文 参考訳（メタデータ） (2020-12-07T07:53:09Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。