We study the tolerant testing problem for high-dimensional samplers. Given as input two samplers $\mathcal{P}$ and $\mathcal{Q}$ over the $n$-dimensional space $\{0,1\}^n$, and two parameters $\varepsilon_2 > \varepsilon_1$, the goal of tolerant testing is to test whether the distributions generated by $\mathcal{P}$ and $\mathcal{Q}$ are $\varepsilon_1$-close or $\varepsilon_2$-far. Since exponential lower bounds (in $n$) are known for the problem in the standard sampling model, research has focused on models where one can draw \textit{conditional} samples. Among these models, \textit{subcube conditioning} ($\mathsf{SUBCOND}$), which allows conditioning on arbitrary subcubes of the domain, holds the promise of widespread adoption in practice owing to its ability to capture the natural behavior of samplers in constrained domains. To translate the promise into practice, we need to overcome two crucial roadblocks for tests based on $\mathsf{SUBCOND}$: the prohibitively large number of queries ($\tilde{\mathcal{O}}(n^5/\varepsilon_2^5)$) and limitation to non-tolerant testing (i.e., $\varepsilon_1 = 0$). The primary contribution of this work is to overcome the above challenges: we design a new tolerant testing methodology (i.e., $\varepsilon_1 \geq 0$) that allows us to significantly improve the upper bound to $\tilde{\mathcal{O}}(n^3/(\varepsilon_2-\varepsilon_1)^5)$.
相關內容
We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with $m$ edges and polynomially bounded integral demands, costs, and capacities. As a consequence, we obtain the first running time improvement for deterministic algorithms that compute maximum-flow in graphs with polynomial bounded capacities since the work of Goldberg-Rao [J.ACM '98]. Our algorithm builds on the framework of Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] that computes an optimal flow by computing a sequence of $m^{1+o(1)}$-approximate undirected minimum-ratio cycles. We develop a deterministic dynamic graph data-structure to compute such a sequence of minimum-ratio cycles in an amortized $m^{o(1)}$ time per edge update. Our key technical contributions are deterministic analogues of the vertex sparsification and edge sparsification components of the data-structure from Chen et al. For the vertex sparsification component, we give a method to avoid the randomness in Chen et al. which involved sampling random trees to recurse on. For the edge sparsification component, we design a deterministic algorithm that maintains an embedding of a dynamic graph into a sparse spanner. We also show how our dynamic spanner can be applied to give a deterministic data structure that maintains a fully dynamic low-stretch spanning tree on graphs with polynomially bounded edge lengths, with subpolynomial average stretch and subpolynomial amortized time per edge update.
It is shown in this note that approximating the number of independent sets in a $k$-uniform linear hypergraph with maximum degree at most $\Delta$ is NP-hard if $\Delta\geq 5\cdot 2^{k-1}+1$. This confirms that for the relevant sampling and approximate counting problems, the regimes on the maximum degree where the state-of-the-art algorithms work are tight, up to some small factors. These algorithms include: the approximate sampler and randomised approximation scheme by Hermon, Sly and Zhang (RSA, 2019), the perfect sampler by Qiu, Wang and Zhang (ICALP, 2022), and the deterministic approximation scheme by Feng, Guo, Wang, Wang and Yin (FOCS, 2023).
A combinatorial problem concerning the maximum size of the (hamming) weight set of an $[n,k]_q$ linear code was recently introduced. Codes attaining the established upper bound are the Maximum Weight Spectrum (MWS) codes. Those $[n,k]_q $ codes with the same weight set as $ \mathbb{F}_q^n $ are called Full Weight Spectrum (FWS) codes. FWS codes are necessarily ``short", whereas MWS codes are necessarily ``long". For fixed $ k,q $ the values of $ n $ for which an $ [n,k]_q $-FWS code exists are completely determined, but the determination of the minimum length $ M(H,k,q) $ of an $ [n,k]_q $-MWS code remains an open problem. The current work broadens discussion first to general coordinate-wise weight functions, and then specifically to the Lee weight and a Manhattan like weight. In the general case we provide bounds on $ n $ for which an FWS code exists, and bounds on $ n $ for which an MWS code exists. When specializing to the Lee or to the Manhattan setting we are able to completely determine the parameters of FWS codes. As with the Hamming case, we are able to provide an upper bound on $ M(\mathcal{L},k,q) $ (the minimum length of Lee MWS codes), and pose the determination of $ M(\mathcal{L},k,q) $ as an open problem. On the other hand, with respect to the Manhattan weight we completely determine the parameters of MWS codes.
A differentially private computation often begins with a bound on a $d$-dimensional statistic's $\ell_p$ sensitivity. The $K$-norm mechanism can yield more accurate additive noise by using a statistic-specific (and possibly non-$\ell_p$) norm. However, sampling such mechanisms requires sampling from the corresponding norm balls. These are $d$-dimensional convex polytopes, and the fastest known general algorithm for approximately sampling such polytopes takes time $\tilde O(d^{3+\omega})$, where $\omega \geq 2$ is the matrix multiplication exponent. For the simple problems of sum and ranked vote, this paper constructs samplers that run in time $\tilde O(d^2)$. More broadly, we suggest that problem-specific $K$-norm mechanisms may be an overlooked practical tool for private additive noise.
Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the \emph{determinant maximization} problem is to pick $k$ vectors with the maximum volume. Determinant maximization is the MAP-inference task for determinantal point processes (DPP) and has recently received considerable attention for modeling diversity. As most applications for the problem use large amounts of data, this problem has been studied in the relevant \textit{composable coreset} setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19] showed that one can get composable coresets with optimal approximation factor of $\tilde O(k)^k$ for the problem, and that a local search algorithm achieves an almost optimal approximation guarantee of $O(k)^{2k}$. In this work, we show that the widely-used Greedy algorithm also provides composable coresets with an almost optimal approximation factor of $O(k)^{3k}$, which improves over the previously known guarantee of $C^{k^2}$, and supports the prior experimental results showing the practicality of the greedy algorithm as a coreset. Our main result follows by showing a local optimality property for Greedy: swapping a single point from the greedy solution with a vector that was not picked by the greedy algorithm can increase the volume by a factor of at most $(1+\sqrt{k})$. This is tight up to the additive constant $1$. Finally, our experiments show that the local optimality of the greedy algorithm is even lower than the theoretical bound on real data sets.
We study the following two related problems. The first is to determine to what error an arbitrary zonoid in $\mathbb{R}^{d+1}$ can be approximated in the Hausdorff distance by a sum of $n$ line segments. The second is to determine optimal approximation rates in the uniform norm for shallow ReLU$^k$ neural networks on their variation spaces. The first of these problems has been solved for $d\neq 2,3$, but when $d=2,3$ a logarithmic gap between the best upper and lower bounds remains. We close this gap, which completes the solution in all dimensions. For the second problem, our techniques significantly improve upon existing approximation rates when $k\geq 1$, and enable uniform approximation of both the target function and its derivatives.
We consider the problem of identifying, from statistics, a distribution of discrete random variables $X_1,\ldots,X_n$ that is a mixture of $k$ product distributions. The best previous sample complexity for $n \in O(k)$ was $(1/\zeta)^{O(k^2 \log k)}$ (under a mild separation assumption parameterized by $\zeta$). The best known lower bound was $\exp(\Omega(k))$. It is known that $n\geq 2k-1$ is necessary and sufficient for identification. We show, for any $n\geq 2k-1$, how to achieve sample complexity and run-time complexity $(1/\zeta)^{O(k)}$. We also extend the known lower bound of $e^{\Omega(k)}$ to match our upper bound across a broad range of $\zeta$. Our results are obtained by combining (a) a classic method for robust tensor decomposition, (b) a novel way of bounding the condition number of key matrices called Hadamard extensions, by studying their action only on flattened rank-1 tensors.
We present a generalisation of the theory of quantitative algebras of Mardare, Panangaden and Plotkin where (i) the carriers of quantitative algebras are not restricted to be metric spaces and can be arbitrary fuzzy relations or generalised metric spaces, and (ii) the interpretations of the algebraic operations are not required to be nonexpansive. Our main results include: a novel sound and complete proof system, the proof that free quantitative algebras always exist, the proof of strict monadicity of the induced Free-Forgetful adjunction, the result that all monads (on fuzzy relations) that lift finitary monads (on sets) admit a quantitative equational presentation.
We explore the space of matrix-generated (0, m, 2)-nets and (0, 2)-sequences in base 2, also known as digital dyadic nets and sequences. In computer graphics, they are arguably leading the competition for use in rendering. We provide a complete characterization of the design space and count the possible number of constructions with and without considering possible reorderings of the point set. Based on this analysis, we then show that every digital dyadic net can be reordered into a sequence, together with a corresponding algorithm. Finally, we present a novel family of self-similar digital dyadic sequences, to be named $\xi$-sequences, that spans a subspace with fewer degrees of freedom. Those $\xi$-sequences are extremely efficient to sample and compute, and we demonstrate their advantages over the classic Sobol (0, 2)-sequence.
Join-preserving maps on the discrete time scale $\omega^+$, referred to as time warps, have been proposed as graded modalities that can be used to quantify the growth of information in the course of program execution. The set of time warps forms a simple distributive involutive residuated lattice -- called the time warp algebra -- that is equipped with residual operations relevant to potential applications. In this paper, we show that although the time warp algebra generates a variety that lacks the finite model property, it nevertheless has a decidable equational theory. We also describe an implementation of a procedure for deciding equations in this algebra, written in the OCaml programming language, that makes use of the Z3 theorem prover.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191