Non-Smooth Non-Convex Stochastic Optimization: Sign-Based Methods and Beyond

Gradient compression algorithms, such as sign-based methods, are widely used to reduce the computational and communication overhead of large-scale optimization. However, existing studies rely on smoothness or convexity assumptions, which are frequently violated in real-world applications. To address this limitation, we initiate the study of non-smooth non-convex stochastic optimization with compressed gradients. Let $d$ denote the dimensionality. First, we develop a sign-based online method and incorporate it into the online-to-non-convex (O2NC) conversion, which yields a query complexity of $O(d{ϵ}^{-3}{\delta }^{-1})$. Second, we consider the zeroth-order optimization setting, where only noisy function values are accessible. In this regime, our method attains an $O(d{ϵ}^{-3}{\delta }^{-1})$ query complexity, which simultaneously matches that of the first-order compressed setting and the optimal $O(d{ϵ}^{-3}{\delta }^{-1})$ complexity of zeroth-order optimization without compression. The primary idea is to design a compression-estimation decoupling strategy, which constructs the gradient estimator with multiple samples and recursively applies the sign compressor over several rounds, thereby controlling the estimation and compression errors at the same time. Finally, we extend our methods to general compressors and to distributed stochastic optimization with bidirectional compression in both the first-order and zeroth-order settings.