Linear-Memory and Decomposition-Invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes
Recently, several works have shown that natural modifications of the classical conditional gradient method (aka Frank-Wolfe algorithm) for constrained convex optimization, provably converge with a linear rate when: i) the feasible set is a polytope, and ii) the objective is smooth and strongly-convex. However, all of these results suffer from two significant shortcomings:
1. large memory requirement due to the need to store an explicit convex decomposition of the current iterate, and as a consequence, large running-time overhead per iteration 2. the worst case convergence rate depends unfavorably on the dimension In this work we present a new conditional gradient variant and a corresponding analysis that improves on both of the above shortcomings. In particular:
1. both memory and computation overheads are only linear in the dimension 2. in case the optimal solution is sparse, the new convergence rate replaces a factor which is at least linear in the dimension in previous work, with a linear dependence on the number of non-zeros in the optimal solution At the heart of our method and corresponding analysis, is a novel way to compute decomposition-invariant away-steps. While our theoretical guarantees do not apply to any polytope, they apply to several important structured polytopes that capture central concepts such as paths in graphs, perfect matchings in bipartite graphs, marginal distributions that arise in structured prediction tasks, and more. Our theoretical findings are complemented by empirical evidence which shows that our method delivers state-of-the-art performance.
In this paper, the authors provide a new conditional-gradient-type method for minimization of a smooth strongly convex function over a special class of polytopes. The proposed method is less memory consuming and have cheaper iteration than the state-of-the-art methods. Convergence rate of the method is provided and numerical comparison with existing methods is also presented.
Initial review.  Technical quality: 1. Line 138: Actually, this statement holds for large n. 2. In my opinion, the arguments about the drawbacks of the existing methods in the end of Section 3.1 are not so strong. Existing methods can have superlinear memory and running-time overheads in general case. But in the considered in this paper case of structured polytopes, it may not hold. For example, in the case of the standard simplex, the step 5 in Algorithm 2 costs $O(n)$ operations. The same holds for the memory consumption. It seems that one can criticize the decomposition-specific performance argument in the same way. 3. It is not clear how one can use logarithmic-scale search to estimate $M_1/sqrt{M_2}$. 4. It is not clear why, for the numerical experiments, the authors choose the "line-search" version of their algorithm, despite that it doesn't have a proved convergence theorem. 5. It is not clear, why the authors do not compare their method with the method of [6]. It seems that the latter can be efficient on the considered class of structured polytopes.  Novelty/originality: To the best of my knowledge, the method and its analysis are new.  Potential impact or usefulness: 1. A more detailed description of "applications in machine learning, signal processing and other domains" would increase the potential impact of the paper. 2. Potential drawback of the method could be that one needs an information about $card(x^*)$ in order to implement method with provable convergence rate. 3. It seems that the line-search option in Algorithm 3 could be quite hard to implement in practice.  Clarity and presentation: 1. It was quite hard for me to clarify, what is meant by minimization of a linear form which is given by a vector with infinite-valued components. My first guess was that if you minimize such a linear form given by a vector $(\infty, 1)^T$, it is the same as minimization of a linear form given by a vector $(1, 0)^T$. The reason is that you can neglect 1 in comparison with $\infty$.  2. The text should be proof readed. Here are some examples of misprints. Line 54: "a the convex" should be "as the convex" Line 92: "shaper" should be "sharper" Step 6 of Algorithm 3: $R^m$ should be $R^n$   ===================================== Update after author feedback  Technical quality: 1. This comment remains the same.  2. As it is done now, in the end of Section 3.1, it seems a bit unfair to criticize the existing methods and their performance for _general_ polytopes, and, then, propose a method for a _narrow_ class of polytopes. In that sense, the authors provide in their rebuttal a reasonable argument "However for more complex polytopes ..."  It should be included in the text.  At the same time, the authors write in the rebuttal "This difference in memory requirement is well demonstrated in our OCR experiment, showing significant savings for our method." But, in the text, they report only memory consumption of ACG and PCG, but not the memory consumption of their method. 3. After clarification in the authors' feedback, I still have some doubts concerning the logarithmic-scale search for estimation of $M_1/sqrt{M_2}$. As far as I understood from the text, it will work if we estimate M_1/sqrt{M_2} by some M \in [0.5 M_1/sqrt{M_2}, M_1/sqrt{M_2}]. This interval does not seem to be very wide. 4. In the rebuttal, the arguments on choice of "line-search" version for experiments seem to be reasonable and it should be added to the text. 5. After clarification in the authors' feedback, this point is still not clear for me. It could be fair to compare the proposed provable algorithm with [6], since both of them do not use line search.  Novelty/originality: No change in my opinion.  Potential impact or usefulness: 1. This comment remains the same.  2. In their rebuttal, the authors write that there is no need to know $card(x^*)$. I agree with their explanation. Nevertheless, as I think, potential drawback of the method could be that one needs a good approximation for M_1/sqrt{M_2} (i.e. some M \in [0.5 M_1/sqrt{M_2}, M_1/sqrt{M_2}]) in order to implement method with provable convergence rate. 3. I think the remark in authors' feedback "In general, one can apply the line-search to the upper-bound given by Definition 2, which is always easy to compute." should be added to the text with some explanations on why minimizing the upper-bound will work. 4. New item. I think, the description of logarithmic-scale search for estimation of $M_1/sqrt{M_2}$ should be added to the text.  Clarity and presentation: 1. I think, the authors can easily clarify this point in the text and should do it. 2. This comment remains the same.