論文の概要: Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization

• arxiv url: http://arxiv.org/abs/2207.09660v2
• Date: Mon, 30 Sep 2024 19:30:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-02 16:31:46.390395
• Title: Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
• Title（参考訳）: 一般化階数1行列センシングのための交代最小化:ランダム初期化からのシャープ予測
• Authors: Kabir Aladin Chandrasekher, Mengqi Lou, Ashwin Pananjady,
• Abstract要約: ランクランダム行列の特性をdで推定する手法を示す。 鋭い収束は、単一のステップで正確な回復を保証する。 我々の分析は、この問題の他のいくつかの特性も明らかにしている。
• 参考スコア（独自算出の注目度）: 5.900674344455754
• License:
• Abstract: We consider the problem of estimating the factors of a rank-$1$ matrix with i.i.d. Gaussian, rank-$1$ measurements that are nonlinearly transformed and corrupted by noise. Considering two prototypical choices for the nonlinearity, we study the convergence properties of a natural alternating update rule for this nonconvex optimization problem starting from a random initialization. We show sharp convergence guarantees for a sample-split version of the algorithm by deriving a deterministic recursion that is accurate even in high-dimensional problems. Notably, while the infinite-sample population update is uninformative and suggests exact recovery in a single step, the algorithm -- and our deterministic prediction -- converges geometrically fast from a random initialization. Our sharp, non-asymptotic analysis also exposes several other fine-grained properties of this problem, including how the nonlinearity and noise level affect convergence behavior. On a technical level, our results are enabled by showing that the empirical error recursion can be predicted by our deterministic sequence within fluctuations of the order $n^{-1/2}$ when each iteration is run with $n$ observations. Our technique leverages leave-one-out tools originating in the literature on high-dimensional $M$-estimation and provides an avenue for sharply analyzing higher-order iterative algorithms from a random initialization in other high-dimensional optimization problems with random data.
• Abstract（参考訳）: 我々は、ノイズによって非線形に変換され破壊されるランク=1$行列、すなわちランク=1$の測定値を用いてランク=1$行列の因子を推定する問題を考察する。 非線形性に対する2つの原型的選択を考えると、ランダム初期化から始まるこの非凸最適化問題に対する自然な交互更新則の収束特性について検討する。 我々は,高次元問題においても精度の高い決定論的再帰を導出することにより,アルゴリズムの標本分割版に対する鋭い収束保証を示す。 特に、無限サンプルの集団更新は非形式的で、単一のステップで正確なリカバリを示唆する一方で、アルゴリズムと決定論的予測は、ランダムな初期化から幾何的に速く収束する。 我々の鋭く非漸近解析は、非線形性とノイズレベルが収束挙動にどのように影響するかなど、この問題の他の細かな性質も明らかにしている。 技術的レベルでは、各反復が$n$の観測で実行されるときのオーダー$n^{-1/2}$のゆらぎの中で、経験的誤差再帰を決定論的シーケンスで予測できることが示される。 提案手法は,高次元の$M$-estimationに関する文献から得られたLeft-one-outツールを活用し,ランダムな初期化から高階の反復アルゴリズムを高速に解析する手段を提供する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing [6.446062819763263]
  ノイズにより劣化したランク1ガウス測度から未知のランク1行列を復元する問題を分析する。 我々は,この手法の正確な誤差を予測する決定論的再帰を導出する。 非漸近的なフレームワークを使用することで、これはどんなバッチサイズでも、幅広いステップサイズにも当てはまります。
  論文  参考訳（メタデータ） (2024-02-02T17:55:12Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing [9.264464791978362]
  Alternating Least Squares (ALS) は $O(log n + log (1/varepsilon)) $ iterations において $varepsilon$-accuracy で真の解に収束することを示す。 我々の証明の鍵となるのは、ALSの軌道が反復する観察は、ランダムな測定行列の特定のエントリのみに非常に軽度に依存することである。
  論文  参考訳（メタデータ） (2022-04-25T08:55:38Z)
• Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance [17.199063087458907]
  我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。 このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。 我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
  論文  参考訳（メタデータ） (2022-02-23T17:08:40Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  回帰モデルのクラスに対する反復アルゴリズムの収束を解析するための一般的なレシピを開発する。 決定論的には、有限サンプル状態におけるアルゴリズムの収束率と最終的なエラーフロアの両方を正確にキャプチャする。 我々は、更新の交互化に基づく高次アルゴリズムと、下位次数に基づく一次アルゴリズムの両方に対して、鋭い収束率を示す。
  論文  参考訳（メタデータ） (2021-09-20T21:48:19Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  このモデルに基づく最小二乗リスクに対する1パス, 固定段差勾配勾配の収束度を解析した。 特殊な場合として、ランダムなサンプリング点における値のノイズのない観測から単位区間上の実関数を推定するオンラインアルゴリズムを解析する。
  論文  参考訳（メタデータ） (2020-06-15T08:25:50Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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