論文の概要: Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation

• arxiv url: http://arxiv.org/abs/2505.10882v1
• Date: Fri, 16 May 2025 05:41:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-19 14:36:14.17708
• Title: Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation
• Title（参考訳）: 主固有ベクトル推定のための適応センシングの大域的収束
• Authors: Alex Saad-Falcon, Brighton Ancelin, Justin Romberg,
• Abstract要約: Ojaのような部分空間追跡アルゴリズムはより効率的な代替手段を提供するが、通常はフル次元の観測を必要とする。 我々は,この適応センシング手法が雑音の存在下でのグローバル収束を実現することを証明した。 結果は、フル次元サンプルの取得が困難またはコストがかかるアプリケーションに重要な意味を持つ。
• 参考スコア（独自算出の注目度）: 9.170594803531866
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper addresses the challenge of efficient principal component analysis (PCA) in high-dimensional spaces by analyzing a compressively sampled variant of Oja's algorithm with adaptive sensing. Traditional PCA methods incur substantial computational costs that scale poorly with data dimensionality, whereas subspace tracking algorithms like Oja's offer more efficient alternatives but typically require full-dimensional observations. We analyze a variant where, at each iteration, only two compressed measurements are taken: one in the direction of the current estimate and one in a random orthogonal direction. We prove that this adaptive sensing approach achieves global convergence in the presence of noise when tracking the leading eigenvector of a datastream with eigengap $\Delta=\lambda_1-\lambda_2$. Our theoretical analysis demonstrates that the algorithm experiences two phases: (1) a warmup phase requiring $O(\lambda_1\lambda_2d^2/\Delta^2)$ iterations to achieve a constant-level alignment with the true eigenvector, followed by (2) a local convergence phase where the sine alignment error decays at a rate of $O(\lambda_1\lambda_2d^2/\Delta^2 t)$ for iterations $t$. The guarantee aligns with existing minimax lower bounds with an added factor of $d$ due to the compressive sampling. This work provides the first convergence guarantees in adaptive sensing for subspace tracking with noise. Our proof technique is also considerably simpler than those in prior works. The results have important implications for applications where acquiring full-dimensional samples is challenging or costly.
• Abstract（参考訳）: 本稿では,Ojaアルゴリズムの圧縮サンプリング変種を適応センシングを用いて解析することにより,高次元空間における効率的な主成分分析(PCA)の課題に対処する。 従来のPCA手法はデータ次元のスケールが悪く、Ojaのような部分空間追跡アルゴリズムはより効率的な代替手段を提供するが、一般的にはフル次元の観測を必要とする。 各イテレーションにおいて、現在の推定値の方向の1つと、ランダムな直交方向の1つの2つの圧縮された測定しか取らない変種を解析する。 この適応センシング手法は,eigengap $\Delta=\lambda_1-\lambda_2$でデータストリームの先頭固有ベクトルを追跡する際に,ノイズの存在下でのグローバル収束を実現する。 理論解析により,(1) 実固有ベクトルと一定レベルのアライメントを達成するために$O(\lambda_1\lambda_2d^2/\Delta^2) の繰り返しを必要とするウォームアップフェーズ,(2) 正弦アライメント誤差が$O(\lambda_1\lambda_2d^2/\Delta^2 t) の速度で崩壊する局所収束フェーズ,である。 この保証は、圧縮サンプリングのため、既存のminimaxローバウンドに$d$の要素を追加して適合する。 この研究は、雑音を伴う部分空間追跡のための適応センシングにおける最初の収束保証を提供する。 我々の証明手法は、以前の研究よりもかなり単純である。 この結果は、フル次元サンプルの取得が困難またはコストのかかるアプリケーションに重要な意味を持つ。

関連論文リスト

• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。 最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。 一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
  論文  参考訳（メタデータ） (2024-05-29T18:36:59Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。 DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
  論文  参考訳（メタデータ） (2022-06-27T03:45:02Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Private Stochastic Non-Convex Optimization: Adaptive Algorithms and Tighter Generalization Bounds [72.63031036770425]
  有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。 標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
  論文  参考訳（メタデータ） (2020-06-24T06:01:24Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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