Variance Reduced methods for Non-convex Composition Optimization

This composition between two finite-sum structures 1 n n i 1 F i ( 1 m m j 1 G j (x)) arises in many machine learning applications such as reinforcement learning [1, 2, 3] and nonlinear embedding [4]. For example, stochastic neighbor embedding (SNE) [4] is a powerful approach to map data from a high dimensional space to a low dimensional space. Let{ z i} n i 1 and { x i} n i 1 denote the representation ofn data points in the high dimensional space and the low dimensional space, respectively. The objective is to pursue a low dimensional representation{ x i} n i 1, such that the distribution in the low dimensional space is as close to the distribution in the high dimensional space as possible. This problem is essentially a composition optimization problem: min x t i p i t log p i t q i t, (2) where p i t exp( ‖ z t z i‖ 2 / 2σ 2 i) j 6 t exp( ‖ z t z j ‖ 2 /2σ 2 i), q i t exp( ‖ x t x i‖ 2) j 6 t exp( ‖ x t x j ‖ 2), lliu8101@uni.sydney.edu.au