EURO 2025 Leeds
Abstract Submission

812. Structured Finite-Difference Methods for Zeroth-order Optimization

Invited abstract in session WA-35: Recent trends in zeroth order and simulation-based optimization: 2, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.

Wednesday, 8:30-10:00
Room: Michael Sadler LG15

Authors (first author is the speaker)

1. Marco Rando
Malga - DIBRIS, Universita degli Studi di Genova
2. Cheik Traoré
University of Genoa
3. Cesare Molinari
Università di Genova
4. Lorenzo Rosasco
DIBRIS, Universita' di Genova
5. Silvia Villa
Department of Mathematics, MaLGa, università di Genova

Abstract

Finite-difference methods are widely used for solving black-box optimization problems by approximating function gradients along selected directions. Recent advancements have shown that imposing structure in these directions improves performance, but existing results are often restricted to specific settings or particular choices of directions. In this work, we extend structured finite-difference methods to a broader range of settings. We begin by proposing and analyzing a structured finite-difference method for stochastic smooth optimization, introducing a new gradient approximation technique. We analyze our approach in smooth convex and PL non-convex settings. We then address non-smooth black-box optimization by developing a structured finite-difference algorithm that leverages a smooth approximation of the target function. Our analysis establishes that this method accurately estimates gradients along a subset of random orthogonal directions and achieves optimal complexity in terms of dimension dependence. Finally, we consider black-box finite-sum optimization and incorporate variance reduction techniques into our framework. We provide theoretical guarantees for our approach in multiple settings and validate our findings through numerical experiments, showing better performance compared to state-of-the-art algorithms.

Keywords

Status: accepted

Back to the list of papers