2020/08/24 by Krishnakumar Balasubramanian, Saeed Ghadimi, Balasubramanian, Krishnakumar +3
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2008.10526
openalex publication_date 2020/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study smooth stochastic multi-level composition optimization problems, where the objective function is a nested composition of T functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze their convergence to an ε-stationary point of the problem. We show that the first algorithm, which is a generalization of \citeGhaRuswan20 to the T level case, can achieve a sample complexity of O(1/ε6) by using mini-batches of samples in each iteration. By modifying this algorithm using linearized stochastic estimates of the function values, we improve the sample complexity to O(1/ε4). \colorblackThis modification not only removes the requirement of having a mini-batch of samples in each iteration, but also makes the algorithm parameter-free and easy to implement. To the best of our knowledge, this is the first time that such an online algorithm designed for the (un)constrained multi-level setting, obtains the same sample complexity of the smooth single-level setting, under standard assumptions (unbiasedness and boundedness of the second moments) on the stochastic first-order oracle.