論文の概要: Query Efficient Structured Matrix Learning

• arxiv url: http://arxiv.org/abs/2507.19290v1
• Date: Fri, 25 Jul 2025 14:04:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-28 16:16:48.984624
• Title: Query Efficient Structured Matrix Learning
• Title（参考訳）: クエリ効率の良い構造化行列学習
• Authors: Noah Amsel, Pratyush Avi, Tyler Chen, Feyza Duman Keles, Chinmay Hegde, Cameron Musco, Christopher Musco, David Persson,
• Abstract要約: 我々は任意の有限サイズの行列族、$mathcalF$から、ほぼ最適の$A$の近似を求める。 驚くべきことに、マットベックモデルでは、複雑さの2次的な改善を$tildeO(sqrtlog|mathcalF|)$にすることができる。 例えば、次元$q$の任意の楕円行列族から準最適近似が $tildeO(sqrt) で学習できることを確かめる。
• 参考スコア（独自算出の注目度）: 32.0553563150929
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix $A$ given access to matrix-vector product (matvec) queries of the form $x \rightarrow Ax$ and $x \rightarrow A^Tx$. This problem is of central importance to algorithms across scientific computing and machine learning, with applications to fast multiplication and inversion for structured matrices, building preconditioners for first-order optimization, and as a model for differential operator learning. Prior work focuses on obtaining query complexity upper and lower bounds for learning specific structured matrix families that commonly arise in applications. We initiate the study of the problem in greater generality, aiming to understand the query complexity of learning approximations from general matrix families. Our main result focuses on finding a near-optimal approximation to $A$ from any finite-sized family of matrices, $\mathcal{F}$. Standard results from matrix sketching show that $O(\log|\mathcal{F}|)$ matvec queries suffice in this setting. This bound can also be achieved, and is optimal, for vector-matrix-vector queries of the form $x,y\rightarrow x^TAy$, which have been widely studied in work on rank-$1$ matrix sensing. Surprisingly, we show that, in the matvec model, it is possible to obtain a nearly quadratic improvement in complexity, to $\tilde{O}(\sqrt{\log|\mathcal{F}|})$. Further, we prove that this bound is tight up to log-log factors.Via covering number arguments, our result extends to well-studied infinite families. As an example, we establish that a near-optimal approximation from any \emph{linear matrix family} of dimension $q$ can be learned with $\tilde{O}(\sqrt{q})$ matvec queries, improving on an $O(q)$ bound achievable via sketching techniques and vector-matrix-vector queries.
• Abstract（参考訳）: 構造化近似(低ランク、スパース、バンド化等)を未知の行列に学習する問題について研究し、行列ベクトル積(matvec)のクエリに$x \rightarrow Ax$と$x \rightarrow A^Tx$の形でアクセスする。 この問題は、科学計算や機械学習にまたがるアルゴリズムにおいて重要な問題であり、高速な乗算と構造行列の逆変換、一階最適化のためのプレコンディショナーの構築、微分演算子学習のモデルとして応用されている。 以前の研究は、一般にアプリケーションで発生する特定の構造化行列族を学習するために、クエリの複雑さを上と下の境界で取得することに焦点を当てていた。 本研究は,一般行列系からの学習近似のクエリ複雑性を理解することを目的とした,より一般的な問題の研究を開始する。 我々の主な結果は、任意の有限サイズの行列族、$\mathcal{F}$から A$ に近い近似を求めることである。 行列スケッチの標準的な結果は、$O(\log|\mathcal{F}|)$ matvecクエリがこの設定で十分であることを示している。 この境界はまた、ランク1$マトリクスセンシングの研究で広く研究されている$x,y\rightarrow x^TAy$という形のベクトル行列ベクトルクエリに対しても達成でき、最適である。 驚くべきことに、マットベックモデルでは、複雑さのほぼ2次改善を$\tilde{O}(\sqrt{\log|\mathcal{F}|})$に得ることができる。 さらに、この境界はlog-log因子に限りがあることを証明し、数論をカバーして、その結果はよく研究された無限族にまで拡張する。 例えば、次元$q$の任意の \emph{linear matrix family} からの近似が $\tilde{O}(\sqrt{q})$ matvec クエリで学習できることを確立し、スケッチ技術とベクトル行列ベクトルクエリによって$O(q)$bound achievable を改良した。

関連論文リスト

• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions [23.539428616884035]
  非対称ガウス・ケルネル行列に対する行列ベクトル積の高速アルゴリズムについて研究する。 我々のアルゴリズムは、$K$に関する以下のモデリング仮定に依存している: 最悪のケースの成長とは対照的に、$K$のエントリの合計は$n$で線形にスケールする。 我々は、この仮定の下で動作し、制約のない計算を行う最初の準四進時間アルゴリズムを得る。
  論文  参考訳（メタデータ） (2025-07-31T13:29:43Z)
• Optimal Quantization for Matrix Multiplication [35.007966885532724]
  我々は、近似誤差を明確に保証したネスト格子に基づく普遍的量子化器を構築する。 我々の量子化器の実用的低複雑さバージョンは、非常に最適に近い性能を達成する。
  論文  参考訳（メタデータ） (2024-10-17T17:19:48Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Matrix Compression via Randomized Low Rank and Low Precision Factorization [47.902465710511485]
  現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。 この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。 LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
  論文  参考訳（メタデータ） (2023-10-17T06:56:57Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。 本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
  論文  参考訳（メタデータ） (2023-03-22T04:07:26Z)
• Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach [0.9453554184019107]
  K_ij = kappa(x_i,y_j)$ ここで $kappa(x,y)$ はカーネル関数である。 我々は、点の集合 X$ と $Y$ が大きいカーネル行列に対する低ランク近似を求める。
  論文  参考訳（メタデータ） (2022-12-24T07:15:00Z)
• Private Matrix Approximation and Geometry of Unitary Orbits [29.072423395363668]
  この問題は、スペクトルが$Lambda$と同じ行列で$A$を近似しようとする。 近似誤差の上限値と下限値を持つ効率的でプライベートなアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-06T16:31:44Z)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  我々は、任意の正半定値(PSD)$A$に対して、$(1 pm epsilon)$を$tr(A)$に近似する新しいランダム化アルゴリズムであるHutch++を導入する。 実験ではハッチンソン法を著しく上回る結果を得た。
  論文  参考訳（メタデータ） (2020-10-19T16:45:37Z)
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems [58.83118651518438]
  ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。 これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。 我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
  論文  参考訳（メタデータ） (2020-06-24T19:33:49Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。 提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T03:07:31Z)

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

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