181. An optimal structured zeroth-order algorithm for non-smooth optimization
Invited abstract in session WF-7: Regularization methods for Machine Learning and Inverse Problems, stream Optimization for Inverse Problems and Machine Learning.
Wednesday, 16:20 - 18:00Room: M:I
Authors (first author is the speaker)
| 1. | Marco Rando
|
| Malga - DIBRIS, Universita degli Studi di Genova | |
| 2. | Cesare Molinari
|
| Università di Genova | |
| 3. | Lorenzo Rosasco
|
| MaLGa, DIBRIS, Università di Genova | |
| 4. | Silvia Villa
|
| Department of Mathematics, MaLGa, 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 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 our procedure under different assumptions. In particular, 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.
Keywords
- Derivative-free optimization
- Convex and non-smooth optimization
Status: accepted
Back to the list of papers