We propose and analyze a randomized zeroth-order approach based on approximating the exact gradient by finite differences computed in a set of orthogonal random directions that changes with each iteration. A number of previously proposed methods are recovered as special cases including spherical smoothing, coordinat edescent, as well as discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence rates under different parameter choices and assumptions. In particular, we consider convex objectives, but also possibly non-convex objectives satisfying thePolyak-Łojasiewicz (PL) condition. Theoretical results are complemented and illustrated by numerical experiments.

Zeroth order optimization with orthogonal random directions

David Kozak;Cesare Molinari;Lorenzo Rosasco;Silvia Villa
2022-01-01

Abstract

We propose and analyze a randomized zeroth-order approach based on approximating the exact gradient by finite differences computed in a set of orthogonal random directions that changes with each iteration. A number of previously proposed methods are recovered as special cases including spherical smoothing, coordinat edescent, as well as discretized gradient descent. Our main contribution is proving convergence guarantees as well as convergence rates under different parameter choices and assumptions. In particular, we consider convex objectives, but also possibly non-convex objectives satisfying thePolyak-Łojasiewicz (PL) condition. Theoretical results are complemented and illustrated by numerical experiments.
File in questo prodotto:
File Dimensione Formato  
2107.03941.pdf

accesso aperto

Tipologia: Documento in Post-print
Dimensione 807.23 kB
Formato Adobe PDF
807.23 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11567/1097753
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 4
social impact