Augmenting subspace optimization methods with linear bandits

Abstract

In this work, we consider the framework of methods for unconstrained minimization that are, in each iteration, restricted to a model that is only a valid approximation to the objective function on some affine subspace containing an incumbent point. These methods are of practical interest in computational settings where derivative information is either expensive or impossible to obtain. Recent attention has been paid in the literature to employing randomized matrix sketching for generating the affine subspaces within this framework. We consider a relatively straightforward, deterministic augmentation of such a generic subspace optimization method. In particular, we consider a sequential optimization framework where actions consist of one-dimensional linear subspaces and rewards consist of (approximations to) the magnitudes of directional derivatives computed in the direction of the action subspace. Reward maximization in this context is consistent with maximizing lower bounds on descent guaranteed by first-order Taylor models. This sequential optimization problem can be analysed through the lens of dynamic regret. We modify an existing linear upper confidence bound (UCB) bandit method and prove sublinear dynamic regret in the subspace optimization setting. We demonstrate the efficacy of employing this linear UCB method in a setting where forward-mode algorithmic differentiation can provide directional derivatives in arbitrary directions and in a derivative-free setting. For the derivative-free setting, we propose SS-POUNDers, an extension of the derivative-free optimization method POUNDers that employs the linear UCB mechanism to identify promising subspaces. Our numerical experiments suggest a preference, in either computational setting, for employing a linear UCB mechanism within a subspace optimization method.