Zeroth-order optimization with orthogonal random directions

• 成果类型: Article
• 署名作者: Kozak, David; Molinari, Cesare; Rosasco, Lorenzo; Tenorio, Luis; Villa, Silvia
• 署名单位: Istituto Italiano di Tecnologia - IIT; University of Genoa; Colorado School of Mines; University of Genoa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01866-9
• 发表日期: 2023
• 页码: 1179-1219
• 关键词: convergence; complexity; algorithms

摘要

We propose and analyze a randomized zeroth-order optimization method 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, coordinate descent, 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 the Polyak-Lojasiewicz (PL) condition. Theoretical results are complemented and illustrated by numerical experiments.