{
  "id": "2402.07070",
  "version": "v2",
  "published": "2024-02-11T00:02:36.000Z",
  "updated": "2024-06-09T17:09:17.000Z",
  "title": "Efficient Algorithms for Sum-of-Minimum Optimization",
  "authors": [
    "Lisang Ding",
    "Ziang Chen",
    "Xinshang Wang",
    "Wotao Yin"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2024-06-09T17:09:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "efficient algorithms",
      "lloyds algorithm",
      "initialization algorithm",
      "framework encompasses numerous clustering applications",
      "generalized principal component analysis"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}