論文の概要: Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups
without Data-Dependent Parameters
- arxiv url: http://arxiv.org/abs/2311.14823v1
- Date: Fri, 24 Nov 2023 19:41:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-29 23:20:55.437446
- Title: Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups
without Data-Dependent Parameters
- Title（参考訳）: 線形回帰のための量子アルゴリズムの再検討:データ依存パラメータのない二次高速化
- Authors: Zhao Song, Junze Yin, Ruizhe Zhang
- Abstract要約: 我々は,$widetildeO(epsilon-1sqrtnd1.5) + Mathrmpoly(d/epsilon)$timeで動作する量子アルゴリズムを開発した。
データ依存パラメータに依存しない古典的な下界上の2次量子スピードアップを提供する。
- 参考スコア（独自算出の注目度）: 10.602399256297032
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Linear regression is one of the most fundamental linear algebra problems.
Given a dense matrix $A \in \mathbb{R}^{n \times d}$ and a vector $b$, the goal
is to find $x'$ such that
$ \| Ax' - b \|_2^2 \leq (1+\epsilon) \min_{x} \| A x - b \|_2^2 $. The best
classical algorithm takes $O(nd) + \mathrm{poly}(d/\epsilon)$ time [Clarkson
and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013]. On the other hand,
quantum linear regression algorithms can achieve exponential quantum speedups,
as shown in [Wang Phys. Rev. A 96, 012335, Kerenidis and Prakash ITCS 2017,
Chakraborty, Gily{\'e}n and Jeffery ICALP 2019]. However, the running times of
these algorithms depend on some quantum linear algebra-related parameters, such
as $\kappa(A)$, the condition number of $A$. In this work, we develop a quantum
algorithm that runs in $\widetilde{O}(\epsilon^{-1}\sqrt{n}d^{1.5}) +
\mathrm{poly}(d/\epsilon)$ time. It provides a quadratic quantum speedup in $n$
over the classical lower bound without any dependence on data-dependent
parameters. In addition, we also show our result can be generalized to multiple
regression and ridge linear regression.
- Abstract（参考訳）: 線形回帰は最も基本的な線形代数問題の1つである。
密度行列 $a \in \mathbb{r}^{n \times d}$ とベクトル $b$ が与えられると、目標は$| ax' - b \|_2^2 \leq (1+\epsilon) \min_{x} \| ax - b \|_2^2 $ となるような $x'$ を見つけることである。
最高の古典的アルゴリズムは、$O(nd) + \mathrm{poly}(d/\epsilon)$ time [Clarkson and Woodruff STOC 2013, Nelson and Nguyen FOCS 2013] を取る。
一方、量子線形回帰アルゴリズムは[wang phys]に示すように指数関数的な量子スピードアップを実現することができる。
A 96, 012335, Kerenidis and Prakash ITCS 2017, Chakraborty, Gily{\'e}n, Jeffery ICALP 2019]
しかし、これらのアルゴリズムの実行時間は、例えば$\kappa(A)$、条件番号$A$など、いくつかの量子線型代数関連パラメータに依存する。
本研究では、$\widetilde{O}(\epsilon^{-1}\sqrt{n}d^{1.5}) + \mathrm{poly}(d/\epsilon)$ timeで実行される量子アルゴリズムを開発する。
データ依存パラメータに依存せずに古典的下界上の2次量子スピードアップを$n$で提供する。
さらに,本研究の結果を多重回帰とリッジ線形回帰に一般化できることを示した。
関連論文リスト
- 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) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46: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) - Quantum Algorithms and Lower Bounds for Linear Regression with Norm
Constraints [0.0]
Lassoでは、Frank-Wolfeアルゴリズムのコスト対イテレーションを高速化することで、$d$という2次量子スピードアップが得られることを示す。
リッジにとって、最良の量子アルゴリズムは、古典的アルゴリズムと同様に$d$で線型である。
論文 参考訳（メタデータ） (2021-10-25T16:26:37Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。
任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。
同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
論文 参考訳（メタデータ） (2020-12-11T17:36:33Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。