Optimizing Finite Sum Objectives in Machine Learning with an Extra-Gradient Approach

Abstract

This paper present a extra-gradient optimization method tailored for minimizing unconstrained objective functions expressed as finite sums, particularly in large-scale machine learning tasks. The proposed algorithm employs an adaptive line search strategy combined with a variable sample size mechanism to achieve an optimal balance between computational efficiency and solution accuracy [2]. Unlike traditional monotone methods, our approach leverages a dynamic, non-monotone step size , treated as a random variable determined by the sample data, enhancing its adaptability to noisy and complex environments. The proposed method allows error control through additional sampling. For alternatives and more specific conditions, detailed comments are provided in [3]. One of the promising approaches in this direction of research, but without the use of an extra-gradient step, is presented in [1]. It is implemented within a line-search framework and plays a role in deciding whether to switch from line-search to a predefined step size sequence. The method excels in scenarios involving massive datasets, such as logistic regression, support vector machines, where conventional methods struggle with computational overhead. Comparative analysis highlights its superiority over established techniques, such as SAGA [4] and Adam [5], by demonstrating reduced computational costs and faster convergence rates in practical experiments. Rigorous testing across diverse machine learning benchmarks validates the robustness and efficiency of our approach, showcasing its capability to handle data-intensive and non-convex optimization problems with significant resource savings.