論文の概要: Online Heavy-tailed Change-point detection

• arxiv url: http://arxiv.org/abs/2306.09548v2
• Date: Mon, 3 Jul 2023 17:56:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-04 12:34:27.626281
• Title: Online Heavy-tailed Change-point detection
• Title（参考訳）: オンライン重み付き変化点検出
• Authors: Abishek Sankararaman and Balakrishnan (Murali) Narayanaswamy
• Abstract要約: 我々は,データ生成プロセスの第2モーメントが有界であると仮定した場合でも,クリッピングされたグラディエント・ディクセント(SGD)に基づくアルゴリズムを提案する。 我々は、有界な第2モーメントを持つすべての分布の族に対して、最悪の場合、有限サンプル偽陽性率(FPR)を導出する。 本手法は,データが高次元かつ基礎となる分布が重み付きであっても,有限サンプルFPRを保証する最初のOCPDアルゴリズムである。
• 参考スコア（独自算出の注目度）: 6.7643284029102295
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study algorithms for online change-point detection (OCPD), where samples that are potentially heavy-tailed, are presented one at a time and a change in the underlying mean must be detected as early as possible. We present an algorithm based on clipped Stochastic Gradient Descent (SGD), that works even if we only assume that the second moment of the data generating process is bounded. We derive guarantees on worst-case, finite-sample false-positive rate (FPR) over the family of all distributions with bounded second moment. Thus, our method is the first OCPD algorithm that guarantees finite-sample FPR, even if the data is high dimensional and the underlying distributions are heavy-tailed. The technical contribution of our paper is to show that clipped-SGD can estimate the mean of a random vector and simultaneously provide confidence bounds at all confidence values. We combine this robust estimate with a union bound argument and construct a sequential change-point algorithm with finite-sample FPR guarantees. We show empirically that our algorithm works well in a variety of situations, whether the underlying data are heavy-tailed, light-tailed, high dimensional or discrete. No other algorithm achieves bounded FPR theoretically or empirically, over all settings we study simultaneously.
• Abstract（参考訳）: オンライン変更点検出(OCPD)のアルゴリズムについて検討し、重み付けされたサンプルを1回ずつ提示し、基礎となる平均値の変更をできるだけ早く検出する必要がある。 我々は,データ生成過程の第2モーメントが有界であると仮定した場合でも,クリップ型確率勾配降下 (sgd) に基づくアルゴリズムを提案する。 我々は、有界第2モーメントを持つ全ての分布の族に対して、最悪の場合、有限サンプル偽陽性率(FPR)を導出する。 そこで本手法は,データが高次元かつ基礎となる分布が重み付きであっても,有限サンプルFPRを保証する最初のOCPDアルゴリズムである。 本論文の技術的貢献は,クリッピングSGDがランダムなベクトルの平均を推定し,すべての信頼値に信頼境界を同時に提供することを示すことである。 この頑健な推定を結合境界引数と組み合わせ、有限サンプルFPR保証付き逐次変化点アルゴリズムを構築する。 我々は,本アルゴリズムが重み付け,軽量化,高次元化,離散化など,様々な状況において有効であることを示す。 同時に研究するすべての設定に対して理論的あるいは経験的に有界なFPRを達成するアルゴリズムは他にない。

関連論文リスト

• Inference for an Algorithmic Fairness-Accuracy Frontier [0.9147443443422864]
  We provide a consistent estimator for a theoretical fairness-accuracy frontier forward by Liang, Lu and Mu (2023) フェアネス文学で注目されている仮説を検証するための推論手法を提案する。 サンプルサイズが大きくなるにつれて, 推定された支持関数が密なプロセスに収束することを示す。
  論文  参考訳（メタデータ） (2024-02-14T00:56:09Z)
• Faster Adaptive Federated Learning [84.38913517122619]
  フェデレートラーニングは分散データの出現に伴って注目を集めている。 本稿では,クロスサイロFLにおけるモーメントに基づく分散低減手法に基づく適応アルゴリズム(FAFED)を提案する。
  論文  参考訳（メタデータ） (2022-12-02T05:07:50Z)
• QuTE: decentralized multiple testing on sensor networks with false discovery rate control [130.7122910646076]
  本稿では、偽発見率(FDR)の証明可能な保証を備えたグラフ上での分散多重仮説検定法を設計する。 異なるエージェントが無向グラフのノードに存在し、各エージェントはそのノードに局所的な1つ以上の仮説に対応するp値を持つ。 各エージェントは、グラフ全体の大域的FDRが予め定義されたレベルで制御されなければならないという共同目的のもと、隣人とのみ通信することで、それぞれのローカル仮説の1つ以上の拒絶を個別に決めなければならない。
  論文  参考訳（メタデータ） (2022-10-09T19:48:39Z)
• Differentially Private Federated Learning via Inexact ADMM with Multiple Local Updates [0.0]
  我々は,複数の局所的な更新を施した乗算器アルゴリズムのDP不正確な交互方向法を開発した。 当社のアルゴリズムでは,各イテレーション毎に$barepsilon$-DPを提供しており,$barepsilon$はユーザが管理するプライバシ予算である。 提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも31%削減すると同時に,データプライバシのレベルが同じであることを実証する。
  論文  参考訳（メタデータ） (2022-02-18T19:58:47Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  線形関数近似を用いた強化学習について検討する。 既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。 我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
  論文  参考訳（メタデータ） (2021-06-22T08:48:56Z)
• Differentially Private Federated Learning via Inexact ADMM [0.0]
  差分プライバシー(DP)技術は、データプライバシを推論攻撃から保護するために、フェデレーション付き学習モデルに適用することができる。 我々は,信頼領域のサブプロブレム列を解く乗算器アルゴリズムのDP不正確な交互方向法を開発した。 提案アルゴリズムは,既存のDPアルゴリズムと比較してテストエラーを少なくとも22%削減すると同時に,データプライバシのレベルも同等に向上する。
  論文  参考訳（メタデータ） (2021-06-11T02:28:07Z)
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling [0.9806910643086042]
  本稿では,勾配降下アルゴリズムの平均化法により推定されるパラメータのベクトルに対するオンライン推論法を提案する。 我々のアプローチはオンラインデータで完全に運用されており、機能中心極限定理によって厳格に支えられている。
  論文  参考訳（メタデータ） (2021-06-06T15:38:37Z)
• T-SCI: A Two-Stage Conformal Inference Algorithm with Guaranteed Coverage for Cox-MLP [13.4379473119565]
  検閲データのカバレッジ保証を回復するための2つのアルゴリズムを提案する。 まず,重み付き共形推論を再検討し,部分的確率に基づく新しい非共形性スコアを導入する。 そこで第1段階でWCCIを実行し、第2段階で結果を校正するために量子的コンフォーマル推論を適用する2段階アルゴリズム emphT-SCI を提案する。
  論文  参考訳（メタデータ） (2021-03-08T05:42:05Z)
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times [51.61278695776151]
  フェデレートラーニング(FL)は、分散クライアント間で機械学習モデルを協調的にトレーニングする際のプライバシ保護でよく知られている。 最近の研究では、naive flは勾配リーク攻撃の影響を受けやすいことが指摘されている。 ディファレンシャルプライバシ(dp)は、勾配漏洩攻撃を防御するための有望な対策として現れる。
  論文  参考訳（メタデータ） (2021-01-11T19:43:12Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
  数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。 最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
  論文  参考訳（メタデータ） (2020-05-07T00:39:52Z)

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

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