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,
$$
f(x_{k+1}) \leq f(x_k) - \frac{\eta_k}{2} \\|\nabla f(x_k)\\|_2^2.
$$
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.