Exact Instance Compression for Convex Empirical Risk Minimization via Color Refinement
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912864276578304 |
|---|---|
| author | Zhu, Bryan Chen, Ziang |
| author_facet | Zhu, Bryan Chen, Ziang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_00437 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Instance Compression for Convex Empirical Risk Minimization via Color Refinement Zhu, Bryan Chen, Ziang Optimization and Control Machine Learning 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. |
| title | Exact Instance Compression for Convex Empirical Risk Minimization via Color Refinement |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2602.00437 |