Zeroth-Order Random Subspace Algorithm for Non-smooth Convex Optimization

作     者：Nozawa, Ryota Poirion, Pierre-Louis Takeda, Akiko 

作者机构：Univ Tokyo Dept Math Informat Tokyo Japan RIKEN Ctr Adv Intelligence Project Tokyo Japan 

出 版 物：《JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS》 (J. Optim. Theory Appl.)

年 卷 期：2025年第204卷第3期

页      面：1-31页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：JSPS KAKENHI [23H03351] JST ERATO [JPM-JER1903] 

主　　题：Zeroth-order optimization Random projection Convex optimization Oracle complexity 

摘      要：Zeroth-order optimization, which does not use derivative information, is one of the significant research areas in the field of mathematical optimization and machine learning. Although various studies have explored zeroth-order algorithms, one of the theoretical limitations is that oracle complexity depends on the dimension, i.e., on the number of variables, of the optimization problem. In this paper, to reduce the dependency of the dimension in oracle complexity, we propose a zeroth-order random subspace algorithm by combining a gradient-free algorithm (specifically, Gaussian randomized smoothing with central differences) with random projection. We derive the worst-case oracle complexity of our proposed method in non-smooth and convex settings;it is equivalent to standard results for full-dimensional non-smooth convex algorithms. Furthermore, we prove that ours also has a local convergence rate independent of the original dimension under additional assumptions. In addition to the theoretical results, numerical experiments show that when an objective function has a specific structure, the proposed method can become experimentally more efficient due to random projection.