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

## Abstract

Abstract We contribute to the growing body of knowledge on more powerful and adaptive stepsizes for convex optimization, empowered by local curvature information . We do not go the route of fully-fledged second-order methods which require the expensive computation of the Hessian. Instead, our key observation is that, for some problems (e.g., when minimizing the sum of squares of absolutely convex functions), certain local curvature information is readily available, and can be used to obtain surprisingly powerful matrix-valued stepsizes, and meaningful theory. In particular, we develop three new methods— LCD1 , LCD2 and LCD3 —where the abbreviation stands for local curvature descent . While LCD1 generalizes gradient descent with fixed stepsize, LCD2 generalizes gradient descent with Polyak stepsize. Our methods enhance these classical gradient descent baselines with local curvature information, and our theory recovers the known rates in the special case when no curvature information is used. Our last method, LCD3 , is a variable-metric version of LCD2 ; this feature leads to a closed-form expression for the iterates. Our empirical results are encouraging, and show that the local curvature descent improves upon gradient descent.

### 1 Introduction

In this work we revisit the standard optimization problem

$$ $\min\limits_{x\in\mathbb{R}^{d}}\;f(x),$ (1) $$

where $f:\mathbb{R}^{d}\to\mathbb{R}$ is a continuous convex function with a nonempty set of minimizers $\mathcal{X}_{\star}$. Further, we denote the optimal function value by $f_{\star}:=f(x_{\star})$, where $x_{\star}\in\mathcal{X}_{\star}$.

#### 1.1 First-order methods

First-order methods of the Gradient Descent (GD) and Stochastic Gradient Descent (SGD) variety have been widely adopted to solve problems of type (1) (Polyak, ; Robbins and Monro, ). Due to their simplicity and relatively low computational cost, these methods have seen great success across many machine learning applications, and beyond. Nonetheless, GD, performing iterations of the form

$$ $x_{k+1}=x_{k}-\gamma_{k}\nabla f(x_{k}),$ (2) $$

where $\gamma_{k}>0$ is a learning rate (stepsize), suffers from several well-known drawbacks. For example, for convex and $L$-smooth objectives, GD converges provided that(^1^11It is theoretically possible to use slightly larger stepsizes, by at most a factor of 2, but this is does not play a role in our narrative.)

$$ $\textstyle\sum\limits_{k=0}^{\infty}\gamma_{k}=+\infty\qquad\text{and}\qquad \gamma_{k}\leq\frac{1}{L}\quad\forall k\geq 0$ (3) $$

(Nesterov, ). For many problems, $L$ is very large and/or unknown, and estimating its value is a non-trivial task. Overestimation of the smoothness constant leads to unnecessarily small stepsizes, which degrades performance, both in theory and in practice.

Polyak stepsize.
When the optimal value $f_{\star}$ is known, a very elegant solution to the above-mentioned problems was provided by Polyak (), who proposed the use of what is now known as the Polyak stepsize:

$$ $\textstyle\gamma_{k}:=\frac{f(x_{k})-f_{\star}}{{\left\|\nabla f(x_{k})\right \|}^{2}}.$ (4) $$

It is known that if $f$ is convex and $L$-smooth, then $\gamma_{k}\geq\frac{1}{2L}$ for all $k\geq 0$ . So, unlike strategies based on the recommendation provided by (3), Polyak stepsize can never be too small compared to the upper bound from (3). In fact, it is possible for $\gamma_{k}$ to be larger than $\frac{1}{L}$, which leads to practical benefits. Moreover, this is achieved without having to know or estimate $L$, which is a big advantage. Since the function value $f(x_{k})$ and the gradient $\nabla f(x_{k})$ are typically known, the only price for these benefits is the knowledge of the optimal value $f_{\star}$. This may or may not be a large price to pay, depending on the application.

Malitsky-Mishchenko stepsize. In the case of convex and locally smooth objectives, Malitsky and Mishchenko () recently proposed an ingenious adaptive stepsize rule that iteratively builds an estimate of the inverse local smoothness constant from the information provided by the sequence of iterates and gradients. Furthermore, they prove their methods achieve the same or better rate of convergence as GD, without the need to assume global smoothness. For a review of further approaches to adaptivity, we refer the reader to Malitsky and Mishchenko (), and for several extensions of this line of work, we refer to Zhou et al. ().

Adaptive stepsizes in deep learning.
When training neural networks and other machine learning models, issues related to the appropriate selection of stepsizes are amplified even further. Optimization problems appearing in deep learning are not convex and may not even be $L$-smooth, or $L$ is prohibitively large, and tuning the learning rate usually requires the use of schedulers or a costly grid search. In this domain, adaptive stepsizes have played a pivotal role in the success of first-order optimization algorithms. Adaptive methods such as Adam, RMSProp, AMSGrad, and Adagrad scale the stepsize at each iteration based on the gradients (Kingma and Ba, ; Hinton, ; Reddi et al., ; Duchi et al., ). Although Adam has seen great success empirically when training deep learning models, there is very little theoretical understanding of why it works so well. On the other hand, Adagrad converges at the desired rate for smooth and Lipschitz objectives but is not as successful in practice as Adam (Duchi et al., ).

#### 1.2 Second-order methods

When $f$ is twice differentiable and $L$-smooth, $L$ can be seen as a global upper bound on the largest eigenvalue of the Hessian of $f$. So, there are close connections between the way a learning rate should be set in GD-type methods and the curvature of $f$.

Newton’s method.
Perhaps the most well-known second-order algorithm is Newton’s method:

$$ $x_{k+1}=x_{k}-\left(\nabla^{2}f(x_{k})\right)^{-1}\nabla f(x_{k}).$ $$

When it works, it converges in a few iterations only. However, it may fail to converge even on convex objectives(^2^22A well-known example is the function $f(x)=\ln(e^{-x}+e^{x})$ with $x_{0}=1.1$.). It needs to be modified in order to converge from any starting point, say by adding a damping factor (Hanzely et al., ) or regularization (Mishchenko, ). However, under suitable assumptions, Newton’s method converges quadratically when started close enough to the solution. The key difficulty in performing a Newton’s step is the computation of the Hessian and a performing a linear solve. In analogy with (2), it is possible to think of $\left(\nabla^{2}f(x_{k})\right)^{-1}$ as a matrix-valued stepsize.

Quasi-Newton methods. To reduce the computational cost, quasi-Newton methods such as L-BFGS utilize an approximation of the inverse Hessian that can be computed from gradients and iterates only, typically using the approximation $\nabla^{2}f(x_{k+1})(x_{k+1}-x_{k})\approx\nabla f(x_{k+1})-\nabla f(x_{k})$, which makes sense under appropriate assumptions when $\|x_{k+1}-x_{k}\|$ is small Nocedal and Wright (); Al-Baali et al. (); Al-Baali and Khalfan (); Dennis and Moré (). Until very recently, quasi-Newton methods were merely efficient heuristics, with very weak theory beyond quadratics (Kovalev et al., ; Rodomanov and Nesterov, ).

Polyak stepsize with second-order information. Li et al. () recently proposed extensions of the Polyak stepsize, named SP2 and SP2+, that incorporate second-order information. SP2 can also be derived similarly to the Polyak stepsize. While SP2 can be utilized in the non-convex stochastic setting, it only has convergence theory for quadratic functions and can often be very unstable in practice. Furthermore, the quadratic constraint defined for SP2 may not even be a localization set.

#### 1.3 Notation

All vectors are in $\mathbb{R}^{d}$ unless explicitly stated otherwise. We use $\mathcal{X}_{\star}$ to denote the set of minimizes of $f$. Matrices are uppercase and bold (e.g., $\mathbf{A},\mathbf{C}$), the $d\times d$ zero (resp. identity) matrix is denoted by $\mathbf{0}$ (resp. $\mathbf{I}$), and $\mathbb{S}^{d}_{+}$ is the set of $d\times d$ positive semi-definite matrices. The standard Euclidean inner product is denoted with $\left\langle\cdot,\cdot\right\rangle$. For $\mathbf{A}\in\mathbb{S}^{d}_{+}$, we let ${\left\|x\right\|}^{2}_{\mathbf{A}}:=\left\langle\mathbf{A}x,x\right\rangle$. By $\|x\|_{p}:=(\sum_{i=1}^{d}|x_{i}|^{p})^{1/p}$ we denote the $L_{p}$ norm in $\mathbb{R}^{d}$. The Löwner order for positive semi-definite matrices is denoted with $\preceq$.

### 2 Summary of Contributions

In this work we contribute to the growing body of knowledge on more powerful and adaptive stepsizes, empowered by local curvature information. We do not go the route of fully-fledged second-order methods which require the expensive computation of the Hessian.

> Instead, our key observation is that, for some problems, certain local curvature information is readily available, and can be used to obtain surprisingly powerful matrix-valued stepsizes.

The examples mentioned above, and discussed in detail in Sections 6 and 7 lead to the following abstract assumption, which at the same time defines what we mean by the term local curvature:

###### Assumption 2.1 (Convexity and smoothness with local curvature) .

There exists a curvature mapping/metric/matrix $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$ and a constant $L_{\mathbf{C}}\geq 0$ such that the inequalities

$$ $\displaystyle\underbrace{f(y)+\left\langle\nabla f(y),x-y\right\rangle+\tfrac{ 1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}}_{M^{\rm low}_{\mathbf{C}}(x;y)} \leq f(x),$ (5) $$

$$ $\displaystyle f(x)\leq\underbrace{f(y)+\left\langle\nabla f(y),x-y\right \rangle+\tfrac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)+L_{\mathbf{C}}\cdot \mathbf{I}}}}_{M^{\rm up}_{\mathbf{C}}(x;y)}$ (6) $$

hold for all $x,y\in\mathbb{R}^{d}$.

2.1 defines a new class of functions. Note that with the specific choice $\mathbf{C}(y)\equiv\mathbf{0}$, (5) reduces to convexity, and (6) reduces to $L$-smoothness, with $L=L_{\mathbf{C}}$. Note that any function satisfying (5) is necessarily convex, and similarly, any $L$-smooth function satisfies (6) with any curvature mapping $\mathbf{C}$ and $L_{\mathbf{C}}=L$. However, the converse is not true: a function satisfying (6) is not necessarily $L$-smooth for any finite $L$. Further, note that if $f$ is $\mu$-strongly convex, then it satisfies (5) with curvature mapping $\mathbf{C}(y)\equiv\mu\mathbf{I}$. The class of convex and $L$-smooth functions is one of the most studied functional classes in optimization. Our new class is a strict and, as we shall see, useful generalization.

We now provide a brief overview of our theoretical and empirical contributions:

###### Assumption 2.1 (Convexity and smoothness with local curvature) .

#### 2.1 Local curvature and a new function class

We define a new function class, described by 2.1, extending the classical class of convex and $L$-smooth functions. Further, we show that there are problems which satisfy 2.1 with nontrivial and easy-to-compute curvature mapping $\mathbf{C}$ (see Section 6 and Section 7).

#### 2.2 Three new algorithms

We propose three novel algorithms for solving problem (1) for function $f$ satisfying 2.1: Local Curvature Descent 1 (LCD1), Local Curvature Descent 2 (LCD2) and Local Curvature Descent 3 (LCD3). First, LCD1 generalizes GD with constant stepsize: one moves from point $y$ to the point obtained by minimizing the upper bound (6) on $f$ in $x$. Indeed, if $\mathbf{C}(y)\equiv\mathbf{0}$, this algorithmic design strategy leads to gradient descent with stepsize $1/L$, where $L=L_{\mathbf{C}}$. Second, LCD2 generalizes GD with Polyak stepsize: one moves from point $y$ to the Euclidean projection of $y$ onto the halfspace

$$ $\mathcal{L}_{\mathbf{C}}(y):=\{x\in\mathbb{R}^{d}\;|\;f(y)+\left\langle\nabla f (y),x-y\right\rangle+\tfrac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}\leq f _{\star}\}.$ $$

Indeed, if $\mathbf{C}(y)\equiv\mathbf{0}$, this algorithmic design leads to GD with stepsize (4). Computing the projection involves finding the unique root of a scalar equation in variable, which can be executed efficiently. Third, LCD3 is obtained from LCD2 by replacing the Euclidean projection with the projection defined by the local curvature matrix $\mathbf{C}$. The projection problem then has a closed-form solution.

#### 2.3 Theory

We prove convergence theorems for LCD1 (Theorem 4.1) and LCD2 (Theorem 4.1), with the same $\mathcal{O}(1/k)$ worst case rate of GD with constant and Polyak stepsize, respectively. Previous work on preconditioned Polyak stepsize (Abdukhakimov et al., ) fails to provide convergence theory and uses matrix stepsizes based on heuristics. In contrast, LCD2 utilizes local curvature from 2.1, and enjoys strong convergence guarantees.

#### 2.4 Experiments

We demonstrate superior empirical behavior of LCD2 over the GD with Polyak stepsize across several standard machine learning problems to which our theory applies. The presence of local curvature in our algorithms boosts their empirical performance when compared to their counterparts not taking advantage of local curvature.

### 3 Three Flavors of Local Curvature Descent

We now describe our methods.

#### 3.1 Local Curvature Descent 1

Our first method, LCD1 is obtained by minimizing the upper bound from Assumption 2.1 where $y=x_{k}$, and letting $x_{k+1}$ be the minimizer:

$$ $\boxed{x_{k+1}=x_{k}-\left[\mathbf{C}(x_{k})+L_{\mathbf{C}}\cdot\mathbf{I} \right]^{-1}\nabla f(x_{k})}$ ( LCD1 ) $$

The derivation is routine; nevertheless, the detailed steps behind Equation LCD1 can be found in Appendix A.1. If $\mathbf{C}(x)\equiv\mathbf{0}$ and we let $L=L_{\mathbf{C}}$, we recover GD with the constant stepsize $\gamma_{k}=\frac{1}{L}$. Note that just like GD, LCD1 is not adaptive to the smoothness parameter $L_{\mathbf{C}}$; this parameter is needed to perform a step.

#### 3.2 Local Curvature Descent 2

Given any $y\in\mathbb{R}^{d}$, let us define the localization set

$$ $\displaystyle\mathcal{L}_{\mathbf{C}}(y):=\left\{x\in\mathbb{R}^{d}\;:\;M_{ \mathbf{C}}^{\rm low}(x,y)\leq f_{\star}\right\}.$ (7) $$

Due to (5), we have $\mathcal{X}_{\star}\subset\mathcal{L}_{\mathbf{C}}(y)$, which justifies the use of the word “localization”. Furthermore, $y\in\mathcal{X}_{\star}$ if and only if $y\in\mathcal{L}_{\mathbf{C}}(y)$. Therefore, $\mathcal{L}_{\mathbf{C}}(x_{k})$ separates $\mathbb{R}^{d}$ in two regions: one containing $\mathcal{X}_{\star}$, the other the current iterate $y=x_{k}$. This allows us to design our second algorithm, LCD2: we simply project the current iterate $x_{k}$ into the localization set $\mathcal{L}_{\mathbf{C}}(x_{k})$, bringing it closer to the set of optimal points $\mathcal{X}_{\star}$:

$$ $\boxed{\textstyle x_{k+1}=\operatorname*{arg\,min}\limits_{x\in\mathcal{L}_{ \mathbf{C}}(x_{k})}\;\frac{1}{2}{\left\|x-x_{k}\right\|^{2}}}$ ( LCD2 ) $$

It turns out that this projection problem has an implicit parametric solution of the form

$$ $\textstyle x_{k+1}=x_{k}-\left[\mathbf{C}(x_{k})+\beta_{k}\cdot\mathbf{I} \right]^{-1}\nabla f(x_{k}),$ ( LCD2 ) $$

where $\beta_{k}>0$. Importantly, we show in Appendix B.1 that the structure of the problem is easy: the parameter $1/\beta_{k}$ is the unique root of a scalar equation, solvable efficiently. Moreover, if $\mathbf{C}(x_{k})$ is a rank-one matrix or a multiple of $\mathbf{I}$, a closed-form solution exists. We present the details in Appendix B.3.

Note that when $\mathbf{C}(x)\equiv\mathbf{0}$, LCD2 becomes GD with Polyak stepsize. In general, LCD2 can be seen as a variant of GD with Polyak stepsize, enhanced with local curvature. The method no longer points in the negative gradient direction anymore, of course. We argue that one step of LCD2 improves on one step of GD with Polyak stepsize. Indeed, since $\mathcal{L}_{\mathbf{C}}(x_{k})\subseteq\mathcal{L}_{\mathbf{0}}(x_{k})$, with equality if and only if $\mathbf{C}(x_{k})=\mathbf{0}$, the point $x_{k+1}$ obtained by LCD2 is closer to $\mathcal{X}_{\star}$ than what is achieved by a single step of GD with Polyak stepsize.

#### 3.3 Local Curvature Descent 3

Our last method, LCD3, was born out of the desire to remove the need for the univariate root-finding subroutine in order to execute the projection defining LCD2. This can be achieved by projecting using the norm given by the local curvature matrix $\mathbf{C}(x_{k})$ instead:

$$ $\boxed{\textstyle x_{k+1}=\operatorname*{arg\,min}\limits_{x\in\mathcal{L}_{ \mathbf{C}}(x_{k})}\;\frac{1}{2}{\left\|x-x_{k}\right\|^{2}_{\mathbf{C}(x_{k}) }}}$ ( LCD3 ) $$

If $\mathbf{C}$ is invertible(^3^33We assume this for simplicity only.), this projection problem admits the closed-form solution

$$ $\textstyle x_{k+1}=x_{k}-\left(1-\sqrt{1-\frac{2(f(x_{k})-f_{\star})}{{\left\| \nabla f(x_{k})\right\|}_{\mathbf{C}^{-1}(x_{k})}^{2}}}\right)\mathbf{C}^{-1}( x_{k})\nabla f(x_{k}).$ ( LCD3 ) $$

The full derivation of this fact can be found in Appendix C.1. Although LCD3 uses the same localization set as LCD2, we do not provide any convergence theorem for this method. The variable metric nature of the projection makes it technically difficult to provide a meaningful analysis of this method. Nevertheless, we justify the introduction of LCD3 via its promising experimental behavior in Section 8 and Appendix F.

### 4 Convergence Rates

Having described the methods, this appears to be the right moment to present our main convergence results for LCD1 and LCD2.

###### Theorem 4.1 (Convergence of LCD1 ) .

Let 2.1 be satisfied. For all $k\geq 1$, the iterates of LCD1 satisfy

$$ $\textstyle f(x_{k})-f_{\star}\leq\frac{L_{\mathbf{C}}{\left\|x_{0}-x_{\star} \right\|}^{2}}{2k}.$ $$

###### Theorem 4.2 (Convergence of LCD2 ) .

Let 2.1 be satisfied. For all $k\geq 1$, the iterates of LCD2 satisfy

$$ $\textstyle\min\limits_{1\leq t\leq k}\;f(x_{t})-f_{\star}\leq\frac{L_{\mathbf{ C}}{\left\|x_{0}-x_{\star}\right\|}^{2}}{2k}.$ $$

The proofs of these results can be found in Appendix A.2 and Appendix B.2, respectively. It is possible to derive linear convergence results under the assumption that $\mathbf{C}(x)\succeq\mu\mathbf{I}$ for all $x\in\mathbb{R}^{d}$ and some $\mu>0$; however, we refrain from listing these for brevity reasons.

If $\mathbf{C}(x)\equiv\mathbf{0}$, and we let $L=L_{\mathbf{C}}$, these theorems recover the standard rates known for GD with the stepsize $1/L$ and GD with Polyak stepsize, respectively. So, we generalize these earlier results. However, it is possible for a function to satisfy 2.1 and not be $L$-smooth. In this sense, our results extend the reach of the classical theorems beyond the class of convex and $L$-smooth functions. On the other hand, if $f$ is convex and $L$-smooth, it may be possible that it satisfies 2.1 with some nonzero local curvature mapping $\mathbf{C}$, in which case $L_{\mathbf{C}}\leq L$. Indeed,

$$ $\underset{x\in\mathbb{R}^{d}}{\inf}\lambda_{\min}(\mathbf{C}(x))\leq L-L_{ \mathbf{C}}\leq\underset{x\in\mathbb{R}^{d}}{\sup}\lambda_{\max}(\mathbf{C}(x)),$ $$

where $\lambda_{\min}(\cdot)$ (resp. $\lambda_{\max}(\cdot)$) represents the smallest (resp. largest) eigenvalue of the argument, confirming $L_{\mathbf{C}}\leq L$. However, it may be that $L_{\mathbf{C}}\ll L$, in which case our result leads to improved complexity. Nevertheless, the main allure of our methods is their attractive empirical behavior.

Convex quadratics. For convex quadratics, 2.1 is satisfied with $\mathbf{C}(x)=\nabla^{2}f(x)$ and $L_{\mathbf{C}}=0$. In this case, both LCD1 and LCD2 reduce to Newton’s method, and converge in a single step. Moreover, Theorem 4.1 and Theorem 4.2 predict this one-step convergence behavior.

To validate our theoretical setting, we will show that functions satisfying Assumption 2.1 are easy to construct, well-behaved, and practically interesting.

###### Theorem 4.1 (Convergence of LCD1 ) .

###### Theorem 4.2 (Convergence of LCD2 ) .

### 5 Local Curvature Calculus

We now mention a couple basic properties of functions that satisfy Inequalities (5) and (6).

###### Lemma 5.1 .

Let $\alpha,\beta\in\mathbb{R}$ with $\beta\geq 0$. Suppose functions $f$ and $g$ satisfy inequality (5) with curvature mappings $\mathbf{C}_{1}$ and $\mathbf{C}_{2}$ respectively. Then:

$$ $f+\alpha,\qquad\beta f,\quad\text{and}\quad f+g,$ $$

satisfy Inequality (5) with curvature mappings $\mathbf{C}_{1}$, $\beta\mathbf{C}_{1}$, and $\mathbf{C}_{1}+\mathbf{C}_{2}$ respectively.

The proof of the lemma can be found in Appendix D.1. A particularly useful instantiation of Lemma 5.1 is presented in the following corollary.

###### Corollary 5.1 .

If $f$ satisfies (5) and $g$ is convex, then $h:=f+g$ also satisfies (5).

Corollary 5.1 enables us to derive a variety of examples of functions satisfying inequality (5) by summing convex functions with instances from our class. Moreover, we can also show that inequality (5) is preserved under pre-composition with linear functions. Additional results for functions satisfying Assumption 2.1 can be found in Appendix D.

###### Lemma 5.1 .

###### Corollary 5.1 .

### 6 Examples of Functions Satisfying 2.1

We first list three examples that satisfy both inequalities in Assumption 2.1. Firstly, observe that if a function is $L$-smooth, then it satisfies inequality (6) since $\mathbf{C}(x)$ is assumed to be a positive semi-definite matrix. We aim to find convex functions that satisfy our assumption in a non-trivial manner, i.e., $\mathbf{C}(x)\not\equiv\mathbf{0}$ and $\mathbf{C}(x)\not\equiv\mu\mathbf{I}$ for some $\mu>0$.

###### Example 6.1 (Huber loss) .

Let $\delta>0$ and consider the Huber loss function $h:\mathbb{R}\to\mathbb{R}$ given by

$$ $h(x)=\begin{cases}\frac{1}{2}x^{2}&\left\lvert x\right\rvert\leq\delta\\ \delta(\left\lvert x\right\rvert-\frac{1}{2}\delta)&\left\lvert x\right\rvert> \delta\end{cases}.$ $$

Then $f=h^{2}$ satisfies 2.1 with constant $L_{\mathbf{C}}=2\delta^{2}$ and curvature mapping

$$ $\mathbf{C}(x)=\begin{cases}x^{2}&\left\lvert x\right\rvert\leq\delta\\ \delta^{2}&\left\lvert x\right\rvert>\delta\end{cases}.$ $$

Example 6.1 is particularly interesting because $\mathbf{C}(x)+2\delta^{2}\leq 3\delta^{2}$ for any $x\in\mathbb{R}$. By computing the second derivative of $f$, we can obtain the tightest $L$-smoothness constant; it is equal to $3\delta^{2}$. Therefore, the variable bound we derived is at least as good as the $L$-smoothness bound.

###### Example 6.2 (Squared $p$ norm) .

Let $p\geq 2$ and define $f:\mathbb{R}^{d}\to\mathbb{R}$ as $f(x)=\left\|x\right\|_{p}$. Then $f^{2}$ satisfies 2.1 with either of the two curvature mappings,

$$ $\textstyle\mathbf{C}(x)=\frac{2}{{\left\|x\right\|}_{p}^{p-2}}\operatorname{ Diag}{(\left\lvert x_{1}\right\rvert^{p-2},\ldots,\left\lvert x_{d}\right \rvert^{p-2})},\quad\mathbf{C}(x)=2\nabla f(x)\nabla f(x)^{\top},$ $$

and constant $L_{\mathbf{C}}=2(p-1)$.

###### Example 6.3 ( $L_{p}$ regression) .

Suppose $\mathbf{A}\in\mathbb{R}^{n\times d}$ and $b\in\mathbb{R}^{n}$. For $p\geq 2$, the function $f(x)=\left\|\mathbf{A}x-b\right\|_{p}^{2},$
satisfies Assumption 2.1 as a precomposition of Example 6.2 with an affine function.

Therefore, linear regression in the squared $L_{p}$ norm satisfies our assumption. The $L_{p}$ regression problem has several applications in machine learning (Dasgupta et al., ; Musco et al., ; Yang et al., ). This includes low-rank matrix approximation, sparse recovery, data clustering, and learning tasks (Adil et al., ). In general, convex optimization in non-Euclidean geometries is a well-studied and important research direction. This motivates us to study $L_{p}$ norms further and understand how they can fit within our assumptions.

We can perform other simple modifications of $L_{p}$ norm that satisfy only inequality (5).

###### Example 6.4 .

Let $p\geq 2$. Then $f(x)=\left\|x\right\|_{p}^{p}$ satisfies (5) with either of the curvature mappings

$$ $\textstyle\mathbf{C}_{1}(x)=\frac{1}{p-1}\nabla^{2}f(x),\qquad\mathbf{C}_{2}(x )=\frac{1}{pf(x)}\nabla f(x)\nabla f(x)^{\top}.$ $$

We postpone comments to Appendix D.3.
Using Corollary 5.1 and the above examples, we can construct regularized convex problems that satisfy our assumptions. For instance, we can add the square of an $L_{p}$ norm to the logistic loss function to obtain an objective function that satisfies (5), with the mapping from the regularizer. The objective function will be $L$-smooth, so it also satisfies inequality (6).

###### Example 6.1 (Huber loss) .

###### Example 6.2 (Squared p 𝑝 p italic_p norm) .

###### Example 6.3 ( L p subscript 𝐿 𝑝 L_{p} italic_L start_POSTSUBSCRIPT italic_p end_POSTSUBSCRIPT regression) .

###### Example 6.4 .

### 7 Absolutely Convex Functions

In addition to the examples from Section 6, we now introduce the class of absolutely convex functions, and the problem of minimizing the sum of squares of absolutely convex functions. In this setting, as we shall show, the curvature mapping $\mathbf{C}$ satisfying Inequality (5) is readily available.

#### 7.1 Absolute convexity

Absolutely convex functions are defined as follows.

###### Definition 7.1 (Absolute convexity) .

A function $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex if

$$ $\phi(x)\geq|\phi(y)+\langle\nabla\phi(y),\,x-y\rangle|\quad\forall x,y\in \mathbb{R}^{d}.$ (8) $$

Above, $\nabla\phi(y)$ refers to a subgradient of $\phi$ at $y$. Geometrically, (8) means that linear approximations of $\phi$ are always above the graph of $-\phi$ in addition to being below the graph of $\phi$ (same as convexity),

$$ $-\phi(x)\leq\phi(y)+\left\langle\nabla\phi(y),x-y\right\rangle\leq\phi(x).$ $$

Thus, any absolutely convex function is necessarily convex and non-negative. A constant function is absolutely convex if and only if it is non-negative. A linear function is absolutely convex if and only if it is constant and non-negative. Moreover, the absolute value of any affine function is absolutely convex; that is, $\phi(x)=|\left\langle a,x\right\rangle+b|$ is absolutely convex. We avoid stating basic calculus rules as in Lemma 5.1, and opt to present only one interesting property, and one notable example. Many others can be found in Appendix E.

###### Lemma 7.1 .

Absolutely convex functions have bounded subgradients.

###### Example 7.1 .

If $p\geq 1$, then $\phi(x)={\left\|x\right\|}_{p}$ is absolutely convex.

###### Definition 7.1 (Absolute convexity) .

###### Lemma 7.1 .

###### Example 7.1 .

#### 7.2 Minimizing the sum of squares of absolutely convex functions

To conclude, we present the derivation of the curvature mapping $\mathbf{C}$ for the sum of squares of absolutely convex functions. Consider the optimization problem

$$ $\textstyle x_{\star}=\operatorname*{arg\,min}\limits_{x\in\mathbb{R}^{d}}\left \{f(x):=\frac{1}{n}\sum\limits_{i=1}^{n}\phi_{i}^{2}(x)\right\},$ (9) $$

where each $\phi_{i}$ is absolutely convex and a solution, $x_{\star}$, is assumed to exist. Let $f_{i}:=\phi_{i}^{2}$, so that $\nabla f_{i}(x)=2\phi_{i}(x)\nabla\phi_{i}(x)$. The gradient of $f$ is given by

$$ $\textstyle\nabla f(x)=\frac{1}{n}\sum\limits_{i=1}^{n}\nabla f_{i}(x)=\frac{2} {n}\sum\limits_{i=1}^{n}\phi_{i}(x)\nabla\phi_{i}(x).$ $$

