2016/04/05 by Jalaj Upadhyay, Upadhyay, Jalaj
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1604.01429
openalex publication_date 2016/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study what price one has to pay to release \em differentially private low-rank factorization of a matrix. We consider various settings that are close to the real world applications of low-rank factorization: (i) the manner in which matrices are updated (row by row or in an arbitrary manner), (ii) whether matrices are distributed or not, and (iii) how the output is produced (once at the end of all updates, also known as \em one-shot algorithms or continually). Even though these settings are well studied without privacy, surprisingly, there are no private algorithm for these settings (except when a matrix is updated row by row). We present the first set of differentially private algorithms for all these settings. Our algorithms when private matrix is updated in an arbitrary manner promise differential privacy with respect to two stronger privacy guarantees than previously studied, use space and time \em comparable to the non-private algorithm, and achieve \em optimal accuracy. To complement our positive results, we also prove that the space required by our algorithms is optimal up to logarithmic factors. When data matrices are distributed over multiple servers, we give a non-interactive differentially private algorithm with communication cost independent of dimension. In concise, we give algorithms that incur optimal cost. We also perform experiments to verify that all our algorithms perform well in practice and outperform the best known algorithms until now for large range of parameters. We give experimental results for total approximation error and additive error for varying dimensions, α and k.