論文の概要: On the separation of correlation-assisted sum capacities of multiple access channels

• arxiv url: http://arxiv.org/abs/2205.13538v2
• Date: Thu, 22 Sep 2022 00:20:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-11 16:28:53.292636
• Title: On the separation of correlation-assisted sum capacities of multiple access channels
• Title（参考訳）: 多重アクセスチャネルの相関支援和容量の分離について
• Authors: Akshay Seshadri, Felix Leditzky, Vikesh Siddhu, Graeme Smith
• Abstract要約: 擬似多項式時間に対する任意の2-sender相関を計算することが可能であることを示す。 また、準多項式時間に対する任意の緩和連続相関を計算することが可能であることを示す。
• 参考スコア（独自算出の注目度）: 13.572917264310119
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The capacity of a channel characterizes the maximum rate at which information can be transmitted through the channel asymptotically faithfully. For a channel with multiple senders and a single receiver, computing its sum capacity is possible in theory, but challenging in practice because of the nonconvex optimization involved. In this work, we study the sum capacity of a family of multiple access channels (MACs) obtained from nonlocal games. For any MAC in this family, we obtain an upper bound on the sum rate that depends only on the properties of the game when allowing assistance from an arbitrary set of correlations between the senders. This approach can be used to prove separations between sum capacities when the senders are allowed to share different sets of correlations, such as classical, quantum or no-signalling correlations. We also construct a specific nonlocal game to show that the approach of bounding the sum capacity by relaxing the nonconvex optimization can give arbitrarily loose bounds. Towards a potential solution to this problem, we first prove a Lipschitz-like property for the mutual information. Using a modification of existing algorithms for optimizing Lipschitz-continuous functions, we then show that it is possible to compute the sum capacity of an arbitrary two-sender MAC to a fixed additive precision in quasi-polynomial time. We showcase our method by efficiently computing the sum capacity of a family of two-sender MACs for which one of the input alphabets has size two. Furthermore, we demonstrate with an example that our algorithm may compute the sum capacity to a higher precision than using the convex relaxation.
• Abstract（参考訳）: チャネルの容量は、チャネルを通じて情報が漸近的に忠実に送信できる最大レートを特徴付ける。 複数の送信機と単一受信機を持つチャネルでは、理論上は総和容量を計算できるが、非凸最適化が関与しているため実際は困難である。 本研究では,非ローカルゲームから得られるマルチアクセスチャネル群(MAC)の総容量について検討する。 この族内の任意のMACに対して、送り手間の任意の相関の集合からの補助を許すとき、ゲームの性質にのみ依存する和率の上限を得る。 このアプローチは、送信者が古典的、量子的、あるいは無シグナリング関係のような異なる相関の集合を共有することを許されたときの和容量の分離を証明するために用いられる。 また、特定の非局所ゲームを構築し、非凸最適化の緩和による和容量の有界化のアプローチが任意にゆるやかな境界を与えることを示す。 この問題に対する潜在的な解決に向けて、我々はまず相互情報に対するリプシッツ的性質を証明する。 リプシッツ連続関数を最適化するための既存のアルゴリズムの修正を用いて、任意の2次元MACの和容量を準多項式時間で固定加算精度に計算可能であることを示す。 入力アルファベットの1つがサイズ2の2次元MACのファミリーの和容量を効率よく計算することで,本手法を実証する。 さらに,本アルゴリズムでは,対流緩和を用いた場合よりも高い精度で和を計算できることを示す。

関連論文リスト

• One-shot Multiple Access Channel Simulation [9.271640666465364]
  製品入力に対する共有ランダム性支援多重アクセスチャネル(MAC)シミュレーションの問題点を考察する。 チャネルのスムーズな最大情報を用いて,内界と外界をほぼマッチングすることで,ワンショット通信コスト領域を特徴付ける。
  論文  参考訳（メタデータ） (2024-10-22T17:18:38Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Provable benefits of score matching [30.317535687908755]
  スコアマッチング損失が計算効率良く最適化できるような分布の自然指数族の最初の例を示す。 確率損失を最適化するためのゼロ階または1階のオラクルの設計はNPハードであることを示す。 スコアマッチング損失の最小化は、計算的かつ統計的に効率的であり、周囲の次元は複雑である。
  論文  参考訳（メタデータ） (2023-06-03T03:42:30Z)
• Clustering a Mixture of Gaussians with Unknown Covariance [4.821312633849745]
  最大極大推定に基づくMax-Cut整数プログラムを導出する。 最適な速度を得るが、2次サンプルサイズを必要とする効率的なスペクトルアルゴリズムを開発する。 我々は Max-Cut プログラムを$k$-means プログラムに一般化する。
  論文  参考訳（メタデータ） (2021-10-04T17:59:20Z)
• Distributed Quantum Faithful Simulation and Function Computation Using Algebraic Structured Measurements [8.594140167290098]
  連立量子状態に作用する量子測度を分散的にシミュレートする作業について考察する。 計算はオンザフライで行われ、チャーリーでの個々の測定結果を再構築する必要がなくなる。
  論文  参考訳（メタデータ） (2021-01-07T04:22:15Z)
• On the classical capacity of quantum Gaussian measurement [0.0]
  一般に最適なアンサンブルの平均状態のガウス性を証明する。 アンサンブルの構造に関するガウス最大化器の仮説について論じる。
  論文  参考訳（メタデータ） (2021-01-02T11:11:22Z)
• Learning Aggregation Functions [78.47770735205134]
  任意の濃度の集合に対する学習可能なアグリゲータであるLAF(Learning Aggregation Function)を紹介する。 半合成および実データを用いて,LAFが最先端の和(max-)分解アーキテクチャより優れていることを示す実験を報告する。
  論文  参考訳（メタデータ） (2020-12-15T18:28:53Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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