{"ID":2880500,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13496","arxiv_id":"2508.13496","title":"Revisiting Randomized Smoothing: Nonsmooth Nonconvex Optimization Beyond Global Lipschitz Continuity","abstract":"Randomized smoothing is a widely adopted technique for optimizing nonsmooth objective functions. However, its efficiency analysis typically relies on global Lipschitz continuity, a condition rarely met in practical applications. To address this limitation, we introduce a new subgradient growth condition that naturally encompasses a wide range of locally Lipschitz functions, with the classical global Lipschitz function as a special case. Under this milder condition, we prove that randomized smoothing yields a differentiable function that satisfies certain generalized smoothness properties. To optimize such functions, we propose novel randomized smoothing gradient algorithms that, with high probability, converge to $(δ, ε)$-Goldstein stationary points and achieve a sample complexity of $\\tilde{\\mathcal{O}}(d^{5/2}δ^{-1}ε^{-4})$. By incorporating variance reduction techniques, we further improve the sample complexity to $\\tilde{\\mathcal{O}}(d^{3/2}δ^{-1}ε^{-3})$, matching the optimal $ε$-bound under the global Lipschitz assumption, up to a logarithmic factor. Experimental results validate the effectiveness of our proposed algorithms.","short_abstract":"Randomized smoothing is a widely adopted technique for optimizing nonsmooth objective functions. However, its efficiency analysis typically relies on global Lipschitz continuity, a condition rarely met in practical applications. To address this limitation, we introduce a new subgradient growth condition that naturally...","url_abs":"https://arxiv.org/abs/2508.13496","url_pdf":"https://arxiv.org/pdf/2508.13496v3","authors":"[\"Jingfan Xia\",\"Zhenwei Lin\",\"Qi Deng\"]","published":"2025-08-19T04:10:38Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}