Efficient Algorithms for Sum-of-Minimum Optimization

In this work, we propose a novel optimization model termed ``sum-of-minimum" optimization. This model computes the sum (or average) of N values where each is the minimum of the k results of applying a distinct objective function to the same set of k variables, and the model seeks to minimize this sum (or average) over those k variables. When the N functions are distance measures, we recover the k-means clustering problem by treating the k variables as k cluster centroids and the sum as the total distance of the input points to their nearest centroids. Therefore, the sum-of-minimum model embodies a clustering functionality with more general measurements instead of just distances. We develop efficient algorithms for sum-of-minimum optimization by generalizing a randomized initialization algorithm for 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 the 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 that are based on simpler but less precise optimization reformulations.