3 papers
cs.DS2026
Entrywise Low-Rank Approximation and Matrix Norms via Global Correlation Rounding
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
Given a matrix , the goal of the entrywise low-rank approximation problem is to find over all rank- matrices , where is t…
cs.DS2025
Additive Approximation Schemes for Low-Dimensional Embeddings
Prashanti Anderson, Ainesh Bakshi, Samuel B. Hopkins
We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the -Euclidean Metric Violation problem ($\textsf{$k$-EMV}$), where…
cs.DS2025
Sample-Optimal Private Regression in Polynomial Time
Prashanti Anderson, Ainesh Bakshi, Mahbod Majid +1
We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure).…