Differentially Private Robust Low-Rank Approximation
Authors: Raman Arora, Vladimir braverman, Jalaj Upadhyay
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give the first time and space-efficient differentially private algorithm for low-rank matrix approximation with respect to entrywise p-norm. and Proofs of all results are deferred to the supplementary material of this paper. and Our main result is as follows. Theorem 10. Algorithm ROBUST-LRA (see Algorithm 1) is (", δ)-differentially private. Furthermore, given a matrix A 2 Rn d, it runs in poly(k, n, d) time, e O(k(n + d)) space, and outputs a rank k matrix M such that, with probability 9/10 over the randomness of the algorithm... |
| Researcher Affiliation | Academia | Raman Arora Johns Hopkins University Baltimore, MD-21201 arora@cs.jhu.edu Vladimir Braverman Johns Hopkins University Baltimore, MD-21201 vova@cs.jhu.edu Jalaj Upadhyay Johns Hopkins University Baltimore, MD-21201 jalaj@jhu.edu |
| Pseudocode | Yes | Algorithm 1 ROBUST-LRA Input: Input data matrix A 2 Rn d, target rank k Output: Rank-k matrix M 2 Rn d and Algorithm 2 ROBUST-PCA Input: Input data matrix A 2 Rd n, target rank k Output: Rank-k projection matrix 2 Rd d |
| Open Source Code | No | The paper does not provide information about open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not mention specific datasets or their public availability for training. |
| Dataset Splits | No | The paper is theoretical and does not provide specific dataset split information. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide specific experimental setup details. |