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

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 (g) and submodular (f) objectives g+f, 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 of 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 (g) of the objective is strongly convex and show it converges linearly when it is also smooth. Our analysis relies on duality between minimization of the composite objectives and the minimization of a convex function over the submodular base polytope. We introduce a limited memory version, L-FCFW, of the Fully-Corrective Frank-Wolfe 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. Our results on L-FCFW hold for general polytopes and may be of independent interest.