論文の概要: Quantum Algorithms for the Pathwise Lasso
- arxiv url: http://arxiv.org/abs/2312.14141v1
- Date: Thu, 21 Dec 2023 18:57:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-22 13:30:14.872289
- Title: Quantum Algorithms for the Pathwise Lasso
- Title(参考訳): パスワイズラッソのための量子アルゴリズム
- Authors: Jo\~ao F. Doriguello, Debbie Lim, Chi Seng Pun, Patrick Rebentrost,
Tushar Vaidya
- Abstract要約: 古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
- 参考スコア(独自算出の注目度): 1.9374282535132377
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: We present a novel quantum high-dimensional linear regression algorithm with
an $\ell_1$-penalty based on the classical LARS (Least Angle Regression)
pathwise algorithm. Similarly to available classical numerical algorithms for
Lasso, our quantum algorithm provides the full regularisation path as the
penalty term varies, but quadratically faster per iteration under specific
conditions. A quadratic speedup on the number of features/predictors $d$ is
possible by using the simple quantum minimum-finding subroutine from D\"urr and
Hoyer (arXiv'96) in order to obtain the joining time at each iteration. We then
improve upon this simple quantum algorithm and obtain a quadratic speedup both
in the number of features $d$ and the number of observations $n$ by using the
recent approximate quantum minimum-finding subroutine from Chen and de Wolf
(ICALP'23). As one of our main contributions, we construct a quantum unitary
based on quantum amplitude estimation to approximately compute the joining
times to be searched over by the approximate quantum minimum finding. Since the
joining times are no longer exactly computed, it is no longer clear that the
resulting approximate quantum algorithm obtains a good solution. As our second
main contribution, we prove, via an approximate version of the KKT conditions
and a duality gap, that the LARS algorithm (and therefore our quantum
algorithm) is robust to errors. This means that it still outputs a path that
minimises the Lasso cost function up to a small error if the joining times are
only approximately computed. Finally, in the model where the observations are
generated by an underlying linear model with an unknown coefficient vector, we
prove bounds on the difference between the unknown coefficient vector and the
approximate Lasso solution, which generalises known results about convergence
rates in classical statistical learning theory analysis.
- Abstract(参考訳): 古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づいて,$\ell_1$-penaltyの量子高次元線形回帰アルゴリズムを提案する。
ラッソの古典的数値アルゴリズムと同様に、我々の量子アルゴリズムは、ペナルティ項が変化するにつれて完全な正規化パスを提供するが、特定の条件下では反復ごとに2次的に高速である。
D\"urr と Hoyer (arXiv'96) の単純な量子最小フィン化サブルーチンを用いて、各イテレーションにおける結合時間を取得することで、特徴/予測子数$d$の2次高速化が可能となる。
次に、この単純な量子アルゴリズムを改善し、Chen と de Wolf (ICALP'23) の近似量子最小有限サブルーチンを用いて、特徴数 $d$ と観測数 $n$ の両方で二次的なスピードアップを得る。
我々の主な貢献の1つとして、量子振幅推定に基づく量子ユニタリを構築し、近似量子最小探索によって探索される結合時間を近似的に計算する。
結合時間はもはや正確に計算されないため、得られた近似量子アルゴリズムが良い解を得るかどうかはもはや明らかではない。
2つ目の主な貢献として、KKT条件の近似バージョンと双対性ギャップを通じて、LARSアルゴリズム(したがって我々の量子アルゴリズム)がエラーに対して堅牢であることを示す。
これは、結合時間がほぼ計算されている場合に、ラッソのコスト関数を小さな誤差まで最小化する経路を出力することを意味する。
最後に、未知の係数ベクトルを持つ基底線形モデルにより観測結果が生成されるモデルにおいて、未知の係数ベクトルと近似ラッソ解との差を証明し、古典的統計学習理論解析における収束率に関する既知の結果を一般化する。
関連論文リスト
- Two-Timescale Q-Learning with Function Approximation in Zero-Sum
Stochastic Games [31.554420227087043]
そこで本稿では,関数近似を用いた2時間スムーズなQ$学習アルゴリズムを提案する。
2時間スケールの$Q$ラーニングでは、高速スケールは勾配降下に精力的に更新され、より遅いスケールは、前回と最新の高速スケールのコンベックスを組み合わせて更新される。
重要な新規性は、遅い時間スケールの進化を捉えるために有効なリャプノフ函数を構築することである。
論文 参考訳(メタデータ) (2023-12-08T08:39:36Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
非対数確率分布からサンプリングする量子アルゴリズムを提案する。
f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
論文 参考訳(メタデータ) (2023-10-17T17:55:32Z) - Measuring the Loschmidt amplitude for finite-energy properties of the
Fermi-Hubbard model on an ion-trap quantum computer [27.84599956781646]
本稿では,現在の量子コンピュータ上での量子古典的時系列アルゴリズムの動作について検討する。
具体的には,Fermi-Hubbardモデルに対するLoschmidt振幅をQuantinuum H2-1トラップイオンデバイス上の16$site ladder geometry(32軌道)で測定する。
有限エネルギーにおける局所観測可能量の期待値を測定することにより、量子古典アルゴリズムの完全動作に対する雑音の影響を数値解析する。
論文 参考訳(メタデータ) (2023-09-19T11:59:36Z) - Quantum speedup of leverage score sampling and its application [0.0]
本稿では,レバレッジスコアの計算を高速化する量子アルゴリズムを提案する。
応用として,ベクトル解出力を用いた剛性回帰問題に対する新しい量子アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-15T14:40:18Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳(メタデータ) (2022-10-12T19:10:43Z) - Adaptive Algorithm for Quantum Amplitude Estimation [13.82667502131475]
振幅の間隔推定のための適応アルゴリズムを提案する。
提案アルゴリズムは、同じレベルの精度を達成するために、同じ数の量子クエリを使用する。
我々は,古典モンテカルロサンプリングに対する2次高速化として,オラクルクエリの数が$O(1/epsilon)$に達することを厳密に証明する。
論文 参考訳(メタデータ) (2022-06-16T21:11:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳(メタデータ) (2021-11-30T12:21:41Z) - Quantum Assisted Eigensolver [0.0]
本研究では,ハミルトニアンの基底状態と基底状態エネルギーを近似するハイブリッド量子古典アルゴリズムを提案する。
アルゴリズムの量子部分からの出力を古典コンピュータの入力として利用する。
論文 参考訳(メタデータ) (2020-09-23T08:33:18Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳(メタデータ) (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。