論文の概要: Linear Regression by Quantum Amplitude Estimation and its Extension to
Convex Optimization
- arxiv url: http://arxiv.org/abs/2105.13511v2
- Date: Thu, 26 Aug 2021 01:58:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-29 04:54:16.001696
- Title: Linear Regression by Quantum Amplitude Estimation and its Extension to
Convex Optimization
- Title（参考訳）: 量子振幅推定による線形回帰と凸最適化への拡張
- Authors: Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda, Kazuyoshi Yoshino
- Abstract要約: 線形回帰のための新しい量子アルゴリズムを提案し,その複雑性は$O(epsilon-1)$であり,データ点数に対する対数依存性は$N_D$である。
この方法では,データ点の和の形で計算のボトルネックを克服し,その複雑性を$N_D$に比例する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear regression is a basic and widely-used methodology in data analysis. It
is known that some quantum algorithms efficiently perform least squares linear
regression of an exponentially large data set. However, if we obtain values of
the regression coefficients as classical data, the complexity of the existing
quantum algorithms can be larger than the classical method. This is because it
depends strongly on the tolerance error $\epsilon$: the best one among the
existing proposals is $O(\epsilon^{-2})$. In this paper, we propose the new
quantum algorithm for linear regression, which has the complexity of
$O(\epsilon^{-1})$ and keeps the logarithmic dependence on the number of data
points $N_D$. In this method, we overcome bottleneck parts in the calculation,
which take the form of the sum over data points and therefore have the
complexity proportional to $N_D$, using quantum amplitude estimation, and other
parts classically. Additionally, we generalize our method to some class of
convex optimization problems.
- Abstract（参考訳）: 線形回帰は、データ分析において基礎的で広く使われている方法論である。
いくつかの量子アルゴリズムは指数関数的に大きいデータセットの最小二乗線形回帰を効率的に行うことが知られている。
しかし、回帰係数の値を古典データとして得ると、既存の量子アルゴリズムの複雑性は古典法よりも大きくなる可能性がある。
これは、許容誤差$\epsilon$に強く依存しているためである: 既存の提案の中で最良のものは$o(\epsilon^{-2})$である。
本稿では,線形回帰のための新しい量子アルゴリズムを提案する。このアルゴリズムの複雑性は$o(\epsilon^{-1})$であり,データ点数に対する対数依存性は$n_d$である。
本研究では,データ点上の和の形式をとり,量子振幅推定などの古典的手法を用いて,n_d$ に比例する複雑性を持つ計算のボトルネック部分を克服する。
さらに,本手法を凸最適化問題のクラスに一般化する。
関連論文リスト
- Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。
特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
論文 参考訳（メタデータ） (2024-10-30T10:09:05Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Adaptive Learning for Quantum Linear Regression [10.445957451908695]
最近の研究で、線形回帰は二次二進最適化問題として定式化された。
このアプローチは、大規模なデータセットに対する計算時間のアドバンテージを約束する。
しかし、解の質は精度ベクトルの必要利用によって制限される。
本研究では,精度ベクター符号化の改良に焦点をあてる。
論文 参考訳（メタデータ） (2024-08-05T21:09:01Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear
regression via Majorization Minimization with an application to
semi-supervised graph learning [0.0]
スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。
我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
論文 参考訳（メタデータ） (2021-10-23T10:19:11Z) - Adiabatic Quantum Feature Selection for Sparse Linear Regression [0.17499351967216337]
合成および実世界のデータセット上でQUBOソリューションの品質を定式化し比較する。
その結果, 最適解を求める上で, 提案した断熱量子コンピューティング手法の有効性が示された。
論文 参考訳（メタデータ） (2021-06-04T09:14:01Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。