Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards Testing Monotonicity of Distributions Over General Posets
110
0
0.0
(
0
)
Added by
Maryam Aliakbarpour
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution $p$ over a poset is monotone if, for any pair of domain elements $x$ and $y$ such that $x preceq y$, $p(x) leq p(y)$. To understand the sample complexity of this problem, we introduce a new property called bigness over a finite domain, where the distribution is $T$-big if the minimum probability for any domain element is at least $T$. We establish a lower bound of $Omega(n/log n)$ for testing bigness of distributions on domains of size $n$. We then build on these lower bounds to give $Omega(n/log{n})$ lower bounds for testing monotonicity over a matching poset of size $n$ and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem.
rate research
Read More
Acquisition of data is a difficult task in many applications of machine learning, and it is only natural that one hopes and expects the populating risk to decrease (better performance) monotonically with increasing data points. It turns out, somewhat surprisingly, that this is not the case even for the most standard algorithms such as empirical risk minimization. Non-monotonic behaviour of the risk and instability in training have manifested and appeared in the popular deep learning paradigm under the description of double descent. These problems highlight bewilderment in our understanding of learning algorithms and generalization. It is, therefore, crucial to pursue this concern and provide a characterization of such behaviour. In this paper, we derive the first consistent and risk-monotonic algorithms for a general statistical learning setting under weak assumptions, consequently resolving an open problem (Viering et al. 2019) on how to avoid non-monotonic behaviour of risk curves. Our work makes a significant contribution to the topic of risk-monotonicity, which may be key in resolving empirical phenomena such as double descent.
We propose a new setting for testing properties of distributions while receiving samples from several distributions, but few samples per distribution. Given samples from $s$ distributions, $p_1, p_2, ldots, p_s$, we design testers for the following problems: (1) Uniformity Testing: Testing whether all the $p_i$s are uniform or $epsilon$-far from being uniform in $ell_1$-distance (2) Identity Testing: Testing whether all the $p_i$s are equal to an explicitly given distribution $q$ or $epsilon$-far from $q$ in $ell_1$-distance, and (3) Closeness Testing: Testing whether all the $p_i$s are equal to a distribution $q$ which we have sample access to, or $epsilon$-far from $q$ in $ell_1$-distance. By assuming an additional natural condition about the source distributions, we provide sample optimal testers for all of these problems.
In algebraic quantum field theory the spacetime manifold is replaced by a suitable base for its topology ordered under inclusion. We explain how certain topological invariants of the manifold can be computed in terms of the base poset. We develop a theory of connections and curvature for bundles over posets in search of a formulation of gauge theories in algebraic quantum field theory.
There has been significant study on the sample complexity of testing properties of distributions over large domains. For many properties, it is known that the sample complexity can be substantially smaller than the domain size. For example, over a domain of size $n$, distinguishing the uniform distribution from distributions that are far from uniform in $ell_1$-distance uses only $O(sqrt{n})$ samples. However, the picture is very different in the presence of arbitrary noise, even when the amount of noise is quite small. In this case, one must distinguish if samples are coming from a distribution that is $epsilon$-close to uniform from the case where the distribution is $(1-epsilon)$-far from uniform. The latter task requires nearly linear in $n$ samples [Valiant 2008, Valian and Valiant 2011]. In this work, we present a noise model that on one hand is more tractable for the testing problem, and on the other hand represents a rich class of noise families. In our model, the noisy distribution is a mixture of the original distribution and noise, where the latter is known to the tester either explicitly or via sample access; the form of the noise is also known a priori. Focusing on the identity and closeness testing problems leads to the following mixture testing question: Given samples of distributions $p, q_1,q_2$, can we test if $p$ is a mixture of $q_1$ and $q_2$? We consider this general question in various scenarios that differ in terms of how the tester can access the distributions, and show that indeed this problem is more tractable. Our results show that the sample complexity of our testers are exactly the same as for the classical non-mixture case.
Polyhedral products were defined by Bahri, Bendersky, Cohen and Gitler, to be spaces obtained as unions of certain product spaces indexed by the simplices of an abstract simplicial complex. In this paper we give a very general homotopy theoretic construction of polyhedral products over arbitrary pointed posets. We show that under certain restrictions on the poset $calp$, that include all known cases, the cohomology of the resulting spaces can be computed as an inverse limit over $calp$ of the cohomology of the building blocks. This motivates the definition of an analogous algebraic construction - the polyhedral tensor product. We show that for a large family of posets, the cohomology of the polyhedral product is given by the polyhedral tensor product. We then restrict attention to polyhedral posets, a family of posets that include face posets of simplicial complexes, and simplicial posets, as well as many others. We define the Stanley-Reisner ring of a polyhedral poset and show that, like in the classical cases, these rings occur as the cohomology of certain polyhedral products over the poset in question. For any pointed poset $calp$ we construct a simplicial poset $s(calp)$, and show that if $calp$ is a polyhedral poset then polyhedral products over $calp$ coincide up to homotopy with the corresponding polyhedral products over $s(calp)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
