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 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 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 FrankWolfe (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.
Summary: ------- The paper proposes a simple modification of the Original Simplicial Method that keeps in memory only the active linear constraints. Then by linking the dual method to Fully corrective Frank Wolfe they get convergence rates.  Quality & Clarity: ------------------ The paper is well written and motivated for people in the field. Note that it is probably quite abstruse otherwise. Its place in the literature is well defined. Proofs are correct.  The final rates (Theorem 2 and 3) are quickly stated: what is the total cost of the algorithm, taking into account the computations of the subproblems ? (by taking a concrete example where the subproblems can be computed efficiently) This would enlighten the impact in this rate of the limited memory implementation in comparison to the original simplicial method.  In Theorem 3, first, \Delta^{(i+1)} should be \Delta^{(i)}. Then these results only state that the estimated gap is bounded by the true gap, I don't get the sub-linear rate from reading these equations.  Originality & Significance: --------------------------- The paper introduces two simple, though efficient, ideas to develop and analyze an alternative of the simplicial method (looking only at the active linear constraints of each subproblem and drawing convergence rates from the Frank-Wolfe literature). Relating the dual of the simplicial method to Franck-Wolfe method was already done by Bach [2]. I think that the present paper is therefore only incremental. Moreover the authors do not give compelling applications (this is due to the restricted application of the original simplicial method). In particular, they do not give concrete examples where the subproblems can easily be computed, that would help to understand the practical impact of the method.   Minor comments: --------------- - l139: no parenthesis around w - l140: put footnote for closed function here - l 227: Replace "Moreover" by "Therefore" - l 378: must be strictly contained *in* - As stated from the beginning, OSM is not Kelley's method, so why is the algorithm called Limited memory Kelley's method and Limited memory simplicial method ? This confusion might weaken its referencing in the literature, I think.   -------------------------------------- Answer to author's feedback -------------------------------------- Thank you for your detailed feedback. I revised my "incremental" comment. The problem was clearly asked before and the answer you provided is simple, clear and interesting.