# Efficient Algorithms for Sum-of-Minimum Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2024.

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

- [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025)
- [Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization](https://mlsanity.com/paper/2405.19650/) (2024)
- [Covering Multiple Objectives with a Small Set of Solutions Using Bayesian Optimization](https://mlsanity.com/paper/2501.19342/) (2025)
- [Quality-Diversity Optimization as Multi-Objective Optimization](https://mlsanity.com/paper/2602.00478/) (2026)

## Abstract (arXiv)

In this work, we propose a novel optimization model termed "sum-of-minimum" optimization. This model seeks to minimize the sum or average of N objective functions over k parameters, where each objective takes the minimum value of a predefined sub-function with respect to the k parameters. This universal framework encompasses numerous clustering applications in machine learning and related fields. We develop efficient algorithms for solving sum-of-minimum optimization problems, inspired by a randomized initialization algorithm for the classic k-means (Arthur & Vassilvitskii, 2007) and Lloyd's algorithm (Lloyd, 1982). We establish a new tight bound for the generalized initialization algorithm and prove a gradient-descent-like convergence rate for generalized Lloyd's algorithm. The efficiency of our algorithms is numerically examined on multiple tasks, including generalized principal component analysis, mixed linear regression, and small-scale neural network training. Our approach compares favorably to previous ones based on simpler-but-less-precise optimization reformulations.