Stefan Tiegel

collaborators

4 papers

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).…

cs.DS2024

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More

Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia +1

We study $sparse singular value certificates$ for random rectangular matrices. If $M$ is an $n \times d$ matrix with independent Gaussian entries, we give a new family of…

cs.CC2024

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

Kiril Bangachev, Guy Bresler, Stefan Tiegel +1

We present a polynomial-time reduction from solving noisy linear equations over $Z / q Z$ in dimension $I^ (k lo g n / poly (lo g k, lo g q, lo g lo g n))$ with a u…

cs.DS2024

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications

Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia +1

We prove that there is a universal constant $C > 0$ so that for every $d \in N$ , every centered subgaussian distribution $D$ on $R^{d}$ , and every even $p \in…