Research map / Optimization / Nonconvex and smooth optimization
Polynomial Preconditioning for Gradient Methods
Nikita Doikov, Anton Rodomanov
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| Add symmetric polynomial preconditioner P1 = tr(B)I - B to the Gradient Method (ablation) | Gradient Method · Huber loss regression (synthetic, gap between λ1 and λ2) | func. residual convergence | Improved |
| Add symmetric polynomial preconditioner P2 to the Gradient Method (ablation) | Gradient Method · Huber loss regression (synthetic, gap between λ1 and λ3) | func. residual convergence | Improved |
| Use symmetric polynomial preconditioner P2 instead of identity in Gradient Method | Gradient Method · Logistic regression (mnist and other LIBSVM datasets) | iterations / matrix-vector products to reach func. residual: two times faster | Improved |
| Use symmetric polynomial preconditioner P2 in Fast Gradient Method instead of identity | Fast Gradient Method · Logistic regression (mnist and other LIBSVM datasets) | iterations / matrix-vector products to reach func. residual: about 1.5 times faster | Improved |
| Use Krylov (adaptive optimal polynomial) preconditioning in Gradient Method | Gradient Method · Logistic regression (LIBSVM datasets) | iterations to reach func. residual | Improved |
| Use symmetric polynomial preconditioning P1 and P2 in GM and FGM without extra per-iteration arithmetic cost | Gradient Method and Fast Gradient Method · Logistic regression (a9a, phishing, breast-cancer, ionosphere, covtype, mnist) | func. residual vs iterations | Improved |
| Use Krylov preconditioning with higher degree (τ=3 vs lower) and higher cost per iteration | Gradient Method · Logistic regression (LIBSVM datasets) | matrix-vector products | Mixed |
| Use GM with symmetric polynomial preconditioner P2 (order τ=2) | Gradient Method · Soft maximum (log-sum-exp) objective, n=100, m=200 | matrix-vector products and time to residual | Improved |
| Use FGM with symmetric polynomial preconditioner P2 | Fast Gradient Method · Soft maximum (log-sum-exp) objective | matrix-vector products and time vs BFGS | No clear effect |
Closest papers by meaning
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.89)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.88)
- Structured Preconditioners in Adaptive Optimization: A Unified Analysis (ICML 2025 · similarity 0.88)
- Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.87)
- Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives (NeurIPS 2026 · similarity 0.87)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 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.
