論文の概要: Adiabatic Quantum Feature Selection for Sparse Linear Regression
- arxiv url: http://arxiv.org/abs/2106.02357v1
- Date: Fri, 4 Jun 2021 09:14:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-07 15:14:31.636040
- Title: Adiabatic Quantum Feature Selection for Sparse Linear Regression
- Title(参考訳): Sparse Linear RegressionのためのAdiabatic Quantum Feature Selection
- Authors: Surya Sai Teja Desu, P.K. Srijith, M.V. Panduranga Rao, Naveen
Sivadasan
- Abstract要約: 合成および実世界のデータセット上でQUBOソリューションの品質を定式化し比較する。
その結果, 最適解を求める上で, 提案した断熱量子コンピューティング手法の有効性が示された。
- 参考スコア(独自算出の注目度): 0.17499351967216337
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Linear regression is a popular machine learning approach to learn and predict
real valued outputs or dependent variables from independent variables or
features. In many real world problems, its beneficial to perform sparse linear
regression to identify important features helpful in predicting the dependent
variable. It not only helps in getting interpretable results but also avoids
overfitting when the number of features is large, and the amount of data is
small. The most natural way to achieve this is by using `best subset selection'
which penalizes non-zero model parameters by adding $\ell_0$ norm over
parameters to the least squares loss. However, this makes the objective
function non-convex and intractable even for a small number of features. This
paper aims to address the intractability of sparse linear regression with
$\ell_0$ norm using adiabatic quantum computing, a quantum computing paradigm
that is particularly useful for solving optimization problems faster. We
formulate the $\ell_0$ optimization problem as a Quadratic Unconstrained Binary
Optimization (QUBO) problem and solve it using the D-Wave adiabatic quantum
computer. We study and compare the quality of QUBO solution on synthetic and
real world datasets. The results demonstrate the effectiveness of the proposed
adiabatic quantum computing approach in finding the optimal solution. The QUBO
solution matches the optimal solution for a wide range of sparsity penalty
values across the datasets.
- Abstract(参考訳): 線形回帰は、独立した変数や特徴から実際の値付き出力や依存変数を学習し、予測するための一般的な機械学習アプローチである。
多くの実世界の問題において、依存変数を予測するのに役立つ重要な特徴を特定するために、疎線形回帰を実行することは有益である。
解釈可能な結果を得るのに役立つだけでなく、機能の数が大きければオーバーフィッティングを回避し、データの量も少なくなる。
これを実現する最も自然な方法は、最小二乗損失にパラメータ上の$\ell_0$ノルムを追加することで、ゼロでないモデルパラメータをペナルティ化する 'best subset selection' を使用することである。
しかし、これは目的関数が非凸であり、少数の機能であっても難解である。
本稿では,量子コンピューティングのパラダイムである adiabatic quantum computing を用いて,分散線形回帰を $\ell_0$ norm で解くことの難しさに対処し,最適化問題を高速に解く上で特に有用である。
擬似非拘束バイナリ最適化(QUBO)問題として$\ell_0$の最適化問題を定式化し、D波断熱量子コンピュータを用いて解く。
合成および実世界のデータセット上でQUBOソリューションの品質を比較し,比較する。
その結果,提案する断熱量子コンピューティング手法が最適解の探索に有効であることが示された。
QUBOソリューションは、データセット全体にわたる広い範囲のペナルティ値に対する最適なソリューションと一致します。
関連論文リスト
- Globally Convergent Accelerated Algorithms for Multilinear Sparse
Logistic Regression with $\ell_0$-constraints [2.323238724742687]
多重線形ロジスティック回帰は多次元データ解析の強力なツールである。
本稿では,$ell_0$-MLSRを解くために,アクセラレーションされた近位置換最小値MLSRモデルを提案する。
また、APALM$+$が一階臨界点に大域収束し、クルディ・ロジャシエヴィチ性質を用いて収束を確立することも示している。
論文 参考訳(メタデータ) (2023-09-17T11:05:08Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳(メタデータ) (2023-05-28T06:33:37Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
そこで本研究では,最小限の最小残差である$tilde O(dsqrtH3K)$を計算効率よく実現したアルゴリズムを提案する。
我々の研究は線形 MDP を用いた最適 RL に対する完全な答えを提供する。
論文 参考訳(メタデータ) (2022-12-12T18:58:59Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳(メタデータ) (2022-11-16T18:59:54Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳(メタデータ) (2022-09-16T19:15:50Z) - 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) - Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。
本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文 参考訳(メタデータ) (2021-06-12T10:59:02Z) - Linear Regression by Quantum Amplitude Estimation and its Extension to
Convex Optimization [0.0]
線形回帰のための新しい量子アルゴリズムを提案し,その複雑性は$O(epsilon-1)$であり,データ点数に対する対数依存性は$N_D$である。
この方法では,データ点の和の形で計算のボトルネックを克服し,その複雑性を$N_D$に比例する。
論文 参考訳(メタデータ) (2021-05-28T00:04:11Z) - 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) - Implicit differentiation of Lasso-type models for hyperparameter
optimization [82.73138686390514]
ラッソ型問題に適した行列逆転のない効率的な暗黙微分アルゴリズムを提案する。
提案手法は,解の空間性を利用して高次元データにスケールする。
論文 参考訳(メタデータ) (2020-02-20T18:43:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。