Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Fast Algorithms for Sparse PCA and Robust Sparse Estimation
Giannis Iakovidis, Ankit Pensia
We study fast algorithms for sparse-PCA certification. Given a positive semidefinite matrix , the problem asks either to rule out a large -sparse quadratic form or to return…
cs.DS2026
Testable Learning of General Halfspaces under Massart Noise
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the algorithmic task of testably learning general Massart halfspaces under the Gaussian distribution. In the testable learning setting, the aim is the design of a tester-l…
cs.DS2025
Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given…