Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent

Dear Reviewer,

Thank you for taking the time to review our work!

How does the local curvature assumption differ from or extend relative smoothness?

Other works such as [1] propose the notion of relative smoothness based on the Bregmann divergence of some arbitrary strictly convex and continuously differentiable kernel function $h$. The motivation for our assumption is to leverage local curvature information to develop adaptive algorithms with matrix-valued step sizes without going the route of fully-fledged second-order methods. Hence, we focus on deriving and analyzing algorithms that utilize a local curvature matrix.

Specifically, we believe that relative smoothness does not fully capture our assumption. The variable nature of the norm does not allow for the term $\frac{1}{2}||x-y||^2_{C(y) + LI}$ in our assumption to be expressed as the Bregman divergence of some kernel function. For example, taking the Euclidean kernel $h(x) = \frac{1}{2}||x||^2_2$ recovers the classical $L$-smoothness assumption,

$$f(x) \leq f(x) + \left<\nabla f(y),x-y \right> + \frac{L}{2}||x-y||^2_2.$$

Let's say we want the norm to be induced by a matrix that can vary with $y$ because our assumption is of the following form,

$$f(x) \leq f(x) + \left<\nabla f(y),x-y \right> + \frac{1}{2}||x-y||^2_{C(y) + LI}.$$

In this case, a simple kernel function is not immediate. If we try to use $h(x) = ||x||^2_{C(x)}$, the expression for $D_h(x,y)$ does not simplify to $\frac{1}{2}||x-y||^2_{C(y)}$. In fact, we need to differentiate through $C(x)$ to calculate the Bregman divergence so the expression for $D_h(x,y)$ quickly becomes much more complicated than the terms in our assumption.

Furthermore, we would like to emphasize that Assumption 2.1 in our work introduces both an upper bound and lower bound on $f$. Of course, the relative smoothness assumption pertains to the upper bound on $f$.

Do the convergence guarantees for LCD1 and LCD2 improve upon what could be derived using relative smoothness?

Our assumptions and algorithms are not covered by the relative smoothness framework due to the variable nature of the norm. Thus a direct comparison cannot be made. However, works such as [1] derive an $O(1/k)$ rate for the Bregman Gradient algorithm. The Bregman Gradient algorithm which is derived from the relative smoothness assumption is analogous to LCD1 which is derived from the upper bound in Assumption 2.1. LCD1 also achieves an $O(1/k)$ rate.

Are there problem settings where the local curvature approach provides benefits over relative smoothness?

The analysis of LCD1 and LCD2 leads to better constants compared to their classical counterparts. Also, GD with Polyak step and GD with step size $\frac{1}{L}$ have the same theoretical convergence rate. However, there is a great benefit in using the Polyak step size because it converges much faster empirically. The same reasoning applies to LCD2, an extension of the Polyak step size. Although LCD2 has the same theoretical rate as GD (up to constants), by utilizing local curvature information and adaptive step size, LCD2 exhibits superior empirical performance compared to both Polyak step size and constant step GD.

For machine learning problems, diagonal curvature matrices may be available as demonstrated by our examples. This results in computationally cheap update steps for our algorithms and improved empirical performance shown by our experiments. The performance of algorithms derived from relative smoothness would depend on the kernel function that is used in the algorithm. Certain kernel functions may result in updated steps that cannot be computed efficiently in practice.

[1] Bregman First Order Methods: https://arxiv.org/pdf/1911.08510

Dear Reviewer,

Thank you for the time spent analyzing the content of our work!

The setting is very limited, namely, convex optimization problems for which the scaling matrix C(y) is known and available.

We understand the reviewer's concern but politely disagree. The new assumptions are weaker than well-studied strong convexity and smoothness. Also, we show a few interesting examples satisfying our assumptions, which are not strongly convex or smooth. Interestingly, our assumptions recover convexity and smoothness, another important set-up in optimization, as a special case.

It is claimed that Assumption 2.1 defines a new class of functions, but that is not true. These ideas are all related to notions of generalized convexity and generalized distance functions.

Other works such as [1-3] that have examined assumptions like relative convexity and relative smoothness have limitations that are addressed in our work. For example, [1] only considers fixed positive definite matrices $M$ and $G$ to define a smoothness and convexity assumption:

For all $x, y \in \mathbb{R}^d$,

$

$

f(x) \leq f(x) + \left<\nabla f(y),x-y \right> + \frac{1}{2}||x-y||_{M}

$

$

$f(x+h) \geq f(x) + \left<\nabla f(y),x-y \right> + \frac{1}{2}||x-y||_{G}$

In our assumption, the curvature matrix is allowed to vary with $y$ which makes it much more flexible. A simple example of a function that satisfies Assumption 2.1 but not this assumption is the square of the Huber loss.

Our assumption is more general than the relative smoothness/convexity assumption proposed in [2]. They only consider Hessian matrices $H(x) = \nabla^2 f(x)$. Our goal is to develop adaptive matrix-valued step sizes without going the route of fully-fledged second-order methods. Assumption 2.1 does not restrict that the matrix must be the Hessian. This gives us the flexibility to use some local curvature information when it is available to design powerful adaptive step sizes.

