Deterministic nonsmooth optimization needs exponentially more effort than randomized methods
The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization
Machine Learning
Summary
Finding good solutions for certain complicated optimization problems can be done efficiently using random methods. The authors show that if you try to solve these problems using only fixed, predictable steps, the time needed grows exponentially with the problem's size. This means randomization offers a big speed advantage for some hard mathematical problems. Their work settles a long-standing question about the limits of deterministic methods.
What this means in practice
- •For optimization engineers: Understand that deterministic algorithms require exponentially more computational effort in high-dimensional nonsmooth problems, guiding method choice for large-scale optimization.
- •For machine learning developers: Avoid deterministic nonsmooth optimization methods in training models with nonsmooth loss functions due to their impractical computational costs compared to randomized approaches.
A theory result. No direct application yet.
Authors
Guy Kornowski
Abstract
We study the complexity of finding $(δ,ε)$-Goldstein stationary points of nonsmooth nonconvex Lipschitz functions. By now, it is known that randomized first-order algorithms can solve this task with a dimension-free oracle complexity [Zhang et al., 2020], whereas deterministic algorithms cannot, as their complexity must scale at least linearly with the dimension $d$ [Jordan et al., 2023, Tian and So, 2024]. This leaves open whether deterministic algorithms can nevertheless solve the problem with oracle complexity polynomial in $d$. We answer this question negatively by proving a lower bound of order $(1/ε)^{Ω(d)}$ for deterministic algorithm, closing the exponential gap between the previously known lower and upper bounds and resolving an open problem posed by Jordan et al. [2023]. We further discuss several extensions and implications of this result to weaker stationarity notions, finding a descent direction and deterministic smoothing. Overall, our results establish an exponential computational advantage in nonsmooth nonconvex optimization offered by randomization.