Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

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.

We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. %In this paper, we demonstrate that a vanilla stochastic algorithm---without additional modifications such as clipping or normalization---can achieve optimal complexity for these problems. In this paper, we analyze the first-order oracle complexity of vanilla stochastic algorithms---without additional modifications such as clipping or normalization---for solving these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity for finding an approximate optimal solution in expectation that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Moreover, we derive high-probability first-order oracle complexity bounds for the accelerated stochastic proximal subgradient method under heavy-tailed and sub-Weibull noise, respectively. Numerical experiments are further provided to illustrate the numerical behavior of the methods.

In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems with exact constraints and stochastic objective evaluations. To solve this class of problems, we propose a framework of mirror descent linearized augmented Lagrangian methods that employs two-point stochastic zeroth-order gradient estimators and exploits non-Euclidean mirror descent geometry. Under mild assumptions, we establish oracle complexity guarantees for finding an $ε$-KKT point parameterized by $p \geq 2$. Under Rademacher smoothing, our analysis reveals a trade-off between the variance of the zeroth-order gradient estimators and the smoothness of the mirror map. In the high-accuracy regime, the resulting effective oracle complexity is $\mathcal{O}(p d^{2/p}ε^{-3})$ for $p \in [2,2\ln d]$ and $\mathcal{O}(\ln d\,ε^{-3})$ for $p > 2\ln d$. These bounds reduce the dimension dependence in the leading term. When $p=2$, our method recovers the Euclidean setting with an oracle complexity of $\mathcal{O}(dε^{-3})$, improving the $ε$-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an $ε$-KKT point within $\mathcal{O}(1+\log\log(e/ε))$ stages while maintaining the leading-order complexity. Numerical tests on QCQPs, black-box adversarial attacks, and fairness-constrained classification demonstrate the effectiveness of our proposed method.