In response to Reviewer inYC, we address the relationship between Assumption 2.1 and relative smoothness using Bregmann divergence in detail. To summarize, the variable nature of the norm in our assumption does not allow it to be expressed using the Bregmann divergence of some kernel function.

If we restricted to fixed matrices $M$ and $G$ then we can use $h_1(x) = \frac{1}{2}||x||^2_M$ and $h_2(x) = \frac{1}{2}||x||_{G}^2$ as kernel functions to derive the assumption in [1]. Of course, as we mentioned this assumption is more restrictive than Assumption 2.1. The variable nature of the matrix norm captures local curvature information which is crucial to our algorithms and separates our assumption from relative smoothness/convexity.

Prior to equation (22), what is Step 3 of LCD2? There does not appear to be a "step 3"? This seems to follow easily from the projection theorem onto closed and convex sets.

Apologies for the confusion. This does follow from the projection theorem. The "Step 3" part is a typo. It is meant to refer to the projection onto the localization set. We have fixed this in an updated version.

[1] SDNA: https://arxiv.org/pdf/1502.02268

[2] Randomized Sub-space Newton: https://arxiv.org/pdf/1905.10874

[3] Bregman First Order Methods: https://arxiv.org/pdf/1911.08510

Dear Reviewer,

Thank you for taking the time to engage with out work!

The assumption could still have been justified with examples of interesting functions that satisfy assumption 2.1 in non-trivial ways. Unfortunately, that does not seem to be the case

Our class of functions includes any strongly-convex function (a common assumption in optimization) as a special case when $\mathbf{C}(x) = \mu \mathbf{I}$. We provide additional examples of functions that are not strongly-convex but satisfy our assumption with a non-trivial $\mathbf{C}(x)$ curvature matrix including the square of absolutely convex functions. Therefore, many functions relevant to optimization are included in this new class.

None of our examples have a curvature matrix that is equal to the Hessian (other than convex quadratics). Of course, the curvature matrices are related to the Hessian but that is not surprising since they represent some local curvature information and $C(x) \preceq \nabla^2f(x)$.

The experiments are also only performed on these trivial examples and authors compare their proposed step sizes only against Polyak step size.

Experiments are tailored to the assumptions we consider. Our goal is to build a deep understanding of this setup before entering stochastic or non-convex regions

Can the authors comment on the second order characterization of assumption 2.1?

We would like to clarify that Assumption 2.1 is not equivalent to

$

$

C(x) \preceq \nabla^2f(x) \preceq C(x) + LI.

$

$

Only one direction is true. If Assumption 2.1 is satisfied then this characterization is true. The other direction does not work. For example, of course, $\nabla^2 f(x) \preceq \nabla^2f(x) \preceq \nabla^2 f(x) + LI$. But setting $C = \nabla^2 f(x)$ does not work for many examples. For instance, consider the square of the Huber loss with the curvature matrix as the Hessian. Then the lower bound fails for $x = 0$ and $y = 0.5$.

What is the time complexity of LCD2 compared to Polyak step size? Specifically, how does the computation of affect the complexity?

We can use Newton's root-finding method to compute $\beta_k$. The main cost is computing the eigendecomposition of $C(x_k)$ at the beginning of each iteration of LCD2. This has complexity $O(n^3)$ but in practice it is faster than computing the inverse. Of course, when $C(x_k)$ is a diagonal matrix we don't need to compute the eigendecomposition. We can take a few steps of Newton's method for a good approximation of $B_k$. Empirically, we observed that LCD2 converged faster than Polyak even for wall-clock time.

Dear Reviewer,

Thank you for taking the time to review our work!

Is there any relation between convex and smooth local curvature functions with functions defined by Bregman divergence? If yes, is there a connection between Mirror Descent and LCD1?

In response to Reviewer inYC, we address the relationship between Assumption 2.1 and relative smoothness using Bregman divergence in detail. To summarize, the variable nature of the norm in our assumption does not allow it to be expressed using the Bregman divergence of some kernel function.

GD with Polyak stepsizes also converge for the problem (1) under the proposed assumption, as well as the normalized gradient method, however, with a slower convergence rate. It would be beneficial to add a comparison of existing methods not only in experiments but also in the main section.

Our results include that GD with Polyak step size converges at an $O(1/k)$ rate which is the same rate obtained by LCD1 and LCD2. Empirically, we found that LCD2 and LCD3 have superior performance compared to GD with Polyak step size.

How the choice of C(x) in experiments affect the performance if the methods?

Intuitively, we found that when $C(x)$ "represents" more information about the optimization problem, the better the LCD methods perform. For example, in experiments where the $C(x)$ matrix is derived from the regularization term, LCD2 performs better than Polyak as the regularization weight $\lambda$ increases. Of course, we found that using the $C(x)$ which results in a tighter bound performs better.

In the first experiment with regularization, GD also can be used; it would be interesting to see if LCD1 outperforms GD.

In the plots for this experiment, we did not include GD because it performed worse than LCD1 and made no progress.

Thank you for finding the typos. We have fixed those in an updated version.