論文の概要: Optimal Online Change Detection via Random Fourier Features

• arxiv url: http://arxiv.org/abs/2505.17789v1
• Date: Fri, 23 May 2025 12:02:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-26 18:08:34.046009
• Title: Optimal Online Change Detection via Random Fourier Features
• Title（参考訳）: ランダムフーリエ特徴を用いた最適オンライン変化検出
• Authors: Florian Kalinke, Shakeel Gavioli-Akilagun,
• Abstract要約: 本稿では,多変量データストリームにおけるオンライン非パラメータ変化点検出の問題について検討する。 本稿では,ランダムなフーリエ特徴に基づく逐次テスト手法を提案する。 我々は,検出遅延がミニマックス感において最適であることを示す情報理論境界を含む,アルゴリズムの性能に関する強力な理論的保証を証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: This article studies the problem of online non-parametric change point detection in multivariate data streams. We approach the problem through the lens of kernel-based two-sample testing and introduce a sequential testing procedure based on random Fourier features, running with logarithmic time complexity per observation and with overall logarithmic space complexity. The algorithm has two advantages compared to the state of the art. First, our approach is genuinely online, and no access to training data known to be from the pre-change distribution is necessary. Second, the algorithm does not require the user to specify a window parameter over which local tests are to be calculated. We prove strong theoretical guarantees on the algorithm's performance, including information-theoretic bounds demonstrating that the detection delay is optimal in the minimax sense. Numerical studies on real and synthetic data show that our algorithm is competitive with respect to the state of the art.
• Abstract（参考訳）: 本稿では,多変量データストリームにおけるオンライン非パラメータ変化点検出の問題について検討する。 カーネルベースの2サンプルテストのレンズを用いてこの問題にアプローチし、ランダムなフーリエ特徴に基づくシーケンシャルなテスト手順を導入し、観測毎の対数時間複雑度と全対数空間複雑度で実行する。 このアルゴリズムは最先端と比較して2つの利点がある。 第一に、我々のアプローチは真にオンラインであり、事前変更分布からのトレーニングデータへのアクセスは不要である。 第二に、アルゴリズムはユーザーがローカルテストが計算されるウィンドウパラメータを指定する必要はない。 我々は,検出遅延がミニマックス感において最適であることを示す情報理論境界を含む,アルゴリズムの性能に関する強力な理論的保証を証明した。 実データおよび合成データに関する数値的研究は、我々のアルゴリズムが最先端技術に対して競合していることを示している。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  非定常データストリームから非線形関数のパラメータを推定するための効率的なオンライン近似ベイズ推定アルゴリズムを提案する。 この方法は拡張カルマンフィルタ (EKF) に基づいているが、新しい低ランク+斜角行列分解法を用いている。 変分推論に基づく手法とは対照的に,本手法は完全に決定論的であり,ステップサイズチューニングを必要としない。
  論文  参考訳（メタデータ） (2023-05-31T03:48:49Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning [5.202524136984542]
  シーケンスの分布の変化を検出するために,フレキシブルな非パラメトリック手法を構築した。 機能的プルーニングのアイデアのおかげで、NP-FOCuSは観測回数の対数直線的な計算コストを持つ。 検出能力の面では、NP-FOCuSは様々な設定で現在の非パラメトリックオンライン変更ポイント技術より優れている。
  論文  参考訳（メタデータ） (2023-02-06T11:50:02Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Online Kernel CUSUM for Change-Point Detection [12.383181837411469]
  本稿では,変化点検出のための計算効率の良いオンラインカーネルCumulative Sum (CUSUM) を提案する。 提案手法は,既存のカーネルベースの変更点検出法と比較して,小さな変更に対する感度の向上を示す。
  論文  参考訳（メタデータ） (2022-11-28T05:08:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。 このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
  論文  参考訳（メタデータ） (2020-06-06T19:28:14Z)

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

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