Research map / Learning theory and algorithms / Matrix and tensor methods
Do Subsampled Newton Methods Work for High-Dimensional Data?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use uniform Hessian subsampling with sample size governed by ridge coherence and effective dimension | SSN · Convex ERM, including high-dimensional data | sample complexity for the stated convergence guarantee: s = \tilde{\Theta} ( \mu^{\gamma} \ed ) | Helped |
| Use ridge leverage score sampling instead of uniform sampling | SSN · Convex ERM | sample complexity: s = \tilde{\Theta} ( \ed ) | Helped |
| Average the local approximate Newton directions | GIANT · Distributed convex ERM | sample complexity: from s = \tilde{\Theta} \big( \tfrac{\ed }{\epsilon^2} \big) to s = \tilde{\Theta} \big( \tfrac{\ed }{\epsilon} \big) | Helped |
| Apply subsampled Newton with the analyzed bounds to non-smooth regularized objectives | SSPN · Convex ERM with non-smooth regularization | iteration complexity | No clear effect |
| Solve the subproblem inexactly while meeting the stated error condition | SSN · Convex ERM | convergence bound: \varepsilon + \varepsilon_0 | No clear effect |
| Solve each local subproblem inexactly while meeting the stated error condition | GIANT · Distributed convex ERM | convergence bound: \varepsilon + \varepsilon_0 | No clear effect |
| Solve the proximal subproblem inexactly while meeting the stated error condition | SSPN · Convex ERM with non-smooth regularization | convergence bound: \varepsilon + \varepsilon_0 | No clear effect |
Closest papers by meaning
- Sub-sampled Newton Methods with Non-uniform Sampling (NeurIPS 2016 · similarity 0.90)
- Approximate Newton Methods and Their Local Convergence (ICML 2017 · similarity 0.89)
- Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach (NeurIPS 2021 · similarity 0.88)
- Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (NeurIPS 2016 · similarity 0.86)
- Debiasing Random Oblique Projections for Subsampled OLS and Fast CUR in High Dimensions (NeurIPS 2026 · similarity 0.85)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.