論文の概要: Simple, unified analysis of Johnson-Lindenstrauss with applications
- arxiv url: http://arxiv.org/abs/2402.10232v4
- Date: Fri, 19 Jul 2024 12:49:42 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-22 23:56:51.421439
- Title: Simple, unified analysis of Johnson-Lindenstrauss with applications
- Title（参考訳）: Johnson-Lindenstraus の単純統一解析とその応用
- Authors: Yingru Li,
- Abstract要約: Johnson-Lindenstrauss (JL) フレームワークの簡易かつ統一的な解析法を提案する。
提案手法は,JL フレームワーク下での様々な構成の理解と統合を簡略化する。
この統合は、ストリーミングアルゴリズムから強化学習まで、アプリケーションに不可欠なデータ固有の幾何学を保存する。
- 参考スコア（独自算出の注目度）: 1.6317061277457001
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a simplified and unified analysis of the Johnson-Lindenstrauss (JL) lemma, a cornerstone of dimensionality reduction for managing high-dimensional data. Our approach simplifies understanding and unifies various constructions under the JL framework, including spherical, binary-coin, sparse JL, Gaussian, and sub-Gaussian models. This unification preserves the intrinsic geometry of data, essential for applications from streaming algorithms to reinforcement learning. We provide the first rigorous proof of the spherical construction's effectiveness and introduce a general class of sub-Gaussian constructions within this simplified framework. Central to our contribution is an innovative extension of the Hanson-Wright inequality to high dimensions, complete with explicit constants. By using simple yet powerful probabilistic tools and analytical techniques, such as an enhanced diagonalization process, our analysis solidifies the theoretical foundation of the JL lemma by removing an independence assumption and extends its practical applicability to contemporary algorithms.
- Abstract（参考訳）: 本稿では,ジョンソン・リンデンシュトラウス(JL)補題の簡易かつ統一的な解析法を提案する。
提案手法は, 球面, バイナリコイン, スパースJL, ガウスモデル, ガウス下モデルなど, JL フレームワーク下での様々な構成の理解と統一を単純化する。
この統合は、ストリーミングアルゴリズムから強化学習まで、アプリケーションに不可欠なデータ固有の幾何学を保存する。
球面構成の有効性の厳密な証明を初めて提供し、この単純化された枠組みの中にガウス下構成の一般クラスを導入する。
私たちの貢献の中心は、ハンソン・ライトの不等式を高次元への革新的拡張であり、明示的な定数で完備である。
本研究は, 簡易かつ強力な確率的ツールと, 対角化プロセスの強化などの解析手法を用いて, 独立性の仮定を取り除き, 現代アルゴリズムへの実践的適用性を高めることにより, JL補題の理論的基礎を固める。
関連論文リスト
- Pushing the Limits of Large Language Model Quantization via the Linearity Theorem [71.3332971315821]
本稿では,階層的$ell$再構成誤差と量子化によるモデルパープレキシティ増加との直接的な関係を確立する「線形定理」を提案する。
この知見は,(1)アダマール回転とHIGGSと呼ばれるMSE最適格子を用いた単純なデータフリーLCM量子化法,(2)非一様層ごとの量子化レベルを求める問題に対する最適解の2つの新しい応用を可能にする。
論文 参考訳（メタデータ） (2024-11-26T15:35:44Z) - Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities [0.5592394503914488]
本稿では、所定の基準測度$mu$の摂動として、目標測度$pi$を同定し、近似する手法を提案する。
我々の主な貢献は、多元対数ソボレフ不等式(LSI)と、このアンザッツとの近似との接続を明らかにすることである。
論文 参考訳（メタデータ） (2024-06-18T20:02:44Z) - An Improved Analysis of Langevin Algorithms with Prior Diffusion for
Non-Log-Concave Sampling [27.882407333690267]
本研究では, 先行拡散を用いた改良型ランゲヴィンアルゴリズムが, 強対数対数対象分布に対して独立に次元を収束させることができることを示す。
また、修正したランゲヴィンアルゴリズムは、異なるステップサイズスケジュールを持つKL発散の次元非依存収束も得ることを証明した。
論文 参考訳（メタデータ） (2024-03-10T11:50:34Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Distributionally Robust Fair Principal Components via Geodesic Descents [16.440434996206623]
大学入学、医療、信用承認などのその後の領域では、学習予測の公正性や堅牢性といった新たな基準を考慮に入れることが不可欠である。
本稿では,主成分分析のための分布的ロバストな最適化問題を提案する。
実世界のデータセットに対する実験結果から,提案手法が最先端のベースラインに対して有益であることを示す。
論文 参考訳（メタデータ） (2022-02-07T11:08:13Z) - ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。
既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。
本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
論文 参考訳（メタデータ） (2021-10-13T19:36:50Z) - Learning primal-dual sparse kernel machines [10.230121160034674]
伝統的に、カーネル法は、学習問題の解は再生されたカーネルヒルベルト空間(RKHS)にマッピングされたデータの線形結合として得られるという代表者定理に依存している。
本稿では,RKHS の要素が必ずしもトレーニングセットの要素に対応するとは限らない元データ空間において,前像分解を持つ解を求めることを提案する。
勾配に基づく手法は入力空間のスパース要素の最適化に重きを置き、原始空間と双対空間の両方でカーネルベースのモデルを得ることができる。
論文 参考訳（メタデータ） (2021-08-27T09:38:53Z) - DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
近年のDAG構造学習は連続的な非巡回性制約を伴う制約付き連続最適化問題として定式化されている。
本稿では,DAG空間の重み付き隣接行列を直接モデル化し,学習するための新しい学習フレームワークを提案する。
本手法は, 線形および一般化された構造方程式モデルにおいて, ベースラインDAG構造学習法よりも精度が高いが, 効率がよいことを示す。
論文 参考訳（メタデータ） (2021-06-14T07:11:36Z) - GELATO: Geometrically Enriched Latent Model for Offline Reinforcement
Learning [54.291331971813364]
オフライン強化学習アプローチは、近近法と不確実性認識法に分けられる。
本研究では,この2つを潜在変動モデルに組み合わせることのメリットを実証する。
提案したメトリクスは、分布サンプルのアウトの品質と、データ内のサンプルの不一致の両方を測定します。
論文 参考訳（メタデータ） (2021-02-22T19:42:40Z) - Search for Efficient Formulations for Hamiltonian Simulation of
non-Abelian Lattice Gauge Theories [0.0]
格子ゲージ理論(LGTs)のハミルトン的定式化は、量子シミュレーションのための最も自然な枠組みである。
計算学的には最も正確であるが、そのような理論におけるハミルトンの定式化(英語版)は依然として重要な課題である。
本論文は,非アベリアLGTの場合において,この問題に対処するための第一歩である。
論文 参考訳（メタデータ） (2020-09-24T16:44:39Z) - On dissipative symplectic integration with applications to
gradient-based optimization [77.34726150561087]
本稿では,離散化を体系的に実現する幾何学的枠組みを提案する。
我々は、シンプレクティックな非保守的、特に散逸的なハミルトン系への一般化が、制御された誤差まで収束率を維持することができることを示す。
論文 参考訳（メタデータ） (2020-04-15T00:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。