Variance Reduced Methods for Non-Convex Composition Optimization.

Area of Science:

• Optimization Theory
• Machine Learning
• Applied Mathematics

Background:

• Non-convex composite optimization problems with finite-sum structures are prevalent in machine learning, particularly in nonlinear embedding and reinforcement learning.
• Existing methods like Stochastic Gradient Descent (SGD) and Stochastic Variance Reduced Gradient (SVRG) exhibit high query complexities, especially with numerous inner component functions.

Purpose of the Study:

• To develop novel algorithms that improve query complexity for non-convex composite optimization.
• To analyze the performance of these algorithms concerning the number of inner and outer component functions.
• To extend the algorithms for mini-batch scenarios to further enhance efficiency.

Main Methods:

• Devised Stochastic Composition via Variance Reduction (SCVR) algorithm.
• Developed SCVRII algorithm, considering different inner component function estimations.
• Proposed a mini-batch extension for enhanced query complexity.

Main Results:

• SCVR and SCVRII demonstrate improved query complexities compared to existing methods.
• Analysis provides insights into complexity variations based on the number of inner and outer functions.
• Mini-batch extension offers further query complexity improvements at optimal batch sizes.

Conclusions:

• The proposed SCVR and SCVRII algorithms offer significant improvements in query complexity for non-convex composite optimization.
• The theoretical analyses and experimental results validate the effectiveness of the developed methods.
• These algorithms provide efficient solutions for large-scale machine learning applications like nonlinear embedding and reinforcement learning.