Second-order methods improve differential privacy in convex optimization.
problem Improving differential privacy in convex optimization.
method Developed a private variant of the regularized cubic Newton method for strongly convex loss functions.
result Achieves quadratic convergence and optimal excess loss for strongly convex loss functions.
Improved privacy-preserving methods for convex optimization with heavy-tailed data.
problem Privacy-preserving optimization of convex functions with heavy-tailed data.
method Developed algorithms for private mean estimation and convex optimization under concentrated differential privacy constraints.
result Achieved improved upper bounds on excess population risk for convex and strongly convex loss functions.
Private algorithms minimize population loss with optimal rate.
problem Private optimization of convex functions with stochastic samples.
method Differentially private algorithms based on algorithmic stability.
result Optimal rate of 1 / n 1/\sqrt{n} 1/ n for population loss. New algorithms for differentially private optimization in convex and non-convex settings with near-optimal rates.
problem Differentially private optimization in convex and non-convex settings.
method Developed algorithms for convex and non-convex settings with near-optimal excess population risk.
result Achieved near-optimal rates in near-linear time for convex settings and nearly dimension independent rates for non-convex settings.
Paper estimates differences in multi-attribute Gaussian graphical models using non-convex penalties.
problem Estimating differences in multi-attribute Gaussian graphical models with similar structure.
method Penalized D-trace loss function with non-convex (log-sum and SCAD) penalties, proximal gradient descent methods.
result Theoretical analysis and numerical examples support consistency in support recovery and estimation.
New method simplifies checking consistency of differentiable loss functions.
problem Verifying consistency of differentiable loss functions is difficult.
method Developed a new approach called strong indirect elicitation (strong IE) to simplify checking consistency.
result Strong IE is equivalent to calibration for strongly convex, differentiable surrogates.
New DP algorithm improves privacy and efficiency for convex optimization.
problem Efficient, DP algorithms for convex optimization with strong excess risk bounds.
method Output perturbation for a broad class of tilted loss functions.
result Near optimal DP excess risk and runtime bounds for convex optimization.
In this paper we study the differentially private Empirical Risk Minimization (ERM) problem in different settings. For smooth (strongly) convex loss function with or without (non)-smooth regularization, we give algorithms that achieve either optimal or near optimal utility bounds with less gradient complexity compared …
Paper relaxes SGD privacy and generalization guarantees for non-smooth convex losses.
problem Privacy and generalization in SGD for non-smooth convex losses.
method Relaxes Lipschitz and strong smoothness assumptions to Hölder smoothness, proving ( ε , δ ) (ε,δ) ( ε , δ ) -DP and optimal excess risk. result Noisy SGD with α α α -Hölder smooth losses achieves optimal excess risk with linear gradient complexity for α ≥ 1 / 2 α \geq 1/2 α ≥ 1/2 . Paper proposes WD-DP ERM for distributed learning with improved privacy and performance.
problem Training models in distributed settings with privacy and performance guarantees.
method Weighted distributed differential privacy (WD-DP) for ERM, considering different weights of clients.
result Improved noise bound and excess empirical risk bound in distributed settings.
We consider deep linear networks with arbitrary convex differentiable loss. We provide a short and elementary proof of the fact that all local minima are global minima if the hidden layers are either 1) at least as wide as the input layer, or 2) at least as wide as the output layer. This result is the strongest possibl…
Paper improves differential privacy analysis for machine learning.
problem Quantifying privacy leakage in noisy gradient descent.
method Shifted interpolation in f f f -differential privacy. result First exact privacy analysis for strongly convex optimization.
New algorithms achieve optimal DP convex optimization with linear time and gradient computations.
problem Private stochastic convex optimization with optimal excess loss.
method Two new techniques: variable batch sizes and localization with stable optimization.
result Achieves optimal bound on excess loss with O ( min { n , n 2 / d } ) O(\min\{n, n^2/d\}) O ( min { n , n 2 / d }) gradient computations. New stability bounds for SGD on nonsmooth convex losses.
problem Understanding stability of SGD on nonsmooth convex losses.
method Sharp upper and lower bounds for SGD and full-batch GD on nonsmooth convex losses.
result SGD can be less stable but still useful for generalization bounds.
Paper improves privacy and utility of SGD with bounded domain and smooth losses.
problem Lack of tight privacy bounds and practical assumptions in DPSGD.
method Rigorous privacy characterization for DPSGD with general L-smooth and non-convex loss functions, tracking privacy loss over iterations.
result Privacy loss converges without convexity assumption for bounded domain, improving utility.
Study on privacy leakage in noisy gradient descent algorithms.
problem Information leakage of iterative randomized learning algorithms about training data.
method Analyzes the dynamics of Rényi differential privacy loss in noisy gradient descent algorithms.
result Privacy loss converges exponentially fast for smooth and strongly convex loss functions.
Optimal learning rate schedules for SGD in changing data distributions.
problem Minimizing regret in online learning with changing data distributions.
method Characterized optimal schedules for linear regression, proposed schedules for general convex and non-convex losses, and defined a notion of regret for non-convex losses.
result Upper and lower bounds for regret with constants for convex losses, and an upper bound on total expected regret for non-convex losses.
New framework for DP-SMO with near-optimal privacy-loss trade-off.
problem Optimal trade-off between privacy and population loss in DP-SMO.
method General framework using Phased-ERM method and black-box optimization.
result Near-linear time algorithms with near-optimal guarantees.
Deep linear networks avoid spurious local minima under certain conditions.
problem Existence of spurious local minima in deep linear networks.
method Reduction to two-layer case, quadratic loss analysis, and perturbation argument to show full rank property.
result Deep linear networks have no spurious local minima under specific conditions.
Optimizes private learning with differential privacy for LASSO problems.
problem Private optimization of convex functions over ℓ 1 \ell_1 ℓ 1 -bounded domains. method Combines iterative localization with private regularized mirror descent and variance-reduced Frank-Wolfe algorithm.
result Achieves optimal excess population loss rates in ℓ 1 \ell_1 ℓ 1 geometry. Paper addresses DP-SCO on heavy-tailed data, providing methods and results.
problem Designing DP algorithms for SCO on heavy-tailed data.
method Sample-and-aggregate framework, gradient smoothing and trimming.
result Achieved DP guarantees for various loss functions with different excess population risks.
Improved privacy bounds for learning linear predictors with convex losses.
problem Differentially private learning of linear predictors with convex losses.
method Developed private model selection approach to achieve optimal rates.
result Improved upper and lower bounds for excess population risk.
Optimal private ERM and SCO with subquadratic gradient complexity.
problem Private optimization of non-smooth convex functions.
method Subquadratic gradient complexity algorithm using subsampling and smoothing.
result Achieved optimal excess empirical risk and population loss.
New algorithm achieves optimal privacy and efficiency in non-Euclidean convex optimization.
problem Optimizing convex functions while maintaining privacy in non-Euclidean settings.
method Developed a linear-time algorithm for ℓ p \ell_p ℓ p -setups, leveraging geometric properties. result Optimal excess risk achieved in linear time for 1 < p ≤ 2 1 < p \leq 2 1 < p ≤ 2 . New algorithm reduces privacy loss in SGD without learning rate tuning.
problem Locally differentially private stochastic optimization with high privacy loss.
method BANCO (Betting Algorithm for Noisy COins) for ε ε ε -LDP SGD. result Matches convergence rate of tuned SGD without learning rate tuning.
Optimizes privacy-preserving optimization for heavy-tailed data.
problem Privacy-preserving optimization with heavy-tailed gradients.
method Pure ε-differential privacy framework for Lipschitz extensions.
result Minimax optimal excess-risk rate for pure ε-DP heavy-tailed SCO.
In this paper, we study two general classes of optimization algorithms for kernel methods with convex loss function and quadratic norm regularization, and analyze their convergence. The first approach, based on fixed-point iterations, is simple to implement and analyze, and can be easily parallelized. The second, based…
New privacy bounds for DP-SGD's last iterate, even with cyclic sampling.
problem Privacy of the last iterate in DP-SGD with cyclic sampling.
method Established new RDP upper bounds for the last iterate under realistic assumptions.
result Privacy bounds for DP-SGD's last iterate with cyclic sampling and clipping, even for nonconvex losses.
Extends private optimization to non-convex problems efficiently.
problem Private optimization of non-convex functions over discrete and continuous domains.
method Two algorithms: one for discrete domains and one for continuous domains, both requiring boundedness and Lipschitz continuity.
result Oracle-efficient optimization algorithms for non-convex problems, outperforming standard approaches in some cases.
Uniform diffusion approximation for SGD in non-convex settings.
problem Finite-time diffusion approximation for SGD.
method Establishing uniform-in-time diffusion approximation with strong convexity and mild conditions.
result Uniform-in-time diffusion approximation of SGD without convexity of each loss function.
This manuscript provides optimization guarantees, generalization bounds, and statistical consistency results for AdaBoost variants which replace the exponential loss with the logistic and similar losses (specifically, twice differentiable convex losses which are Lipschitz and tend to zero on one side). The heart of the…
Monotonic Linear Interpolation property in neural networks persists despite non-convexity.
problem Understanding the geometric properties of neural network loss landscapes.
method Tools from differential geometry to analyze the monotonicity of neural network weights.
result Sufficient conditions for the Monotonic Linear Interpolation property under mean squared error.
Optimizes differentially private kernel learning with random projection.
problem Privacy-preserving learning algorithms with optimal performance.
method Differentially private kernel ERM algorithm based on random projection in reproducing kernel Hilbert space.
result Achieves minimax-optimal excess risk rates for various loss functions.
Proposes MGCE for improved classification performance.
problem Optimizing between robustness and optimization difficulty in classification.
method Minimax formulation of GCE leading to convex optimization over margins.
result MGCE achieves strong accuracy and better calibration, especially in noisy labels.
Paper addresses ERM in LDP, reducing sample complexity for smooth and convex losses.
problem Achieving error α in ERM with non-interactive LDP, especially for high-dimensional data.
method Developed algorithms using Bernstein polynomial and polynomial approximation techniques.
result For smooth and convex losses, sample complexity is linear in dimensionality.
Reduces the cost of making fair models using differential privacy.
problem Ensuring fairness in machine learning models while maintaining differential privacy.
method Information-theoretic reductions to solve constrained optimization problems.
result First polynomial-time algorithms for ( ε , δ ) (ε, δ) ( ε , δ ) differential privacy with tight sample complexity bounds. Paper revisits DP-SCO in Euclidean and ℓ p d \ell_p^d ℓ p d spaces, focusing on constrained and bounded sets.
problem Differentially private stochastic convex optimization in constrained and bounded sets in Euclidean and ℓ p d \ell_p^d ℓ p d spaces. method Proposes methods achieving excess population risks dependent on Gaussian width of the constraint set, and novel algorithms for unconstrained and heavy-tailed data.
result Theoretical results for DP-SCO in ℓ p d \ell_p^d ℓ p d spaces, including optimal bounds for strongly convex functions. In this paper, we initiate a systematic investigation of differentially private algorithms for convex empirical risk minimization. Various instantiations of this problem have been studied before. We provide new algorithms and matching lower bounds for private ERM assuming only that each data point's contribution to the…
Improved DP SO with large Lipschitz parameters, handling outliers and heavy-tailed data.
problem Differential privacy in stochastic optimization with large Lipschitz parameters.
method Assumes bounded k-th order moments, provides linear-time algorithms for smooth convex and non-smooth convex losses.
result Improved risk bounds scaling with k-th moment, not uniform Lipschitz parameter.
Optimal DP mechanisms for vector queries are found to be staircase distributions.
problem Designing optimal additive mechanisms for vector-valued queries under differential privacy.
method Reduction to radially symmetric distributions and convex rearrangement theory.
result Staircase mechanisms are optimal for any norm and cost function.
Improved DP algorithms for non-convex optimization with tighter generalization bounds.
problem Private stochastic non-convex optimization in high-dimensional spaces.
method Differential privacy techniques, including adaptive algorithms like DP RMSProp and DP Adam, combined with adaptive data analysis.
result Achieved a sharper rate of p 4 / n \sqrt[4]{p}/\sqrt{n} 4 p / n for population loss, improving upon previous bounds. New DP optimization methods for sparse gradients, improving on existing algorithms.
problem Differentially private optimization with sparse gradients in high-dimensional settings.
method Improved bounds for mean estimation, pure- and approximate-DP algorithms for stochastic convex optimization.
result First nearly dimension-independent rates for DP optimization with sparse gradients.
We use smoothed analysis techniques to provide guarantees on the training loss of Multilayer Neural Networks (MNNs) at differentiable local minima. Specifically, we examine MNNs with piecewise linear activation functions, quadratic loss and a single output, under mild over-parametrization. We prove that for a MNN with …
Zeroth-order optimization methods lack inherent privacy guarantees.
problem Ensuring differential privacy in zeroth-order optimization methods.
method Analyzing ZO-GD with and without random initialization for convex and strongly convex objectives.
result ZO-GD is not differentially private for strongly convex objectives and can have superlinear privacy loss.
New framework for private convex optimization in arbitrary norms.
problem Private optimization of convex functions in non-Euclidean settings.
method Regularized exponential mechanism based on localization tools from convex geometry.
result First optimal privacy-utility tradeoffs for ℓ p \ell_p ℓ p norms and Schatten- p p p norms. Paper relaxes stability and generalization assumptions for SGD.
problem Stability and generalization for SGD under restrictive assumptions.
method Introduces on-average model stability and develops novel bounds.
result First-ever-known fast bounds in low-noise setting using stability approach.
New analysis shows SGD with noise doesn't leak more privacy with more iterations.
problem Privacy loss in noisy SGD with more iterations.
method Privacy Amplification by Iteration and Sampled Gaussian Mechanism.
result Privacy loss remains constant after a burn-in period, not increasing with more iterations.
Neural networks solve the Dirichlet problem for Monge-Ampère equations.
problem Solving the Dirichlet problem for the Monge-Ampère equation.
method Using deep input convex neural networks to find the unique convex solution.
result Deep input convex neural networks can solve the Monge-Ampère Dirichlet problem.