Research map / Optimization / Nonconvex and smooth optimization
Efficient Algorithms for Sum-Of-Minimum Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes the sum-of-minimum optimization model with a generalized k-means++ initialization and generalized Lloyd's algorithm, proving tight O(L^2/mu^2 ln k) initialization bounds and O(1/T) convergence, and showing gains on GPCA, mixed linear regression, and small neural network training.
Problem
Minimizing the average of N sub-objectives each taking the minimum over k parameter choices (a clustering-type nonconvex problem), which generalizes k-means, mixed linear regression, and GPCA; existing methods use smooth but less precise product reformulations.
Approach
Generalize k-means++ seeding (sampling indices by optimality gap to current centers) and Lloyd's algorithm (reclassify then gradient step per group) directly to the sum-of-minimum objective, avoiding the product reformulation, with tight approximation bounds under L-smooth, mu-strongly convex sub-functions.
Key results
- On GPCA with k=2, d=4, the sum-of-minimum model reaches 98.24% cluster accuracy versus 81.88% for the sum-of-product formulation after 50 iterations.
- The proposed initialization reduces failure rate and average iterations in mixed linear regression for k=4 (e.g., failure 0.050 vs 0.056 random at d=4, iterations 14.55 vs 17.58).
- For mixed nonlinear regression (d_I,d_H)=(5,3), the proposed seeding needs 181.4 epochs versus 329.4 for random initialization to reach ground-truth training loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the sum-of-minimum formulation and proposed GPCA algorithm instead of the sum-of-product formulation with BCD | GPCA · GPCA, k=2, d=4, 50 iterations | cluster accuracy (%): 81.88 -> 98.24 | Helped |
| Use the sum-of-minimum formulation and proposed GPCA algorithm instead of the sum-of-product formulation with BCD | GPCA · GPCA, k=3, d=5, 50 iterations | cluster accuracy (%): 62.89 -> 94.98 | Helped |
| Use the sum-of-minimum formulation and proposed GPCA algorithm instead of the sum-of-product formulation with BCD | GPCA · GPCA, k=4, d=6, 50 iterations | cluster accuracy (%): 57.89 -> 93.73 | Helped |
| Use the sum-of-minimum formulation and proposed GPCA algorithm instead of the sum-of-product formulation with BCD | GPCA · GPCA, k=2, d=4, 10 iterations | CPU time (seconds): 0.14 -> 0.08 | Helped |
| Use proposed initialization instead of random initialization | Lloyd's algorithm for mixed linear regression · Mixed linear regression, k=4, d=4 | failure rate: 0.056 -> 0.050 | Helped |
| Use proposed initialization instead of random initialization | Lloyd's algorithm for mixed linear regression · Mixed linear regression, k=5, d=4 | failure rate: 0.161 -> 0.162 | Hurt |
| Use proposed initialization instead of uniform seeding | Lloyd's algorithm for mixed linear regression · Mixed linear regression, k=5, d=4 | failure rate: 0.145 -> 0.162 | Hurt |
| Use proposed initialization instead of uniform seeding | Lloyd's algorithm for mixed linear regression · Mixed linear regression, k=6, d=8 | failure rate: 0.596 -> 0.563 | Helped |
| Use proposed initialization instead of random initialization | Lloyd's algorithm for mixed linear regression · Mixed linear regression, k=6, d=8 | average iterations: 48.730 -> 40.320 | Helped |
| Use proposed initialization instead of random initialization | Lloyd's algorithm for mixed nonlinear regression · Mixed nonlinear regression, (d_I,d_H)=(5,3) | average epochs to ground-truth training loss: 329.4 -> 181.4 | Helped |
| Use proposed initialization instead of uniform seeding | Lloyd's algorithm for mixed nonlinear regression · Mixed nonlinear regression, (d_I,d_H)=(7,5) | average epochs to ground-truth training loss: 71.2 -> 49.3 | Helped |
| Use proposed initialization instead of random initialization | Lloyd's algorithm for mixed nonlinear regression · Mixed nonlinear regression, (d_I,d_H)=(5,3), 300 epochs | testing loss (10e-3): 4.63 -> 3.93 | Helped |
Limitations
- Theory assumes L-smooth, mu-strongly convex sub-functions; non-convex case left open.
- Experiments are small-scale synthetic tasks only.
- Exact optimal scores require f_i^*, which may be costly; approximations add error terms.
Experimental setup
Datasets: synthetic GPCA data synthetic mixed linear regression data synthetic mixed nonlinear regression data
Benchmarks: synthetic GPCA synthetic mixed linear regression synthetic mixed nonlinear regression
Metrics: cluster accuracy CPU time failing rate average iterations training loss testing loss
Baselines: sum-of-product GPCA formulation with block coordinate descent random initialization uniform seeding initialization
Builds on: k-means++ Lloyd's algorithm Adam
Closest papers by meaning
- A Scalable Deterministic Global Optimization Algorithm for Clustering Problems (ICML 2021 · similarity 0.86)
- Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.85)
- Accelerating data-driven algorithm selection for combinatorial partitioning problems (NeurIPS 2025 · similarity 0.85)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.84)
- Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features (ICML 2024 · similarity 0.84)
- Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.