Compositional Stochastic Average Gradient for Machine Learning and Related Applications
This work addresses optimization challenges in machine learning, statistical inference, and portfolio optimization, presenting an incremental improvement over existing methods.
The paper tackles the problem of minimizing compositions of finite-sum expected value functions (FS-CEVF) in machine learning and related fields by introducing compositional stochastic average gradient descent (C-SAG), which achieves a linear convergence rate and lower oracle query complexity per iteration than the state-of-the-art C-SVRG, with experiments showing substantially faster convergence.
Many machine learning, statistical inference, and portfolio optimization problems require minimization of a composition of expected value functions (CEVF). Of particular interest is the finite-sum versions of such compositional optimization problems (FS-CEVF). Compositional stochastic variance reduced gradient (C-SVRG) methods that combine stochastic compositional gradient descent (SCGD) and stochastic variance reduced gradient descent (SVRG) methods are the state-of-the-art methods for FS-CEVF problems. We introduce compositional stochastic average gradient descent (C-SAG) a novel extension of the stochastic average gradient method (SAG) to minimize composition of finite-sum functions. C-SAG, like SAG, estimates gradient by incorporating memory of previous gradient information. We present theoretical analyses of C-SAG which show that C-SAG, like SAG, and C-SVRG, achieves a linear convergence rate when the objective function is strongly convex; However, C-CAG achieves lower oracle query complexity per iteration than C-SVRG. Finally, we present results of experiments showing that C-SAG converges substantially faster than full gradient (FG), as well as C-SVRG.