論文の概要: Uniformity Testing over Hypergrids with Subcube Conditioning
- arxiv url: http://arxiv.org/abs/2302.09013v1
- Date: Fri, 17 Feb 2023 17:29:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-20 13:57:39.065580
- Title: Uniformity Testing over Hypergrids with Subcube Conditioning
- Title（参考訳）: サブキューブ条件付きハイパーグリッドの均一性試験
- Authors: Xi Chen, Cassandra Marcussen
- Abstract要約: ハイパーグレード$[m]n$でサポートされている分布の均一性をテストするアルゴリズムを提供する。
我々のアルゴリズムの分析の背後にある重要な技術的貢献は、フーリエ解析を用いて$mathbbZ_mn$以上の関数に対するピシエの不等式のロバストなバージョンの証明である。
- 参考スコア（独自算出の注目度）: 17.002754306362885
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give an algorithm for testing uniformity of distributions supported on
hypergrids $[m]^n$, which makes $\tilde{O}(\text{poly}(m)\sqrt{n}/\epsilon^2)$
queries to a subcube conditional sampling oracle. When the side length $m$ of
the hypergrid is a constant, our algorithm is nearly optimal and strengthens
the algorithm of [CCK+21] which has the same query complexity but works for
hypercubes $\{\pm 1\}^n$ only.
A key technical contribution behind the analysis of our algorithm is a proof
of a robust version of Pisier's inequality for functions over $\mathbb{Z}_m^n$
using Fourier analysis.
- Abstract（参考訳）: ハイパーグリッドでサポートされている分布の均一性をテストするアルゴリズムを$[m]^n$で提供し、サブキューブ条件付きサンプリングオラクルに$\tilde{O}(\text{poly}(m)\sqrt{n}/\epsilon^2)$クエリを生成する。
ハイパーグリッドの側長$m$が定数である場合、我々のアルゴリズムはほぼ最適であり、クエリの複雑さは同じだがハイパーキューブ$\{\pm 1\}^n$でのみ動作する[CCK+21]アルゴリズムを強化する。
我々のアルゴリズムの分析の背後にある重要な技術的貢献は、フーリエ解析を用いた$\mathbb{Z}_m^n$上の関数に対するピシエの不等式の頑健なバージョンの証明である。
関連論文リスト
- Parallel Sampling via Counting [3.6854430278041264]
任意の分布からのサンプリングを高速化するために並列化を用いる方法を示す。
我々のアルゴリズムは、$O(n2/3cdot operatornamepolylog(n,q))$ parallel timeである。
この結果は自己回帰モデルにおけるサンプリングに影響を及ぼす。
論文 参考訳（メタデータ） (2024-08-18T11:42:54Z) - 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Gaussian Mean Testing Made Simple [46.03021473600576]
a distribution $p$ on $mathbbRd$ の i.d. サンプルを考えると、このタスクは以下のケースで高い確率で区別することである。
一ページ解析によるガウス平均検定の極めて単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-25T01:59:13Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - On Robust Optimal Transport: Computational Complexity, Low-rank
Approximation, and Barycenter Computation [14.80695185915604]
我々は、最適なトランスポートの2つの頑健なバージョン、$textitRobust Semi-constrained Optimal Transport$ (RSOT) と $textitRobust Unconstrained Optimal Transport$ (ROT) を考える。
離散設定における両方の問題に対して、$widetildemathcalO(fracn2varepsilon)$timeでRSOTとROTの$varepsilon$-approximationsを生成するSinkhornベースのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-13T03:55:52Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Learning and Testing Junta Distributions with Subcube Conditioning [11.464622619555222]
本研究では,一様分布に関して,1,1n$のユンタ分布の学習と試験の問題点について検討する。
主な寄与は、サブキューブ条件付き$k$-junta分布における関連する座標を見つけるアルゴリズムである。
論文 参考訳（メタデータ） (2020-04-26T22:52:53Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。