Time-Reversed Dissipation Induces Duality Between Minimizing Gradient Norm and Function Value

Summary

This paper introduces novel notion of H-duality, which shows unexpected connection between time-reversed coefficients of methods and optimality w.r.t. gradient norm or function value.

Strengths

Very inspiring work, introduced notion is quite curious. I think that such an idea will be interesting to most of readers. The contribution of this paper is primarily theoretical which could make it "intermediate" for those readers who work in practical field of ML, but I believe that introduced notions can help theorists to develop the theory of optimisation taking into account more important details, which will impact on practice in the end. Especially such abstract works can affect theory the most, if the introduced notion is really helpful and fundamental, which can be confirmed only by the time, but I see it necessary to present such ideas to community to "test" them. Idea seems to be novel: my experience doesn't tell me attempts to introduced such a parallels in methods constructions in terms of duality notion.

Weaknesses

I do not see significant weaknesses. Proof presented in the paper are correct, but assumption are expressful enough to make proofs simple in cases where they are satisfied. In the best case, more detailed development of these concepts should lead to simplification and weakening of assumptions by showing from when do they arise in many cases.

Questions

Notion is based on phrases like "efficiently reduce function values/gradient magnitude", which is not very clear in part "efficiently". Any method which optimises function value optimises gradient norm as well for convex functions, so word "efficiently" requires formalisation. I guess, it is connected with optimality w.r.t. different measures of convergence. If it's possible to develop it better, it would be good.

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Everything is okay

Summary

This work defines H-duality, which is a one-to-one correspondence between methods that minimize function values and methods that minimize gradient magnitudes, under the assumption that the objective function is convex and $L$-smooth. It is proved in both discrete and continuous time dynamics that, when one method satisfies a convergence condition, the convergence of its H-duality correspondence can also be guaranteed. Furthermore, a new class of methods is derived by applying H-duality to a known class of FSFOMs, and the H-duality convergence theorem can be used to establish the convergence of the new methods.

Strengths

1. To the best of my knowledge, the concept of H-duality proposed in this work is novel, and the theorems which establish the equivalence between convergence conditions of two algorithms and their H-duality are also novel. 2. This work demonstrates that the proposed H-duality can be useful, by using it to establish a symmetry property between pairs of methods, to prove the convergence of them, and to derive new methods. 3. The paper is in general well written, and the sketch of proof helps readers more easily understand the techniques in the proof.

Weaknesses

1. It should be noted that this work only applies to $L$-smooth and convex objective functions, and the value of $L$ is required be known as a prior, since it is used in the methods. 2. If I understand correctly, the number of iterations $N$ is fixed in advance, which could also limit the applicability of this work. (details in question 1)

Questions

1. In practice a method is usually terminated when a certain stopping criterion is reached, and the total number of iterations $N$ is often not known or fixed in advance. However, in this work, $N$ is required to be known and fixed. Could the authors please discuss about this difference? How would it affect the applicability of the conclusions in this work? 2. In section 2.3, it is not obvious to me why $U \geq 0$ is equivalent to (C1), because there is an additional term $- \frac{L}{2} \|\|x_\star -x_0 + \frac{1}{L} \sum_{i=0}^N (u_i - u_{i-1}) \nabla f(x_i) \|\|^2$, which is not in (C1). Could the authors please explain in a high level how to bridge this gap?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

As far as I can see, there is no potential negative societal impact of this work.

Summary

This paper studies the duality for optimization algorithms. As claimed by the authors, the notion they present is distinct form any previously known duality or symmetry relations. In this work, the authors present a one-to-one correspondence between methods efficiently minimizing function values and methods efficiently minimizing gradient magnitude, which is called H-duality. Using H-duality, a clearer understanding of the symmetry between FGM/OGM and OGM-G and a new class of methods efficiently reducing gradient magnitudes can be obtained. The authors claim that their new composite minimization method achieve better results than state-of-the-art methods in efficiently reducing gradient magnitude in the composite minimization setup.

Strengths

1. This paper presents a novel notion of duality. 2. The theory of H-duality seems to be sound.

Weaknesses

1. The relevance to NeurIPS is a concern. Actually, this paper studies the duality for optimization algorithms, which is an important problem in Optimization and Control. I am not sure whether NeurIPS is the right place. 2. In the Section 4 “New method efficiently reducing gradient mapping norm: (SFG)”, the authors claim that their method (SFG) is faster than FISTA-G by a constant factor of 5.28 while having substantially simpler coefficients. In the paper which presented FISTA-G, two graph were given to describe different methods’ effectiveness on reducing the gradient magnitude. But the result of experiments can’t be found in the paper, which make the comparison between SFG and FISTA-G is lack of persuasiveness. Could you add the result of experiments to describe the comparison between SFG and FISTA-G?

Questions

Please see my question in the "Weakness" section.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Not applicable.

