論文の概要: Simple, unified analysis of Johnson-Lindenstrauss with applications
- arxiv url: http://arxiv.org/abs/2402.10232v2
- Date: Wed, 21 Feb 2024 15:30:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-22 18:51:31.347062
- Title: Simple, unified analysis of Johnson-Lindenstrauss with applications
- Title（参考訳）: Johnson-Lindenstraus の単純統一解析とその応用
- Authors: Yingru Li
- Abstract要約: ジョンソン・リンデンシュトラウス(JL)補題の単純かつ統一的な解析法を提案する。
提案手法は, 球面, バイナリコイン, スパースJL, ガウスモデル, ガウスモデルなど, JL フレームワーク下での様々な構成を統一する。
私たちの貢献の中心は、ハンソン・ライトの不等式から高次元への革新的拡張であり、明示的な定数で完備である。
- 参考スコア（独自算出の注目度）: 1.6317061277457001
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we present a simple and unified analysis of the
Johnson-Lindenstrauss (JL) lemma, a cornerstone in the field of dimensionality
reduction critical for managing high-dimensional data. Our approach not only
simplifies the understanding but also unifies various constructions under the
JL framework, including spherical, binary-coin, sparse JL, Gaussian and
sub-Gaussian models. This simplification and unification make significant
strides in preserving the intrinsic geometry of data, essential across diverse
applications from streaming algorithms to reinforcement learning. Notably, we
deliver the first rigorous proof of the spherical construction's effectiveness
and provide a general class of sub-Gaussian constructions within this
simplified framework. At the heart of our contribution is an innovative
extension of the Hanson-Wright inequality to high dimensions, complete with
explicit constants, marking a substantial leap in the literature. By employing
simple yet powerful probabilistic tools and analytical techniques, such as an
enhanced diagonalization process, our analysis not only solidifies the JL
lemma's theoretical foundation but also extends its practical reach, showcasing
its adaptability and importance in contemporary computational algorithms.
- Abstract（参考訳）: 本稿では,ジョンソン・リンデンシュトラウス(JL)補題の単純かつ統一的な解析について述べる。
我々のアプローチは理解を単純化するだけでなく、球面、バイナリコイン、スパースJL、ガウスおよびガウス以下のモデルを含む様々な構成をJLフレームワークで統一する。
この単純化と統一は、ストリーミングアルゴリズムから強化学習まで、さまざまなアプリケーションで不可欠なデータの内在的な幾何学を維持する上で、大きな一歩を踏み出します。
特に球面構成の有効性に関する最初の厳密な証明を提供し、この単純化された枠組みの中でサブガウス構成の一般的なクラスを提供する。
私たちの貢献の核心は、ハンソン=ライトの不等式を高次元に革新的に拡張し、明示的な定数を満たし、文学における大きな飛躍を示している。
拡張対角化プロセスのような単純かつ強力な確率的ツールと分析手法を用いることで,jl lemma 理論の基礎を固めるだけでなく,その実用性も拡張し,現代の計算アルゴリズムにおいてその適応性と重要性を示している。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。