Since $\phi_{i}$ is absolutely convex, $f_{i}$ is necessarily convex. Indeed, by squaring both sides of the defining inequality (8), we get

$$ $f_{i}(y)+\left\langle\nabla f_{i}(y),x-y\right\rangle+\left\langle\nabla\phi_{ i}(y)\nabla\phi_{i}(y)^{\top}(x-y),x-y\right\rangle\leq f_{i}(x),\qquad\forall x ,y\in\mathbb{R}^{d}.$ $$

Summing these inequalities across $i$ and taking the average, we find that the curvature mapping can be set to

$$ $\textstyle\mathbf{C}(x)=\frac{2}{n}\sum\limits_{i=1}^{n}\nabla\phi_{i}(x) \nabla\phi_{i}(x)^{\top}.$ $$

In Appendix F, we provide experiments on objective functions that are in this class.

### 8 Experiments

To illustrate practical performance of the presented methods, we run a series of experiments on MacBook Pro with Apple M1 chip and 8GB of RAM. We use datasets from LibSVM (Chang and Lin, ). We implemented all algorithms in Python.

Let us focus on solving

$$ $\textstyle f(x)=\frac{1}{n}\sum\limits_{i=1}^{n}\log(1+e^{-b_{i}a_{i}x})+ \lambda{\left\|x\right\|}^{p}_{p},$ $$

where $a_{i}\in\mathbb{R}^{d}$ and $b_{i}\in\{-1,1\}$ are the data samples associated with a binary classification problem. The regularization weight $\lambda$ is set proportionally to the $L$-smoothness constant of the logistic regression instance.

In the first experiment, we use $L_{2}$ regularization. Therefore, $f$ is $L$-smooth and $\mu$-strongly-convex, so $\mathbf{C}(x)\equiv\mu\mathbf{I}$. As mentioned previously, in this setting, LCD1 recovers GD and LCD2 has a closed-form solution coinciding with LCD3.

Figure: Figure 1: Logistic regression on a2a dataset with $L_{2}$ regularization.
Refer to caption: extracted/5615196/imgs/log_reg_l2/a2a_p2_a0.00015.png

Figures 1(c)–2(c) show that LCD2 consistently outperforms Polyak. As expected, the gap increases with $\lambda$ because $\mathbf{C}(x)$ only stores information about the regularizer. Thus, increasing $\lambda$ shrinks the localization set of LCD2 so its improvement over Polyak grows. Importantly, since LCD2 has a closed form solution, its cost-per-iteration is the same as Polyak.

In the next experiment, we use $L_{3}$ regularization. In Example 6.4 we propose two $\mathbf{C}(x)$ matrix candidates for ${\left\|x\right\|}_{p}^{p}$. Here we decide on the diagonal variant $\mathbf{C}_{1}(x)$. The objective function is no longer $L$-smooth, due to the non-smooth regularizer. As a result, we run LCD1 with the smallest $L_{\mathbf{C}}$ such that the method converges. Additionally, LCD2 no longer has a closed form solution, so the projection algorithm must be deployed. To perform a fair comparison of our algorithms, we show both time and iteration plots.

Figure: Figure 3: Logistic regression on mushrooms dataset with $L_{3}$ regularization - iteration convergence.
Refer to caption: extracted/5615196/imgs/log_reg_l3/mushrooms_p3_a0.003.png

Figure 3(c) displays similar to the $L_{2}$ case improvement of LCD2 over Polyak, which grows with $\lambda$. Our heuristic LCD3 can produce satisfying results, experimentally. However, its convergence cannot be guaranteed. In fact, as $\lambda$ increases it becomes unstable. LCD1 converges at comparable pace with the other three methods at initial steps, yet the limited adaptiveness slows it down later on.

Figure 4(c) shows convergence of our methods in time. One may point that the plots look almost identical to the iteration counterpart. The main reason is the cost of computing the gradient, which is $\mathcal{O}(nd)$. All other operations performed by LCD3 and LCD1 are $\mathcal{O}(d)$. The method with the most expensive update rule is LCD2. At every step it performs around $5$ rounds of the projection algorithm, each costing $\mathcal{O}(d)$. We conclude that all the methods have comparable computational cost per iteration, as the main expense is the gradient evaluation. While the complexities discussed above are for diagonal matrices, we remark that the general $\mathcal{O}(d^{3})$ cost is bearable when $n\gg d$. Moreover, our examples usually allow cheap diagonal matrix methods.

Further experiments with ridge regression and sum of squared Huber losses are in Appendix F.

### 9 Conclusion

We explored adaptive matrix-valued stepsizes under novel assumptions that reinforce convexity and $L$-smoothness with extra curvature information. Under our assumptions, we proposed LCD1 and LCD2, which generalize GD with constant stepsize and Polyak stepsize, respectively. Moreover, we provided convergence theorems for both of these algorithms. We also proposed LCD3 which displays promising experimental behavior. Our key insight is that, for some problems, we have certain local curvature information that can be readily exploited. We tested the methods on these problems using a variety of realistic datasets, demonstrating good empirical performance.

The main limitation of our analysis is the restriction to a deterministic setting. We also acknowledge that the assumption is yet to explore in its entirety. As a matter of fact, the most natural extension of the present work is including stochasticity and understanding the full potential of Assumption 2.1.

### 10 Acknowledgements

The work of all authors was supported by the KAUST Baseline Research Fund awarded to Peter Richtárik, who additionally acknowledges support from the SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence. The work of
Simone Maria Giancola, Dymitr Lubczyk and Robin Yadav was supported by the Visiting Student Research Program (VSRP) at KAUST. All authors are thankful to the KAUST AI Initiative for office space and administrative support.

## Appendix

### Appendix A Local Curvature Descent 1 ( LCD1 )

#### A.1 Derivation

Suppose that the upper bound in (6) from 2.1) holds. Then, at a given point $x_{k+1}\in\mathbb{R}^{d}$, we have:

$$ $f(x_{k+1})\leq f(x_{k})+\left\langle\nabla f(x_{k}),x_{k+1}-x_{k}\right\rangle +\frac{1}{2}{\left\|x_{k+1}-x_{k}\right\|^{2}_{\mathbf{C}(x_{k})+L_{\mathbf{C} }\mathbf{I}}}\qquad\forall x_{k}\in\mathbb{R}^{d}.$ $$

Minimizing the right hand side with respect to $x_{k+1}$ we find that:

$$ $x_{k+1}=x_{k}-\left[\mathbf{C}(x_{k})+L_{\mathbf{C}}\mathbf{I}\right]^{-1} \nabla f(x_{k}).$ (10) $$

In particular, the matrix that pre-multiplies the vector is always invertible, since $\mathbf{C}(x)$ is positive semi-definite for each $x\in\mathbb{R}^{d}$.

#### A.2 Convergence proof

###### Lemma A.1 .

Let Assumption 2.1 hold. For all $k\geq 0$, the sequence $(x_{k})_{k\in\mathbb{N}}$ of LCD1 is such that:

$$ ${\left\|x_{k+1}-x_{\star}\right\|}_{2}^{2}-{\left\|x_{k}-x_{\star}\right\|}_{2 }^{2}\leq-\frac{2}{L_{\mathbf{C}}}\left(f(x_{k+1})-f(x_{\star})\right),\quad \forall k\in\mathbb{N}.$ (11) $$

###### Proof.

The proof is achieved by carefully bounding terms. For this reason, we split it into three steps.

We seek a connection between the two distances in the geometry induced by $\tilde{\mathbf{C}}(x_{k}):=\mathbf{C}(x_{k})+L_{\mathbf{C}}\mathbf{I}$:

