論文の概要: Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms

• arxiv url: http://arxiv.org/abs/2509.21847v1
• Date: Fri, 26 Sep 2025 04:15:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.171934
• Title: Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms
• Title（参考訳）: Johnson-Lindenstraussを超えて: スケッチされた双線形形式のための一様境界
• Authors: Rohan Deb, Qiaobo Li, Mayank Shrivastava, Arindam Banerjee,
• Abstract要約: 我々は、スケッチされた双線型形式を解析し、関連する集合の幾何学的複雑さの観点から一様境界を導出する枠組みを開発する。 この統一解析は、J-L補題のような既知の結果を特別なケースとして回収し、RIP型保証を延長する。
• 参考スコア（独自算出の注目度）: 9.956186859874851
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Uniform bounds on sketched inner products of vectors or matrices underpin several important computational and statistical results in machine learning and randomized algorithms, including the Johnson-Lindenstrauss (J-L) lemma, the Restricted Isometry Property (RIP), randomized sketching, and approximate linear algebra. However, many modern analyses involve *sketched bilinear forms*, for which existing uniform bounds either do not apply or are not sharp on general sets. In this work, we develop a general framework to analyze such sketched bilinear forms and derive uniform bounds in terms of geometric complexities of the associated sets. Our approach relies on generic chaining and introduces new techniques for handling suprema over pairs of sets. We further extend these results to the setting where the bilinear form involves a sum of $T$ independent sketching matrices and show that the deviation scales as $\sqrt{T}$. This unified analysis recovers known results such as the J-L lemma as special cases, while extending RIP-type guarantees. Additionally, we obtain improved convergence bounds for sketched Federated Learning algorithms where such cross terms arise naturally due to sketched gradient compression, and design sketched variants of bandit algorithms with sharper regret bounds that depend on the geometric complexity of the action and parameter sets, rather than the ambient dimension.
• Abstract（参考訳）: ベクトルや行列のスケッチされた内部積上の一様境界は、ジョンソン・リンデンシュトラウス(J-L)補題、制限等方性(RIP)、ランダム化されたスケッチ、近似線型代数など、機械学習およびランダム化アルゴリズムにおいて重要な計算および統計的結果の基盤となっている。 しかし、現代の多くの分析では *sketched bilinear form* が関係しており、既存の一様境界は一般集合に当てはまらないか、シャープでない。 本研究では、そのようなスケッチされた双線型形式を解析し、関連する集合の幾何学的複雑さの観点から一様境界を導出する一般的な枠組みを開発する。 提案手法はジェネリックチェアリングに依存し,一組の集合を超越的に扱うための新しい手法を導入する。 さらにこれらの結果を、双線型形式が独立スケッチ行列の和$T$を伴い、偏差が$\sqrt{T}$となるような設定にまで拡張する。 この統一解析は、J-L補題のような既知の結果を特別なケースとして回収し、RIP型保証を延長する。 さらに、スケッチされた勾配圧縮によってそのようなクロス項が自然に生じるようなスケッチ付きフェデレート学習アルゴリズムの収束境界の改善と、周囲次元よりもアクションとパラメータセットの幾何学的複雑さに依存する、よりシャープな後悔境界を持つバンディットアルゴリズムのスケッチ付き変種を設計する。

関連論文リスト

• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras [0.0]
  連結グラフ上の最大カット(最大カット)問題に対する3つの QAOA ans" の根底となる代数的性質について検討する。 標準QAOAsatzと軌道と多角アンサッツを解析する。
  論文  参考訳（メタデータ） (2024-10-07T16:46:20Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  ユークリッド空間における多くの集合の被覆数について上限を証明する。 本稿では,3つの計算応用における結果のパワーについて説明する。
  論文  参考訳（メタデータ） (2023-11-09T03:06:59Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  非剛体形状の正確なスパース対応を生成するための新しい混合整数プログラミング(MIP)法を提案する。 いくつかの挑戦的な3Dデータセットに対して,スパースな非剛性マッチングの最先端結果を示す。
  論文  参考訳（メタデータ） (2023-08-16T14:25:30Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• A graphical calculus for integration over random diagonal unitary matrices [1.5229257192293197]
  テンソルネットワークダイアグラムの平均を計算するためのグラフ計算を提供する。 我々は、一様ブロック置換の部分順序集合の順序構造を利用する。 同様の計算法は、独立な一様符号からなるランダムベクトルに対して開発された。
  論文  参考訳（メタデータ） (2020-07-22T06:06:51Z)

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

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