論文の概要: Approximation algorithms for noncommutative constraint satisfaction
problems
- arxiv url: http://arxiv.org/abs/2312.16765v1
- Date: Thu, 28 Dec 2023 01:22:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-29 18:03:25.004023
- Title: Approximation algorithms for noncommutative constraint satisfaction
problems
- Title(参考訳): 非可換制約満足問題に対する近似アルゴリズム
- Authors: Eric Culf, Hamoon Mousavi, and Taro Spirig
- Abstract要約: 我々は制約満足度問題(CSP)の作用素、あるいは非可換変量について研究する。
非可換なCSPに対する近似アルゴリズムを設計するためのフレームワークを提案する。
この研究は、より広い非可換 CSP のクラスに対する近似比を確立する最初のものである。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study operator - or noncommutative - variants of constraint satisfaction
problems (CSPs). These higher-dimensional variants are a core topic of
investigation in quantum information, where they arise as nonlocal games and
entangled multiprover interactive proof systems (MIP*). The idea of
higher-dimensional relaxations of CSPs is also important in the classical
literature. For example since the celebrated work of Goemans and Williamson on
Max-Cut, higher dimensional vector relaxations have been central in the design
of approximation algorithms for classical CSPs.
We introduce a framework for designing approximation algorithms for
noncommutative CSPs. Prior to this work Max-$2$-Lin$(k)$ was the only family of
noncommutative CSPs known to be efficiently solvable. This work is the first to
establish approximation ratios for a broader class of noncommutative CSPs.
In the study of classical CSPs, $k$-ary decision variables are often
represented by $k$-th roots of unity, which generalise to the noncommutative
setting as order-$k$ unitary operators. In our framework, using representation
theory, we develop a way of constructing unitary solutions from SDP
relaxations, extending the pioneering work of Tsirelson on XOR games. Then, we
introduce a novel rounding scheme to transform these solutions to order-$k$
unitaries. Our main technical innovation here is a theorem guaranteeing that,
for any set of unitary operators, there exists a set of order-$k$ unitaries
that closely mimics it. As an integral part of the rounding scheme, we prove a
random matrix theory result that characterises the distribution of the relative
angles between eigenvalues of random unitaries using tools from free
probability.
- Abstract(参考訳): 本研究では,制約満足度問題 (CSP) の演算子-あるいは非可換変量について検討する。
これらの高次元の変種は、非局所ゲームや絡み合ったマルチプロペラ対話型証明システム(MIP*)として生じる量子情報のコアトピックである。
cspsの高次元緩和の概念は古典文学においても重要である。
例えば、Goemans と Williamson の Max-Cut での有名な業績から、高次元ベクトル緩和は古典的 CSP の近似アルゴリズムの設計の中心となっている。
非可換なCSPに対する近似アルゴリズムを設計するためのフレームワークを提案する。
この研究に先立ち、Max-$2$-Lin$(k)$は効率よく解けることが知られている非可換 CSP の族である。
この研究は、より広範な非可換 CSP の近似比を確立する最初のものである。
古典的なcspの研究において、$k$-ary 決定変数は、しばしばユニティの$k$-th ルートで表され、これは非可換な設定をorder-$k$ユニタリ作用素として一般化する。
本稿では,表現論を用いて,SDP緩和から一元解を構築する手法を開発し,XORゲーム上でのTsirelsonの先駆的な研究を拡張した。
次に、これらの解をオーダー-$k$ユニタリに変換する新しい丸めスキームを導入する。
ここでの我々の主要な技術的革新は、任意のユニタリ作用素の集合に対して、それを密接に模倣する位数-$k$のユニタリが存在するという定理である。
円周スキームの積分部として,自由確率のツールを用いて,ランダムユニタリの固有値間の相対角分布を特徴付けるランダム行列理論を証明した。
関連論文リスト
- Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions [18.086061048484616]
平衡問題の幅広いクラスをモデル化した有限サム単調包含問題について検討する。
我々の主な貢献は、複雑性の保証を改善するために分散還元を利用する古典的ハルパーン反復の変種である。
我々は、この複雑さが単調なリプシッツ設定では改善できないと論じる。
論文 参考訳(メタデータ) (2023-10-04T17:24:45Z) - Sample-Efficient Reinforcement Learning for POMDPs with Linear Function
Approximations [130.66193083412716]
本稿では,関数近似と部分観測可能性の緊張に対処する。
最適ポリシーと値関数は有限メモリヒルベルト・ベルマン作用素の列によって特徴づけられることを示す。
本稿では、カーネル空間(RKHS)の埋め込みを再現することで、これらの演算子の楽観的な推定値を構成するRLアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-04-20T21:15:38Z) - PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。
我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。
これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
論文 参考訳(メタデータ) (2022-01-19T22:21:21Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes [22.07834608976826]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳(メタデータ) (2021-10-21T18:05:40Z) - Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。
楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。
我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
論文 参考訳(メタデータ) (2021-10-21T15:25:15Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳(メタデータ) (2021-10-07T09:38:15Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳(メタデータ) (2021-07-03T23:17:26Z) - Nonparametric approximation of conditional expectation operators [0.3655021726150368]
最小の仮定の下で、$[Pf](x) := mathbbE[f(Y) mid X = x ]$ で定義される$L2$-operatorの近似について検討する。
我々は、再生されたカーネル空間上で作用するヒルベルト・シュミット作用素により、作用素ノルムにおいて$P$が任意に適切に近似できることを証明した。
論文 参考訳(メタデータ) (2020-12-23T19:06:12Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳(メタデータ) (2020-10-12T17:41:44Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。