Source author record

Karl Wimmer

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics Machine Learning Computational Complexity math.CO math.PR

Catalog footprint

Research overview

6works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

List Learning with Attribute Noise

We introduce and study the model of list learning with attribute noise. Learning with attribute noise was introduced by Shackelford and Volper (COLT 1988) as a variant of PAC learning, in which the algorithm has access to noisy examples and uncorrupted labels, and the goal is to recover an accurate hypothesis. Sloan (COLT 1988) and Goldman and Sloan (Algorithmica 1995) discovered information-theoretic limits to learning in this model, which have impeded further progress. In this article we extend the model to that of list learning, drawing inspiration from the list-decoding model in coding theory, and its recent variant studied in the context of learning. On the positive side, we show that sparse conjunctions can be efficiently list learned under some assumptions on the underlying ground-truth distribution. On the negative side, our results show that even in the list-learning model, efficient learning of parities and majorities is not possible regardless of the representation used.

preprint2020arXiv

Testing Data Binnings

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$ , both over $[n]=\{1,2,\dots,n\}$ , whether $\mathbf{p}$ equals $\mathbf{q}$ , or is significantly different from it. In this paper, we introduce the related question of 'identity up to binning,' where the reference distribution $\mathbf{q}$ is over $k \ll n$ elements: the question is then whether there exists a suitable binning of the domain $[n]$ into $k$ intervals such that, once "binned," $\mathbf{p}$ is equal to $\mathbf{q}$ . We provide nearly tight upper and lower bounds on the sample complexity of this new question, showing both a quantitative and qualitative difference with the vanilla identity testing one, and answering an open question of Canonne (2019). Finally, we discuss several extensions and related research directions.

preprint2016arXiv

Invariance principle on the slice

We prove an invariance principle for functions on a slice of the Boolean cube, which is the set of all vectors {0,1}^n with Hamming weight k. Our invariance principle shows that a low-degree, low-influence function has similar distributions on the slice, on the entire Boolean cube, and on Gaussian space. Our proof relies on a combination of ideas from analysis and probability, algebra and combinatorics. Our result imply a version of majority is stablest for functions on the slice, a version of Bourgain's tail bound, and a version of the Kindler-Safra theorem. As a corollary of the Kindler-Safra theorem, we prove a stability result of Wilson's theorem for t-intersecting families of sets, improving on a result of Friedgut.

preprint2016arXiv

Testing $k$ -Monotonicity

A Boolean $k$ -monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$ . Therefore, $k$ -monotone functions are natural generalizations of the classical monotone functions, which are the $1$ -monotone functions. Motivated by the recent interest in $k$ -monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $k$ -monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $k$ -monotone (or are close to being $k$ -monotone) from functions that are far from being $k$ -monotone. Our results include the following: - We demonstrate a separation between testing $k$ -monotonicity and testing monotonicity, on the hypercube domain $\{0,1\}^d$ , for $k\geq 3$ ; - We demonstrate a separation between testing and learning on $\{0,1\}^d$ , for $k=ω(\log d)$ : testing $k$ -monotonicity can be performed with $2^{O(\sqrt d \cdot \log d\cdot \log{1/\varepsilon})}$ queries, while learning $k$ -monotone functions requires $2^{Ω(k\cdot \sqrt d\cdot{1/\varepsilon})}$ queries (Blais et al. (RANDOM 2015)). - We present a tolerant test for functions $f\colon[n]^d\to \{0,1\}$ with complexity independent of $n$ , which makes progress on a problem left open by Berman et al. (STOC 2014). Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $[n]^d$ , and draw connections to distribution testing techniques.

preprint2014arXiv

Approximate resilience, monotonicity, and the complexity of agnostic learning

A function $f$ is $d$ -resilient if all its Fourier coefficients of degree at most $d$ are zero, i.e., $f$ is uncorrelated with all low-degree parities. We study the notion of $\mathit{approximate}$ $\mathit{resilience}$ of Boolean functions, where we say that $f$ is $α$ -approximately $d$ -resilient if $f$ is $α$ -close to a $[-1,1]$ -valued $d$ -resilient function in $\ell_1$ distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class $C$ over the uniform distribution. Roughly speaking, if all functions in a class $C$ are far from being $d$ -resilient then $C$ can be learned agnostically in time $n^{O(d)}$ and conversely, if $C$ contains a function close to being $d$ -resilient then agnostic learning of $C$ in the statistical query (SQ) framework of Kearns has complexity of at least $n^{Ω(d)}$ . This characterization is based on the duality between $\ell_1$ approximation by degree- $d$ polynomials and approximate $d$ -resilience that we establish. In particular, it implies that $\ell_1$ approximation by low-degree polynomials, known to be sufficient for agnostic learning over product distributions, is in fact necessary. Focusing on monotone Boolean functions, we exhibit the existence of near-optimal $α$ -approximately $\widetildeΩ(α\sqrt{n})$ -resilient monotone functions for all $α>0$ . Prior to our work, it was conceivable even that every monotone function is $Ω(1)$ -far from any $1$ -resilient function. Furthermore, we construct simple, explicit monotone functions based on ${\sf Tribes}$ and ${\sf CycleRun}$ that are close to highly resilient functions. Our constructions are based on a fairly general resilience analysis and amplification. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas.

preprint2014arXiv

Optimal query complexity for estimating the trace of a matrix

Given an implicit $n\times n$ matrix $A$ with oracle access $x^TA x$ for any $x\in \mathbb{R}^n$ , we study the query complexity of randomized algorithms for estimating the trace of the matrix. This problem has many applications in quantum physics, machine learning, and pattern matching. Two metrics are commonly used for evaluating the estimators: i) variance; ii) a high probability multiplicative-approximation guarantee. Almost all the known estimators are of the form $\frac{1}{k}\sum_{i=1}^k x_i^T A x_i$ for $x_i\in \mathbb{R}^n$ being i.i.d. for some special distribution. Our main results are summarized as follows. We give an exact characterization of the minimum variance unbiased estimator in the broad class of linear nonadaptive estimators (which subsumes all the existing known estimators). We also consider the query complexity lower bounds for any (possibly nonlinear and adaptive) estimators: (1) We show that any estimator requires $Ω(1/ε)$ queries to have a guarantee of variance at most $ε$ . (2) We show that any estimator requires $Ω(\frac{1}{ε^2}\log \frac{1}δ)$ queries to achieve a $(1\pmε)$ -multiplicative approximation guarantee with probability at least $1 - δ$ . Both above lower bounds are asymptotically tight. As a corollary, we also resolve a conjecture in the seminal work of Avron and Toledo (Journal of the ACM 2011) regarding the sample complexity of the Gaussian Estimator.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Karl Wimmer

Research overview

Is this your work?

6 publications

List Learning with Attribute Noise

Testing Data Binnings

Invariance principle on the slice

Testing $k$ -Monotonicity

Approximate resilience, monotonicity, and the complexity of agnostic learning

Optimal query complexity for estimating the trace of a matrix

See the researcher in context

Building this map preview

Karl Wimmer

Research overview

Is this your work?

6 publications

List Learning with Attribute Noise

Testing Data Binnings

Invariance principle on the slice

Testing kkk-Monotonicity

Approximate resilience, monotonicity, and the complexity of agnostic learning

Optimal query complexity for estimating the trace of a matrix

See the researcher in context

Building this map preview

Testing $k$ -Monotonicity