More Like this

1. Deterministic Nonsmooth Nonconvex Optimization

   Michael I. Jordan; Guy Kornowski; Tianyi Lin; Ohad Shamir; Manolis Zampetakis (July 2023, Conference on Learning Theory)

   We study the complexity of optimizing nonsmooth nonconvex Lipschitz functions by producing (δ, ǫ)-Goldstein stationary points. Several recent works have presented randomized algorithms that produce such points using eO(δ−1ǫ−3) first-order oracle calls, independent of the dimension d. It has been an open problem as to whether a similar result can be obtained via a deterministic algorithm. We resolve this open problem, showing that randomization is necessary to obtain a dimension-free rate. In particular, we prove a lower bound of (d) for any deterministic algorithm. Moreover, we show that unlike smooth or convex optimization, access to function values is required for any deterministic algorithm to halt within any finite time horizon. On the other hand, we prove that if the function is even slightly smooth, then the dimension-free rate of eO(δ−1ǫ−3) can be obtained by a deterministic algorithm with merely a logarithmic dependence on the smoothness parameter. Motivated by these findings, we turn to study the complexity of deterministically smoothing Lipschitz functions. Though there are well-known efficient black-box randomized smoothings, we start by showing that no such deterministic procedure can smooth functions in a meaningful manner (suitably defined), resolving an open question in the literature. We then bypass this impossibility result for the structured case of ReLU neural networks. To that end, in a practical “white-box” setting in which the optimizer is granted access to the network’s architecture, we propose a simple, dimension-free, deterministic smoothing of ReLU networks that provably preserves (δ, ǫ)-Goldstein stationary points. Our method applies to a variety of architectures of arbitrary depth, including ResNets and ConvNets. Combined with our algorithm for slightly-smooth functions, this yields the first deterministic, dimension-free algorithm for optimizing ReLU networks, circumventing our lower bound. 

   more » « less
2. Outlier-robust nonsmooth stochastic optimization

   https://doi.org/10.23952/jnva.10.2026.2.2  

   Li, Shuyao; Wright, Stephen; Diakonikolas, Jelena (January 2026, Journal of Nonlinear and Variational Analysis)

   Mordukhovich, Boris S; Qin, Xiaolong; Yao, Jen-Chih (Ed.)
3. Real Options Problem with Nonsmooth Obstacle

   https://doi.org/10.1137/20M1386815  

   Acharya, Subas; Bensoussan, Alain; Rachinskii, Dmitrii; Rivera, Alejandro (January 2021, SIAM Journal on Financial Mathematics)
4. The nonsmooth landscape of phase retrieval

   https://doi.org/10.1093/imanum/drz031  

   Davis, Damek; Drusvyatskiy, Dmitriy; Paquette, Courtney (January 2020, IMA Journal of Numerical Analysis)

   Abstract We consider a popular nonsmooth formulation of the real phase retrieval problem. We show that under standard statistical assumptions a simple subgradient method converges linearly when initialized within a constant relative distance of an optimal solution. Seeking to understand the distribution of the stationary points of the problem, we complete the paper by proving that as the number of Gaussian measurements increases, the stationary points converge to a codimension two set, at a controlled rate. Experiments on image recovery problems illustrate the developed algorithm and theory. 

   more » « less
5. Nonsmooth rank-one matrix factorization landscape

   https://doi.org/10.1007/s11590-021-01819-9  

   Josz, C.; Lexiao, L. (November 2021, Optimization letters)

   We provide the first positive result on the nonsmooth optimization landscape of robust principal component analysis, to the best of our knowledge. It is the object of several conjectures and remains mostly uncharted territory. We identify a necessary and sufficient condition for the absence of spurious local minima in the rank-one case. Our proof exploits the subdifferential regularity of the objective function in order to eliminate the existence quantifier from the first-order optimality condition known as Fermat’s rule. 

   more » « less