論文の概要: Optimization Can Learn Johnson Lindenstrauss Embeddings

• arxiv url: http://arxiv.org/abs/2412.07242v1
• Date: Tue, 10 Dec 2024 07:07:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-11 14:39:10.156685
• Title: Optimization Can Learn Johnson Lindenstrauss Embeddings
• Title（参考訳）: 最適化はJohnson Lindenstraussの埋め込みを学べる
• Authors: Nikos Tsikouras, Constantine Caramanis, Christos Tzamos,
• Abstract要約: Johnson-Lindenstrauss (JL) のようなランダム化法は、そのような表現を達成するための不可能な理論的保証を提供する。 本稿では,この基本課題を回避する拡散モデルに基づく新しい手法を提案する。 この大きな空間を移動することによって、目的が決定論的(ゼロ分散)な解に収束し、悪い定常点を避けることが示される。
• 参考スコア（独自算出の注目度）: 30.652854230884145
• License:
• Abstract: Embeddings play a pivotal role across various disciplines, offering compact representations of complex data structures. Randomized methods like Johnson-Lindenstrauss (JL) provide state-of-the-art and essentially unimprovable theoretical guarantees for achieving such representations. These guarantees are worst-case and in particular, neither the analysis, nor the algorithm, takes into account any potential structural information of the data. The natural question is: must we randomize? Could we instead use an optimization-based approach, working directly with the data? A first answer is no: as we show, the distance-preserving objective of JL has a non-convex landscape over the space of projection matrices, with many bad stationary points. But this is not the final answer. We present a novel method motivated by diffusion models, that circumvents this fundamental challenge: rather than performing optimization directly over the space of projection matrices, we use optimization over the larger space of random solution samplers, gradually reducing the variance of the sampler. We show that by moving through this larger space, our objective converges to a deterministic (zero variance) solution, avoiding bad stationary points. This method can also be seen as an optimization-based derandomization approach and is an idea and method that we believe can be applied to many other problems.
• Abstract（参考訳）: 埋め込みは様々な分野において重要な役割を担い、複雑なデータ構造のコンパクトな表現を提供する。 Johnson-Lindenstrauss (JL) のようなランダム化された手法は、そのような表現を達成するための最先端で本質的には不可能な理論的保証を提供する。 これらの保証は最悪のケースであり、特に分析もアルゴリズムも、データの潜在的な構造情報を考慮していない。 自然の疑問は、ランダムにしなければなりませんか? 代わりに、データを直接処理する最適化ベースのアプローチを使用できるでしょうか? 私たちが示すように、JL の距離保存目的は射影行列空間上の非凸な風景を持ち、多くの悪い定常点を持つ。 しかし、これは最終的な答えではない。 射影行列の空間上で直接最適化を行うのではなく、ランダムな解サンプルラーの空間上での最適化を用いて、サンプルラーの分散を徐々に減少させる。 この大きな空間を移動することによって、我々の目的が決定論的(ゼロ分散)な解に収束し、悪い定常点を避けることが示される。 この手法は最適化に基づくデランドマイズ手法として見ることができ、他の多くの問題に適用できると考えるアイデアと方法である。

関連論文リスト

• Self-Supervised Dataset Distillation for Transfer Learning [77.4714995131992]
  ラベルなしデータセットを、効率的な自己教師付き学習(SSL)のための小さな合成サンプル群に蒸留する新しい問題を提案する。 両レベル最適化におけるSSL目標に対する合成サンプルの勾配は、データ拡張やマスキングから生じるランダム性から、テキストバイアスを受けていることを最初に証明する。 転送学習を含む様々な応用における本手法の有効性を実証的に検証する。
  論文  参考訳（メタデータ） (2023-10-10T10:48:52Z)
• Multistage Stochastic Optimization via Kernels [3.7565501074323224]
  我々は,多段階最適化問題に対する非パラメトリック,データ駆動,トラクタブルアプローチを開発した。 本稿では,提案手法が最適に近い平均性能で決定ルールを生成することを示す。
  論文  参考訳（メタデータ） (2023-03-11T23:19:32Z)
• A sub-sampling algorithm preventing outliers [0.0]
  我々は、高レバレッジポイントを使わずに、ほぼD-最適部分集合を選択できる教師なし交換手順を提案する。 また、この交換手順の教師付きバージョンを提供し、高いレバレッジポイントに加えて、応答の外れ値も避ける。 教師なしの選択手順と教師なしの選択手順は、正確な予測を得ることを目的として、I-最適性に一般化される。
  論文  参考訳（メタデータ） (2022-08-12T11:03:57Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Distributionally Robust Optimization with Markovian Data [8.126833795693699]
  本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。 本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
  論文  参考訳（メタデータ） (2021-06-12T10:59:02Z)
• Data-Driven Combinatorial Optimization with Incomplete Information: a Distributionally Robust Optimization Approach [0.0]
  我々は,コストベクトルが先行性を持たないが,有限データセットでしか観測できない線形最適化問題を解析する。 目標は、データセットを対象関数の期待値の推定値に変換する手順を見つけることである。
  論文  参考訳（メタデータ） (2021-05-28T23:17:35Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。 我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。 また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
  論文  参考訳（メタデータ） (2020-02-16T09:01:18Z)

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

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