Research map / Optimization / Nonconvex and smooth optimization
Inexact Newton-type Methods for Optimisation with Nonnegativity Constraints
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 Newton-MR two-metric projection methods that combine projected gradient steps on the active set with inexact MINRES-based Newton steps on the inactive set, using nonpositive curvature directions, and proves O(eps^-2) and O(eps^-3/2) iteration complexity for nonnegativity-constrained nonconvex problems.
Problem
Large-scale nonconvex optimisation with nonnegativity constraints (e.g., nonnegative least squares, NMF, l1-regularised problems reformulated with nonnegativity), where first-order methods are slow on ill-conditioned problems and second-order alternatives have hard subproblems.
Approach
Extends the two-metric projection framework by taking simultaneous projected gradient steps on the active set and Hessian-free Newton-MR steps (MINRES with nonpositive curvature detection) on the inactive set, with inexact MINRES tolerances, yielding complexity guarantees for nonconvex bound-constrained problems.
Key results
- Newton-MR TMP achieves O(eps_g^-2) global iteration complexity under minimal assumptions and O(eps_g^-3/2) under stronger assumptions (Lipschitz Hessian, curvature bounds), matching state of the art for second-order methods.
- Operational complexity of O(eps_g^-2) gradient evaluations and tilde-O(eps_g^-3/2) Hessian-vector products is derived for the improved-rate variant.
- Empirically, the method is competitive with or outperforms projected Newton-CG, projected gradient, and FISTA on l1-regularised regression, neural network training, and NMF tasks, though FISTA is best on convex multinomial regression.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the improved-rate variant, including strict positive-curvature certification, Type II steps, and an inexactness tolerance scaled with ε_k | Newton-MR TMP · Nonconvex problems with nonnegativity constraints under the stronger assumptions | iteration complexity: \mathcal{O}(\epsilon_g^{-2}) -> \mathcal{O}(\epsilon_g^{-3/2}) | Helped |
Surprising findings
- On convex multinomial regression, FISTA clearly outperforms the proposed method, though the proposed method remains competitive.
Limitations
- Worst-case constants may depend poorly on problem constants (e.g., L_g^3), which may hurt practical performance.
- Improved-rate variant requires stronger assumptions (Lipschitz Hessian, uniform positive curvature on Krylov subspace, NPC direction lower bound).
Experimental setup
Datasets: MNIST CIFAR10 Fashion MNIST 20 Newsgroups Olivetti faces
Benchmarks: MNIST CIFAR10 Fashion MNIST 20 Newsgroups Olivetti faces
Metrics: objective value versus oracle calls objective value versus wall-clock time
Baselines: projected Newton-CG projected gradient with line search FISTA proximal gradient with momentum Newton-CG log barrier
Builds on: two-metric projection Newton-MR MINRES projected gradient Newton-CG
Closest papers by meaning
- A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees (NeurIPS 2025 · similarity 0.87)
- Revisiting Frank-Wolfe for Structured Nonconvex Optimization (NeurIPS 2025 · similarity 0.87)
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.86)
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · similarity 0.86)
- Skip the Hessian, Keep the Rates: Globalized Semismooth Newton with Lazy Hessian Updates (NeurIPS 2026 · similarity 0.86)
- Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees (ICML 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.