Stochastically Controlled Compositional Gradient for Composition Problems

We consider composition problems of the form (1/n)Σ i=1n Fi (1/m)Σj=1m Gj(x), which are important for machine learning. Although gradient descent and stochastic gradient descent are straightforward solutions, the essential computation of G (x)= (1/m)Σj=1m Gj(x) in each single iteration is expensive, let alone for large m. In this article, we devise a stochastically controlled compositional gradient algorithm. Specifically, we introduce two variants of stochastically controlled technique to estimate the inner function G(x) and the gradient of the objective function, respectively. The computational cost is largely reduced. However, the natural needs of two stochastic subsets {D1 and D2 form direct barriers to guarantee the convergence of the algorithm, especially the theoretical proof of the convergence. To this end, we present a general convergence analysis by proving |D1| = min {1/ψ, m} and |D2| = min {1/ϵ, n}, through which the proposed method significantly improve composition algorithms under low target accuracy (i.e., 1/ϵ ≪ m or n) in both strongly convex and nonconvex settings. Comprehensive experiments demonstrate the superiority of the proposed method over existing methods.