論文の概要: Terminal Embeddings in Sublinear Time
- arxiv url: http://arxiv.org/abs/2110.08691v1
- Date: Sun, 17 Oct 2021 00:50:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-19 15:39:09.817426
- Title: Terminal Embeddings in Sublinear Time
- Title（参考訳）: 部分線形時間における端子埋め込み
- Authors: Yeshwanth Cherapanamjeri, Jelani Nelson
- Abstract要約: 我々は、$T$を前処理して、サブ線形時間における$qinmathbbRd$の端末埋め込み画像の計算をサポートする、ほぼ線形空間のデータ構造を得る方法を示す。
この研究の主な貢献は、端末の埋め込みを計算するための新しいデータ構造を提供することです。
- 参考スコア（独自算出の注目度）: 11.929584800629675
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a {\it
terminal embedding} from one metric space $(X,d_X)$ to another $(Y,d_Y)$ with a
set of designated terminals $T\subset X$. Such an embedding $f$ is said to have
distortion $\rho\ge 1$ if $\rho$ is the smallest value such that there exists a
constant $C>0$ satisfying
\begin{equation*}
\forall x\in T\ \forall q\in X,\ C d_X(x, q) \le d_Y(f(x), f(q)) \le C \rho
d_X(x, q) .
\end{equation*}
In the case that $X,Y$ are both Euclidean metrics with $Y$ being
$m$-dimensional, recently (Narayanan, Nelson 2019), following work of
(Mahabadi, Makarychev, Makarychev, Razenshteyn 2018), showed that distortion
$1+\epsilon$ is achievable via such a terminal embedding with $m =
O(\epsilon^{-2}\log n)$ for $n := |T|$. This generalizes the
Johnson-Lindenstrauss lemma, which only preserves distances within $T$ and not
to $T$ from the rest of space. The downside is that evaluating the embedding on
some $q\in \mathbb{R}^d$ required solving a semidefinite program with
$\Theta(n)$ constraints in $m$ variables and thus required some superlinear
$\mathrm{poly}(n)$ runtime. Our main contribution in this work is to give a new
data structure for computing terminal embeddings. We show how to pre-process
$T$ to obtain an almost linear-space data structure that supports computing the
terminal embedding image of any $q\in\mathbb{R}^d$ in sublinear time
$n^{1-\Theta(\epsilon^2)+o(1)} + dn^{o(1)}$. To accomplish this, we leverage
tools developed in the context of approximate nearest neighbor search.
- Abstract（参考訳）: 最近 (elkin, filtser, neiman 2017) は、ある計量空間 $(x,d_x)$ から別の $(y,d_y)$ への、指定された端末のセット $t\subset x$ への埋め込みの概念を導入した。
そのような埋め込み $f$ が歪み $\rho\ge 1$ を持つとは、$\rho$ が定数 $C>0$ が存在して、x\in T\ \forall q\in X,\ C d_X(x, q) \le d_Y(f(x), f(q)) \le C \rho d_X(x, q) を満たすような最小値である。
\end{equation*} $X,Y$ がともに Euclidean 計量で$Y$ が $m$-dimensional である場合(Narayananan, Nelson 2019)、(Mahabadi, Makarychev, Makarychev, Razenshteyn 2018)、$m = O(\epsilon^{-2}\log n)$ for $n := |T|$ で埋め込んだような端末で 1+\epsilon$ の歪みが達成可能であることを示した。
これはジョンソン・リンデンシュトラウス補題を一般化し、これは空間の残りの部分から$T$の範囲内でしか距離を保たない。
欠点は、$q\in \mathbb{r}^d$ の埋め込みを評価するには$m$変数の$\theta(n)$制約で半定義のプログラムを解く必要があり、従って超線形$\mathrm{poly}(n)$ ランタイムが必要となることである。
この研究の主な貢献は、端末埋め込みを計算するための新しいデータ構造を提供することです。
我々は,準線形時間 $n^{1-\theta(\epsilon^2)+o(1)} + dn^{o(1)}$ における任意の$q\in\mathbb{r}^d$ の端末埋め込み画像の計算をサポートする略線形空間データ構造を得るために,$t$ を前処理する方法を示す。
これを実現するために,近い近傍探索の文脈で開発されたツールを活用する。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳（メタデータ） (2023-11-17T18:01:58Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Sparse Dimensionality Reduction Revisited [13.170012290527017]
スパースジョンソン・リンデンシュトラウス変換は次元還元の中心的な手法の一つである。
疎な埋め込みを再検討し、下界の抜け穴を同定する。
また,最適埋め込み次元に対する最適半空間埋め込みの空隙性も改善する。
論文 参考訳（メタデータ） (2023-02-13T08:01:25Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳（メタデータ） (2023-02-01T05:22:40Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Approximate Maximum Halfspace Discrepancy [6.35821487778241]
範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。
数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
論文 参考訳（メタデータ） (2021-06-25T19:14:45Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳（メタデータ） (2020-05-22T16:55:01Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。