Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization

R may be neither smooth nor convex. Such problems are ubiquitous throughout machine learning, where losses given by deep-learning based models give rise to highly nonsmooth nonconvex (NSNC) landscapes. Due to its fundamental importance in modern machine learning, the field of nonconvex optimization has received substantial attention in recent years. Moving away from the classical regime of convex optimization, many works aimed at understanding the complexity of producing approximatestationary points, namely with small gradient norm [Ghadimi and Lan, 2013, Fang et al., 2018, Carmon et al., 2020, Arjevani et al., 2023]. As it turns out, without smoothness, it is impossible to directly minimize the gradient norm without suffering from an exponential-dimension dependent runtime in the worst case [Kornowski and Shamir, 2022]. Nonetheless, a nuanced notion coined as Goldstein-stationarity [Goldstein, 1977], has been shown in recent years to enable favorable guarantees.