A Hybrid Stochastic-Deterministic Minibatch Proximal Gradient Method for Efficient Optimization and Generalization.

Area of Science:

• Optimization
• Machine Learning
• Computational Complexity

Background:

• Stochastic variance-reduced gradient (SVRG) algorithms are successful for large-scale problems but suffer from linear scaling in stochastic gradient complexity with data size.
• This complexity becomes computationally expensive for very large datasets, hindering scalability.

Purpose of the Study:

• To develop a novel algorithm, Hybrid Stochastic-Deterministic Minibatch Proximal Gradient (HSDMPG), that overcomes the data-size dependency of existing methods.
• To achieve improved computational complexity for strongly convex problems with linear prediction structures, such as least squares and logistic/softmax regression.

Main Methods:

• The HSDMPG algorithm iteratively samples an evolving minibatch of individual losses to approximate the original problem.
• It efficiently minimizes these smaller, sampled subproblems, leading to data-size-independent complexity for large-scale scenarios.

Main Results:

• HSDMPG achieves an ϵ-optimization error within O(κ/ϵ) stochastic gradient evaluations for strongly convex loss with n components (ζ=1 for quadratic, ζ=2 for generic loss).
• For large-scale problems, HSDMPG's complexity outperforms SVRG-type algorithms.
• Crucially, for ϵ = O(1/√n), HSDMPG achieves optimal generalization in less than a single data pass, with complexities of O(n^0.5 log^2(n)) for quadratic and O(n^0.5 log^3(n)) for generic losses.

Conclusions:

• HSDMPG offers significant computational advantages over existing methods for large-scale optimization problems.
• The algorithm's ability to achieve optimal generalization in under one pass represents a breakthrough in efficient machine learning.
• Extensions to online strongly convex problems also demonstrate HSDMPG's superior efficiency.