Introduction
Optimization problems involving submodular functions are ubiquitous in machine learning, appearing in tasks ranging from document summarization to sensor placement. While the Original Simplicial Method (OSM)—a variant of Kelley’s cutting-plane method—is a standard tool for these problems, it suffers from significant practical drawbacks: its memory requirements grow linearly with the number of iterations, and its convergence rate was previously unknown.
The Cutting-Plane Approach
Kelley’s method works by constructing a piecewise linear lower approximation of the objective function using "cutting planes" or supporting hyperplanes. In each iteration, a new constraint is added to refine this approximation.
As shown in Figure 1, the algorithm iteratively updates its estimate of the minimizer. However, in the original formulation (OSM), every single cutting plane generated is stored. This leads to "memory bloat," where the subproblems solved at each step become increasingly complex and computationally expensive.
Limited Memory Kelley’s Method (L-KM)
To address these inefficiencies, researchers from Cornell and Georgia Tech proposed the Limited Memory Kelley’s Method (L-KM). The key innovation is a pruning strategy: L-KM identifies and retains only the "active" constraints—those that define the current solution—and discards the rest.
The authors prove a remarkable theoretical bound: for an $n$-dimensional problem, one only needs at most $n+1$ constraints to maintain the necessary approximation. This keeps the memory footprint constant regardless of the number of iterations.
Duality and Linear Convergence
The paper’s core theoretical contribution lies in bridging the gap between Kelley’s methods and Frank-Wolfe algorithms. By introducing a dual algorithm called Limited Memory Fully-Corrective Frank-Wolfe (L-FCFW), the authors demonstrate that L-KM and L-FCFW are mathematically equivalent.
This duality allows the authors to prove the first linear convergence rate for this class of methods. Specifically, when the convex part of the objective is both smooth and strongly convex, the optimality gap decreases exponentially. Surprisingly, this analysis also reveals that the original OSM converges linearly, a property that was previously unproven.
Experimental Performance
The theoretical benefits of L-KM are reflected in computational studies. Comparing L-KM against OSM on composite convex and submodular objectives highlights the dramatic difference in resource usage.
As illustrated in Figure 2, L-KM successfully caps its memory usage (number of vertices) while maintaining the same convergence speed as the memory-intensive OSM. In higher dimensions, this translates to significant time savings per iteration, as the subproblems remain small and manageable.
Conclusion
By establishing a formal link between cutting-plane and Frank-Wolfe methods, this work provides a robust framework for efficient submodular optimization. L-KM offers a practical, memory-efficient alternative to traditional methods without sacrificing convergence speed, paving the way for more scalable machine learning applications.
Summary updated