論文の概要: A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee

• arxiv url: http://arxiv.org/abs/2302.00248v1
• Date: Wed, 1 Feb 2023 05:22:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-02 13:25:15.066214
• Title: A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee
• Title（参考訳）: $\ell_\infty$ 保証付き高速回帰に対する最適に近いバウンド
• Authors: Zhao Song and Mingquan Ye and Junze Yin and Lichen Zhang
• Abstract要約: 行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。 このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。 我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
• 参考スコア（独自算出の注目度）: 16.409210914237086
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Given a matrix $A\in \mathbb{R}^{n\times d}$ and a vector $b\in \mathbb{R}^n$, we consider the regression problem with $\ell_\infty$ guarantees: finding a vector $x'\in \mathbb{R}^d$ such that $ \|x'-x^*\|_\infty \leq \frac{\epsilon}{\sqrt{d}}\cdot \|Ax^*-b\|_2\cdot \|A^\dagger\|$ where $x^*=\arg\min_{x\in \mathbb{R}^d}\|Ax-b\|_2$. One popular approach for solving such $\ell_2$ regression problem is via sketching: picking a structured random matrix $S\in \mathbb{R}^{m\times n}$ with $m\ll n$ and $SA$ can be quickly computed, solve the ``sketched'' regression problem $\arg\min_{x\in \mathbb{R}^d} \|SAx-Sb\|_2$. In this paper, we show that in order to obtain such $\ell_\infty$ guarantee for $\ell_2$ regression, one has to use sketching matrices that are dense. To the best of our knowledge, this is the first user case in which dense sketching matrices are necessary. On the algorithmic side, we prove that there exists a distribution of dense sketching matrices with $m=\epsilon^{-2}d\log^3(n/\delta)$ such that solving the sketched regression problem gives the $\ell_\infty$ guarantee, with probability at least $1-\delta$. Moreover, the matrix $SA$ can be computed in time $O(nd\log n)$. Our row count is nearly-optimal up to logarithmic factors, and significantly improves the result in [Price, Song and Woodruff, ICALP'17], in which a super-linear in $d$ rows, $m=\Omega(\epsilon^{-2}d^{1+\gamma})$ for $\gamma=\Theta(\sqrt{\frac{\log\log n}{\log d}})$ is required. We also develop a novel analytical framework for $\ell_\infty$ guarantee regression that utilizes the Oblivious Coordinate-wise Embedding (OCE) property introduced in [Song and Yu, ICML'21]. Our analysis is arguably much simpler and more general than [Price, Song and Woodruff, ICALP'17], and it extends to dense sketches for tensor product of vectors.
• Abstract（参考訳）: 行列 $A\in \mathbb{R}^{n\times d}$ とベクトル $b\in \mathbb{R}^n$ が与えられたとき、この回帰問題を $\ell_\infty$ で保証する: ベクトル $x'-x^*\|_\infty \leq \frac {\epsilon}{\sqrt{d}}\cdot \|Ax^*-b\|_2\cdot \|Ax^*-b\|_2\cdot \|A^\dagger\|$ ここで $x^*=\arg\min_{x\in \mathbb{R}^d}\|Ax-b\|$ を求める。 構造化ランダム行列 $S\in \mathbb{R}^{m\times n}$ を$m\ll n$ で、$SA$ を素早く計算し、 `sketched'' の回帰問題 $\arg\min_{x\in \mathbb{R}^d} \|SAx-Sb\|_2$ を解く。 本稿では,そのような$\ell_\infty$を$\ell_2$レグレッションで得るためには,密度の高いスケッチ行列を用いる必要があることを示す。 私たちの知る限りでは、これは密集したスケッチ行列を必要とする最初のユーザーケースです。 アルゴリズム側では、スケッチされた回帰問題を解くために、$m=\epsilon^{-2}d\log^3(n/\delta)$ の密なスケッチ行列の分布があることを証明し、少なくとも 1-\delta$ の確率で$\ell_\infty$ の保証を与える。 さらに、行列 $sa$ は時間 $o(nd\log n)$ で計算できる。 Price, Song and Woodruff, ICALP'17] では$d$ rows, $m=\Omega(\epsilon^{-2}d^{1+\gamma})$ for $\gamma=\Theta(\sqrt{\frac{\log n}{\log d}})$が要求される。 また,[Song and Yu, ICML'21] で導入された OCE 特性を利用した $\ell_\infty$ guarantee regression の新たな解析フレームワークも開発している。 我々の解析は[Price, Song and Woodruff, ICALP'17] よりもはるかに単純で一般的であり、ベクトルのテンソル積に対する濃密なスケッチにまで拡張される。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
  未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。 我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。 このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
  論文  参考訳（メタデータ） (2024-02-22T02:20:24Z)
• A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time [7.613259578185218]
  我々は、一層注意ネットワーク目的関数 $L(X,Y) の証明可能な保証を提供することに注力する。 多層LCMネットワークでは、mathbbRn×d2$の行列$Bを層の出力と見なすことができる。 損失関数をトレーニングする反復アルゴリズムを$L(X,Y)$ up $epsilon$で、$widetildeO( (cal T_mathrmmat(n,d) + dで実行される。
  論文  参考訳（メタデータ） (2023-09-14T04:23:40Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• 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)

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

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