# Exact Instance Compression for Convex Empirical Risk Minimization via Color Refinement

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 15 references that are in the map.
- First posted on arXiv 31 Jan 2026.

## Builds on (most cited first, 7 of 7)

- [Equivariance Through Parameter-Sharing](https://mlsanity.com/paper/1702.08389/) (2017)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [OpenML-Python: an extensible Python API for OpenML](https://mlsanity.com/paper/1911.02490/) (2019)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement](https://mlsanity.com/paper/1509.08251/) (2015)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [Dimension Reduction via Colour Refinement](https://mlsanity.com/paper/1307.5697/) (2013)

## Abstract (arXiv)

Empirical risk minimization (ERM) can be computationally expensive, with standard solvers scaling poorly even in the convex setting. We propose a novel lossless compression framework for convex ERM based on color refinement, extending prior work from linear programs and convex quadratic programs to a broad class of differentiable convex optimization problems. We develop concrete algorithms for a range of models, including linear and polynomial regression, binary and multiclass logistic regression, regression with elastic-net regularization, and kernel methods such as kernel ridge regression and kernel logistic regression. Numerical experiments on representative datasets demonstrate the effectiveness of the proposed approach.