2022/02/09 by Tesi Xiao, Krishnakumar Balasubramanian, Xiao, Tesi +3
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2202.04296
openalex publication_date 2022/02/09 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
We propose a projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization, where the objective function is a nested composition of T functions and the constraint set is a closed convex set. Our algorithm assumes access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle satisfying certain standard unbiasedness and second moment assumptions. We show that the number of calls to the stochastic first-order oracle and the linear-minimization oracle required by the proposed algorithm, to obtain an ε-stationary solution, are of order OT(ε-2) and OT(ε-3) respectively, where OT hides constants in T. Notably, the dependence of these complexity bounds on ε and T are separate in the sense that changing one does not impact the dependence of the bounds on the other. Moreover, our algorithm is parameter-free and does not require any (increasing) order of mini-batches to converge unlike the common practice in the analysis of stochastic conditional gradient-type algorithms.