A0666
Title: Statistical learning theory for stochastic compositional gradient methods
Authors: Yiming Ying - University of Sydney (Australia) [presenting]
Abstract: Many machine learning tasks can be framed as stochastic compositional optimization (SCO) problems, including reinforcement learning, AUC maximization, and meta-learning, where the objective function involves a nested composition associated with an expectation. While numerous studies have focused on the convergence behavior of SCO algorithms, little attention has been given to understanding their generalization, i.e., how these learning algorithms generalize from training to test examples. The stability and generalization analysis of stochastic compositional gradient descent algorithms is delved into within the framework of statistical learning theory. Specifically, the compositional uniform stability of two prominent stochastic compositional gradient descent algorithms is examined, namely SCGD and SCSC. In contrast to existing literature, the analysis yields dimension-independent bounds that underscore the critical dependence of the SCO algorithm's generalization on two key factors: the variance of the gradient of the inner function and the convergence of the moving average term to the true inner function. Moreover, the findings exemplify the intricate interplay between statistical and computational behaviors in stochastic optimization for machine learning.
