論文の概要: Quantum speedup of leverage score sampling and its application

• arxiv url: http://arxiv.org/abs/2301.06107v2
• Date: Sat, 16 Sep 2023 12:24:51 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-20 01:00:16.544259
• Title: Quantum speedup of leverage score sampling and its application
• Title（参考訳）: レバレッジスコアサンプリングの量子高速化とその応用
• Authors: Changpeng Shao
• Abstract要約: 本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。 応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Leverage score sampling is crucial to the design of randomized algorithms for large-scale matrix problems, while the computation of leverage scores is a bottleneck of many applications. In this paper, we propose a quantum algorithm to accelerate this useful method. The speedup is at least quadratic and could be exponential for well-conditioned matrices. We also prove some quantum lower bounds, which suggest that our quantum algorithm is close to optimal. As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs. It achieves polynomial speedups over the best classical algorithm known. In this process, we give an improved randomized algorithm for rigid regression.
• Abstract（参考訳）: レバレッジスコアのサンプリングは大規模行列問題に対するランダム化アルゴリズムの設計に不可欠であるが、レバレッジスコアの計算は多くのアプリケーションのボトルネックとなっている。 本稿では,この有用な手法を高速化する量子アルゴリズムを提案する。 スピードアップは少なくとも二次的であり、よく条件付けられた行列に対して指数関数的である。 また、いくつかの量子下界を証明し、量子アルゴリズムが最適に近いことを示唆する。 応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。 既知の最良の古典的アルゴリズムよりも多項式の高速化を実現する。 この過程で、剛性回帰のための改良されたランダム化アルゴリズムを与える。

関連論文リスト

• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [8.147652597876862]
  線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
  論文  参考訳（メタデータ） (2023-07-13T08:46:19Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Tight Bound for Estimating Expectation Values from a System of Linear Equations [0.0]
  線形方程式系 (SLEP) は複素可逆行列$A$によって定義される。 ここで、$x$ は方程式 $Ax = b$ の解ベクトルである。 この設定におけるSLEPの量子クエリの複雑さは$Theta(alpha/epsilon)$であることを示す。
  論文  参考訳（メタデータ） (2021-11-20T00:10:51Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
  そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。 この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
  論文  参考訳（メタデータ） (2021-03-18T15:12:44Z)
• An improved quantum-inspired algorithm for linear regression [15.090593955414137]
  量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。 量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-15T17:58:25Z)
• 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)

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

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