論文の概要: Sublinear classical and quantum algorithms for general matrix games
- arxiv url: http://arxiv.org/abs/2012.06519v1
- Date: Fri, 11 Dec 2020 17:36:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-11 02:47:25.877854
- Title: Sublinear classical and quantum algorithms for general matrix games
- Title（参考訳）: 一般行列ゲームに対する線形古典的および量子的アルゴリズム
- Authors: Tongyang Li, Chunhao Wang, Shouvanik Chakrabarti, and Xiaodi Wu
- Abstract要約: 行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。
任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。
同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
- 参考スコア（独自算出の注目度）: 11.339580074756189
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate sublinear classical and quantum algorithms for matrix games, a
fundamental problem in optimization and machine learning, with provable
guarantees. Given a matrix $A\in\mathbb{R}^{n\times d}$, sublinear algorithms
for the matrix game $\min_{x\in\mathcal{X}}\max_{y\in\mathcal{Y}} y^{\top} Ax$
were previously known only for two special cases: (1) $\mathcal{Y}$ being the
$\ell_{1}$-norm unit ball, and (2) $\mathcal{X}$ being either the $\ell_{1}$-
or the $\ell_{2}$-norm unit ball. We give a sublinear classical algorithm that
can interpolate smoothly between these two cases: for any fixed $q\in (1,2]$,
we solve the matrix game where $\mathcal{X}$ is a $\ell_{q}$-norm unit ball
within additive error $\epsilon$ in time $\tilde{O}((n+d)/{\epsilon^{2}})$. We
also provide a corresponding sublinear quantum algorithm that solves the same
task in time $\tilde{O}((\sqrt{n}+\sqrt{d})\textrm{poly}(1/\epsilon))$ with a
quadratic improvement in both $n$ and $d$. Both our classical and quantum
algorithms are optimal in the dimension parameters $n$ and $d$ up to
poly-logarithmic factors. Finally, we propose sublinear classical and quantum
algorithms for the approximate Carath\'eodory problem and the $\ell_{q}$-margin
support vector machines as applications.
- Abstract（参考訳）: 最適化と機械学習の基本的な問題である行列ゲームに対する線形古典的および量子的アルゴリズムを証明可能な保証とともに検討する。
行列 $a\in\mathbb{r}^{n\times d}$ が与えられたとき、行列ゲーム $\min_{x\in\mathcal{x}}\max_{y\in\mathcal{y}} y^{\top} ax$ のサブ線形アルゴリズムは、(1) $\mathcal{y}$ が $\ell_{1}$-norm 単位球であること、(2) $\mathcal{x}$ が $\ell_{1}$ または $\ell_{2}$-norm 単位球であることの2つの特別なケースでのみ知られていた。
任意の固定された$q\in (1,2]$ に対して、$\mathcal{x}$ is a $\ell_{q}$-norm unit ball in additive error $\epsilon$ in time $\tilde{o}((n+d)/{\epsilon^{2}})$という行列ゲームを解く。
対応する部分線形量子アルゴリズムも提供し、$n$ と $d$ の2次改良により、時間$\tilde{o}((\sqrt{n}+\sqrt{d})\textrm{poly}(1/\epsilon))$ で同じタスクを解く。
古典的および量子的アルゴリズムは、多元対数因子の次元パラメータ$n$と$d$で最適である。
最後に,近似carath\eodory問題と$\ell_{q}$-marginサポートベクターマシンに対する部分線形古典および量子アルゴリズムを応用として提案する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - 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) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳（メタデータ） (2023-10-27T16:54:29Z) - Fast and Practical Quantum-Inspired Classical Algorithms for Solving
Linear Systems [11.929584800629673]
線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。
我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
論文 参考訳（メタデータ） (2023-07-13T08:46:19Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Quantum algorithms for matrix scaling and matrix balancing [9.010461408997646]
行列スケーリングと行列バランシングは、様々な応用の2つの基本的な線形代数問題である。
これらの問題に対する量子アルゴリズムのパワーと限界について検討する。
Sinkhornの行列スケーリングアルゴリズムとOsborneの行列バランスアルゴリズムの2つの古典的手法の量子的実装を提供する。
論文 参考訳（メタデータ） (2020-11-25T15:26:59Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - An improved quantum-inspired algorithm for linear regression [15.090593955414137]
量子行列反転アルゴリズムに類似した線形回帰の古典的アルゴリズムを提案する。
量子コンピュータは、このQRAMデータ構造設定において、線形回帰の最大12倍の高速化を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-15T17:58:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。