5 papers
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Michael Menart, Aleksandar Nikolov, Ohad Shamir
We prove two lower bounds for the first order oracle complexity of minimizing a -dimensional -Lipschitz convex function over the unit ball with bits of memory. We first s…
On the Gradient Complexity of Private Optimization with Private Oracles
Michael Menart, Aleksandar Nikolov
We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider th…
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
Aleksandar Nikolov, Haohua Tang, Jonathan Ullman
In this paper we consider several related online computation problems. First, we study answering sequences of statistical queries arriving online, and being answered immediately wh…
Discrepancy of Arithmetic Progressions in Boxes and Convex Bodies
Lily Li, Aleksandar Nikolov
The combinatorial discrepancy of arithmetic progressions inside is the smallest integer for which can be colored with two colors so that any ari…
Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries
Christian Janos Lebeda, Aleksandar Nikolov, Haohua Tang
We revisit the task of releasing marginal queries under differential privacy with additive (correlated) Gaussian noise. We first give a construction for answering arbitrary workloa…