論文の概要: Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

• arxiv url: http://arxiv.org/abs/2304.07652v1
• Date: Sat, 15 Apr 2023 22:42:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-18 18:08:40.132745
• Title: Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
• Title（参考訳）: ワーストケース保証を用いたストリーミング量子近似の学習補間
• Authors: Nicholas Schiefer, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Tal Wagner
• Abstract要約: $varepsilon$-approximate Quantile sketch over a stream of $n$ inputs is almost the rank of any query point $q$。 有名なKLLスケッチは、最悪のケースストリーム上で証明可能な最適な量子近似アルゴリズムを達成するが、実際に達成される近似は、しばしば最適ではない。 ストリーミング量子化問題に適用し、KLLよりも実世界のデータセットの近似性を向上し、最悪の場合、同様の保証を維持する。
• 参考スコア（独自算出の注目度）: 22.16980344969893
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An $\varepsilon$-approximate quantile sketch over a stream of $n$ inputs approximates the rank of any query point $q$ - that is, the number of input points less than $q$ - up to an additive error of $\varepsilon n$, generally with some probability of at least $1 - 1/\mathrm{poly}(n)$, while consuming $o(n)$ space. While the celebrated KLL sketch of Karnin, Lang, and Liberty achieves a provably optimal quantile approximation algorithm over worst-case streams, the approximations it achieves in practice are often far from optimal. Indeed, the most commonly used technique in practice is Dunning's t-digest, which often achieves much better approximations than KLL on real-world data but is known to have arbitrarily large errors in the worst case. We apply interpolation techniques to the streaming quantiles problem to attempt to achieve better approximations on real-world data sets than KLL while maintaining similar guarantees in the worst case.
• Abstract（参考訳）: a $\varepsilon$-approximate Quantile sketch over a stream of $n$ inputs is almost the rank of any query point $q$ - すなわち、$q$未満の入力点の個数は$\varepsilon n$の加算誤差までであり、一般には少なくとも1- 1/\mathrm{poly}(n)$の確率で$o(n)$ spaceを消費する。 カルニン、ラング、リバティの有名なkllのスケッチは、最悪の場合のストリーム上で証明可能な最適な分位近似アルゴリズムを実現するが、実際に達成した近似はしばしば最適とは程遠い。 実際、最も一般的に使われているテクニックはDunningのt-digestであり、実世界のデータではKLLよりもはるかに優れた近似を達成しているが、最悪の場合、任意に大きなエラーを犯すことが知られている。 ストリーミング量子化問題に対して補間手法を適用し,KLLよりも実世界のデータセットの近似性を向上し,最悪の場合でも同様の保証を維持する。

関連論文リスト

• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。 我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T11:31:54Z)
• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy [36.04370583654189]
  クリッピング機構が$O(max_i x_i cdot loglog U /varepsilon)$のインスタンス最適誤差を実現する方法を示す。 また、この手法を高次元和推定問題とスパースベクトルアグリゲーションに拡張する。
  論文  参考訳（メタデータ） (2024-03-15T09:04:00Z)
• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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