論文の概要: Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
- arxiv url: http://arxiv.org/abs/2609.26508v1
- Date: Tue, 22 Sep 2026 14:38:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-24 01:05:39.704133
- Title: Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
- Title（参考訳）: Gap-freeストリーミングPCAはランクワン以上のアップデート: ほぼ最適なレートと差別化プライバシへの応用
- Abstract要約: 我々は、この問題の最も一般的なギャップフリーな変種に対して、ユビキタスなOjaのアルゴリズム[Oja82]を新たに解析する。
当社のメインアプリケーションとして,[Bro26] の Conjecture 1.1 を対数因子に設定することで,ギャップフリーで微分プライベートな PCA 保証を行う。
- 参考スコア（独自算出の注目度）: 17.240861539586316
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream. We give a new analysis of the ubiquitous Oja's algorithm [Oja82] for the most general, gap-free variant of this problem, where no eigengap assumptions are made on the underlying mean matrix, complemented by a nearly-matching lower bound. Prior works achieving near-optimal rates for streaming PCA either required gap assumptions [JJK+16, HNWW21], or were limited to rank-one updates [AZL17, Lia23]. Our proof only uses a second moment bound on the individual stochastic updates, bypassing the almost sure bounds needed by prior near-optimal analyses, and the analogous offline matrix Bernstein bound. We also extend our result to a Rayleigh quotient notion of approximate PCA, addressing an open question of [JJK+16]. As our main application, we give gap-free differentially private PCA guarantees for sub-Gaussian data, settling Conjecture 1.1 of [Bro26] up to logarithmic factors.
- Abstract（参考訳）: ストリーミング主成分分析(PCA)は、データストリーム上の単一パスにおいて、主要なスペクトル部分空間を復元しようとする。
我々は、この問題の最も一般的なギャップのない変種に対して、ユビキタスなOjaのアルゴリズム[Oja82]を新たに解析する。
従来のPCAストリーミングでは,ギャップ仮定 [JJK+16, HNWW21] が必要か,あるいはランクワン更新 [AZL17, Lia23] に限定されていた。
我々の証明は、個々の確率的更新に束縛された第2のモーメントのみを使用し、事前の準最適解析で必要とされるほぼ確実な境界と、類似のオフライン行列ベルンシュタイン境界をバイパスする。
また、この結果をレイリー商PCAの概念に拡張し、[JK+16] の開問題に対処する。
当社のメインアプリケーションとして,[Bro26] の Conjecture 1.1 を対数因子に設定することで,ギャップフリーで微分プライベートな PCA 保証を行う。
関連論文リスト
- Inference and Uncertainty Quantification for Streaming $r$-PCA [0.40105987447353786]
Ojaのアルゴリズムを用いてPCAをストリーミングする際の2つのオープンな問題に対処する。
両大口径スパーステール系において, 対数的因子まで, 一致した下界を証明した。
論文 参考訳（メタデータ） (2026-08-18T23:02:28Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
オンラインスパース線形回帰(OSLR)では,予測のために1インスタンスあたり$d$あたり$k$しかアクセスできない。
提案手法では, 過去の後悔点を大幅に改善する拡張時間アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-31T05:02:33Z) - Sparse PCA with Oracle Property [115.72363972222622]
新規な正規化を伴うスパースPCAの半定緩和に基づく推定器群を提案する。
我々は、家族内の別の推定器が、スパースPCAの標準半定緩和よりも、より急激な収束率を達成することを証明した。
論文 参考訳（メタデータ） (2023-12-28T02:52:54Z) - Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA [43.106438224356175]
ほぼ最適誤差保証付き頑健なPCAのためのニア線形時間アルゴリズムを開発した。
また,メモリ使用量にほぼ線形なロバストPCAのためのシングルパスストリーミングアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-05-04T04:45:16Z) - Bayes-optimal limits in structured PCA, and how to reach them [21.3083877172595]
本研究では,主成分分析(PCA)のパラダイム行列モデルについて検討し,次数1の行列が付加雑音によって劣化することを示した。
このモデルにおいて、ベイズ-最適推論の極限を初めて特徴づける。
本稿では、適応的Thouless-Anderson-Palmer方程式の理論に着想を得た、新しい近似メッセージパッシングアルゴリズム(AMP)を提案する。
論文 参考訳（メタデータ） (2022-10-03T21:31:41Z) - Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms [9.112172220055431]
一般的な高次元のガウス設計の下で、スパースPCAに対して入出力$ell_2,infty$boundsを提供する。
提案手法は,確率の高い正しいサポートを選択するアルゴリズムであり,スパーシスタントなアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-08T18:50:35Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - Sparse Feature Selection Makes Batch Reinforcement Learning More Sample
Efficient [62.24615324523435]
本稿では,スパース線形関数近似を用いた高次元バッチ強化学習(RL)の統計的解析を行う。
候補となる機能が多数存在する場合,提案手法がバッチRLをより効率的にサンプリングできるという事実に光を当てる。
論文 参考訳（メタデータ） (2020-11-08T16:48:02Z) - A Simplified Run Time Analysis of the Univariate Marginal Distribution
Algorithm on LeadingOnes [9.853329403413701]
単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。
より少ない選択率によるランタイムゲインを示す。
同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
論文 参考訳（メタデータ） (2020-04-10T10:20:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。