論文の概要: A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP
hierarchies
- arxiv url: http://arxiv.org/abs/2311.17840v1
- Date: Wed, 29 Nov 2023 17:42:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 20:19:52.357065
- Title: A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP
hierarchies
- Title(参考訳): lp階層による多次元スケーリングのための準多項時間アルゴリズム
- Authors: Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram,
Silvio Lattanzi
- Abstract要約: 多次元スケーリング(MDS)は、$n$オブジェクト間のペアワイドな相似性を低次元空間に埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
我々の分析は、低次元ユークリッド空間の幾何学を利用して、アスペクト比$Delta$への指数的依存を避けることができる。
- 参考スコア(独自算出の注目度): 37.29025597886073
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multi-dimensional Scaling (MDS) is a family of methods for embedding
pair-wise dissimilarities between $n$ objects into low-dimensional space. MDS
is widely used as a data visualization tool in the social and biological
sciences, statistics, and machine learning. We study the Kamada-Kawai
formulation of MDS: given a set of non-negative dissimilarities $\{d_{i,j}\}_{i
, j \in [n]}$ over $n$ points, the goal is to find an embedding
$\{x_1,\dots,x_n\} \subset \mathbb{R}^k$ that minimizes \[ \text{OPT} =
\min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_i -
x_j\|}{d_{i,j}}\right)^2 \right] \]
Despite its popularity, our theoretical understanding of MDS is extremely
limited. Recently, Demaine, Hesterberg, Koehler, Lynch, and Urschel
(arXiv:2109.11505) gave the first approximation algorithm with provable
guarantees for Kamada-Kawai, which achieves an embedding with cost $\text{OPT}
+\epsilon$ in $n^2 \cdot 2^{\tilde{\mathcal{O}}(k \Delta^4 / \epsilon^2)}$
time, where $\Delta$ is the aspect ratio of the input dissimilarities. In this
work, we give the first approximation algorithm for MDS with quasi-polynomial
dependency on $\Delta$: for target dimension $k$, we achieve a solution with
cost $\mathcal{O}(\text{OPT}^{ \hspace{0.04in}1/k } \cdot \log(\Delta/\epsilon)
)+ \epsilon$ in time $n^{ \mathcal{O}(1)} \cdot 2^{\tilde{\mathcal{O}}( k^2
(\log(\Delta)/\epsilon)^{k/2 + 1} ) }$.
Our approach is based on a novel analysis of a conditioning-based rounding
scheme for the Sherali-Adams LP Hierarchy. Crucially, our analysis exploits the
geometry of low-dimensional Euclidean space, allowing us to avoid an
exponential dependence on the aspect ratio $\Delta$. We believe our
geometry-aware treatment of the Sherali-Adams Hierarchy is an important step
towards developing general-purpose techniques for efficient metric optimization
algorithms.
- Abstract(参考訳): 多次元スケーリング(MDS)は、$n$オブジェクト間のペアワイドな相似性を低次元空間に埋め込む方法のファミリーである。
MDSは、社会科学、統計学、機械学習におけるデータ可視化ツールとして広く利用されている。
非負の相似性の集合 $\{d_{i,j}\}_{i , j \in [n]}$ over $n$ points, the goal to find a embeddedding $\{x_1,\dots,x_n\} \subset \mathbb{R}^k$ that minimals \[ \text{OPT} = \min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_x_x_j\|}{d_{i,j}}\right)^2 \right] それらの人気にもかかわらず、MDSの理論的理解は非常に制限されている。
最近、Demaine, Hesterberg, Koehler, Lynch, Urschel (arXiv:2109.11505) は、Kamada-Kawai に対する証明可能な保証を持つ最初の近似アルゴリズムを与え、これはコスト $\text{OPT} +\epsilon$ in $n^2 \cdot 2^{\tilde{\mathcal{O}}(k \Delta^4 / \epsilon^2)} の埋め込みを実現する。
対象次元 $k$ に対して、コスト $\mathcal{o}(\text{opt}^{ \hspace{0.04in}1/k } \cdot \log(\delta/\epsilon) )+ \epsilon$ in time $n^{ \mathcal{o}(1)} \cdot 2^{\tilde{\mathcal{o}}(k^2 (\log(\delta)/\epsilon)^{k/2 + 1} ) } で解を得る。
本手法は,シェラリ・アダムスLP階層に対する条件付きラウンドリングスキームの新規解析に基づく。
重要なことは、我々の分析は低次元ユークリッド空間の幾何学を利用して、アスペクト比$\Delta$の指数的依存を避けることができる。
sherali-adams階層の幾何学的対応は、効率的なメトリック最適化アルゴリズムのための汎用技術を開発するための重要なステップであると考えています。
関連論文リスト
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳(メタデータ) (2024-03-05T12:28:00Z) - A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
Minimizing the Maximum of Smooth Functions [44.655316553524855]
我々は,$d$次元ユークリッド領域あるいは単純領域上で$max_iin[n] f_i(x) を最小化するアルゴリズムを設計する。
それぞれの$f_i$が1ドルLipschitzと1ドルSmoothのとき、我々の手法は$epsilon-approximateの解を計算する。
論文 参考訳(メタデータ) (2023-11-17T22:07:18Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric
Spaces [0.6732660670243813]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳(メタデータ) (2023-05-12T08:43:28Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳(メタデータ) (2022-10-05T22:52:00Z) - Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple,
and Practical [1.2183405753834562]
有限集合系 $(X,mathcal S)$ が与えられたとき、2色の $chi:Xto-1,1$ は数学的な S|chi(S)|$ において $max_S として定義される。
我々は、任意の$d>0$と$(X,mathcal S)$に対して、二重シャッター関数 $pi*(k)=O(kd)$ のランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-02T15:59:09Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳(メタデータ) (2021-08-19T16:16:48Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳(メタデータ) (2020-08-15T11:06:45Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。