Stochastically Controlled Compositional Gradient for Composition Problems

doi:10.1109/TNNLS.2021.3098222

2023-02-01

PRE

DOI：10.1109/TNNLS.2021.3098222

原文链接

原文求助

摘要

En 中文

We consider composition problems of the form ${1}/{n} n-ary sumation _{i= 1}<^>n F_i{1}/{m} n-ary sumation _{j = 1}<^>m G_j(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} n-ary sumation _{j = 1}<^>{m}{G_j( 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 ${ D}_{1}$ and ${ D}_{2}$ 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 $|{D}_{1}|=min{1/epsilon,m}$ and $|{D}_{2}|=min{1/epsilon,n }$ , through which the proposed method significantly improve composition algorithms under low target accuracy (i.e., 1/epsilon MUCH LESS-THAN m or n) in both strongly convex and nonconvex settings. Comprehensive experiments demonstrate the superiority of the proposed method over existing methods.

Keyword:

Complexity theory

Convergence

Optimization

Jacobian matrices

Convex functions

Linear programming

Learning systems

Composition problem

stochastic optimization

stochastically controlled gradient

variance reduction