Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization

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.