Session: Derivative-free optimization for special classes of problems I
Chair: Clément Royer
Cluster: Derivative-free Optimization
Talk 1: A derivative-free algorithm for continuous submodular optimization
Speaker: Clément Royer
Abstract: Submodular functions are a classical concept of discrete optimization, that can also be extended to the continuous setting. In particular, the class of continuous submodular functions encompasses some nonconvex functions arising in natural language processing, which partly explains renewed interest for this topic in recent years. In this talk, we propose a derivative-free algorithm for submodular optimization over compact sets, adapted from a classical framework for bound-constrained derivative-free optimization. By leveraging properties of submodular functions, we obtain complexity guarantees for this method, that represent a significant improvement over guarantees in the general, nonconvex setting. We then investigate the practical behavior of our method on our problems of interest.
Talk 2: The cosine measure of a function
Speaker: Gabriel Jarry-Bolduc
Abstract: The cosine measure of a set of vectors is a valuable tool in derivative-free optimization to judge the quality of a set of vectors. It gives information on how uniformly the set of vectors is covering the space R^n. A set of vectors is a positive spanning set of R^n if and only if its cosine measure is greater than zero. An important property of positive spanning sets is that when the gradient of a function at a point is well-defined and not equal to the zero vector, then there is at least one descent direction (ascent direction) of the function at the point contained in the set. This is not necessarily true if the gradient is equal to the zero vector or if the gradient does not exist. To characterize the previous two cases, the novel concept of cosine measure of a function is introduced in this talk. It provides an infimum on the value of the cosine measure of a set of vectors guaranteed to contain a descent direction of the function at the point of interest. It is shown how to theoretically compute the cosine measure of a function for popular classes of nonsmooth functions.
Talk 3: 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).
