論文の概要: Quantum Boosting
- arxiv url: http://arxiv.org/abs/2002.05056v2
- Date: Fri, 14 Aug 2020 23:06:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-01 20:39:57.467769
- Title: Quantum Boosting
- Title（参考訳）: 量子ブースティング
- Authors: Srinivasan Arunachalam, Reevu Maity
- Abstract要約: ブースティングは、弱い不正確な機械学習アルゴリズムを強力な正確な学習アルゴリズムに変換するテクニックである。
量子技術が古典的AdaBoostの時間複雑性をいかに改善できるかを示す。
- 参考スコア（独自算出の注目度）: 8.93449755281201
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Suppose we have a weak learning algorithm $\mathcal{A}$ for a Boolean-valued
problem: $\mathcal{A}$ produces hypotheses whose bias $\gamma$ is small, only
slightly better than random guessing (this could, for instance, be due to
implementing $\mathcal{A}$ on a noisy device), can we boost the performance of
$\mathcal{A}$ so that $\mathcal{A}$'s output is correct on $2/3$ of the inputs?
Boosting is a technique that converts a weak and inaccurate machine learning
algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by
Freund and Schapire (for which they were awarded the G\"odel prize in 2003) is
one of the widely used boosting algorithms, with many applications in theory
and practice. Suppose we have a $\gamma$-weak learner for a Boolean concept
class $C$ that takes time $R(C)$, then the time complexity of AdaBoost scales
as $VC(C)\cdot poly(R(C), 1/\gamma)$, where $VC(C)$ is the $VC$-dimension of
$C$. In this paper, we show how quantum techniques can improve the time
complexity of classical AdaBoost. To this end, suppose we have a $\gamma$-weak
quantum learner for a Boolean concept class $C$ that takes time $Q(C)$, we
introduce a quantum boosting algorithm whose complexity scales as
$\sqrt{VC(C)}\cdot poly(Q(C),1/\gamma);$ thereby achieving a quadratic quantum
improvement over classical AdaBoost in terms of $VC(C)$.
- Abstract（参考訳）: 弱学習アルゴリズム $\mathcal{A}$ for a Boolean-valued problem: $\mathcal{A}$ produce hypotheses that bias $\gamma$ is small, only more than random guessing (例えば、ノイズのあるデバイスに$\mathcal{A}$を実装することによって) すると、$\mathcal{A}$のパフォーマンスを向上できるので、$\mathcal{A}$の出力は入力の2/3$で正しいか?
ブースティングは、弱い不正確な機械学習アルゴリズムを強力な正確な学習アルゴリズムに変換するテクニックである。
Freund と Schapire による AdaBoost アルゴリズム(2003年に G\"odel prize を授与された)は、理論と実践に多くの応用がある、広く使われているブースティングアルゴリズムの1つである。
AdaBoostの時間複雑性を$VC(C)\cdot poly(R(C), 1/\gamma)$とすると、$VC(C)$は$C$のVC$次元である。
本稿では,量子技術が古典的AdaBoostの時間複雑性をいかに改善するかを示す。
この目的のために、ブールの概念クラスに対する$\gamma$-weak量子学習器を$C$とすると、$Q(C)$、複雑性が$\sqrt{VC(C)}\cdot poly(Q(C),1/\gamma);$としてスケールする量子ブースティングアルゴリズムを導入する。
関連論文リスト
- Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - The Cost of Parallelizing Boosting [1.9235143628887907]
本研究は,学習用弱強化アルゴリズムの並列化コストについて検討する。
ブースティングの"軽い"並列化でさえ、トレーニングの複雑さが指数関数的に爆発的に大きくなる必要があることを示す。
論文 参考訳（メタデータ） (2024-02-23T07:03:52Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。