Research map / Learning theory and algorithms / Matrix and tensor methods
Sub-sampled Newton Methods with Non-uniform Sampling
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 |
|---|---|---|---|
| replace uniform sampling with block partial leverage score sampling in SSN | ridge logistic regression Hessian approximation · four real datasets, lambda=0.01 | running time to medium/high precision vs Newton: at least 2x faster than Newton | Helped |
| replace uniform sampling with block norm squares sampling in SSN | ridge logistic regression Hessian approximation · four real datasets, lambda=0.01 | running time vs Newton | Helped |
| uniform sampling vs non-uniform sampling as condition number grows (ablation) | SSN uniform sampling · ridge logistic regression on Adult with varying lambda | running time to 1e-8 relative error | Hurt |
| use leverage score (partial) sampling instead of block norm squares sampling (ablation) | SSN sampling distribution · ridge logistic regression, ill-conditioned lambda | convergence robustness to condition number | Helped |
| recompute partial leverage scores only every 10 iterations (stale scores) (ablation) | PLevSS · ridge logistic regression | running time | No clear effect |
| uniform sampling performance on high-coherence dataset | SSN uniform sampling · ridge logistic regression with lambda=0.01 on high-nonuniformity data | convergence to optimum | Hurt |
Closest papers by meaning
- Do Subsampled Newton Methods Work for High-Dimensional Data? (AAAI 2020 · similarity 0.90)
- Sub-sampled Cubic Regularization for Non-convex Optimization (ICML 2017 · similarity 0.90)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton (ICML 2025 · similarity 0.86)
- Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods (ICLR 2025 · similarity 0.86)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.86)
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.