Adaptive Proximal Gradient Method for Convex Optimization

Summary

The paper refines the analysis of AdGD to accommodate larger stepsizes, an approach that exploits local curvature instead of global smoothness. The technique is later extended to ProxAdGD. Experiments demonstrate the superiority of ProxAdGD over Armijo’s linesearh.

Strengths

1. The paper unfolds by providing intuition and examples, helping the readers to deepen their understanding beyond the technical results. 2. Better guarantees that exploits local properties of the objective are desirable, both in deterministic and stochastic settings.

Weaknesses

3. A more detailed comparison to the results of [MM20] is required. Does the improvement merely tighten the constants or enable a drastically different behaviour than [MM20]? 4. Experiments comparing the stepsize choices of the paper and [MM20] are sorely missing. Both the difference between the stepsizes along the optimization and the optimization error of each method.

Questions

5. See weaknesses. 6. Did the authors consider the stochastic case? Either by a theoretical analysis or by experiments. [MM20] provided both a theoretical guarantee (without adaptivity to local curvature) and experiments with neural networks. (The reviewer does not ask the authors to conduct new experiments with neural networks but merely asks if such were previously performed.) Overall, the paper presents a clear picture of AdGD which helps deepen our understanding, includes an improved stepsize selection and the new AdProxGD method. That being said, the quantification of the improvement is unclear due to limited comparison with [MM20]. Such a comparison will move along way toward establishing the value of this work. Typos: line 54 - some some, line 272 - experimentswe.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

Discussed in weaknesses.

Summary

The paper introduces new algorithms for solving convex optimization problems, where a step size parameter adapts to the underlying objective function. Adaptation is achieved by making good use of the already available gradient information, and does not have a further computational cost. The authors propose multiple variants. One of those rely on a generalized derivation of an algorithm from a recent paper, to achieve an improved step sizes. Another provides yet larger stepsizes, and a third one allows non-differentiable (but still convex) objective functions, provided that can be split into a smooth and a non-smooth function where the proximity operator of the non-smooth function is feasible to realize. They compare their algorithm against a simple alternative on a specific problem to demonstrate how it can reduce computational cost.

Strengths

The first algorithm alone, which relies on a generalized derivation of a past algorithm, is of interest. The two additional algorithms also allow to further expand the usefulness of the paper. In particular, the third algorithm, which allows handling of non-smooth functions, would be useful in practice. In particular, it extends the applicability of the algorithm to constrained problems (provided projections to the constraint set is feasible in practice), or potentially, problems with sparsity constraints, which can be enforced by convex functions like some variant of an $\ell_1$ norm. I think such problems are pretty relevant for ML, and I'd expect the paper to be of interest to a wide community.

Weaknesses

The attention is restricted to convex problems. To be fair, this is perhaps welcome, as it allows the authors to provide a clean analysis of their algorithms. In practice, many convex algorithms found their way to non-convex problems with success, sometimes without justification. At times, I wished the authors would complete their arguments fully. I have a few comment below. The numerical problem didn't feel very fair for the competitor algorithm (I probably would not have used such an algorithm due to how expensive its steps are -- see below).

Questions

- eqn 13 : I don't see how a simple substitution of the previous inequality to (10) gets you this. If you're using additional steps, please either not, or include details -- it's perfectly understandable to push some content to the appendix, but the manuscript is perfectly brings the development to this stage to suddenly switch gears. Since this subsection is meant to be simple, I'd suggest including details. - line 191, "note that the second bound..." : please note this is the "second bound in step 5 of Alg. 2". - eqn 15 : In this inequality, should $\alpha_k$ and $\alpha_{k-1}$ be interchanged? In that case, the following interpretation is also not correct. - eqn 16 : For a wildly changing function $L_1$ won't capture the behavior globally anyway. Is this meant for a relatively "well-behaved" function? - line 221 : I'd suggest writing out the definition of the proximity operator $arg min_t 0.5 \|x - t\|_2^2 + g(t)$ instead of relying on short hand. The text is perfectly readable without knowing what a proximity operator is. In fact, you could also include $\alpha_k$ in there, since that's used in the algorithm description. - line 222, "Algorithm 3, presented in Appendix C" : Please include the algorithm as part of the main text. - Numerical experiment on the constrained problem : I understand the motivation behind comparing the objective wrt the projections. However, this is particularly a problem where a line search would be feasible due to the high computational cost. It would be interesting to compare against a basic forward backward splitting method with a fairly reasonable estimate of the local $L$. If that's not possible, and the baseline algorithm is the most suitable, it'd be good to include an argument.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper considers optimization problems where the function is convex and possibly composite. Gradient Descent and the Proximal Gradient method are studied, and one of the main motivations of this work is the paper [MM20], which developed a locally adaptive step size and an associated algorithm 'adaptive gradient descent without descent AdGD'. In the current work, the authors consider whether the bounds on the step for AdGD are essential, and they find that they are, but can be improved upon. They present Algorithm 2, which employs their refined step size, and Theorem 2 details the convergence properties. As well as improving the step size criteria, this work also extends that of [MM20] by presenting an adaptive proximal variant. The algorithm is given in Algorithm 3, and convergence properties are presented in Theorem 3. The authors compare their algorithm with others in the literature in Section 5, including detailing possible extensions, and why they might prove tricky. Finally, numerical experiments are presented in Section 6 (with proofs and further experiments in the appendix).

