On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization
On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization
复制标题
关于确定性非光滑和非凸优化的复杂性
DOI：
10.48550/arxiv.2209.12463
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Manolis Zampetakis
中科院分区：
文献类型：
--
作者：
Michael I. Jordan;Tianyi Lin;Manolis Zampetakis
In this paper, we present several new results on minimizing a nonsmooth and nonconvex function under a Lipschitz condition. Recent work shows that while the classical notion of Clarke stationarity is computationally intractable up to some sufficiently small constant tolerance, the randomized first-order algorithms find a $(\delta, \epsilon)$-Goldstein stationary point with the complexity bound of $\tilde{O}(\delta^{-1}\epsilon^{-3})$, which is independent of dimension $d \geq 1$~\citep{Zhang-2020-Complexity, Davis-2022-Gradient, Tian-2022-Finite}. However, the deterministic algorithms have not been fully explored, leaving open several problems in nonsmooth nonconvex optimization. Our first contribution is to demonstrate that the randomization is \textit{necessary} to obtain a dimension-independent guarantee, by proving a lower bound of $\Omega(d)$ for any deterministic algorithm that has access to both $1^{st}$ and $0^{th}$ oracles. Furthermore, we show that the $0^{th}$ oracle is \textit{essential} to obtain a finite-time convergence guarantee, by showing that any deterministic algorithm with only the $1^{st}$ oracle is not able to find an approximate Goldstein stationary point within a finite number of iterations up to sufficiently small constant parameter and tolerance. Finally, we propose a deterministic smoothing approach under the \textit{arithmetic circuit} model where the resulting smoothness parameter is exponential in a certain parameter $M>0$ (e.g., the number of nodes in the representation of the function), and design a new deterministic first-order algorithm that achieves a dimension-independent complexity bound of $\tilde{O}(M\delta^{-1}\epsilon^{-3})$.
In this paper, we present several new results on minimizing a nonsmooth and nonconvex function under a Lipschitz condition. Recent work shows that while the classical notion of Clarke stationarity is computationally intractable up to some sufficiently small constant tolerance, the randomized first-order algorithms find a $(\delta, \epsilon)$-Goldstein stationary point with the complexity bound of $\tilde{O}(\delta^{-1}\epsilon^{-3})$, which is independent of dimension $d \geq 1$~\citep{Zhang-2020-Complexity, Davis-2022-Gradient, Tian-2022-Finite}. However, the deterministic algorithms have not been fully explored, leaving open several problems in nonsmooth nonconvex optimization. Our first contribution is to demonstrate that the randomization is \textit{necessary} to obtain a dimension-independent guarantee, by proving a lower bound of $\Omega(d)$ for any deterministic algorithm that has access to both $1^{st}$ and $0^{th}$ oracles. Furthermore, we show that the $0^{th}$ oracle is \textit{essential} to obtain a finite-time convergence guarantee, by showing that any deterministic algorithm with only the $1^{st}$ oracle is not able to find an approximate Goldstein stationary point within a finite number of iterations up to sufficiently small constant parameter and tolerance. Finally, we propose a deterministic smoothing approach under the \textit{arithmetic circuit} model where the resulting smoothness parameter is exponential in a certain parameter $M>0$ (e.g., the number of nodes in the representation of the function), and design a new deterministic first-order algorithm that achieves a dimension-independent complexity bound of $\tilde{O}(M\delta^{-1}\epsilon^{-3})$.
登录
查看更多内容
DOI：
10.1137/090774100
发表时间：
2010-08
期刊：
SIAM J. Optim.
影响因子：
--
作者：
C. Cartis;N. Gould;P. Toint
通讯作者：
C. Cartis;N. Gould;P. Toint
DOI：
--
发表时间：
2021-12
期刊：
--
影响因子：
--
作者：
Damek Davis;D. Drusvyatskiy;Y. Lee;Swati Padmanabhan;Guanghao Ye
通讯作者：
Damek Davis;D. Drusvyatskiy;Y. Lee;Swati Padmanabhan;Guanghao Ye
DOI：
10.1137/19m1298147
发表时间：
2019-10
期刊：
SIAM J. Optim.
影响因子：
--
作者：
A. Daniilidis;D. Drusvyatskiy
通讯作者：
A. Daniilidis;D. Drusvyatskiy
影响因子：
3
作者：
Davis, Damek;Drusvyatskiy, Dmitriy;Lee, Jason D.
通讯作者：
Lee, Jason D.