Adaptive Normalized Gradient Method for (L0,L1)-smooth Problems: Estimating Problem Parameters as a Region
Abstract
We propose a parameter-free and efficient gradient descent algorithm for (L0,L1)-smooth optimization. This notion of smoothness, introduced by Zhang et al. (2020), allows the smoothness bound to grow with the gradient norm. Similar to cutting-plane localization, our method uses a sequence of observations to maintain a region of plausible values for (L0,L1) and uses this region to select step sizes. In the convex setting, our method attains the standard iteration complexity bound 𝒪̃((L0/ε+ L12)|x0−x*|2) for finding an ε-optimal solution, while in the nonconvex setting it finds an ε-stationary point within 𝒪̃((L0/ε2 + L1/ε)(f(x0)−f*)) iterations. To the best of our knowledge, this is the first work to establish, for a single parameter-free algorithm, the best-known iteration-complexity guarantee in the nonconvex setting while also providing the above iteration-complexity guarantee in the convex setting. Experiments on logistic regression and real phase retrieval demonstrate that our method can exploit (L0,L1)-smoothness and perform efficiently on nonconvex problems.
Related
- Self-Normalized Inference from Riemannian Stochastic Gradient Paths
- Finite volume discretization and normalized gradient flow for computing minimizers of the rotating Gross-Pitaevskii energy
- Asymptotically Hölder gradient regularity for degenerate or singular parabolic normalized $ p$-Laplace equations
- Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness
- Estimating Population-Risk Curves Along Nonconvex Gradient Flows from the Training Sample
BibTeX
@misc{okazaki2026adaptive,
title = {{Adaptive Normalized Gradient Method for $(L_0,L_1)$-smooth Problems: Estimating Problem Parameters as a Region}},
author = {Rikiya Okazaki and Shotaro Yagishita and Hideitsu Hino},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27681},
eprint = {2610.27681},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27681},
}
RIS
TY - UNPB
TI - Adaptive Normalized Gradient Method for (L_0,L_1)-smooth Problems: Estimating Problem Parameters as a Region
AU - Rikiya Okazaki
AU - Shotaro Yagishita
AU - Hideitsu Hino
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27681
UR - https://arxiv.org/abs/2610.27681
AB - We propose a parameter-free and efficient gradient descent algorithm for (L_0,L_1)-smooth optimization. This notion of smoothness, introduced by Zhang et al. (2020), allows the smoothness bound to grow with the gradient norm. Similar to cutting-plane localization, our method uses a sequence of observations to maintain a region of plausible values for (L_0,L_1) and uses this region to select step sizes. In the convex setting, our method attains the standard iteration complexity bound 𝒪̃((L_0/ε+ L_1^2)|x^0−x^*|^2) for finding an ε-optimal solution, while in the nonconvex setting it finds an ε-stationary point within 𝒪̃((L_0/ε^2 + L_1/ε)(f(x^0)−f^*)) iterations. To the best of our knowledge, this is the first work to establish, for a single parameter-free algorithm, the best-known iteration-complexity guarantee in the nonconvex setting while also providing the above iteration-complexity guarantee in the convex setting. Experiments on logistic regression and real phase retrieval demonstrate that our method can exploit (L_0,L_1)-smoothness and perform efficiently on nonconvex problems.
ER -