$$ $\displaystyle{\left\|x_{k}-x_{\star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle={\left\|x_{k}-x_{k+1}+x_{k+1}-x_{\star}\right\|}_{\tilde{\mathbf {C}}(x_{k})}^{2}$ $\displaystyle={\left\|x_{k}-x_{k+1}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}+2 \left\langle[\tilde{\mathbf{C}}(x_{k})](x_{k}-x_{k+1}),x_{k+1}-x_{\star}\right\rangle$ $\displaystyle\phantom{+{\left\|x_{k+1}\right\|}}+{\left\|x_{k+1}-x_{\star} \right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle={\left\|x_{k}-x_{k+1}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}+2 \left\langle\nabla f(x_{k}),x_{k+1}-x_{\star}\right\rangle+{\left\|x_{k+1}-x_{ \star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle={\left\|x_{k+1}-x_{k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}+2 \left\langle\nabla f(x_{k}),x_{k+1}-x_{\star}\right\rangle+{\left\|x_{k+1}-x_{ \star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}.$ $$

Rearranging the terms we obtain

$$ $\displaystyle{\left\|x_{k+1}-x_{\star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2 }-{\left\|x_{k}-x_{\star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle=-{\left\|x_{k+1}-x_{k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}- 2\left\langle\nabla f(x_{k}),x_{k+1}-x_{\star}\right\rangle$ $\displaystyle=-{\left\|x_{k+1}-x_{k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle\phantom{{\left\|x\right\|}}-2\left\langle\nabla f(x_{k}),x_{k+1} -x_{k}+x_{k}-x_{\star}\right\rangle$ $\displaystyle=-{\left\|x_{k+1}-x_{k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}- 2\left\langle\nabla f(x_{k}),x_{k+1}-x_{k}\right\rangle$ $\displaystyle\phantom{{\left\|x\right\|}}+2\left\langle\nabla f(x_{k}),x_{ \star}-x_{k}\right\rangle.$ $$

In particular, we wish to bound the inner products.

Rearranging the lower bound (5) in Assumption 2.1 for the pair $(x_{k},x_{\star})$:

$$ $2\left\langle\nabla f(x_{k}),x_{\star}-x_{k}\right\rangle\leq 2(f(x_{\star})-f (x_{k}))-{\left\|x_{k}-x_{\star}\right\|}_{\mathbf{C}(x_{k})}^{2}.$ $$

In a similar way, massaging the upper bound (6) of Assumption 2.1 for the pair $(x_{k+1},x_{k})$ one can derive:

$$ $-2\left\langle\nabla f(x_{k}),x_{k+1}-x_{k}\right\rangle\leq{\left\|x_{k+1}-x_ {k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}+2(f(x_{k})-f(x_{k+1})).$ $$

Combining two previous steps we find:

$$ $\displaystyle{\left\|x_{k+1}-x_{\star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2 }-{\left\|x_{k}-x_{\star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle\leq-{\left\|x_{k+1}-x_{k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{ 2}+{\left\|x_{k+1}-x_{k}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}$ $\displaystyle+2(f(x_{k})-f(x_{k+1}))+2(f(x_{\star})-f(x_{k}))-{\left\|x_{k}-x_ {\star}\right\|}_{\mathbf{C}(x_{k})}^{2}$ $\displaystyle=2(f(x_{\star})-f(x_{k+1}))-{\left\|x_{k}-x_{\star}\right\|}_{ \mathbf{C}(x_{k})}^{2}.$ $$

The term ${\left\|x_{k}-x_{\star}\right\|}_{\mathbf{C}(x_{k})}^{2}$ is on both sides of the inequality, so we can cancel it out:

$$ ${\left\|x_{k+1}-x_{\star}\right\|}_{\tilde{\mathbf{C}}(x_{k})}^{2}-{\left\|x_{ k}-x_{\star}\right\|}_{L_{\mathbf{C}}\mathbf{I}}^{2}\leq 2(f(x_{\star})-f(x_{k +1})).$ $$

Having almost removed all the $\mathbf{C}(x_{k})$ norms, it suffices to apply the crude bound:

$$ $L_{\mathbf{C}}{\left\|x_{k+1}-x_{\star}\right\|}^{2}={\left\|x_{k+1}-x_{\star} \right\|}_{L_{\mathbf{C}}\mathbf{I}}^{2}\leq{\left\|x_{k+1}-x_{\star}\right\|} _{\tilde{\mathbf{C}}(x_{k})}^{2},$ $$

which holds since $L_{\mathbf{C}}\mathbf{I}\preceq\mathbf{C}(x_{k})+L_{\mathbf{C}}\mathbf{I}=
\tilde{\mathbf{C}}(x_{k})$.

Therefore, we obtain

$$ $\displaystyle{\left\|x_{k+1}-x_{\star}\right\|}_{L_{\mathbf{C}}\mathbf{I}}^{2} -{\left\|x_{k}-x_{\star}\right\|}_{L_{\mathbf{C}}\mathbf{I}}^{2}$ $\displaystyle\leq 2(f(x_{\star})-f(x_{k+1}))=-2(f(x_{k+1})-f(x_{\star})).$ $$

Reordering gives the claim.
∎

###### Lemma A.2 .

For any $k\in\mathbb{N}$, the iterations of LCD1 satisfy:

$$ $f(x_{k+1})-f(x_{k})\leq-\frac{1}{2}{\left\|\nabla f(x_{k})\right\|}_{(\mathbf{ C}(x_{k})+L_{\mathbf{C}}\mathbf{I})^{-1}}^{2}\leq 0.$ (12) $$

###### Proof.

Let us remind the form of the updates for each $k\in\mathbb{N}$

$$ $x_{k+1}=x_{k}-\left[\tilde{\mathbf{C}}(x_{k})\right]^{-1}\nabla f(x_{k}),$ $$

where $\tilde{\mathbf{C}}(x_{k})=\mathbf{C}(x_{k})+L_{\mathbf{C}}\mathbf{I}$.

By Assumption 2.1, we know that

$$ $\displaystyle f(x_{k+1})$ $\displaystyle\leq f(x_{k})-\left\langle\nabla f(x_{k}),[\tilde{\mathbf{C}}(x_{ k})]^{-1}\nabla f(x_{k})\right\rangle+\frac{1}{2}\left\langle\nabla f(x_{k}),[ \tilde{\mathbf{C}}(x_{k})]^{-1}\nabla f(x_{k})\right\rangle$ $\displaystyle=f(x_{k})-\frac{1}{2}{\left\|\nabla f(x_{k})\right\|}_{[\tilde{ \mathbf{C}}(x_{k})]^{-1}}^{2},$ $$

and the claim follows by simple rearrangement.
∎

Having the lemmas established, let us proceed to the proof of Theorem 4.1. We want to show that if $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Assumption 2.1 then for any $k\in\mathbb{N}$, the iterates of LCD1 are such that:

$$ $f(x_{k})-f(x_{\star})\leq\frac{L_{\mathbf{C}}}{2k}{\left\|x_{0}-x_{\star} \right\|^{2}}.$ (13) $$

###### Proof.

We use a standard Lyapunov function proof technique. For completeness, let us report it.

By Lemma A.2, function values get closer to $f_{\star}$ across iterations. Lemma A.1, the vectors get closer in norm to an optimum.

Then, we can combine the two positive decreasing terms $L_{\mathbf{C}}{\left\|x_{k}-x_{\star}\right\|}^{2}$ and $f(x_{k})-f(x_{\star})$ into a Lyapunov energy function:

$$ $\mathcal{E}_{k}:=L_{\mathbf{C}}{\left\|x_{k}-x_{\star}\right\|}^{2}+2k(f(x_{k} )-f(x_{\star})),\qquad\forall k\in\mathbb{N}.$ $$

In particular, $\mathcal{E}_{0}=L_{\mathbf{C}}{\left\|x_{0}-x_{\star}\right\|}^{2}$, and we claim that $\mathcal{E}_{k}$ is a decreasing function. To see this, we start by rewriting the difference:

$$ $\displaystyle\mathcal{E}_{k+1}-\mathcal{E}_{k}$ $\displaystyle=2(k+1)(f(x_{k+1})-f(x_{\star}))-2k(f(x_{k})-f(x_{\star}))$ $\displaystyle\phantom{+{\left\|x\right\|}}+L_{\mathbf{C}}{\left\|x_{k+1}-x_{ \star}\right\|}^{2}-L_{\mathbf{C}}{\left\|x_{k}-x_{\star}\right\|}^{2}$ $\displaystyle=2(f(x_{k+1})-f(x_{\star}))+2k(f(x_{k+1})-f(x_{\star})-f(x_{k})+f (x_{\star}))$ $\displaystyle\phantom{+{\left\|x\right\|}}+L{\left\|x_{k+1}-x_{\star}\right\|} ^{2}-L_{\mathbf{C}}{\left\|x_{k}-x_{\star}\right\|}^{2}$ $\displaystyle=2(f(x_{k+1})-f(x_{\star}))+2k(f(x_{k+1})-f(x_{k}))$ $\displaystyle\phantom{+{\left\|x\right\|}}+L_{\mathbf{C}}{\left\|x_{k+1}-x_{ \star}\right\|}^{2}-L_{\mathbf{C}}{\left\|x_{k}-x_{\star}\right\|}^{2}.$ $$

It is evident that we can apply our Lemmas as follows:

$$ $\displaystyle f(x_{k+1})-f(x_{k})$ $\displaystyle\leq 0$ by Lemma A.2 ; (14) $\displaystyle L_{\mathbf{C}}{\left\|x_{k+1}-x_{\star}\right\|}^{2}-L_{\mathbf{ C}}{\left\|x_{k}-x_{\star}\right\|}^{2}$ $\displaystyle\leq f(x_{k+1})-f(x_{\star})$ by Lemma A.1 . (15) $$

Putting everything together:

$$ $\mathcal{E}_{k+1}-\mathcal{E}_{k}\leq 2(f(x_{k+1})-f(x_{\star}))-2(f(x_{k+1})- f(x_{\star}))=0,$ $$

showing that $\mathcal{E}_{k}$ is decreasing. As a particular case, we then find:

$$ $2k(f(x_{k})-f(x_{\star}))\leq\mathcal{E}_{k}\leq\mathcal{E}_{0}=L_{\mathbf{C}} {\left\|x_{0}-x_{\star}\right\|}^{2},$ $$

which reordered recovers the rate of GD with stepsize $\frac{1}{L_{\mathbf{C}}}$, i.e.

$$ $f(x_{k})-f(x_{\star})\leq\frac{L_{\mathbf{C}}{\left\|x_{0}-x_{\star}\right\|}^ {2}}{2k}.$ $$

∎

Remark. For quadratic functions Assumption 2.1 is satisfied with $\mathbf{C}(x)$ equal to the Hessian, and $L_{\mathbf{C}}=0$. Thus, LCD1 convergences in one step for this class of functions.

###### Lemma A.1 .

###### Proof.

###### Lemma A.2 .

###### Proof.

###### Proof.

### Appendix B Local Curvature Descent 2 ( LCD2 )

#### B.1 Derivation

Consider the minimization problem for the update step of LCD2:

$$ $\displaystyle\min_{x\in\mathcal{L}_{\mathbf{C}}(x_{k})}\frac{1}{2}{\left\|x-x_ {k}\right\|}^{2},$ (16) $$

where

$$ $\mathcal{L}_{\mathbf{C}}(x_{k})=\left\{x\in\mathbb{R}^{d}\mid f(x_{k})+\left \langle\nabla f(x_{k}),x-x_{k}\right\rangle+\frac{1}{2}{\left\|x-x_{k}\right\| ^{2}_{\mathbf{C}(x_{k})}}\leq f_{\star}\right\}.$ (17) $$

If $\mathbf{C}(x_{k})$ is the zero matrix, we know this problem has a closed-form solution. Therefore, we focus on the case where $\mathbf{C}(x_{k})$ is a non-zero matrix. Moreover, we assume that $x_{k}\not\in\mathcal{X_{\star}}$. The Lagrangian of this problem is:

$$ $\mathscr{L}(x,\beta)=\frac{1}{2}{\left\|x-x_{k}\right\|}^{2}+\beta\left(\frac{ 1}{2}{\left\|x-x_{k}\right\|^{2}_{\mathbf{C}(x_{k})}}+\left\langle\nabla f(x_{ k}),x-x_{k}\right\rangle+f(x_{k})-f_{\star}\right),$ $$

where $\beta\geq 0$. For optimal $\bar{x}$ and $\bar{\beta}$ we have that $\nabla_{x}\mathscr{L}(\bar{x},\bar{\beta})=0$. Therefore,

$$ $\bar{x}-x_{k}+\bar{\beta}\left({\left\|\bar{x}-x_{k}\right\|^{2}_{\mathbf{C}(x _{k})}}+\nabla f(x_{k})\right)=0.$ $$

Isolating for $\bar{x}$, we find that:

$$ $\bar{x}=x_{k}-\bar{\beta}\left[\mathbf{I}+\bar{\beta}\mathbf{C}(x_{k})\right]^ {-1}\nabla f(x_{k}).$ $$

We can see $\bar{\beta}\neq 0$ so the constraint is tight. The next step would be to substitute $\bar{x}$ into the constraint and solve for $\bar{\beta}$:

$$ $\frac{1}{2}{\left\|\bar{x}-x_{k}\right\|^{2}_{\mathbf{C}(x_{k})}}+\left\langle \nabla f(x_{k}),\bar{x}-x_{k}\right\rangle+f(x_{k})-f_{\star}=0.$ $$

Despite the left-hand side being a scalar function of $\bar{\beta}$, we cannot obtain a closed-form solution for $\bar{\beta}$. However, we can use an iterative root-finding sub-routine such as Newton’s method to get an approximation of $\bar{\beta}$ cheaply and effectively. By substituting in the value of $\bar{x}$, we see that we need to find the root of the following function:

$$ $\displaystyle H(\beta)$ $\displaystyle\coloneqq\frac{\beta^{2}}{2}g_{k}^{\top}\left[\mathbf{I}+\beta \mathbf{C}(x_{k})\right]^{-\top}\mathbf{C}(x_{k})\left[\mathbf{I}+\beta\mathbf {C}(x_{k})\right]^{-1}g_{k}$ (18) $\displaystyle\phantom{\qquad\qquad}-\beta g_{k}^{\top}\left[\mathbf{I}+\beta \mathbf{C}(x_{k})\right]^{-1}g_{k}+\Delta_{k}.$ $$

To simplify notation, let $\mathbf{C}:=\mathbf{C}(x_{k})$, $g:=\nabla f(x_{k})$ and $\Delta_{k}:=f(x_{k})-f_{\star}$.

In the following proposition, we confirm that $H$ has a root in the interval $[0,\infty)$. We also show that $H$ is convex and monotonically decreasing on that interval. Therefore, Newton’s method is guaranteed to converge to the root of $H$ at a quadratic rate. In particular, we do not need $H$ to be monotonically decreasing; nonetheless, it is an interesting property of the problem.

###### Proposition B.1 (Properties of $H$ ) .

Let $H$ be defined as in Equation 18. Then, for $\beta\geq 0$:

$$ $H(0)>0,\quad H^{\prime}(\beta)<0,\quad H^{\prime\prime}(\beta)>0,\quad\lim_{ \beta\to\infty}H(\beta)<0.$ (19) $$

###### Proof.

W.l.o.g. assume that $\mathbf{C}$ is a symmetric matrix. As a result, $\mathbf{C}$ is orthogonally diagonalizable so we let $\mathbf{C}=\mathbf{Q}\mathbf{D}\mathbf{Q}^{\top}$ where $\mathbf{D}$ is a diagonal matrix, and $\mathbf{Q}$ is an orthogonal matrix such that $\mathbf{Q}\mathbf{Q}^{\top}=\mathbf{I}$. Manipulating the inverse matrix in the definition of $H$, we find:

$$ $\left[\mathbf{I}+\beta\mathbf{C}(x_{k})\right]^{-1}=\left[\mathbf{Q}\mathbf{Q} ^{\top}+\beta\mathbf{Q}\mathbf{D}\mathbf{Q}^{\top}\right]^{-1}=\left[\mathbf{Q }(\mathbf{I}+\beta\mathbf{D})\mathbf{Q}^{\top}\right]^{-1}=\mathbf{Q}\left[ \mathbf{I}+\beta\mathbf{D}\right]^{-1}\mathbf{Q}^{\top}.$ $$

Let $\tilde{g}:=\mathbf{Q}^{\top}g$. Let $D_{i}$ represent the $i^{\text{th}}$ entry of the diagonal of $\mathbf{D}$ and $\tilde{g}_{i}$ represent the $i^{\text{th}}$ entry in $\tilde{g}$. We rewrite $H$ as:

$$ $\displaystyle H(\beta)$ $\displaystyle=\frac{\beta^{2}}{2}g^{\top}\mathbf{Q}\left[\mathbf{I}+\beta \mathbf{D}\right]^{-1}\mathbf{D}\left[\mathbf{I}+\beta\mathbf{D}\right]^{-1} \mathbf{Q}^{\top}g-\beta g^{\top}\mathbf{Q}\left[\mathbf{I}+\beta\mathbf{D} \right]^{-1}\mathbf{Q}^{\top}g+\Delta_{k}$ $\displaystyle=\frac{\beta^{2}}{2}\tilde{g}^{\top}\left[\mathbf{I}+\beta\mathbf {D}\right]^{-1}\mathbf{D}\left[\mathbf{I}+\beta\mathbf{D}\right]^{-1}\tilde{g} -\beta\tilde{g}^{\top}\left[\mathbf{I}+\beta\mathbf{D}\right]^{-1}\tilde{g}+ \Delta_{k}$ $\displaystyle=\frac{\beta^{2}}{2}\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}D_{i}}{( 1+\beta D_{i})^{2}}-\beta\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}}{1+\beta D_{i}} +\Delta_{k}.$ $$

By inspection, $H$ is a rational function and the derivative is easily found;

$$ $\displaystyle H^{\prime}(\beta)$ $\displaystyle=\beta\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}D_{i}}{(1+\beta D_{i}) ^{2}}-\beta^{2}\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}D_{i}^{2}}{(1+\beta D_{i}) ^{3}}-\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}}{1+\beta D_{i}}+\beta\sum_{i=1}^{d }\frac{\tilde{g}_{i}^{2}D_{i}}{(1+\beta D_{i})^{2}}$ $\displaystyle=-\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}}{(1+\beta D_{i})^{3}}.$ $$

Since $\mathbf{C}$ is a positive semi-definite matrix, $D_{i}\geq 0$ for all $i$. Thus for $\beta\geq 0$, we have $H^{\prime}(\beta)\leq 0$. Since the null-space of an orthogonal matrix is the singleton of the zero vector, the product $\tilde{g}=\mathbf{Q}^{\top}g$ is different than zero when $g\neq 0$, which holds by the assumption $x_{k}\notin\mathcal{X}_{\star}$. Therefore, there is at least one $\tilde{g}_{i}$ that is non-zero and thus, $H^{\prime}(\beta)\neq 0$.
The second derivative of $H$ is,

$$ $H^{\prime\prime}(\beta)=3\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}D_{i}}{(1+\beta D _{i})^{4}}.$ $$

By similar arguments used for the first derivative, we can show that $H^{\prime\prime}(\beta)>0$.
To conclude, we will show that $\lim_{\beta\to\infty}H(\beta)<0$. We discuss two cases separately.
Suppose $\mathbf{C}$ is not invertible. Then, there exists an entry $i$ of $\mathbf{D}$ such that $D_{i}=0$. Without loss of generality, suppose that the last entry $D_{d}$, is equal to 0 0. The same reasoning will apply if more than one entry is equal to 0 0. Taking the limit:

$$ $\displaystyle\lim_{\beta\to\infty}H(\beta)$ $\displaystyle=\lim_{\beta\to\infty}\frac{\beta^{2}}{2}\sum_{i=1}^{d}\frac{ \tilde{g}_{i}^{2}D_{i}}{(1+\beta D_{i})^{2}}-\beta\sum_{i=1}^{d}\frac{\tilde{g }_{i}^{2}}{1+\beta D_{i}}+\Delta_{k}$ $\displaystyle=\lim_{\beta\to\infty}\frac{\beta^{2}}{2}\sum_{i=1}^{d-1}\frac{ \tilde{g}_{i}^{2}D_{i}}{(1+\beta D_{i})^{2}}-\beta\sum_{i=1}^{d-1}\frac{\tilde {g}_{i}^{2}}{1+\beta D_{i}}-\beta\tilde{g}_{i}^{2}+\Delta_{k}$ $\displaystyle=\frac{1}{2}\sum_{i=1}^{d-1}\frac{\tilde{g}_{i}^{2}}{D_{i}}-\sum_ {i=1}^{d-1}\frac{\tilde{g}_{i}^{2}}{D_{i}}+\Delta_{k}+\lim_{\beta\to\infty}- \beta\tilde{g}_{i}^{2}$ $\displaystyle=-\infty$ $\displaystyle<0.$ $$

Now suppose that $\mathbf{C}$ is invertible. Then, $D_{i}>0$ for all $i$. Differently from before:

$$ $\displaystyle\lim_{\beta\to\infty}H(\beta)$ $\displaystyle=\lim_{\beta\to\infty}\frac{\beta^{2}}{2}\sum_{i=1}^{d}\frac{ \tilde{g}_{i}^{2}D_{i}}{(1+\beta D_{i})^{2}}-\beta\sum_{i=1}^{d}\frac{\tilde{g }_{i}^{2}}{1+\beta D_{i}}+\Delta_{k}$ $\displaystyle=\frac{1}{2}\sum_{i=1}^{d}\frac{\tilde{g}_{i}^{2}}{D_{i}}-\sum_{i =1}^{d}\frac{\tilde{g}_{i}^{2}}{D_{i}}+\Delta_{k}$ $\displaystyle=\frac{1}{2}\tilde{g}^{\top}\mathbf{D}^{-1}\tilde{g}-\tilde{g}^{ \top}\mathbf{D}^{-1}\tilde{g}+\Delta_{k}$ $\displaystyle=-\frac{1}{2}g^{\top}\mathbf{Q}\mathbf{D}^{-1}\mathbf{Q}^{\top}g+ \Delta_{k}$ $\displaystyle=-\frac{1}{2}g^{\top}\mathbf{C}^{-1}g+\Delta_{k}.$ $$

Recalling our definitions, the right hand side is:

$$ $\lim_{\beta\to\infty}H(\beta)=-\frac{1}{2}{\left\|\nabla f(x_{k})\right\|^{2}_ {[\mathbf{C}(x_{k})]^{-1}}}+f(x_{k})-f_{\star}.$ $$

By Lemma D.5, $\lim_{\beta\to\infty}H(\beta)\leq 0$. The inequality is strict when $f(x_{k})-f_{\star}\neq\frac{1}{2}{\left\|\nabla f(x_{k})\right\|^{2}_{\mathbf{
C}^{-1}}}$. In the case where equality holds, we have that $\lim_{\beta\to\infty}H(\beta)=0$. Therefore, $H$ does not have a root in the interval $[0,\infty)$ but the solution to the optimization problem is obtain when $\beta=\infty$. This corresponds to the following optimal solution $\bar{x}$:

$$ $\bar{x}=x_{k}-\mathbf{C}^{-1}(x_{k})\nabla f(x_{k}).$ (20) $$

Interestingly, under the same condition, LCD3 takes a step in the form $x_{k+1}=x_{k}-\mathbf{C}^{-1}(x_{k})\nabla f(x_{k})$. An example of a setting where the equality condition holds is when $f$ is a convex quadratic and $\mathbf{C}$ is the Hessian of $f$. One can see that the update step of LCD3 and LCD2 are equivalent to Newton’s method for that case so they both converge in one iteration.
∎

It may seem that using Newton’s root finding method is impractical because computing $H$ defined in Equation 18 for a given $\beta$ requires performing a matrix inversion. However, this can be avoided by computing the eigendecomposition of $\mathbf{C}(x_{k})$ at the beginning of each step of LCD2. Then each subsequent evaluation of $H$ done by Newton’s method sub-routine only requires inverting a diagonal matrix and not the full matrix. Thus, the main cost at each step of LCD2 is computing the eigendecomposition of $\mathbf{C}(x_{k})$ once, which in practice is much faster than computing the inverse. Furthermore, if $\mathbf{C}(x_{k})$ is a diagonal matrix, the eigendecomposition of $\mathbf{C}(x_{k})$ is itself so each step of LCD2 becomes even cheaper. Also, in practice, Newton’s method for root-finding is terminated when $\left\lvert H\right\rvert<\epsilon$. Therefore, in the case where

$$ $f(x_{k})-f_{\star}=\frac{1}{2}{\left\|\nabla f(x_{k})\right\|^{2}_{\mathbf{C}^ {-1}(x_{k})}},$ $$

the method will run until a large enough $\beta$ is obtained and the step will become numerically equivalent to $\bar{x}=x_{k}-\mathbf{C}^{-1}(x_{k})\nabla f(x_{k})$.

On a related note, Newton’s method is used to solve a similar constrained optimization problem for trust region methods, namely, the trust region sub-problem [Nocedal and Wright, ]. Practical versions of such algorithms do not iterate until convergence but are content with an approximate solution that can be obtained in two or three iterations.

###### Proposition B.1 (Properties of H 𝐻 H italic_H ) .

###### Proof.

#### B.2 Convergence proof

###### Lemma B.1 .

Let Assumption 2.1 hold. For all $k\geq 0$, the sequence $(x_{k})_{k\in\mathbb{N}}$ of LCD2 obeys the recursion:

$$ ${\left\|x_{k+1}-x_{\star}\right\|}^{2}\leq{\left\|x_{k}-x_{\star}\right\|}^{2} -{\left\|x_{k+1}-x_{k}\right\|}^{2}.$ $$

Hence, for any $k\geq 1$, we have

$$ $\min\limits_{0\leq t\leq k-1}\;{\left\|x_{t+1}-x_{t}\right\|}^{2}\leq\frac{{ \left\|x_{0}-x_{\star}\right\|}^{2}}{k}.$ (21) $$

###### Proof.

Let us write down the first-order optimality conditions for the optimization problem at Step 3 of LCD2:

$$ $\left\langle x_{k}-x_{k+1},x_{k+1}-y\right\rangle\geq 0,\qquad\forall y\in \mathcal{L}_{\mathbf{C}}(x_{k}).$ (22) $$

Since $x_{\star}\in\mathcal{L}_{\mathbf{C}}(x_{k})$, for any $k\geq 0$ we have

$$ $\displaystyle{\left\|x_{k+1}-x_{\star}\right\|}^{2}$ $\displaystyle={\left\|x_{k}-x_{\star}\right\|}^{2}-2\left\langle x_{k}-x_{k+1} ,x_{k}-x_{\star}\right\rangle+{\left\|x_{k+1}-x_{k}\right\|}^{2}$ $\displaystyle={\left\|x_{k}-x_{\star}\right\|}^{2}-2\left\langle x_{k}-x_{k+1} ,x_{k+1}-x_{\star}\right\rangle$ $\displaystyle\phantom{{\left\|x\right\|}}-2\left\langle x_{k}-x_{k+1},x_{k}-x_ {k+1}\right\rangle+{\left\|x_{k+1}-x_{k}\right\|}^{2}$ $\displaystyle={\left\|x_{k}-x_{\star}\right\|}^{2}-2\left\langle x_{k}-x_{k+1} ,x_{k+1}-x_{\star}\right\rangle-{\left\|x_{k+1}-x_{k}\right\|}^{2}$ $\displaystyle\stackrel{{\scriptstyle\mathclap{\eqref{eqn:FMP_lemma_cond}}}}{{ \leq}}{\left\|x_{k}-x_{\star}\right\|}^{2}-{\left\|x_{k+1}-x_{k}\right\|}^{2}.$ $$

Summing up these inequalities for $k=0,\dots,K-1$, we
obtain (21).
∎

Let us proceed to the proof of Theorem 4.2 for LCD2. We show that any if $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Assumption 2.1 for any $k\geq 1$ the iterates of LCD2 are such that:

$$ $\displaystyle\min\limits_{1\leq t\leq k}\;f(x_{t})-f_{\star}$ $\displaystyle\leq{L_{\mathbf{C}}{\left\|x_{0}-x_{\star}\right\|}^{2}\over 2k}.$ $$

###### Proof.

Since $x_{k+1}\in{\cal L_{\mathbf{C}}}(x_{k})$, we have

$$ $\displaystyle f(x_{k+1})$ $\displaystyle\stackrel{{\scriptstyle(\ref{eqn:upper bound main assumption})}}{ {\leq}}f(x_{k})+\left\langle\nabla f(x_{k}),x_{k+1}-x_{k}\right\rangle+\frac{1 }{2}{\left\|x_{k+1}-x_{k}\right\|}_{\mathbf{C}(x_{k})+L_{\mathbf{C}}\mathbf{I} }^{2}$ $\displaystyle=f(x_{k})+\left\langle\nabla f(x_{k}),x_{k+1}-x_{k}\right\rangle+ \frac{1}{2}{\left\|x_{k+1}-x_{k}\right\|}_{\mathbf{C}(x_{k})}^{2}$ $\displaystyle\qquad-\frac{1}{2}{\left\|x_{k+1}-x_{k}\right\|}_{\mathbf{C}(x_{k })}^{2}+\frac{1}{2}{\left\|x_{k+1}-x_{k}\right\|}_{\mathbf{C}(x_{k})+L_{ \mathbf{C}}\mathbf{I}}^{2}$ $\displaystyle=f(x_{k})+\left\langle\nabla f(x_{k}),x_{k+1}-x_{k}\right\rangle+ \frac{1}{2}{\left\|x_{k+1}-x_{k}\right\|}_{\mathbf{C}(x_{k})}^{2}+\frac{1}{2}{ \left\|x_{k+1}-x_{k}\right\|}_{L_{\mathbf{C}}\mathbf{I}}^{2}$ $\displaystyle\stackrel{{\scriptstyle(\ref{eqn:jjHHbuy87f898GDf_9f})}}{{\leq}}f _{\star}+\frac{1}{2}{\left\|x_{k+1}-x_{k}\right\|}_{L_{\mathbf{C}}\mathbf{I}}^ {2}$ $\displaystyle=f_{\star}+\frac{L_{\mathbf{C}}{\left\|x_{k+1}-x_{k}\right\|}^{2} }{2}.$ $$

By rearranging the above inequality and applying (21) from Lemma B.1, we get

$$ $\displaystyle\min\limits_{0\leq t\leq k-1}\;f(x_{t+1})-f_{\star}$ $\displaystyle\stackrel{{\scriptstyle(\ref{eqn:upper bound main assumption})}}{ {\leq}}\min\limits_{0\leq t\leq k-1}\;\frac{L_{\mathbf{C}}{\left\|x_{t+1}-x_{t }\right\|}^{2}}{2}$ $\displaystyle\stackrel{{\scriptstyle(\ref{eqn:FMP gets closer lemma rate})}}{{ \leq}}\frac{L_{\mathbf{C}}{\left\|x_{0}-x_{\star}\right\|}^{2}}{2k}.$ $$

∎

Remark. For quadratic functions Assumption 2.1 is satisfied with $\mathbf{C}(x)$ equal to the Hessian, and $L_{\mathbf{C}}=0$. Thus, LCD2 convergences in one step for this class of functions.

###### Lemma B.1 .

###### Proof.

###### Proof.

#### B.3 Closed-form solutions

In the main text, we argued that the update step of LCD2 has a closed-form solution in certain special cases. One interesting case is when $\mathbf{C}(x_{k})$ is a rank one matrix. In the setting of minimizing the sum of squares of absolutely convex functions, we present a special rank one matrix and the corresponding update step of LCD2. For general rank one matrices, the update step is not as interpretable or insightful so we leave out the computation.

Let $f(x)=\sum_{i=1}^{d}\phi_{i}^{2}(x)$ where $\phi_{i}:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex. Then $f$ satisfies inequality (5) with the following curvature mapping:

$$ $\mathbf{C}(y)=\frac{1}{2f(y)}\nabla f(y)\nabla f(y)^{\top}.$ $$

If we use the localization set defined by this curvature mapping, we can obtain a closed-form solution to the LCD2 update step. To simplify notation, let $g_{k}:=\nabla f(x_{k})$, $f_{k}:=f(x_{k})$, $\Delta_{k}:=f(x_{k})-f_{\star}$, $\mathbf{D}:=\mathbf{D}(x_{k})$ and $\mathbf{Q}=\mathbf{Q}(x_{k})$. Consider the orthogonal decomposition of $\mathbf{C}(x_{k})$:

$$ $\mathbf{D}(x_{k})=\operatorname{Diag}\left(\frac{g_{k}^{\top}g_{k}}{2f_{k}},\ 0,\ \dots,\ 0\right)\qquad\mathbf{Q}(x_{k})=\left[\frac{g_{k}}{\left\|g_{k} \right\|_{2}}\quad\hat{g}_{k,1}\quad\ldots\quad\hat{g}_{k,d-1}\right],$ $$

where $\hat{g}_{k,1},\ldots,\hat{g}_{k,d-1}$ are $d-1$ orthogonal eigenvectors that are all also orthogonal to $g_{k}$.

From Appendix B, we know that to obtain a closed-form solution of LCD2, we must find the positive root of the following function:

$$ $\displaystyle H(\alpha)$ $\displaystyle=\frac{\alpha^{2}}{2}g_{k}^{\top}\mathbf{Q}(\mathbf{I}+\alpha \mathbf{D})^{-1}\mathbf{D}(\mathbf{I}+\alpha\mathbf{D})^{-1}\mathbf{Q}^{\top}g _{k}-\alpha g_{k}^{\top}\mathbf{Q}(\mathbf{I}-\alpha\mathbf{D})^{-1}\mathbf{Q} ^{\top}g_{k}+\Delta_{k}$ $\displaystyle=\alpha^{2}\frac{f_{k}(g_{k}^{\top}g_{k})^{2}}{(2f_{k}+\alpha g_{ k}^{\top}g_{k})^{2}}-\alpha\frac{2f_{k}g_{k}^{\top}g_{k}}{2f_{k}+\alpha g_{k}^ {\top}g_{k}}+\Delta_{k}.$ $$

The second equality comes from simplifying the matrix multiplications and observing that,

$$ $(\mathbf{I}+\alpha\mathbf{D})^{-1}=\operatorname{Diag}\left(\frac{2f_{k}}{2f_{ k}+\alpha g_{k}^{\top}g_{k}},\ 0,\ \dots,\ 0\right)\qquad\mathbf{Q}^{\top}g_{k }=[{\left\|g_{k}\right\|}_{2}\quad 0\quad\ldots\quad 0]^{\top}$ $$

Let $v=g_{k}^{\top}g_{k}$. Since $\mathbf{C}$ is a rank-one matrix, we can simplify $H$ and realize that it is a quadratic function of $\alpha$,

$$ $H(\alpha)=\frac{f_{k}v^{2}}{(2f_{k}+\alpha v)^{2}}\alpha^{2}-\frac{2f_{k}v}{2f _{k}+\alpha v}\alpha+\Delta_{k}=0.$ $$

Therefore, we will have at most two roots and there must exist a unique positive root that corresponds to the solution of the problem (the optimalLagrange multiplier). We can solve this quadratic to obtain an interpretable update step for LCD2. To start, we multiply the entire equation by $(2f_{k}+\alpha v)^{2}$ and simplify to get,

$$ $(v^{2}\Delta_{k}-f_{k}v^{2})\alpha^{2}+\alpha(4f_{k}v\alpha-4f_{k}^{2}v)+4f_{k }^{2}\alpha=0.$ $$

By observing that $\Delta_{k}=f_{k}-f_{\star}$ we can simplify the expression further,

$$ $f_{\star}v^{2}\alpha^{2}+4f_{k}f_{\star}v\alpha-4f_{k}^{2}\Delta_{k}=0.$ $$

Therefore,

$$ $\displaystyle\alpha$ $\displaystyle=\frac{-4f_{k}f_{\star}v\pm\sqrt{(4f_{k}f_{\star}v)^{2}+4(f_{ \star}v)(4f_{k}^{2}\Delta_{k})}}{2f_{\star}v^{2}}=\frac{-2f_{k}f_{\star}\pm 2f _{k}\sqrt{f_{k}f_{\star}}}{f_{\star}v}.$ $$

To determine which root is positive we can rearrange the terms to see that,

$$ $\alpha=\frac{2f_{k}\sqrt{f_{\star}}(-\sqrt{f_{\star}}\pm\sqrt{f_{k}})}{f_{ \star}v}.$ $$

For $\alpha$ to be positive we must select the positive sign. Now recall from Appendix B, that the update step of LCD2 is defined as follows,

$$ $\displaystyle x_{k+1}$ $\displaystyle=x_{k}-\alpha(\mathbf{I}+\alpha\mathbf{C})^{-1}g_{k}$ $\displaystyle=x_{k}-\alpha\mathbf{Q}(\mathbf{I}+\alpha\mathbf{D})^{-1}\mathbf{ Q}^{\top}g_{k}$ $\displaystyle=x_{k}-\gamma_{k}g_{k},$ $$

where $\gamma_{k}=\alpha\frac{2f_{k}}{2f_{k}+\alpha v}$.
We substitute

$$ $\alpha=\frac{-2f_{k}f_{\star}+2f_{k}\sqrt{f_{k}f_{\star}}}{f_{\star}v}$ $$

into $\gamma_{k}$ to get

$$ $\displaystyle\gamma_{k}=\dfrac{2f_{k}\left(\frac{-2f_{k}f_{\star}+2f_{k}\sqrt{ f_{k}f_{\star}}}{f_{\star}v}\right)}{2f_{k}+v\left(\frac{-2f_{k}f_{\star}+2f_{ k}\sqrt{f_{k}f_{\star}}}{f_{\star}v}\right)}=\dfrac{2f_{k}\left(\frac{-2f_{k}f _{\star}+2f_{k}\sqrt{f_{k}f_{\star}}}{f_{\star}v}\right)}{\frac{2f_{k}\sqrt{f_ {k}f_{\star}}}{f_{\star}}}=\frac{2f_{k}-2\sqrt{f_{k}f_{\star}}}{v}.$ $$

Therefore, we conclude that the update step has the following form:

$$ $x_{k+1}=x_{k}-\frac{2\left(f(x_{k})-\sqrt{f(x_{k})f_{\star}}\right)}{\left\| \nabla f(x_{k})\right\|_{2}^{2}}\nabla f(x_{k}).$ $$

The update step of LCD2 differs from the classic Polyak stepsize in that we have $\sqrt{f(x_{k})f_{\star}}$ instead of $f_{\star}$ and we multiply by $2$.

Remark. In case $\mathbf{C}(x)=c\mathbf{I}$, for $c>0$, LCD2 reduces to LCD3. Thus, the closed-form solution exists.

### Appendix C Local Curvature Descent 3 ( LCD3 )

#### C.1 Derivation

Suppose the optimal value $f_{\star}$ is known. While the update step of LCD2 does not have a closed-form solution, the following update step does:

$$ $x_{k+1}=\arg\min_{x\in\mathcal{L}_{\mathbf{C}}(x_{k})}\frac{1}{2}{\left\|x-x_{ k}\right\|^{2}_{\mathbf{C}(x_{k})}},$ (23) $$

where $\mathcal{L}_{\mathbf{C}}(x_{k})$ is the same localization set defined in (17). Instead of using the $L_{2}$ norm, we can use the norm induced by $\mathbf{C}(x_{k})$. Hence, this algorithm is referred to as LCD3. The benefit of using a different norm is that we can obtain a closed-form solution to this constrained optimization algorithm.

The Lagrangian of this problem is

$$ $\mathscr{L}(x,\alpha):=\frac{1}{2}{\left\|x-x_{k}\right\|^{2}_{\mathbf{C}(x_{k })}}+\alpha\left(f(x_{k})+\left\langle\nabla f(x_{k}),x-x_{k}\right\rangle+ \frac{1}{2}{\left\|x-x_{k}\right\|^{2}_{\mathbf{C}(x_{k})}}-f_{\star}\right).$ $$

If $\alpha$ is the optimal multiplier, then for optimal $\bar{x}$ we get $\nabla_{x}\mathscr{L}(\bar{x},\bar{\alpha})=0$. The gradient is:

$$ $\nabla_{x}\mathscr{L}(\bar{x},\bar{\alpha})=\mathbf{C}(x_{k})(\bar{x}-x_{k})+ \bar{\alpha}\left(\nabla f(x_{k})+\mathbf{C}(x_{k})(\bar{x}-x_{k})\right)=0.$ $$

Isolating $\bar{x}$, we get:

$$ $\bar{x}=x_{k}-\frac{\bar{\alpha}}{1+\bar{\alpha}}\left[\mathbf{C}(x_{k})\right ]^{-1}\nabla f(x_{k}).$ (24) $$

Let $t:=\frac{\bar{\alpha}}{1+\bar{\alpha}}$. If $\bar{\alpha}=0$, $x_{k}\in\mathcal{L}_{\mathbf{C}}(x_{k})$, which means that the algorithm converged since $x_{k}\in\mathcal{L}_{\mathbf{C}}(x_{k})$ if and only if $x_{k}\in\mathcal{X}_{\star}$. Then, for a generic update, we will have $\bar{\alpha}\neq 0$.
Imposing $\nabla_{\alpha}\mathscr{L}(\bar{x},\bar{\alpha})=0$, which means that the constraint must be tight:

$$ $f(x_{k})+\left\langle\nabla f(x_{k}),\bar{x}-x_{k}\right\rangle+\frac{1}{2}{ \left\|x-x_{k}\right\|^{2}_{\mathbf{C}(x_{k})}}-f_{\star}=0.$ $$

Plugging $\bar{x}\equiv\bar{x}(t)\equiv\bar{x}(\bar{\alpha})$ into the equation gives

$$ $-t\left\langle\nabla f(x_{k}),\left[\mathbf{C}(x_{k})\right]^{-1}\nabla f(x_{k })\right\rangle+\frac{t^{2}}{2}\left\langle\nabla f(x_{k}),\left[\mathbf{C}(x_ {k})\right]^{-1}\nabla f(x_{k})\right\rangle=f_{\star}-f(x_{k}).$ $$

The two inner products are norms of the form ${\left\|\nabla f(x_{k})\right\|^{2}_{[\mathbf{C}(x_{k})]^{-1}}}$, and with more compact notation we can write:

$$ $t^{2}-2t+\frac{2(f(x_{k})-f_{\star})}{{\left\|\nabla f(x_{k})\right\|}_{[ \mathbf{C}(x_{k})]^{-1}}^{2}}=0.$ $$

This equation has two roots summing up to 2, but only one of them can be of the form $t=\frac{\bar{\alpha}}{1+\bar{\alpha}}$ since only one of them can be smaller than 1, with expression:

$$ $t=1-\sqrt{1-\frac{2(f(x_{k})-f_{\star})}{{\left\|\nabla f(x_{k})\right\|}_{[ \mathbf{C}(x_{k})]^{-1}}^{2}}}.$ (25) $$

Substituting back $t=\frac{\bar{\alpha}}{1+\bar{\alpha}}$ into (24), where $t$ is given by (25), leads to the method

$$ $x_{k+1}=x_{k}-\left(1-\sqrt{1-\frac{2(f(x_{k})-f_{\star})}{{\left\|\nabla f(x_ {k})\right\|}_{[\mathbf{C}(x_{k})]^{-1}}^{2}}}\right)\left[\mathbf{C}(x_{k}) \right]^{-1}\nabla f(x_{k}).$ $$

To realize that the scalar component of the stepsize is well-defined, it suffices to show that:

$$ $1-\frac{2(f(x_{k})-f_{\star})}{{\left\|\nabla f(x_{k})\right\|}_{[\mathbf{C}(x _{k})]^{-1}}^{2}}\geq 0,$ (26) $$

which follows by reordering the result of Lemma D.5 for the pair $(x_{k},x_{\star})$.

Then the update rule has a closed-form solution:

$$ $x_{k+1}=x_{k}-\gamma_{k}^{{\color[rgb]{0,0.88,0}\definecolor[named]{ pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12} \pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\sf LCD3}}\left[\mathbf{C}(x_{k}) \right]^{-1}\nabla f(x_{k}),\quad\gamma_{k}^{{\color[rgb]{0,0.88,0} \definecolor[named]{pgfstrokecolor}{rgb}{0,0.88,0}\pgfsys@color@cmyk@stroke{0. 91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill{0.91}{0}{0.88}{0.12}\sf LCD3}}:= \left(1-\sqrt{1-\frac{2(f(x_{k})-f_{\star})}{{\left\|\nabla f(x_{k})\right\|}_ {\mathbf{C}_{k}^{-1}}^{2}}}\right).$ (27) $$

In particular, the argument of the square root is always positive, making LCD3 well-defined. Routine (27) is promising: we apply a scalar stepsize $\gamma_{k}^{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{
0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill
{0.91}{0}{0.88}{0.12}\sf LCD3}}$ that is similar in spirit to Polyak’s in Equation 4, and “reorient” the gradient according to $\mathbf{C}_{k}^{-1}=\left[\mathbf{C}(x_{k})\right]^{-1}$.

Moreover, at each step, we aim to be as close as possible according to local upper-lower bounds on $f$. Experiments in section 8 and F, show that the algorithm converges, but is slower than LCD2.

#### C.2 Convergence for quadratics

Despite not converging in general, in special cases LCD3 reduces to Newton’s method. Below, we show that the update rule  (27) takes the form of Hessian times gradient.

Let $\phi_{i}(x)=|a_{i}^{\top}x-b_{i}|$, where $a_{i}\in\mathbb{R}^{d}$ and $b_{i}\in\mathbb{R}$, for $i\in\{1,\ldots,n\}$. We know from Example 7.1 that $\phi_{i}$ is absolutely convex. Then problem (9) becomes

$$ $\min_{x\in\mathbb{R}^{d}}\left\{f(x):=\frac{1}{n}\sum_{i=1}^{n}\left(a_{i}^{ \top}x-b_{i}\right)^{2}\right\}.$ $$

If $x$ is such that $\phi_{i}(x)\neq 0$ for all $i$, then $\nabla\phi_{i}(x)=\frac{a_{i}^{\top}x-b_{i}}{\phi_{i}(x)}a_{i}$. Therefore, in view of the computation in Section 7 we get

$$ $\displaystyle\mathbf{C}(x)$ $\displaystyle=\frac{2}{n}\sum_{i=1}^{n}\nabla\phi_{i}(x)\nabla\phi_{i}(x)^{ \top}=\frac{2}{n}\sum_{i=1}^{n}\frac{a_{i}^{\top}x-b_{i}}{\phi_{i}(x)}a_{i} \left(\frac{a_{i}^{\top}x-b_{i}}{\phi_{i}(x)}a_{i}\right)^{\top}$ $\displaystyle=\frac{2}{n}\sum_{i=1}^{n}\frac{(a_{i}^{\top}x-b_{i})^{2}}{\phi_{ i}^{2}(x)}a_{i}a_{i}^{\top}=\frac{2}{n}\sum_{i=1}^{n}a_{i}a_{i}^{\top}=\nabla^ {2}f(x).$ $$

Therefore, for least-squares problems, the LCD3 method of (27) moves in Newton’s direction. Furthermore, $\gamma_{k}^{{\color[rgb]{0,0.88,0}\definecolor[named]{pgfstrokecolor}{rgb}{
0,0.88,0}\pgfsys@color@cmyk@stroke{0.91}{0}{0.88}{0.12}\pgfsys@color@cmyk@fill
{0.91}{0}{0.88}{0.12}\sf LCD3}}=1$ since for quadratics we have the identity

$$ $f(x_{k})-f_{\star}=\frac{1}{2}{\left\|\nabla f(x_{k})\right\|}_{[\mathbf{C}(x_ {k})]^{-1}}^{2}.$ $$

Indeed, this follows from Lemma D.5 and the fact that for quadratics, equation (5) is an identity.
So, for least-squares problems, LCD3 reduces to Newton’s method, and converges in one step.

### Appendix D Properties & Examples

#### D.1 On the lower bound

For clarity, the statements are repeated, but correspond to Lemma 5.1 and Corollary 5.1.

###### Lemma D.1 .

Suppose $f,f_{1},f_{2}:\mathbb{R}^{d}\to\mathbb{R}$ satisfy Equation 5 with curvature mappings $\mathbf{C},\mathbf{C}_{1},\mathbf{C}_{2}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$, respectively. Then, the following functions satisfy Equation 5:

- (1)
$f+\alpha$ for $\alpha\in\mathbb{R}$, with $\mathbf{C}(\cdot)$;
- (2)
$\alpha f$ for $\alpha\geq 0$, with $\alpha\mathbf{C}(\cdot)$;
- (3)
$f_{1}+f_{2}$, with $\mathbf{C}_{1}(\cdot)+\mathbf{C}_{2}(\cdot)$.

###### Proof.

We prove each statement separately.
$(1)$ For any $x,y\in\mathbb{R}^{d}$, it holds:

$$ $\displaystyle g(x):=f(x)+\alpha$ $\displaystyle\geq f(y)+\left\langle\nabla f(y),x-y\right\rangle+\frac{1}{2}{ \left\|x-y\right\|^{2}_{\mathbf{C}(y)}}+\alpha$ $\displaystyle=g(y)+\left\langle\nabla g(y),x-y\right\rangle+\frac{1}{2}{\left \|x-y\right\|^{2}_{\mathbf{C}(y)}}.$ $$

$(2)$ Similarly, for all $x,y\in\mathbb{R}^{d}$, one has:

$$ $\displaystyle g(x):=\alpha f(x)$ $\displaystyle\geq\alpha\left(f(y)+\left\langle\nabla f(y),x-y\right\rangle+ \frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}\right)$ $\displaystyle=\alpha f(y)+\left\langle\alpha\nabla f(y),x-y\right\rangle+\frac {1}{2}{\left\|\alpha(x-y)\right\|^{2}_{\mathbf{C}(y)}}$ $\displaystyle=g(y)+\left\langle\nabla g(y),x-y\right\rangle+\frac{1}{2}{\left \|\alpha(x-y)\right\|^{2}_{\mathbf{C}(y)}}.$ $$

$(3)$ Concluding, for arbitrary vectors:

$$ $\displaystyle g(x):=f_{1}(x)+f_{2}(x)$ $\displaystyle\geq f_{1}(y)+\left\langle\nabla f_{1}(y),x-y\right\rangle+\frac{ 1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}_{1}(y)}}$ $\displaystyle\phantom{{}=f_{1}(y)}+f_{2}(y)+\left\langle\nabla f_{2}(y),x-y \right\rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}_{2}(y)}}$ $\displaystyle=g(y)+\left\langle\nabla g(y),x-y\right\rangle+\frac{1}{2}{\left \|x-y\right\|^{2}_{\mathbf{C}_{1}(y)+\mathbf{C}_{2}(y)}}.$ $$

∎

###### Corollary D.1 .

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies the lower bound of Equation 5 with curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$. Let $g:\mathbb{R}^{d}\to\mathbb{R}$ be a convex function. Then, $h(x)=f(x)+g(x)$ satisfies the lower bound with matrix $\mathbf{C}(y)$.

###### Proof.

Since $g$ is convex it satisfies the lower bound with matrix $\mathbf{C}(y)\equiv\mathbf{0}$. By Lemma D.1, $h$ satisfies the lower bound with $\mathbf{C}(y)+\mathbf{0}=\mathbf{C}(y)$.
∎

Another lemma used to construct functions that satisfy the lower bound is the following.

###### Lemma D.2 .

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Equation 5 with the curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$. Let $\mathbf{A}\in\mathbb{R}^{d\times m}$ and $b\in\mathbb{R}^{d}$. Then $g:\mathbb{R}^{m}\to\mathbb{R}$ where $g(x):=f(\mathbf{A}x+b)$ satisfies Equation 5 with curvature mapping $\tilde{\mathbf{C}}(y)=\mathbf{A}^{\top}\mathbf{C}(\mathbf{A}y+b)\mathbf{A}$.

###### Proof.

Without loss of generality, we can assume that $\mathbf{C}(y)$ is symmetric. Then,

$$ $\displaystyle g(x):=f(\mathbf{A}x+b)$ $\displaystyle\geq f(\mathbf{A}y+b)+\left\langle\nabla f(\mathbf{A}y+b),\mathbf {A}x+b-(\mathbf{A}y+b)\right\rangle$ $\displaystyle\phantom{{}=f(Ay+b)}+\frac{1}{2}\left\langle\mathbf{C}(\mathbf{A} y+b)(\mathbf{A}x+b-(\mathbf{A}y+b)),\mathbf{A}x+b-(\mathbf{A}y+b)\right\rangle$ $\displaystyle=f(\mathbf{A}y+b)+\left\langle\nabla f(\mathbf{A}y+b),\mathbf{A}( x-y)\right\rangle$ $\displaystyle\phantom{{}=f(Ay+b)}+\frac{1}{2}\left\langle\mathbf{C}(\mathbf{A} y+b)(\mathbf{A}(x-y)),\mathbf{A}(x-y)\right\rangle$ $\displaystyle=f(\mathbf{A}y+b)+\left\langle\mathbf{A}^{\top}\nabla f(\mathbf{A }y+b),x-y\right\rangle$ $\displaystyle\phantom{{}=f(Ay+b)}+\frac{1}{2}\left\langle\mathbf{A}^{\top} \mathbf{C}(\mathbf{A}y+b)\mathbf{A}(x-y),x-y\right\rangle$ $\displaystyle=g(y)+\left\langle\nabla g(y),x-y\right\rangle+\frac{1}{2}\left \langle\tilde{\mathbf{C}}(y)(x-y),x-y\right\rangle.$ $$

Considering the right hand side and the left hand side, we have recovered the claimed expression. The only missing detail is proving that $\tilde{\mathbf{C}}(\cdot)$ is positive semi-definite. Let $z\in\mathbb{R}^{m}$. Since $\mathbf{C}(y)$ is symmetric and positive semi-definite then $\mathbf{C}(y)=\mathbf{C}(y)^{\frac{1}{2}}\mathbf{C}(y)^{\frac{1}{2}}$ and $\mathbf{C}(y)^{\frac{1}{2}}$ is also symmetric. Therefore:

$$ $\displaystyle z^{\top}\tilde{\mathbf{C}}(y)z$ $\displaystyle=z^{\top}\mathbf{A}^{\top}\mathbf{C}(\mathbf{A}y+b)\mathbf{A}z$ $\displaystyle=z^{\top}\mathbf{A}^{\top}\mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}} \mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}}\mathbf{A}z$ $\displaystyle=((\mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}})^{\top}\mathbf{A}z)^{ \top}(\mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}}\mathbf{A}z)$ $\displaystyle=(\mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}}\mathbf{A}z)^{\top}( \mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}}\mathbf{A}z)$ $\displaystyle={\left\|\mathbf{C}(\mathbf{A}y+b)^{\frac{1}{2}}\mathbf{A}z\right \|}^{2}\geq 0.$ $$

