Stochastically Controlled Compositional Gradient for Composition Problems.

Area of Science:

• Machine Learning
• Optimization Algorithms

Background:

• Composition problems are crucial in machine learning, but computing inner functions and gradients is computationally expensive.
• Existing gradient descent methods struggle with large datasets (large m and n).

Purpose of the Study:

• To develop a computationally efficient algorithm for solving compositional problems.
• To address the convergence challenges in stochastic compositional gradient methods.

Main Methods:

• Devised a stochastically controlled compositional gradient algorithm.
• Introduced two variants of stochastically controlled techniques to estimate the inner function G(x) and the objective function's gradient.
• Presented a general convergence analysis with specific subset size proofs: |D1|=min{1/ϵ,m} and |D2|=min{1/ϵ,n}.

Main Results:

• Significantly reduced computational cost for estimating G(x) and gradients.
• Achieved improved convergence guarantees, especially under low target accuracy (1/ϵ << m or n).
• Demonstrated superior performance compared to existing methods through comprehensive experiments in both strongly convex and nonconvex settings.

Conclusions:

• The proposed stochastically controlled compositional gradient algorithm offers substantial computational advantages.
• The method provides robust convergence guarantees for a wide range of machine learning problems.
• This work advances the efficiency and theoretical understanding of optimization for compositional models.