Strengths

Writing. The paper was well written and I enjoyed reading it. I liked the writing style because the authors made efforts to explain *why* they were doing what they were (not just what they were doing). I liked that the authors opted to keep the exposition simple and easy to follow (e.g. see Remark 1 regarding the potential use of cocoercivity). Contribution. Gradient descent is one of the most important algorithms in this field, and the step size has a major impact on the practical performance of the algorithm. This work presents an step size selection condition that is conceptually simple, and is cheap to evaluate, which is a nice contribution. The extension to the proximal setting is also welcome.

Weaknesses

It would be good if the authors tightened up the wording of, for example, their theorem statements. For example, for Theorem 2, I think it would be better if they mentioned "given an initial point $x_0$, and an initial step size $\alpha_0>0$. Also, the phrase "converges to a solution" is used, but it would be better if they also referred to the problem they were trying to solve and said what they mean by a solution (and they should also specify that $F=f$, define $f_*$, etc). They should then check the other theorem statements and update them appropriately. I feel it is really important for them to be precise. In Lemma 1 I think it should be mentioned that $\alpha_k>0$ (i.e., the step size can be 'arbitrary but positive'). Numerical experiments. The authors presented several numerical experiments, which is good. However, it would have been good to have had more discussion explaining to the reader what the plots were showing, i.e., more emphasis describing the observed practical behaviour of the algorithms, and specifically commenting on the performance for the parameter choices.

Questions

N/A

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

N/A

Summary

In the paper, the authors explore two adaptive first-order algorithms in convex optimization, namely gradient descent and proximal gradient methods, which are based on observed gradient differences. With a novel Lyapunov energy, the authors prove its convergences assuming only local Lipschitz condition of the gradient and extend it to the proximal case. In addition, the methods allow larger initial stepsizes than those in previous work.

Strengths

For many other methods, such as Gradient Descent, we should assume the problems are globally L-smooth and calculate the value L. However, we just ensure the object functions are locally L-smooth if using the methods in this paper. The same as Barzilai-Borwein stepsize, the methods do not include linesearch procedure. It means they are just based on observed gradient differences and do not need high computational cost in each iteration. However, in the contrast to the Barzilai-Borwein stepsize, the paper could guarantee its convergences theoretically in convex and proximal case.

Weaknesses

1.We may not guarantee its convergences in the nonconvex case. 2. In the second experiment, the first term in problem may be (1+x_1^2 )^(1/2), rather than (1+x_1 )^(1/2).

Questions

1. What about the result by using stochastic gradient?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

response to rebuttal

Thank you for the responses. My comments were mainly suggestions -- I appreciate the additional clarification that you'll be adding. For the suggestions you choose not to follow, I won't press further. I was going to insist on (15), but I realized both versions are correct. Starting from (assuming the term inside $\sqrt{\cdot}$ is positive) $$ \alpha_k \leq \dfrac{\alpha_{k-1}}{\sqrt{2 \alpha_{k-1}^2 L_k^2 - 1}} $$ we have $$ 2 \alpha_{k-1}^2 L_k^2 - 1 \leq \dfrac{\alpha^2_{k-1}}{\alpha^2_k}. $$ Rearranging and dividing by 2, I get $$ \alpha_{k-1}^2 L_k^2 - \dfrac{\alpha^2_{k-1}}{2\alpha^2_k} \leq \frac{1}{2}. $$ I thought this contradicts (15) but multiplying both sides by $\dfrac{\alpha^2_{k}}{\alpha^2_{k-1}}$ and rearranging, we get (15).