By the arbitrariness of $z$, the matrix is positive semi-definite.
∎

###### Lemma D.3 .

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Equation 5 with curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$. Then the following inequalities hold for any $x,y\in\mathbb{R}^{d}$,

- (1)
$\left\langle\nabla f(y)-\nabla f(x),x-y\right\rangle\geq\frac{1}{2}{\left\|x-y
\right\|}^{2}_{\mathbf{C}(y)+\mathbf{C}(x)}$
- (2)
$\left\langle\nabla f(y)-\nabla f(x),x-y\right\rangle\geq\frac{1}{2}{\left\|x-y
\right\|}^{2}_{\mathbf{C}(y)}$
- (3)
$\left\langle\nabla f(y)-\nabla f(x),x-y\right\rangle\geq\frac{1}{2}{\left\|x-y
\right\|}^{2}_{\mathbf{C}(x)}$

###### Proof.

Let us present one proof in detail. The other two follow trivially.
$(1)$ By the definition of Bregman divergence:

$$ $\displaystyle\frac{1}{2}{\left\|x-y\right\|}^{2}_{\mathbf{C}(x)+\mathbf{C}(y)}$ $\displaystyle=\frac{1}{2}{\left\|x-y\right\|}_{\mathbf{C}(y)}^{2}+\frac{1}{2}{ \left\|y-x\right\|}_{\mathbf{C}(x)}^{2}$ $\displaystyle\leq D_{f}(x,y)+D_{f}(y,x)$ $\displaystyle=\left\langle\nabla f(x)-\nabla f(y),x-y\right\rangle.$ $$

$(2)$ Start with $(1)$ and note that $\frac{1}{2}{\left\|x-y\right\|}^{2}_{\mathbf{C}(x)+\mathbf{C}(y)}\geq\frac{1}{
2}{\left\|x-y\right\|}^{2}_{\mathbf{C}(y)}$.
$(2)$ Same as above but use that $\frac{1}{2}{\left\|x-y\right\|}^{2}_{\mathbf{C}(x)+\mathbf{C}(y)}\geq\frac{1}{
2}{\left\|x-y\right\|}^{2}_{\mathbf{C}(x)}$.
∎

###### Lemma D.4 .

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies

$$ ${\left\|x-y\right\|}^{2}_{\mathbf{C}(y)}\leq\left\langle\nabla f(x)-\nabla f(y ),x-y\right\rangle$ $$

for all $x,y\in\mathbb{R}^{d}$ with curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$.
Then $f$ satisfies Equation 5 with curvature mapping $\mathbf{C}(\cdot)$.

###### Proof.

By the fundamental theorem of calculus:

$$ $\displaystyle f(x)-f(y)$ $\displaystyle=\int_{0}^{1}\left\langle\nabla f(y+t(x-y)),x-y\right\rangle dt$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+\int_{0}^{1}\left \langle\nabla f(y+t(x-y))-\nabla f(y),x-y\right\rangle dt$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+\int_{0}^{1}\frac{1}{t} \left\langle\nabla f(y+t(x-y))-\nabla f(y),t(x-y)\right\rangle dt$ $\displaystyle\geq\left\langle\nabla f(y),x-y\right\rangle+\int_{0}^{1}\frac{1} {t}{\left\|t(x-y)\right\|}^{2}_{\mathbf{C}(y)}dt$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+{\left\|x-y\right\|}^{2 }_{\mathbf{C}(y)}\int_{0}^{1}tdt$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+\frac{1}{2}{\left\|x-y \right\|}^{2}_{\mathbf{C}(y)}.$ $$

Rearranging the terms we obtain that $D_{f}(x,y)\geq\frac{1}{2}{\left\|x-y\right\|}^{2}_{\mathbf{C}(y)}$ as desired.
∎

###### Lemma D.5 .

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Equation 5 with curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$. Suppose that $f$ is differentiable and $\mathbf{C}$ is non-singular. Then

$$ $\frac{1}{2}{\left\|\nabla f(x)-\nabla f(y)\right\|}^{2}_{\mathbf{C}(x)^{-1}} \geq D_{f}(x,y),\qquad\forall x,y\in\mathbb{R}^{d}.$ $$

###### Proof.

Fix $x\in\mathbb{R}^{d}$. Suppose $y\in\mathbb{R}^{d}$ is arbitrary. Let $\varphi(y):=f(y)-\left\langle\nabla f(x),y\right\rangle$. By construction, $\nabla\varphi(y)=\nabla f(y)-\nabla f(x)$. Using this fact, it can be shown that for any $u,v\in\mathbb{R}^{d}$, ${D_{f}(u,v)\geq\frac{1}{2}{\left\|u-v\right\|}_{\mathbf{C}(v)}^{2}}$. Therefore, $\varphi$ satisfies Equation 5 with curvature mapping $\mathbf{C}$. Hence, for $v\in\mathbb{R}^{d}$ we have that $\varphi(y)\geq G(y)$ where $G(y)$ is defined as

$$ $G(y):=\varphi(v)+\left\langle\nabla\varphi(v),y-v\right\rangle+\frac{1}{2}{ \left\|y-v\right\|}_{\mathbf{C}(v)}^{2}.$ $$

Observe that $\nabla\varphi(x)=0$. Since $\varphi$ is convex, $x$ is a minimizer of $\varphi$, and we the inequality below holds:

$$ $\displaystyle\varphi(x)=\inf_{y}\varphi(y)\geq\inf_{y}G(y).$ (28) $$

By computing the gradient of $G$ and setting it to zero, we find $\overline{y}=-\mathbf{C}(v)^{-1}\nabla\varphi(v)+v$ such that $\nabla G(\overline{y})=0$. Therefore,

$$ $\displaystyle f(x)-\left\langle\nabla f(x),x\right\rangle=\varphi(x)$ $\displaystyle\geq G(\overline{y})$ $\displaystyle=\varphi(v)-\left\langle\nabla\varphi(v),\mathbf{C}(v)^{-1}\nabla \varphi(v)\right\rangle+\frac{1}{2}{\left\|\mathbf{C}(v)^{-1}\nabla\varphi(v) \right\|}_{\mathbf{C}(v)}^{2}$ $\displaystyle=\varphi(v)-{\left\|\nabla\varphi(v)\right\|}_{\mathbf{C}^{-1}(v) }+\frac{1}{2}{\left\|\nabla\varphi(v)\right\|}_{\mathbf{C}^{-1}(v)}$ $\displaystyle=f(v)-\left\langle\nabla f(x),v\right\rangle-\frac{1}{2}{\left\| \nabla\varphi(v)\right\|}_{\mathbf{C}^{-1}(v)}$ $\displaystyle=f(v)-\left\langle\nabla f(x),v\right\rangle-\frac{1}{2}{\left\| \nabla f(v)-\nabla f(x)\right\|}_{\mathbf{C}^{-1}(v)}.$ $$

By rearranging the terms, we find our result since $x$ and $v$ are arbitrary:

$$ $\displaystyle\frac{1}{2}{\left\|\nabla f(v)-\nabla f(x)\right\|}_{\mathbf{C}^{ -1}(v)}$ $\displaystyle\geq f(v)-f(x)+\left\langle\nabla f(x),x\right\rangle-\left \langle\nabla f(x),v\right\rangle$ $\displaystyle=f(v)-f(x)+\left\langle\nabla f(x),x-v\right\rangle$ $\displaystyle=f(v)-f(x)-\left\langle\nabla f(x),v-x\right\rangle$ $\displaystyle=D_{f}(v,x).$ $$

∎

###### Lemma D.6 .

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Equation 5 with curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$. If $f$ is twice continuously differentiable, then

$$ $\mathbf{C}(x)\preceq\nabla^{2}f(x),$ $$

for all $x\in\mathbb{R}^{d}$.

###### Proof.

Let $x,y^{\prime}\in\mathbb{R}^{d}$ and $\lambda>0$. Since $f$ satisfies Equation 5 we can substitute $x+\lambda(y^{\prime}-x)$ and $\lambda(y^{\prime}-x)$ into the first inequality described in Lemma D.3, to find:

$$ $\displaystyle\left\langle\nabla f(x+\lambda(y^{\prime}-x))-\nabla f(x),\lambda (y^{\prime}-x)\right\rangle$ $\displaystyle\geq\frac{1}{2}{\left\|\lambda(y^{\prime}-x)\right\|}^{2}_{ \mathbf{C}(x)+\mathbf{C}(x+\lambda(y^{\prime}-x))}$ $\displaystyle=\frac{\lambda^{2}}{2}{\left\|y^{\prime}-x\right\|}^{2}_{\mathbf{ C}(x)+\mathbf{C}(x+\lambda(y^{\prime}-x))}.$ $$

By the Fundamental Theorem of Calculus, we further have that:

$$ $\left\langle\nabla f(x+\lambda(y^{\prime}-x))-\nabla f(x),y^{\prime}-x\right \rangle=\int_{0}^{1}\left\langle\nabla^{2}f(x+t\lambda(y^{\prime}-x))(\lambda( y^{\prime}-x)),y^{\prime}-x\right\rangle dt.$ $$

Dividing the first inequality by $\lambda^{2}$ on both sides we obtain an intermediate inequality:

$$ $\displaystyle\frac{1}{2}{\left\|y^{\prime}-x\right\|}_{\mathbf{C}(x)+\mathbf{C }(x+\lambda(y^{\prime}-x))}$ $\displaystyle\leq\frac{1}{\lambda}\left\langle\nabla f(x+\lambda(y^{\prime}-x) )-\nabla f(x),y^{\prime}-x\right\rangle$ $\displaystyle=\frac{1}{\lambda}\int_{0}^{1}\left\langle\nabla^{2}f(x+t\lambda( y^{\prime}-x))(\lambda(y^{\prime}-x)),y^{\prime}-x\right\rangle dt$ $\displaystyle=\int_{0}^{1}\left\langle\nabla^{2}f(x+t\lambda(y^{\prime}-x))(y^ {\prime}-x),y^{\prime}-x\right\rangle dt,$ $$

from which we take $\lambda\to 0$ of both sides to get an inequality between norms,

$$ $\displaystyle\frac{1}{2}{\left\|y^{\prime}-x\right\|}^{2}_{2\mathbf{C}(x)}$ $\displaystyle\leq\int_{0}^{1}\left\langle\nabla^{2}f(x)(y^{\prime}-x),y^{ \prime}-x\right\rangle dt$ $\displaystyle=\left\langle\nabla^{2}f(x)(y^{\prime}-x),y^{\prime}-x\right\rangle.$ $$

Thus, ${\left\|y^{\prime}-x\right\|^{2}_{\mathbf{C}(x)}}\leq\left\langle\nabla^{2}f(x
)(y^{\prime}-x),y^{\prime}-x\right\rangle$. Since $x,y^{\prime}$ are arbitrary this implies that ${\mathbf{C}(x)\preceq\nabla^{2}f(x)}$.
∎

###### Lemma D.1 .

###### Proof.

###### Corollary D.1 .

###### Proof.

###### Lemma D.2 .

###### Proof.

###### Lemma D.3 .

###### Proof.

###### Lemma D.4 .

###### Proof.

###### Lemma D.5 .

###### Proof.

###### Lemma D.6 .

###### Proof.

#### D.2 On the upper bound

We provide analogous lemmas involving functions that satisfy Equation 6.

###### Lemma D.7 .

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies Equation 6. Then for all $x,y\in\mathbb{R}^{d}$ we have,

$$ $\left\langle\nabla f(y)-\nabla f(x),y-x\right\rangle\leq\frac{1}{2}{\left\|x-y \right\|}_{\mathbf{C}(x)+\mathbf{C}(y)}^{2}+L_{\mathbf{C}}{\left\|x-y\right\|} ^{2}.$ $$

###### Proof.

Take the sum of the two Bregmann divergences:

$$ $\displaystyle\left\langle\nabla f(y)-\nabla f(x),y-x\right\rangle$ $\displaystyle=D_{f}(x,y)+D_{f}(y,x)$ $\displaystyle\leq\frac{1}{2}{\left\|x-y\right\|}_{\mathbf{C}(x)+L_{\mathbf{C}} \mathbf{I}}^{2}+\frac{1}{2}{\left\|x-y\right\|}_{\mathbf{C}(y)+L_{\mathbf{C}} \mathbf{I}}^{2}$ $\displaystyle=\frac{1}{2}{\left\|x-y\right\|}_{\mathbf{C}(x)+\mathbf{C}(y)}^{2 }+L_{\mathbf{C}}{\left\|x-y\right\|}^{2}.$ $$

∎

###### Lemma D.8 .

Suppose $f:\mathbb{R}^{d}\to\mathbb{R}$ satisfies the following inequality with constant $L_{\mathbf{C}}>0$ and curvature mapping $\mathbf{C}:\mathbb{R}^{d}\to\mathbb{S}^{d}_{+}$,

$$ $\left\langle\nabla f(x)-\nabla f(y),x-y\right\rangle\leq{\left\|x-y\right\|}^{ 2}_{\mathbf{C}(y)+L_{\mathbf{C}}\mathbf{I}}\qquad\forall x,y\in\mathbb{R}^{d}.$ $$

Then $f$ satisfies Equation 6 with curvature mapping $\mathbf{C}$ and constant $L_{\mathbf{C}}$.

###### Proof.

We invoke the Fundamental Theorem of Calculus:

$$ $\displaystyle f(x)-f(y)$ $\displaystyle=\int_{0}^{1}\left\langle\nabla f(y+t(x-y)),x-y\right\rangle \mathrm{d}t$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+\int_{0}^{1}\left \langle\nabla f(y+t(x-y))-\nabla f(y),x-y\right\rangle\mathrm{d}t$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+\int_{0}^{1}\frac{1}{t} \left\langle\nabla f(y+t(x-y))-\nabla f(y),t(x-y)\right\rangle\mathrm{d}t$ $\displaystyle\leq\left\langle\nabla f(y),x-y\right\rangle+\int_{0}^{1}\frac{1} {t}{\left\|t(x-y)\right\|}_{\mathbf{C}(y)+L_{\mathbf{C}}\mathbf{I}}^{2}\mathrm {d}t$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+{\left\|x-y\right\|}_{ \mathbf{C}(y)+L_{\mathbf{C}}\mathbf{I}}^{2}\int_{0}^{1}t\mathrm{d}t$ $\displaystyle=\left\langle\nabla f(y),x-y\right\rangle+\frac{1}{2}{\left\|x-y \right\|}_{\mathbf{C}(y)+L_{\mathbf{C}}\mathbf{I}}^{2}.$ $$

Rearranging the inequality above we get our result, $D_{f}(x,y)\leq\frac{1}{2}{\left\|x-y\right\|}_{\mathbf{C}(y)+L\mathbf{I}}^{2}$.
∎

###### Lemma D.9 .

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}$ is convex and satisfies Equation 6. Also, assume that $f$ is differentiable. Then,

$$ $\frac{1}{2}{\left\|\nabla f(x)-\nabla f(y)\right\|}^{2}_{(\mathbf{C}(x)+L_{ \mathbf{C}}\mathbf{I})^{-1}}\leq D_{f}(x,y)$ $$

###### Proof.

Fix $x\in\mathbb{R}^{d}$. Suppose $y\in\mathbb{R}^{d}$. Let $\varphi(y):=f(y)-\left\langle\nabla f(x),y\right\rangle$. By construction, ${\nabla\varphi(y)=\nabla f(y)-\nabla f(x)}$.

Using the above fact, we can show that $\varphi$ is convex and that for any $u,v\in\mathbb{R}^{d}$, we have ${D_{\varphi}(u,v)\leq\frac{1}{2}{\left\|u-v\right\|}^{2}_{\mathbf{C}(v)+L_{
\mathbf{C}}\mathbf{I}}}$. Therefore $\varphi$ satisfies Equation 6. Now, let $v\in\mathbb{R}^{d}$ be arbitrary. Since $\varphi$ satisfies Equation 6, $\varphi(y)\leq G(y)$ where

$$ $G(y):=\varphi(v)+\left\langle\nabla\varphi(v),y-v\right\rangle+\frac{1}{2}{ \left\|y-v\right\|}^{2}_{\mathbf{C}(v)+L_{\mathbf{C}}\mathbf{I}}.$ $$

Moreover, $x$ is a minimizer of $\varphi$ because $\nabla\varphi(x)=0$ and $\varphi$ is convex. Combining the last two facts,

$$ $\varphi(x)=\inf_{y}\varphi(y)\geq\inf_{y}G(y).$ $$

We minimize $G$ with respect to $y$ by finding a $\bar{y}\in\mathbb{R}^{d}$ such that $\nabla G(\bar{y})=0$. Since $\mathbf{C}(v)$ is positive semi-definite, $\mathbf{C}(v)+L_{\mathbf{C}}\mathbf{I}$ is non-singular. Then $\bar{y}=v-(\mathbf{C}(v)+L_{\mathbf{C}}\mathbf{I})^{-1}\varphi(v)$. Therefore,

$$ $\displaystyle f(x)-\left\langle\nabla f(x),x\right\rangle=\varphi(x)$ $\displaystyle\leq G(\bar{y})$ $\displaystyle=\varphi(v)-\left\langle\nabla\varphi(v),(\mathbf{C}(v)+L_{ \mathbf{C}}\mathbf{I})^{-1}\nabla\varphi(v)\right\rangle$ $\displaystyle\phantom{{}=f(Ay+b)}+\frac{1}{2}{\left\|(\mathbf{C}(v)+L_{\mathbf {C}}\mathbf{I})^{-1}\nabla\varphi(v)\right\|}^{2}_{\mathbf{C}(v)+L_{\mathbf{C} }\mathbf{I}}$ $\displaystyle=\varphi(v)-{\left\|\nabla\varphi(v)\right\|}^{2}_{(\mathbf{C}(v) +L_{\mathbf{C}}\mathbf{I})^{-1}}+\frac{1}{2}{\left\|\nabla\varphi(v)\right\|}^ {2}_{(\mathbf{C}(v)+L_{\mathbf{C}}\mathbf{I})^{-1}}$ $\displaystyle=\varphi(v)-\frac{1}{2}{\left\|\nabla\varphi(v)\right\|}^{2}_{( \mathbf{C}(v)+L_{\mathbf{C}}\mathbf{I})^{-1}}$ $\displaystyle=f(v)-\left\langle\nabla f(x),v\right\rangle-\frac{1}{2}{\left\| \nabla f(v)-\nabla f(x)\right\|}^{2}_{(\mathbf{C}(v)+L_{\mathbf{C}}\mathbf{I}) ^{-1}}.$ $$

Rearranging the terms we obtain

$$ $\displaystyle\frac{1}{2}{\left\|\nabla f(v)-\nabla f(x)\right\|}^{2}_{(\mathbf {C}(v)+L_{\mathbf{C}}\mathbf{I})^{-1}}$ $\displaystyle\leq f(v)-f(x)-\left\langle\nabla f(x),v\right\rangle+\left \langle\nabla f(x),x\right\rangle$ $\displaystyle=f(v)-f(x)-\left\langle\nabla f(x),v\right\rangle-\left\langle \nabla f(x),-x\right\rangle$ $\displaystyle=f(v)-f(x)-\left\langle\nabla f(x),v-x\right\rangle$ $\displaystyle=D_{f}(v,x).$ $$

Since $v,x$ were arbitrary, the claim is true.
∎

###### Lemma D.10 .

Suppose that $f:\mathbb{R}^{d}\to\mathbb{R}$ is convex and satisfies Equation 6. Also, assume that $f$ is twice differentiable. Then,

$$ $\nabla^{2}f(x)\preceq\mathbf{C}(x)+L\mathbf{I}.$ $$

###### Proof.

Suppose $x,y^{\prime}\in\mathbb{R}^{d}$ and $\lambda>0$. Since $f$ satisfies Equation 6, we can substitute $x+\lambda(y^{\prime}-x)$ and $\lambda(y^{\prime}-x)$ into Lemma D.7,

$$ $\displaystyle\left\langle\nabla f(x+\lambda(y^{\prime}-x))-\nabla f(x),\lambda (y^{\prime}-x)\right\rangle$ $\displaystyle\leq\frac{1}{2}{\left\|\lambda(y^{\prime}-x)\right\|}^{2}_{ \mathbf{C}(x)+\mathbf{C}(x+\lambda(y^{\prime}-x))+2L_{\mathbf{C}}\mathbf{I}}$ $\displaystyle=\frac{\lambda^{2}}{2}{\left\|y^{\prime}-x\right\|}^{2}_{\mathbf{ C}(x)+\mathbf{C}(x+\lambda(y^{\prime}-x))+2L_{\mathbf{C}}\mathbf{I}}.$ $$

The following equality is a direct application of the fundamental theorem of calculus:

$$ $\displaystyle\left\langle\nabla f(x+\lambda(y^{\prime}-x))-\nabla f(x),y^{ \prime}-x\right\rangle$ $\displaystyle=\int_{0}^{1}\left\langle\nabla^{2}f(x+t\lambda(y^{\prime}-x))( \lambda(y^{\prime}-x)),y^{\prime}-x\right\rangle dt$ $\displaystyle=\int_{0}^{1}\lambda\left\langle\nabla^{2}f(x+t\lambda(y^{\prime} -x))(y^{\prime}-x),y^{\prime}-x\right\rangle dt$ $$

Dividing the inequality by $\lambda^{2}$ on both sides:

$$ $\displaystyle\frac{1}{2}{\left\|y^{\prime}-x\right\|}^{2}_{\mathbf{C}(x)+ \mathbf{C}(x+\lambda(y^{\prime}-x))+2L_{\mathbf{C}}\mathbf{I}}$ $\displaystyle\geq\frac{1}{\lambda^{2}}\left\langle\nabla f(x+\lambda(y^{\prime }-x))-\nabla f(x),\lambda(y^{\prime}-x)\right\rangle$ $\displaystyle=\frac{1}{\lambda}\left\langle\nabla f(x+\lambda(y^{\prime}-x))- \nabla f(x),y^{\prime}-x\right\rangle$ $\displaystyle=\frac{1}{\lambda}\int_{0}^{1}\lambda\left\langle\nabla^{2}f(x+t \lambda(y^{\prime}-x))(y^{\prime}-x),y^{\prime}-x\right\rangle dt$ $\displaystyle=\int_{0}^{1}\left\langle\nabla^{2}f(x+t\lambda(y^{\prime}-x))(y^ {\prime}-x),y^{\prime}-x\right\rangle dt.$ $$

It suffices to take limits $\lambda\to 0$ to get that:

$$ $\displaystyle\frac{1}{2}{\left\|y^{\prime}-x\right\|}^{2}_{\mathbf{C}(x)+ \mathbf{C}(x)+2L_{\mathbf{C}}\mathbf{I}}$ $\displaystyle\geq\int_{0}^{1}\left\langle\nabla^{2}f(x)(y^{\prime}-x),y^{ \prime}-x\right\rangle dt$ $\displaystyle=\left\langle\nabla^{2}f(x)(y^{\prime}-x),y^{\prime}-x\right\rangle,$ $$

allowing us to conclude with:

$$ $\displaystyle\frac{1}{2}{\left\|y^{\prime}-x\right\|}^{2}_{\mathbf{C}(x)+ \mathbf{C}(x)+2L_{\mathbf{C}}\mathbf{I}}$ $\displaystyle=\frac{1}{2}{\left\|y^{\prime}-x\right\|}^{2}_{2\mathbf{C}(x)+2L_ {\mathbf{C}}\mathbf{I}}$ $\displaystyle=\left\langle(\mathbf{C}(x)+L_{\mathbf{C}}\mathbf{I})(y^{\prime}- x),y^{\prime}-x\right\rangle$ $\displaystyle\geq\left\langle\nabla^{2}f(x)(y^{\prime}-x),y^{\prime}-x\right\rangle.$ $$

Since $y^{\prime},x\in\mathbb{R}^{d}$ are arbitrary, we proved the claim: $\nabla^{2}f(x)\preceq\mathbf{C}(x)+L_{\mathbf{C}}\mathbf{I}$.
∎

###### Lemma D.7 .

###### Proof.

###### Lemma D.8 .

###### Proof.

###### Lemma D.9 .

###### Proof.

###### Lemma D.10 .

###### Proof.

#### D.3 Lower bound examples

###### Lemma D.11 .

Suppose $p\geq 2$. Let $f:\mathbb{R}^{d}\to\mathbb{R}$ where $f(x)={\left\|x\right\|}^{p}_{p}$. Then $f$ satisfies Equation 5 in Assumption 2.1 with curvature mapping

$$ $\mathbf{C}(y)=p\operatorname{Diag}{(\left\lvert y_{1}\right\rvert^{p-2},\ldots ,\left\lvert y_{d}\right\rvert^{p-2})}=\frac{1}{p-1}\nabla^{2}f(y).$ $$

###### Proof.

When $p=2$, we have that $\mathbf{C}(y)=2\mathbf{I}$. Then $f$ satisfies Equation 5 because ${\left\|x\right\|}^{2}$ is $2$-strongly-convex.
Now suppose $p>2$. For arbitrary $x,y\in\mathbb{R}^{d}$, an application of Young’s Inequality yields

$$ $\dfrac{({\left\|x\right\|}_{p}^{2})^{\frac{p}{2}}}{\frac{p}{2}}+\dfrac{({\left \|y\right\|}_{p}^{p-2})^{\frac{p}{p-2}}}{\frac{p}{p-2}}\geq{\left\|x\right\|}_ {p}^{2}{\left\|y\right\|}_{p}^{p-2}.$ $$

Rearranging, we obtain:

$$ ${\left\|x\right\|}_{p}^{p}-\frac{p}{2}{\left\|x\right\|}_{p}^{2}{\left\|y \right\|}_{p}^{p-2}+\left(\frac{p}{2}-1\right){\left\|y\right\|}_{p}^{p}\geq 0.$ (29) $$

By applying Hölder’s inequality, we get:

$$ $\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right\rvert^{ p-2}\leq{\left\|x\right\|}_{p}^{2}{\left\|y\right\|}_{p}^{p-2},$ (30) $$

and thus,

$$ $-\frac{p}{2}{\left\|x\right\|}_{p}^{2}{\left\|y\right\|}_{p}^{p-2}\leq-\frac{p }{2}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right \rvert^{p-2}.$ $$

By adding ${\left\|x\right\|}_{p}^{p}+\left(\frac{p}{2}-1\right){\left\|y\right\|}_{p}^{p}$ to both sides of Equation 30 and using Equation 29 we get,

$$ ${\left\|x\right\|}_{p}^{p}-\frac{p}{2}\sum_{i=1}^{d}\left\lvert x_{i}\right \rvert^{2}\left\lvert y_{i}\right\rvert^{p-2}+\left(\frac{p}{2}-1\right){\left \|y\right\|}_{p}^{p}\geq 0.$ $$

