EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

901. An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization

Invited abstract in session TC-32: Algorithms for machine learning and inverse problems: zeroth-order optimisation, stream Advances in large scale nonlinear optimization.

Tuesday, 12:30-14:00
Room: 41 (building: 303A)

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

Status: accepted

Back to the list of papers