Session: Derivative-free optimization for large scale problems
Chair: Zaikun Zhang
Cluster: Derivative-free Optimization
Talk 1: Scalable derivative-free optimization algorithms with low-dimensional subspace techniques
Speaker: Zaikun Zhang
Abstract: We re-introduce a derivative-free subspace optimization framework originating from Chapter 5 the thesis [Z. Zhang, On Derivative-Free Optimization Methods, PhD thesis, Chinese Academy of Sciences, Beijing, 2012] of the author under the supervision of Ya-xiang Yuan. At each iteration, the framework defines a (low-dimensional) subspace based on an approximate gradient, and then solves a subproblem in this subspace to generate a new iterate. We sketch the global convergence and worst-case complexity analysis of the framework, elaborate on its implementation, and present some numerical results on solving problems with dimension as high as 10,000. The same framework was presented during ICCOPT 2013 in Lisbon under the title "A Derivative-Free Optimization Algorithm with Low-Dimensional Subspace Techniques for Large-Scale Problems", although it remains nearly unknown to the community until very recently. An algorithms following this framework named NEWUOAs was implemented by Zhang in MATLAB in 2011 (https://github.com/newuoas/newuoas), ported to Module-3 by Nystroem (Intel) in 2017, and included in cm3 in 2019 (https://github.com/modula3/cm3/blob/master/caltech-other/newuoa/src/NewUOAs.m3).
Talk 2: High-dimensional DFO: Stochastic subspace descent and improvements
Speaker: Stephen Becker
Abstract: We describe and analyze a family of algorithms which we call "stochastic subspace descent" which use projections of the gradient onto random subspaces, in a slightly similar spirit to well-known work by Nesterov and Spokoiny. We explain the benefits of subspace projection compared to Gaussian directional derivatives. We present a complete convergence analysis, and show that the method is well suited for high-dimensional problems. We also focus on our very recent work for cheap and automatic stepsize selection, as well as some preliminary results on biased sampling which requires leaving the "projected" paradigm.
Talk 3: Blockwise direct search methods
Speaker: Haitian Li
Abstract: Direct search methods are one class of derivative-free optimization algorithms that evaluate the objective function only based on the comparison of function values. We introduce a new framework of direct search method called blockwise direct search (BDS), which divides the searching set into blocks. For every iteration, each block has its step size. We develop this framework into a solver, which is open-source and easy to use. In numerical experiments, we observe that BDS can also be compared with model based methods in some cases. In addition, our solver shows its efficiency and stability under noise without introducing specific techniques. BDS can also be used to tune the hyperparameters itself to improve the performance.