To derive the result, we begin by rearranging the above inequality:

$$ $\displaystyle{\left\|x\right\|}_{p}^{p}$ $\displaystyle\geq\frac{p}{2}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2} \left\lvert y_{i}\right\rvert^{p-2}-\left(\frac{p}{2}-1\right){\left\|y\right \|}_{p}^{p}$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{p}^{p}+\frac{p}{2}\sum_{i=1}^{d}\left\lvert x_{i}\right \rvert^{2}\left\lvert y_{i}\right\rvert^{p-2}$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+p\sum_{i= 1}^{d}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{i}-p\sum_{i=1}^{d}y_{i}\left \lvert y_{i}\right\rvert^{p-2}x_{i}+\frac{p}{2}{\left\|y\right\|}_{p}^{p}+ \frac{p}{2}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i} \right\rvert^{p-2}.$ $$

After reordering, we find:

$$ $\begin{split}{\left\|x\right\|}_{p}^{p}\geq&{\left\|y\right\|}_{p}^{p}+p\sum_{ i=1}^{d}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{i}-p\sum_{i=1}^{d}y_{i}^{2} \left\lvert y_{i}\right\rvert^{p-2}\\ &\phantom{{\left\|x\right\|}}-p\sum_{i=1}^{d}y_{i}\left\lvert y_{i}\right \rvert^{p-2}x_{i}+\frac{p}{2}{\left\|y\right\|}_{p}^{p}+\frac{p}{2}\sum_{i=1}^ {d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right\rvert^{p-2}.\end{split}$ $$

By performing some basic algebra and observing that $\frac{\partial f}{\partial y_{i}}=py_{i}\left\lvert y_{i}\right\rvert^{p-2}$, we obtain our result:

$$ $\displaystyle{\left\|x\right\|}_{p}^{p}$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\sum_{i=1}^{d}py_{i}\left\lvert y_{i} \right\rvert^{p-2}(x_{i}-y_{i})-p\sum_{i=1}^{d}y_{i}\left\lvert y_{i}\right \rvert^{p-2}x_{i}+\frac{p}{2}{\left\|y\right\|}_{p}^{p}+\frac{p}{2}\sum_{i=1}^ {d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right\rvert^{p-2}$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\sum_{i=1}^{d}py_{i}\left\lvert y_{i} \right\rvert^{p-2}(x_{i}-y_{i})+\frac{p}{2}\sum_{i=1}^{d}\left\lvert y_{i} \right\rvert^{p}-p\sum_{i=1}^{d}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{i}+ \frac{p}{2}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i} \right\rvert^{p-2}$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\sum_{i=1}^{d}py_{i}\left\lvert y_{i} \right\rvert^{p-2}(x_{i}-y_{i})+\frac{1}{2}\left\langle\mathbf{C}(y)y,y\right \rangle-\left\langle\mathbf{C}(y)y,x\right\rangle+\frac{1}{2}\left\langle \mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\sum_{i=1}^{d}py_{i}\left\lvert y_{i} \right\rvert^{p-2}(x_{i}-y_{i})+\frac{1}{2}\left\langle\mathbf{C}(y)(x-y),(x-y )\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}.$ $$

∎

###### Lemma D.12 .

Suppose $p\geq 2$. Let $f:\mathbb{R}^{d}\to\mathbb{R}$ where $f(x)={\left\|x\right\|}^{p}_{p}$. Then $f$ satisfies Equation 5 in Assumption 2.1 with curvature mapping $\mathbf{C}(y)$ were the $(i,j)^{\text{th}}$ entry of $\mathbf{C}(y)$ is

$$ $\mathbf{C}_{i,j}(y)=\frac{p}{{\left\|y\right\|}_{p}^{p}}y_{i}y_{j}\left\lvert y _{i}\right\rvert^{p-2}\left\lvert y_{j}\right\rvert^{p-2},$ $$

or alternatively, in matrix form:

$$ $\mathbf{C}(y)=\frac{1}{p{\left\|y\right\|}_{p}^{p}}\nabla f(y)\nabla f(y)^{ \top}.$ $$

###### Proof.

When $p=2$ we get that $\mathbf{C}(y)=\frac{2}{{\left\|y\right\|}^{2}}yy^{\top}$. Since ${\left\|x\right\|}^{2}$ is the square of ${\left\|x\right\|}$ which is absolutely convex, $f(x)={\left\|x\right\|}^{2}$ satisfies Equation 5 because the curvature mapping $\mathbf{C}$ corresponds to the mapping obtained from absolute convexity.
Now suppose $p>2$. Again by Hölder’s Inequality, we have that

$$ $\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert\left\lvert y_{i}\right\rvert^{p-1} \leq{\left\|x\right\|}_{p}{\left\|y\right\|}_{p}^{p-1}.$ (31) $$

We can lower bound the left-hand side in the following manner:

$$ $\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert\left\lvert y_{i}\right\rvert^{p-1} =\sum_{i=1}^{d}\left\lvert x_{i}y_{i}^{p-1}\right\rvert=\sum_{i=1}^{d}\left \lvert x_{i}y_{i}y_{i}^{p-2}\right\rvert=\sum_{i=1}^{d}\left\lvert x_{i}y_{i} \left\lvert y_{i}\right\rvert^{p-2}\right\rvert\geq\left\lvert\sum_{i=1}^{d}x_ {i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}\right\rvert.$ $$

Combining this inequality with Inequality (31) and squaring both sides we get,

$$ ${\left\|x\right\|}_{p}^{2}{\left\|y\right\|}_{p}^{2p-2}\geq\left(\sum_{i=1}^{d }\left\lvert x_{i}\right\rvert\left\lvert y_{i}\right\rvert^{p-1}\right)^{2} \geq\left(\left\lvert\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p- 2}\right\rvert\right)^{2}=\left(\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y_{i} \right\rvert^{p-2}\right)^{2}.$ $$

Then we multiply both sides by $-\frac{p}{2}$,

$$ $-\frac{p}{2}{\left\|x\right\|}_{p}^{2}{\left\|y\right\|}_{p}^{2p-2}\leq-\frac{ p}{2}\left(\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}\right)^ {2}.$ (32) $$

From Lemma D.11, we know an application of Young’s Inequality with some rearranging yields the following:

$$ ${\left\|x\right\|}_{p}^{p}+\left(\frac{p}{2}-1\right){\left\|y\right\|}_{p}^{p }-\frac{p}{2}{\left\|x\right\|}_{p}^{2}{\left\|y\right\|}_{p}^{p-2}\geq 0.$ $$

Now multiply both sides by ${\left\|y\right\|}_{p}^{p}$,

$$ ${\left\|x\right\|}_{p}^{p}{\left\|y\right\|}_{p}^{p}+\left(\frac{p}{2}-1\right ){\left\|y\right\|}_{p}^{2p}-\frac{p}{2}{\left\|x\right\|}_{p}^{2}{\left\|y \right\|}_{p}^{2p-2}\geq 0.$ (33) $$

Adding ${\left\|x\right\|}_{p}^{p}{\left\|y\right\|}_{p}^{p}+\left(\frac{p}{2}-1\right
){\left\|y\right\|}_{p}^{2p}$ to both sides of Equation 32 and together with Equation 33 we have that,

$$ ${\left\|x\right\|}_{p}^{p}{\left\|y\right\|}_{p}^{p}+\left(\frac{p}{2}-1\right ){\left\|y\right\|}_{p}^{2p}-\frac{p}{2}(\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y _{i}\right\rvert^{p-2})^{2}\geq 0.$ $$

Rearranging this inequality and proceeding with the following steps we obtain the claim.

$$ $\displaystyle{\left\|x\right\|}_{p}^{p}$ $\displaystyle\geq\left(1-\frac{p}{2}\right){\left\|y\right\|}_{p}^{p}+\frac{p} {2{\left\|y\right\|}_{p}^{p}}\left(\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y_{i} \right\rvert^{p-2}\right)^{2}$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{p}^{p}+\frac{p}{2{\left\|y\right\|}_{p}^{p}}\left(\sum_{ i=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}\right)\left(\sum_{j=1}^{ d}x_{j}y_{j}\left\lvert y_{j}\right\rvert^{p-2}\right)$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{p}^{p}+\frac{p}{2{\left\|y\right\|}_{p}^{p}}\sum_{i=1}^{ d}\sum_{j=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{j}y_{j}\left \lvert y_{j}\right\rvert^{p-2}$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{p}^{p}+\frac{p}{2{\left\|y\right\|}_{p}^{p}}\sum_{i=1}^{ d}\sum_{j=1}^{d}x_{i}y_{i}y_{j}\left\lvert y_{i}\right\rvert^{p-2}\left\lvert y _{j}\right\rvert^{p-2}x_{j}$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2{\left\|y\right\|}_{p}^{p}}{\left\|y\right\|}_{p}^{2p}+\frac{1}{2}\left \langle\mathbf{C}(y)x,x\right\rangle,$ $$

The last term seems complicated but can be expressed as a matrix inner product. Continuing,

$$ $\displaystyle{\left\|x\right\|}_{p}^{p}$ $\displaystyle\geq{\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{ p}{2{\left\|y\right\|}_{p}^{p}}\left(\sum_{i=1}^{d}\left\lvert y_{i}\right \rvert^{p}\right)\left(\sum_{j=1}^{d}\left\lvert y_{j}\right\rvert^{p}\right)+ \frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2{\left\|y\right\|}_{p}^{p}}\left(\sum_{i=1}^{d}\sum_{j=1}^{d}\left\lvert y_{i }\right\rvert^{p}\left\lvert y_{j}\right\rvert^{p}\right)+\frac{1}{2}\left \langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{p}{ 2{\left\|y\right\|}_{p}^{p}}\left(\sum_{i=1}^{d}\sum_{j=1}^{d}y_{i}y_{i}y_{j} \left\lvert y_{i}\right\rvert^{p-2}\left\lvert y_{j}\right\rvert^{p-2}y_{j} \right)+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+\frac{1}{ 2}\left\langle\mathbf{C}(y)y,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}( y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+p\sum_{i= 1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}-p\sum_{i=1}^{d}x_{i}y_{i} \left\lvert y_{i}\right\rvert^{p-2}$ $\displaystyle\phantom{+{\left\|x\right\|}}+\frac{1}{2}\left\langle\mathbf{C}(y )y,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+p\sum_{i= 1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}-\frac{p}{{\left\|y\right\| }_{p}^{p}}\left(\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2} \right)\left(\sum_{j=1}^{d}\left\lvert y_{j}\right\rvert^{p}\right)$ $\displaystyle\phantom{+{\left\|x\right\|}}+\frac{1}{2}\left\langle\mathbf{C}(y )y,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle.$ $$

To finalize, we proceed with the last few equalities:

$$ $\displaystyle{\left\|x\right\|}_{p}^{p}$ $\displaystyle\geq{\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+p\sum_ {i=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}-\frac{p}{{\left\|y \right\|}_{p}^{p}}\left(\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^ {p-2}\right)\left(\sum_{j=1}^{d}y_{j}y_{j}\left\lvert y_{j}\right\rvert^{p-2}\right)$ $\displaystyle\phantom{+{\left\|x\right\|}}+\frac{1}{2}\left\langle\mathbf{C}(y )y,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+p\sum_{i= 1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}-\frac{p}{{\left\|y\right\| }_{p}^{p}}\sum_{i=1}^{d}\sum_{j=1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^ {p-2}y_{j}\left\lvert y_{j}\right\rvert^{p-2}y_{j}$ $\displaystyle\phantom{+{\left\|x\right\|}}+\frac{1}{2}\left\langle\mathbf{C}(y )y,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}-p{\left\|y\right\|}_{p}^{p}+p\sum_{i= 1}^{d}x_{i}y_{i}\left\lvert y_{i}\right\rvert^{p-2}-\left\langle\mathbf{C}(y)x ,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)y,y\right\rangle+\frac{1}{ 2}\left\langle\mathbf{C}(y)x,x\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}+p\sum_{i=1}^{d}x_{i}y_{i}\left\lvert y _{i}\right\rvert^{p-2}-p\sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p}+\frac{ 1}{2}\left\langle\mathbf{C}(x-y),x-y\right\rangle$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\sum_{i=1}^{d}py_{i}\left\lvert y_{i} \right\rvert^{p-2}(x_{i}-y_{i})+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C} (y)}}$ $\displaystyle={\left\|y\right\|}_{p}^{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}.$ $$

∎

###### Lemma D.13 .

Suppose $p\geq 2$. The function $f(x)={\left\|x\right\|}^{p}$ satisfies Equation 5 with either of the two curvature mappings:

$$ $(1)\ \mathbf{C}(y)=p{\left\|y\right\|}_{2}^{p-2}\mathbf{I}.\qquad(2)\ \mathbf{ C}(y)=p{\left\|y\right\|}_{2}^{p-4}yy^{\top}.$ $$

###### Proof.

$(1)$. When $p=2$, we have $\mathbf{C}(y)=2\mathbf{I}$. Therefore, $f$ satisfies Equation 5 because ${\left\|x\right\|}^{2}$ is $2$-strongly-convex.
Now suppose $p>2$. By applying Young’s Inequality we get that:

$$ $\dfrac{({\left\|x\right\|}^{2})^{\frac{p}{2}}}{\frac{p}{2}}+\dfrac{({\left\|y \right\|}^{p-2})^{\frac{p}{p-2}}}{\frac{p}{p-2}}\geq{\left\|x\right\|}^{2}{ \left\|y\right\|}^{p-2},$ $$

and rearranging

$$ ${\left\|x\right\|}^{p}+\left(\frac{p}{2}-1\right){\left\|y\right\|}^{p}\geq \frac{p}{2}{\left\|y\right\|}^{p-2}{\left\|x\right\|}^{2}.$ $$

We get our result from the above inequality and by observing that $\nabla f(y)=p{\left\|y\right\|}_{2}^{p-2}y$.

$$ $\displaystyle{\left\|x\right\|}_{2}^{p}$ $\displaystyle\geq\left(1-\frac{p}{2}\right){\left\|y\right\|}_{2}^{p}+\frac{p} {2}{\left\|y\right\|}_{2}^{p-2}{\left\|x\right\|}_{2}^{2}$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{2}^{p-2}{\left\|x\right\|}_{2}^{2}+\frac{p}{2}{\left\|y \right\|}_{2}^{p}$ $\displaystyle={\left\|y\right\|}_{2}^{p}+p{\left\|y\right\|}_{2}^{p-2}\left \langle x,y\right\rangle-p{\left\|y\right\|}_{2}^{p-2}\left\langle x,y\right \rangle-p{\left\|y\right\|}_{2}^{p}+\frac{p}{2}{\left\|y\right\|}_{2}^{p-2}{ \left\|x\right\|}_{2}^{2}+\frac{p}{2}{\left\|y\right\|}_{2}^{p}$ $\displaystyle={\left\|y\right\|}_{2}^{p}+p{\left\|y\right\|}_{2}^{p-2}\left \langle x,y\right\rangle-p{\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{ p-2}\left\langle x,y\right\rangle+\frac{p}{2}{\left\|y\right\|}_{2}^{p-2}\left \langle x,x\right\rangle+\frac{p}{2}{\left\|y\right\|}_{2}^{p-2}\left\langle y ,y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}+p{\left\|y\right\|}_{2}^{p-2}\left \langle x,y\right\rangle-p{\left\|y\right\|}_{2}^{p-2}\left\langle y,y\right \rangle-\left\langle\mathbf{C}(y)x,y\right\rangle+\frac{1}{2}\left\langle \mathbf{C}(y)x,x\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)y,y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}+p{\left\|y\right\|}_{2}^{p-2}\left \langle x,y\right\rangle-p{\left\|y\right\|}_{2}^{p-2}\left\langle y,y\right \rangle+\frac{1}{2}\left\langle\mathbf{C}(y)(x-y),x-y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}+\left\langle p{\left\|y\right\|}_{2}^ {p-2}y,x-y\right\rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}$ $\displaystyle={\left\|y\right\|}_{2}^{p}+\left\langle p{\left\|y\right\|}_{2}^ {p-2}y,x-y\right\rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}$ $\displaystyle={\left\|y\right\|}_{2}^{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}.$ $$

$(2)$ When $p=2$, we have $\mathbf{C}(y)=\frac{p}{{\left\|y\right\|}_{2}^{2}}yy^{\top}$. Since ${\left\|x\right\|}^{2}$ is a square of an absolutely convex function, it satisfies Equation 5 with curvature mapping $\mathbf{C}(y)$. For more details, refer to section 7 and E.
Suppose that $p>2$. As done previously, we can use Young’s Inequality to obtain:

$$ ${\left\|x\right\|}^{p}+\left(\frac{p}{2}-1\right){\left\|y\right\|}^{p}\geq \frac{p}{2}{\left\|y\right\|}^{p-2}{\left\|x\right\|}^{2}.$ (34) $$

Moreover, by Cauchy-Schwarz:

$$ ${\left\|x\right\|}_{2}{\left\|y\right\|}_{2}\geq\left\lvert\left\langle x,y \right\rangle\right\rvert\Longrightarrow{\left\|x\right\|}_{2}^{2}{\left\|y \right\|}_{2}^{2}\geq(\left\langle x,y\right\rangle)^{2}.$ $$

Multiplying both sides by $-\frac{p}{2}{\left\|y\right\|}^{p-4}$ we get,

$$ $-\frac{p}{2}{\left\|x\right\|}^{2}{\left\|y\right\|}^{p-2}\leq-\frac{p}{2}{ \left\|y\right\|}^{p-4}(\left\langle x,y\right\rangle)^{2},$ $$

Adding ${\left\|x\right\|}_{2}^{p}+\left(\frac{p}{2}-1\right){\left\|y\right\|}_{2}^{p}$ to both sides and by using Equation 34,

$$ ${\left\|x\right\|}^{p}-\frac{p}{2}{\left\|y\right\|}^{p-4}(\left\langle x,y \right\rangle)^{2}+\left(\frac{p}{2}-1\right){\left\|y\right\|}^{p}\geq 0.$ $$

We can reorder the terms to obtain the result:

$$ $\displaystyle{\left\|x\right\|}_{2}^{p}$ $\displaystyle\geq\left(1-\frac{p}{2}\right){\left\|y\right\|}_{2}^{p}+\frac{p} {2}{\left\|y\right\|}_{2}^{p-4}(\left\langle x,y\right\rangle)^{2}$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{2}^{p-4}(\left\langle x,y\right\rangle)^{2}+\frac{p}{2}{ \left\|y\right\|}_{2}^{p}$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+\frac{p}{ 2}{\left\|y\right\|}_{2}^{p-4}x^{\top}yy^{\top}x+\frac{p}{2}{\left\|y\right\|} _{2}^{p-4}y^{\top}yy^{\top}y$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+\frac{1}{ 2}\left\langle\mathbf{C}(y)x,x\right\rangle+\frac{1}{2}\left\langle\mathbf{C}( y)y,y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+p{\left\| y\right\|}_{2}^{p-2}\left\langle x,y\right\rangle-p{\left\|y\right\|}_{2}^{p-2 }\left\langle x,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right \rangle+\frac{1}{2}\left\langle\mathbf{C}(y)y,y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+p{\left\| y\right\|}_{2}^{p-2}\left\langle x,y\right\rangle-p{\left\|y\right\|}_{2}^{p-4 }x^{\top}yy^{\top}y+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle+\frac {1}{2}\left\langle\mathbf{C}(y)y,y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+p{\left\| y\right\|}_{2}^{p-2}\left\langle x,y\right\rangle-\left\langle\mathbf{C}(y)x,y \right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle+\frac{1}{2} \left\langle\mathbf{C}(y)y,y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p}+p{\left\| y\right\|}_{2}^{p-2}\left\langle x,y\right\rangle+\left\langle\mathbf{C}(y)(x- y),x-y\right\rangle$ $\displaystyle={\left\|y\right\|}_{2}^{p}-p{\left\|y\right\|}_{2}^{p-2}\left \langle y,y\right\rangle+p{\left\|y\right\|}_{2}^{p-2}\left\langle x,y\right \rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}$ $\displaystyle={\left\|y\right\|}_{2}^{p}+\left\langle p{\left\|y\right\|}_{2}^ {p-2}y,x-y\right\rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}$ $\displaystyle={\left\|y\right\|}_{2}^{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}.$ $$

∎

###### Lemma D.14 .

Suppose $p\geq 2$ and let $f:\mathbb{R}^{d}\to\mathbb{R}$ be defined as $f(x)=\left\|x\right\|_{p}^{2}$. Then $f$ satisfies Equation 5 with the following curvature mapping:

$$ $\mathbf{C}(y)=\frac{2}{\left\|y\right\|^{p-2}_{p}}\operatorname{Diag}(\left \lvert y_{1}\right\rvert^{p-2},\ \dots,\ \left\lvert y_{d}\right\rvert^{p-2})$ $$

###### Proof.

Using Holder’s inequality we can see that,

$$ $\left(\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right \rvert^{p-2}\right)^{p}\leq\left(\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{ p}\right)^{2}\left(\sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p-2}\right)^{p -2}=\left\|x\right\|^{2p}_{p}\left\|y\right\|^{p(p-2)}_{p}$ $$

We raise both sides to the power of $\frac{1}{p}$ and proceed by rearranging some terms:

