Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the geometric structure in composite minimization by making gradients small. More specifically, the author identifies parallel and collinear geometric structures. The novelty of this paper is the analysis of parallel structure and its extension to new variants of accelerated methods. It is indeed important to study the geometric structures for convergence rates of gradients for convex problems and the Lyapunov analysis is a standard way to analyze the convergence rates.  
main_review: This paper provides a comprehensive and elegant analysis in terms of providing geometric insights for accelerated methods. Basically, I think this paper is a wonderful work. The only two comments I have is : 1. It would be nice to have some theoretical insights for geometric structures under non-convex settings as citation[2] did. 2. It is encouraged to use more real dataset instead of generated ones to support the theoretical results in this paper. 

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper discovers parallel and co-linear structures in known accelerated first order methods and claims that these are important ingredients to achieve acceleration. The introduction of parallel structure in an optimization algorithm yields a standard way of designing a discrete Lyapunov function to analyze its convergence. A new Lyapunov analysis for OGM-G is obtained, but also a new method FISTA-G, which, combined with FISTA, yields to an improvement in the state of the art regarding convergence of gradient in the proximal gradient setting. An experiment in compressed sensing is presented as well.
main_review: The mechanism behind acceleration is a vastly studied problem in optimization community and I think that any contribution to that is of interest for neurips. The paper finds common characteristics of popular accelerated algorithms. More specifically, these algorithms can be written as a primary and secondary sequence of iterates that satisfy parallel properties in the convex case and co-linear properties in the strongly convex case. What I like here is that the co-linear structure "converges" in some sense to the parallel one when the strong convexity constant goes to $0$.

The authors believe that these can serve as unified characteristics of all accelerated methods and a first remarkable result is that changing slightly the auxiliary sequence of iterates in OGM-G, can yield to a novel Lyapunov analysis of convergence. However, the OGM-G presented in the paper is the same as the original one? The auxiliary iterates participate also in the definition of the primary ones...

After a modification in FISTA to make the auxiliary iterates parallel, the new method FISTA-G combined with FISTA yields $O(1/K^4)$ iteration complexity for gradient convergence. This is better than the sate of the art which is $O(1/K^3)$. Excuse my ignorance here but why FISTA+FISTA-G yields better result than FISTA-G running for all $2K$ iterates? Can you give some intuition? Also, what is the difficulty to establish iteration complexity of the new method for the suboptimality of function values?

Similar things happening for methods for accelerated strongly convex optimization where the auxiliary iterates are endowed with the co-linear structure. In 228 it is claimed that the new methods improve over the original ones, can you explain exactly how? It is not obvious to me.

The paper is in general well-written and explains in detail subtle differences among a very large literature in accelerated methods. However, the figures are not very enlightening to me and I find a bit weird the use of arrows above vectors.

Limitations of the work are discussed at the end, noting that the presented algorithms are not anytime algorithms, but this is also a limitation of the original methods that upon them the paper improves. 

Overall, I find the content of the paper a bit out of the ordinary, but since the presented observations can yield to better convergence result even in the special case of prox-grad, I think that this is a good contribution and vote for acceptance. However, I was not able to check the math in detail in the given time which means that my evaluation is not confident. The only concern that i have is that maybe this paper is not such a good fit for neurips due to its highly technical nature (40 pages, mostly math). Probably an optimization journal would be a better fit for proper reviewing.






limitations_and_societal_impact: The authors discuss limitations of the work and there is no negative societal impact.
review_title: null

final_score: rating: 2: Strong rejection
review_content: summary: This paper tries to propose a new algorithm to obtain faster rate O(1/k^4) for convex objective function. The bound is OK on the surface, actually does not make sense.
main_review: The main algorithm (FISTA-G) between the line 114 and the line 115 does not work practically. The key coefficient psi_k needs the afterword coefficient psi_{k+1} and psi_{k+2}. Moreover, for every specific iteration number K, it needs a special coefficients, psi_{0}, ..., psi_{K+2}. In other words, for different K, these settings are not an algorithm but a series of algorithms, and every algorithm only efficient for a specific K. Essentially, it is not an algorithm and then obtains a bound O(1/K^4) for it. I believe this paper only hopes to use some tricks to obtain a desired bound and does not design an efficient algorithm.
limitations_and_societal_impact: I hope the authors could consider a real algorithms in practice, not only give a bound and a superficial proof.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Two main contributions of this paper include (i) proposing a geometric structure that is satisfied by many first-order accelerated methods and (ii) proposing algorithms with the rate $O(1/K^4)$ for the squared gradient norm.
main_review: 1. The parallel structure and the collinear structure are quite interesting. 
2. The way of determining the extrapolation parameters $\theta_k$ is strange:$ \theta_K =1$, $\theta_k$ is defined depending on $\theta_{k+1}$. Does it mean we must save all the values of the sequence $\theta_k$ in advance before running the algorithm?  
3. $U_k$ is a sequence, it is not a Lyapunov function. The authors may want to call it an auxiliary sequence. 
4. Although the obtained rate is optimal, it is not clear how to choose K to obtain an $\varepsilon$-optimal solution. This is important because K is chosen in advance for the proposed algorithms. 


limitations_and_societal_impact: N.A.
review_title: null

Meta-review: The paper provides new geometric insights into acceleration under the Euclidean squared norm based on parallelism and collinearity of query and auxiliary points. The reviewers and area chair found the conceptual value of this contribution somewhat hard to evaluate, possibly because it only covers the Euclidean case and does not fully motivate the choice of Lyapunov function. However, the value of the contribution is reinforced by the fact that the authors use it to provide the best known bounds for making gradient small in the prox-grad setting and to derive a number of alternative algorithms for making gradient small. This improvement testifies to the novelty and usefulness of the techniques in the paper.
Decision: Accept (Poster)