Research map / Optimization / Nonconvex and smooth optimization
Improving Convergence Guarantees of Random Subspace Second-order Algorithm for Nonconvex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RSHTR, a random subspace trust-region method that solves homogenized subproblems via minimum-eigenvalue computations in a random low-dimensional subspace, with global O(ε^{-3/2}) FOSP/SOSP and local linear/quadratic convergence guarantees.
Problem
Large-dimensional nonconvex unconstrained optimization where full-space second-order methods are costly; existing random subspace methods have weak complexity or no local rate guarantees.
Approach
Applies the homogenized trust-region subproblem (HSODM) inside a random Gaussian subspace, so each iteration solves a (s+1)-dimensional minimum-eigenvalue problem without forming the restricted Hessian, yielding O(ε^{-3/2}) complexity and local linear/quadratic convergence under low effective dimensionality.
Key results
- RSHTR achieves O(ε^{-3/2}) iteration complexity to an ε-approximate first-order stationary point with local linear convergence, and quadratic local convergence under rank-deficiency (low effective dimensionality) assumptions.
- Total complexity O(ε^{-3/2} s^{5/4} n^{7/4}) versus O(ε^{-3/2} n^2) for full-space HSODM, with space O(sn).
- On the low effective Rosenbrock problem (n=10000, r=50 ≤ s=100) quadratic convergence is observed, while full-space HSODM does not complete a single step.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RSHTR instead of the compared optimization methods | Low Effective Rosenbrock (LER), r=50, s=100 · LER | global convergence speed | Helped |
| Use RSHTR instead of the compared optimization methods | MovieLens 100k matrix factorization · MovieLens 100k | function-value decrease | Helped |
| Vary the subspace dimension | Random subspace methods on MovieLens 100k · MovieLens 100k | relative performance | No clear effect |
| Use RSHTR instead of the existing methods | Classification algorithms · News20, RCV1, SCOTUS, MNIST, and CIFAR-10 | function value versus computation time | Helped |
| Set the problem rank r above the subspace dimension s | RSHTR on Low Effective Rosenbrock · LER | convergence speed | Hurt |
| Use the full-space algorithm instead of RSHTR | LER with n=10000, r=50, and s=100 · LER | completed iterations | Hurt |
| Use RSHTR instead of the other algorithms | Matrix factorization · MovieLens 100k | function-value decrease | Mixed |
Surprising findings
- Full-space HSODM did not complete even a single step on the n=10000 low effective Rosenbrock problem within the time limit.
- Random subspace methods converge more slowly when the problem rank r exceeds the subspace dimension s.
Limitations
- Global SOSP guarantee under rank deficiency requires the rank of the Hessian at the output to be at most s; the general SOSP guarantee needs the stated extra assumption.
- Iteration complexity degrades by a factor (n/s)^{3/4 or more} relative to full-space HSODM unless low effective dimensionality holds.
- Local superlinear convergence is not achieved in general; the fixed-step parameter delta is not adaptive.
Experimental setup
Datasets: MovieLens 100k News20 RCV1 SCOTUS MNIST CIFAR-10 Low Effective Rosenbrock (synthetic)
Benchmarks: MovieLens 100k News20 RCV1 SCOTUS MNIST CIFAR-10 Low Effective Rosenbrock
Metrics: function value computation time
Baselines: HSODM RSRN Gradient Descent RSGD
Builds on: HSODM random subspace gradient descent randomized Lanczos
Closest papers by meaning
- Accelerated Projected Gradient Algorithms for Sparsity Constrained Optimization Problems (NeurIPS 2022 · similarity 0.87)
- Optimal Randomized First-Order Methods for Least-Squares Problems (ICML 2020 · similarity 0.86)
- High-Dimensional Optimization in Adaptive Random Subspaces (NeurIPS 2019 · similarity 0.86)
- Local Linear Convergence of Gradient Methods for Subspace Optimization via Strict Complementarity (NeurIPS 2022 · similarity 0.86)
- Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data (ICML 2023 · similarity 0.85)
- Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness (AAAI 2024 · similarity 0.85)
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.