Dear Reviewer,

Thank you for your time and review. We were pleased to see that you thought our "tighter, adaptive guarantees are appealing due to the observed success beyond the theoretical convergence bounds" and that "the technique naturally yields results for several existing methods."

We understand you currently do not appreciate Theorem 4.4, but our paper has many other results (a total of 11 Lemmas, propositions and Theorems). Does the reviewer appreciate or have questions regarding any other specific part of our paper?

1. The paper discusses only deterministic optimization. Can the framework be used for stochastic optimization?

We agree that developing stochastic results is desirable and we are confident that our framework is useful for stochastic optimization. For instance, directional smoothness has already been used (e.g. in [2]) to explore empirical properties of stochastic algorithms. However, we must leave exploring this in detail to future work.

Since directional smoothness is a new concept, we need the space in this paper to carefully characterize classes of functions which have a meaningful directional smoothness function, and to show how this is a useful concept for the optimization. This is consistent with the literature, where optimization concepts are often studied in the deterministic setting before being extended to stochastic optimization. For example, you have linked papers [4, 5] on the Polyak step-sizes; [5] only consider the deterministic setting and it took several years after its publication for [4] to study the stochastic setting.

2. The novelty of the approach is unclear for some of the observed results.

The novelty of our approach is proposing a new directional smoothness assumption, showing that this assumption holds for differentiable functions, and then showing how directional smoothness function can be used to precisely characterize the convergence of first order methods.

3. Theorem 4.4 ... the simple adaptive result is only framed for convenience in the directional smoothness framework.

Theorem 4.4 says that for any directional smoothness function $M$, the sub-optimality bound $\frac{D^2}{\sum_{k=0}^{t-1} M(x_{k+1}, x_k)^{-1}}$ holds, where $D=\|x_0-x_{\ast}\|$. The point of this theorem is to show that Polyak's method has a certain universality: whatever directional smoothness function $M$ exists, Polyak's algorithm adapts to it. The proof the reviewer gives does not show this, and while useful for establishing a convergence bound, doesn't indicate a universality property. Indeed, many algorithms achieve rates that look like $\frac{D^2}{\sum_{k=0}^{t-1} \eta_{k}}$, e.g. GD with any step-size sequence $\eta_{k} \leq \frac{1}{L}$ achieves this rate. What sets our theorem apart is that it shows the Polyak step-sizes possess an adaptivity that GD with a non-adaptive step-size sequence does not.

However, we will also add a remark showing how to conclude the proof by keeping the Polyak step-size (i.e. without replacing it by directional smoothness). This observation gives us new insights into the Polyak step-size, showing that the Polyak step-size itself is a type of directional smoothness, and can be used to form a smoothness upper-bound such as Eq (1).

4. It is arguably known that the standard analysis technique of GD exploits smoothness only between consecutive points.

This is exactly what our work shows explicitly. Though intuitively GD is a local method, and should depend on local notations of smoothness, we found that there is no satisfying prior definition and theory that captures this local behaviour. Unless the reviewer has a reference in mind that they could share?

We also note that tight proofs for the convergence of GD for non-strongly convex functions (e.g. [3; Theorem 3.3]) actually do rely on smoothness everywhere rather than just between iterates. This is because they use an inequality sometimes called co-coercivity, [3; Lemma 3.5] which requires global smoothness. Moreover, the existence of an extensive literature on local Lipschitz continuity shows that relaxing global smoothness assumptions is not straightforward in general.

5. What is the main difficulty when we replace global smoothness with an adaptive variant?

Firstly, discovering the correct definitions of local/adaptive variants of smoothness is not straightforward. Secondly, verifying conditions under which these variants yield directional smoothness bounds and proving bounds like Prop. 3.1, which allow for steps to increase the optimality gap, both require developing non-standard proof techniques. The fact that these results seem obvious in hindsight is a testament to the fact that we "got it right" compared to the many other relaxations of smoothness which have been proposed.

The main technical difficulty is that the directional smoothness depends on the step-size. The standard analysis of GD starts with smoothness as $f(x_{k+1}) \leq f(x_k) + \langle \nabla f(x_k), x_{k+1} - x_k \rangle + \frac{L}{2} \\| x_{k+1} - x_k \\|^2 = f(x_k) - \eta_{k} (1 - \frac{\eta_k L}{2}) \\| \nabla f(x_k) \\| ^2,$ from which we obtain convergence of the gradient norm when $\eta_k < \frac{2}{L}$. When we replace $L$ by a directional smoothness $M$ instead, we get the requirement $\eta_{k} < \frac{2}{M(x_{k+1}, x_k)}$. Both sides of the equation depend on $\eta_{k}$, as $x_{k+1}$ depends on $\eta_k$. This implicit equation is not straightforward to solve and it's not obvious that a solution even exists. We prove that strongly adapted step-sizes do exist, derive new direct methods for computing such step-sizes (root-finding, exponential search), and establish novel connections to normalized GD and the Polyak step-size. Again, we believe the fact that these results are clean and easy-to-follow in hindsight is a strength of our work, not a weakness.

1. Many of the results until Section 4.2 are direct consequences of the (directional) descent inequality.

The reviewer has listed this as one of the weakness of our paper, but we would argue that this is a strength. It is this clear link between the definition of directional smoothness, the descent property, and the convergence rates that makes directional smoothness such an interesting definition. We were very surprised to see that such a natural definition had not been explored before.

2. Stochastic setting or different algorithms (such as Nesterov AGD) could give a more wholistic picture of the approach.

We agree that having the stochastic setting would strengthen the paper. But since directional smoothness is a new concept, we decided on carefully analysing the deterministic setting first, and leaving the stochastic setting for future work.

As for analysing more algorithms, again we agree more would always strengthen the paper. Yet, we already analyse four different settings of GD with a constant step size, exponential line search, normalized gradient and Polyak step-size. These four settings already justify the utility of our new definition and also leave no additional room within a 9 page paper.

3. In the proof of Proposition 3.2, why does the last inequality (above line 438) hold?

It looks like this is a minor bug. However, it's immediately corrected by upper-bounding as $(1 - \mu_k \eta_k) \Delta_k \leq |1 - \mu_k \eta_k| \Delta_k,$ since $\Delta_k \geq 0$. This doesn't affect the meaning of the proof since we need $\eta_k \leq 1 / \mu_k$ for any hope of progress. Many thanks for pointing it out.

4. Theorem 4.3 is very unclear to me.

One iteration in this setting means one single gradient access. So to get $f(\hat{x}_T) - f(x^*) \leq \varepsilon$, we require $\widetilde{O}(\varepsilon^{-1})$ gradient accesses. The output of the algorithm $\hat{x}$ would come from running gradient descent one final time after line 5 in Algorithm 1-- we will clarify this and write the algorithm in full for the next version of the paper. Thank you for drawing it to our attention.

5. Why did the authors not plug in these step-sizes into the general results?

This is an excellent question. We would have preferred to proceed in this manner, but the Polyak step-size and the normalized GD step-size are not necessarily adapted to the directional smoothness. In other words, they are not descent methods. Instead, Polyak and normalized GD make progress by decreasing the distances $\Delta_k = \\|x_{k} = x^*\\|_2^2$. As a result, we require dedicated proofs which leverage the specific structure of each algorithm.

6. Can we reconstruct/improve results for other notions of smoothness using directional smoothness?

Thank you for raising this question relating to $(L_0,L_1)$--smoothness and point outing [2, Lemma A.3] and [3, Lemma 8]. Looking to Lemma A.3, though at face value it does fit our definition of directional smoothness with, $M(x_{k+1},x_k) : = (AL_0+B L_1 \\|\nabla f(x_k)\\|)/2,$ we see an issue that prevents us from applying our theory. The issue is related to the constants $A$, $L1$ and $B$ which actually depend on all iterations of the algorithm. This is because the result of Lemma A.3 holds under the assumption that $\\|x_k -x_{k+1}\\| \leq c/L_1,$ for all iterations $k$, and for fixed constants $c$ and $L_1$. In other words, we have that, $\max_k \\|x_k -x_{k+1}\\| \leq c/L_1,$ and $c/L_1$ depends on the entire trajectory of the underlying algorithm. Furthermore, the constants $A$ and $B$ depend on this constant $c$ since, $A = 1 + e^c -\frac{e^c-1}{c},$ and, $B =\frac{e^c-1}{c}.$ Consequently the quantity $(A L_0 + B L_1 \\|\nabla f(x_k)\\|)/2$ depends on all iterations, and thus doesn't fit our definition of directional smoothness. We will continue to consider possible connections, and write a comment about this in our updated draft.

7. Is there hope for any lower bound results that show strongly adapted stepsizes are indeed the best?

This is an interesting and subtle problem since showing meaningful lower-bounds requires a minimum of variation in the curvature of $f$. For example, if $f(x) = 0.5 \\|x - x^*\\|_2^2$, then the Polyak step-size is just $\eta_k = 1/2$ and there is no difference between Polyak and vanilla GD. This indicates that we may need to exclude "simple" problems like isotropic quadratics from the function class in order to prove that strongly adapted step-sizes lead to strictly improved rates. Since this is highly non-trivial, we leave it to future work.

8. Are there any difficulties extending the notion of directional smoothness to the typical nonconvex setting?

Please see the general response.

9. Typographical issues and inconsistencies:

Thanks for pointing these out. We will correct them for the camera ready deadline.

Additional References

[1] Hübler et al., Parameter-Agnostic Optimization under Relaxed Smoothness, AISTATS 2024

[2] Zhang et al., Improved Analysis of Clipping Algorithms for Non-convex Optimization, NeurIPS 2020

[3] Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, Makoto Yamada, Polyak Meets Parameter-free Clipped Gradient Descent, arXiv, May 2024

[4] Peter Richtárik, Simone Maria Giancola, Dymitr Lubczyk, Robin Yadav, Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent, arXiv, May 2024

Thank you for engaging with our response! Please let us know if the following answers address your concerns.

Does the result hinge on this weighted average?

Thank you for this relevant question. As we note in Line 228 and after Eq. 25, the weighted average of iterates using the (unknown) smoothness function is always lower-bounded (in $f$) by the best iterate, so we can replace $\bar x$ with $\text{argmin}_{k} f(x_k)$ without changing the guarantee. Thus, the best iterate is adaptive to any directional smoothness function without any knowledge of $M$. If we have access to function value evaluations, calculating the argmin is no more difficult than calculating the weighted average.

Applicability to other settings.

We understand your concerns. We can extend our results to Nesterov acceleration to obtain optimal rates which only depend on the directional smoothness. Nesterov [N18] shows that any gradient method making progress like,

can be generically accelerated using an estimating sequences argument. This condition is satisfied by gradient descent with step-sizes adapted to a directional smoothness function $M$. Thus, GD with adapted step-sizes can be accelerated to obtain optimal linear/sub-linear rates with a dependence on the maximum directional smoothness observed over the optimization trajectory. Such a result can only improve on the classical accelerated rate.

We will add a formal proof of this result to the paper.

We'd like to reiterate that it has not been established in prior work that adapted stepsizes exist, or that they can be found easily. While our provided counterexample means that in general non-convex optimization might not be amenable to an easy analysis, this does not rule out that it can be useful under extra assumptions (e.g. that the Hessian is locally Lipschitz, or with directional smoothness functions that can potentially depend on more than two points).

[N18] Nesterov, Yurii. Lectures on convex optimization. Vol. 137. Berlin: Springer, 2018.

Proof of Proposition 3.2

Thanks again for catching this issue.

$(L_0, L_1)$ smoothness and Lemma [1, Lemma 8]

Thank you for pointing us to this more modern result and reference. We now agree that indeed that $(L_0, L_1)$ smoothness is a valid directional smoothness function according to our definition. This is actually a very interesting observation, which has several consequences including expanding the applications of directional smoothness, and explaining recent work on $(L_0, L_1)$ smoothness and the Polyak step-size.

1. [Polyak step size and $(L_0, L_1)$ smoothness] During the NeurIPS deadline (May 2024), two works appeared online showing that the Polyak step-size can be analysed under $(L_0, L_1)$ smoothness [3], and a related local curvature condition [4]. In particular Theorem 4 in [4] establishes that if the objective $f(x)$ is convex, smooth and $(L_0, L_1)$ smooth, that GD with a Polyak step size converges at a $O(1/T)$ rate with favourable constants. But now that it is clear that $(L_0, L_1)$ smoothness is a directional smoothness, we can immediately improve up on Theorem 4 in [2] in two ways: (a) we now know that assuming L smoothness (in addition to $(L_0, L_1)$ smooth) is not needed, and (b) this $O(1/T)$ result holds not just for $(L_0, L_1)$ smoothness, but for every directional smoothness constants as we have shown in Theorem 4.4. We also believe this will have consequences on the related definition of local curvature and the results in [4]. In other words, directional smoothness is a generalization of $(L_0,L_1)$ smoothness that also guarantees convergence at the same rate.

2. [Non-convex path forward] Both [3] and [4] consider the non-convex setting and analyse variants of normalized gradient descent with momentum. Now that we know that $(L_0, L_1)$ smooth is a particular type of directional smoothness, we can consider generalizing their result to any type of directional smoothness function, thus giving us a clear way forward for the non-convex setting. To do this, we believe we will be able to leverage our Lemma D.4. Yet it is not immediately obvious how to do this, so we cannot promise any substantial result in this paper.

We sincerely thank the reviewer for bringing this up. We will include now an extended remark on this connection and consequences to [3] and [4]. We will also add an acknowledgement to Reviewer vUdK for pointing this out to us, and for a insightful review.

1. I wonder if there are any interesting applications for which their rates can be more explicit and show clear improvement over classical ones.

Yes, and we provide such an example in Section 4.1 for quadratics. In this example, instead of the convergence rate relying on the largest eigenvalue of the constant Hessian matrix, our results show that the convergence rate relies instead on Rayleigh coefficient with respect to the local gradient. This Rayleigh coefficient is smaller than the largest eigenvalue, unless the local gradient happens to be exactly the eigenvector associated to the largest eigenvalue.

2. Have the authors considered non-convex settings?

Please see the general response.

3. Connections to edge of stability and adaptivity.

There are close connections betweens directional smoothness, edge of stability, and the performance of adaptive gradient methods. Kwangjun et al. [1] propose an alternative definition of directional smoothness (which is closely related to our path-wise smoothness) and use this quantity to study the behavior of SGD in stable and unstable regimes. Similarly, Yan et al. [2] consider a directional sharpness measure. They provide experiments showing that directional sharpness is lower for adaptive methods like Adam than for gradient descent. We will add these references to the paper.