Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives

Song Ping Zhou, Swati Gupta, Madeleine Udell

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.

Figure 1: The iterative process of Kelley's method, showing how the lower approximation $g + f_{(k)}$ is refined at each step to find the minimizer $x^{(k)}$.

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.

Figure 2: Performance comparison between L-KM and OSM. The left panels show that L-KM maintains a small, bounded number of vertices (memory), while OSM's memory grows linearly. The right panels demonstrate that both methods achieve similar linear convergence.

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

Abstract

The original simplicial method (OSM), a variant of the classic Kelley's cutting plane method, has been shown to converge to the minimizer of a composite convex and submodular objective, though no rate of convergence for this method was known. Moreover, OSM is required to solve subproblems in each iteration whose size grows linearly in the number of iterations. We propose a limited memory version of Kelley's method (L-KM) and os OSM that requires limited memory (at most n + 1 constraints for an n-dimensional problem) independent of the iteration. We prove convergence for L-KM when the convex part of the objective (g) is strongly convex and show it converges linearly when g is also smooth. Our analysis relies on duality between minimization of the composite objective and minimization of a convex function over the corresponding submodular base polytope. We introduce a limited memory version, L-FCFW, of the Fully-Corrective Frank-Wolfe (FCFW) method with approximate correction, to solve the dual problem. We show that L-FCFW and L-KM are dual algorithms that produce the same sequence of iterates; hence both converge linearly (when g is smooth and strongly convex) and with limited memory. We propose L-KM to minimize composite convex and submodular objectives; however, our results on L-FCFW hold for general polytopes and may be of independent interest.
BibTeX
@inproceedings{zhou2018limited,
  author = {Song Ping Zhou and Swati Gupta and Madeleine Udell},
  title = {{Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=r1bdTPZOZS},
}
Figure