Zeroth-Order Non-smooth Non-convex Optimization via Gaussian Smoothing
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911737207324672 |
|---|---|
| author | Paul, Anik Kumar Bhatnagar, Shalabh |
| author_facet | Paul, Anik Kumar Bhatnagar, Shalabh |
| contents | This paper addresses stochastic optimization of Lipschitz-continuous, nonsmooth and nonconvex objectives over compact convex sets, where only noisy function evaluations are available. While gradient-free methods have been developed for smooth nonconvex problems, extending these techniques to the nonsmooth setting remains challenging. The primary difficulty arises from the absence of a Taylor series expansion for Clarke subdifferentials, which limits the ability to approximate and analyze the behavior of the objective function in a neighborhood of a point. We propose a two time-scale zeroth-order projected stochastic subgradient method leveraging Gaussian smoothing to approximate Clarke subdifferentials. First, we establish that the expectation of the Gaussian-smoothed subgradient lies within an explicitly bounded error of the Clarke subdifferential, a result that extends prior analyses beyond convex/smooth settings. Second, we design a novel algorithm with coupled updates: a fast timescale tracks the subgradient approximation, while a slow timescale drives convergence. Using continuous-time dynamical systems theory and robust perturbation analysis, we prove that iterates converge almost surely to a neighborhood of the set of Clarke stationary points, with neighborhood size controlled by the smoothing parameter. To our knowledge, this is the first zeroth-order method achieving almost sure convergence for constrained nonsmooth nonconvex optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11073 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Zeroth-Order Non-smooth Non-convex Optimization via Gaussian Smoothing Paul, Anik Kumar Bhatnagar, Shalabh Optimization and Control This paper addresses stochastic optimization of Lipschitz-continuous, nonsmooth and nonconvex objectives over compact convex sets, where only noisy function evaluations are available. While gradient-free methods have been developed for smooth nonconvex problems, extending these techniques to the nonsmooth setting remains challenging. The primary difficulty arises from the absence of a Taylor series expansion for Clarke subdifferentials, which limits the ability to approximate and analyze the behavior of the objective function in a neighborhood of a point. We propose a two time-scale zeroth-order projected stochastic subgradient method leveraging Gaussian smoothing to approximate Clarke subdifferentials. First, we establish that the expectation of the Gaussian-smoothed subgradient lies within an explicitly bounded error of the Clarke subdifferential, a result that extends prior analyses beyond convex/smooth settings. Second, we design a novel algorithm with coupled updates: a fast timescale tracks the subgradient approximation, while a slow timescale drives convergence. Using continuous-time dynamical systems theory and robust perturbation analysis, we prove that iterates converge almost surely to a neighborhood of the set of Clarke stationary points, with neighborhood size controlled by the smoothing parameter. To our knowledge, this is the first zeroth-order method achieving almost sure convergence for constrained nonsmooth nonconvex optimization problems. |
| title | Zeroth-Order Non-smooth Non-convex Optimization via Gaussian Smoothing |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.11073 |