Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
This work addresses the need for flexible mini-batching in machine learning optimization, particularly for non-convex scenarios, though it is incremental as it builds on existing dual-free methods.
The paper tackles the problem of regularized empirical risk minimization by developing a new algorithm that extends dual-free analysis techniques to arbitrary mini-batching schemes, enabling convergence for non-convex loss functions under convex average loss, with complexity results matching QUARTZ for convex losses.
In this work we develop a new algorithm for regularized empirical risk minimization. Our method extends recent techniques of Shalev-Shwartz [02/2015], which enable a dual-free analysis of SDCA, to arbitrary mini-batching schemes. Moreover, our method is able to better utilize the information in the data defining the ERM problem. For convex loss functions, our complexity results match those of QUARTZ, which is a primal-dual method also allowing for arbitrary mini-batching schemes. The advantage of a dual-free analysis comes from the fact that it guarantees convergence even for non-convex loss functions, as long as the average loss is convex. We illustrate through experiments the utility of being able to design arbitrary mini-batching schemes.