論文の概要: Online Lewis Weight Sampling
- arxiv url: http://arxiv.org/abs/2207.08268v1
- Date: Sun, 17 Jul 2022 19:40:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-20 04:02:17.695859
- Title: Online Lewis Weight Sampling
- Title（参考訳）: オンラインLewisウェイトサンプリング
- Authors: David P. Woodruff, Taisuke Yasuda
- Abstract要約: コーエンとペンはルイスの重量サンプリングを理論計算機科学コミュニティに導入した。
この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。
オンラインコアセット,スライディングウィンドウ,および逆ストリーミングモデルにおいて,すべての$pin(0,infty)$に対して,ほぼ最適に近い$ell_p$サブスペース埋め込みを設計する。
- 参考スコア（独自算出の注目度）: 62.38157566916501
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The seminal work of Cohen and Peng introduced Lewis weight sampling to the
theoretical computer science community, yielding fast row sampling algorithms
for approximating $d$-dimensional subspaces of $\ell_p$ up to $(1+\epsilon)$
error. Several works have extended this important primitive to other settings,
including the online coreset, sliding window, and adversarial streaming models.
However, these results are only for $p\in\{1,2\}$, and results for $p=1$
require a suboptimal $\tilde O(d^2/\epsilon^2)$ samples.
In this work, we design the first nearly optimal $\ell_p$ subspace embeddings
for all $p\in(0,\infty)$ in the online coreset, sliding window, and the
adversarial streaming models. In all three models, our algorithms store $\tilde
O(d^{1\lor(p/2)}/\epsilon^2)$ rows. This answers a substantial generalization
of the main open question of [BDMMUWZ2020], and gives the first results for all
$p\notin\{1,2\}$.
Towards our result, we give the first analysis of "one-shot'' Lewis weight
sampling of sampling rows proportionally to their Lewis weights, with sample
complexity $\tilde O(d^{p/2}/\epsilon^2)$ for $p>2$. Previously, this scheme
was only known to have sample complexity $\tilde O(d^{p/2}/\epsilon^5)$,
whereas $\tilde O(d^{p/2}/\epsilon^2)$ is known if a more sophisticated
recursive sampling is used. The recursive sampling cannot be implemented
online, thus necessitating an analysis of one-shot Lewis weight sampling. Our
analysis uses a novel connection to online numerical linear algebra.
As an application, we obtain the first one-pass streaming coreset algorithms
for $(1+\epsilon)$ approximation of important generalized linear models, such
as logistic regression and $p$-probit regression. Our upper bounds are
parameterized by a complexity parameter $\mu$ introduced by [MSSW2018], and we
show the first lower bounds showing that a linear dependence on $\mu$ is
necessary.
- Abstract（参考訳）: cohen と peng の独創的な研究は、lewis weight sampling を理論計算機科学コミュニティに導入し、$d$-dimensional subspaces を$(1+\epsilon)$ error に近似する高速列サンプリングアルゴリズムを生み出した。
この重要なプリミティブを、オンラインコアセット、スライディングウィンドウ、対向ストリーミングモデルなど、他の設定に拡張した作品もいくつかある。
しかし、これらの結果は$p\in\{1,2\}$にのみ適用され、$p=1$には$\tilde O(d^2/\epsilon^2)$サンプルが必要である。
本研究では,オンラインコアセット,スライディングウィンドウ,および対向ストリーミングモデルにおいて,すべての$p\in(0,\infty)$に対して,最も最適な$\ell_p$サブスペース埋め込みを設計する。
3つのモデルすべてにおいて、アルゴリズムは$\tilde o(d^{1\lor(p/2)}/\epsilon^2)$行を格納する。
これは[bdmmuwz2020] の主オープン問題の実質的な一般化に答え、すべての$p\notin\{1,2\}$ の最初の結果を与える。
この結果に向けて、ルイス重みに比例してサンプリング列の「ワンショット」ルイス重みサンプリングを初めて分析し、サンプル複雑性$\tilde O(d^{p/2}/\epsilon^2)$ for $p>2$とする。
以前は、このスキームはサンプル複雑性$\tilde O(d^{p/2}/\epsilon^5)$しか知られていなかったが、$\tilde O(d^{p/2}/\epsilon^2)$はより洗練された再帰的なサンプリングが用いられる場合に知られている。
再帰的なサンプリングはオンラインでは実施できないため、ワンショットのルイス加重サンプリングの分析が必要である。
本解析では,オンライン数値線形代数への新たな接続を用いる。
アプリケーションとして、ロジスティック回帰や$p$-probit回帰といった、重要な一般化線形モデルの1+\epsilon)$近似に対する最初の1パスストリーミングコアセットアルゴリズムを得る。
我々の上界は[MSSW2018]によって導入された複雑性パラメータ$\mu$でパラメータ化され、最初の下界は$\mu$への線形依存が必要であることを示す。
関連論文リスト
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry [20.068722738606287]
我々は、$(epsilon,delta)$-differential privacy(DP)の制約の下で、サドル点問題(SSP)と変分不等式(SVI)を研究する。
強いSPギャップ上の$tildeObig(frac1sqrtn + fracsqrtdnepsilonbig)$のバウンドを得る。
我々は、$の強いVI-ギャップ上の有界値を得る最初の解析を提供する。
論文 参考訳（メタデータ） (2024-11-07T21:45:05Z) - Parallel Sampling via Counting [3.6854430278041264]
任意の分布からのサンプリングを高速化するために並列化を用いる方法を示す。
我々のアルゴリズムは、$O(n2/3cdot operatornamepolylog(n,q))$ parallel timeである。
この結果は自己回帰モデルにおけるサンプリングに影響を及ぼす。
論文 参考訳（メタデータ） (2024-08-18T11:42:54Z) - Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。
我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。
ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-06-01T07:33:41Z) - Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。
また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
論文 参考訳（メタデータ） (2024-06-01T07:03:40Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - L1 Regression with Lewis Weights Subsampling [10.796388585158184]
Lewisの重みに従って$X$からサンプリングし、経験的最小化器を出力すると、1-delta$$$mの確率で成功することを示す。
また、対応する$Omega(fracdvarepsilon2 + (d + frac1varepsilon2) logfrac1delta)$も与えます。
論文 参考訳（メタデータ） (2021-05-19T23:15:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。