Private optimization in the interpolation regime: faster rates and hardness results
Authors: Hilal Asi, Karan Chadha, Gary Cheng, John Duchi
ICML 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we show that without additional assumptions, interpolation problems do not exhibit an improved convergence rates with differential privacy. However, when the functions exhibit quadratic growth around the optimum, we show (near) exponential improvements in the private sample complexity. In particular, we propose an adaptive algorithm that improves the sample complexity to achieve expected error α from d ε α to 1 αρ + d for any fixed ρ > 0, while retaining the standard minimax-optimal sample complexity for non-interpolation problems. We prove a lower bound that shows the dimension-dependent term in the expression above is tight. Furthermore, we provide a superefficiency result which demonstrates the necessity of the polynomial term for adaptive algorithms: any algorithm that has a polylogarithmic sample complexity for interpolation problems cannot achieve the minimax-optimal rates for the family of non-interpolation problems. |
| Researcher Affiliation | Academia | 1Department of Electrical Engineering, Stanford University, Stanford, USA 2Department of Statistics, Stanford University, Stanford, USA. |
| Pseudocode | Yes | Algorithm 1 Lipschitzian-Extension Algorithm, Algorithm 2 Domain and Lipschitz Localization algorithm, Algorithm 3 Algorithm that adapts to interpolation, Algorithm 4 Localization based Algorithm, Algorithm 5 Epoch-based algorithms for κ-growth, Algorithm 6 Epoch based epoch based epoch based clipped-GD |
| Open Source Code | No | No, the paper does not provide concrete access to source code for the methodology described. There are no statements about releasing code or links to repositories. |
| Open Datasets | No | No, the paper is theoretical and does not conduct experiments on specific datasets, therefore it does not provide concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | No, the paper is theoretical and does not conduct empirical studies requiring dataset splits for training, validation, or testing. |
| Hardware Specification | No | No, the paper is theoretical and does not describe experimental procedures that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | No, the paper is theoretical and does not implement or run experiments, thus it does not specify software dependencies with version numbers. |
| Experiment Setup | No | No, the paper is theoretical and does not describe an experimental setup, hyperparameters, or training configurations, as it does not conduct empirical studies. |