Fugu-MT 論文翻訳(概要): Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

論文の概要: Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

arxiv url: http://arxiv.org/abs/2311.17840v3
Date: Thu, 15 May 2025 19:04:15 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-19 14:36:10.785511
Title: Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Title（参考訳）: Sherali-AdamsによるBi-Lipschitz歪みを超えるメトリック埋め込み
Authors: Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi,
Abstract要約: 準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
参考スコア（独自算出の注目度）: 34.7582575446942
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretical computer science community has focused on bi-Lipschitz embeddings, which guarantee that every pairwise distance is approximately preserved. In contrast, alternative embedding objectives that are commonly used in practice avoid bi-Lipschitz distortion; yet these approaches have received comparatively less study in theory. In this paper, we focus on Multi-dimensional Scaling (MDS), where we are given a set of non-negative dissimilarities $\{d_{i,j}\}_{i,j\in [n]}$ over $n$ points, and the goal is to find an embedding $\{x_1,\dots,x_n\} \subset R^k$ that minimizes $$\textrm{OPT}=\min_{x}\mathbb{E}_{i,j\in [n]}\left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2.$$ Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine et. al. (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for this objective, which achieves an embedding in constant dimensional Euclidean space with cost $\textrm{OPT} +\epsilon$ in $n^2\cdot 2^{\textrm{poly}(\Delta/\epsilon)}$ time, where $\Delta$ is the aspect ratio of the input dissimilarities. For metrics that admit low-cost embeddings, $\Delta$ scales polynomially in $n$. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $\Delta$: for constant dimensional Euclidean space, we achieve a solution with cost $O(\log \Delta)\cdot \textrm{OPT}^{\Omega(1)}+\epsilon$ in time $n^{O(1)} \cdot 2^{\text{poly}((\log(\Delta)/\epsilon))}$. Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP Hierarchy, allowing us to avoid exponential dependency on the aspect ratio, which would typically result from this rounding.
Abstract（参考訳）: メトリック埋め込みはアルゴリズム設計において広く使われている手法であり、一般に ``complex'' 計量はより単純で低次元のものに埋め込まれる。歴史的に、理論計算機科学のコミュニティはバイリプシッツの埋め込みに焦点を合わせており、全てのペア距離がほぼ保存されていることを保証している。対照的に、実際に一般的に使用される別の埋め込み目的はバイリプシッツ歪みを回避しているが、これらのアプローチは理論において比較的少ない研究を受けている。本稿では,非負の相似性 $\{d_{i,j}\}_{i,j\in [n]}$ over $n$point を与えられる多次元スケーリング(MDS)に注目し,その目的は埋め込み $\{x_1,\dots,x_n\} \subset R^k$ を最小化$$$\textrm{OPT}=\min_{x}\mathbb{E}_{i,j\in [n]}\left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2.$D を求めることである。最近では、Demaine et al (arXiv:2109.11505) は、この目的に対して証明可能な保証を持つ最初の近似アルゴリズムを与え、コスト$\textrm{OPT} +\epsilon$ in $n^2\cdot 2^{\textrm{poly}(\Delta/\epsilon)} の定次元ユークリッド空間への埋め込みを実現する。低コストの埋め込みを許容するメトリクスの場合、$\Delta$は多項式を$n$でスケールする。本研究は,定次元ユークリッド空間に対する MDS に対する準多項式依存性を持つ MDS に対する最初の近似アルゴリズムを与える。コスト$O(\log \Delta)\cdot \textrm{OPT}^{\Omega(1)}+\epsilon$ in time $n^{O(1)} \cdot 2^{\text{poly}((\log(\Delta)/\epsilon))}$。我々のアルゴリズムは、シェラリ・アダムスLP階層の条件付きラウンドリングの幾何学的認識に基づく新しい解析に基づいており、通常はこのラウンドリングから生じるアスペクト比への指数的依存を避けることができる。

関連論文リスト

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文参考訳（メタデータ） (2024-06-10T17:44:11Z)
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)
Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文参考訳（メタデータ） (2023-12-24T08:27:30Z)
Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
ワッサーシュタイン空間上の有限次元多面体部分集合の理論を開発し、一階法による函数の最適化を行う。我々の主な応用は平均場変動推論の問題であり、これは分布の$pi$ over $mathbbRd$を製品測度$pistar$で近似しようとするものである。解析の副産物として,MFVIのための勾配に基づくアルゴリズムの最初のエンドツーエンド解析を求める。
論文参考訳（メタデータ） (2023-12-05T16:02:04Z)
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文参考訳（メタデータ） (2023-05-12T08:43:28Z)
Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文参考訳（メタデータ） (2023-02-03T03:19:14Z)
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)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文参考訳（メタデータ） (2022-05-23T17:59:18Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文参考訳（メタデータ） (2020-08-15T11:06:45Z)

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

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