Source author record

Jonathan Weed

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

ResearcherUnclaimed source record

math.CO Computational Complexity Computer Science and Game Theory Discrete Mathematics Information Theory Machine Learning math.AG math.IT math.ST Statistics Theory

Catalog footprint

Research overview

5works

10topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Convergence of Smoothed Empirical Measures with Applications to Entropy Estimation

This paper studies convergence of empirical measures smoothed by a Gaussian kernel. Specifically, consider approximating $P\ast\mathcal{N}_σ$ , for $\mathcal{N}_σ\triangleq\mathcal{N}(0,σ^2 \mathrm{I}_d)$ , by $\hat{P}_n\ast\mathcal{N}_σ$ , where $\hat{P}_n$ is the empirical measure, under different statistical distances. The convergence is examined in terms of the Wasserstein distance, total variation (TV), Kullback-Leibler (KL) divergence, and $χ^2$ -divergence. We show that the approximation error under the TV distance and 1-Wasserstein distance ( $\mathsf{W}_1$ ) converges at rate $e^{O(d)}n^{-\frac{1}{2}}$ in remarkable contrast to a typical $n^{-\frac{1}{d}}$ rate for unsmoothed $\mathsf{W}_1$ (and $d\ge 3$ ). For the KL divergence, squared 2-Wasserstein distance ( $\mathsf{W}_2^2$ ), and $χ^2$ -divergence, the convergence rate is $e^{O(d)}n^{-1}$ , but only if $P$ achieves finite input-output $χ^2$ mutual information across the additive white Gaussian noise channel. If the latter condition is not met, the rate changes to $ω(n^{-1})$ for the KL divergence and $\mathsf{W}_2^2$ , while the $χ^2$ -divergence becomes infinite - a curious dichotomy. As a main application we consider estimating the differential entropy $h(P\ast\mathcal{N}_σ)$ in the high-dimensional regime. The distribution $P$ is unknown but $n$ i.i.d samples from it are available. We first show that any good estimator of $h(P\ast\mathcal{N}_σ)$ must have sample complexity that is exponential in $d$ . Using the empirical approximation results we then show that the absolute-error risk of the plug-in estimator converges at the parametric rate $e^{O(d)}n^{-\frac{1}{2}}$ , thus establishing the minimax rate-optimality of the plug-in. Numerical results that demonstrate a significant empirical superiority of the plug-in approach to general-purpose differential entropy estimators are provided.

preprint2016arXiv

Further results on arc and bar k-visibility graphs

We consider visibility graphs involving bars and arcs in which lines of sight can pass through up to k objects. We prove a new edge bound for arc k-visibility graphs, provide maximal constructions for arc and semi-arc k-visibility graphs, and give a complete characterization of semi-arc visibility graphs. We show that the family of arc i-visibility graphs is never contained in the family of bar j-visibility graphs for any i and j, and that the family of bar i-visibility graphs is not contained in the family of bar j-visibility graphs for $i \neq j$ . We also give the first thickness bounds for arc and semi-arc k-visibility graphs. Finally, we introduce a model for random semi-bar and semi-arc k-visibility graphs and analyze its properties.

preprint2015arXiv

Multinational War is Hard

In this paper, we show that the problem of determining whether one player can force a win in a multiplayer version of the children's card game War is PSPACE-hard. The same reduction shows that a related problem, asking whether a player can survive k rounds, is PSPACE-complete when k is polynomial in the size of the input.

preprint2015arXiv

Online learning in repeated auctions

Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical and we simply compare our performance against that of the best fixed bid in hindsight. We show that sublinear regret is also achievable in this case and prove matching minimax lower bounds. To our knowledge, this is the first complete set of strategies for bidders participating in auctions of this type.

preprint2008arXiv

Permutations with Kazhdan-Lusztig polynomial P_{id,w}(q) = 1 + q^h

Using resolutions of singularities introduced by Cortez and a method for calculating Kazhdan-Lusztig polynomials due to Polo, we prove the conjecture of Billey and Braden characterizing permutations w with Kazhdan-Lusztig polynomial P_{id,w}(q)=1+q^h for some h.

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.