論文の概要: Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures

• arxiv url: http://arxiv.org/abs/2107.06626v1
• Date: Wed, 14 Jul 2021 12:00:46 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-15 22:22:05.568576
• Title: Optimality of the Johnson-Lindenstrauss Dimensionality Reduction for Practical Measures
• Title（参考訳）: ジョンソン・リンデンシュトラウス次元還元の実用的尺度に対する最適性
• Authors: Yair Bartal and Ora Nova Fandina and Kasper Green Larsen
• Abstract要約: Johnson-Lindenstrauss次元減少法が最悪の場合の歪みに対して最適であることが知られている。 JL法が実際に歪みの測定に最適かどうかという問題は最近, citeBFN19 (NeurIPS'19) で提起された。 これらの境界は任意の次元還元法において、任意の1leq q leq O(fraclog (2eps2 n)eps)$および$epsilon geq frac1sqrtnに対して最適であることを示す。
• 参考スコア（独自算出の注目度）: 11.183319154396367
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: It is well known that the Johnson-Lindenstrauss dimensionality reduction method is optimal for worst case distortion. While in practice many other methods and heuristics are used, not much is known in terms of bounds on their performance. The question of whether the JL method is optimal for practical measures of distortion was recently raised in \cite{BFN19} (NeurIPS'19). They provided upper bounds on its quality for a wide range of practical measures and showed that indeed these are best possible in many cases. Yet, some of the most important cases, including the fundamental case of average distortion were left open. In particular, they show that the JL transform has $1+\epsilon$ average distortion for embedding into $k$-dimensional Euclidean space, where $k=O(1/\eps^2)$, and for more general $q$-norms of distortion, $k = O(\max\{1/\eps^2,q/\eps\})$, whereas tight lower bounds were established only for large values of $q$ via reduction to the worst case. In this paper we prove that these bounds are best possible for any dimensionality reduction method, for any $1 \leq q \leq O(\frac{\log (2\eps^2 n)}{\eps})$ and $\epsilon \geq \frac{1}{\sqrt{n}}$, where $n$ is the size of the subset of Euclidean space. Our results imply that the JL method is optimal for various distortion measures commonly used in practice, such as {\it stress, energy} and {\it relative error}. We prove that if any of these measures is bounded by $\eps$ then $k=\Omega(1/\eps^2)$, for any $\epsilon \geq \frac{1}{\sqrt{n}}$, matching the upper bounds of \cite{BFN19} and extending their tightness results for the full range moment analysis. Our results may indicate that the JL dimensionality reduction method should be considered more often in practical applications, and the bounds we provide for its quality should be served as a measure for comparison when evaluating the performance of other methods and heuristics.
• Abstract（参考訳）: Johnson-Lindenstrauss次元減少法が最悪の場合の歪みに対して最適であることが知られている。 実際には、他の多くの方法やヒューリスティックが使用されるが、その性能の境界についてはあまり知られていない。 JL法が実際に歪みの測定に最適かどうかという問題は、最近 \cite{BFN19} (NeurIPS'19) で提起された。 彼らは幅広い実践的措置のために品質の上界を提供し、多くのケースでこれが最善であることを示した。 しかし、平均歪みの基本的なケースを含む最も重要なケースは、未解決のまま残されている。 特に、JL変換は、$k=O(1/\eps^2)$、より一般的な$q$-normsの歪み、$k = O(\max\{1/\eps^2,q/\eps\})$、$k=O(1/\eps^2)$、$k=O(\max\{1/\eps^2,q/\eps\})$に埋め込むための平均歪みが1+\epsilon$1+\epsilon$である。 本稿では、任意の次元減少法において、これらの境界が最善であることが証明され、任意の 1 \leq q \leq o(\frac{\log (2\eps^2n)}{\eps})$ および $\epsilon \geq \frac{1}{\sqrt{n}}$ に対して、$n$ はユークリッド空間の部分集合の大きさである。 以上の結果から, JL法は, 応力, エネルギー, 相対誤差など, 実際に一般的に用いられる様々な歪み測定に最適であることが示唆された。 これらの測度のいずれかが$\eps$であれば、$k=\Omega(1/\eps^2)$, for any $\epsilon \geq \frac{1}{\sqrt{n}}$, with the upper bounds of \cite{BFN19} and extended their tightness results for the full range moment analysis。 以上の結果から,JL次元減少法は実用的応用においてより頻繁に検討されるべきであり,他の手法とヒューリスティックスの性能を評価する際には,その品質に対する限界を比較尺度として提供すべきであると考えられる。

関連論文リスト

• Theoretical limits of descending $\ell_0$ sparse-regression ML algorithms [0.0]
  本研究では,emphmaximum-likelihood (ML)デコーディングの性能解析プログラムを開発した。 ML性能パラメータの鍵となるのは、残留エンフェロ平均二乗誤差(textbfRMSE$)を発見し、いわゆるエンフェロ遷移(PT)現象を示す。 Fl RDTの具体的実装と実用的妥当性は、典型的には、基礎となる数値評価のサイズのセットを実行する能力に依存している。
  論文  参考訳（メタデータ） (2024-10-10T06:33:41Z)
• Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization [48.84672493756553]
  我々は,1ステップあたり$Obig(slogfrac dsbig)$クエリのみを使用する勾配のクエリ効率と精度の高い推定器を提案する。 Indyk-Price-Woodruff (IPW) アルゴリズムを線形測定から非線形関数への圧縮センシングにおいて一般化した。
  論文  参考訳（メタデータ） (2024-05-27T03:52:53Z)
• Practical Performance Guarantees for Pipelined DNN Inference [3.493620624883548]
  グラフを$k$のステージに分割することで、ディープニューラルネットワーク(DNN)推論のためのパイプライン並列性を最適化する。 改良された下限が最適性ギャップを9.855xで閉じていることが示される。
  論文  参考訳（メタデータ） (2023-11-07T03:55:39Z)
• Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization [9.019243171993553]
  トレーニングステップ$T$とStep-size$eta$は、滑らかな凸最適化(SCO)問題の認定に影響を与える可能性がある。 まず、グラディエントDescent(GD)とグラディエントDescent(SGD)の厳密な過剰リスク低境界を提供する。 近年の作業は、より良い速度で達成できるが、トレーニング時間が長い場合には改善が減少する。
  論文  参考訳（メタデータ） (2023-03-19T20:24:33Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs [35.988644745703645]
  我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。 本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-28T13:01:38Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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