Summary

This paper shows an intriguing symmetry in convex optimization between first-order methods that efficiently minimizes the function value and those that efficiently minimizes the squared gradient norm. In particular, they show that if a specific Lyapunov function upper bounds the function value suboptimality for Algorithm A, then a corresponding Lyapunov function would upper bound the squared gradient norm for Algorithm B, which is the "dual" of Algorithm A. This duality relation is further extended to continuous-time dynamics. By using this new tool, the authors propose a new parameterized family of methods for reducing the squared gradient norm, as well as a new composite minimization method that improves the state-of-the-art by a constant factor.

Strengths

- I find the results in this paper interesting and novel. At the surface, accelerated methods for reducing the function value seem quite distinct from those for reducing the gradient norm, and the mechanism for the latter is somehow mysterious. Surprisingly, the authors uncover a one-to-one correspondence between these two families of algorithms. This new concept of H-duality could help us better understand OGM-G type algorithms and design better and practical ones for minimizing the gradient norm. - Moreover, the paper is very well-written. While the underlying proofs require heavy notations and tedious calculations, the authors manage to make the main theorems quite accessible and clearly explain the high-level ideas.

Weaknesses

Overall, I don't find any major issues with this paper. While this might be too much to ask, I feel that I still don't have a good intuition for H-duality theorem or why it makes sense to reverse the combining coefficients, except that the algebra indicates so. Still, I believe this could be the first step towards some more fundamental understanding.

Questions

- Just a clarifying question, it seems to me that the H-duality is only useful when the algorithm can be analyzed using the particular Lyapunov function in (2). On the other hand, many algorithms, such as the original Nesterov's accelerated method, may not conform to such a Lyapunov function, since they do not rely on the cocoercivity inequaltiy. Is it possible to generalize (2) to a broader family of Lyapunov functions? - By definition, it is necessary to know the time horizon $N$ to form the H-dual of a given algorithm. Is it possible to establish a duality relation between two anytime algorithms? More concretely, can we use H-duality theorem to obtain an anytime method for reducing the gradient norm? A minor typo: in (1) it should be $\nabla f(x_i)$ instead of $\nabla f(x_k)$.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

The authors have addressed the limitations.

Summary

This paper presents the concept of H-duality, which refers to the duality between optimization algorithms. The notion involves two sets of algorithms: 1) those that efficiently reduce the function value, and 2) those that efficiently reduce the gradient magnitude. The authors create the H matrix, which contains the coefficients of previous gradient evaluations at time step t, for all fixed step size first-order methods. They define the anti-transpose of H, denoted as H^A, as the H-dual of H. In the main theorem, the authors demonstrate that if there exists an algorithm that reduces the function value using matrix H, then there is another algorithm that minimizes the gradient magnitude using H^A. This duality property is applicable to both discrete time and continuous time first-order optimization algorithms. Leveraging this duality property for composite objectives, the authors utilize a proximal-based first-order method that minimizes the function value. Subsequently, they propose a novel algorithm that minimizes the gradient value.

Strengths

The introduction of duality between algorithms is a concept presented to the optimization community. This idea not only aids in establishing equivalence between algorithms but also proves valuable in conducting convergence analysis for these algorithms.

Weaknesses

The proposed duality, while introducing a novel perspective, has certain limitations as it does not encompass a broader class of algorithms and loss functions commonly used in machine learning. For instance, it requires the convergence of the last iterate and overlooks convergence based on average iterates. Additionally, it assumes the objective to be convex and L-smooth, which may not always hold in practical Machine Learning scenarios. As a result, the paper primarily pertains to optimization theory rather than providing specific optimization techniques tailored to machine learning applications, especially for stochastic algorithms frequently used in this field. The paper lacks a clear explanation of how discovering this equivalence between algorithms can facilitate the development of better optimization techniques. For instance, in cases where the objective is convex and the gradient vanishes (\nabla f* = 0), it is evident that achieving convergence based on function values can easily translate to convergence based on gradient magnitudes. Another aspect that remains unclear in the paper is whether algorithms that are H-dual to each other exhibit similar convergence rates. For instance, in the gradient descent (GD) example, it is observed that the gradient norm can attain a rate of O(1/N^2) under certain conditions. Consequently, it is ambiguous whether two dual algorithms have identical convergence rates or if one may achieve a better rate. In the former case, it becomes necessary to conduct separate convergence analyses for each algorithm to account for potential differences in their rates.

Questions

look at the weaknesses

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

Have been addressed

Thank you for your response

I thank the authors for their detailed response. The observation that the potential function is motivated by the Lagrangian of the PEP is interesting and partly answers my question, though why such a transformation would connect the two Lagrangian functions is still a bit puzzling to me. In any case, I believe this is a nice work and would be of great interest to the community.

Thanks for the response

Thanks for the response! I have no more comments.