論文の概要: Approximation algorithms for confidence bands for time series
- arxiv url: http://arxiv.org/abs/2112.06225v1
- Date: Sun, 12 Dec 2021 13:08:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-15 10:08:24.333215
- Title: Approximation algorithms for confidence bands for time series
- Title（参考訳）: 時系列における信頼バンドの近似アルゴリズム
- Authors: Nikolaj Tatti
- Abstract要約: NPハード問題であるにもかかわらず、約$k$の最適信頼帯域を見つけることができることを示す。
簡単な2-近似アルゴリズムを実証し、より優れた近似保証を達成できないことを示す。
- 参考スコア（独自算出の注目度）: 1.9188864062289428
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Confidence intervals are a standard technique for analyzing data. When
applied to time series, confidence intervals are computed for each time point
separately. Alternatively, we can compute confidence bands, where we are
required to find the smallest area enveloping $k$ time series, where $k$ is a
user parameter. Confidence bands can be then used to detect abnormal time
series, not just individual observations within the time series. We will show
that despite being an NP-hard problem it is possible to find optimal confidence
band for some $k$. We do this by considering a different problem: discovering
regularized bands, where we minimize the envelope area minus the number of
included time series weighted by a parameter $\alpha$. Unlike normal confidence
bands we can solve the problem exactly by using a minimum cut. By varying
$\alpha$ we can obtain solutions for various $k$. If we have a constraint $k$
for which we cannot find appropriate $\alpha$, we demonstrate a simple
algorithm that yields $O(\sqrt{n})$ approximation guarantee by connecting the
problem to a minimum $k$-union problem. This connection also implies that we
cannot approximate the problem better than $O(n^{1/4})$ under some (mild)
assumptions. Finally, we consider a variant where instead of minimizing the
area we minimize the maximum width. Here, we demonstrate a simple
2-approximation algorithm and show that we cannot achieve better approximation
guarantee.
- Abstract（参考訳）: 信頼区間はデータ分析の標準的な手法である。
時系列に適用すると、各時点毎に信頼区間を別々に計算する。
あるいは、$k$がユーザパラメータであるような、$k$時系列を包含する最小の領域を見つける必要がある、信頼バンドを計算できる。
信頼バンドは、時系列内の個々の観測だけでなく、異常な時系列を検出するために使用できる。
NPハード問題であるにもかかわらず、約$k$の最適信頼帯域を見つけることができることを示す。
正規化バンドを発見し、エンベロープ領域を最小化し、パラメータ$\alpha$で重み付けされた含む時系列の数を最小にする。
通常の信頼バンドと異なり、最小カットを用いて正確に問題を解くことができる。
alpha$を変更すれば、様々な$k$の解が得られる。
もし、適切な $\alpha$ を見つけることができない制約 $k$ があるなら、問題を最小の $k$-union 問題に結びつけることで、$o(\sqrt{n})$ 近似保証を得る単純なアルゴリズムを実証する。
この接続はまた、いくつかの (mild) 仮定の下では $o(n^{1/4})$ よりも問題を近似できないことを意味する。
最後に、面積を最小化する代わりに、最大幅を最小化する変種を考える。
ここでは,単純な2近似アルゴリズムを実演し,より良い近似保証は達成できないことを示す。
関連論文リスト
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。
我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。
PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
論文 参考訳（メタデータ） (2024-11-02T02:50:12Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
論文 参考訳（メタデータ） (2023-05-08T17:46:01Z) - Differentially Private Algorithms for the Stochastic Saddle Point
Problem with Optimal Rates for the Strong Gap [12.446156563700482]
凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。
また、安定性と精度の間には根本的なトレードオフがあることも示している。
論文 参考訳（メタデータ） (2023-02-24T21:50:02Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Differentially private $k$-means clustering via exponential mechanism
and max cover [6.736814259597673]
我々は、$k$-meansクラスタリング問題に対して、新しい$(epsilon_p, delta_p)$-differentially privateアルゴリズムを導入する。
論文 参考訳（メタデータ） (2020-09-02T17:52:54Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。