Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees
Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we consider the intermediate case of optimization over the convex cone, parametrized as the conic hull of a generic atom set, leading to the first principled definitions of non-negative MP algorithms for which we give explicit convergence rates and demonstrate excellent empirical performance. In particular, we derive sublinear (O(1/t)) convergence on general smooth and convex objectives, and linear convergence (O(e −t )) on strongly convex objectives, in both cases for general sets of atoms. Furthermore, we establish a clear correspondence of our algorithms to known algorithms from the MP and FW literature. Our novel algorithms and analyses target general atom sets and general objective functions, and hence are directly applicable to a large variety of learning settings.
%%%% Summary
The authors consider constrained convex optimization problems where the constraints are conic and given by a bounded set of atoms. The authors propose linear oracle based method to tackle such problems in the spirit of Frank-Wolfe algorithm and Matching Pursuit techniques. The main algorithm is the Non-Negative Matching Pursuit and the authors propose several active set variants. The paper contains convergence analysis for all the algorithms under different scenarios. In a nutshel, the convergence rate is sublinear for general objectives and linear for strongly convex objectives. The linear rates involve a new geometric quantity, the cone width. Finally the authors illustrate the relevance of their algorithm on several machine learning tasks and different datasets.
%%%% Main comments
I did not have time to check the affine invariant algorithms and analyses presented in the appendix.
The papers contains interesting novel ideas and extensions for linear oracle based optimization methods but the technical presentation suffer some weaknesses:
- Theorem 2 which presentation is problematic and does not really provide any convergence guaranty.
- All the linear convergence rates rely on Theorem 8 which is burried at the end of the appendix and which proof is not clear enough.
- Lower bounds on the number of good steps of each algorithm which are not really proved since they rely on an argument of the type "it works the same as in another close setting".
The numerical experiments are numerous and convincing, but I think that the authors should provide empirical evidences showing that the computational cost are of the same order of magnitude compared competing methods for the experiments they carried out.
%%%% Details on the main comments
%% Theorem 2
The presention and statement of Theorem 2 (and all the sublinear rates given in the paper) has the following form:
- Given a fixed horizon T
- Consider rho, a bound on the iterates x_0 ... x_T
- Then for all t > 0 the suboptimality is of the order of c / t where c depends on rho.
First, the proof cannot hold for all t > 0 but only for 0 < t <= T. Indeed, in the proof, equation (16) relies on the fact that the rho bound holds for x_t which is only ensured for t <  = T.
Second the numerator actually contains rho^2. When T increases, rho could increase as well and the given bound does not even need to approach 0.
This presentation is problematic. One possible way to fix this would be to provide a priori conditions (such as coercivity) which ensure that the sequence of iterates remain in a compact set, allowing to define an upper bound independantly of the horizon T.
In the proof I did not understand the sentence "The reason being that f is convex, therefore, for t > 0 we have f (x t ) < = f (0)."
%% Lemma 7 and Theorem 8
I could not understand Lemma 7. 
The equation is given without any comment and I cannot understand its meaning without further explaination. Is this equation defining K'? Or is it the case that K' can be chosen to satisfy this equation? Does it have any other meaning?
Lemma 7 deals only with g-faces which are polytopes. Is it always the case? What happens if K is not a polytope? Can this be done without loss of generality? Is it just a typo?
Theorem 8:
The presentation is problematic. In Lemma 7, r is not a feasible direction. In Theorem 8, it is the gradient of f at x_t. Theorem 8 says "using the notation from Lemma 7". The proof of Theorem 8 says "if r is a feasible direction". All this makes the work of the reader very hard.
Notations of Lemma 7 are not properly used:
- What is e? e is not fixed by Lemma 7, it is just a variable defining a maximum. This is a recurent mistake in the proofs.
- What is K? K is supposed to be given in Lemma 7 but not in Theorem 8.
- Polytope?
All this could be more explicit.
"As x is not optimal by convexity we have that < r , e >  > 0". Where is it assumed that $x$ is not optimal? How does this translate in the proposed inequality?
What does the following mean?
"We then project r on the faces of cone(A) containing x until it is a feasible direction"
Do the author project on an intersection of faces or alternatively on each face or something else?
It would be more appropriate to say "the projection is a feasible direction" since r is fixed to be the gradient of f. It is very uncomfortable to have the value of r changing within the proof in an "algorithmic fashion" and makes it very hard to check accuracy of the arguments.
In any case, I suspect that the resulting r could be 0 in which case the next equation does not make sense. What prevents the resulting r from being null? 
In the next sentences, the authors use Lemma 7 which assumes that r is not a feasible direction. This is contradictory with the preceeding paragraph. At this point I was completely confused and lost hope to understand the details of this proof.
What is r' on line 723 and in the preceeding equation?
I understand that there is a kind of recursive process in the proof. Why should the last sentence be true?
%% Further comments
Line 220, max should be argmax
I did not really understand the non-negative matrix facotrization experiment. Since the resulting approximation is of rank 10, does it mean that the authors ran their algorithm for 10 steps only?