$$ $\displaystyle\left\|x\right\|^{2}_{p}$ $\displaystyle\geq\frac{1}{\left\|y\right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert x _{i}\right\rvert^{2}\left\lvert y_{i}\right\rvert^{p-2}$ $\displaystyle=\left\|y\right\|^{2}_{p}-\left\|y\right\|^{2}_{p}+\frac{1}{\left \|y\right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left \lvert y_{i}\right\rvert^{p-2}$ $\displaystyle=\left\|y\right\|^{2}_{p}-\frac{1}{\left\|y\right\|^{p-2}_{p}} \sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p}+\frac{1}{\left\|y\right\|^{p-2 }_{p}}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right \rvert^{p-2}$ $\displaystyle=\left\|y\right\|^{2}_{p}-\frac{2}{\left\|y\right\|^{p-2}_{p}} \sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p}+\frac{1}{\left\|y\right\|^{p-2 }_{p}}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2}\left\lvert y_{i}\right \rvert^{p-2}+\frac{1}{\left\|y\right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert y_{ i}\right\rvert^{p}$ $\displaystyle=\left\|y\right\|^{2}_{p}+\frac{2}{\left\|y\right\|^{p-2}_{p}} \sum_{i=1}^{d}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{i}-\frac{2}{\left\|y \right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p}+\frac{1}{ \left\|y\right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2} \left\lvert y_{i}\right\rvert^{p-2}$ $\displaystyle\phantom{+\left\|x\right\|}-\frac{2}{\left\|y\right\|^{p-2}_{p}} \sum_{i=1}^{d}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{i}+\frac{1}{\left\|y \right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p}$ $$

We can arrive at our result by realizing that the last three terms are equal to ${\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}$ and the middle two terms are equal to $\left\langle\nabla f(y),x-y\right\rangle$. Observe that $\frac{\partial f}{\partial y_{i}}=\frac{2}{\left\|y\right\|^{p-2}_{p}}y_{i}
\left\lvert y_{i}\right\rvert^{p-2}$. Therefore,

$$ $\displaystyle\left\|x\right\|^{2}_{p}$ $\displaystyle\geq\left\|y\right\|^{2}_{p}+\sum_{i=1}^{d}\frac{2y_{i}\left \lvert y_{i}\right\rvert^{p-2}}{\left\|y\right\|^{p-2}_{p}}(x_{i}-y_{i})+\frac {1}{\left\|y\right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert x_{i}\right\rvert^{2} \left\lvert y_{i}\right\rvert^{p-2}$ $\displaystyle\phantom{\left\|x\right\|\qquad}-\frac{2}{\left\|y\right\|^{p-2}_ {p}}\sum_{i=1}^{d}y_{i}\left\lvert y_{i}\right\rvert^{p-2}x_{i}+\frac{1}{\left \|y\right\|^{p-2}_{p}}\sum_{i=1}^{d}\left\lvert y_{i}\right\rvert^{p}$ $\displaystyle=\left\|y\right\|^{2}_{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}\left\langle\mathbf{C}(y)x,x\right\rangle-\left\langle \mathbf{C}(y)x,y\right\rangle+\frac{1}{2}\left\langle\mathbf{C}(y)y,y\right\rangle$ $\displaystyle=\left\|y\right\|^{2}_{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}\left\langle\mathbf{C}(y)(x-y),x-y\right\rangle$ $\displaystyle=\left\|y\right\|^{2}_{p}+\left\langle\nabla f(y),x-y\right \rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{\mathbf{C}(y)}}$ $$

∎

###### Lemma D.15 .

Suppose $p\geq 1$. Let $g:\mathbb{R}^{d}\to\mathbb{R}$ be $g(x)={\left\|x\right\|}_{p}$. Then $f\coloneq g^{2}$ satisfies Equation 5 with the following curvature mapping:

$$ $\mathbf{C}(y)=2\nabla g(y)\nabla g(y)^{\top}.$ $$

###### Proof.

By Lemma E.2, $g$ is absolutely convex for $p\geq 1$. Therefore, $g^{2}$ satisfies Equation 5 with curvature mapping $\mathbf{C}$.
∎

###### Lemma D.11 .

###### Proof.

###### Lemma D.12 .

###### Proof.

###### Lemma D.13 .

###### Proof.

###### Lemma D.14 .

###### Proof.

###### Lemma D.15 .

###### Proof.

#### D.4 Lower and upper bound examples

###### Lemma D.16 .

Let $\mathbf{G}$ be a symmetric positive semi-definite matrix. Let $f:\mathbb{R}^{d}\to\mathbb{R}$ where ${f(x)={\left\|x\right\|^{2}_{\mathbf{G}}}}$. Then $f$ satisfies 2.1 with curvature mapping $\mathbf{C}(y)\equiv 2\mathbf{G}$ and constant $L_{\mathbf{C}}=0$.

###### Proof.

We start by computing:

$$ $\displaystyle 0$ $\displaystyle={\left\|y\right\|^{2}_{\mathbf{G}}}-2{\left\|y\right\|^{2}_{ \mathbf{G}}}+{\left\|y\right\|^{2}_{\mathbf{G}}}$ $\displaystyle=-{\left\|x\right\|^{2}_{\mathbf{G}}}+{\left\|x\right\|^{2}_{ \mathbf{G}}}+{\left\|y\right\|^{2}_{\mathbf{G}}}-2{\left\|y\right\|^{2}_{ \mathbf{G}}}+{\left\|y\right\|^{2}_{\mathbf{G}}}$ $\displaystyle=-{\left\|x\right\|^{2}_{\mathbf{G}}}+{\left\|y\right\|^{2}_{ \mathbf{G}}}-2\left\langle\mathbf{G}y,y\right\rangle+\left\langle\mathbf{G}y,y \right\rangle+\left\langle\mathbf{G}x,x\right\rangle$ $\displaystyle=-{\left\|x\right\|^{2}_{\mathbf{G}}}+{\left\|y\right\|^{2}_{ \mathbf{G}}}-2\left\langle\mathbf{G}y,y\right\rangle+\left\langle\mathbf{G}y,y \right\rangle+\left\langle\mathbf{G}x,x\right\rangle$ $\displaystyle=-{\left\|x\right\|^{2}_{\mathbf{G}}}+{\left\|y\right\|^{2}_{ \mathbf{G}}}+2\left\langle\mathbf{G}y,x\right\rangle-2\left\langle\mathbf{G}y, y\right\rangle+\left\langle\mathbf{G}y,y\right\rangle-2\left\langle\mathbf{G}y ,x\right\rangle+\left\langle\mathbf{G}x,x\right\rangle$ $\displaystyle=-{\left\|x\right\|^{2}_{\mathbf{G}}}+{\left\|y\right\|^{2}_{ \mathbf{G}}}+\left\langle 2\mathbf{G}y,x-y\right\rangle+\left\langle\mathbf{G} y,y\right\rangle-2\left\langle\mathbf{G}y,x\right\rangle+\left\langle\mathbf{G }x,x\right\rangle$ $\displaystyle=-{\left\|x\right\|^{2}_{\mathbf{G}}}+{\left\|y\right\|^{2}_{ \mathbf{G}}}+\left\langle 2\mathbf{G}y,x-y\right\rangle+\frac{1}{2}2{\left\|x- y\right\|^{2}_{\mathbf{G}}}.$ $$

Rearranging the terms we get

$$ $\displaystyle{\left\|x\right\|^{2}_{\mathbf{G}}}$ $\displaystyle={\left\|y\right\|^{2}_{\mathbf{G}}}+\left\langle 2\mathbf{G}y,x- y\right\rangle+\frac{1}{2}2{\left\|x-y\right\|^{2}_{\mathbf{G}}}$ $\displaystyle={\left\|y\right\|^{2}_{\mathbf{G}}}+\left\langle\nabla f(y),x-y \right\rangle+\frac{1}{2}{\left\|x-y\right\|^{2}_{2\mathbf{C}(y)}}.$ $$

∎

###### Lemma D.17 .

Let $p\geq 2$. Suppose $g:\mathbb{R}^{d}\to\mathbb{R}$ with $g(x)={\left\|x\right\|}_{p}^{2}$. Let $f\coloneqq g^{2}$. Then $f$ satisfies 2.1 with constant $L_{\mathbf{C}}=2(p-1)$ and either of the two curvature mappings:

$$ $\mathbf{B}(y)=\frac{2}{\left\|y\right\|^{p-2}_{p}}\operatorname{Diag}(\left \lvert y_{1}\right\rvert^{p-2},\ \dots,\ \left\lvert y_{d}\right\rvert^{p-2}) \qquad\mathbf{B}(y)=2\nabla g(y)\nabla g(y)^{\top}.$ $$

###### Proof.

In Lemma D.14, we proved that $f$ satisfies inequality (5) with the abovementioned curvature mappings. Now we will show that $f$ is smooth so it satisfies inequality (6). For $p=2$. it is clear that $f$ is $2$-smooth. We focus on the case where $p>2$.

Since $p>2$ we have that $1<q<2$ where $q=\frac{p}{p-1}$. Kakade et al. [] proved that $h(x)=\frac{1}{2}\left\|x\right\|^{2}_{q}$ is strongly-convex with respect to the $L_{q}$ norm with $\mu=q-1$. We also know that $L_{p}$ norms are a decreasing function of $p$. Therefore, $h(x)=\frac{1}{2}\left\|x\right\|^{2}_{q}$ is also strongly-convex with respect to the $L_{2}$ norm because $\left\|x-y\right\|^{2}_{2}\leq\left\|x-y\right\|^{2}_{q}$:

$$ $\displaystyle\frac{1}{2}\left\|x\right\|^{2}_{q}$ $\displaystyle\geq\frac{1}{2}\left\|y\right\|^{2}_{q}+\left\langle\nabla h(y),x -y\right\rangle+\frac{1}{2}\mu\left\|x-y\right\|^{2}_{q}$ $\displaystyle\geq\frac{1}{2}\left\|y\right\|^{2}_{q}+\left\langle\nabla h(y),x -y\right\rangle+\frac{1}{2}\mu\left\|x-y\right\|^{2}_{2}$ $$

The Frenchel conjugate of $\frac{1}{2}\left\|\cdot\right\|^{2}_{q}$ is $\frac{1}{2}\left\|\cdot\right\|^{2}_{p}$ because the the dual norm of $\left\|\cdot\right\|_{q}$ is $\left\|\cdot\right\|_{p}$. Kakade et al. [] showed that if $h$ is $\mu$-strongly-convex then the Frenchel conjugate of $h$ is $\frac{1}{\mu}$-smooth. Therefore, $\frac{1}{2}\left\|x\right\|^{2}_{p}$ is $L$-smooth with $L=\frac{1}{q-1}=p-1$. Thus, $f(x)=\left\|x\right\|^{2}_{p}$ is smooth with constant ${2(p-1)}$.
∎

###### Lemma D.18 .

Suppose $a,b\in\mathbb{R}$ and $a\neq 0$ and $b>0$. The function $f:\mathbb{R}\to\mathbb{R}$ defined as

$$ $f(x)=\sqrt{ax^{4}+b}$ $$

satisfies the upper and lower bounds in 2.1 with $\mathbf{C}(y)=\frac{2ay^{2}}{f(y)}$ and $L_{\mathbf{C}}=\sqrt{8a}$.

###### Proof.

Observe that $x^{2}+y^{2}\geq 2x^{2}y^{2}$. Multiply both sides by $ab$ we get $ab(x^{2}+y^{2})\geq 2abx^{2}y^{2}$. Then we add $a^{2}x^{4}y^{4}+b^{2}$ to both sides,

$$ $a^{2}x^{4}y^{4}+abx^{2}+aby^{2}+b^{2}\geq a^{2}x^{4}y^{4}+2abx^{2}y^{2}+b^{2}.$ $$

We can write this equivalently as,

$$ $(ax^{4}+b)(ay^{4}+b)\geq(b+ax^{2}y^{2})^{2}.$ $$

Then taking the square root of both sides,

$$ $\displaystyle\sqrt{(ax^{4}+b)(ay^{4}+b)}$ $\displaystyle\geq b+ax^{2}y^{2}=ay^{4}+b-ay^{4}+ax^{2}y^{2}.$ $$

Rearranging the terms,

$$ $\displaystyle\sqrt{ax^{4}+b}\sqrt{ay^{4}+b}$ $\displaystyle\geq ay^{4}+b-ay^{4}+ax^{2}y^{2}$ $\displaystyle=ay^{4}+b-2ay^{4}+ax^{2}y^{2}+ay^{4}$ $\displaystyle=ay^{4}+b+2axy^{3}-2ay^{4}+ax^{2}y^{2}-2axy^{3}+ay^{4}$ $\displaystyle=ay^{4}+b+2ay^{3}(x-y)+ay^{2}(x^{2}-2xy+y^{2})$ $\displaystyle=ay^{4}+b+2ay^{3}(x-y)+\frac{1}{2}2ay^{2}(x-y)^{2}.$ $$

Divide both sides by $\sqrt{ay^{4}+b}$ to obtain our result,

$$ $\sqrt{ax^{4}+b}\geq\sqrt{ay^{4}+b}+\frac{2ay^{3}}{\sqrt{ay^{4}+b}}(x-y)+\frac{ 1}{2}\frac{2ay^{2}}{\sqrt{ax^{4}+b}}(x-y)^{2}.$ $$

To compute $L_{\mathbf{C}}$, note that $f$ is $L$-smooth so we can find an upper bound on $f^{\prime\prime}$ which is given by $L_{\mathbf{C}}=\sqrt{8a}$.
∎

###### Lemma D.19 .

Suppose $\delta>0$. Suppose $h:\mathbb{R}\to\mathbb{R}$ is such that:

$$ $h(x)=\begin{cases}\frac{1}{2}x^{2}&\left\lvert x\right\rvert\leq\delta\\ \delta(\left\lvert x\right\rvert-\frac{1}{2}\delta)&\left\lvert x\right\rvert> \delta\end{cases}.$ $$

Let $f=h^{2}$. Then $f$ satisfies (2.1) with constant $L_{\mathbf{C}}=2\delta^{2}$ and curvature mapping

$$ $\mathbf{C}(y)=\begin{cases}y^{2}&\left\lvert y\right\rvert\leq\delta\\ \delta^{2}&\left\lvert y\right\rvert>\delta\end{cases}$ $$

Notice that $L_{\mathbf{C}}$ is less than the $L$-smoothness constant of $f$, which is $3\delta^{2}$ (the tightest bound on the second derivative of $f$).

###### Proof.

First, we will prove that $f$ satisfies inequality (5). We will split the proof into four cases and prove the inequality holds in each case.

Case $\left\lvert x\right\rvert,\left\lvert y\right\rvert\leq\delta$. We know $x^{4}+y^{4}\geq 2x^{2}y^{2}$. We divide both sides by $4$ and rearrange the terms,

$$ $\displaystyle\frac{1}{4}x^{4}\geq-\frac{1}{4}y^{4}+\frac{1}{2}x^{2}y^{2}$ $\displaystyle=\frac{1}{4}y^{4}-y^{4}+\frac{1}{2}y^{4}+\frac{1}{2}x^{2}y^{2}$ $\displaystyle=\frac{1}{4}y^{4}-y^{4}+\frac{1}{2}y^{4}+\frac{1}{2}x^{2}y^{2}+xy ^{3}-xy^{3}$ $\displaystyle=\frac{1}{4}y^{4}-y^{4}+xy^{3}+\frac{1}{2}y^{2}(x^{2}-2xy+y^{2})$ $\displaystyle=\frac{1}{4}y^{4}-y^{3}(x-y)+\frac{1}{2}y^{2}(x-y)^{2}.$ $$

We have our result because $f^{\prime}(y)=y^{3}$ for $\left\lvert y\right\rvert\leq\delta$.

Case $\left\lvert x\right\rvert\geq\delta$ and $\left\lvert y\right\rvert\leq\delta$. For any $\left\lvert y\right\rvert\leq\delta$ define $r:\mathbb{R}\to\mathbb{R}$ as the following,

$$ $r(x)=\frac{y^{4}}{4}+\frac{\delta^{4}}{4}+\delta^{2}x^{2}-\delta^{3}\left \lvert x\right\rvert-\frac{x^{2}y^{2}}{2}$ $$

First, we need to show that $r(x)\geq 0$.
Suppose $x\geq\delta$. When $x=\delta$,

$$ $r(x)=\frac{y^{4}}{4}-\frac{y^{2}\delta^{2}}{2}+\frac{\delta^{4}}{4}=\frac{1}{4 }(y^{2}-\delta^{2})\geq 0.$ $$

Therefore, for $x>\delta$, if we show that $r^{\prime}(x)\geq 0$ then $r(x)\geq 0$. By a simple computation, we get that

$$ $r^{\prime}(x)=2\delta^{2}x-\delta^{3}-\frac{xy^{2}}{2}.$ $$

Since $x\geq\delta$ then obviously $x\geq\frac{2}{3}\delta$ so $\frac{3}{2}x-\delta\geq 0$. Rearranging the terms and multiplying the entire inequality by $\delta$ we get that

$$ $2\delta^{2}x-\delta^{3}-\frac{x\delta^{2}}{2}\geq 0.$ $$

It is easy to show that $-y^{2}\geq-\delta^{2}$ because $\left\lvert y\right\rvert\leq\delta$. Therefore,

$$ $r^{\prime}(x)=2\delta^{2}x-\delta^{3}-\frac{xy}{2}\geq 2\delta^{2}x-\delta^{3} -\frac{x\delta^{2}}{2}\geq 0.$ $$

Now suppose $x\leq-\delta$. Observe that $r(-\delta)=r(\delta)\geq 0$. Thus, if we show that for $x\leq-\delta$, $r^{\prime}(x)\leq 0$ then $r(x)\geq 0$. For $x\leq-\delta$, we have that

$$ $r^{\prime}(x)=2\delta^{2}x+\delta^{3}-\frac{xy^{2}}{2}.$ $$

Notice that $y^{2}\leq\delta^{2}$ because $\left\lvert y\right\rvert\leq\delta$. Then we have that $2\delta^{2}-\frac{y^{2}}{2}\geq\frac{3\delta^{2}}{2}$. Multiplying both sides of this inequality by $x$ we obtain,

$$ $x\left(2\delta^{2}-\frac{y^{2}}{2}\right)\leq\frac{3\delta^{2}x}{2}\leq\frac{3 \delta^{3}}{2}\leq-\delta^{3}.$ $$

The inequality was reversed because $x\leq-\delta<0$ and the second inequality also follows from $x\leq-\delta$. Rearranging the terms in this inequality we see that

$$ $r^{\prime}(x)=2\delta^{2}x-\delta^{3}-\frac{xy^{2}}{2}\leq 0.$ $$

Therefore, we have shown that $r(x)\geq 0$ for arbitrary $abs{y}\leq\delta$. Then by rearranging the terms in $r$, we have that

$$ $\delta^{2}x^{2}-\delta^{3}\left\lvert x\right\rvert+\frac{\delta^{4}}{4}\geq- \frac{y^{4}}{4}+\frac{x^{2}y^{2}}{2}.$ $$

The left-hand side is equal to $\delta^{2}(\left\lvert x\right\rvert-\frac{1}{2}\delta)=f(x)$. In the previous case, we showed that the right-hand side is equal to $\frac{1}{4}y^{4}-y^{3}(x-y)+\frac{1}{2}y^{2}(x-y)^{2}$. Therefore, we have our result.

Case $\left\lvert x\right\rvert,\left\lvert y\right\rvert\geq\delta$. First, we show that the following inequality holds:

$$ $x^{2}-2xy+y^{2}-2\delta\left(\left\lvert x\right\rvert-x\frac{y}{\left\lvert y \right\rvert}\right)\geq 0.$ (35) $$

For $x,y\geq\delta$ and $x,y\leq-\delta$ it is easy to show because $(x-y)^{2}\geq 0$. Now suppose $x\geq\delta$ and $y\leq-\delta$. Then we must show that

$$ $x^{2}-2xy+y^{2}-4\delta x\geq 0.$ $$

Since $y\leq-\delta$ we have that $(x-y)^{2}\geq(x+\delta)^{2}$. Therefore,

$$ $(x-y)^{2}-4\delta x\geq(x+\delta)^{2}-4\delta x=(x-\delta)^{2}\geq 0.$ $$

Now suppose $x\leq-\delta$ and $y\geq\delta$. Similar to before, we need to show

$$ $x^{2}-2xy+y^{2}+4\delta x\geq 0.$ $$

Since $y\geq\delta$ we obtain $4xy\leq 4\delta x$ by multiplying both sides by $4x$ and reversing the inequality because $x\leq-\delta<0$. Therefore,

$$ $(x-y)^{2}+4\delta x\geq(x-y)^{2}+4xy=(x+y)^{2}\geq 0.$ $$

As a result, we have shown inequality (35) holds. We can rewrite the inequality as

$$ $\frac{x^{2}}{2}-xy+\frac{y^{2}}{2}-\delta\left\lvert x\right\rvert+\delta x \frac{y}{\left\lvert y\right\rvert}\geq 0.$ $$

Moving some terms to the right-hand side we get,

$$ $\displaystyle x^{2}-\delta\left\lvert x\right\rvert+\frac{\delta^{2}}{4}$ $\displaystyle\geq-\frac{-y^{2}}{2}+\frac{\delta^{2}}{4}+xy+\frac{x^{2}}{2}- \delta\frac{xy}{\left\lvert y\right\rvert}$ $\displaystyle=\left(\left\lvert y\right\rvert-\frac{1}{2}\delta\right)^{2}+2xy -\delta\frac{xy}{\left\lvert y\right\rvert}-2y^{2}+\delta\left\lvert y\right \rvert+\frac{x^{2}}{2}-xy+\frac{y^{2}}{2}.$ $$

Recall, that $f^{\prime}(y)=2\delta^{2}\left(\left\lvert y\right\rvert-\frac{1}{2}\delta
\right)\frac{y}{\left\lvert y\right\rvert}$. Observe that we can factor the left-hand side of the inequality and after multiplying both sides by $\delta^{2}$ we get our result:

$$ $\displaystyle\delta^{2}\left(\left\lvert x\right\rvert-\frac{1}{2}\delta\right )^{2}$ $\displaystyle\geq\delta^{2}\left(\left\lvert y\right\rvert-\frac{1}{2}\delta \right)^{2}+2\delta^{2}xy-\delta^{2}\frac{xy}{\left\lvert y\right\rvert}-2 \delta^{2}y^{2}+\delta^{3}\left\lvert y\right\rvert+\frac{\delta^{2}}{2}x^{2}- \delta^{2}xy+\frac{\delta^{2}}{2}y^{2}$ $\displaystyle=\delta^{2}\left(\left\lvert y\right\rvert-\frac{1}{2}\delta \right)^{2}+2\delta^{2}\left(\left\lvert y\right\rvert-\frac{1}{2}\delta\right )\frac{y}{\left\lvert y\right\rvert}(x-y)+\frac{1}{2}\delta^{2}(x-y)^{2}$ $$

The case where $\left\lvert x\right\rvert\leq\delta,\left\lvert y\right\rvert\geq\delta$ is similar to the previous cases. Using some elementary calculus, one can show that

$$ $\frac{x^{4}}{4}+\frac{\delta^{2}y^{2}}{2}-\frac{\delta^{4}}{4}-\delta^{2}xy- \frac{\delta^{2}x^{2}}{2}+\delta^{3}x\geq 0.$ $$

Rearranging the terms above directly leads to the result.

Now we show that $f$ satisfies inequality (6) with $L_{\mathbf{C}}=2\delta^{2}$. In the case where $\left\lvert y\right\rvert\geq\delta$, $L_{\mathbf{C}}+\mathbf{C}(y)=3\delta^{2}$ is the $L$-smoothness constant of $f$ so the inequality holds. We consider the case where $\left\lvert y\right\rvert\leq\delta$.

Case $\left\lvert x\right\rvert,\left\lvert y\right\rvert\leq\delta$. Then $xy\leq\left\lvert xy\right\rvert\leq\delta^{2}$ so $x^{2}+xy\leq 2\delta^{2}$. Adding $y^{2}$ to both sides and multiplying by $(x-y)^{2}$ we obtain,

$$ $\displaystyle(x-y)^{2}(y^{2}+2\delta^{2})$ $\displaystyle\geq(x-y)^{2}(x^{2}+xy+y^{2})$ $\displaystyle=(x^{3}-y^{3})(x-y).$ $$

By Lemma D.8 we have our result.

Case $\left\lvert x\right\rvert\geq\delta,\left\lvert y\right\rvert\leq\delta$. We must show that the following inequality holds:

$$ $\frac{y^{4}}{4}-\frac{x^{2}y^{2}}{2}+2\delta^{2}xy-\delta^{2}y^{2}-\delta^{3} \left\lvert x\right\rvert+\frac{\delta^{4}}{4}\leq 0.$ $$

We leave out the details of the calculations. The proof is similar to the same case for showing the lower bound. We can define a polynomial in $x$ for arbitrary $\left\lvert y\right\rvert\leq\delta$. Then we show that this polynomial is less than 0 0 for $x\geq\delta$ by computing the value at $\delta$ and show that the derivative is negative for $x\geq\delta$ We proceed similarly for $x\leq-\delta$. By rearranging and manipulating the terms in the above inequality we can arrive at our result. These calculations are similar to the previous cases so we exclude them for brevity.
∎

###### Lemma D.16 .

###### Proof.

###### Lemma D.17 .

###### Proof.

###### Lemma D.18 .

###### Proof.

###### Lemma D.19 .

###### Proof.

### Appendix E Absolutely Convex Functions

Discussing the theory constructions derived from Assumption 2.1, we introduced a stand-alone class of functions, satisfying an absolute convexity condition. In this section, we derive more properties and examples. Let us remind that a function $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex if and only if:

$$ $\phi(y)\geq|\phi(x)+\left\langle\nabla\phi(x),y-x\right\rangle|,\qquad\forall x ,y\in\mathbb{R}^{d}.$ (36) $$

Our first statement is a Lemma that establishes calculus in the spirit of Lemma 5.1 in the main text.

###### Lemma E.1 .

Let $\phi,\phi_{1},\phi_{2}:\mathbb{R}^{d}\to\mathbb{R}$ be absolutely convex, and let $\mathbf{A}\in\mathbb{R}^{d\times m}$, $b\in\mathbb{R}^{d}$ and $\alpha\geq 0$. Then

- (i)
$\phi+\alpha$ is absolutely convex.
- (ii)
$\alpha\phi$ is absolutely convex.
- (iii)
$\phi_{1}+\phi_{2}$ is absolutely convex.
- (iv)
$\phi(\mathbf{A}x+b)$ is absolutely convex.

###### Proof.

We prove each statement:

- (i)
$\psi(x):=\phi(x)+\alpha\geq\left|\phi(y)+\left\langle\nabla\phi(y),x-y\right
\rangle\right|+\alpha\geq\left|\phi(y)+\left\langle\nabla\phi(y),x-y\right
\rangle+\alpha\right|=\left|\psi(y)+\left\langle\nabla\psi(y),x-y\right\rangle
\right|.$
- (ii)
$\psi(x):=\alpha\phi(x)\geq\alpha\left(\left|\phi(y)+\left\langle\nabla\phi(y),
x-y\right\rangle\right|\right)\geq\alpha\left|\phi(y)+\left\langle\nabla\phi(y
),x-y\right\rangle\right|=\left|\alpha\phi(y)+\left\langle\alpha\nabla\phi(y),
x-y\right\rangle\right|=\left|\psi(y)+\left\langle\nabla\psi(y),x-y\right
\rangle\right|.$
- (iii)
$\psi(x):=\phi_{1}(x)+\phi_{2}(x)\geq\left|\phi_{1}(y)+\left\langle\nabla\phi_{
1}(y),x-y\right\rangle\right|+\left|\phi_{2}(y)+\left\langle\nabla\phi_{2}(y),
x-y\right\rangle\right|$
$\geq\left|\phi_{1}(y)+\left\langle\nabla\phi_{1}(y),x-y\right\rangle+\phi_{2}(
y)+\left\langle\nabla\phi_{2}(y),x-y\right\rangle\right|=\left|\psi(y)+\left
\langle\nabla\psi(y),x-y\right\rangle\right|$.
- (iv)
$\psi(x)=\phi(\mathbf{A}x+b)\geq|\phi(\mathbf{A}y+b)+\left\langle\nabla\phi(
\mathbf{A}y+b),\mathbf{A}x+b-(\mathbf{A}y+b)\right\rangle|=|\phi(\mathbf{A}y+b
)+\left\langle\mathbf{A}^{\top}\nabla\phi(\mathbf{A}y+b),x-y\right\rangle|=|
\phi(\mathbf{A}y+b)+\left\langle A^{\top}\nabla\phi(\mathbf{A}y+b),x-y\right
\rangle|=|\psi(y)+\left\langle\nabla\psi(y),x-y\right\rangle|.$

∎

###### Lemma E.1 .

###### Proof.

#### E.1 Examples

###### Lemma E.2 .

Let $p\geq 1$. Then $\phi:\mathbb{R}^{d}\to\mathbb{R}$ where $\phi(x)={\left\|x\right\|}_{p}$ is absolutely convex.

###### Proof.

We already know that $\phi$ is convex so we show that

$$ $-\phi(y)-\left\langle\nabla\phi(y),x-y\right\rangle\leq\phi(x),$ $$

where $\frac{\partial\phi(y)}{\partial y_{i}}=\frac{y_{i}|y_{i}|^{p-2}}{{\left\|y
\right\|}_{p}^{p-1}}$ for $x,y\in\mathbb{R}^{d}$.

Observe that

$$ $\left\langle\phi(y),x-y\right\rangle=\sum_{i=1}^{d}\frac{y_{i}|y_{i}|^{p-2}}{{ \left\|y\right\|}_{p}^{p-1}}(x_{i}-y_{i}).$ $$

We make use of Holder’s inequality which is stated below for $r,s\geq 0$,

$$ $\left(\sum_{i=1}^{d}|x_{i}|^{r}|y_{i}|^{s}\right)^{r+s}\leq\left(\sum_{i=1}^{d }|x_{i}|^{r+s}\right)^{r}\left(\sum_{i=1}^{d}|y_{i}|^{r+s}\right)^{s}.$ $$

For any $x,y\in\mathbb{R}^{d}$ and with $r=1$ and $s=p-1$ we have that ,

$$ $\left(\sum_{i=1}^{d}|x_{i}||y_{i}|^{p-1}\right)^{p}\leq\left(\sum_{i=1}^{d}|x_ {i}|^{p}\right)\left(\sum_{i=1}^{d}|y_{i}|^{p}\right)^{p-1}.$ $$

Simplifying this expression we obtain,

$$ $\displaystyle\sum_{i=1}^{d}|x_{i}||y_{i}|^{p-1}$ $\displaystyle\leq\left(\sum_{i=1}^{d}|x_{i}|^{p}\right)^{\frac{1}{p}}\left( \sum_{i=1}^{d}|y_{i}|^{p}\right)^{\frac{p-1}{p}}$ $\displaystyle={\left\|x\right\|}_{p}\left(\left(\sum_{i=1}^{d}|y_{i}|^{p} \right)^{\frac{1}{p}}\right)^{p-1}$ $\displaystyle={\left\|x\right\|}_{p}{\left\|y\right\|}_{p}^{p-1}.$ $$

We can obtain a lower bound on the term,

$$ $\displaystyle\sum_{i=1}^{d}|x_{i}||y_{i}|^{p-1}$ $\displaystyle=\sum_{i=1}^{d}|x_{i}||y_{i}||y_{i}|^{p-2}=\sum_{i=1}^{d}|x_{i}y_ {i}||y_{i}|^{p-2}$ $\displaystyle\geq\sum_{i=1}^{d}-(x_{i}y_{i})|y_{i}|^{p-2}$ $\displaystyle=-\sum_{i=1}^{d}x_{i}y_{i}|y_{i}|^{p-2}.$ $$

Therefore,

$$ ${\left\|x\right\|}_{p}{\left\|y\right\|}_{p}^{p-1}\geq-\sum_{i=1}^{d}x_{i}y_{i }|y_{i}|^{p-2}.$ $$

Now add ${\left\|y\right\|}_{p}^{p}=\sum_{i=1}^{d}|y_{i}|^{p}$ to both sides of the inequality we get

$$ $\displaystyle{\left\|x\right\|}_{p}{\left\|y\right\|}_{p}^{p-1}+{\left\|y \right\|}_{p}^{p}$ $\displaystyle\geq\sum_{i=1}^{d}|y_{i}|^{p}-\sum_{i=1}^{d}x_{i}y_{i}|y_{i}|^{p- 2}=\sum_{i=1}^{d}y_{i}^{2}|y_{i}|^{p-2}-\sum_{i=1}^{d}x_{i}y_{i}|y_{i}|^{p-2}$ $\displaystyle=\sum_{i=1}^{d}\left(y_{i}^{2}|y_{i}|^{p-2}-x_{i}y_{i}|y_{i}|^{p- 2}\right)=\sum_{i=1}^{d}y_{i}|y_{i}|^{p-2}(y_{i}-x_{i})$ $\displaystyle=-\sum_{i=1}^{d}y_{i}|y_{i}|^{p-2}(x_{i}-y_{i}).$ $$

Now divide both sides of this inequality by ${\left\|y\right\|}_{p}^{p-1}$,

$$ ${\left\|x\right\|}_{p}+{\left\|y\right\|}_{p}\geq-\sum_{i=1}^{d}\frac{y_{i}|y_ {i}|^{p-2}}{{\left\|y\right\|}_{p}^{p-1}}(x_{i}-y_{i}).$ $$

By rearranging the terms we get our desired inequality

$$ $-{\left\|y\right\|}_{p}-\sum_{i=1}^{d}\frac{y_{i}|y_{i}|^{p-2}}{{\left\|y \right\|}_{p}^{p-1}}(x_{i}-y_{i})\leq{\left\|x\right\|}_{p}.$ $$

∎

###### Lemma E.3 .

There exists an absolutely convex function $\phi:\mathbb{R}\to\mathbb{R}$ such that the derivative of $f\coloneq\phi^{2}$ is not Lipschitz continuous. Namely,

$$ $\phi(x)=\begin{cases}\frac{3}{2}\left\lvert x\right\rvert+\frac{1}{2}&\left \lvert x\right\rvert\geq 1\\ x^{\frac{3}{2}}+1&0\leq x<1\\ (-x)^{\frac{3}{2}}+1&-1<x<0\end{cases}.$ $$

###### Proof.

Firstly, by a simple computation we can show that $\phi^{\prime\prime}\geq 0$ so $\phi$ is convex. Observe that $\left\lvert f^{\prime}\right\rvert\leq\frac{3}{2}$ and $x_{\star}=0$. Also notice that $\phi$ is bounded below by $\frac{3}{2}\left\lvert x\right\rvert$. Therefore, by Lemma E.16, $\phi$ is absolutely convex.

From a brief computation, we can obtain,

$$ $f^{\prime}(x)=\begin{cases}\frac{3}{2}(3\left\lvert x\right\rvert+1)\frac{x}{ \left\lvert x\right\rvert}&\left\lvert x\right\rvert\geq 1\\ 3(x^{\frac{3}{2}}+1)x^{\frac{1}{2}}&0\leq x<1\\ 3((-x)^{\frac{3}{2}}+1)(-x)^{\frac{1}{2}}&-1<x<0\end{cases}.$ $$

Now suppose by contradiction that $h^{\prime}$ is Lipschitz continuous. Then there exists an $L>0$ such that for all $x,y\in\mathbb{R}^{d}$,

$$ $\frac{\left\lvert f^{\prime}(x)-f^{\prime}(y)\right\rvert}{\left\lvert x-y \right\rvert}\leq L.$ $$

Specifically, this holds for $0<x<1$ and $y=0$ so we have

$$ $\displaystyle\frac{\left\lvert f^{\prime}(x)-f^{\prime}(y)\right\rvert}{\left \lvert x-y\right\rvert}$ $\displaystyle=\frac{\left\lvert f^{\prime}(x)\right\rvert}{\left\lvert x\right \rvert}=\frac{\left\lvert 3x^{2}+3x^{\frac{1}{2}}\right\rvert}{\left\lvert x \right\rvert}$ $\displaystyle=\frac{3x^{2}+3x^{\frac{1}{2}}}{x}=3x+\frac{3}{\sqrt{x}}\leq L.$ $$

We can find an $x$ small enough such that $\frac{3}{\sqrt{x}}>L$. Therefore, the inequality cannot hold. As a consequence, $f^{\prime}$ is not Lipschitz continuous.
∎

###### Lemma E.4 .

Let $\delta>0$. Then $f,\phi:\mathbb{R}\to\mathbb{R}$ defined below are absolutely convex.

$$ $f(x)=\delta\sqrt{1+\frac{x^{2}}{\delta^{2}}},\qquad\phi(x)=\begin{cases}\frac{ 1}{2}x^{2}+\frac{\delta^{2}}{2}&\left\lvert x\right\rvert\leq\delta\\ \delta(\left\lvert x\right\rvert-\frac{\delta}{2})+\frac{\delta^{2}}{2}&x> \delta\end{cases},$ $$

Note that $f$ is the pseudo-Huber loss function and $\phi$ is the Huber loss function.

###### Proof.

Both the Huber loss and pseudo-Huber loss functions are well-known examples of convex loss functions. The minimizer of $f$ and $\phi$ is $x_{\star}=0$.

From a simple computation we obtain that $\left\lvert f^{\prime}(x)\right\rvert\leq 1$ for all $x\in\mathbb{R}$,

$$ $f^{\prime}(x)=\frac{x}{\delta\sqrt{1+\frac{x^{2}}{\delta^{2}}}}\leq\dfrac{x}{ \delta\frac{x}{\delta}}=1.$ $$

Also, we know that for all $x\in\mathbb{R}$,

$$ $f(x)=\delta\sqrt{1+\frac{x^{2}}{\delta^{2}}}\geq\delta\sqrt{\frac{x^{2}}{ \delta^{2}}}=\sqrt{x^{2}}=\left\lvert x\right\rvert.$ $$

Therefore, by Lemma E.16, $f$ is absolutely convex.

By computing the derivative of $\phi$, we can show that $\left\lvert\phi^{\prime}(x)\right\rvert\leq\delta$ for all $x\in\mathbb{R}$. Now we show that $\phi(x)\geq\delta\left\lvert x\right\rvert$.

When $x>\delta$, we can simply observe that $\phi(x)=\delta\left\lvert x\right\rvert$. Now consider the case where $x\leq\delta$. We have that,

$$ $(\left\lvert x\right\rvert-\delta)^{2}\geq 0.$ $$

Expanding the square we get,

$$ $x^{2}-2\delta\left\lvert x\right\rvert+\delta^{2}\geq 0.$ $$

Rearranging the terms and dividing by $2$ we see that,

$$ $\phi(x)=\frac{1}{2}x^{2}+\frac{\delta^{2}}{2}\geq\delta\left\lvert x\right\rvert.$ $$

Hence, by Lemma E.16, $\phi$ is absolutely convex.
∎

###### Lemma E.5 .

Let $a>0$ and $b\geq 0$. Then $\phi:\mathbb{R}\to\mathbb{R}$ where $\phi(x)=\sqrt{ax^{2}+b}$ is absolutely convex.

###### Proof.

Notice that $x_{\star}=0$. Also by a simple computation we know can show that $f$ is convex,

$$ $\phi^{\prime\prime}(x)=\frac{ab}{(ax^{2}+b)^{\frac{3}{2}}}\geq 0.$ $$

We can compute an upper bound on the derivative of $f$,

$$ $\phi^{\prime}(x)=\frac{ax}{\sqrt{ax^{2}+b}}\leq\frac{ax}{\sqrt{ax^{2}}}=\sqrt{ a}.$ $$

Then,

$$ $\phi(x)=\sqrt{ax^{2}+b}\geq\sqrt{ax^{2}}=\sqrt{a}\sqrt{x^{2}}=\sqrt{a}\left \lvert x\right\rvert.$ $$

Since $\phi(x)\geq\sqrt{a}\left\lvert x\right\rvert$, by Lemma E.16, $f$ is absolutely convex.
∎

###### Lemma E.6 .

The function $\phi:\mathbb{R}\to\mathbb{R}$, defined as follows

$$ $\phi(x)=\begin{cases}x+1+\frac{1}{x+1}&x\geq 0\\ 1-x+\frac{1}{1-x}&x<0\end{cases}$ $$

is absolutely convex.

###### Proof.

Observe that $x_{\star}=0$. By a simple computation, we can show that $\phi^{\prime\prime}(x)\geq 0$ for all $x\in\mathbb{R}$,

$$ $\phi^{\prime\prime}(x)=\begin{cases}\frac{2}{(x+1)^{3}}&x\geq 0\\ \frac{2}{(1-x)^{3}}&x<0\end{cases}.$ $$

Similarly to the previous examples, we compute an upper bound on $\phi^{\prime}$,

$$ $\phi^{\prime}(x)=\begin{cases}1-\frac{1}{(x+1)^{2}}&x\geq 0\\ \frac{1}{(1-x)^{2}}-1&x<0\end{cases}.$ $$

It is clear that $\left\lvert\phi^{\prime}(x)\right\rvert\leq 1$ for all $x\in\mathbb{R}$. It is easy to shoiw $\phi(x)\geq\left\lvert x\right\rvert$. For $x\geq 0$, we have

$$ $\phi(x)=x+1+\frac{1}{x+1}\geq x.$ $$

For $x<0$, we have

$$ $\phi(x)=1-x+\frac{1}{1-x}\geq-x.$ $$

Therefore, by Lemma E.16, $\phi$ is absolutely convex.
∎

###### Lemma E.2 .

###### Proof.

###### Lemma E.3 .

###### Proof.

###### Lemma E.4 .

###### Proof.

###### Lemma E.5 .

###### Proof.

###### Lemma E.6 .

###### Proof.

#### E.2 Functions with zero minimum

Absolutely convex functions have some interesting properties when their minimum is 0 0.

###### Lemma E.7 .

If $\phi$ is absolutely convex, then the following statements are equivalent:

- 1.
$\phi(0)=0$,
- 2.
$\phi(x)=\left\langle\nabla\phi(x),x\right\rangle$,
- 3.
$\phi$ is homogeneous of degree 1.

###### Proof.

We establish three implications:

$(i)\Rightarrow(ii)$ Pick any $y$. If $\phi(0)=0$, then using Equation 36 with $x=0$ leads to $\left|\phi(y)+\left\langle\nabla\phi(y),-y\right\rangle\right|\leq 0$, which implies $\phi(y)=\left\langle\nabla\phi(y),y\right\rangle$.

$(ii)\Rightarrow(iii)$ We start by substituting $\phi(y)=\left\langle\nabla\phi(y),y\right\rangle$ and $\phi(x)=\left\langle\nabla\phi(x),x\right\rangle$ into ${\phi(x)\geq\phi(y)+\left\langle\nabla\phi(y),x-y\right\rangle}$ to get,

$$ $\phi(x)=\left\langle\nabla\phi(x),x\right\rangle\geq\left\langle\nabla\phi(y), y\right\rangle+\left\langle\nabla\phi(y),x-y\right\rangle=\left\langle\nabla \phi(y),x\right\rangle.$ $$

This means that,

$$ $\phi(x)=\max_{g\in Q}\left\langle g,x\right\rangle,$ $$

where $Q:=\{\nabla\phi(y)\;:\;y\in\mathbb{R}^{d}\}$. As a consequence, for any $t\geq 0$ and $x\in\mathbb{R}^{d}$ we get

$$ $\phi(tx)=\max_{g\in Q}\left\langle g,tx\right\rangle=t\max_{g\in Q}\left \langle g,x\right\rangle=t\phi(x).$ $$

$(iii)\Rightarrow(i)$ Choose any $x\in\mathbb{R}^{d}$ and $t=0$. Then $\phi(0)=\phi(tx)=t\phi(x)=0\phi(x)=0$.
∎

###### Lemma E.8 .

Let $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}$ be absolutely convex. Suppose there exists an $x_{\star}\in\mathbb{R}^{d}$ such that $\phi(x_{\star})=0$. Then

