Answers are grounded in this paper and cite their sources.
This study introduces a new subgradient growth condition for randomized smoothing, improving sample complexity for locally Lipschitz functions.
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 Õ(d5/2δ⁻¹ε⁻⁴). By incorporating variance reduction techniques, we further improve the sample complexity to Õ(d3/2δ⁻¹ε⁻³), matching the optimal $ε$-bound under the global Lipschitz assumption, up to a logarithmic factor. Experimental results validate the effectiveness of our proposed algorithms.
No takes yet. Share an insight, caveat, or question.
Xia et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: