Adaptive Proximal Gradient Method for Convex Optimization
Authors: Yura Malitsky
Konstantin Mishchenko
Venue: NeurIPS 2024 poster (2024)
Keywords: adaptive methods
gradient descent
proximal gradient method
Primary area: optimization
TL;DR: Adaptive versions of GD and ProxGD with large steps.

Abstract: In this paper, we explore two fundamental first-order algorithms in convex optimization, namely, gradient descent (GD) and proximal gradient method (ProxGD). Our focus is on making these algorithms entirely adaptive by leveraging local curvature information of smooth functions. We propose adaptive versions of GD and ProxGD that are based on observed gradient differences and, thus, have no added computational costs. Moreover, we prove convergence of our methods assuming only local Lipschitzness of the gradient. In addition, the proposed versions allow for even larger stepsizes than those initially suggested in [MM20].

Adaptive Proximal Gradient Method for Convex Optimization
Yura Malitsky Faculty of Mathematics University of Vienna, Austria yurii mal leissiii@uiiiii ac. at
Konstantin Mishchenko Samsung Al Center, UK
konsta.miish@@eeee.... miishhgmail....mmmmmmmmmmmm.mm.m com
Abstract
In this paper, we explore two fundamental first-order algorithms in convex opti- mization, namely, gradient descent (GD) and proximal gradient method (ProxGD). Our focus is on making these algorithms entirely adaptive by leveraging local cur- vature information of smooth functions. We propose adaptive versions of GD and ProxGD that are based on observed gradient differences and, thus, have no added computational costs. Moreover, we prove convergence of our methods assuming only locul Lipschitzness of the gradient. In addition, the proposed versions allow for even larger stepsizes than those initially suggested in [MM20].
1 Intro
In this paper, we address a convex minimization problem
min F(x). =E
We are interested in the cases when either F is differentiable and then we will use notation F or g. Here, f represents convex and differentiable
it has a composite additive structure as F F= f function, while y convex, lower semi-continuous (Isc), and prox-friendly. Throughout the paper, will interchangeably refer to the smoothness of and the Lipschitzness of Vf. occasionally with the adjective "locally." indicating that restricted to a bounded set. We will refer to this property smoothness, without mentioning the Lipschitzness of f. so we hope there will be no confusion in this regard.
For simplicity, in most of the introduction, we consider only the simpler problem min, fzr). We study one of the most classical optimization algorithms - gradient descent
k+1
x ()***)
Its simplicity and the sole prerequisite of knowing the gradient of make it appealing for diverse applications. This method is central in modern continuous optimization, forming the bedrock for numerous extensions.
Given the initial point z", the only thing we need implement (1) is to choose a stepsize ag (also known as a learning rate in machine learning literature). This seemingly tiny detail is crucial for the method convergence and performance. When a user invokes GD as a solver, the standard approach would be to pick an arbitrary value for au,, run the algorithm, and observe its behavior. It diverges at some point, the user would try a smaller stepsize and repeat the same procedure. If, on the other hand, the method takes too much time to converge, the user might try to increase the stepsize. In practice, this approach not very efficient, as we have no theoretical guarantees for randomly guessed stepsize, and the divergence may occur after long time. Both underestimating and overestimating the stepsize can, thus, lead to large overhead.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Below we briefly list possible approaches to choosing or estimating the stepsize and we provide more detailed literature overview in Section 5.
Fixed stepsize. When f is L-smooth, GD can utilize fixed stepsize or: < & and values larger than a will provably lead to divergence. Consequently, in such scenarios, the rate of convergence is given by [(**) S. O ( clearly indicating direct dependence on the stepsize. Nevertheless, several drawbacks emerge from this approach:
(a) L is not available in many practical scenarios;
(b) if the curvature of f changes a lot, GD with the global value L may be too conservative;
(c) f may be not globally L-smooth.
For illustration, consider the following functions. Firstly, when dealing with f() 211 bl( where E Rexd and b E R,, estimating involves evaluating the largest eigenvalue of A A. Second, the logistic loss fx) = log(1 + exp( (xpp-boo_ baa x)); with E R be E {-1, 1}. is almost flat for large I, yet for values of x closer to 0, has L = ||lall Thus, the solution is far from 0, gradient descent with a constant stepsize would be too conservative. Finally, consider f(x) = x². While this simple objective is not globally L-smooth for any value of L, any bounded set it is smooth, and we would hope we can still minimize objectives like that.
Linesearch. Also known backtracking in the literature. In the k-th iteration we compute *+*1 with a certain stepsize og and check a specific condition. If the condition holds, we accept *+1 and proceed to the next iteration; otherwise we halve og and recompute *+1 using this reduced stepsize. This approach, while the most robust and theoretically sound, incurs substantially higher computational costs compared regular GD due the linesearch procedure.
Adagrad-ty -ttpe algorithms. These are the methods of the type'
Uk = Uk-1 + / fz*"(()) [[**)*** )
k+1 = x² dk fz(**)
(2)
where c-1 2 is some constants, and dę is estimate of |z - x01 for some solution x². While such methods indeed have certain nice properties, dy is usually either constant or quickly converges to constant value, so a quick glance at (2) will reveal that its stepsizes decreasing. Therefore, despite the name, we cannot expect true adaptivity of this method to the local curvature of f.
Heuristics. Numerous heuristics exist for selecting ag based on local properties of and ff. with the Marzilai-Borwedr method [BB88] being among the most widely popular. However, it is crucial to partieularly interested in such approaches, they lack consistency and may even
note that we lead to divergence, even for simple convex problems.
We have already mentioned adaptivity a few times, without properly introducing it. Now let us try to properly understand its meaning in the context of gradient descent. Besides the initial point 2 GD has only one degree of freedom approximately an inverse of the local smoothness. We call method adaptive, if it automatically adapts stepsize to this local smoothness without additional expensive computation and the method does not deteriorate the rate of the original method the worst case. our case, the original method is GD with a fixed stepsize.
its stepsize. From the analysis we know that it has to be
By this definition, GD with linesearch is not adaptive, because finds the right stepsize with some extra evaluations of or V.f. GD with diminishing steps (as in subgradient Adagrad methods) is also not adaptive, because decreasing steps cannot general represent well the function's 's curvature; also the rate of the subgradient method is definitely worse. It goes without saying, that for good
'ee provide only the simplest instance of such algorithms.

---

method its rate must experience improvement when we confine the class of smooth convex functions the strongly convex ones.
CONTRIBUTION
In a previous work [MM20], which serves as the cornerstone for the current paper, the authors proposed an adaptive gradient method named "Adaptive Gradient Descent without Descent" (AdGD). In the current paper, we
deepen our understanding of AdGD and identify its limitations;
refine its theory accommodate even larger steps;
* extend the revised algorithm from unconstrained to the proximal case.
The analysis in the last two cases is not a trivial extension, and we were rather pleasantly surprised that this was possible at all. After all, the theory of GD is well-established and we thought it to be too well-explored for us to discover something new.
Continuous point of view. It is instructive for some time to switch from the discrete setting to the continuous and to compare gradient descent (GD) with parent - gradient flow (GF)
x' zt(t)= = f
x=0) = Tu.
(3)
where is the time variable and (t) denotes the derivative of xx(t) with respect To guarantee the existence and uniqueness of a trajectory z²t) of GF, it is sufficient to assume that V is locally Lipschitz-cootinuous Then one can prove convergence of ztt) to minimizer of f in just few lines. For GD, on the other hand, the central assumption is global Lipschitzness of V.. Our analysis of gradient descent makes it level: local Lipschitzness suffices for both. Or to put differently, we provide an adaptive discretization of GF that converges under the same assumptions as the original continuous problem (3).
Proximal case. We emphasize that there is already an excellent extension by Latafat et al. [Lat+23] of the work [MM20] to the additive composite case. Our proposed result, however, is based on an improved unconstrained analysis and uses different (and simpler) proof. We believe that both these facts will be of interest. We don't have a good understanding why, but for us finding the proof for the proximal case was quite challenging. It does not follow the standard lines of arguments and uses novel Lyapunov energy the analysis.
Nonconvex problems. We believe that our algorithm will be no less important in the nonconvex case, where gradients are rarely globally Lipschitz continuous and where the curvature may change more drastically. It is true that our analysis applies only to the convex case, but, as far as we know, limited theory has never yet prevented practitioners from using methods in a broader setting. And based on our (speculative) experience, we found it challenging to identify nonconvex functions where the method did not converge to a local solution.
Outline. In Section 2, we begin by revisiting AdGD from [MM20], examining its limitations, and demonstrating simple way to enhance it. This section maintains an informal tone, making easily accessible for quick reading and classroom presentation. In Section 3, we further improve the method and provide all formal proofs, most of which we move to the Appendix. Section extends the improved method to the proximal case. In Section we put our finding in the perspective and compare to some existing works. Lastly, in Section 6 (see also Appendix D), we conduct experiments to evaluate the proposed method against different linesearch variants.
1.1 Preliminaries
We say that a mapping is locally Lipschitz if it is Lipschitz over any compact set of its domain. function f: Rd - IR is (locally) smooth if its gradient V. is (locally) Lipschitz.
A convex L-smooth function is characterized by the following inequality
f(y) f(x) (V)(x).
x)
2L VV(()
[1(=)]1 Vz.y.
(4)
3

---

This is equivalently of saying that f
ffiz is Σ -occoercivee operator, that is
(vf(y) y > [V [=(=)]| Va, y-
(5)
For convex differentiable f that is not Z-smooth one can only say that f is monotone, that is Vr,y.
V (z). x>
-
(6)
We use notation [t]+ = mt, 0} and for any a > we suppose that j -00. With a slight abuse of notation, write [n] to denote the set f1....,mk, A solution and the value of the optimization problem min f() are denoted by x² and fx, respectively.
n).
Adaptive gradient descent: better analysis
Let us start with the simpler problem of min. f(x) with convex, locally smooth f: R - R. To solve it, [MM20), the authors proposed a method called adaptive gradient descent without descent (AdGD), whose update is given below:
min 1 ON 11-00-100--11 2 2/( (f((*-1)||
1 - x: xb-11
)
where 02 O
ax-1 (7)
x 6+1 = = [
Similarly to the standard GD,, this method leads to O(1/k) convergence rate. However, unlike the former, it doesn't 't require any knowledge about Lipschitz constant of V and doesn't even require global Lipschitz continuity of V..
The update for ag has two ingredients. The first bound an < <vI+ 8 -- ---- sets how fast steps | x-1
may increase from iteration iteration. The second ork & 2 - corresponds to estimate of local Lipschitzness of f.
It is important to understand how essential these bounds are. Do really need to control the growth rate a or is an artifact of our analysis? For the second bound, it is not clear whether in the denominator is necessary. For example, given L-smooth f, our scheme (7) does not encompass standard GD with a₃ = for k.
First bound.
Answering the first question is relatively easy. Consider the following function
(())
1222, [a([æ] log(1 [=)) b, x Φ 1,
[-1,
f(x)
(8)
where parameters a, are chosen ensure that f(+1) and f'(+1) well-defined, namely a = 2 and b = 2 2og 2' see Lemma in Appendix A.
From an optimization point of view, is nice function. In particular, it is convex (even locally strongly convex) and gradient 1-Lipschitz, see Lemma 3. This means that both GD and AdGD linearly converge on it. However, if we remove the first condition for as in AdGD, this new modified algorithm will fail to converge. We can prove an even stronger statement. Specifically, let e > 1, ag = 1 and consider the following method
1 k
OA c (1)t) V
VA > 1
Vf(x)) Vk > 0.
In other words, the update (9) is the same as (7) except we removed the first constraint for og in (7) and introduced a constant factor to make the second one more general.
Theorem For any 2 there exists d0 such that the method (9) applied to I defined (8) diverges.

---

The formal proof of this statement is in Appendix A, but its main idea should be intuitively clear. First, observe that for with large absolute value, f(x behaves mostly like a linear function. However, (a) approaches -1 when x + -o and +1 when + +oc. Therefore, if x* and - have the same sign, the local smoothness estimate will be too optimistic and x*+11 will "leapfrog" the optimum. In contrast, if the signs of x² and -²=1 are different, then x+ will fail to get sufficiently close to the optimum. It is interesting remark that on this function both versions of the Barzilai-Boud -orweinn method will diverge as well.
Consequently, the answer to the first question is affirmative: we do need some extra condition for the stepsize ar--
Second bound. The answer the second question is the opposite: it is indeed an artifact of our previous analysis. In the next section, we propose an improvement over the previous version [MM20]. We give concise presentation in informal way. We keep more formal style for section 3 where an even better version (also slightly more complicated) will be presented.
2.1 Improving AdGD
The analysis of GD usually starts from the standard identity, followed by convexity inequality
|| - x 1| | og ax (x²*) - xz'
1| - xx112 - 20rk (V (V x,="","))) + ((
< 11 - x²112 20t (s(x*) - ((x))) a \({)))
(10)
In [MM20] the only "nontrivial" step in the proof was upper bounding V ||xb+1 x* 112 Now we do it in slightly different way. First, need the following fact.
that is
Lemma 1. For GD iterates (x*) with arbitrary positive stepsizes, holds
(v)(**) ff(=*=))) & [[
(11)
Proof.
This is just monotonicity of Vfin in disguise:
[V (v*("") (((===1)) (Vf(2 -v((t)) vf(**-11)
(V (f(x*), 0.
a
Now we are going to bound || x* 112. For convenience, denote the approximate local Lipschitz constant
[V((at) (
L
|| 1
Let og satisfy as (x( (x(+11)) < <11Ø=* -xt-1l for some 7 0, that is agLi & Y
Using ||u||2 = ||u - 0/|2 - ||0|| + 2(u,, v),, we have
||x 11 a
-2 - +00 Vf((+-1))
= agL2212 - 112 V 11 + (vx vs(x
< - vf(x*-1))
= - - x
<
f(xx1))
(12)
where the last inequality follows from convexity of f. For 7 < 1 we can rewrite (12)
72
72
0g.k
|1a - 2812
1 1- 110
-x-111
1 22 ||a x11
(f(x - f(())))
72
5

---

Substituting this inequality into (10) gives us
Os
| 2=12 2 + || 1ett1
1= + ax
2
(f(at) -
1 1-
72
agdx
< | 1²11 11 1- 11 112 + 1-
( f-).
(13)
As we want to telescope the above inequality, we require
0g0kk 1- a (2 0x-1 1-
af (2(1- 0k-1) a
On the other hand, we have already used that Cg & % These two conditions lead to the bound
0g min min 2/(1 72) + 0 10k-1
7
(14)
L
where 7 (0, 1) can be arbitrary. Now by playing with different values of y, we obtain different instances of adaptive gradient descent method. For instance, by setting y = /2 we get
0g min ( 1V1+00-Iaa
V2Lk
which is strict improvement upon the original version in [MM20]. A simple reason why this is possible is that, unlike [MM20], we did not resort to the Cauchy-Schwand inequality and instead relied on transformation (12) and Lemma
Algorithm Adaptive gradient descent
Algorithm 2 Adaptive gradient descent-2
1: Input: x² E Rd_ 0g = O, 0x > 0
1: Input: x" E IRd, 0p
3 ag
> 0
2: x² x. -r V (xx")
2: x² = x oo f(("))
3: for k = 21,2... do
for k: 1,, do
4: LB [[V((=*) ff(x f( III | - 21
4: LA = [Vʃ(=*) - -
5: a minf + 0g 1kk-1 22L.
5: ag = min (V 3/3
2 0 1
ak-1
6: k+1 z Ork (z**))
6: x k+1 x
an V((
7: O2 as
DK-1
0₂
We summarize the new scheme in Algorithm 1. and hope that inequality (13) should be sufficient for the curious reader to complete the proof. In any case, the next section will contain further improvement with all the missing proofs.
We do not provide formal proof for this scheme
Remark One might notice that we have used several times monotonicity V where we actually could use stronger property of cocoercivity (5). That is true, but just prefer simplicity. We recommend work [Lat++3]] that exploits cocoercivity this framework.
Adaptive gradient descent: larger stepsize
In this section, we modify Algorithm to use even larger steps resulting in Algorithm 2. This, however, will require a slightly more complex analysis.
Recall the notation [t] max(t, 0} and note that the second bound ag & av
in step
2n
of Algorithm 2 is equivalent to
of
a
(15)
2a
2'
which obviously allows for larger range of ag than a. & in Algorithm On the other
hand, the first bound ag & / + 0k-1au-1 is definitely worse. At the moment, it not even clear whether it allows ag to increase.

---

Remark 2. A notable distinction between Algorithm and Algorithm is that the former allows to use a standard fixed step a₁ z. provided that f is L-smooth. For instance, if we start from on I and use 1. > L in every iteration (we can always use larger value), then it follows from (15) and 0g-12 that ag
for all >
Algorithm 2 requires an initial stepsize ag. While the algorithm converges for any value ag > 0, it is important to choose initial step og wisely. We suggest to do the following
1
choose on such that 00 E
(16)
V2
The upper bound ensures that ag is not too large, while the lower ensures that it is not too small either. In most scenarios, this requires to run a linesearch, but we emphasize that is only needed for the first iteration. Further discussion this topie is in Appendix B.1.
We first prove that the sequence (x*) is bounded and then derive the convergence result. Both statements are proved in Appendix B.2.
Lemma The sequence (x*) is bounded. In particular, for any solution x² we have x²t E B(x", R). where
R² ||-- V ao(((x") f.). Theorem 2. Let be convex with locally Lipschitz gradient V f. x E IR, and ag 0. Then the sequence (x*) generated by Algorithm 2 converges to a solution of ming (x) and
(17)
min (i(())))) - (E
(18)
2 E
where defined as in (17). In particular, if ou satisfies (16), then
LR²
min min(J(x') - S-) V2k'
(19)
RE(M]
where I is the Lipschitz constant o over B(x", R).
Of course, the important bound here is (18). The second bound only shows that our choice of stepsizes ag cannot be too bad. The bound in (19) is stronger than the bound ^3LR", which could be obtained 2 as direct consequence of Lemma 7 with simple analysis. The derivation of the sharper bound as in (19) presented in Appendix B.3 with, unfortunately, much more involved analysis.
4 Adaptive proximal gradient method
In this section, we turn to a more general problem of composite optimization, min F(x) == (x) + g(x).
(20)
where g: Rd + (-oc, +oo] is proper convex Isc function and f: Rd - R. is convex differen- tiable function with locally Lipschitz f.. Additionally, we assume that g is prox-friendly, that is we efficiently compute its proximal mapping prox, (Id +
We present Algorithm that is a verbatim adaptation of Algorithm 2 with the proximal operator applied on top of the main update (similarly, it could be applied to Algorithm 1). However, its analysis not a straightforward generalization. We encountered two issues in the proof:
combining previous analysis AdGD and the prox-mapping. As shown even (13), we operate with the vectors x² and 2-1 in terms of However, using the prox-inequaligg gives us the value (+*++)), which is not straightforward to combine with f((*) and ((*==1)
proving convergence of (a*). The challenge arises from having non- non-linear update due to the prox-mapping and allowing de to go co, making the proof quite different from the traditional approach.
We define R in the same way as in (17)
R - 22 20 (F(22²) (F -.)).
(21)
where FF(x") denotes subgradient of F 2
7

---

Algorithm 3 Adaptive proximal gradient method
Input: x² E R 80 1/4 ao 20
2: x² prox ang (x ag Vf(²))
3: for k = 1, 2.
do
4: L = | (x²)) ()((*~1)|1
110 - xx-11
5: ak = min
V 5 + On 0 //20 0
#/ [1] = max(4,
22 1
6:
x k+1 prox (roxongg(**
(xt aA vx((')))
7:
0s
Theorem 3. Let f be convex with a locally Lipschitz gradient V g be convex Isc, x E R2, and
ag > 0. Then the sequence (x*) generated by Algorithm 3 converges solution of (20) and
R
min min(F(x') -F))) vE(k]
< 2 2 2i==1 00
(22)
In particular, if oro satisfies (16), then
LR
min (((x) F.)
(23)
VE(K]
V2k²
where L is the Lipschitz constant of f over B(x", R).
Literature and discussion
Linesearch. There are many variants of linesearch procedures that go back to celebrated works of Goldstein [Gol62] and Armijo [Arm66]. We discuss an efficient implementation of the latter in detail in the next section. For other variants of linesearch, refer to [BN16; Sa117].
Adagrad-type methods. Original Adagrad algorithm was proposed simultancously in [DHS and [MS10] M0]. The method has had stunning impact on machine learning applications. It has also spawned a stream of various extensions that retain the same idea of using eventually decreasing steps. Because of this, its adaptivity is more prominent in the non-smooth regime, where stepsizes must be diminishing to guarantee convergence. Recent works [DM23; IHC23] have proposed ways to increase dy in the update (2) and [KMJ23] even proved convergence of some Adagrad-type methods on smooth objectives. However, the stepsize in these methods eventually stops increasing, making them less adaptive.
In addition, Adagrad-type methods are usually sensitive to the initialization, as they either degrade in performance when di D and D not chosen carefully, or their convergence rate depends multiplicatively on log(l|æ - x (l/d).. In contrast, in our methods, the cost of estimating do to satisfy condition (16) is additive and its impact vanishes as the total number of iterations increases.
Refined results on GD with fixed stepsize. Paper [TV22] summarizes quite well the difficulty of GD analysis with large steps. In the authors derive sharp convergence bounds separately for two cases al E (0, 1] and aL E (1, 2), and the latter case is considerably harder. In our analysis it is even harder, since the steps can go far beyond the global upper bound 2 surprising recent result [Gri23] showcases how little is understood in this case.
Small gradient. The lack-of- property makes it hard to deduce the (1/kk) rate for the last-iterate [**(())),, which is known for GD with a fixed stepsize. We leave it as an open problem to establish rate.
Extensions. Because the analysis the algorithm is so special, it not easy to extend to basic generalizations of GD. However, some works have already built upon it. In [VMC21], the authors

---

consider a convex smooth minimization subject to linear constraints and combined the adaptive GD [MM20] with the Chambolle-Poee Pookkeeeeockkeeooo algorithm [CP10]. The authors of [Lat+23] went even further and considered a more general composite minimization problem subject to linear constraints, where the same two ideas as before were combined with a novel way of handling the prox mapping.
If we consider variational inequalities settings in the monotone case, then it is not clear how such adaptivity can help, since the most natural extension, the forward-backwatd method will diverge. Furthermore, the adaptive golden ratio algorithm [Mal19], which inspired the development of AdProxGD, already includes all the features that AdProxGD has.
6 Experiments
In the experiments' we compare our method to the ProxGD with Armijo's linesearch. We believe it is the best and arguably the most popular alternative to our method. An efficient implementation of Armijo's s linesearch requires two parameters, 8 > and r < iteration of linesearch starts from dx -0 that is, we want to try slightly larger step than in the previous iteration. If linesearch does not terminate, we start decreasing a stepsize geometrically with ratio Formally, are looking for the largest Cr ag- 1, for 0, 1, ...... such that for x
the k-th iteration, the first
prox (It ag fxx it holds that
[(* & f(x*) + (1
|| x² 112
201
is evident that each iteration of this linesearch requires one evaluation of f and prox,- However, important to highlight that in some cases, the last evaluation of f(**+1) (during linesearch) may not incur any additional costs, certain expensive operations, such matrix-vector multiplication, can be reused to compute the next gradient V f((*+1)) Throughout our comparisons, we consistently took these factors into account and reported only essential operations that cannot be further reused.
Our legend will stay the same for all plots:
AdProxGD (1.1, 0.9)
(1.2, 0.5)
(1.5, 0.8)
(1.1,
(1.2, 0.9)
(1.5, 0.5)
(1.2, 0.8)
(1.1, 0.8)
(1.5, 0.9)
where each pair numbers represents (s, r) for ProxGD with linesearch described above. As we will see, the choice of (s,r) matters a lot. More experiments are provided in the Appendix D.
Maximum likelihood estimate of the information matrix. We consider [BV04, Equation (7.5)), where our goal is to estimate the inverse of a covariance matrix Y subject to eigenvalue bounds. Formally, this problem can be formulated as follows
min
f(X) = log det X tr(XY) subject to 11 11 X x ul,
(24)
X
where Sd denotes the space of n-by-n symmetric matrices and & B means that B is positive semidefinite.
Computing projection onto the constraint set C C (X: X 5 w/} requires computing matrix eigendecomposition. However, it is noteworthy that once the eigendecomposition is computed, both the objective and gradient evaluations can be carried out a low cost. Consequently. when comparing methods, only emphasized the number of projections conducted. We generated random y E IR" with entries from N (0, 10) and ò, e R" with entries from N (0, 1). and then set y/1 = + 6,, for i = 1...,, M. Then we computed Y = M DM y.u, The results are presented in Figure 1. For two scenarios we generated, the proposed method converged faster than any of the linesearch versions.
Acknowledgments and Disclosure of Funding
The authors would like to thank Puya Latafat, who found a subtle error in the convergence proof of (x*) in Theorem 3 in the first version of this manuscript. Thanks to him, were able to simplify our proof considerably. We also thank anonymous reviewers who found many typos and inaccuracies. Yura Malitsky's 's research was partially funded by the Austrian Science Fund (FWF) (10.55776/STA223].
hhtps///ghhbb.ommmymmllll///aalp

---

AdProxGD
(1.2, 0.5)
(1.5,0.8) 0.8)
(.1.0.5)
(1.2, 0.9)
(1.1. 0.9)
(1.5, 0.5)
(1.2, 0.8)
(1.1, 0.8)
(1.5, 0.9)
10
10
objective
10
10
10-10 10
10
1000 1500
5.00x10' 1.00x10* 1.50x10*
projections
# projections
(a) Fl 100, [ = 0.1, 10 = 50
(b) 50, 1 = 0.1, = 1000. M = 100
Figure I: Maximum likelihood estimate, problem (24)
References
[Arm66]
L. Armijo. "Minimization of functions having Lipschitz continuous first partial derivatives". In: Pucific J. Math. 16.1 (1966). pp. 1-3, DOI: 10. 1............ 2140/pjm...m.. 1966. 16.1.
[BB88]
J. Barzilai and J. M. Borwein. "Two-point step size gradient methods". In: IMA J Numer Anal 8.1 141.
(1988). pp. 141-148. DOT: 10. 1.93/imammnt
[BN16]
J. Y. Bello Cruz and T. T. Nghia. "On the convergence of the forward backward splitting method with linescarches". In: Optim. Methods Softw. 31.6 (2016), pp. 1209-1238.
[BV04]
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. DOI:
10. 1017/cbo97905 18104411.
[CP10]
A. Chambolle and T. Pock. "A first-order primal-dual algorithm for convex problems with appli- cations imaging". In: Math Imaging Vis 40.1 (2010), pp. 120-145. DOI: 10. 1007/
010-0251-1.
[DM23]
Defazio K. Mishchenko. "Learning-rate rate--rteeeeeeee learning by D-adaptation". In: Proceedings of the 40th International Conference on Machine Learning. Vol. 202. 2023, pp. 7449-7479.
[DHS1]]
Singer. "Adaptive subgradient methods for online learning and stochastic optimization". In: J. Mach. Learn. Res. 12 (2011), pp. 2121-2159.
Duchi, E. Hazan,
[Gol62]
A. A. Goldstein. "Cauchy's method minimization". In: Numer. Math. 4.1 (1962), pp. 146-150. DOE: 10. 1000000003966006.
[Gri23]
B. Grimmer. "Provably faster gradient descent via long steps". In: (2023), arXiv: 2307 2307.06324.
[HC22]
M. Ivgi. Hinder, and Carmon. "DoG SGD's best friend: parameter-fi free dynamic step size schedule". In: Proceedings of the 40th International Conference on Machine Learning. Vol. 202. 2023, pp. 14465-14499.
[KMJ23]
A. Khaled, K. Mishchenko, and C. Jin. "DoWG unleashed: An efficient universal parameter-free gradient descent method"' In: (2023). arXiv: 2305. 16284.
[Lat+23]
P. Latafat, A. Themelis, L. Stella, and P. Patrinos. "Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient". In: (2023). arXiv: 2301. 2301.04431. 04431. Y. Malitsky. "Golden ratio algorithms for variational inequalities". In: Muth. Program. 184.1-2 (2019), pp. 383-410 DOr: 10. 1007 00000//0000---00 019 -019--011----11111 w. arXiv: 1803. 1803.08832.
[Mal19]
[MM20]
Y. Malitsky and K. Mishchenko. "Adaptive gradient descent without descent". In: Proceedings the 37th International Conference on Machine Learning. Vol. 119. Proceedings of Machine Learning Research. PMLR, 2020, pp. 6702-6712. arXiv: 1910.
[MS10]
H. B. MeMahan and M. Streeter. "Adaptive bound optimization for online convex optimization". In: Proceedings of the 23rd Annual Conference on Learning Theory (COLT). 2010. Salzo. "The variable metric assumptions".. . In: SIAM J. Optim. 27.4 .7.4( (2017), pp. 2153-2181 DOL: 10. 1137 / 1m1077344.
[Sal17]
splitting algorithm under mild differentiabiliiy
[TV22]
M. Teboulle and Y. Vaisbourd, "An elementary approach tight worst case complexity analysis of gradient based methods". In: Math. Program. 201.1-2 (2022), pp. 63-96. DOt: 10. 1007000001000
022-01899-0.
[VMC21] M.-.. Vladarean, Y. Malitsky, and V. Cevher. "A first-order primal-dual method with adaptivity to local smoothness". In: NeurIPS. Vol. 34. 2021, pp. 6171-6182, arXiv: 2110. 2110.15148, 15148.
10

---

Appendix
A Counterexample
Lemma 3. The function f defined in (8) satisfies the following properties:
1. f is convex.
2. f' is I--Lipschitz with T, = 1.
3. f is locally strongly convex, i... for any bounded set A' there exists constant JAx >> 0 such that (f'( - f'()) > px - yl for any æ, y E X.
4. [x)) < G with G = 2.
5. f is 2-Lipschitz.
Proof. First, let us find f' and] f":
f(x))
2
I [
(x)
1.
x (-1,1) I x& [-,,]]
oz I+
x && [-1,]
so indeed 2 and 2 log 2 g. Convexity of f follows from the fact that f > 0 for any x. Lipschitzness of f follows directly from the bound f (x)x)= & 1 for all æ. Similarly, local strong convexity follows from the bound (x) 2 max (1= =: fex for any x X. Finally, the last
two properties trivially follow from the expression for f'(x).
Proof of Theorem I. Let choose x0 r + 2 with sufficiently large >> 6c. This readily implies that
2x
(2 - x 22
+ x
xd +1
Our goal is to show that the iterates follow very specific pattern. Namely, we prove that for all > 0,
sign(x²* 2M) = sign(x.2 21+1)
sign(x 2x++) * sign(22h),
|x 2x+ 2/x0 2k+11
2k
If this condition holds true, then the sequence (x must be divergent.
First, observe that if |,**), | admits simple expression:
e r and sign(x*) = sign(r*-1). )) then the smoothness estimate
A-1
1zt
k-
(x - fx
1+ |
1+ ++
1+
1 1zz k-1
La
1x -xt-1
x
2
(1+ + bx ()(()(1 + 1x
r(1 110k
Therefore, in that case axl (x*)((z*)) > x(1+)=11) 1D ff (xxxx)) = rxw'l > 3/,²). Since sign(f'(x*))
2c
sign(x*), it implies that ( > 2| and sign(**** # sign(**)).
Next, if |x=), k r with |a*l| > 2| and sign(x*) * sign(x 1), then we have
2|="| 1+127
and
(x - (2(x-11)
1+|2*
x²
1+
k-
k-1
I+|a+
+ 1لايع
La
1 x
x
+ |
3
2
+
l
lrck
+
x

---

|n"1 |="1 Since sign(f((x))) sign(x*) and 1+| < 2c
1.4 3. we
This implies ag conclude that sign (x: +1)
2(1+
sign and
||²| (1
|n
Ork |ack
|
|
As x and x satisfy the first case, by induction we deduce that all iterates (x*) follow the described pattern.
B Analysis of Algorithm 2
B.1 Initial stepsize (expanded discussion)
Algorithm 2 requires an initial stepsize ogg While the algorithm converges for any value og > 0 with the rate
R
mfn()(r)) 2
[E[A]
(see eq. (17) for the definition of R), the choice of ax will impact further steps due to the bound Or & 12233 + 0x-10 Because of this reason, we do not want to choose ag too small. On the
other hand, too large og will make R large. To counterbalance these two extremes, we suggest to do the following:
[11 122
1
choose an such that cuL1 E
(25)
The upper bound ensures that ag is not too large, while the lower ensures that it is not too small either. In most scenarios, this requires needed for the first iteration. In some sense, our condition (16) is similar to classical Goldstein's 's rule [Gol62] on selecting the stepsize: not too small and not too big.
a linesearch, but emphasize more time: it is only
Of course, if we start with a very small co, only the first bound for og will be active for some time, and we will eventually reach a reasonable range for stepsize. However, linesearch with a more aggressive factor (say, 10) will allow us to reach this range faster. If we start with og = 10-8 when in fact reasonable range for steps in this region is [1, 10). then we will need at least 100 iterations of our method, while linesearch with a factor 10 will find it in less than 10 iterations.
It may happen that the problem is degenerated in the sense that for any Og. 0gh2 < + In other words, increasing ogy leads to decreasing L1 and linesearch may never stop. In this we should terminate a linesearch after og reaches any prescribed value, say
B.2 Analysis of Algorithm 2
Lemma 4. For iterates (x*) of Algorithm it holds
1 I x 112
3
||a z* 112
-
2 @f
(26)
Before we continue, let us give some intuition for this lemma. Its analysis follows mostly the same steps as in (12). However, now we will split fxx (1=)]] into two parts and use one of it to improve the smoothness bound for ag.
Proof. We start from the third line in (12) and then apply the above splitting:
|| k 1|2 = az
2 1,0
x²
11-1 of (1* 1/2 + (V (((²"1))
2
a 1
11 - x 1
1 (V
20
2
(1580111
2 110 x 1 2
2 (V ((*)), v 1)
0
3
x 112 + oy 0n (V /V ( - 2t
(27)
Convexity of of completes the proof.
12

---

Lemma 5. For iterates (x*) of Algorithm 2 and any solution x" it holds
| - x" 1|² + || 1²1 + ax ((a)) -.)
< || x= 11 + 1| - 111 30n -J.))
(28)
Proof. From (26) we have
|| $ 112
< 11 x 21- || - 2²112 -3 f(x²)).
(29)
Using this inequality in (10); we get
| x² 2² + || 2²11 + 22x (fx(f(x*)) - f+)
< || x²1 1|? + || 111 3ax O2 (f(xx=1) -f(x"))
which is equivalent (28).
Proof of Lemma 2. The first bound for ou in Algorithm 2 gives us 30y02 < + (2 -3)---))---1 We use in (28) and telescope then obtain
|| 6+1 x²'l 1|2 +
a2 (2
< || x 11? + || - 10123 ao ((a))
(30)
This immediately implies that (x*) is bounded, but we would like to obtain the bound without an intermediate iterate x² From (10) we know that
| - x01 1| & 1|
x²112 + [(x)|1 20xl)(x²)) -.))
Combining it with (30), we deduce
| 6+1 - x²1 + || k+1 - + (2+30))(f(a)) - S.)
< 11 x²112 + 2a V f(x + 30000(f(=)) (fx")) f.).
Using that 0, completes the proof.
we did in Algorithm I which would have improved the final constant R. However, since the first bound for og is worse this time, we would need a more complicated initial bound for ag. We decided to keep it simple.
Remark 3. We could have used Og
Notation. For brevity, we write + 1 to denote that in the k-th iteration satisfies the first bound, that is 0g = / + 6x-1. Similarly. for ag + 2. Also let L be the Lipschitz constant of V f over the set B(x", R). This means that LA & L for all k.
Next few statements are not very important for the first reading, as they only concern with lower -i bound of Σ a4. The main statement in Theorem 2 is valid independently of them, the reader can go directly there.
Lemma 6. If a + 2, then ar >
and ax-1 + a > Z. V2L
Proof. Note that in this case ag 20 14 and hence 1 213. This implies that 1. V2L
Ok
VILK
By AM-GM inequality.
+
+
1 2/
(0x-1 + ox)2 (o=1+
2 0k-10k
400
and the conclusion ax-1 0ek
8
2 follows.
2
La
Lemma 7. If ao satisfies (16), then ag >
1 for
all le >> 1.
VSL
13

---

Proof. We use induction. For k = 1, we have either on = / 0000 3 VEL
or 01 + 2, which in
view of Lemma also implies on > V2L
Suppose that 0--1 VaL.
and we must show that on V31. If 0 H then done.
Therefore, suppose that ag 1. Consider two options for ak-1. If ag-1 + 1, then Pk-1 3 2233.
Thus, for ag we have that
2 + 3
Okk
V
2 ax-1 13
V3L
If (1-1 + 2, then ag-1
and hence
/2L.
0g V
02
1
3
3 /2L
V3L
which completes the proof.
Remark 4. It is clear from above proof that condition oo give us the basis for induction. Without that condition, one can still show in the same way that ag > min V3L
J2L, from (16) was used only to
k The stepsize in the previous section is Summing this result from 1 to h yields Σ ON > V37.
& so it is natural to wonder: why does the current section contain a "larger lower bounded by V2L stepsize"? The answer is that while cannot show that each individual step is larger, still show in the next theorem that its total length will be lower bounded by the same quantity.
Proof of Theorem 2. We proceed in the same way as in Lemma 2, but this time keep all the terms that were discarded earlier. Specifically, summing (28) over all le yields
1 8+1 x² x=2 + || 1²1
az (2 + (f - f.) + Σ (a.(2 30,) (0(+10++))(((²')) - fa)
1 - x11 x21 ||- x0 + 3a (f(x)) f-) < I 201
1 + V + (n( - f.)== R2
(31)
where the last two bounds follow from the same arguments in Lemma Note that each factor (a + 30x) - 3ax (x+1) is nonnegative and their sum is
(2 38
(ax(2 + 30.) 30, (o,-10+41) = 04 + 30 2
Σ 2=1
O2-
Hence, we readily obtain that
R
min(f( fa) 2 >
kE(k]
In particular, if onp satisfies (16), then inequality (19) is a direct consequence of Lemma 11, which we prove in the next section.
remains to prove that (a*) converges to a solution. The next arguments will similar to the ones in [MM20]. We have already proved that (1**) bounded. As f is L-smooth over B(x", R), we have
f(x)) f(*²)
- 2L
Using this sharper bound instead of plain convexity in (10) and repeating the same arguments in Lemma 5, we end up with the same inequality plus the extra term
- ||x x x12 + ||x0 x²11 + ag (0x) +.)+ + ak
T | [2
< ||a0 - x²12 112 + ||a. 1 3a O (f f.).
(32)
14

---

Now, by telescoping this inequality we infer that Σ t fV < R². Since the sequence
(ax. is separated from 0 (note that this is independent of condition (16) by Remark 4), we conclude that (x** + k + oc. Hence, all limit points of (x*) are solutions. Applying a0 <
(2 + 30 1 in (32) we get
| - 10 + bx+1 < || - x²1 bk:
where by = || 112 + oz (2 + +0 (0 ([(x))1) fa). Then the convergence of (a*) to
solution follows from the standard Opial-type arguments.
B.3 Better bounds for the sum of stepsizes
h In this section, we prove the bound Σ 04 V2r.
Lemma 8. If 0g < then ag + and ag 1x-14x V5, ax22b > ax-z >
Proof. By definition, ag + means that or / + 04-10 and thus 0g
Hence,
0g + 2. Then we have that 02 /202 _4
J which implies ax- I > v5. Since we get
large -1- the first bound on stepsizes does not allow previous steps to be much smaller. That is the idea we shall use.
For any k, we have that 0g < V ] - As 0o & 1, it is trivial to prove that 0g < I+ to.
which is the root of
+t O. From ax-IL > V5, it follows that
2 v5 <a V - toak-2Lk.
Hence, to prove 2 2
3 2. it only remains to check that >
/5 3 2.
to
Similarly, we have
3 2
2
V
0 & 100R-33T
And to prove L > 1, we must check that
3 25o
1.
Given the sequence (0n))21, we call its element om breakpoint, if 0m < 3 and am < I The next lemma says that a small step can only occur shortly after a breakpoint. Lemma 9, If or
viz then exactly one of the following holds
ii 0 is a breakpoint;
(ii) ak-1 < Cr and a is a breakpoint.
Proof. In view of Lemma 6, the statement implies that ag + 1. Suppose that Q4-1 is not a breakpoint, since otherwise we are done. This means that either (a) ag-1 > 7, or (b) ak-1 1 and 0 > }.
In the first case we immediately get a contradiction, since ag =
02 0 106-1
3 V2T.'
Then if we consider (b), the bound 0--1 > implies that O--1 & as < /2T. Then we can apply the same arguments above, but to 0g---- This means that either 0 will be breakpoint we will have a chain 0z-2 & 04-1 < O& VEL However, the latter option cannot occur, because
using f--1 > and 0i- 7 V3L ensure us that
2 V3
2 13
V5
0
0 0k-10
+1
V3L
3L
V2L'
15

---

Although a breakpoint indicates that we are in the region with a small stepsize, Lemma 8 guarantees that previous steps were quite large. The next lemma shows that in total we make significant progress. Lemma 10. If Omm is breakpoint, then Σ}= am+s
L
Proof. If Omm is a breakpoint, then on one hand Lemma 8 implies that am-1 On the other hand, we have that Om
Lm 0m 20m Combining, we get
L
3
V2r. am++1
3
v31.
and 0mm+2 V
amtj و 3 + v +
V2 +
> 5.59.
v3
Lemma 11. If og satisfies (16), then for any k > 1 we have
k
(33)
V2L
Proof. Let M = -Im a breakpoint: 0m++1
V2L J.
We can split Σx= 0g into two terms as
Σ a.= Σ
am+j + rest.
(34)
mEM j=-2
1. Indeed, if a, < V2T. is in the We claim that elements in the "rest" are greater or equal than V2r.
"rest" term, then either a;-1 is breakpoint or a;-1 < V2L and a,-2 2 is a breakpoint, as Lemma suggests. In either case, must be included in the first sum, by the definition of M..
Now let us estimate both terms. The first sum in (34) is greater than SIM
L
3|MI
V2L by Lemma 10.
The total sum in the "rest" term is not less than k- M Hence, the desired inequality follows. It has
/2l.
be only noted that if 1: E M, we have additionally consider the sum Σ 0k-1+ > VEL for which the bound follows from the same arguments as in Lemma 10.
Remark It is obvious that our analysis was not optimal. For instance, whenever 0g + 2, we could 2_ Similarly, we got much better bound for every breakpoint. However, did not want overcomplicate already tedious examination. We leave it as open question if one provide bound closer A. (or better?) with readable proof.
use 0--- 1 a% > & instead of more conservative '22,"
C Adaptive proximal gradient method
Recall that the second bound for the stepsize is equivalent to
1
1
(35)
20
2
We can rewrite k+1 prox. (a* - a& V (x*))) as an implicit equation
A+1 x² -
au (V (l(x))))),
(36)
where () is a certain subgradient of g at ++1 that is Vg(x e 0g(x++1), For this particular subgradient we will also use the notation
vマ(=*) = VF(**) + (z(xt).
First, we adapt our basic inequality (10) to the more general case. By prox- prox-inequality, we have
k * + ag (**x), x+| > an (g(2x++1)) g(x)), Vr.
(37)
16

---

Then we set = x= above and transform it into
|| x²12 2ax.la(a*t)) - g(x"(()))))))))")))) & 1|2 - x²11++ 2ax (Vf(x"), - shtl) - -1x
# $12
(38)
This standard inequality is at the heart of the analysis of the proximal gradient method. To complete the full proof, or rather to get the final inequality, the classical analysis only requires applying one convexity inequality and one descent lemma to function f. Our analysis, however, will be different.
The main nuisance is that in the k-th iteration the proximal map yields us g(x*11)- g(x*) term, while our adaptivity approach works with f(x²) - f(z"), ) as we remember from before. Thus. our first obstacle to understand how to combine these two terms.
First, we estimate the term
(V xx - xktl) in the RHS of (38). We have (V](x"), x- x ) (VI(a*), x² - x²h) (VS(x*), - -
= (VI(a=), -xa) + (VS(x*) + Vg((a"), x* - I 2b + (Vg(=*) (((a=)),",r)) ), xt))
< f(x)) f(x*) (V Vg(x*), x² xttt) g(aktl) g(x*),
where in the last inequality used separately convexity of / and g. Applying this inequality in (38) yields
| x²12 + 2ax -
< 1| - - 2a (x((")) + gg(z))) x² shtt - 1| 10++1=x+0 111
< 11 x-=''" 12 a ( + {)
(39)
As see, the final inequality is very much in the spirit of (10).
Lemma 12 (Compare to Lemma 1). For iterates (x*) with arbitrary stepsizes, it holds
(V)(**) + Vg(a*), Vf(a Vg(a²)) < (V + {g(at))
(40)
Proof. As before, this is just monotonicity of V in disguise:
IV + - (V + g vf(a"-1) Fg(z²1)
Vz(=²) -V
Vg(z*))
f x k 2²) > 0.
= ak-1
The next lemma is special for the composite case. Although it looks like this fact should be known in the literature, we were not able to identify it.
Lemma 13. For iterates (I*) of the proximal gradient method with arbitrary stepsizes, it holds
ff((*)) + (g( & [[ + (a(a")
(41)
Proof. This time it is just monotonicity of 0g in disguise:
[[V](**) {2 (*** + (g(x + Vo(a*)- - (2(a
= + vo(x))- Eo(24t1)) /
a4
|
x
111 + (at kt1 &z(a*t) (g(u)t))) + (/Vo(tt)- (agaa)--aaatttt -
0%
1
| I
211
+ a6
(1r k+1 Fg(x*t (g(e+t11)
>
(***)) + Vg(z \1)2+
where the last inequality follows from monotonicity of dg and (36).
17

---

In Section 3 we estimated || - 1² = vf This time, || - x²12 and
a (() are different and it is the latter term that matters to us.
Lemma 14 (Compare to Lemma 4). For iterates (a**) ) of Algorithm 3 it holds
0 / + 2 -F((((((=)))) -F(x)))
2
Proof. The main idea of the proof is exactly the same as in Lemma 4. However, the presence of Vg((²) make it slightly more cumbersome. The previous two lemmata are instrumental on our way. We have
V ( a Vf
V + (o(21))
20 [V)(2) + Vg(a")) V
1) + Vg(l"1)
a
2 a
=a.
x² 11
| f (z + マg(
=
20 2
2
+ 22 [(
+ Vg(x*)
V + {g(l"))
3a
< a
L3 20
1 1-
Vf(x') + Ag(TTt) V + g)
2
(35860)
3
11 x
1/ + a2 (VS(x*) +
2
(36)
V A 11 )) + 6 か) 2|
+ 2
On (F ), k-1 - xt)
2
(41)
3
F +
aa Ox FF((tt xd-1 - x²)).
2
2
Convexity of F completes the proof.
Lemma 15 (Compare to Lemma 5). For iterates (o**) of Algorithm 3 and any solution x it holds
l+ xx 11 + at / || an + 30p 30x))(PP))))) (F F.)
< 11a* - x= + oz (. || + 3z ((**-1) - F.).
(42)
Proof. The same as in Lemma 5.
Recall that we define R as
R² = 1200 21112 + 22 22 (o(F(z)) -(f=))=F.).. F.).
(43)
Lemma 16. The sequence (x**) is bounded. In particular, for any solution x" of (20) we have xk E B(x",R).
Proof. The same as in Lemma 2. We use (42) to telescope until k: 1 and then apply (39) with 0 to bound ||' - 11.
Proof of Theorem 3. The proof of inequalities (22) and (23) is almost identical to the one in Theo- rem 2. The proof of convergence of (a*) to a solution is, however, more nuanced. The nontrivial part to show that all limit points of (a*) are solutions. While on the surface, should be no harder than before, the fact that ling->+oc Og can be too complicates things bit.
Let x= be solution of (20). By I-smoothness of f over B(x", R), we have
1
f(x*) f( > (Vf(="), - x*) +
ff((tt) vf(z")]1
V
2L
Using this improved bound, similarly how it was done in (32), we get
|aa x 2²1| + ( on 30w)(F(**) F.) ak
vf(x")11 2
< I1a* - -x'1x11--
+ 0 21
VF (2 || ( - F.).
(44)
18

---

By telescoping this inequality as before, we can now additionally infer that
ax a<IlV/(**) VV((=)) < +o0
(45)
and thus, - -V(x=)I -
O. Specifically, this implies Vʃ(x*) vs(x=11) - 0 as h: co.
We want to prove that all limit points of (x*) are solutions. To this end, we will use prox vrox-ineuuality (37) rewritten as
(u R+1 x², 2 x² , (VI(x*), rht1) > gga - g(x), Vx
(46)
ag
which in turn, by convexity of f, leads to
- - ) + (VS(=*)
7 F(x - F(x)).
(47)
O
The left-hand side has two terms, and the second term evidently tends to 0 as - If we can show the same for the first term, it will imply that all limit points of (x are solutions.
Consider (46) again, but this time we set z = x². This yields
| - 1²11 + (V (VS(""), - 1 2 -
O
We manipulate the inequality above as follows
||o
1² & (Vf(="), x - , + g(x*) - g(x
- Intl) + (Vf(x") ,, - xbtl) + g(x g(
5n
1at x 112 + 8n.
2
20
where in the last inequality we applied Cauchy-Schwarz Schwarz and Young's inequalities. From this we deduce that
| 1²1 au anllVS(<*)) vf(x*)11 20,.
OAk
Note that the sequence (ax | ff(x*) - f=x))]] is summable by (45). Also, the sequence (6x) is summable, since (x*) bounded and g(x*) is lower-bounded: g(x*) > F. f(xx) > -c for all
k. Hence, Σx 1 || 112 +oo and, thus, 1 | x* - 0 as k +00. Given that
ouk (ax) is separated from zero, it immediately follows that || - -=11 - as well.
Therefore, we have proved that all limit points of (a*) are solutions. The proof of convergence of the whole sequence (x**) runs as before in Theorem 2.
Remark 6. We didn't derive a linear convergence of the adaptive proximal gradient, when F is strongly convex. We only mention that it is quite straightforward and goes along the same lines as the original AdGD in [MM20, Theorem 2] in the strongly convex regime.
D Additional experiments
Low-rank matrix completion. form
We consider a famous low-rank matrix completion problem in the
1 min 2 | - A) subject to X
||
< r,
(48)
where Q is subset of indices (i,j) and r is the supposed maximum rank. To project onto the spectral ball C = {X: || & r). computing the singular value decomposition (SVD) is required, making it the most computationally expensive operation in this setting.
We created matrix A by multiplying matrices U and VT, where U and V are n-by-r matrices with entries sampled from a normal distribution. The subset was randomly chosen as a fraction of f entries from [n]] (w). The obtained results are depicted in Figure 2, where we solely compared the number of computed SVDs. For two scenarios we generated, the proposed method was always faster than any of the linesearch versions.
19

---

AdProxGD
(1.2, 0.5)
(1.5,0.8
(1.1.
(1.2, 0.9)
(1.1. 0.9)
(1.5, 0.5)
(1.2, 0.8)
(1.1, 0.8)
(1.5, 0.9)
10
objective
169
10
10
10
200
300
10x100
2.0x10
3.0x16'
# SVD
SVD
(a) 100, 20
(b) 200, r 20
Figure 2: Low-rank matrix completion, problem (48)
subject to linear constraints. We consider [BV04, Ex- ample 10.4], where we want to minimize the length of a piecewise-linear curve passing through points in R with coordinates (1, .... (n, Fxd) while satisfying linear constraints Ar where (Z),..., Given A E Rm and E IR, this can be modeled as
Minimal length piecewise-lineat
min (1 2 E (#:11- - 2;)33//a subject to
Az = b.
(49)
While applying the proximal gradient method, the most computationally expensive operation is computing the projection onto C {x: Ax = b). Assuming that A full rank with m & n, this b).
projection can be computed as Pez = ATAATT)--
In comparison, we focused solely on the number of computed projections. We generated a random m-by-n matrix and random vector w with entries sampled from normal distribution and b = Aw. In Figure 3, we can see again that the proposed method converged faster than any of the linesearch versions.
AdProxGD
(1.2, 0.5)
(1.5, 0.8)
(1.1, 0.S) (1.1, 0.8)
(1.2, 0.9)
(1.1, 0.9)
(1.5, 0.5)
(1.2, 0.8)
(1.5, 0.9)
10
objective
10
10
10 10
10
100
200
300
400
500
500
1000
1500
2000
# projections
# projections
(a) m = 50, n
200
(b) m 50, n 500
Figure 3: Minimal length piecewise- linear curve, problem (49)
We want to solve the matrix factorization problem subject to Nonnegative matrix factorization. nonnegative constraints:
min f(U = U.VR
2 LUV -1
(50)
where given n-by-n low-rank matrix. Although nonconvex, this problem is famously well- tackled by first-order methods. In each iteration, the gradient V fxx) involves 3 matrix-matrix
20

---

multiplications, whereas evaluating the objective fx) only requires 1. Note that for the last iteration of the linesearch, the computed matrix product can be reused compute the gradient for the next iteration.
We created matrix A by multiplying matrices B and CT, where B and C are n-by-r matrices with entries sampled from a normal distribution. Negative entries in both matrices B and C' were then set zero, The results are presented in Figure 4, where the number of gradients roughly means the number of 3 matrix-matrix multiplications, In both cases we generated, the proposed method converged faster than any of the linesearch versions.
AdProxGD
(1.2, 0.5)
(1.5, 0.8)
(1.1, 0.S) (1.1, 0.8)
(1.2, 0.9)
(1.1, 0.9)
(1.5, 0.5)
(1.2, 0.8)
(1.5, 0.9)
10"
objective
16
10 10
10
1000
2000
3000
1000
2000
3000
4000
5000
6000
# gTadients
gradients
(a) 100,
20
(b) 100, r 30
Figure 4: Nonnegative matrix factorization, problem (50)
Dual of the entropy maximization problem. to linear constraints
Consider the entropy maximization problem subject
Ty log 24 subject to Ar b. Σ 24 and xj >>
(51)
where A IRxx _ Its dual problem is given by
min XER JER
+ (b, 4.,
(52)
where a; E R" is the i-th column of A (the derivation is provided in [BV04, Chapter 5.1.6)).
AdProxGD
(1.2, 0.5)
(1.5, 0.8)
(1.1, 0.5)
(1.2, 0.9)
(1.1, 0.9)
(1.5, 0.5)
(1.2, 0.8)
(1.1, 0.8)
(1.5, 0.9)
10
16
objective
10
10
10-10 10
10
2000
4000
6000
20
40
60
80
# gradients
# gradients
(a) m 500, n = 100
(b) m 100, m 500
Figure 5: Dual of the entropy maximization, problem (52)
the latter problem (52) that we solved. generated m-by-n matrix A with entries sampled from normal distribution. Then generated random E R. from the unit simplex and set
21

---

b= Aw. Each gradient requires two -eector multiplications, while the objective evaluation requires only one (and, as before, the last one can be reused for the next gradient). The results are presented in Figure 5, where the number of gradients roughly means the number of 2 matrix-vecton multiplications. In the first scenario, the proposed method is faster than all the linesearch versions, while in the second one, only one version of linesearch was comparable in performance.
Conclusion. Based on our preliminary experiments, evident that AdProxGD indeed performs better. To our surprise, a few specific pairs (r, consistently outperform the rest among ProxGD with linesearch. We are not aware of any theoretical finding that would confirm this evidence. Also, from numerical point of view, the linesearch implementation is not always robust. In particular, when we are already close to solution, the linesearch condition can sometimes fail because the numbers it operates on all very small.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction describes our contributions in details.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations in the Literature and Discussion section, as well as in other various parts of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
Each statement has proof either in the main text or in Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe in details how a random data was generated for the experiments. The code is publicly available.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [Yes]
Justification:
The code is publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. wwtppblicgguiiiiccccccceecoopppe htteg/uuuddeeeduubbeeeeeeeeeeeee /at////ooommsssseeeeee ssisssolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
is described details which parameters were used.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: There error bars for the experiments. The paper is mostly of theoretical interest.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
25

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification:
This is not important for our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: pettps:/nneure /ttp::///eeuu.eeeeeeee httppp/cccccptccccccccecccaaeeae csGuidel inne?
Answer: [Yes]
Justification: This is theoretical paper.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical work that does not have any foreseeable societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is theoretical paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: All experiments were randomly generated.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
27

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not contain a study involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not contain a study involving human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "EERqgmhiZB", "reviewer": "Reviewer_GkbV", "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.", "questions": "1. What about the result by using stochastic gradient?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n\nThe 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. \n2. In the second experiment, the first term in problem may be (1+x_1^2 )^(1/2), rather than (1+x_1 )^(1/2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive evaluation of our work!\n\n1. Indeed, the theory won't be applicable in the nonconvex case. Convexity was instrumental in deriving all the proofs, and in the weakly convex case it is not clear how to proceed. However, we don't agree that this is a weakness. First of all, convex problems arise as subproblems in many applications such as bilevel optimization and optimal control, and black-box methods are of particular interest in such cases. Secondly, many optimization methods such as momentum and Nesterov's acceleration have been designed using the convex framework and have been used across problem classes.\n\n   Moreover, we do not believe it is possible to achieve same adaptivity as in our method in the general nonconvex case. While we cannot prove this definitively, there are no works, at least to our knowledge, that demonstrate adaptivity (as defined in the paper) in the general nonconvex case with a sound theory and convergence rate. Thus, we believe it is unjust to criticize the paper for not achieving something that is currently beyond reach for all.\n\n\n2. Thank you for noticing the typo!\n\n\n3. Unfortunately, it is again unclear how to develop a sound theory in the stochastic case, the theory is lacking even for linesearch methods. The difficulty comes from the fact that convergence guarantee for SGD usually require the stepsize to either use the Lipschitz constant of the full gradient or the maximum over all Lipschitz constants across all stochastic samples. Empirical stochastic gradients would only give a rough estimate of these quantities, so it is not immediate how we could get solid convergence guarantees for such methods. However, we believe it is a very intriguing and interesting direction for future research and we hope that adaptive methods will be extended to this setting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "akedSl0NzV", "reviewer": "Reviewer_5AVv", "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. \nAs 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.\nThe authors compare their algorithm with others in the literature in Section 5, including detailing possible extensions, and why they might prove tricky. \nFinally, numerical experiments are presented in Section 6 (with proofs and further experiments in the appendix).", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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).\nI 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).\nContribution. 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. \n\nIn Lemma 1 I think it should be mentioned that $\\alpha_k>0$ (i.e., the step size can be 'arbitrary but positive').\n\nNumerical 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive evaluation of our work and the high praise! We are especially pleased that you liked the way the paper is written; we put a lot of effort into making it readable and enjoyable.\n\nWe agree with tightening the statements and will make the necessary changes in the revision.\n\nThe same goes for Lemma 1.\n\nRegarding the descriptions of the experiments, we were limited by space. If the paper is accepted, we will make sure to add more details.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QuS6hOI1Tf", "reviewer": "Reviewer_Wsqq", "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.", "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.\n- line 191, \"note that the second bound...\" : please note this is the \"second bound in step 5 of Alg. 2\".\n- eqn 15 : In this inequality, should $\\alpha_k$ and $\\alpha_{k-1}$ be interchanged? In that case, the following interpretation is also not correct.\n- 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?\n- 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.\n- line 222, \"Algorithm 3, presented in Appendix C\" : Please include the algorithm as part of the main text.\n- 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.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\nAt times, I wished the authors would complete their arguments fully. I have a few comment below.\n\nThe 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive evaluation of our work!\n\n1. Indeed, we tried to explain our derivations as thoroughly as possible. As we mentioned, equation (13) is just a substitution of the previous equation into (10). We may have forgotten to clarify that $\\alpha^{2}_{k} \\|\\nabla f(x^{k})\\|^{2} = \\|x^{k+1} - x^{k}\\|^{2}$. We will make this clearer in the revision.\n   \n2. True, we will add this in the revision.\n   \n3. We believe eq. (15) is correct as it stands. It is derived directly by squaring the previous inequality and dividing both sides by $\\alpha^{2}_{k-1}$.\n \n4. We are not sure we fully understood the question. No single number can capture the global behavior of a function. In our case, $L_{1}$ is simply the first approximation of a local Lipschitz constant around $x^{1}$. Note that it serves as a lower bound for the global Lipschitz constant $L$, and this may be the only aspect it captures.\n   \n5. We beg to disagree here about the use of the short notation. We believe $\\mathrm{prox}$ enhances readability in the same way that the metric projection $P_{C}$ is much more convenient than writing $\\arg\\min_{x \\in C} \\| x-a \\|^{2}$ each time. However, we agree that it's better to include the definition you mentioned when we define the proximal operator in line 221.\n   \n6. Thanks for this comment! You cannot imagine how much time we spent trying to fit it into the main text, but it always pushed out something more important. If the paper is accepted, we will have an additional page, so it won't be a problem anymore.\n\n7. We think it is actually important to compare the algorithm with the most widely used and robust approach — linesearch. Choosing a reasonably accurate estimate of the local Lipschitz constant is easier said than done. For instance, it is far from trivial to determine what to choose in problem (24).\n\n   One of the main goals of this paper was to study composite optimization, where prox or projections matter. However, we conducted an extensive study for the unconstrained case already in [MM20]. Also, note that problems (50) and (52) in the Appendix do not consider projections and only compare gradients.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aP9Tsk6Cj7", "reviewer": "Reviewer_NQsh", "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.", "questions": "5. See weaknesses.\n6. 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.)\n\nOverall, 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.\n\nTypos: line 54 - some some, line 272 - experimentswe.", "limitations": "Discussed in weaknesses.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper unfolds by providing intuition and examples, helping the readers to deepen their understanding beyond the technical results.\n2. 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]?\n4. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. The improvements over [MM20] are multiple:\n\n   (i) We allow for larger steps, leading to improved final complexity. While a direct comparison is missing due to the less explicit final bound in [MM20], we have strived to make our bounds as explicit as possible in this work.\n\n   (ii) We have gained a better understanding of the proposed algorithm and the reasons behind the complex structure of the stepsize (Theorem 1).\n\n   (iii) We have extended this improved analysis to the proximal case, which is a non-trivial task compared to the setting with a fixed stepsize.\n\n2. In our work, we haven't conducted experiments in the stochastic case. In [MM20], there wasn't a strong theory for the stochastic case, so a variation of the algorithm proposed in [MM20] was tested with additional hyperparameters. These hyperparameters cover a family of algorithms, including the newly proposed one (though [MM20]'s theory didn't support it). So the method we proposed here was already tested in unconstrained stochastic case by [MM20], and by repeating these experiments we wouldn't gain new insights. Additionally, the constrained case for neural networks is very uncommon and not particularly interesting.\n\n   We hope that our response addresses your concern and we would greatly appreciate it if you revisited the score given to our work. As it currently stands, it is unclear to us why you voted for the rejection of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: After the rebuttal, all reviewers recommended acceptance.
Decision: Accept (poster)