Research map / Optimization / Nonconvex and smooth optimization
Escaping Saddle Points in Constrained Optimization
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 |
|---|---|---|---|
| Add a second-order quadratic-subproblem step after reaching an ε-FOSP | Generic constrained optimization framework · Smooth nonconvex optimization over a convex set | iterations to an (ε,γ)-SOSP: \mathcal{O}(\max\{\eps^{-2} , \rho^{-3}\gamma^{-3}\}) | Helped |
| Use Frank-Wolfe for the first-order stage | Generic constrained optimization framework · Smooth nonconvex optimization over a convex set | iterations to an ε-FOSP: \mathcal{O}(\eps^{-2}) | Helped |
| Use projected gradient descent for the first-order stage | Generic constrained optimization framework · Smooth nonconvex optimization over a convex set | iterations to an ε-FOSP: \mathcal{O}(\eps^{-2}) | Helped |
| Use the quadratic-constraint approximation with \rho\approx 1/m^2 | Generic constrained optimization framework · Intersection of m ellipsoids centered at the origin | arithmetic operations to an (ε,γ)-SOSP: \mathcal{O}(\max\{\tau\eps^{-2} ,d^3m^7\gamma^{-3}\}) | Helped |
| Use stochastic gradient and Hessian estimates with the specified batch sizes | Generic constrained optimization framework · Stochastic constrained optimization | stochastic gradient evaluations to an (ε,γ)-SOSP: \mathcal{O}(\max\{\eps^{-4},\eps^{-2}\rho^{-4}\gamma^{-4}, \rho^{-7}\gamma^{-7}\}) | Helped |
| Use stochastic gradient and Hessian estimates with the specified batch sizes | Generic constrained optimization framework · Stochastic constrained optimization | stochastic Hessian evaluations to an (ε,γ)-SOSP: \mathcal{O}(\max\{\eps^{-2}\rho^{-3}\gamma^{-3},\rho^{-5}\gamma^{-5}\}) | Helped |
| Use the SDP relaxation, yielding approximation factor 1/m rather than the cited \rho\approx 1/m^2 approach | Quadratic subproblem solver · m convex quadratic constraints | quadratic subproblem approximation factor: 1/m; \rho\approx 1/m^2 | Helped |
Closest papers by meaning
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.89)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.89)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.89)
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms (ICML 2025 · similarity 0.88)
- Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds (NeurIPS 2024 · similarity 0.88)
- Barrier Algorithms for Constrained Non-Convex Optimization (ICML 2024 · similarity 0.88)
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.