Deterministic methods for derivative-free optimization that use finite difference to approximately conduct first-order updates usually have an evaluation cost per iteration proportional to the problem dimension, making these methods prohibitively expensive for high-dimensional problem.

In this work, we consider a regularized setting of minimizing the sum of a smooth function and a nonsmooth regularization term, where we only have access to the function value of the smooth term but assume full knowledge of the regularization. By identifying the structure at the point of convergence induced by the regularization using an inexact proximal gradient method constructed through finite difference, we propose an acceleration method whose per-iteration evaluation cost is linear only to the rank of the structure instead of the original problem dimension, and thus making the algorithm much more efficient without harming the convergence guarantees. We discuss how the structure can be found under a general error bound condition, and cover related convergence properties.

We further consider a progressive identification strategy that gradually decreases the estimated rank of the structure through an approximate Riemannian proximal gradient method by confining to the manifold that represents the structure at the current point, and discuss how it could potentially improve the convergence speed.

This is joint work with Geovani Nunes Grapiglia.

LEE Ching-pei is an Associate Professor at the Institute of Statistical Mathematics and will hold a joint appointment in the Department of Mathematical Informatics at the University of Tokyo starting in September. Ching-pei received a Ph.D. in Computer Sciences with a minor in Mathematics from the University of Wisconsin-Madison under the supervision of Stephen J. Wright. Ching-pei's research focuses on efficient algorithms for large-scale problems in nonlinear optimization and their applications in machine learning, with an emphasis on both theoretical analysis and practical performance. Dr. Lee is the recipient of several prestigious honors and fellowships, including the BOOST Fellowship and the PRESTO Fellowship from the Japan Science and Technology Agency, as well as the Emerging Young Scholars Award from the Ministry of Science and Technology of Taiwan.