$$ $\phi(x)=\left\langle\nabla\phi(x),x-x_{\star}\right\rangle.$ $$

###### Proof.

From absolute convexity, we have that

$$ $0\leq|\phi(x)+\left\langle\nabla\phi(x),x_{\star}-x\right\rangle|\leq\phi(x_{ \star})=0.$ $$

So

$$ $\phi(x)+\left\langle\nabla\phi(x),x_{\star}-x\right\rangle=0.$ $$

Simply rearranging we get our result,

$$ $\phi(x)=-\left\langle\nabla\phi(x),x_{\star}-x\right\rangle=\left\langle\nabla \phi(x),x-x_{\star}\right\rangle.$ $$

∎

###### Lemma E.9 .

Let $\phi:\mathbb{R}\rightarrow\mathbb{R}$ be absolutely convex. Suppose there exists an $x_{\star}\in\mathbb{R}$ such that $\phi(x_{\star})=0$. Also, suppose that $\phi$ is differentiable everywhere but at $x_{\star}$. Then it must be that

$$ $\phi(x)=m\left\lvert x-x_{\star}\right\rvert=\begin{cases}-m(x-x_{\star})&x<x_ {\star}\\ m(x-x_{\star})&x>x_{\star}\\ \end{cases}$ (37) $$

for some $m\in\mathbb{R}_{\geq 0}$.

###### Proof.

We have that $f(x)=\phi(x+x_{\star})$ is absolutely convex. It is also homogeneous of degree one since $f(0)=0$. Define $U_{1}=\{x\in\mathbb{R}\ |\ x>0\}$ and $U_{2}=\{x\in\mathbb{R}\ |\ x<0\}$.

By homogeneity, for any $t>0$ and $x\in U_{1}$ we have that $f(tx)=tf(x)$. Differentiating both sides with respect to $x$ we get $f^{\prime}(tx)=f^{\prime}(x)$. This means that for any $x\in U_{1}$ we have that $f^{\prime}(x)=m_{1}$ for some $m_{1}\in\mathbb{R}$. Since $U_{1}$ is a connected open set, we have that $f(x)=m_{1}x$ for $x\in U_{1}$.

By similar reasoning, for $x\in U_{2}$, $f^{\prime}(x)=m_{2}$ for some $m_{2}\in\mathbb{R}$.
Also then, $f(x)=m_{2}x$ for $x\in U_{2}$.

Now consider $x\in U_{1}$ and $y\in U_{2}$. By absolute convexity we know that

$$ $\displaystyle m_{1}x=f(x)$ $\displaystyle\geq|f(y)+f^{\prime}(y)(x-y)|=|m_{2}y+m_{2}(x-y)|=|m_{2}x|\geq|m_ {2}||x|.$ $$

Then $m_{1}\geq|m_{2}|\frac{x}{|x|}=|m_{2}|$ which comes from the fact that $x\in U_{1}$ so $x>0$ and thus $\frac{x}{|x|}=1$. Similarly,

$$ $\displaystyle m_{2}y=f(y)$ $\displaystyle\geq|f(x)+f^{\prime}(x)(y-x)|=|m_{1}x+m_{1}(y-x)|=|m_{1}y|\geq|m_ {1}||y|.$ $$

Then $|m_{1}|\leq m_{2}\frac{y}{|y|}=-m_{2}$ because $y\in U_{2}$ so $y<0$ and thus $\frac{y}{|y|}=-1$.

Since $0\leq|m_{1}|\leq-m_{2}$ we get $m_{2}\leq 0$. Also because $|m_{2}|\leq m_{1}$ it must be that $m_{2}=-m_{1}$ where $m_{1}\geq 0$.

For brevity, we set $m=m_{1}$ and so we have that

$$ $f(x)=\begin{cases}-mx&x<0\\ mx&x>0\\ \end{cases}.$ $$

By definition we have that $\phi(x)=f(x-x_{\star})$. Therefore, we obtain our desired result

$$ $\phi(x)=\begin{cases}-m(x-x_{\star})&x-x_{\star}<0\\ m(x-x_{\star})&x-x_{\star}>0\\ \end{cases}.$ $$

∎

###### Lemma E.10 .

Suppose that $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex and $\phi(0)=0$. Then $\phi$ is sub-additive,

$$ $\phi(x+y)\leq\phi(x)+\phi(y).$ $$

###### Proof.

By Lemma E.7, we know $\phi$ is positively homogeneous of degree one. Also because $\phi$ is convex we have that for any $0\leq\alpha\leq 1$,

$$ $\phi(\alpha x+(1-\alpha)y)\leq\alpha\phi(x)+(1-\alpha)\phi(y).$ $$

Selecting $\alpha=\frac{1}{2}$,

$$ $\phi\left(\frac{1}{2}x+\frac{1}{2}y\right)\leq\frac{1}{2}\phi(x)+\frac{1}{2} \phi(y).$ (38) $$

By homogeneity of $\phi$,

$$ $\frac{1}{2}\phi(x+y)\leq\phi\left(\frac{1}{2}x+\frac{1}{2}y\right).$ $$

By combining the previous inequality with inequality (38) and multiplying by $2$ we get our result.
∎

###### Lemma E.11 .

Suppose that $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex and $\phi(0)=0$. Then the epigraph of $\phi$ is a convex cone.

###### Proof.

Now we show that $\operatorname{epi}{\phi}$ is a convex cone. Suppose $(x,\mu_{1})\in\operatorname{epi}{\phi}$ and $(y,\mu_{2})\in\operatorname{epi}{\phi}$. Suppose $\alpha\geq 0$ and $\beta\geq 0$. Then

$$ $\phi(\alpha x+\beta y)\leq\phi(\alpha x)+\phi(\beta y)=\alpha\phi(x)+\beta\phi (y)\leq\alpha\mu_{1}+\beta\mu_{2}.$ $$

The first inequality is from sub-additivity and the first equality is from homogeneity, Therefore, $(\alpha x+\beta y,\alpha\mu_{1}+\beta\mu_{2})\in\operatorname{epi}{\phi}$ so $\operatorname{epi}{\phi}$ is a convex cone.
∎

###### Lemma E.12 .

Suppose that $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex and $\phi(0)=0$. Then $\phi$ is even, i.e.

$$ $\phi(x)=\phi(-x),\qquad\forall x\in\mathbb{R}^{d}.$ (39) $$

###### Proof.

By absolute convexity we have that for any $x,y\in\mathbb{R}^{d}$

$$ $\displaystyle\left\langle\nabla\phi(x),x\right\rangle=\phi(x)$ $\displaystyle\geq\left\lvert\phi(y)+\left\langle\nabla\phi(y),x-y\right\rangle\right\rvert$ $\displaystyle=\left\lvert\phi(y)+\left\langle\nabla\phi(y),x\right\rangle+ \left\langle\nabla\phi(y),-y\right\rangle\right\rvert$ $\displaystyle=\left\lvert\phi(y)+\left\langle\nabla\phi(y),x\right\rangle- \left\langle\nabla\phi(y),y\right\rangle\right\rvert$ $\displaystyle=\left\lvert\phi(y)+\left\langle\nabla\phi(y),x\right\rangle-\phi (y)\right\rvert$ $\displaystyle=\left\lvert\left\langle\nabla\phi(y),x\right\rangle\right\rvert.$ (40) $$

Similarly,

$$ $\phi(y)=\left\langle\nabla\phi(y),y\right\rangle\geq\left\lvert\left\langle \nabla\phi(x),y\right\rangle\right\rvert.$ (41) $$

Now subtitute $y=-x$ into (E.12),

$$ $\phi(x)\geq\left\lvert\left\langle\nabla\phi(-x),x\right\rangle\right\rvert= \left\lvert\left\langle\nabla\phi(-x),-x\right\rangle\right\rvert=\left\lvert \phi(-x)\right\rvert=\phi(-x),$ $$

where the last equality is because absolutely convex functions are non-negative. Substituting ${y=-x}$ into (41),

$$ $\phi(-x)\geq\left\lvert\left\langle\nabla\phi(x),-x\right\rangle\right\rvert= \left\lvert\left\langle\nabla\phi(x),x\right\rangle\right\rvert=\left\lvert \phi(x)\right\rvert=\phi(x).$ $$

Therefore, $\phi(x)=\phi(-x)$.
∎

###### Lemma E.7 .

###### Proof.

###### Lemma E.8 .

###### Proof.

###### Lemma E.9 .

###### Proof.

###### Lemma E.10 .

###### Proof.

###### Lemma E.11 .

###### Proof.

###### Lemma E.12 .

###### Proof.

#### E.3 Real valued functions

Simple absolutely convex functions from the real numbers to the real numbers are an instructive playground to understand how to finalize the generalized proofs. Below, we report some properties of such sub-class. In particular, we prove bounded subgradients in Lemma E.15 and a useful result for validating examples in Lemma E.16.

###### Lemma E.13 .

Let $f:\mathbb{R}\to\mathbb{R}$ defined as follows, $f(x)=\left\lvert a+b(x-x_{0})\right\rvert$ for some $a,b,x_{0}\in\mathbb{R}$ with $b\neq 0$. Then for any $c>0$. There exists $x_{1},x_{2}\in\mathbb{R}$ with $x_{2}\geq x_{1}$, $f(x_{1})=f(x_{2})=c$, $\left\lvert x_{2}-x_{1}\right\rvert=\frac{2c}{\left\lvert b\right\rvert}$ and $f^{\prime}(x_{2})\geq 0$ and $f^{\prime}(x_{1})\leq 0$.

###### Proof.

By simply solving the equation $f(x)=c$, we get that

$$ $\displaystyle x_{2}$ $\displaystyle=\frac{c-a}{b}+x_{0};$ $\displaystyle x_{1}$ $\displaystyle=\frac{-c-a}{b}+x_{0}.$ $$

Thus,

$$ $\displaystyle\left\lvert x_{2}-x_{1}\right\rvert$ $\displaystyle=\left\lvert\frac{c-a}{b}+x_{0}-\frac{-c-a}{b}-x_{0}\right\rvert= \left\lvert\frac{c-a+c+a}{b}\right\rvert=\left\lvert\frac{2c}{b}\right\rvert.$ $$

Suppose without loss of generality that $b>0$. Then $f^{\prime}(x_{2})=cb>0$ and $f^{\prime}(x_{1})=-cb<0$.
∎

###### Lemma E.14 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is a convex function that is not constant with minimizer $x_{\star}$. Suppose $\phi$ lower bounded by $f(x)=\left\lvert a+b(x-x_{0})\right\rvert$ for $a,b,x_{0}\in\mathbb{R}$ and $b\neq 0$. For any $c>\phi(x_{\star})$ there exists an $x^{\prime}$ such that $\phi(x^{\prime})=c$ and $\left\lvert x^{\prime}-x_{\star}\right\rvert\leq\frac{2c}{\left\lvert b\right\rvert}$.

###### Proof.

By Lemma E.13, there exists $x_{1},x_{2}\in\mathbb{R}$ such that $\left\lvert x_{2}-x_{1}\right\rvert=\frac{2c}{|b|}$ and $f(x_{1})=f(x_{2})=c$.

We also know that $x_{2}>x_{1}$ and that $f^{\prime}(x_{2})\geq 0$ and $f^{\prime}(x_{1})\leq 0$. We will show that $x_{1}<x_{\star}<x_{2}$. Suppose by contradiction that $x_{\star}\geq x_{2}$. Since $f$ is a linear function with slope $f^{\prime}(x_{2})$ on the interval $[x_{2},\infty)$ we get

$$ $f(x_{\star})=f(x_{2})+f^{\prime}(x_{2})(x_{\star}-x_{2})\geq f(x_{2})=c>\phi(x _{\star}),$ $$

which is a contradiction because $f$ is supposed to be a lower bound on $\phi$. The first inequality follows from the fact that $f^{\prime}(x_{2})(x_{\star}-x_{2})\geq 0$. A similar argument follows if the assumption $x_{\star}\leq x_{1}$ is made.

So $c=f(x_{1})\leq\phi(x_{1})$ and $\phi(x_{\star})<c$. By the Intermediate Value Theorem, there exists $x^{\prime}\in(x_{1},x_{\star})$ such that $\phi(x^{\prime})=c$.

Thus $x_{1}<x^{\prime}<x_{\star}<x_{2}$. Therefore, $\left\lvert x^{\prime}-x_{\star}\right\rvert\leq\left\lvert x_{2}-x_{1}\right
\rvert=\frac{2c}{|b|}$ with $\phi(x^{\prime})=c$.
∎

###### Lemma E.15 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is absolutely convex and has a minimizer $x_{\star}$. Then there exists an $M\in\mathbb{R}$ such that $\left\lvert\phi^{\prime}(x)\right\rvert\leq M$ for all $x\in\mathbb{R}$ i.e. $\left\lvert\phi^{\prime}\right\rvert$ is bounded.

###### Proof.

If $\phi$ is constant then its derivative is bounded so we consider the case where $\phi$ is not constant.

We will do a proof by contradiction. Let $c\in\mathbb{R}$ such that $c>\phi(x_{\star})$. Let $\epsilon=\frac{c-\phi(x_{\star})}{2}$. Note that $\left\lvert\phi(x_{\star})-c\right\rvert>\epsilon$.

By continuity of $\phi$ at $x_{\star}$ there must be a $\delta>0$ such that if $\left\lvert x-x_{\star}\right\rvert\leq\delta$ then $\left\lvert\phi(x)-\phi(x_{\star})\right\rvert\leq\epsilon$.

Suppose that $\left\lvert\phi^{\prime}\right\rvert$ is unbounded. Therefore, there exists a sequence of numbers $y_{n}\in\mathbb{R}$ such that

$$ $\lim_{n\to\infty}\left\lvert\phi^{\prime}(y_{n})\right\rvert=\infty$ $$

For any $n$, let $f_{n}(x)=\left\lvert\phi(y_{n})+\phi^{\prime}(y_{n})(x-y_{n})\right\rvert$. Since $\phi$ is absolutely convex, $f_{n}$ must be a lower bound on $\phi$. By Lemma E.14 there exists an $x_{n}$ such that $\phi(x_{n})=c$ and $\left\lvert x_{n}-x_{\star}\right\rvert\leq\frac{2c}{\left\lvert\phi^{\prime}(
y_{n})\right\rvert}$ for any $y_{n}$.

Since $|\phi^{\prime}|$ is unbounded we can choose a $N$ such that $\frac{2c}{\left\lvert\phi^{\prime}(y_{N})\right\rvert}\leq\delta$. Thus $\left\lvert x_{N}-x_{\star}\right\rvert\leq\delta$. Therefore, $\left\lvert\phi(x_{\star})-\phi(x_{N})\right\rvert=\left\lvert\phi(x_{\star})-
c\right\rvert\leq\epsilon$.

But this contradicts the fact that $\left\lvert\phi(x_{\star})-c\right\rvert>\epsilon$.
∎

###### Lemma E.16 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is convex and has a minimizer at $x_{\star}=0$. Suppose $\phi^{\prime}$ is bounded. If $\phi$ can be lower bounded by $h(x)=m\left\lvert x\right\rvert$ where $\left\lvert\phi^{\prime}(y)\right\rvert\leq m$ for all $y\in\mathbb{R}$ then $\phi$ is absolutely convex.

###### Proof.

Suppose without loss of generality $y<x_{\star}=0$. Since $\phi$ is convex we have that $\phi^{\prime}(y)\leq 0$ by monotoncity of $\left\lvert\phi^{\prime}\right\rvert$. Since $m$ is a bound on $\phi^{\prime}$ we get

$$ $m\geq-\phi^{\prime}(y)\geq 0.$ (42) $$

Since $h$ is a lower bound on $\phi$ we also know that .

$$ $\phi(y)\geq-my\geq 0.$ (43) $$

Now let $f(x)=\left\lvert\phi(y)+\phi^{\prime}(y)(x-y)\right\rvert$. Denote $x^{v}$ as the point where $f(x^{v})=0$. On the interval $(-\infty,x^{v}]$, $f$ is equal to the line tangent to $\phi$ at point $y$. So by convexity, $f$ is a lower bound on $\phi$ on the interval $(-\infty,x^{v}]$. It remains to show that $f$ lower bounds $\phi$ on the interval $[x^{v},\infty)$.

First, we show that $x^{v}=-\frac{\phi(y)}{\phi^{\prime}(y)}+y\geq x_{\star}=0$. We can take the reciprocal of inequality (42) to obtain, $\frac{1}{m}\leq-\frac{1}{\phi^{\prime}(y)}$. Multiply this inequality by (43) to get, $-y\leq-\frac{\phi(y)}{\phi^{\prime}(y)}$. We can do this because the terms on both sides of the inequalities are positive. Rearranging we can see that $x^{v}\geq 0$.

Suppose $x\in[x^{v},\infty)$. On this interval, $f$ is a line with slope $-\phi^{\prime}(y)$ passing through the point $(x^{v},0)$. Thus we can rewrite $f$ as $f(x)=-\phi^{\prime}(y)(x-x^{v})$. Since $x^{v}\geq 0$ we know that $x-x^{v}\leq x$. Multiply this inequality by $m\geq-\phi^{\prime}(y)\geq 0$ to get that $-\phi^{\prime}(y)(x-x^{v})\leq mx$. Since $h(x)=mx$ is a lower bound on $\phi$ we have that $-\phi^{\prime}(y)(x-x^{v})\leq\phi(x)$. Therefore, $f$ is a lower bound on $\phi$ for arbitrary $y<0$ so we are done.

A similar argument can be made for $y\geq 0$, the signs will be flipped at each step.
∎

A direction of potential interest for future developments is how to “absolutely-convexify” a given function. Below, we prove the propotypical case of functions from $\mathbb{R}$ to $\mathbb{R}$. In words, any convex function lifted high enough is absolutely convex.

###### Lemma E.17 .

Suppose $f:\mathbb{R}\rightarrow\mathbb{R}$ is a convex function. Then $\phi(x)=f(x)+\beta$ is non-negative for $x\in[a,b]$ with $\alpha=max\{|f^{\prime}(a)|,|f^{\prime}(b)|\}$ and $\beta=\frac{\alpha(b-a)}{2}-\frac{f(a)+f(b)}{2}$.

###### Proof.

It is sufficient to show that $\phi(x)\geq 0$ for $x\in[a,b]$:

$$ $\displaystyle\phi(x)$ $\displaystyle=f(x)+\frac{\alpha(b-a)}{2}-\frac{f(a)+f(b)}{2}$ $\displaystyle=\frac{f(x)-f(a)+\alpha(x-a)}{2}+\frac{f(x)-f(b)-\alpha(x-b)}{2}$ $\displaystyle\geq\frac{D_{f}(x,a)}{2}+\frac{D_{f}(x,b)}{2}$ $\displaystyle\geq 0.$ $$

∎

###### Lemma E.18 .

Suppose $f:\mathbb{R}\rightarrow\mathbb{R}$ is a convex function. Then for any interval $[a,b]$ there exists $\beta$, such that $\phi(x)=f(x)+\beta$ is absolutely convex on $[a,b]$.

###### Proof.

As $\phi$ is convex by convexity of $f$, it is sufficient to show that for every $x,y\in[a,b]$:

$$ $-\phi(x)\leq\phi(y)+\phi^{\prime}(y)(x-y).$ $$

From Lemma E.17 we have $\phi(x)\geq 0$, so it is sufficient to consider the case when $\phi^{\prime}(y)(x-y)\leq 0$.

Having $\alpha,\beta$ from Lemma E.17.

Case 1: $\phi^{\prime}(y)\leq 0$ and $x\geq y$.

From the convexity of $\phi$ it follows that:

$$ $\displaystyle\phi(y)+\phi^{\prime}(y)(x-y)-(\phi(a)+\phi^{\prime}(a)(x-a))$ $\displaystyle=D_{\phi}(y,a)+(\phi^{\prime}(y)-\phi^{\prime}(a))(x-y)$ $\displaystyle\geq D_{\phi}(y,a)$ $\displaystyle\geq 0.$ $$

Hence, $-f^{\prime}(a)\leq\alpha$ by construction, implying:

$$ $\phi(a)-\alpha(x-a)\leq\phi(y)+\phi^{\prime}(y)(x-y).$ $$

It remains to show that:

$$ $\displaystyle\phi(x)+\phi(a)-\alpha(x-a)$ $\displaystyle=f(x)+f(a)+2\beta-\alpha(x-a)$ $\displaystyle=f(x)-f(b)+\alpha(b-a)-\alpha(x-a)$ $\displaystyle=f(x)-f(b)-\alpha(x-b)$ $\displaystyle\geq D_{f}(x,b)$ $\displaystyle\geq 0.$ $$

Case 2: $\phi^{\prime}(y)\geq 0$ and $x\leq y$.

In analogy with the previous case:

$$ $\phi(b)+\alpha(x-b)\leq\phi(y)+\phi^{\prime}(y)(x-y).$ $$

Therefore, it is sufficient to show that:

$$ $\displaystyle\phi(x)+\phi(b)+\alpha(x-b)$ $\displaystyle=f(x)+f(b)+2\beta+\alpha(x-b)$ $\displaystyle=f(x)-f(a)+\alpha(b-a)+\alpha(x-b)$ $\displaystyle=f(x)-f(a)+\alpha(x-a)$ $\displaystyle\geq D_{f}(x,a)$ $\displaystyle\geq 0.$ $$

∎

It is useful to remind the fllowing standard result for sub-gradients. The proof is in the referenced book.

###### Lemma E.19 (Lebourg Mean Value Theorem [Clarke, 1990 ] ) .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is Lipschitz on any open set containing the line segment $[x,y]$. Then there exists an $a\in(x,y)$ such that

$$ $\phi(x)-\phi(y)\in\left\langle\partial\phi(a),x-y\right\rangle.$ $$

###### Lemma E.20 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is absolutely convex. Let $M\in\mathbb{R}$ be the bound on the subgradient of $\phi$, i.e. $\left\lvert\phi^{\prime}(x)\right\rvert\leq M$. Fix a $y\in\mathbb{R}$. Then for any $x\geq y$ we have that

$$ $\phi(y)+M(x-y)\geq\phi(x).$ $$

Similarly, for any $x\leq y$,

$$ $\phi(y)-M(x-y)\geq\phi(x).$ $$

###### Proof.

We prove the first claim. Suppose $x\geq y$.

Since $\phi$ is convex, it is locally Lipschitz i.e. Lipschitz on $[y,x]$. By Lebourg’s MVT we know there exists a $c\in(y,x)$ such that $\phi(x)-\phi(y)=g(x-y)$ where $g\in\partial\phi(c)$. Note that $g\leq M$. So, $g(x-y)\leq M(x-y)$ because $x-y\geq 0$. Therefore,

$$ $\phi(x)-\phi(y)\leq M(x-y).$ $$

Rearranging this expression we obtain $\phi(x)\leq\phi(y)+M(x_{0}-y)$.

The proof of the second claim follows the same format and uses the fact that $g\geq-M$ instead.
∎

###### Lemma E.21 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is absolutely convex. Let $M\in\mathbb{R}$ be such that $\left\lvert\phi^{\prime}\right\rvert\leq M$. Then the following limits exist and are equal

$$ $\lim_{x\to\infty}\left\lvert\phi^{\prime}(x)\right\rvert=\lim_{x\to-\infty} \left\lvert\phi^{\prime}(x)\right\rvert.$ $$

###### Proof.

First, we show that $\lim_{x\to\infty}\left\lvert\phi^{\prime}(x)\right\rvert$ exists.

Let $\{x_{n}\}$ be an arbitrary sequence such that $x_{n}\to\infty$. Since $\phi$ is convex the sequence $\{\left\lvert\phi^{\prime}(x_{n})\right\rvert\}$ is monotonically increasing. Also, it is bounded above. Therefore, by the Monotone Convergence Theorem there exists an $L_{1}\in\mathbb{R}$

