Differentially private learning beyond the classical dimensionality regime
This interesting paper concens differentially private learning beyond the classical dimensionality regime. To gain some perspective, it is well known that there are many limitations of classical statistical theory for modern high-dimensional supervised learning problems. To give a typical example, in genomics, neuroscience, image data and many other applications from various domains, the dimensionality \(d\) of the data is often larger than \(n\) the number of points and there are many well statistics techniques to address these challenges, for example the entire area of manifold learning and many others. In the paper under review, the authors study differentially private learning in the proportional dimensionality regime, in which the number of data samples \(n\) and problem dimension \(d\) approach infinity at rates proportional to one another. What this means is that \( d/n\to\varepsilon\) for large enough \(n\). The key is that \(\varepsilon\) is a given constant in the interval \((0,\infty)\). Note that unlike many previous works where \(\varepsilon\) is positive and small enough the much weaker assumption on \(\varepsilon\) makes the problem significally harder.\N\NThe authors in particular, provide sharp theoretical estimates of the error of several well known differentially private algorithms for robust linear regression and logistic regression, including output perturbation, objective perturbation, and noisy stochastic gradient descent, in the proportional dimensionality regime. They also discover and provide many new observations not known before. See the paper under review for more details. \N\NThe paper is well written with a good set of references.\N\NFor the entire collection see [Zbl 08152620].
- A model of double descent for high-dimensional binary linear classification
- A modern maximum-likelihood theory for high-dimensional logistic regression
- A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
- Applications of the Lindeberg Principle in Communications and Statistical Learning
- Approximate message passing algorithms for rotationally invariant matrices
- Concentrated differential privacy: simplifications, extensions, and lower bounds
- Convex optimization: algorithms and complexity
- Differential privacy and robust statistics
- Differentially private empirical risk minimization
- Does SLOPE outperform bridge regression?
- Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism
- High-dimensional probability. An introduction with applications in data science
- High-dimensional statistics. A non-asymptotic viewpoint
- Living on the edge: phase transitions in convex programs with random data
- Nonuniformity of p-values can occur early in diverging dimensions
- Old techniques in differentially private linear regression
- On general minimax theorems
- On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Precise Error Analysis of Regularized <inline-formula> <tex-math notation="LaTeX">$M$ </tex-math> </inline-formula>-Estimators in High Dimensions
- Privacy for free in the overparameterized regime
- Private empirical risk minimization: efficient algorithms and tight error bounds
- Privately Estimating a Gaussian: Efficient, Robust and Optimal
- Reconciling modern machine-learning practice and the classical bias-variance trade-off
- Rigorous dynamical mean field theory for stochastic gradient descent methods
- Robust Estimation of a Location Parameter
- Robustness Implies Privacy in Statistical Estimation
- SLOPE for Sparse Linear Regression: Asymptotics and Optimal Regularization
- Some inequalities for Gaussian processes and applications
- Spectral universality in regularized linear regression with nearly deterministic sensing matrices
- Statistically optimal robust mean and covariance estimation for anisotropic gaussians
- The algorithmic foundations of differential privacy
- The asymptotic distribution of the MLE in high-dimensional logistic models: arbitrary covariance
- The complexity of differential privacy
- The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy
- The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve
- The LASSO Risk for Gaussian Matrices
- The Lasso with general Gaussian designs with applications to hypothesis testing
- The Noise-Sensitivity Phase Transition in Compressed Sensing
- The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression
- The structure of optimal private tests for simple hypotheses
- Theory of Cryptography
- Two models of double descent for weak features
- Universality in polytope phase transitions and message passing algorithms
- Universality laws for randomized dimension reduction, with applications
- Universality of approximate message passing algorithms and tensor networks
- Universality of approximate message passing with semirandom matrices
- Universality of regularized regression estimators in high dimensions
This page was built for publication: Differentially private learning beyond the classical dimensionality regime
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7233236)
