# Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses

arXiv: https://arxiv.org/abs/1506.02227 · HTML: https://mlsanity.com/paper/1506.02227/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2015.

## Built on by (most cited first, 2 of 2)

- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Better Methods and Theory for Federated Learning: Compression, Client Selection and Heterogeneity](https://mlsanity.com/paper/2207.00392/) (2022)

## Abstract (arXiv)

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.