Fugu-MT 論文翻訳(概要): Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

論文の概要: Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints

arxiv url: http://arxiv.org/abs/2110.13086v1
Date: Mon, 25 Oct 2021 16:26:37 GMT
ステータス: 処理完了
システム内更新日: 2021-10-26 18:51:10.564362
Title: Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
Title（参考訳）: 正規制約付き線形回帰のための量子アルゴリズムと下限
Authors: Yanlin Chen (QuSoft, CWI) and Ronald de Wolf (QuSoft, CWI and Amsterdam)
Abstract要約: Lassoでは、Frank-Wolfeアルゴリズムのコスト対イテレーションを高速化することで、$d$という2次量子スピードアップが得られることを示す。リッジにとって、最良の量子アルゴリズムは、古典的アルゴリズムと同様に$d$で線型である。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector $\theta\in\mathbb{R}^d$ of coefficients is constrained in either $\ell_1$-norm (for Lasso) or in $\ell_2$-norm (for Ridge). We study the complexity of quantum algorithms for finding $\varepsilon$-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of $d$ by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in $d$, as are the best classical algorithms.
Abstract（参考訳）: ラッソとリッジは機械学習と統計学の重要な最小化問題である。これらは2乗損失を持つ線型回帰のバージョンで、ベクトル $\theta\in\mathbb{R}^d$ の係数は $\ell_1$-norm (Lasso) または $\ell_2$-norm (ridge) のどちらかで制約される。これらの最小化問題に対する$\varepsilon$-minimizersを求める量子アルゴリズムの複雑さについて検討する。ラッソにとって、フランク・ウルフアルゴリズムの解法あたりのコストをスピードアップすることで、2次量子速度は$d$で得られるが、リッジにとっては最高の量子アルゴリズムは、古典的なアルゴリズムと同様に$d$で線形である。

関連論文リスト

Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文参考訳（メタデータ） (2023-12-21T18:57:54Z)
Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters [10.602399256297032]
我々は,$widetildeO(epsilon-1sqrtnd1.5) + Mathrmpoly(d/epsilon)$timeで動作する量子アルゴリズムを開発した。データ依存パラメータに依存しない古典的な下界上の2次量子スピードアップを提供する。
論文参考訳（メタデータ） (2023-11-24T19:41:28Z)
A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文参考訳（メタデータ） (2023-11-07T13:26:20Z)
Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文参考訳（メタデータ） (2023-11-06T16:00:07Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文参考訳（メタデータ） (2023-05-19T00:07:32Z)
Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文参考訳（メタデータ） (2023-02-03T03:19:14Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文参考訳（メタデータ） (2022-02-23T02:39:04Z)
Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-04-30T10:42:48Z)

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