論文の概要: Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

• arxiv url: http://arxiv.org/abs/2506.00165v1
• Date: Fri, 30 May 2025 19:11:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 01:42:09.1574
• Title: Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
• Title（参考訳）: ユークリッド最大化と多様性対策のためのランダム化次元化
• Authors: Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten,
• Abstract要約: 次元縮小の効果は、基礎となるデータセットである$X$のemphdoubling dimension $lambda_X$と密接に結びついていることが示される。 具体的には、ターゲット次元が$O(lambda_X)$ sufficesであり、ほぼ最適解の値を保存するのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 15.600580592567738
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the \emph{doubling dimension} $\lambda_X$ of the underlying dataset $X$ -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of $O(\lambda_X)$ suffices to approximately preserve the value of any near-optimal solution,which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.
• Abstract（参考訳）: ランダム化次元減少は、大規模ユークリッド最適化問題を高速化するための広く使われているアルゴリズム手法である。 本稿では,最大マッチング,最大スパンニング木,最大TSP,およびデータセットの多様性に関する様々な尺度を含む,様々な最大化問題の次元削減について検討する。 これらの問題に対して、次元縮小の効果は、点集合の内在的な次元を測定する量であるデータセット$X$の \emph{doubling dimension} $\lambda_X$ と密接に結びついていることが示される。 具体的には、ターゲット次元が$O(\lambda_X)$ sufficesであり、ほぼ最適解の値を保存するのに十分であることを示す。 これは古典的な次元の減少の結果とは対照的であり、データセットサイズが$|X|$に大きく依存する。 また、射影空間における解の質を検証し、次元の減少によるスピードアップを検証した経験的結果も提供する。

関連論文リスト

• The signaling dimension in generalized probabilistic theories [48.99818550820575]
  物理系のシグナリング次元は、与えられた系のすべての入出力相関を再現するために必要な古典系の最小次元を定量化する。 線量測定を線量効果で考えるのに十分であることを示すとともに、そのような測定の要素の数を線形次元で表す。 有限個の極端効果を持つ系に対しては、極端測定を光線-極端効果で特徴づけるという問題を再放送する。
  論文  参考訳（メタデータ） (2023-11-22T02:09:16Z)
• Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm [1.3469999282609788]
  我々は、$n-要素$d$-ary文字列の集合上で定義される最適化問題の一般化された定式化に焦点を当てる。 我々の主な貢献は、当初提案されたQAOAの次元を含む。 アルゴリズムをより小さな次元の空間に制限することは、回路の量子シミュレーションと古典シミュレーションの両方を著しく加速させる可能性がある。
  論文  参考訳（メタデータ） (2023-09-25T00:35:40Z)
• Linearly-scalable learning of smooth low-dimensional patterns with permutation-aided entropic dimension reduction [0.0]
  多くのデータサイエンス応用において、高次元データセットから適切に順序付けられた滑らかな低次元データパターンを抽出することが目的である。 本研究では, ユークリッドの滑らか度をパターン品質基準として選択する場合, これらの問題を数値的に効率的に解けることを示す。
  論文  参考訳（メタデータ） (2023-06-17T08:03:24Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-maxアルゴリズムはユークリッド設定で解析されている。 指数関数法 (RCEG) が線形速度で最終収束を補正したことを証明した。
  論文  参考訳（メタデータ） (2022-06-04T18:53:44Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering [13.208510864854894]
  ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。 本稿では,施設配置問題と単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。
  論文  参考訳（メタデータ） (2021-07-05T05:55:26Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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