We present a new online matrix factorization algorithm that competitively matches the best offline factorization up to logarithmic factors. In the online matrix factorization problem, a new row qt of a matrix arrives at each time step t, and the algorithm needs to maintain a factorization LtRt=Qt such that at each time it appends some rows to Rt, and outputs a new row ℓt s.t. ℓtRt=qt. Our algorithm maintains the competitiveness over this online process, even if the number of rows to arrive is unknown. We give two applications of this online algorithm: (1) We study differentially private algorithms that answer statistical queries arriving online. Known matrix factorization mechanisms can answer a set of statistical queries with error bounded by the γ2 norm of their query matrix, but require that all queries are known in advance. We show that nearly the same error bounds can be achieved in the online setting for non-adaptively chosen queries. As a related contribution, we give online competitive private query release algorithms for small datasets using a different set of techniques with incomparable properties. (2) We give an algorithm for online discrepancy minimization that competes with the γ2 norm, and also against hereditary discrepancy, up to logarithmic factors.

We investigate unbiased high-dimensional mean estimators in differential privacy. We consider differentially private mechanisms whose expected output equals the mean of the input dataset, for every dataset drawn from a fixed bounded $d$-dimensional domain $K$. A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. In the first part of this paper, we study the optimal error achievable by a Gaussian noise mechanism for a given domain $K$ when the error is measured in the $\ell_p$ norm for some $p \ge 2$. We give algorithms that compute the optimal covariance for the Gaussian noise for a given $K$ under suitable assumptions, and prove a number of nice geometric properties of the optimal error. These results generalize the theory of factorization mechanisms from domains $K$ that are symmetric and finite (or, equivalently, symmetric polytopes) to arbitrary bounded domains. In the second part of the paper we show that Gaussian noise mechanisms achieve nearly optimal error among all private unbiased mean estimation mechanisms in a very strong sense. In particular, for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error as the best Gaussian noise mechanism. We extend this result to local differential privacy, and to approximate differential privacy, but for the latter the error lower bound holds either for a dataset or for a neighboring dataset, and this relaxation is necessary.

A recent series of papers by Andoni, Naor, Nikolov, Razenshteyn, and Waingarten (STOC 2018, FOCS 2018) has given approximate near neighbour search (NNS) data structures for a wide class of distance metrics, including all norms. In particular, these data structures achieve approximation on the order of p for 𝓁_p^d norms with space complexity nearly linear in the dataset size n and polynomial in the dimension d, and query time sub-linear in n and polynomial in d. The main shortcoming is the exponential in d pre-processing time required for their construction. In this paper, we describe a more direct framework for constructing NNS data structures for general norms. More specifically, we show via an algorithmic reduction that an efficient NNS data structure for a metric ℳ is implied by an efficient average distortion embedding of ℳ into 𝓁₁ or the Euclidean space. In particular, the resulting data structures require only polynomial pre-processing time, as long as the embedding can be computed in polynomial time. As a concrete instantiation of this framework, we give an NNS data structure for 𝓁_p with efficient pre-processing that matches the approximation factor, space and query complexity of the aforementioned data structure of Andoni et al. On the way, we resolve a question of Naor (Analysis and Geometry in Metric Spaces, 2014) and provide an explicit, efficiently computable embedding of 𝓁_p, for p ≥ 1, into 𝓁₁ with average distortion on the order of p. Furthermore, we also give data structures for Schatten-p spaces with improved space and query complexity, albeit still requiring exponential pre-processing when p ≥ 2. We expect our approach to pave the way for constructing efficient NNS data structures for all norms.