EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization

Guanghui Lan, Yuyuan Ouyang, Zhe Zhang

Mathematical Programming · 07.04.2026

DOI: 10.1007/s10107-026-02352-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Programming, online erschienen am 07.04.2026. Verfasst von Guanghui Lan und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 28 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Air Force Office of Scientific Research, Office of Naval Research.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We propose novel optimal and parameter-free algorithms for computing an approximate solution with small (projected) gradient norm. Specifically, for computing an approximate solution such that the norm of its (projected) gradient does not exceed $$\varepsilon $$ ε , we obtain the following results: a) for the convex case, the total number of gradient evaluations is bounded by $$\mathcal{O} (1)\sqrt{L\Vert x_0 - x^*\Vert /\varepsilon }$$ O ( 1 ) L ‖ x 0 - x ∗ ‖ / ε , where L is the Lipschitz constant of the gradient and $$x^*$$ x ∗ is any optimal solution; b) for the strongly convex case, the total number of gradient evaluations is bounded by $$\mathcal{O} (1)\sqrt{L/\mu }\log (\Vert \nabla f(x_0)\Vert /\varepsilon )$$ O ( 1 ) L / μ log ( ‖ ∇ f ( x 0 ) ‖ / ε ) , where $$\mu $$ μ is the strong convexity modulus; and c) for the nonconvex case, the total number of gradient evaluations is bounded by $$\mathcal{O} (1)\sqrt{Ll}(f(x_0) - f(x^*))/\varepsilon ^2$$ O ( 1 ) Ll ( f ( x 0 ) - f ( x ∗ ) ) / ε 2 , where l is the lower curvature constant. Our complexity results match the lower complexity bounds of the convex and strongly cases, and achieve the above best-known complexity bound for the nonconvex case for the first time in the literature. Our results can also be extended to problems with constraints and composite objectives. Moreover, for all the convex, strongly convex, and nonconvex cases, we propose parameter-free algorithms that do not require the input of any problem parameters or the convexity status of the problem. To the best of our knowledge, there do not exist such parameter-free methods before especially for the strongly convex and nonconvex cases. Since most regularity conditions (e.g., strong convexity and lower curvature) are imposed over a global scope, the corresponding problem parameters are notoriously difficult to estimate. However, gradient norm minimization equips us with a convenient tool to monitor the progress of algorithms and thus the ability to estimate such parameters in-situ.

Förderung

  • Air Force Office of Scientific Research
  • Office of Naval Research

Zitieren

APA

Lan, G., Ouyang, Y., & Zhang, Z. (2026). Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization. Mathematical Programming. https://doi.org/10.1007/s10107-026-02352-2

Vancouver

Lan G, Ouyang Y, Zhang Z. Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization. Mathematical Programming. 2026. doi:10.1007/s10107-026-02352-2

BibTeX
@article{Lan2026,
  author = {Lan, Guanghui and Ouyang, Yuyuan and Zhang, Zhe},
  title = {Optimal and parameter-free gradient minimization methods for convex and nonconvex optimization},
  journal = {Mathematical Programming},
  year = {2026},
  doi = {10.1007/s10107-026-02352-2}
}
Kostenlos starten →