$$ $\lim_{n\to\infty}\left\lvert\phi^{\prime}(x_{n})\right\rvert=L_{1}\ \ \text{ and}\ \ L_{1}\geq\left\lvert\phi^{\prime}\right\rvert.$ $$

Since $x_{n}$ is arbitrary it must be that $\lim_{x\to\infty}\left\lvert\phi^{\prime}(x)\right\rvert=L_{1}$. A similar argument can demonstrate that there exists an $L_{2}\in\mathbb{R}$ with $\left\lvert L_{2}\right\rvert\geq\left\lvert\phi^{\prime}\right\rvert$ and $\lim_{x\to-\infty}\left\lvert\phi^{\prime}(x)\right\rvert=\left\lvert L_{2}\right\rvert$.

Now we show that $L_{1}=\left\lvert L_{2}\right\rvert$. We will do this by contradiction. Suppose without loss of generality that $L_{1}>\left\lvert L_{2}\right\rvert$ and that $L_{2}<0$.

There exists an $\epsilon>0$ such that $L_{1}-\epsilon>\left\lvert L_{2}\right\rvert$. Now there also exists an $N$ such that for any $y>N$ we have that $\left\lvert\phi^{\prime}(y)-L_{1}\right\rvert<\epsilon$. So $L_{1}-\epsilon<\phi^{\prime}(y)$.

By absolutely convexity of $\phi$, function $f(x)=\left\lvert\phi(y)+\phi^{\prime}(y)(x-y)\right\rvert$ is a lower bound on $\phi$. Let $x_{v}$ be the value where $f(x_{v})=0$.

Define $l(x)=-\phi^{\prime}(y)(x-x_{v})$, which is the line passing through the point $(x_{v},0)$ with slope $-\phi^{\prime}(y)$. Observe that for $x\in(-\infty,x_{v}]$, $l(x)=f(x)$ so $l$ is a lower bound on $\phi$ in that interval. Define $h_{1}(x)=-(L_{1}-\epsilon)(x-x_{v})$ to be the line passing through $(x_{v},0)$ with slope $-(L_{1}-\epsilon)$. For $x\leq x_{v}$, $h_{1}(x)<l(x)$ because $L_{1}-\epsilon<\phi^{\prime}(y)$. Therefore, $h_{1}(x)<\phi(x)$ for $x\in(-\infty,x_{v}]$.

Define $h_{2}(x)=\phi(x_{v})+L_{2}(x-x_{v})$. Since $L_{2}<0$, by Lemma E.20, the function $h_{2}$ is an upper bound on $\phi$ for any $x<x_{v}$.

By calculation we can determine an $x_{i}$ such that $h_{1}(x_{i})=h_{2}(x_{i})$ where

$$ $x_{i}=\frac{x_{v}(L_{2}+L_{1}-\epsilon)-\phi(x_{v})}{L_{2}+L_{1}-\epsilon}.$ $$

Now we show that $x_{i}\leq x_{v}$. Note that $\phi$ is absolutely convex so $-\phi(x_{0})\leq 0$. By adding $(L_{2}+L_{1}-\epsilon)x_{v}$ to both sides of this inequality we obtain

$$ $\displaystyle x_{v}(L_{2}+L_{1}-\epsilon)-\phi(x_{0})\leq x_{v}(L_{2}+L_{1}- \epsilon).$ $$

Dividing by $L_{2}+L_{1}-\epsilon$ we get

$$ $\displaystyle x_{i}=\frac{x_{v}(L_{2}+L_{1}-\epsilon)-\phi(x_{v})}{L_{2}+L_{1} -\epsilon}\leq x_{v}.$ $$

Let $x<x_{i}$. So $h_{1}(x)=h_{1}(x_{i})-(L_{1}-\epsilon)(x-x_{i})$ and $h_{2}(x)=h_{1}(x_{i})+L_{2}(x-x_{i})$. Observe that $-(L_{1}-\epsilon)<L_{2}$ because $L_{2}<0$ and $L_{1}-\epsilon>\left\lvert L_{2}\right\rvert$. Multiplying both sides of this inequality by $x-x_{i}$ which is less than 0 0 and then adding $h(x_{i})$ to both sides again we see that $h_{1}(x)>h_{2}(x)$.

Therefore, for any $x<x_{i}<x_{v}$, we have that $h_{1}(x)>h_{2}(x)$. This is a contradiction because on the interval $(-\infty,x_{v})$, $h_{1}$ is a lower bound so $\phi(x)\geq h_{1}(x)$ and $h_{2}$ is an upper bound so $h_{2}(x)\geq\phi(x)$.
∎

###### Lemma E.22 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ is absolutely convex. Suppose it has a minimum point $x_{\star}$. Suppose there exists a $y_{1},y_{2}\in\mathbb{R}$ such that $y_{1}<x_{\star}<y_{2}$ and for every $y\leq y_{1}$, $\phi^{\prime}(y)=m_{1}$ and for every $y^{\prime}\geq y_{2}$, $\phi^{\prime}(y^{\prime})=m_{2}$. Then $m_{1}=m_{2}$.

###### Proof.

Note that since $\phi$ is convex it has monotonicly increasing derivative. Therefore, $m_{1}<0$ since $y<x_{\star}$ and $m_{2}>0$ since $y^{\prime}>x_{\star}$. Let $f(x)=\left\lvert\phi(y_{1})+m_{1}(x-y_{1})\right\rvert$ be the tangent cone to $y_{1}$. Then define line $h(x)=\left\lvert m_{1}\right\rvert(x+\frac{\phi(y_{1})}{m_{1}}-y_{1})$ which is a line that has the same slope as $f$ and intersects the vertex of $f$. Note that $h$ is a lower bound on $\phi$ by absolute convexity.
∎

###### Lemma E.23 .

Suppose $\phi:\mathbb{R}\to\mathbb{R}$ be absolutely convex and assume $\phi^{*}=\inf_{x\ \in\mathbb{R}}\phi(x)<\infty$. Then there exists an $x_{\star}\in\mathbb{R}$ such that $\phi(x_{\star})\leq\phi(x)$ for any $x\in\mathbb{R}$.

###### Proof.

Suppose $x\in\mathbb{R}$ is arbitrary. Choose a $y\in\mathbb{R}$ and by absolute convexity we have that $\left\lvert\phi^{\prime}(y)+\phi^{\prime}(y)(x-y)\right\rvert\leq\phi(x)$. We can rearrange the terms on the left side and take the limit to see that

$$ $\lim_{\left\lvert x\right\rvert\to\infty}\left\lvert\phi(y)-\phi^{\prime}(y)y+ \phi^{\prime}(y)x\right\rvert=\infty.$ $$

since only the last term which is linear depends on $x$. Therefore, we have that $\lim_{\left\lvert x\right\rvert\to\infty}\phi(x)=\infty$.

This demonstrates that $\phi$ is coercive. Now let $x_{n}$ be a sequence such that $\phi(x_{n})\to f^{*}$. Suppose that $\lim_{n\to\infty}\left\lvert x_{n}\right\rvert=\infty$. Then by coercivity, we get that $\lim_{\left\lvert x_{n}\right\rvert\to\infty}\phi(x_{n})=infty$ which is a contradiction with the fact that $\phi^{*}\leq\infty$. Thus it must be that $\lim_{n\to\infty}\left\lvert x_{n}\right\rvert=r$ for some $r\in\mathbb{R}$. Let $B_{r}=\{x\in\mathbb{R}\ |\ \left\lvert x\right\rvert\leq r\}$ which is compact because it is closed and bounded. Since $x_{n}\in B_{r}$ and every sequence in a compact set has a convergent subsequence, so there exists an $x_{\star}\in B_{r}$ s.t. $x_{n_{k}}\to x_{\star}$. By continuity of $\phi$ (because it is a convex function) we obtain $f^{*}=\lim_{k\to\infty}f(x_{n_{k}})=f(x_{\star})$.
∎

###### Lemma E.13 .

###### Proof.

###### Lemma E.14 .

###### Proof.

###### Lemma E.15 .

###### Proof.

###### Lemma E.16 .

###### Proof.

###### Lemma E.17 .

###### Proof.

###### Lemma E.18 .

###### Proof.

###### Lemma E.19 (Lebourg Mean Value Theorem [Clarke, 1990 ] ) .

###### Lemma E.20 .

###### Proof.

###### Lemma E.21 .

###### Proof.

###### Lemma E.22 .

###### Proof.

###### Lemma E.23 .

###### Proof.

#### E.4 Multivariable functions

Having analyzed the easy case, we move to general instances of absolutely convex functions. In particular, we prove that gradients of absolutely convex functions are bounded. The first statement is a rewriting of Lemma 7.1 in the main text.

###### Lemma E.24 .

Suppose $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex and has a minimizer $x_{\star}$. Then there exists a $M\in\mathbb{R}$ such that ${\left\|\nabla\phi(x)\right\|}_{2}\leq M$ for all $x\in\mathbb{R}^{d}$.

###### Proof.

If $\phi$ is the constant function then its gradient is bounded so we consider the case where $\phi$ is not constant.

We will do a proof by contradiction. Let $c>\phi(x_{\star})$. Let $\epsilon=\frac{c-\phi(x_{\star})}{2}$. Note that $\left\lvert\phi(x_{\star})-c\right\rvert>\epsilon$. Suppose $\delta>0$. Observe that since $\phi$ is convex on $\mathbb{R}^{d}$ it is continuous on $\mathbb{R}^{d}$ and in particular it is continuous at $x_{\star}$. Therefore, there exists a $\delta>0$ such that if $\left\lvert x_{\star}-x\right\rvert\leq\delta$ then $\left\lvert\phi(x_{\star})-\phi(x)\right\rvert\leq\epsilon$.

Suppose that $\left\lvert\nabla\phi\right\rvert$ is unbounded. So, there exists a sequence of points $y_{n}\in\mathbb{R}^{d}$ such that

$$ $\displaystyle\lim_{n\to\infty}\left\|\nabla\phi(x)\right\|_{2}=\infty.$ $$

Let $f_{n}(x)=\left\lvert\phi(y_{n})+\left\langle\nabla\phi(y_{n}),x-y_{n}\right
\rangle\right\rvert$. Since $\phi$ is absolutely convex, $f_{n}$ must be a lower bound on $\phi$. We can proceed similarly to the proof of bounded gradients in $\mathbb{R}$ (Lemma  E.15) by considering the restriction of $f$ and $\phi$ to specific lines. This allows us to find a sequence of points $x_{n}$ that lie on those lines and $x_{n}\to x_{\star}$.

Define $L_{n}$ to be the line that passes through $x_{\star}$ in the direction of $\nabla\phi(y_{n})$. Let $\phi\big{|}_{L_{n}}:\mathbb{R}\to\mathbb{R}$ be the restriction of $\phi$ to the line $L_{n}$ and similarly, $f_{n}\big{|}_{L_{n}}:\mathbb{R}\to\mathbb{R}$ be the restriction of $f_{n}$ to $L_{n}$. Note that the function $f_{n}\big{|}_{L_{n}}$ is of the form $\left\lvert a+b(x-x_{0})\right\rvert$ where $b=\left\|\nabla\phi(y_{n})\right\|^{2}$ for some $a,x_{0}\in\mathbb{R}$. Let $\bar{x}^{*}\in\mathbb{R}$ be the minimizer of $\phi\big{|}_{L_{n}}$. Then by Lemma, there exists a point, $\bar{x}_{n}\in\mathbb{R}$ such that $\phi\big{|}_{L_{n}}(\bar{x}_{n})=c$ and $\left\lvert\bar{x}^{*}-\bar{x}_{n}\right\rvert\leq\frac{2c}{\left\|\nabla\phi(
y_{n})\right\|^{2}}$. Observe that $\bar{x}^{*}$ corresponds to $x_{\star}$. Also, $\bar{x}_{n}$ can be mapped to a point $x_{n}\in\mathbb{R}^{d}$ which lies on the line $L_{n}$ and $\phi(x_{n})=c$ and $\left\lvert x_{\star}-x_{n}\right\rvert\leq\frac{2c}{\left\|\nabla\phi(y_{n})
\right\|^{2}}$. This holds for each $y_{n}$.

Since $\left\|\nabla\phi(y_{n})\right\|_{2}$ is unbounded we can find an $N$ such that $\left\lvert x_{\star}-x_{N}\right\rvert<\delta$. Therefore, $\left\lvert\phi(x_{\star})-\phi(x_{n})\right\rvert=\left\lvert\phi(x_{\star})-
c\right\rvert\leq\epsilon$. However, this contradicts the fact that $\left\lvert\phi(x_{\star})-c\right\rvert>\epsilon$.
∎

###### Lemma E.25 .

The maximum of a constant and an absolutely convex function is absolutely convex.

###### Proof.

Let $\alpha\in\mathbb{R}$ and $f$ be absolutely convex and $g:=\max\{f,\alpha\}$. We split the argument in some sub-steps.

(Trivial case) Since absolutely convex functions are always positive, it follows that if $\alpha\leq 0$ then $g(x)=\max\{f(x),\alpha\}\equiv f(x)$ and $f=g$ is absolutely convex.

(Second case) Let $\alpha>0$. Since $f$ is absolutely convex, it is convex and $g$ is by construction. Therefore, the positive side of the inequality in absolute convexity needs not to be verified. It reamains to show that:

$$ $\mathrm{wts}\quad g(y)\geq-g(x)-\left\langle\nabla g(y),x-y\right\rangle\quad \forall x,y\iff g(y)+g(x)+\left\langle\nabla g(y),x-y\right\rangle\geq 0\quad \forall x,y.$ (44) $$

For convenience, we will show the last version is positive for different choices of $x,y$. Recall that $f$ is always positive so for arbitrary $(x,y)$there are four regions identified by the strips $[0,\alpha);[\alpha,\infty)$ iover which the values $f(x),f(y)$ can fall.

Additionally, recognize that for $z\in\mathbb{R}^{d}$ we have $\nabla g(z)=\nabla\max\{f(z),a\}=\mathbbm{1}_{f(z)>a}\nabla f(z)$.
Let us treat all the cases in separate ways.(^4^44In principle, at $z=a$ there is a singularity, we avoid doing this computation since the non-differentiable definition of absolute convexity is satisfied for the max function.)

If $f(x)\leq\alpha$ and $f(y)<\alpha$ we have the expression $2\alpha\geq 0$ by construction.

If $f(x)>\alpha$ and $f(y)<\alpha$ we have the expression:

$$ $f(x)+\alpha>0;$ (45) $$

again, by construction.

If $f(x)<\alpha$ and $f(y)>\alpha$ we have $a+f(y)+\left\langle\nabla f(y),x-y\right\rangle>f(x)+f(y)+\left\langle\nabla f
(y),x-y\right\rangle\geq 0$ since we assumed $f$ is absolutely convex.

If $f(x)\geq\alpha$ and $f(y)>\alpha$ one has:

$$ $f(x)+f(y)+\left\langle\nabla f(y),x-y\right\rangle\geq 0,$ (46) $$

which follows by the assumed strong convexity of $f$.
∎

remark
Let $x_{\star}=\operatorname*{arg\,min}f$, for an absolutely convex function $f$. Observe that one can always use, for any $y\neq x_{\star},x\neq x_{\star}$:

$$ $f(x)\geq|f(y)+\left\langle\nabla f(y),x_{\star}-y\right\rangle|.$ (47) $$

###### Lemma E.26 .

Suppose $v\in\mathbb{R}^{d}$. A function $\phi:\mathbb{R}^{d}\to\mathbb{R}$ is absolutely convex if and only if the function $f:\mathbb{R}\to\mathbb{R}$ defined as $f(t)=\phi(x+tv)$ is absolutely convex for all $x\in\mathbb{R}^{d}$.

###### Proof.

($\Rightarrow$) Suppose $f(t)$ is an absolutely convex function for any $x,v\in\mathbb{R}^{d}$. We already know that $\phi$ will be convex so we only need to show that for all $y,z\in\mathbb{R}^{d}$,

$$ $-\phi(x)\leq\phi(y)+\left\langle\nabla\phi(y),z-y\right\rangle.$ $$

Note that $f^{\prime}(t)=\left\langle\nabla\phi(x+tv),v\right\rangle$. Select $x=y$ and $v=z-y$. Since $f$ is absolutely convex, the following inequality will hold,

$$ $\displaystyle-f(1)$ $\displaystyle\leq f(0)+f^{\prime}(0)(1-0)=f(0)+f^{\prime}(0)$ $\displaystyle=\phi(y)+\left\langle\nabla\phi(y),z-y\right\rangle.$ $$

We have our result because $f(1)=\phi(y+v)=\phi(z)$

($\Leftarrow$) Suppose $\phi$ is absolutely convex. Let $x,v\in\mathbb{R}^{d}$ be arbitrary. We know already that $f$ is convex. So we just need to show that for any $s,t\in\mathbb{R}$ we have that

$$ $-f(t)\leq f(s)+f^{\prime}(s)(t-s).$ $$

By absolute convexity of $\phi$ we know that,

$$ $\displaystyle-\phi(x+tv)$ $\displaystyle\leq\phi(x+sv)+\left\langle\nabla\phi(x+sv),x+tv-(x+sv)\right\rangle$ $\displaystyle=\phi(x+sv)+\left\langle\nabla\phi(x+sv),tv-sv)\right\rangle$ $\displaystyle=\phi(x+sv)+\left\langle\nabla\phi(x+sv),v\right\rangle(t-s)$ $\displaystyle=f(s)+f^{\prime}(s)(t-s).$ $$

Since $f(t)=\phi(x+tv)$ we have our result.
∎

###### Lemma E.24 .

###### Proof.

###### Lemma E.25 .

###### Proof.

###### Lemma E.26 .

###### Proof.

### Appendix F Extra Experiments

#### F.1 Regression with squared Huber loss

In this experiment we optimize the function

$$ $f(x)=\frac{1}{n}\sum_{i=1}^{n}h_{\delta}^{2}(a_{i}x-b_{i}),$ $$

where $a_{i}\in\mathbb{R}^{d}$, $b_{i}\in\mathbb{R}$ are the data samples associated with a regression problem, and $h_{\delta}$ is the Huber loss function. We run the experiments with $\mathbf{C}(x)$ for absolutely convex functions 7.2.

Figure: Figure 5: Regression on housing dataset.
Refer to caption: extracted/5615196/imgs/huber_loss/housing/huber_1.png

Figures 5(c)–6(c) show that the algorithms using the $\mathbf{C}(x)$ matrix perform much better than the Polyak method. We observe very fast convergence of both LCD3 and LCD2, regardless of $\delta$. Contrary, as $\delta$ increases LCD1 loses in comparison with the other two matrix methods. The most likely reason is increasing part of the objective, which is quartic, as it requires extra adaptiveness on the smoothness constant.

#### F.2 Ridge regression

We consider the following objective function:

$$ $f(x)=\frac{1}{n}\sum_{i=1}^{n}(a_{i}x-b_{i})^{2}+\lambda{\left\|x\right\|}^{2}$ $$

where $a_{i}\in\mathbb{R}^{d}$, $b_{i}\in\mathbb{R}$ are the data samples associated with a regression problem. By $L$ we understand the smoothness constant of a linear regression instance, excluding the regularizer.

Figure: Figure 7: Ridge regression on housing dataset; $\mathbf{C}(x)=2\lambda$.
Refer to caption: extracted/5615196/imgs/lin_reg_l2/reg/housing/lplr_600.png

Figure: Figure 9: Ridge regression on housing dataset; $\mathbf{C}(x)=\frac{2}{n}\mathbf{A}^{\top}\mathbf{A}$.
Refer to caption: extracted/5615196/imgs/lin_reg_l2/quad/housing/lplr_600.png

In Figures 7(c)–8(c), $\mathbf{C}(x)$ is associated with the regularizer, and it becomes a multiple of $\mathbf{I}$. As discussed in the main text, in this case LCD2 has closed-form solution, which coincides with LCD3. The LCD1 algorithm becomes GD. We can see, similar behavior to logistic regression with $L_{2}$ regularizer that is consistent improvement of LCD2 over the Polyak’s method.

Figures 9(c)–10(c) show the results with $\mathbf{C}(x)=\frac{2}{n}\mathbf{A}^{\top}\mathbf{A}$, which is a lower bound on the main part of the objective. In this circumstance, LCD1 becomes the Newton’s method, and converges in one step. As anticipated in the main text, LCD3 can diverge. Finally, LCD2 performs in a very consistent way, and converges in exactly 15 steps across all the setups.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 4
questions: 1. 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?
2. 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.
3. How the choice of $C(x)$ in experiments affects the performancece if the methods?
4. In the first experiment with $L_2$ regularization, GD also can be used; it would be interesting to see if LCD1 outperforms GD.

Typos.
- should it be $\mathbb{R}^d \rightarrow \mathbb{R}^d$ ?
- there is a problem with reference on lines 550-552
- in the proof of Lemma B.1, the last two lines of the first equation are repeated
- lines 756-757 ...the term $||x_k - x_*||^2_{C(x_k)}$ ... "positive" is missing.
- lines 1026-1027 remove "any".
soundness: 3
strengths: 1. The proof of Theorems 4.1 and 4.2 is correct.
2.  A wide range of examples is provided alongside a general framework for constructing convex and smooth functions with local curvatures. 
3. The theoretical results are motivated by examples and supported by experiments.
summary: - The paper introduces a new class of functions called convex and smooth with local structure. Many interesting examples are provided that satisfy the proposed assumption, and the calculus for the proposed class is presented. For this class, the authors proposed three new algorithms LCD1, LCD2, and LCD3. Theorem 4.1, 4.2 shows $\frac{L_C ||x_0 - x_*||^2}{2k}$ for LCD1 which is a generalization of gradient descent, and LCD2 which is a generalization of Polyak stepsizes. It is a good paper, it is well-written, easy to follow, and motivated by examples.
weaknesses: 1. All three methods require a knowledge of $C(x)$. In the examples, such $C(x)$ is provided; however, if one wants to run these methods, one must find such $C(x)$, which can be a non-trivial task. Meanwhile, if $C(x)$ is not known in advance, one can still use GD  with line-search or Polyak stepsizes, or normalized gradient descent. Meaning, to use LCD1, LCD2, and LCD3, the knowledge of $C(x)$ is necessary.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: - Can the authors comment on the second order characterization of assumption 2.1? 
- What is the time complexity of LCD2 compared to Polyak step size? Specifically, how does the computation of $\beta_k$ affect the complexity?
soundness: 2
strengths: The paper is clearly written and is easy to read. It is interesting to see that Newton's method and gradient descent can be seen as special cases of the same framework under the assumption proposed by the authors.
summary: Convexity and L-smoothness are standard assumptions in optimization literature which are useful for easier analysis of optimization algorithms and determining the right algorithm parameters. These global conditions may not always take local differences in the curvature into account. This paper proposes new analogues of the assumptions to incorporate certain kinds of local curvature information. The paper also proposes modifications of gradient descent using matrix valued step sizes to take advantage of the modified assumptions.
weaknesses: The first-order convexity condition and L-smoothness imply that $$ f(y) + \langle \nabla f(y), x-y\rangle \leq f(x) \leq f(y) + \langle \nabla f(y), x-y\rangle  + \frac L2 || x-y||^2.$$ The authors' assumption 2.1 modifies these inequalities by adding the term $\frac12 || x-y||^2_{\mathbf C}$ to the lower bound and upper bound for $f(x)$ provided by these inequalities (since $\frac12 || x-y||^2_{\mathbf C+L\mathbf I} = \frac12 || x-y||^2_{\mathbf C} +  \frac L2 || x-y||^2$). Thus, assumption 2.1 seems to be more general than L-smoothness but it is less general than convexity.

In the standard analyses of GD, L-smoothness guarantees a sufficient decrease with each step (with the right step size) and convexity ensures that that decrease pushes us towards the minimizer. The two inequalities balance each other in a crucial way. This work exploits that tradeoff. However, it is not surprising that if the same term is added to both the lower bound and upper bound of $f(x)$ then they will cancel each other out and the standard convergence proofs will still go through. 

Furthermore, if $f$ is twice differentiable, assumption 2.1 is actually equivalent to
$$\mathbf C(x) \preceq \nabla^2 f(x) \preceq \mathbf C(x) + L_C \mathbf I.$$ This follows from the same kind of standard arguments used to show that convex functions have positive semidefinite Hessians. Having observed this second order condition, many of the remarks that the authors make follow directly. The case when $\mathbf C = 0$ is the standard case with convexity and L-smoothness, and the case when $L_C=0$ is the realm of second order methods like Newton's method. My impression is that to give any useful advantage over standard GD, the map $\mathbf C(x)$ will have to approximate the Hessian $\nabla^2 f(x)$. But then the algorithms provided do not seem to be very useful unless there is a good way to approximate the Hessian.

LCD1 actually just seems to be a version of Newton's method where the Hessian is overestimated by its upper bound $\mathbf C(x) + L_C \mathbf I$ to make it more stable. The convergence rate provided for LCD1 is the same as GD (unless $L_C = 0$, in which case it is pure Newton's method anyway), which does not provide any new insights either. The authors present LCD2 as a generalization of Polyak's step size, but the step size $\beta_k$ in that case does not even have a closed form. Computing $\beta_k$ itself requires an optimization problem to be solved at each step, and the benefits of doing that are not clear. LCD3 has a closed form step-size but there are no convergence results provided for it, so it's not clear how well it performs.

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. One of the curvature matrices specified for each of the examples 6.1-6.4 is just the Hessian. For examples 6.2 and 6.4, $\nabla f(x) \nabla f(x)^\top$ is proposed as another candidate for the curvature matrix, but these kinds of approximations of the Hessian are already covered by quasi-Newton methods like Berndt–Hall–Hall–Hausman algorithm.

The experiments are also only performed on these trivial examples and authors compare their proposed step sizes only against Polyak step size. The first experiment is on a strongly convex and L-smooth function, which is covered by the classical assumptions, and the optimal method for which would have been a momentum-based algorithm like Nesterov's accelerated gradient descent. The second experiment chooses the Hessian as the curvature matrix, reducing it to the case where second order methods would perform better.

Overall, the assumption proposed in the paper does to offer many new theoretical insights nor do the algorithms proposed offer practical advantages over existing algorithms.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: 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.
soundness: 3
strengths: - The methods illustrate how readily available curvature information for certain problems can be used to design algorithms that improve performance.
- Sections 6 and 7 provide problem examples and proofs, which help identify the class of problems for which these algorithms are applicable.
summary: This paper proposes three variants of descent methods for solving convex optimization problems that satisfy Assumptions 2.1, specifically (5) and (6). Conditions (5) and (6) define a class of convex problems with a curvature matrix C(y) and a smoothness parameter Lc​. These parameters, C(y) and Lc​, are used to compute the step sizes for the three methods. The first method generalizes gradient descent with a fixed step size; the second method generalizes gradient descent with the Polyak step size; and the third method is a heuristic variant of the second method. Both the first and second methods are proved to converge at a rate of O(1/k). Experimental results demonstrate the convergence of the methods, with Methods 2 and 3 notably outperforming the Polyak step-size approach, highlighting the benefits of incorporating curvature information in algorithm design. The paper also provides example problems for which the curvature matrix C(y) and Lc​ are computable.
weaknesses: - The setting is very limited, namely, convex optimization problems for which the scaling matrix C(y) is known and available.
- 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.  In this respect, the extensions of the analyses of gradient descent, etc. are relatively straightforward.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: see above -
soundness: 3
strengths: The paper expands the class of objective functions for which we can obtain solid convergence guarantees. Moreover, the step size strategies (LCD 2 and LCD 3 which generalize Polyak steps) can provide some form of adaptivity. The computational results indicate that there might be empirical performance improvements as well.
summary: The paper explores methods for enhancing gradient descent through adaptive step sizes. The basic idea is to exploit "local curvature" without resorting to fully second-order methods, which require computationally expensive Hessians, i.e., using extra knowledge the idea is to interpolate between pure first order and second order. To this end, the authors introduce three algorithms or more precisely step-size estimation strategies: LCD1, LCD2, and LCD3. Each one optimizes step size based on curvature properties of the objective function. 

The authors establish theoretical convergence rates for LCD1 and LCD2, aligning with those for standard and Polyak step size gradient descent methods, which they intend to extend. The authors also claim improved empirical performance.
weaknesses: I have some concern regarding the novelty of the proposed method/approaches. In particular, the proposed concept of local curvature and the analysis seems to be very similar to "relative smoothness" and the associated analysis, see e.g., 

https://pubsonline.informs.org/doi/10.1287/moor.2016.0817 

and 

https://arxiv.org/pdf/1911.08510

(just to name two examples - there is much more)

Given these similarities the authors should discuss and relate their work to that of relative smoothness and also clearly delineate their own contribution from what is already known or implied by relative smoothness. I would like to ask the authors to clarify this in the rebuttal:

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

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

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


Independent of the above, the paper feels a little incremental, technical (the paper is very long), and niche in the sense that it provides "yet another" step size strategy for a broader class of objectives. The results are nice but not very surprising.

Meta-review: The paper studies settings of smooth convex optimization where additional information about "local curvature" of the objective is readily available. The paper proposes three variations of gradient descent -- generalizing GD with fixed step size and with Polyak step size, and a variable-metric heuristic based on Polyak step size. For the first two step size strategies, the paper proves $1/k$ convergence rate. The paper further provides examples to justify the availability of local curvature information and experiments to demonstrate the effectiveness of the proposed strategies. While the paper is of interest to ICLR and more broadly the optimization community, the contributions felt somewhat specialized and possibly incremental. Thus, at this point, the paper was judged to be below the acceptance threshold.

Decision: Reject