Cover Image

Sample-Optimal Private Regression in Polynomial Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anderson, Prashanti, Bakshi, Ainesh, Majid, Mahbod, Tiegel, Stefan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Information Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sample-Efficient Private Learning of Mixtures of Gaussians
by: Ashtiani, Hassan, et al.
Published: (2024)

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
by: Anderson, Prashanti, et al.
Published: (2026)

Private Mean Estimation with Person-Level Differential Privacy
by: Agarwal, Sushant, et al.
Published: (2024)

A Framework for Searching in Graphs in the Presence of Errors
by: Dereniowski, Dariusz, et al.
Published: (2018)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Robustness Implies Privacy in Statistical Estimation
by: Hopkins, Samuel B., et al.
Published: (2022)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
by: Chen, Sitan, et al.
Published: (2026)

Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples
by: Afzali, Mohammad, et al.
Published: (2023)

Optimal Differentially Private Sampling of Unbounded Gaussians
by: Iverson, Valentio, et al.
Published: (2025)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
by: Chen, Hongjie, et al.
Published: (2025)

SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications
by: Diakonikolas, Ilias, et al.
Published: (2024)

Efficient Certificates of Anti-Concentration Beyond Gaussians
by: Bakshi, Ainesh, et al.
Published: (2024)

Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
by: Tasnim, Naima, et al.
Published: (2025)

Structure learning of Hamiltonians from real-time evolution
by: Bakshi, Ainesh, et al.
Published: (2024)

Learning quantum Hamiltonians at any temperature in polynomial time
by: Bakshi, Ainesh, et al.
Published: (2023)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

Smoothed Score Queries and the Complexity of Sampling
by: Liu, Jingbo
Published: (2026)

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
by: Asi, Hilal, et al.
Published: (2024)

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

Optimal Rates for Differentially Private Hypothesis Testing with E-values
by: Jacobsen, Ben, et al.
Published: (2026)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
by: Diakonikolas, Ilias, et al.
Published: (2024)

On the Statistical Complexity of Sample Amplification
by: Axelrod, Brian, et al.
Published: (2022)

Online Distribution Learning with Local Private Constraints
by: Sima, Jin, et al.
Published: (2024)

An Improved Classical Singular Value Transformation for Quantum Machine Learning
by: Bakshi, Ainesh, et al.
Published: (2023)

Agnostic Private Density Estimation for GMMs via List Global Stability
by: Afzali, Mohammad, et al.
Published: (2024)

Sample-Efficient Linear Regression with Self-Selection Bias
by: Gaitonde, Jason, et al.
Published: (2024)

Optimal high-precision shadow estimation
by: Chen, Sitan, et al.
Published: (2024)

CoinPress: Practical Private Mean and Covariance Estimation
by: Biswas, Sourav, et al.
Published: (2020)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

Learning DNF through Generalized Fourier Representations
by: Heidari, Mohsen, et al.
Published: (2025)

The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
by: Chen, Jiale, et al.
Published: (2025)

The SMART approach to instance-optimal online learning
by: Banerjee, Siddhartha, et al.
Published: (2024)

Subsampling Suffices for Adaptive Data Analysis
by: Blanc, Guy
Published: (2023)

Learning multivariate Gaussians with imperfect advice
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Entropy Coding of Unordered Data Structures
by: Kunze, Julius, et al.
Published: (2024)

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
by: Narayanan, Shyam
Published: (2023)

Robust Regression with Adaptive Contamination in Response: Optimal Rates and Computational Barriers
by: Diakonikolas, Ilias, et al.
Published: (2026)