論文の概要: Learning-Augmented Frequent Directions

• arxiv url: http://arxiv.org/abs/2503.00937v1
• Date: Sun, 02 Mar 2025 15:20:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:14:22.019415
• Title: Learning-Augmented Frequent Directions
• Title（参考訳）: 学習強化周波数方向
• Authors: Anders Aamand, Justin Y. Chen, Siddharth Gollapudi, Sandeep Silwal, Hao Wu,
• Abstract要約: ストリーミング文献の根本的な問題は、少量のメモリだけを使用して、長いデータストリームに現れるアイテムの出現数を近似することである。 我々は、CountMinやCountSketchのような一般的なソリューションの最悪のケース保証と、高周波要素の学習した予測を組み合わせるためのフレームワークを開発する。 本稿では、Frequent Directionsアルゴリズムの学習拡張版を分析し、学習した予測の理論的および経験的な理解を行列ストリーミングに拡張する。
• 参考スコア（独自算出の注目度）: 13.827632579682795
• License:
• Abstract: An influential paper of Hsu et al. (ICLR'19) introduced the study of learning-augmented streaming algorithms in the context of frequency estimation. A fundamental problem in the streaming literature, the goal of frequency estimation is to approximate the number of occurrences of items appearing in a long stream of data using only a small amount of memory. Hsu et al. develop a natural framework to combine the worst-case guarantees of popular solutions such as CountMin and CountSketch with learned predictions of high frequency elements. They demonstrate that learning the underlying structure of data can be used to yield better streaming algorithms, both in theory and practice. We simplify and generalize past work on learning-augmented frequency estimation. Our first contribution is a learning-augmented variant of the Misra-Gries algorithm which improves upon the error of learned CountMin and learned CountSketch and achieves the state-of-the-art performance of randomized algorithms (Aamand et al., NeurIPS'23) with a simpler, deterministic algorithm. Our second contribution is to adapt learning-augmentation to a high-dimensional generalization of frequency estimation corresponding to finding important directions (top singular vectors) of a matrix given its rows one-by-one in a stream. We analyze a learning-augmented variant of the Frequent Directions algorithm, extending the theoretical and empirical understanding of learned predictions to matrix streaming.
• Abstract（参考訳）: Hsu et al (ICLR'19) の影響力のある論文は、周波数推定の文脈における学習強化ストリーミングアルゴリズムの研究を紹介した。 ストリーミング文学における根本的な問題として、周波数推定の目標は、少量のメモリのみを使用して、長いデータストリームに現れるアイテムの出現数を近似することである。 Hsuらは、CountMinやCountSketchのような一般的なソリューションの最悪のケース保証と、高周波要素の学習された予測を組み合わせるための自然なフレームワークを開発している。 彼らは、基礎となるデータ構造を学習することで、理論と実践の両方において、より良いストリーミングアルゴリズムが得られることを実証した。 学習増強周波数推定における過去の作業の簡素化と一般化を行う。 最初のコントリビューションはMisra-Griesアルゴリズムの学習拡張版であり、学習したCountMinの誤差を改善し、ランダム化アルゴリズム(Aamand et al , NeurIPS'23)の最先端性能を実現する。 第2の貢献は、ストリーム内の行を1つずつ与えられた行列の重要方向(最上特異ベクトル)の探索に対応する周波数推定の高次元一般化に学習増強を適用することである。 本稿では、Frequent Directionsアルゴリズムの学習拡張版を分析し、学習した予測の理論的および経験的な理解を行列ストリーミングに拡張する。

関連論文リスト

• Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams [9.22255012731159]
  そこで本研究では,まず,大ヒット数,トップk,フロー周波数推定を識別する,LSSと呼ばれる競合カウンタベースのアルゴリズムを提案する。 以上の結果から, LSSは重打点, トップk, 流速推定において, スペースセービングの精度と効率を高めることができることが示された。
  論文  参考訳（メタデータ） (2024-06-24T02:31:00Z)
• Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
  データストリームに現れる要素の頻度を推定することは、大規模データ分析において重要なタスクである。 理論的には,Hsu等の学習に基づくアルゴリズムを,予測を使わずに上回る新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-12T18:59:06Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Generalization Bounds for Data-Driven Numerical Linear Algebra [24.961270871124217]
  データ駆動アルゴリズムは、トレーニングされた入力サンプルから学習することで、未知のアプリケーション固有の分布からの入力に内部構造やパラメータを適用することができる。 いくつかの最近の研究は、数値線形代数における問題にこのアプローチを適用し、性能において顕著な経験的利得を得た。 本研究では、Gupta と Roughgarden が提案するデータ駆動アルゴリズム選択のためのPAC学習フレームワークにおいて、これらのアルゴリズムの一般化境界を証明する。
  論文  参考訳（メタデータ） (2022-06-16T02:23:45Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。 我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
  論文  参考訳（メタデータ） (2021-10-03T05:38:49Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。 本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
  論文  参考訳（メタデータ） (2021-08-23T21:03:09Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
  本研究では,データ点数に対して時間的多元対数で動作する主成分回帰のアルゴリズムを開発する。 この指数的なスピードアップは、より大きなデータセットにおける潜在的な応用を可能にする。
  論文  参考訳（メタデータ） (2020-10-16T20:50:48Z)
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme [3.7565501074323224]
  本稿では,最適化と機械学習に基づくデータストリームの周波数推定問題に対する新しいアプローチを提案する。 提案手法は、観測されたストリームプレフィックスをほぼ最適にハッシュ要素に利用し、ターゲット周波数分布を圧縮する。 提案手法は, 推定誤差の平均(要素単位)と推定誤差の平均(要素単位)で1～2桁, 予測誤差で45～90%の精度で既存手法より優れていることを示す。
  論文  参考訳（メタデータ） (2020-07-17T22:15:22Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)

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

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