論文の概要: On Non-Interactive Simulation of Distributed Sources with Finite Alphabets
- arxiv url: http://arxiv.org/abs/2403.00989v1
- Date: Fri, 1 Mar 2024 21:23:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-18 06:39:33.678544
- Title: On Non-Interactive Simulation of Distributed Sources with Finite Alphabets
- Title（参考訳）: 有限Alphabetを用いた分散音源の非インタラクティブシミュレーションについて
- Authors: Hojat Allah Salehi, Farhad Shirani,
- Abstract要約: 本研究では,非インタラクティブソースシミュレーション(NISS)問題に対するフーリエ解析フレームワークを提案する。
2つの分散エージェントは、共同分布$P_XdYd$に従って描画されたシーケンスのペア$Xd$と$Yd$を観測する。
エージェントは、出力を$U=f_d(Xd)$と$V=g_d(Yd)$にし、目標分布を$Q_UV$に十分近いジョイント分布を生成する。
- 参考スコア（独自算出の注目度）: 2.2927938232020373
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work presents a Fourier analysis framework for the non-interactive source simulation (NISS) problem. Two distributed agents observe a pair of sequences $X^d$ and $Y^d$ drawn according to a joint distribution $P_{X^dY^d}$. The agents aim to generate outputs $U=f_d(X^d)$ and $V=g_d(Y^d)$ with a joint distribution sufficiently close in total variation to a target distribution $Q_{UV}$. Existing works have shown that the NISS problem with finite-alphabet outputs is decidable. For the binary-output NISS, an upper-bound to the input complexity was derived which is $O(\exp\operatorname{poly}(\frac{1}{\epsilon}))$. In this work, the input complexity and algorithm design are addressed in several classes of NISS scenarios. For binary-output NISS scenarios with doubly-symmetric binary inputs, it is shown that the input complexity is $\Theta(\log{\frac{1}{\epsilon}})$, thus providing a super-exponential improvement in input complexity. An explicit characterization of the simulating pair of functions is provided. For general finite-input scenarios, a constructive algorithm is introduced that explicitly finds the simulating functions $(f_d(X^d),g_d(Y^d))$. The approach relies on a novel Fourier analysis framework. Various numerical simulations of NISS scenarios with IID inputs are provided. Furthermore, to illustrate the general applicability of the Fourier framework, several examples with non-IID inputs, including entanglement-assisted NISS and NISS with Markovian inputs are provided.
- Abstract（参考訳）: 本研究では,非インタラクティブソースシミュレーション(NISS)問題に対するフーリエ解析フレームワークを提案する。
2つの分散エージェントは、共同分布$P_{X^dY^d}$に従って描画されたシーケンスのペア$X^d$と$Y^d$を観測する。
エージェントは出力を$U=f_d(X^d)$と$V=g_d(Y^d)$にし、目標分布を$Q_{UV}$に十分近いジョイント分布を生成する。
既存の研究では、有限アルファベット出力のNAS問題は決定可能であることが示されている。
二項出力NASの場合、入力複雑性の上限は$O(\exp\operatorname{poly}(\frac{1}{\epsilon}))$である。
本研究では,NASシナリオのいくつかのクラスにおいて,入力複雑性とアルゴリズム設計に対処する。
二重対称なバイナリ入力を持つバイナリ出力NASのシナリオでは、入力複雑性は$\Theta(\log{\frac{1}{\epsilon}})$である。
模擬関数対の明示的な特徴付けが提供される。
一般的な有限入力のシナリオに対して、合成関数 $(f_d(X^d),g_d(Y^d))$ を明示的に見つける構成的アルゴリズムが導入された。
このアプローチは、新しいFourier分析フレームワークに依存している。
IID入力によるNASシナリオの様々な数値シミュレーションが提供される。
さらに、フーリエフレームワークの汎用性を説明するために、絡み合い支援型NISやマルコフ入力を用いたNISなど、非IID入力のいくつかの例が提供されている。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Quantum Advantage in Non-Interactive Source Simulation [7.42972486379528]
NISSのシナリオには2つのバリエーションがある。
二項出力NASのシナリオでは、実現可能な分布の集合は互いに等しく、したがってこれらのEA-NISSのシナリオには量子的優位性はない。
非バイナリ出力NASのシナリオでは、EA-NISSでは可能だがCR-NISSでは不可能な分布が存在するという例で示される。
論文 参考訳（メタデータ） (2024-01-31T23:50:10Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。
一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
論文 参考訳（メタデータ） (2023-05-28T19:40:46Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳（メタデータ） (2022-04-14T19:10:53Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。
ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。
本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
論文 参考訳（メタデータ） (2020-07-15T02:46:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。