Timezone: »

 
Poster
Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives
Song Zhou · Swati Gupta · Madeleine Udell

Thu Dec 06 02:00 PM -- 04:00 PM (PST) @ Room 210 #16
in Thu Poster Session B »

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 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 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 convex and submodular objective and minimization of a convex function over the 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.

Keywords: Convex Optimization · Submodular Optimization
[ Paper] 

Author Information

Song Zhou (Cornell University)
Swati Gupta (Georgia Institute of Technology)
Madeleine Udell (Cornell University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors