162. An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization
Invited abstract in session WE-5: Randomized optimization algorithms part 1/2, stream Randomized optimization algorithms.
Wednesday, 14:10 - 15:50Room: M:N
Authors (first author is the speaker)
| 1. | Cesare Molinari
|
| Università di Genova |
Abstract
Finite-difference methods are a class of algorithms designed to solve black-box optimization problems by approximating a gradient of the target function on a set of directions. In black-box optimization, the non-smooth setting is particularly relevant since, in practice, differentiability and smoothness assumptions cannot be verified. To cope with nonsmoothness, several authors use a smooth approximation of the target function and show that finite difference methods approximate its gradient. Recently, it has been proved that imposing a structure in the directions allows improving performance. However, only the smooth setting was considered. To close this gap, we introduce and analyze O-ZD, the first structured finite-difference algorithm for non-smooth black-box optimization. Our method exploits a smooth approximation of the target function and we prove that it approximates its gradient on a subset of random orthogonal directions. We analyze the convergence of O-ZD under different assumptions. For non-smooth convex functions, we obtain the optimal complexity. In the non-smooth non-convex setting, we characterize the number of iterations needed to bound the expected norm of the smoothed gradient. For smooth functions, our analysis recovers existing results for structured zeroth-order methods for the convex case and extends them to the non-convex setting. We conclude with numerical simulations, observing that our algorithm has very good practical performance.
Keywords
- Derivative-free optimization
- Convex and non-smooth optimization
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers