論文の概要: Optimal Approximate Matrix Multiplication over Sliding Windows

• arxiv url: http://arxiv.org/abs/2502.18830v1
• Date: Wed, 26 Feb 2025 05:05:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-27 14:56:19.697337
• Title: Optimal Approximate Matrix Multiplication over Sliding Windows
• Title（参考訳）: スライディングウィンドウ上での最適近似行列乗算
• Authors: Ziqi Yao, Mingsong Chen, Cheng Chen,
• Abstract要約: スライドウィンドウ上でのAMMのためのDS-CODアルゴリズムを提案する。 提案アルゴリズムの理論的誤差境界と複雑性解析について述べる。 本稿では,DS-CODの適応版であるaDS-CODについて述べる。
• 参考スコア（独自算出の注目度）: 9.4089623997727
• License:
• Abstract: We explore the problem of approximate matrix multiplication (AMM) within the sliding window model, where algorithms utilize limited space to perform large-scale matrix multiplication in a streaming manner. This model has garnered increasing attention in the fields of machine learning and data mining due to its ability to handle time sensitivity and reduce the impact of outdated data. However, despite recent advancements, determining the optimal space bound for this problem remains an open question. In this paper, we introduce the DS-COD algorithm for AMM over sliding windows. This novel and deterministic algorithm achieves optimal performance regarding the space-error tradeoff. We provide theoretical error bounds and the complexity analysis for the proposed algorithm, and establish the corresponding space lower bound for the AMM sliding window problem. Additionally, we present an adaptive version of DS-COD, termed aDS-COD, which improves computational efficiency and demonstrates superior empirical performance. Extensive experiments conducted on both synthetic and real-world datasets validate our theoretical findings and highlight the practical effectiveness of our methods.
• Abstract（参考訳）: そこで我々は,アルゴリズムが限られた空間を利用して大規模行列乗算をストリーミング的に行う場合の,スライディングウィンドウモデルにおける近似行列乗法(AMM)の問題について検討する。 このモデルは、時間感度を処理し、時代遅れのデータの影響を減らすことができるため、機械学習やデータマイニングの分野で注目を集めている。 しかし、最近の進歩にもかかわらず、この問題の最適空間を決定することは未解決の問題である。 本稿では,スライドウィンドウ上でのAMMに対するDS-CODアルゴリズムを提案する。 この新しい決定論的アルゴリズムは、宇宙エラーのトレードオフに関する最適な性能を達成する。 提案アルゴリズムの理論的誤差境界と複雑性解析を行い,AMMスライディングウインドウ問題に対する対応する空間下界を確立する。 さらに,DS-CODの適応版であるaDS-CODを提案する。 人工と実世界の両方のデータセットで行われた大規模な実験は、我々の理論的な発見を検証し、我々の方法の実践的有効性を強調した。

関連論文リスト

• Adaptive Data Exploitation in Deep Reinforcement Learning [50.53705050673944]
  深層強化学習(RL)における**データ効率**と**一般化**を強化する強力なフレームワークであるADEPTを紹介する。 具体的には、ADEPTはマルチアーム・バンディット(MAB)アルゴリズムを用いて、異なる学習段階にわたるサンプルデータの使用を適応的に管理する。 Procgen、MiniGrid、PyBulletなどのベンチマークでADEPTをテストする。
  論文  参考訳（メタデータ） (2025-01-22T04:01:17Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。 WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
  論文  参考訳（メタデータ） (2024-10-28T04:47:39Z)
• Efficient Arbitrary Precision Acceleration for Large Language Models on GPU Tensor Cores [3.6385567224218556]
  大規模言語モデル(LLM)は広く応用されているが、効率的な推論では課題に直面している。 本稿では、並列計算を容易にし、対称量子化をサポートする新しいバイポーラ-INTデータフォーマットを提案する。 ビットレベルで分解・復元する任意の精度行列乗算方式を実装し,フレキシブルな精度を実現する。
  論文  参考訳（メタデータ） (2024-09-26T14:17:58Z)
• Large-Scale OD Matrix Estimation with A Deep Learning Method [70.78575952309023]
  提案手法は,ディープラーニングと数値最適化アルゴリズムを統合し,行列構造を推論し,数値最適化を導出する。 大規模合成データセットを用いて,提案手法の優れた一般化性能を実証するために実験を行った。
  論文  参考訳（メタデータ） (2023-10-09T14:30:06Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent [8.714458129632158]
  コルモゴロフモデル(コルモゴロフモデル、英: Kolmogorov model、KM)は、確率変数の集合の基本的な確率構造を学ぶための解釈可能で予測可能な表現手法である。 正規化双対最適化と拡張勾配降下法(GD)を併用した計算スケーラブルなKM学習アルゴリズムを提案する。 提案したKM学習アルゴリズムを用いた論理的関係マイニングの精度は80%以上である。
  論文  参考訳（メタデータ） (2021-07-11T10:33:02Z)
• Revisiting Co-Occurring Directions: Sharper Analysis and Efficient Algorithm for Sparse Matrices [23.22254890452548]
  近似行列乗算(AMM)のストリーミングモデルについて検討する。 我々は、アルゴリズムが限られたメモリでデータを1回だけ渡すことができるというシナリオに興味を持っている。 AMMストリーミングのための最先端決定論的スケッチアルゴリズムは共起方向(COD)である
  論文  参考訳（メタデータ） (2020-09-05T15:35:59Z)
• Adaptive Discretization for Model-Based Reinforcement Learning [10.21634042036049]
  本稿では,適応離散化手法を導入し,効率的なモデルに基づくエピソード強化学習アルゴリズムを設計する。 我々のアルゴリズムは、空間の適応的な離散化を維持するために拡張された楽観的なワンステップ値反復に基づいている。
  論文  参考訳（メタデータ） (2020-07-01T19:36:46Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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