論文の概要: Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent

• arxiv url: http://arxiv.org/abs/2411.03925v1
• Date: Wed, 06 Nov 2024 13:57:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-07 19:24:10.988083
• Title: Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent
• Title（参考訳）: 縮退したグラディエントDescentを用いたスパースオンライン学習のための量子アルゴリズム
• Authors: Debbie Lim, Yixian Qiu, Patrick Rebentrost, Qisheng Wang,
• Abstract要約: ロジスティック回帰、SVM(Support Vector Machine)、最小二乗は統計学とコンピュータ科学のコミュニティでよく研究されている手法である。 我々は,ロジスティック回帰,SVM,最小二乗の量子スパースオンライン学習アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 2.148134736383802
• License:
• Abstract: Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of \hyperlink{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of $O(1/\sqrt{T})$, where $T$ is the number of iterations.
• Abstract（参考訳）: ロジスティック回帰、SVM(Support Vector Machine)、最小二乗は統計学とコンピュータ科学のコミュニティでよく研究されている手法であり、様々な実用的応用がある。 リアルタイムに到着する高次元データは、スパースソリューションを生成するオンライン学習アルゴリズムを設計する。 ハイパーリンク{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} のセミナルな研究は、散発勾配降下による疎度を得る方法を開発し、ほぼ最適のオンライン後悔境界を示す。 本手法により,ロジスティック回帰,SVM,最小二乗の量子スパースオンライン学習アルゴリズムを開発した。 入力に対する効率的な量子アクセスが与えられた場合、問題の次元に関する時間的複雑さの二次的なスピードアップは達成可能である一方で、$O(1/\sqrt{T})$の後悔を保ちながら、$T$は反復数である。

関連論文リスト

• Unified Gradient-Based Machine Unlearning with Remain Geometry Enhancement [29.675650285351768]
  深層ニューラルネットワークのプライバシーと信頼性を高めるために、機械学習(MU)が登場した。 近似MUは大規模モデルの実用的手法である。 本稿では,最新の学習方向を暗黙的に近似する高速スローパラメータ更新手法を提案する。
  論文  参考訳（メタデータ） (2024-09-29T15:17:33Z)
• Variance Reduced Online Gradient Descent for Kernelized Pairwise Learning with Limited Memory [19.822215548822882]
  オンラインのペアワイズ学習を扱うために、オンライン勾配降下アルゴリズム(OGD)が提案されている。 OGDアルゴリズムの最近の進歩は、オンライン勾配の計算の複雑さを減らし、O(T)$未満の複雑さを達成し、たとえ$O(1)$であるとしても達成することを目的としている。 本研究では,カーネルのオンラインペアワイズ学習に拡張し,サブ線形後悔を改善したメモリOGDアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-10T09:50:54Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Optimality of Robust Online Learning [4.21768682940933]
  再生カーネルヒルベルト空間(RKHS)上の回帰のために,ロバストな損失関数$mathcalL_sigma$を用いたオンライン学習アルゴリズムについて検討する。 提案アルゴリズムは,条件付き平均関数の推定を目的としたオンライン最小二乗回帰の頑健な代替手段である。
  論文  参考訳（メタデータ） (2023-04-20T03:00:33Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。 しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
  論文  参考訳（メタデータ） (2022-10-23T11:58:05Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• SHINE: SHaring the INverse Estimate from the forward pass for bi-level optimization and implicit models [15.541264326378366]
  近年,深層ニューラルネットワークの深度を高める手法として暗黙の深度学習が登場している。 トレーニングは双レベル問題として実行され、その計算複雑性は巨大なヤコビ行列の反復反転によって部分的に駆動される。 本稿では,この計算ボトルネックに対処する新たな手法を提案する。
  論文  参考訳（メタデータ） (2021-06-01T15:07:34Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。 私たちの手法は、既存のベースラインよりも数千倍も高速です。 我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
  論文  参考訳（メタデータ） (2021-05-21T16:20:07Z)

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

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