Unbiased Simulation for Optimizing Stochastic Function Compositions

Abstract

In this paper, we introduce an unbiased gradient simulation algorithms for solving convex optimization problem with stochastic function compositions. We show that the unbiased gradient generated from the algorithm has finite variance and finite expected computation cost. We then combined the unbiased gradient simulation with two variance reduced algorithms (namely SVRG and SCSG) and showed that the proposed optimization algorithms based on unbiased gradient simulations exhibit satisfactory convergence properties. Specifically, in the SVRG case, the algorithm with simulated gradient can be shown to converge linearly to optima in expectation and almost surely under strong convexity. Finally, for the numerical experiment,we applied the algorithms to two important cases of stochastic function compositions optimization: maximizing the Cox's partial likelihood model and training conditional random fields.

References in corpus (1)

• Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity

Cited by in corpus (8)

• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• ES-MAML: Simple Hessian-Free Meta Learning
• A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
• Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization
• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Unbiased Gradient Estimation for Distributionally Robust Learning