Mathematics

We initiate the study of hypothesis selection under local differential privacy. Given samples from an unknown probability distribution p and a set of k probability distributions Q, we aim to output, under the constraints of ε-local differential privacy, a distribution from Q whose total variation distance to p is comparable to the best such distribution.

Minimax optimization has found extensive applications in modern machine learning, in settings such as generative adversarial networks (GANs), adversarial training and multi-agent reinforcement learning. As most of these applications involve continuous nonconvex-nonconcave formulations, a very basic question arises — “what is a proper definition of local optima?'” Most previous work answers this question using classical notions of equilibria from simultaneous games, where the min-player and the max-player act simultaneously. In contrast, most applications in machine…

Reaction-diffusion processes across layered media arise in several scientific domains such as pattern-forming E. coli on agar substrates, epidermal-mesenchymal coupling in development, and symmetry-breaking in cell polarisation. We develop a modelling framework for bi-layer reaction-diffusion systems and relate it to a range of existing models. We derive conditions for diffusion-driven instability of a spatially homogeneous equilibrium analogous to the classical conditions for a Turing instability in the simplest nontrivial setting where one domain has a…

We study equilibria in two-buyer sequential second-price (or first-price) auctions for identical goods. Buyers have weakly decreasing incremental values, and we make a behavioural no-overbidding assumption: the buyers do not bid above their incremental values. Structurally, we show equilibria are intrinsically linked to a greedy bidding strategy. We then prove three results. First, any equilibrium consists of three phases: a competitive phase, a competition reduction phase and a monopsony phase. In particular, there is a…

We carry out a numerical study of the spinless modular bootstrap for conformal field theories with current algebra U(1)c × U(1)c, or equivalently the linear programming bound for sphere packing in 2c dimensions. We give a more detailed picture of the behavior for finite c than was previously available, and we extrapolate as c → ∞. Our extrapolation indicates an exponential improvement for sphere packing density bounds in high dimensions. Furthermore, we study when these…

Non-signaling proofs, motivated by quantum computation, have found applications in cryptography and hardness of approximation. An important open problem is characterizing the power of no-signaling proofs. It is known that 2-prover no-signaling proofs are characterized by PSPACE, and that no-signaling proofs with poly(n)-provers are characterized by EXP. However, the power of k-prover no-signaling proofs, for 2<k<poly(n) remained an open problem. We show that k-prover no-signaling proofs (with negligible soundness) for k=O(√logn) are contained in PSPACE. We prove this via two different routes…

Adaptive sampling is a useful algorithmic tool for data summarization problems in the classical centralized setting, where the entire dataset is available to the single processor performing the computation. Adaptive sampling repeatedly selects rows of an underlying matrix A∈Rn×d, where n≫d, with probabilities proportional to their distances to the subspace of the previously selected rows. Intuitively, adaptive sampling seems to be limited to trivial multi-pass algorithms in the streaming model of computation due to its…

Despite the great empirical success of adversarial training to defend deep learning models against adversarial perturbations, so far, it still remains rather unclear what the principles are behind the existence of adversarial perturbations, and what adversarial training does to the neural network to remove them. In this paper, we present a principle that we call “feature purification”, where we show the existence of adversarial examples are due to the accumulation of certain “dense mixtures” in…