論文の概要: Quantum algorithms for hedging and the learning of Ising models

• arxiv url: http://arxiv.org/abs/2002.06003v2
• Date: Mon, 30 Nov 2020 11:23:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-03 17:05:41.657112
• Title: Quantum algorithms for hedging and the learning of Ising models
• Title（参考訳）: ヘッジとイジングモデルの学習のための量子アルゴリズム
• Authors: Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, Miklos Santha
• Abstract要約: オンライン学習のためのパラダイムアルゴリズムは、FreundとSchapireのHedgeアルゴリズムである。 この研究は、このようなオンライン学習のための量子アルゴリズムを論理的に提示する。
• 参考スコア（独自算出の注目度）: 6.346764987071066
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A paradigmatic algorithm for online learning is the Hedge algorithm by Freund and Schapire. An allocation into different strategies is chosen for multiple rounds and each round incurs corresponding losses for each strategy. The algorithm obtains a favorable guarantee for the total losses even in an adversarial situation. This work presents quantum algorithms for such online learning in an oracular setting. For $T$ time steps and $N$ strategies, we exhibit run times of about $O \left ({\rm poly} (T) \sqrt{N} \right)$ for estimating the losses and for betting on individual strategies by sampling. In addition, we discuss a quantum analogue of the Sparsitron, a machine learning algorithm based on the Hedge algorithm. The quantum algorithm inherits the provable learning guarantees from the classical algorithm and exhibits polynomial speedups. The speedups may find relevance in finance, for example for hedging risks, and machine learning, for example for learning generalized linear models or Ising models.
• Abstract（参考訳）: オンライン学習のためのパラダイムアルゴリズムは、FreundとSchapireのHedgeアルゴリズムである。 異なる戦略への割り当てが複数のラウンドに選択され、各ラウンドは各戦略に対応する損失を負う。 このアルゴリズムは、敵対的状況であっても、総損失に対する良好な保証を得る。 本稿では,このようなオンライン学習のための量子アルゴリズムをオラキュラ環境で提示する。 T$の時間ステップと$N$の戦略に対して、損失を推定し、サンプリングによって個々の戦略に賭けるためにおよそ$O \left ({\rm poly} (T) \sqrt{N} \right)$の実行時間を示す。 さらに,Hedgeアルゴリズムに基づく機械学習アルゴリズムであるSparsitronの量子アナログについても論じる。 量子アルゴリズムは古典的アルゴリズムから証明可能な学習保証を継承し、多項式スピードアップを示す。 このスピードアップは、例えばヘッジリスクや機械学習、例えば一般化された線形モデルやイジングモデルなどの金融の関連性を見出すことができる。

関連論文リスト

• Meta-Learning from Learning Curves for Budget-Limited Algorithm Selection [11.409496019407067]
  予算制限のシナリオでは、アルゴリズム候補を慎重に選択し、それを訓練するための予算を割り当てることが不可欠である。 本稿では,エージェントが十分に訓練されるまで待たずに,最も有望なアルゴリズムを学習する過程において,エージェントが選択しなければならない新しい枠組みを提案する。
  論文  参考訳（メタデータ） (2024-10-10T08:09:58Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。 対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2024-01-02T07:46:33Z)
• 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)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• The Bayesian Learning Rule [14.141964578853262]
  我々は、多くの機械学習アルゴリズムが、emphBayesian Learning Ruleと呼ばれる単一のアルゴリズムの特定の例であることを示した。 この規則はベイズ原理から派生したもので、最適化、ディープラーニング、グラフィカルモデルといった分野から幅広いアルゴリズムが得られる。
  論文  参考訳（メタデータ） (2021-07-09T17:28:55Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• An Algorithm for Fast Supervised Learning in Variational Circuits through Simultaneous Processing of Multiple Samples [0.0]
  本稿では,複数のサンプルを並列に処理することで,変分分類器の高速な訓練を行うアルゴリズムを提案する。 提案アルゴリズムは、前方通過におけるqRAMや他の量子回路を利用する。 論文では二分分類のみについて論じるが、アルゴリズムは容易に多クラス分類に一般化できる。
  論文  参考訳（メタデータ） (2020-11-29T06:14:41Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)

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

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