Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak Gradient Descent
Authors: Peter Richtárik
Simone Maria Giancola
Dymitr Lubczyk
Robin Yadav
Venue: NeurIPS 2025 poster ()
Keywords: convex optimization
adaptive step sizes
gradient methods
Primary area: optimization
TL;DR: We propose provably convergent adaptive methods under assumptions that reinforce smoothness and convexity with curvature information.

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), 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.

Local Curvature Descent: Squeezing More Curvature out of Standard and Polyak GD
Peter Richtárik 1.2
Simone Maria Giancola
peter. peter.richtarik0kee wwwhharikkkkaust..tt............ edu.
simone. simone.giancollaeee lancola@kaust edu. sa
Dymitr LubezykI.4 dymitr. lubczyk@student uva.n1 .nl
Robin Yaday1.5
robiny128student. wbc. ca
KAUST, Saudi Arabia; AI Initiative, Saudi Arabia; Laboratoire de Mathématiques d'Orsay, Université Paris-Saclay, CNRS, France; University of Amsterdam, Netherlands; University of British Columbia, Canada
Abstract
We contribute to the growing body of knowledge 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 problems (e.g., when minimizing the sum of squares of absolutely convex functions), certain local curvature information is readily available, and can be used obtain surprisingly powerful matrix-valued stepsizes, and meaningful theory. In particular, we develop three new methods- 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-metrée version of LCD2; this feature leads to closed-form expression for the iterates. Our empirical results are encouraging, and show that the local curvature descent improves upon gradient descent.
Introduction
In this work revisit the standard optimization problem
min f(x),
(I)
ZE34
where f : Rd + IR is a continuous convex function with nonempty set of minimizers X. Further, we denote the optimal function value by := f(x.), where x, X.,
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] 1963 Robbins and Monro 1951]
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
Fk+ Tt.
7% (xx)),
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

where > 0 is learning rate (stepsize), suffers from several well-known drawbacks, For example, for convex and L-smooth objectives, GD converges provided that"
Y t00 and
Pke
1 vk 20
(Nestrrvv 2004]. For many problems, L is very large and/or unknown, and estimating its value is 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. is known, a very elegant solution to the problems provided by Pollya [987]. who proposed the use of what is now known as the Polyak stepsize:
7kk
f(x))-f. [[V](=))]
(4)
is known that if f is convex and L-smooth, then 7h 2 1 for all k 2 0. So, unlike strategies based on the recommendation provided by (3). Polyak stepsize can never be too small compared to the upper bound from @ In fact, it is possible for 7A to be larger than +. which leads to practical benefits. Moreover, this is achieved without having to know or estimate L, which is big advantage. Since the function value f(xx and the gradient V fz()) are typically known, the only price for these benefits is the knowledge of the optimal value f.. This may may not be large price pay, depending on the application.
Malisky--Mishheenko stepsize. In the case of convex and locally smooth objectives, Malitsky and Mishchenko [2020) 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 [2020], and for several extensions of this line of work, we refer to Zhou et al. [2024].
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. Optimiza- tion 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 2017 Hinton] 2014, Reddi et al. 2019 Duchi et al., 2011]. 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. 2011].
1.2 Second-order methods
When f is twice differentiable and L-smooth, L can be 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:
(V=
Fb+11 Ig
When it works, it converges in few iterations only. However, it may fail to converge even on convex o It needs to be modified in order to converge from any starting point, say by adding a damping factor (Hanzely et al. 2022) or regularization [Mishchenko] 2023). However, under suitable assumptions, Newton's '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 performing linear solve. In analogy with it is possible to think of (V2
as a matrix-valued stepsize.
It is possible to use slightly larger stepsizes, by at most factor 2, hut this is not relevant to our narrative.
A kell- example is the function f(x) In(e- e²) with = 1.1.
2

---

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 f= (x (#a+11
I.) R V [[( ((()) which makes sense under appropriate assumptions when | - Øg. is small Nocedal and Wright [2006] Al-Baali et al. [204]) AAl-Baali and Khalfan [2007]. Dennis and More][1977. Until very recently, quasi-Newton methods were merely efficient heuristics, with very weak theory beyond quadratics [Kovalev et al. 2021 Rodomanov and Nesterov 2021). Furthermore, recent work has shown that the Hessian of deep neural networks exhibits a block diagonal structure [Dong et al. 2025]. A deeper understanding of these diagonal patterns can facilitate the design of more efficient adaptive algorithms for deep networks.
Polyak stepsize with second-order information. Li ct al. 2022 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 does not guarantee that iterates move closer to the set minimizers. Instead, we propose an assumption similar to earlier works Karimireddy et al. [2088) Gower et al. [2019), with the aim of using second-order information rigorously.
1.3 Notation
All vectors are in _dd unless explicitly stated otherwise. We use X, to denote the set of minimizes of f. Matrices are uppercase and bold (e.g., A, C), the d x zero (resp. identity) matrix denoted by
0 (resp. I), and $ is the set of d x d positive semi-definite matrices. The standard Euclidean inner
product is denoted with (:-)). .). For A E $4. we let ||=]|a == (Ar, x). By ||> = (E |x;lp)>/> we denote the Lp norm in IRd The Löwner order for positive semi-definite matrices is denoted with 3.
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, key observation is that, for some problems, certain local curvature information is readily available, and can be used to obtain powerful matrix-valued stepsizes.
The examples mentioned above, and discussed in detail in Sections 6 and 7 lead to the following abstract assumption, which 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 map- ping/metrichmarii C dRd + s4 and a constant Le 2 such that the inequalities
f(v) (Vf()), x v) 111 viloww S f(x),
(5)
M
f(x) s f(v) (VI(),= v) -11 - v vllow
(6)
ME (x:v)
for all x, Rd.
Assumption 2.1 defines new class of functions. Note that with the specific choice C(y) 0. (5) reduces to convexity, and (6) reduces to L-smoothness, with L = Lc. Note that any function satisfying (5) is necessarily convex, and similarly, any L-smooth function satisfies 6 with any curvature mapping C and Lo L. However, the converse is not true: function satisfying (6) not necessarily I.-smooth for any finite L.. Further, note that if f is j-strongly convex, then
satisfies (5) with curvature mapping C(y) = μI. The class of convex and L-smooth functions is one
3

---

of the most studied functional classes in optimization. Furthermore, we emphasize our new class strict and, as we shall see, useful generalization. We also show that many practical examples satisfy Assumption 2.1 with diagonal curvature mapping, which is particularly relevant in machine learning applications as enables efficient computation of the update steps for our algorithms.
Additionally, we want to stress that (5) generalizes convexity, which is a global property, and thus, (5) is also global property, captured by the fact that we require it to hold for all x E K However, the curvature matrix depends on which we will see shortly, refers to the current iterate in our methods. So, it depends on the "locus" of the algorithm, i.e. the current iterate. This is why we use the terminology "local". This is not to be misunderstood or misinterpreted for "local" reach. We elaborate on the connections between our assumptions and related notions in the literature in We now provide brief overview of our theoretical and empirical contributions:
Appendix A
2.1 Local curvature and a new function class
We define function class, described by Assumption 2.1 extending the classical class of convex and L-smooth functions. Further, we show that there are problems which satisfy Assumption 2.1 with nontrivial and easy-to-compute curvature mapping C (see Section and Section 7
2.2 Three new algorithms
We propose three novel algorithms for solving problem ① for function f satisfying Assumption 2.1 Local Curvature Descent (LCD1), Local Curvature Descent (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)
in z. Indeed, if C(y) O. this algorithmic design strategy leads to gradient descent with stepsize 1/L, where L = Lc. Second, LCD2 generalizes GD with Polyak stepsize: one moves from point y the Euclidean projection of y onto the ellipsoid:
Lc(v) = fa E Rd M (æ; v) S {+}-
Indeed, if C(y) = O, this algorithmic design leads to GD with stepsize (4). Computing the projection involves finding the unique root of a scalar equation variable, which can executed efficiently. Third, LCD3 is obtained from LCD2 by replacing the Euclidean projection with the projection defined by the local curvature matrix 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.2). with the same (1/kk) worst rate of GD with constant and Polyak stepsize, respectively. Previous work preconditioned Polyak stepsize [Abdukhakimov et al., 2023 fails to provide convergence theory and uses matrix stepsizes based on heuristics. In contrast, LCD2 utilizes local curvature from Assumption 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 algorithms boosts their empirical performance when compared their counterparts not taking advantage of local curvature.
Three Flavors of Local Curvature Descent
We now describe our methods.
3.1 Local Curvature Descent
Our first method, LCD1 is obtained by minimizing the upper bound from Assumption 2.1 where y = and letting Tk+1 be the minimizer:
Tk-
It - -C(()) + Le I] Vf(x))
(LCD1)

---

The derivation is routine; nevertheless, the detailed steps behind Equation (CC11 can be found in Appendix B.1 If C(x) and we let Lc, we recover GD with the constant stepsize " -. Note that just like GD, LCD1 is not adaptive to the smoothness parameter Lc; this parameter is needed to perform step.
1
3.2 Local Curvature Descent
Given any y E IR, let us define the localization set
Lc(y) = { E R E
Me (x, u) S [.]
Due to (5), we have X. C Ly)., which justifies the use of the word "localization". Furthermore, E 2r if and only if y E Lyly). Therefore, (C(Ts) separates Rd in two regions: one containing X,, the other the current iterate y zg.- This allows design our second algorithm, LCD2: simply project the current iterate Ty. into the localization set (*r), bringing it closer to the set of optimal points X.:
1k+1
arg min
1 f| - xxll
(LCD2)
rECo(a))
It turns out that this projection problem has an implicit parametric solution of the form
3k++1
-2k [C(x)) 3x I] V)(x),
(LCD2)
where 3x Importantly we show in Appendix C.I that the structure of the problem is easy: the pa- rameter 1/3, is the unique root of scalar equation, solvable efficiently. Moreover, if C(rz) ) is a rank-
one matrix multiple of I, closed-form solution exists. We present the details in Appendix C.3
When C(x) = 0. the localization set defined in (7) reduces to a half-space, and LCD2 becomes GD with Polyak stepsize. In general, LCD2 be seen as 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 since Le (xxx) S Lo (Rx), with equality if and only if C(rx)) = O, the point #x+1 obtained by LCD2 closer to X, than what is achieved by single step of GD with Polyak stepsize.
step of GD with Polyak stepsize. Indeed,
3.3 Local Curvature Descent
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 C(rR) instead:
Ck++
arg min xELc(Fx)
|| - I5k l(C())
(LCD3)
If C is invertible this projection problem admits the closed-form solution
ak+1 .7kk (1 (1-V²
2(( IV c-1
C- (x=)Vf(x))
(LCD3)
The full derivation of this fact can be found in Appendix D.I 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 and Appendix
4 Convergence Rates
Having described the methods, this appears to be the right moment to present our main convergence
results for LCD1 and LCD2.
We assume this for simplicity only.
5

---

Theorem 4.1 (Convergence of LCD1). Let Assumption 2.7 I be satisfied. For all l 2 1, the iterates of LCD1 satisfy
f(xx) f= f=
S
Lec. mo a.1l
26
Theorem 4.2 (Convergence of LCD2), Let Assumption LCD2 satisfy
be satisfied. For all 1, the iterates of 2.1
min f(x)) ff Lellza-a 22
The proofs of these results be found in Appendix B.2 and Appendix respectively. It is possible to derive linear convergence results under the assumption that ((z) 1l for all E Ra and some μ O; however, we refrain from listing these for brevity reasons.
C(x) = 0, and we let L Lc. these theorems recover the standard rates known for GD with the stepsize 1/ and GD with Polyak stepsize, respectively. So, generalize these earlier results. However, it possible for function to satisfy Assumptionn22I]an 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, f is convex and I-smooth, it may be possible that it satisfies Assumption 2. with some nonzero local curvature mapping C, in which Indeed,
choose L. such that L.c. T..
inf Amin (C(+)) L La S sup Amax (C(x)), zERd
DER
where Amin (resp. A.ax(.)) represents the smallest (resp. largest) eigenvalue of the argument, confirming Le S. L. However, may be that Le < L, in which case our result leads to improved complexity. Nevertheless, the main allure of methods is their attractive empirical behavior.
Convex quadratics. For convex quadratics, Assumption 2.1 is satisfied with C(z) = f²)(2) and
Lc = 0. In this case, both LCD1 and LCD2 reduce Newton's '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, belledehaved, and practically interesting.
5 Local Curvature Calculus
We now mention couple basic properties of functions that satisfy Inequalities 5 and (6)
Lemma 5.1. Let B R with 3 2 0. Suppose functions f and 9 satisfy inequality 5 with curvature mappings C₁ and C2 respectively. Then:
f +
Bf. and f+
satisfy Inequality 55) with curvature mappings C₁ 3C,, and C₁ + C2 respectively.
The proof of the lemma can be found in Appendix E.
A particularly useful instantiation of
Lemma 5. is presented in the following corollary.
Corollary 5.1. I satisfies and is convex, then = f + also satisfies (
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) preserved under pre-composition with linear functions. Additional results for functions satisfying Assumption 2.1 can be found in Appendix
Examples of Functions Satisfying Assumption 2.1
first list three examples that satisfy both inequalities in Assumption 2.1 Firstly, observe that if function is L-smooth, then it satisfies inequality (6) since C(x) is assumed to be positive semi-definite matrix. We aim to find convex functions that satisfy our assumption in a non-trivial
manner, i.c., C(x) * and C(x) # pI for some μ > 0.

---

Example 6.1 (Huber loss). Let > O and consider the Huber loss function h R + R given by
1
|0| < 8
h(x)
[0(
|<| > 8 -0)
Then = h? satisfies Assumption 2.1 with constant Lc 28 and curvature mapping
x |r||
S å
C(x)
82
> 6
Example 6.11pp is particularly interesting because C(x) + 28 s 38 for any R. By computing the second derivative of f. we can obtain the tightest L-smoothness constant; it is equal to 38². Therefore, the variable bound we derived is at least as good as the T-smoothness bound.
Example 6.2 (Squared p norm). Let p 2 2 and define f IR + R as f(x) = || Then f
satisfies Assumption 2.7 with either of the two curvature mappings.
C(x) - 2
Diag 10-2 .....,/.a. .....,/z!!" (le.|""......
C(x) =VV[(vVv(a)
and constant Le 2(p 1).
Example 6.3 (Lp regression). Suppose A E iRxd and E R", For p 2 2, the function f(x)
|A blp- satisfies Assumption 2.1 as precomposition of Example 6.2 with an affine function.
Therefore, linear regression in the squared Lp norm satisfies our assumption. The Lp regression problem has several applications in machine learning (Dasgupta al., 2009 Musco al. 2022 Yang et al. 2018). This includes low-rank matrix approximation, sparse recovery. data clustering. and learning tasks [Adil al. 2023]. In general, convex optimization non-Euclidean geometries a well-studied and important research direction. This motivates us to study Lp norms further and understand how they can fit within our assumptions.
We can perform other simple modifications of Lp norm that satisfy only inequality ( Example 6.4. Let 2 2. Then f(x: = ||=:l satisfies
5 with either of the curvature mappings
C (x p-1 V2 - f(x),
C2(2) pf(m) Vf(=)
We postpone comments Appendix E.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, norm to the logistic loss function obtain an objective function that satisfies (5). with the mapping from the regularizer. The objective function will be L-smooth, so also satisfies inequality (6).
7 Absolutely Convex Functions
addition to the examples from Section we now introduce the class of absolutely conver functions, and the problem of minimizing the sum of squares of absolutely convex functions. In this setting, as we shall show, the curvature mapping satisfying Inequality (5) readily available. Absolutely convex functions are defined follows.
Definition 7.1 (Absolute convexity). A function ó Rd is absolutely convex if
d(x) 2 (p(y) + (Ve(y), x y) Vx, e RR.
(8)
Above, Voi(y) refers to a subgradient of á y. Geometrically, means that linear approximations of á are always above the graph of -Ø in addition to being below the graph of & (same as convexity),
=(x) ) < d(y) + (Vo(y). y) S Φ(x).
Thus, any absolutely convex function is necessarily convex and non-negative. A constant function is absolutely convex if and only if is neg-tvgaeive linear function is absolutely convex if and only if it is constant and non negatiiee Moreover, the absolute value of any affine function is absolutely convex; that is, d(x) = (a. 2) + 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
Lemma 7.1. Absolutely convex functions have bounded subgradients. Example 7.1. If 2 1, then o(x) ||I|l, is absolutely convex.
7

---

7.1 Minimizing the sum of squares of absolutely convex functions
To conclude, we present the derivation of the curvature mapping C for the sum of squares of absolutely convex functions. Consider the optimization problem
11 = [(x)==
2+ arg min zERd
[(x)
where each Φ; is absolutely convex and a solution, J+. assumed to exist. Let fi == 0f, so that fx())) 2p: (z) The gradient of f is given by
Vf(z) = 1.4 Σ (f(=)= - R > - (á)))((
Since Φ; is absolutely convex, fi is necessarily convex. Indeed, by squaring both sides of the defining inequality (8). we get that for x, y E R
(()) (VI(v), y) (V v). S ((x)).
Summing these inequalities across and taking the average, we find that the curvature mapping can be set to,
C(x) 2 n Σ (o())Vo(())".
In Appendix G provide experiments objective functions that are in this class.
8 Experiments
(a)
10
10
(c)
10
1001
m
Poljet
Figure Logistic regression on a2a dataset with L2 regularization.
(a) X = L 10
(b)
10 3
(c) L 10
Figure 2: Logistic regression mushrooms dataset with Le regularization.
Through our experiments, we highlight the effectiveness of our methods on standard convex opti- mization problems, especially when employing diagonal curvature matrices. We use MacBook Pro with Apple MI chip annd 8GB RAM. The datasets are from LibSVM [Chang and Lin 2011 First, let focus on solving the binary classification problem:
f(x) = Σ log(1 + + -ubae))) + A||=11p-
where a; d and by E (-1, 1) are the data samples. The regularization weight À proportional to the L-smoothness constant of the logistic regression instance.

---

In the first experiment, we use L2 regularization. Therefore, f is L-smooth and j-Strongly-conye conveex so C(r) pI. This experiment demonstrates our LCD2 and LCD3 outperform standard adaptive methods for convex optimization, such as the Marzilai-Borwent Malitsky-Mischenko [Malitsky and Mishchenko 2020] step sizes. As mentioned previously, this setting, LCD1 recovers GD and LCD2 has a closed-form solution coinciding with LCD3. 12 show that LCD2 consistently outperforms Polyak. As expected, the gap increases with À because C(x) only stores information about the regularizer. Thus, increasing À shrinks the localization set of LCD2 so its improvement over Polyak grows. Importantly, since LCD2 has a closed form solution, its cost-per-iteen per-iteration is the same Polyak.
[Barzilai and Borwein, 1988] and
In the next experiment, we use L3 regularization. In Example 6.4 we propose two C(z) matrix candidates for ||=l Here we decide on the diagonal variant (z The objective function is no longer L-smooth, due to the non-smooth regularizer. As result, we run LCD1 with the smallest Le such that the method converges. Additionally, LCD2 no longer has a closed form solution, so the projection algorithm must be deployed. To perform fair comparison of our algorithms, we show both time and iteration plots.
Figure 3: Logistic regression on mushrooms dataset with Lg regularization iteration convergence.
(
10
(b)
(c)
10 -2
LCD3
Figure 4: Logistic regression mushrooms dataset with Lg regularization time convergence.
Timetri
302
Tirelns
Tiretnd
(8) L 10
(b)
A
10
(c) À = L 10
Polysk
LCD1
LCD2
LCD3
Figure 3 displays similar to the L2 case improvement LCD2 over Polyak, which grows with Our heuristie LCD3 can produce satisfying results, experimentally. However, its convergence cannot be guaranteed. In fact, as À increases it becomes unstable. LCD1 converges at comparable pace with the other three methods initial steps, yet the limited adaptiveness slows down later on. Figure 4 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 ((nd). All other operations performed by LCD3 and LCD1 are (dd) The method with the most expensive update rule is LCD2. every step it performs around rounds of the projection algorithm, each costing (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 (dd3) cost is bearable when n >> d. Moreover, our examples usually allow cheap diagonal matrix methods. Further experiments are in Appendix G
Conclusion
We explored adaptive matrix-valued stepsizes under novel assumptions that reinforce convexity and L-smoothness with extra curvature information. Under our assumptions, proposed LCD1 and LCD2, which generalize 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 variety of datasets, demonstrating strong empirical performance. The main limitation of our analysis the restriction deterministic setting. We also acknowledge that the assumption has yet to be explored in its entirety. 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-KA 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 thankful to the KAUST Al Initiative for office space and administrative support.
References
F. Abdukhakimov, C. Xiang, D. Kamzolov, and M. Takáë. Stochastic dradient descent with precondi- tioned Polyak step-size, preprint arXiv:2310.02093, 2023.
D. Adil, R. Kyng, R. Peng. and S. Sachdeva. Fast algorithms for rp-regression, preprint arXiv:2211.0333 1.0963,, 2023.
M. Al-Baali and H. Khalfan. An overview of some practical quasi-Newttn methods for unconstrained optimization. Sultan Qaboos University Journal for Science, 12(2):199, 2007. ISSN 2414-536X, 1027-524X. doi:
M. Al-Baali, E. Spedicato, and F. Maggioni. Broyden's 's quasi-Newton methods for nonlinear system of equations and unconstrained optimization: a review and open problems. Optimization Methods and Software, 29( 9944,44, 2014. ISSN 1055-6788, 1029-4937. doi: 10.1080/10556788.200 856909.
Barzilai and J. M. Borwein. Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8(1):141-148 Jan. 1988. ISSN 0272-4979. doi: 10. 10.1093//manum/8 1.141. URL
https://doi org/10. 101300999mmmm itaiimmanmmm///mmm 8 141
H. H. Bauschke, Bolte, and Teboulle. descent lemma beyond lipschitz gradient continuity:
First-order methods revisited and applications. 42(2):330 348, 2017. ISSN 0364-765X. doi: 10. 1287/moor.201..0g URL http:ttt//bbboonnntiiee 0817 Publisher: INFORMS.
informs org//oi/o/ 12.////001..11//o0000.. 1287/moor 2016
C.C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):7::127:27,, 2011. ISSN 2157-6904. doi: 10.1145/ 1961189.1966
F. H. Clarke. Optimization and nonsmooth analysis. Society for Industrial and Applied Mathematics, 1990. ISBN 978-0-89871-256-9 978-1-61 197-119991--999
A. Dasgupta, P. Drineas, Harb, R. Kumar, and M. Mahoney. Sampling algorithms and coresets for L, regression. SIAM Journal on Computing, 38(5):200--2078, 2009. ISSN 0097-5397, 1095-7111. doi: 10. 137/0770666577.
Dennis, Jr. and Moré. Quasi-Newton methods, otivation and theory. SIAM Review, 19(1): 46-89, 1977. ISSN 0036- 1445. doi: 10.1137/1019005
7. Dong, Y. Zhang, 7.-Q. Luo, J. Yao, and R. Sun. Towards Quantifying the Hessian Structure of Neural Networks, May 2025. Utt. wwwp:/oo///ab//bboooo 220.2555000000.. 7xXiv:2505.02809 [cs].
R.-A. Dragomir, A. B. Taylor, A. dàCrMAspremont, and J. Bolte. Optimal complexxiy and certiifccatooo of bregman first-order methods, 2022. ISSN 1436-4646. URL. htw.tttte://do.or////./. 110107-021-0161--
10

---

J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2121-2159, 2011.
R. M. Gower, D. Kovalev, F. Lieder, and Richtárik. RSN: Randomized subspace Newton, 2019.
Hanzely, D. Kamzolov, D. Pasechnyuk, A. Gasnikov, P. Richtárik, and M. Takáč. damped newton method achieves global (zz) and local quadratic convergence rate. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
G. E. Hinton. Neural networks for machine learning. Lecture slides, CSC 321, University of Toronto, 2014.
S. M. Kakade, S. Shalev-Shwartz, and A. Tewari. Regularization techniques for learning with matrices. Journal of Machine Learning Research, 13(55):1865-188 2012.
S. P. Karimireddy, S. U. Stich, and M. Jaggi. Global linear convergence Newton's method without strong- strong--onvexity Lipschitz gradients, 2018.
D. P. Kingma and J. Ba. Adam: method for stochastic optimization, preprint arXiv: 141..9980 2017.
D. Kovalev, R. M. Gower, P. Richtárik, and A. Rogozin. Fast linear convergence of randomized BFGS, preprint arXiv:2002.11337 2021.
S. Li, W. J. Swartworth, M. Takáč, D. Needell, and R. M. Gower. SP2: a second order stochastic Polyak method, preprint arXiv:2207.088 171, 2022.
Y. Malitsky and K. Mishchenko. Adaptive gradient descent without descent. In Proceedings of the 37th International Conference on Machine Learning, pages 6702-6712, Proceedings of Machine Learning Research, 2020.
K. Mishchenko. Regularized Newton method with global ((1/k²) convergence. SIAM Journal on Optimization, 33(3): 140--1662 2023. ISSN 1052-6234, 1095-7189. doi: 10.1137/22M44487755
C. Musco, C. Musco,
Woodruff, and T. Yasuda. Active linear regression for èp norms and beyond. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 744-753, 2022. doi: 10.1 1110/FFOC554457222220000
Nesterov. Introductory lectures on convex optimization: a basic course. Applied Optimization. Kluwer Academic Publishers, 2004. ISBN 978-1-4020--553--.
Nocedal and Wright. Numerical optimization. Springer Series in Operations Research and Financial Engineering. Springer, 2006. ISBN 978-0-387-303003-1.
B. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4): 1963. ISSN 00415553. doi: 10.1016/0041-553366) 90382-3.
B. Polyak. Introduction to optimization. Translations Series in Mathematics and Engineering. Optimization Software, Inc. Publications Division, New York, 1987. ISBN 0-911575-116.
Z. Qu, P. Richtarik, M. Takac, and O. Fercoq. SDNA: Stochastic dual newton ascent for empirical risk minimization. In Proceedings of The 33rd International Conference on Machine Learning, pages 1823-1832. PMLR, 2016. URLLtttps://prrcceddngg .mlr hla..prres/vv//qque qub46..//ub..oo// html ISSN: 1938-7228.
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of Adam and beyond, preprint arXiv:1904.09237,, 2019.
H. Robbins S. Monro. A stochastic approximation method. The Annals of Mathematical Statistics, 22(3):400-403 1951. ISSN 0003-4851. doi: 12.1214/aoms/1 /eepnms//11777991 177729586.
A. Rodomanov and Y. Nesterov. Greedy quasi-Newton methods with explicit superlinear convergence.
SIAM Journal on Optimization, 31(1):785-8) 2021. ISSN 1052-6234, 1095-7189. doi: 10. 133/ 20M1320651.

---

J. Yang, Y.-L. Chow, C. Ré, and M. W. Mahoney. Weighted SGD for 2, regression with randomized preconditioning. Journal of Machine Learning Research, 18(211):1-43, 2018.
D. Zhou, S. Ma, and J. Yang. AdaBB: adaptive Marzilai-Borwein method for convex optimization, preprint A.ii:24011080222 2024.
12

---

Appendix
Table of Contents
Related Assumptions
14
Local Curvature Descent (LCD1)
15
Derivation
15
B.2
Convergence proof
15
Local Curvature Descent (LCD2)
18
Derivation
18
C22
Convergence proof
20
Closed-form solutions
D Local Curvature Descent 3 (LCD3)
23
D.I Derivation
23
D.2 Convergence for quadratics
E
Properties & Examples
25
On the lower bound
25
E.2 On the upper bound
28
E.3 Lower bound examples
30
Lower and upper bound examples
36
Absolutely Convex Functions
Examples
41
Functions with minimum
44
Real valued functions
47
Multiarriblle functions
51
Extra Experiments
53
1 Regression with squared Huber loss
53
G.2 Ridge regression
53
13

---

A Related Assumptions
In this section, we highlight the main differences and advantages of Assumption 2.1 over other related notions in literature such as relative smoothness and relative convexity [Bauschke et al. 2017
Dragomir et al.
2022
Gower al.
2019 Qu et al. 2016].
Bauschke et al.
2017
proposed the notion of smoothness relative to a kernel function. A kernel R on closed convex subset C' of IR is defined as follows,
function h I="
Definition A.1. (Kernel function). A function h : Id + E is called kernel function if,
(i) h is closed convex proper,
(ii) dom h = C.
(iii) h is continuously differentiable and strictly convex on int dom h + 0.
The Bregman distance kernel function is defined as,
(r y) = h(z) h(y) (Vh(y), x -)), Vo E dom h, y E Vdom h. A function f is relatively smooth with respect to / if there exists constant L such that Lh f is convex on dom h. This implies the following inequality,
f(x) S (1) + (Vf(y). x- y) + LDn (r, v). Va E dom h, y E Vdom h.
Notably, if we choose the Euclidean kernel function h(x) = |=ll we recover the classic L-smooth assumption. Suppose M $ is positive semi-definite matrix. If we select h(x) } | M get an inequality that seems similar to Equation (6).
I 1 y M Ax, E Rd.
f(x) s f() + (Vf(v), y)
(10)
2
Furthermore, Qu et al. 2016 propose a corresponding lower bound assumption on based on another positive semi-deñnite matrix G sd.
f(v) (Vf(x), v) 2 vlle S f(x), Vz,y YE.
(11)
The crucial difference between Assumption 2.1 and Equation 1T)) and Equation curvature matrix in Assumption 2.1 can vary with y which allows to capture large class of functions. For instance, a simple function such as the square of the Huber loss given in Example 66. does not satisfy Equation (IT) for any G * 0 but does satisfy Assumption 2.1 Furthermore, the motivation for our assumption is to leverage local curvature information to develop adaptive algorithms. Hence, the fact that Cyy) varies with y. which is the current iterate in our algorithms, crucial to the performance demonstrated by our numerical experiments.
is that the
Additionally, due the variable nature of the norm Assumption 2.1 is not clear that there exists an elementary kernel function h such that LD₁ (z, (2. y) 5 ||æ v Cl((() The difficulty arises
from the fact that the matrix C(y) varies only with y. Therefore, we believe that Assumption 2. is not captured by the relative smoothness framework.
The Hessian of f has also been used to define other notions of relative convexity and relative smoothness. Specifically, there exists constants Í. 2 ja
such that for all x, y E Rd.
i ||
f(x) S f(y) + (VI()), y) + 2
y1 =11==
(12)
((v) + (V)(),x) 1 - f(x).
(13)
Assumption 2.1 does not restrict the curvature matrix to be the Hessian. Besides, our goal is to develop adaptive algorithmss without going the route of fully-fledged second-order methods. Thus, leveraging readily available local curvature information without expensive computation of the Hessian is an advantage of our assumption and methods. Further, Li et al. 2022 recently proposed extensions of the Polyak step size, SP2 and SP2+, that utilize the Hessian but can be unstable in practice. Therefore, we develop our assumption with the aim to rigorously utilize second-order information without the need to compute the Hessian.
14

---

B Local Curvature Descent 1 (LCD1)
B.1 Derivation
Suppose that the upper bound in (6 from Assumption 2.1 holds. Then, at a given point xb+1 E R
we have:
f(x+11) S f(1x) + (Vf(s)) -xk) | sxllC(e))+oel
Vog R
Minimizing the right hand side with respect to 2 we find that:
1 F3 - (C(=)) Lcl] Vf((x)).
(14)
In particular, the matrix that pre- multipliess the vector is always invertible, since C(x) is positive semi-definite for each x E Rd.
B.2 Convergence proof Lemma B.1. Let Assumption
2.1 hold. For all k 2 the sequence (IN) of LCD1 is such that:
2 (f(#++1) f(x.)), Vk E N.
| =x.12 1 2.112 <
(15)
Lc
Proof. The proof is achieved by carefully bounding terms. For this reason, split it into three steps.
We seek a connection between the two distances in the geometry induced by C(æx) == C(*x) + Lel:
| -.-1le (((() || Fk+1 1 1k+1 1.11 ((())
= =1|=x - - ((( +2
+2( ((((x))((aR -xx+1), Ita
+ +| xz 22112
|| x (((mm))))))
(((m))
+ (V Ix+1 x.) + ||I 2.112
= | xx ((
+ 2 V (# TA+1 x.) + || 22112
Rearranging the terms we obtain
|| - x. (222)))))) - || - x. 2 = - -1 - I& (2()) - (V)())). x.)
-1|01+1 - xx ((
- 2 -2(V ( - 8k + Izk - x+m)
xk++
-1| FA (((za) - 2 (xx) (ok),,kk Tk+1 Inm
+ 2 2 (x)), -xx).
In partieular, wish bound the inner products.
Rearranging the lower bound (5) Assumption 2.1 for the pair (II, x.)):
2 V f(xx), x. m&) s ((f - f(xx)) - | - x, 11.112 12
In similar way, massaging the upper bound (6) of Assumption 2.1 for the pair (#4+1, 2K) one can derive: -2 (Vf(zx), Ix+1 - xx) S || Txll(((.)) 2(f(xx) ff (xx+1))
Combining two previous steps we find:
|| - xz 11( - || - 2x.12 ==
5 -11 - x2 2212) + || - 3y (2
+ +((((x)) f(xx+1) + +(( ((0e))-( - -(xx)) - 1|amk - 1x1
= =2(((x.) )- [(xx+1)) - || - -xa12cce)
15

---

The positive term 12 r. (I(((e)) is on both sides of the inequality, so we can cancel it out:
| x. #+1(((())) a|=k x-lliat S ((f(x)) f(*++1))-
Having almost removed all the C(rx) norms, it suffices to apply the crude bound:
Lel| - x. 112 | -x || =x.l(((m))*
which holds since Lel 3 C(ax) + Lel = C(xx).
Therefore, we obtain
|| z. z.llior I 2. Ilec I 2(f(r)) f(*x+1)) -2(f(ER+1) f(x.)).
Reordering gives the claim.
Lemma B.2. For any k E N, the iterations of LCD1 satisfy:
f(#x41) - f(xx) v - S
(16)
Proof. Let us remind the form of the updates for each A: E N
Fk+1 mh [((x))] Vs(x)),
where C(æx) C(xx) LeI.
By Assumption 2.1 we know that
f(xx+1) f(x))
+2 (Caa)
= f((x)) マ (V
and the claim follows by simple rearrangement.
Having the lemmas established, let proceed to the proof of Theorem 4.1 We want to show that if f: Rd R satisfies Assumption 2.1 then for any N, the iterates LCD1 are such that:
Lc
f(xx) f(x.)
I -x,11²
(17)
2k
Proof. We use standard Lyapunov function proof technique. For completeness, let us report it.
By Lemma B.2 function values get closer to f. across iterations. By Lemma B.1 the vectors get closer in norm to an optimum.
Then, we can combine the two positive decreasing terms LCll - 2.11 and f(x)) f(x.) into Lyapunov energy function:
& = Lo 11 - 112 + 2k(((()) - f(x.)),
AkEN
In particular, Eu Le |xo 11 and we claim that Eg decreasing function. To see this, start by rewriting the difference:
Ex+1 Ex = 2(k + (((()))))-((2)))
f(x.))
+ +C - -x,11 Lc 1 1=112
= =2(f(rx+1) - f(x.)) + 25 (xx+1) f(x+) - f(xx) + f(x.))
+ - =
6/ x.11
-
- f(xx)) + 2 2x(((1+1) - f(xx))
+ +cll - = Lellaa - =x,1?
16

---

It is evident that we can apply our Lemmas as follows:
[( - f(xx) 0
by Lemma B.2
(18)
Lcl|#x+1--5 x. - LCIl=R x.12² S -((((()+1)) f(x.))
by Lemma B.I
(19)
Putting everything together:
Ek+1 & I 2( - f(x))) - ((f((x+1)) - f(x.)) = 0,
showing that & is decreasing. As particular case, we then find:
2x(](=*)) - f(xx)) < & S & LeI1 - -x.11
which reordered recovers the rate GD with stepsize 1. i.c.
Le 20 xx
f(xx) - f(x.) S
2k
Remark. For quadratic functions Assumption 2.1 is satisfied with C(x) equal to the Hessian, and Le = 0. Thus, LCD1 convergences in one step for this class of functions.
17

---

C
Local Curvature Descent 2 (LCD2)
C.1
Derivation
Consider the minimization problem for the update step of LCD2:
1 111 rxel?
min xELo(#s)
2
(20)
where
Lc(xx) = { " M
1 Rd 1S(x))(x)))))))) + (VS(a)), mz) 221l sullo( S4
(21)
If C(x)) is the zero matrix, know this problem has closed- solution. Therefore, focus on the case where C(Ix) a non-zero matrix. Moreover, we assume that og & X. The Lagrangian of this problem is:
L(x, B) -)
-1 -11l=
2011 + (Hll= Is (xl(C(e))) + (Vf(zz), x xx) + f(xx)) ff
-aa)
where B 2 For optimal and B have that V2 B) -0. Therefore,
I -- + B [| I& (()) + Vf(xx)) = O.
Isolating for find that:
z= 2k B [+ 3C(xx)]
We 33 of the constraint is tight. The next step would be substitute into the constraint and solve for B:
+ [(xx) Sx 0. b - xx - (VI(zz), - xn) -
Despite the left-hand side being a scalar function of 3, we cannot obtain a closed-form solution for iterative root-finding sub-routine such Newton's method to get an
3. However, we can approximation of 3 cheaply and effectively. By substituting in the value of I. we see that we need to find the root of the following function:
3²
H(3)
9& T I 3C(xx) C(*x) [ 3C(xx)]
(22)
2
3gh [+ [++x((=)]] 9k + AR.
To simplify notation, let C C(xx.. fxxx and A. = f(xx)(())))))))))))) fa.
In the following proposition, we confirm that H has a root in the interval [0, oo). 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 quadratic rate. In particular, we do not need H to be monotonically decreasing; nonetheless, it an interesting property of the problem.
Proposition C.1 (Properties of H). Let H be defined in Equation
22
Then, for 0:
H(0)= > 0, H'(3) < 0, H") > O, lim H(3) <
(23)
8
Proof. W.L.ogg. assume that a symmetric matrix. As result, C is orthogonally diagonalizable let C QDQ where D is diagonal matrix, and Q is an orthogonal matrix such that QQ Manipulating the inverse matrix in the definition of H. we find:
I 3C(x)) [QQ BQDQ 1 [Q[I DD)Q Q 3D] QT.
18

---

Let g: : QT Let D, represent the 1t entry of the diagonal of D and 9 represent the 2th entry in g. We rewrite H as:
82_
H(3)
2 9
Q
[I+
3D]
D 3D]
Q 9 3gg Q 3D] g
8²
2 5
[+ [+
D
D
3D] -
I+ 3D] g + A
8
d
93 Dj
> 1+ 3D,
A
2
(1 + 3D,)²
By inspection, H is rational function and the derivative is easily found;
D
D2 + 3D)33
of Dr 1
(3(3) = 3
+ 3
+ 3D.
BD,
1=1
gr
3D)3
Since C is a positive semi-definite matrix, D; 2 0 for all i. Thus for 3 2 0, we have H²( S 0. Since the null- sull-space of an orthogonal matrix is the singleton of the zero vector, the product ğ - Q-g different than zero when g + O, which holds by the assumption 2g & X, Therefore, there is at least one Di that is non-zero and thus, HB) # O. The second derivative of H is,
DDD. 3D.
3 H" -3)
Σ 1=1
By similar arguments used for the first derivative, we can show that (3) > 0. To conclude, we will show that lim H3) < O. We discuss two cases separately.
Suppose C is not invertible. Then, there exists an entry i of D such that D, = O. Without loss of generality, suppose that the last entry Da, is equal to 0. The same reasoning will apply if more than one entry is equal to O. Taking the limit:
82
d Σ
LD Dj
d
lim H(B) = lim 80000
3
Σ
+ +
80000
2
(1 + 3D,)²
1+ BD:
1=1
1=1
lim
B2 d-1
Σ
g
Dj
d-1 >
19
22
Bo9 +
Ak
3-000
2
(1 + 3D,)²
1+ BD;
1=1
1 d-1
d-1
g
9
+ AB
+
lim -3gg
2
Dj
Dj
8400
i=1
1=1
-00
<0
Now suppose that Cs invertible. Then, D; > 0 for all i. Differently from before:
8²
of
gh
lim 8-500
H(B)
lim
+ A
33000
2
(1+3D.)2 3D.Y²
(1+
1 3D
d
d
Σ
9
+ +Ax
2 1m1
D;
D
i=l
D
9 0 D 9 A
1 T QD 'Q T
29
g +
1 LTC - A
19

---

Recalling our definitions, the right hand side is:
lim (3) - - 8-000
+ f(ax)) - fa.
By Lemma E..
lim H(3) < 0. The inequality is strict when f(xx) 1. * V 1- In the case where equality holds, we have that limg->oe ((3) = O. Therefore, H does not have a root in the interval [0, 20) but the solution the optimization problem is obtain when This corresponds to the following optimal solution ē:
I 2g. (xx)
(24)
Interestingly, under the same condition, LCD3 takes step in the form 2k+1 = 22 - (xx
An example of setting where the equality condition holds is when f is convex quadratic and C is the Hessian of f- One can see that the update step of LCD3 and LCD2 are equivalent to Newton's 's method for that case so they both converge in one iteration.
may seem that using Newton's root finding method is impractical because computing defined in
Equation (22) for given requires performing a matrix inversion. However, this can be avoided by computing the eigendecomposition of C(rx) at the beginning of each step of LCD2. Then each subsequent evaluation of H done by Newton's 's method sub-routine only requires inverting diagonal matrix and not the full matrix. Thus, the main cost at each step of LCD2 is computing the eigendecomposition of C(z2) once, which in practice is much faster than computing the inverse. Furthermore, if C(rx) is a diagonal matrix, the eigendecomposition of C(TR)) is itself so each step of LCD2 becomes even cheaper. Also, in practice, Newton's 's method for root-finding terminated when H < c. Therefore, in the case where
f(xx)
the method will run until a large enough / is obtained and the step will become numerically equivalent 2g C-1 (21(2)) V f
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 (0066). Practical versions of such algorithms do not iterate until convergence but are content with an approximate solution that can be obtained in two three iterations.
C.2 Convergence proof
Lemma C.1. Let Assumption 2.1 hold. For all l: 2 O, the sequence (πK))en of LCD2 obeys the recursion:
[xx+1 - v. S || x.11? || - xx
Hence, for any k 2 1, we have
|| x=ll² 1 I.11l 11?
min ostsk-1
(25)
Proof. Let us write down the first-order optimality conditions for the optimization problem at Step of LCD2:
(at - 2x+1, Fa+1
y) 2 0, Vy E Lc(xx).
(26)
Since v, (xxx), for any 2 we have
||0411 I. ||
||T - xz 2 (xx 2k+1, Tb v.) + || -x
= || - 22,1 - 2 (xx - Ik+1, Tk+1 x.,)
2 (rr Ik+1, Tk 21+1) + || 1 2xa11
||r - x2,12 2 2 2xxx - 2k+1 2t+1 - x.)) - | xx 11?
26
IK - x. 2 || x3
Summing up these inequalities for l: 0, ..... K 1. we obtain 25
20

---

Let proceed to the proof of Theorem 4.2 for LCD2. We show that if f R 7 R satisfies Assumption 2.1 for any the iterates of LCD2 are such that:
Lc 20 x.
min Istsk
f(x)) -
2k
Proof. Since Jk-1 E (1re) we have
f(xx+1) f(zx)= + xx+1 xx)
2x) + 108+1 Ixllo
= f(xx) + (Vf(Tx), Tk+1 - Ix) + 2
xk+1 - xx xxll(((e))
|| - m 11 ((())) + 2
| - xz xxll((mu)+
1
[ + (V5(x)), F4+1 - .x) | xz (()))) 11l - 12gl--alll xxll Lel
21
J+ 2 |k++1 - spkliec
S. + Lc 2k+1 IKl l|
By rearranging the above inequality and applying 25 from Lemma
C.I
we get
Lcl|2141 x ||
min OSiSk-1
f(x+1)) - S.
min ostsk-1
2
LcIla0 x=,1²
2k
Remark. For quadratic functions Assumption 2.1 satisfied with C(x) equal to the Hessian, and Le = 0. Thus, LCD2 convergences in one step for this class of functions.
C.3 Closed-form solutions
In the main text, we argued that the update step of LCD2 has closed-form solution in certain special cases. One interesting case when C(z+,) is a rank one matrix. the setting of minimizing the sum of squares of absolutely convex functions, present a special rank matrix and the corresponding update step of LCD2. For general rank one matrices, the update step is not as interpretable or insightful we leave out the computation.
Let f() E of (z) where o; Rd with the following curvature mapping:
+ IR is absolutely convex. Then f satisfies inequality (
Cly) 25(r) V(()V
If we use the localization set defined by this curvature mapping, obtain closed-form solution to the LCD2 update step. To simplify notation, let gh := Vf(x)), f& : f(xx), A == f(xx) - fa, D -D(x)) and Q Qxxx). Consider the orthogonal decomposition of C(æx):
D(xx)= Diag
9x gh
2
0, O...,. 0)
(xx)
19
Ok
Gk.1
gk.d
where Ik.1. I are d - orthogonal eigenvectors that are all also orthogonal to Ok-
From Appendix C we know that to obtain closed-form solution of LCD2, must find the positive root of the following function:
a H(a) 2 Q(I aD) -DI - gk ag Q T
aD) gk + A
SKlgT gb)
25x 9b + A
= 2
(2fr ag g2)
2fx + ag gk
21

---

The second equality comes from simplifying the matrix multiplications and observing that,
a = Diag
2
O,
0)
Q Oh -
1l1
OJT
2fx agg 9h
Let g 9k- Since C is rank-one matrix, we can simplify and realize that it is quadratic function of a,
flee (2fa + av) 2fx + +.0
2f
((a)=
a As =
Therefore, we will have at most roots and there must exist unique positive root that corresponds to the solution of the problem (the optimalLggrange multiplier). We can solve this quadratic to obtain an interpretable update step for LCD2. To start, we multiply the entire equation by (2ft av) and simplify to get,
(o²Ax fav")a² a44fav 4f + 4fāa
By observing that A fK f. can simplify the expression further,
S.0222 4faJ.va 4 00
Therefore,
4fkf.u V (
25E + 25R.III
2f.0²
SWU
To determine which root is positive we can rearrange the terms to see that,
a
f.v
For a to positive we must select the positive sign. Now recall from Appendix that the update step of LCD2 is defined as follows,
Is - ae(I + +C) -1
1k+1
aQQ( aD)
F4 7k9k:
where 7k-
2fc 0' 2f, For
We substitute
2faf. + 2f fnt.
5.V
into "i to get
2
8.V.
2fk
2f
F.E.
2fr 2V5uf
7k
2 + v
-2fe1.
-2fe1.+2/rv
5.0
Therefore, conclude that the update step has the following form:
2 - ff(xx), (s()))
1++1 = 2k
[V)(x>)1
The update step of LCD2 differs from the classic Polyak stepsize in that we have / (xxa). instead of fa and we multiply by 2.
Remark. case C(x) = cl. for c > 0, LCD2 reduces to LCD3. Thus, the closed-form solution exists.
22

---

D Local Curvature Descent 3 (LCD3)
D.1 Derivation
Suppose the optimal value f. is known. While the update step of LCD2 does not have closed-form solution, the following update step does:
3k++ arg min re Co(xe)
|| - J& =(()((())))
(27)
where Lc(2x) is the same localization set defined in (11 Instead of using the Lg norm, we can use the norm induced by C(rx). Hence, this algorithm referred LCD3. The benefit of using different norm is that we can obtain a closed-fowe -oom solution to this constrained optimization algorithm.
The Lagrangian of this problem is
a(x,a) x Ece + (f(x)) (Vi(xz), mk) | Iu llcce f.).
is the optimal multiplier, then for optimal & we get VnL(E, a:) = 0. The gradient is: Va a)) = CT xk) + (V)(xt) C(ax)) ( - mx)) = 0.
Isolating F, we get:
ā [C(x))] fxxx).
5 Ik
(28)
Lett = 1+o ā 0, on (x(E)) which means that the algorithm converged since 2ı Lc and only if Ih X. Then, for generic update, we will have of 0. Imposing V. V. a which means that the constraint must be tight:
f(xx) + (Vf(xx), - =x)) 2x)+ +1 Iallo(ua) - fa =
Plugging ā = =(() = Ø()) into the equation gives
12 (V((x)) [C(xx)] (C(aa)) ((xx).
(((
2
The two inner products are norms of the form we can write:
V f ( and with more compact notation
2(f(xx)
22 2f + [V [[]((x)]] [c(x))]+
0.
This equation has two roots summing up to 2, but only one of them can be of the form = only one of them can be smaller than 1, with expression:
&
since
14a
2(((x))-1
t=
(29)
(7f(=x))
Substituting back
& I46
into 28
where / is given by (2) leads the method
2(f(zk) f-)
(
Tb+1
Th
[V [[(av))
To realize that the scalar component of the stepsize is well-defined, suffices to show that:
2(f(zx)-1 2 0,
(30)
(++) [[
which follows by reordering the result of Lemma E.5 for the pair (Ik, X.).
23

---

Then the update rule has closed-form solution:
2(f(x)) - f.) [V[()))
1h++1 2%
77
LCD3 [C(x))]] (Irx),
LCD3
(31)
In particular, the argument of the square root is always positive, making LCD3 well-defined. Routine
331 is promising: we apply scalar stepsize 7 LCDS that is similar in spirit Polyak's in Equation (4
and "reorient" gradient according to C = [C(xx)]"*
Moreover, at each step, we aim to be as close possible according to local upper-lower bounds on f.
Experiments in section and G show that the algorithm converges, but is slower than LCD2.
D.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 (31) takes the form of Hessian times gradient.
Let (, (1) = a- x b,1. where ag E Rd and b E IR for i (L....,m... We know from Example that is absolutely convex. Then problem (9 becomes
[(x) = 1 Σ
min ZER
(a x - b.)
t=1
x is such that (x(x)) + for all i, then Vol(x)) in Section 7 we get
a z-b aie Therefore, in view of the computation (a)
a 2i(x)
Q x
b Φ1(x)
C(x) (Z)
ai
ai
n
i=1
2
(a x 6,)² a:a.
Σ
a;a;
(2)(2)
of (x)
Therefore, for least-squares problems, the LCD3 method of 31 moves in Newton's direction. Furthermore, 7
LCD3 since for quadraties we have the identity
f(xx) f. 2 (
Indeed, this follows from Lemma E.5 and the fact that for quadraties, equation (5) is an identity. So, for least-squares problems, LCD3 reduces to Newton's method, and converges in one step.
24

---

E
Properties & Examples
E.1 On the lower bound
For clarity, the statements repeated, but correspond to Lemma 5.1 and Corollary 5.11
Lemma F.1. Suppose J, f1.122 Rd IR satisfy Equation ()) with curvature mappings C, C1 C2
Rd + $4, respectively. Then, the following functions satisfy Equation
(1) f + a R, with C());
(2) af for a 2 O, with aC());
(3) f1+ f2. with C1(+) C2(-).
Proof. We prove each statement separately. (1) For any y, R. it holds:
g(z) = + + (Vf
x 1) + - vllc + aa
= + (Vg 5) yllow
(2) Similarly, for all x, y E Rdd one has:
( (V))) v)
2 yll vl(cow) ((v)
= a + (aVS(y)x - u) +
2 =21aa(x - y) w)(((())
= (Vgly), y) + |a(s - y)llow
(3) Concluding, for arbitrary vectors:
g(x) = fi()) + f2(x) 2 f1()) + (Vfi(),, - 1) + +5 - - ylic,())
f + (V/2()), v) + v
=g(v) + (V((), v) + -- - v -1l
Corollary E.1. Suppose f Rdd -> R satisfies the lower bound of Equation 5 with curvature
mapping C: Rdd + $4. Let Rd + IR be convex function. Then, h(x) = f(z) g(z) satisfies the lower bound with matrix C(y).
Proof. Since g is convex satisfies the lower bound with matrix C(y) = 0. By Lemma E. satisfies the lower bound with C(y) C(y).
Another lemma used to construct functions that satisfy the lower bound is the following.
Lemma E.2. Suppose f : RRd + IR satisfies Equation 5) with the curvature mapping C: Rd + Sd
Let A E Rdxm and b E Rd. Then g: mm - R where g(x) == f(Ar + b) satisfies Equation with curvature mapping C(y) = A C(Ay b)
25

---

Proof.
Without loss of generality, we can assume that C(y) is symmetric. Then,
g(x) = f(Ar + b) 2 (Ay + b) + (V/(Ay + b), Ar + b (Ay + b))
1
+ () (Ay + b)), AT + (Ay + b))
=syAy + b) b), A(r v))
1
+ (C(Ay+b) - U)) A(x y)
2
-fyy + b) (A Vs(Ay + 6), v)
1
+2
(A (ATy + bb)(( - 1),x-11
= =(y) + (Vg(y), - y) + (C()(( y), (Cl))(--v).z
Considering the right hand side and the left hand side, we have recovered the claimed expression. The only missing detail is proving that C(-) positive semi-definite. Let E R Since C(y) symmetric and positive semi-definite then C(y) = C(y) à C(y) and Cly) à is also symmetric. Therefore:
T(y() = x' A A(AC b)
= A ATCCTAAyy C(Ay b)
-(C(Ay +))+) AE) + +))
+ b)+ -(C(Ay+ + (C(AA
= -||c(Ay-b)
20. 0.
By the arbitrariness of 2, the matrix is positive semi-definite.
Lemma E.3. Suppose f Rd + R satisfies Equation () with curvature mapping C: Rd + Sd. Then the following inequalities hold for any 2, y Rd.
(I) (V)()) Vf(x), v) 2 || y (l
(2) (Vf(y) - vf(=), - w) || - و )
(3) (V)(y) - Vf()), v) 2 ج| v 12)))
Proof. Let present one proof in detail. The other two follow trivially. (1) By the definition of Bregman divergence:
= 1 - yl(c.
1
| y1 v1(o00)+((w)
+ $ =1l2
< DD((, v) D)(,,
(Vf(z) - v vf(y), x - v\
(2) Start with (1) and note that 1 || - y 0w))+ 2 111= v1 2
(2) Same as above but use that || - y v _ y ((
Lemma E.4. Suppose f gd lR satisfies
a - visc & (V)(x) Vf(y), x v)
-
for all x. y E d with curvature mapping Rdd $4. Then f satisfies Equation with curvature mapping C(-).
26

---

Proof. By the fundamental theorem of calculus:
f(x) f(v) - L/ (VS(y + 1(x w)), x 1) dt
(V/(g), x - 1) L." (V (( -f)) y) dt
L." (Vf(y + t(x -)) t(x - f) dt
= (Vf(g), 2 - v) +
M ( + /
7 ||t( v) (c) dt
(Vfly), v) + || vlccos) S tdt
(Vf(y),= v) + || vl(c(w)
Rearranging the terms we obtain that Dy(x, v) 2 1
| v desired.
Lemma E.5. Suppose that f: IR + R satisfies Equation 5
with curvature mapping C: Rd - S
Suppose that f differentiable and non-singular. Then
[V5(()) 2
V((())))) 1 2 ()(2,v), Vx, E Rd.
Proof. Fix E Rd. Suppose y Rdd is arbitrary. Let spl)) struction, Vy(l) V fly) ff()) Using this fact, it can be shown that for any u, g Dy(u, v) 2 1 Slluuellece ul Therefore, & satisfies Equation 5 with curvature mapping C, Hence, for v E Rd we have that (pv) 2 G(y) where G(y) is defined as
(V)))))(>).)))) By con-
1 " e Cl()))) Gly) = (()) + (Vp(u). y v) + 2
Observe that Vy((z) 0. Since yp is convex, x is minimizer of yp and we the inequality below holds:
p(0) = inf (vv) inf Giy).. y
(32)
By computing the gradient of G and setting it zero, find y C(v) + v such that VG(T) = 0. Therefore.
f(x) - (Vf(z),)) = p(x) 2 G(T)
=(()
((t) (V))
= =(v) - |V((r)ll 100) + 1 Vo(villc 1())
[(v) VV/(2), m) - [VVe(v))lc-0)))
- -V
f(v) (Vf(z),))
By rearranging the terms, we find our result since x and e arbitrary:
[V (7)(0)>>(((0lc-)) 2 / - +v)()))))))))))))))))))))))))))) (V)()),))
-f(w) -())) v)
-(())
X)
=Dy(o,a).
27

---

Lemma E.6. Suppose that f: f is twice continuously differentiable, then
IR + R satisfies Equation with curvature mapping C: R + S
C(x) = f(z),
for all x E Rd.
Proof. Let x. vf Rd and À O. Since f satisfies Equation we can substitute x Xuy x) and M(y - z) into the first inequality described in Lemma E.3 to find:
(V + Myy =)) Vf(x), X x))
2 Xyy x) 2
X2
I
x -00)))
2
By the Fundamental Theorem of Calculus, we further have that:
L. -)))
(Vi(x + A(y' =)) Vf()),((''))))))))))))))) x)
x)), x) dt.
Dividing the first inequality by xa on both sides obtain intermediate inequality:
1 1 ==llc())+((++( -
1
x (Vf(z + - x)) Vf(x), x)
2
1
/ (V'((+ - - -x)), - 22) dt
À 0
(V 11 - =))) - x), x²) dt,
from which we take A - both sides to get an inequality between norms,
Ilo x112000) $ /' (V2f(=((U - xx),0/ - x) dt
= -(V2 =x), - =x)-
Thus, 11 -
x 2|((( C(x) 1 fx))
S (v2
=2). -)). Since x, are arbitrary this implies that
E.2 On the upper bound
We provide analogous lemmas involving functions that satisfy Equation (6)
Lemma E.7. Suppose f Rd > IR satisfies Equation (6. Then for all x. y E Rdd we have,
(v)()) - Vf(x), - x) S | v vlldw Tcllx yll².
Proof. Take the sum of the two Bregmann divergences:
(Vf(v) v f(())v x) Dy v) (y(,.2)
< マタ |z v + 2 - v v
2 || v + Tolla -112
Lemma E.8. Suppose f: Rd - IR satisfies the following inequality with constant Le > 0 and
curvature mapping C: idd + s
Vf(()) Vf()), v) S ||r y Big Yx, E Rd.
Then satisfies Equation 66 with curvature mapping C and constant Lc-
28

---

Proof. We invoke the Fundamental Theorem of Calculus:
f(z) - ((v)) = /. (Vf(y + t(x - y)) x y) dt
(Vf(y),, - v) + [ (V + f(--txx--000 v)) Vf(x), y) dt
-Vf(y), x- v) + [ VVf(y + t(x 4)) vf(y), f)
S (Vf()) 5) {-1 |1((r wlloow
(V[(y)= v) + || v vllowtoo / ldl
(Vf(y), v) + | y v
Rearranging the inequality above we get our result, (y 2 1- vllcco)+er
Lemma E.9. Suppose that f : IR + R is convex and satisfies Equation (6 Also, assume that is differentiable. Then,
Vf(x) - VfWIl 5 S.500 (2(2.))
Proof. Fix x E Rd Suppose y E Rd. Let ((v) = f(v) - (Vf()).)) v)- By construction, Vy(()) Vf(v) Vf(x).
Using the above fact, we can show that y is convex and that for any u, Rd, we have Du(u, v) $ |u ollc( Therefore &p satisfies Equation 6 Now, let v E Rd be arbitrary. Since yp satisfies Equation ( plv) G(y) where
G(y) == p(u) (Vp(r), y v) 2 ly cLv+
Moreover, is minimizer of &p because V = 0 and yp is convex. Combining the last two facts, (xx) inf (w) 2 inf G(y).
y
y
We minimize G with respect to by finding a " E R such that VG 0. Since C(v) is positive semi-definite, C(u) + Lol non-singular. Then
(C(v)+ + Lc1) (()). Therefore,
f(x) - (V fz) = (xx)= s G(ū)
= =v(() - (Vp((),, + (cl)
+
((0) V (p))) V=(e)l V
1
p(e)
vp(ui] V
2
f(v) (V)()),)) - - ff - -c
Rearranging the terms we obtain
- - S 5((v) - f(x) (V/ V/
2
= =f(v) - f(x)
(Vf(x), -x)
f(v) f(x) - (V/(G),
= Dy(,,
Since v, were arbitrary, the claim is true.
29

---

1 Lemma E.10. Suppose that f ; Rd - R is convex and satisfies Equation 6 Also, assume that f is
twice differentiable. Then,
f(x) 3 C(z) + I.I.
Proof. Suppose x, y' E R2 and X > 0. Since f satisfies Equation (6
we can substitute x + N(y'- -x)
and X(y' x) into Lemma E.7
1
(Vf(x + Vf)) - =)) - | x)
2
X²
11 - -CI 2
The following equality is a direct application of the fundamental theorem of calculus:
(Vf(a + A(y - x)) Vf(x).)/ Vf())
=x)),// - x) dt
S. x (V² -2)1 -2) - -)),8/ - x) dt
Dividing the inequality by X2 on both sides:
2 Ely = ((e 2 [Vf( X V/(c), x))
1
(Vf(z + 1 vf(z),y/ --x =x)
1
[' >(v2f(z + - 2))( - 2). v/ x) dt
X
I (v² + =2)( - -x),2/ x) dt.
It suffices to take limits À - 0 to get that:
1l - x H(0 (V>I(x)([' - -2),2/ - x) dl
= (VVI(=))( - x),1// - =x),
allowing us to conclude with:
2 |l - x 2 =1C))) 1
2 1101 - =120002200
((C(x) + Lcl) x), 1/ x)
2 (V)f(=)() -2).1/ -))
Since y', x E Rdd are arbitrary, we proved the claim: f²)(x) C(x) + LcI.
E.3 Lower bound examples
Lemma E.11. Suppose p 2 2. Let Rdd IR where [(x) 1|
Then f satisfies Equation
in Assumption 2.7 with curvature mapping
C(y) p Diag (lvı p-2 ..... P-2 p-
v fly)
Proof. When p we have that C(y) 21. Then satisfies Equation 2-stronglyyconvex. Now suppose p For arbitrary x, y E Fdd an application of Young's Inequality yields
because ||x|| | is
(||0)| [|
(1lv p
(11v1p=9)=
|| 11
30

---

Rearranging, we obtain:
| 2 |1 p-2 + (
2 1]
Iul 2 0.
(33)
By applying Hölder's inequality, we get:
bal luv p-2 - |
| 1
(34)
and thus,
p d 2
2 || 11
1
m
2 1yv p-
:=1
By adding |<>1/ + (5 - 1) llvll, to both sides of Equation (34 and using Equation 33
we get,
||>||
P x 1 1usl" +
11) llvll 2 O.
2
To derive the result, we begin by rearranging the above inequality:
| p Mil 10-
(5 - 1) ltvelp
p
p d
I|yl1p - pll pllyl1 + 1 I1ul1
2 yi 10-2
1=1
d
= =Ivvll -
111p-1ll1113 1ll + p Σ
Us
V1
p-2 3. - Σ
1
p-2
0sg +
P
+
p
Σ
2
p-2
2
2
1=1
1=1
1=1
After reordering, we find:
|>< 1 2 1111 p
Vi 19a 10 24, - P
V |14 p-2
1=1
d
p
Σ
Uss Ival p-2 I3
+
P
+
p
Σ
|.a||
2
1ea1p-2
2
2
i=1
By performing some basic algebra and observing that
01 = py: 18:1
2
we obtain our result:
||=||/-- = 11ul1
pui l9a pP-2 (z; vi) p
Vi Vi p-2 x, +
+
p
l1s
p-2
2
2
1=1
i=1
Pye lwa 1ua1p= 1p-2 (ore yi)) lua1 P
Σ
y1 1ya
p-2
loral 2
11x12-2
d
1
=Ilvll,
Pys 19r Σ
1p-2 (xx - ve) + 5
(C(y)y,)) v) (C(y),, + (C(y),,a)
=
d
= -Ilv1l, + Σ pyi 19: 20-2 (zz - v1) + (C())(z (I-
2
1
= |Il| + (Vi(y), x - y) + 2 | y
Lemma E. Suppose p 2 2. Let f: R2d + R where f(x) = I|=01l/-- Then f satisfies Equation
in Assumption 2.1 with curvature mapping C(y) were the (i entry of C(y) is
Cz)(v) Tul| yius Wa 1-2 1u 1=2
p
31

---

or alternatively, in matrix form:
Cyy) = plyll, vf(w)
Proof. When 2 we get that C(y) - lvlll
2 yy Since || is the square of | which is
absolutely convex, f(x) ||=|| satisfies Equation 5 because the curvature mapping C ccorrsponns to the mapping obtained from absolute convexity.
Now suppose >> 2. Again by Hölder's Inequality, we have that
d
< ||lll
(35)
We can lower bound the left-hand side in the following manner:
d
r.y
Σ
Σ
miys 1
P--
1=1
Combining this inequality with Inequality
(35 and squaring both sides get,
2 d
2
wayl Ival -
||x ||
yil
1
Tayl lus 1--
Then we multiply both sides by
4.2
d
|
2002
p
Σ
Tiyh lys 1 P-2
(36)
2
From Lemma E.IT we know an application of Young's 's Inequality with some rearranging yields the following:
| (5r 1) llvllp | 1p 2 O.
Now multiply both sides by Ilyelp-
||x | | 1/ + P5 - 1) | |
P -ー
||ا
2 2-- 2 O. ||
(37)
Adding ||=]] + (5 1) I|ell 2r to both sides of Equation (6) and together with Equation we have that,
37
d
| + (2-1)
121p
2p
P
J.yi |y 2-2 2
2
Rearranging this inequality and proceeding with the following steps we obtain the claim.
d
xx|| 1 m (1 5)
12) l1
P
Σ
Jith 1ual"
2 1|
l1el1ß- plly1
P |1rl +
Σ
aat luil 221-22)
|ys1 p22
2|
d
d
= Ilulf
pllll
+ |rrl +
p
wath 10a1e-
aryyl 1
2| p
1=1
pllll
2
+
1| 1
p
J.yiiyy 1ua1 1ug1 20g
f=1
pll!l
|| 2p
|
+
1
((y)),
2
32

---

The last term seems complicated but can be expressed as a matrix inner product. Continuing,
pl + | 2 1
P
Iuil")
Σ lusl" l
+ 1 2
(C())),
1
1 pllll +
p
1all" 10s11
+ 1 ((y)z, 2)
2|
1 ((u)r,
1Il - pllllp + 21
yeniy lusl 1u:12 1u51 y/
2
1 2
-- - rl + (C()): v) + 2 (C(y))r
d >
|bl1 - pll plull +
Tilh Wal p-- 1/10-
24yhs luil"
1
+ (C(y),, 4) + 2 (C(y),, x))
d
(
= |el - plull + Σ
Till Ue 1=2
P
Σ ii=l
rith lve p-2
1us1
i=1
((ly), v) 1
(C))),,
2
To finalize, we proceed with the last few equalities:
ayyh lB p-2 )
|>> 2 lull plull +
Tilik lull
Σ
Σ Un 1us p-2
1y P p
+ + ((w)), v) + (C(y),,
d
d d
= lull plullp + Σ aalii Wua 1--2
Jxtlis 1-1l220) Us 1u510-2 yj
+ 2 (C()),))) v) + (C(y)æ,
d
= =Iellf plaalle + p Σ
Tzyle 19: 1-- (C(y)z, y) + (C(y)y, v) + + (C(y)z,))
d
d
= |l + p Σ
Titii 1/: p 2
Σ
l + (Clx - y) x - n)
i=1
d
|l +
py: 19:1
1111p-2 pp-2 (x= v1) + ~ | vll wl(2w)
1=1
= |ull (v)) - + ||00 vilcow
Lemma E.13. Suppose 2 2. The function fxx = ||>|| satisfies Equation 5 two curvature mappings:
with either of the
(1) Cly) 21 "I
C(y) rlly uyTT.
Proof. (1). When p = 2, we have C(y) 2I. Therefore, f satisfies Equation because ||ar|] is c-strongly-convex.
33

---

Now suppose > 2. By applying Young's ' Inequality we get that:
(1 [
(1lyll"
2 ||0|| 1|111
2
and rearranging
|
+ (2-1)
|1vl 2 |1111~02|(00)
We get our result from the above inequality and by observing that Vf(y) - -plul22- y.
|>> 2 1
2 |1
|lvle plull
P
2
1
(z.
pllvl plul? 1101 |x|1 - EllllB
P
(z,1) = 11y1112 plul1 (τ.τ) plll12 (y. - (C()),,)) v) + (C(y), = (C())),))
-Ivl1E 2lu11 (z,
pllll plul (x. + 1 (z,z) + 21 (w.0)
= 11 + 2lul12 (z. v) - plull (y. 9) + 1
(C(y) - -)) - y)
2
11 (plll1 y v) + I v vl
1 (pllv11 p- y. 2 1)
| v vI
= > + (VI()), - 9) + 2
| y v
(2) When p = 2, we have C(y) ن yy Since || is square of an absolutely convex function, satisfies Equation 5 with curvature mapping C(y). For more details, refer to section and Young's Inequality to obtain:
Suppose that p 2. As done previously,
| (2-1)
|1
p |lyl ス
|
(38)
Moreover, by Cauchy-Sehward
| 2 (xx, wi1l = | (1x, u))
Multiplying both sides by - - -1 we get,
|| < |vll ((x,))-(())))))
Adding ||=1|] + (5 - 1) I| to both sides and by using Equation 38
||>||| 211 "1llll-A(xxx y)) + (2- -1)
1) ||
34

---

We can reorder the terms to obtain the result:
| 2
1
p) 2) llvll + P
1 ((x; y²)
11 plull? + 1lvl2 ((a; y))² llvel'
2
1 plull + L
IIvie x T yy Tx x + lluvl y yy Tw
2
1 - plull +
2 (C(y),, x) + (Cly)), y)
1 plull + 1l (2,9) pllvll (1, (C()),, (C(y)y. v)
+ + (x, v) plllll x yy T 1 (C()),,)) - (C(y)..v)
1
2
11 - plull? + pllull (r, (C()),, u) + 2
(C()),, x)
2 (C(u)).u)
1 plal12 + plvv12 (z.1) (C(y)(= y), y)
llvl plull (v. plubl -2 (v, + 2 || vllc(w)
y x llul + (pl (plvll 1.
u) + 2 vl
1
1uvl + (Vf(v), x v) + || y vieww
Then I satisfies Suppose p 2 2 and let f Rd + be defined as f(x) || Lemma E.14.
Equation with the following curvature mapping:
2 I|
C(y)
Diag(ly1l"
lyal 2)
Proof. Using Holder's inequality we can see that,
F
p-2
Eler
Σ
Σ
p--
=||0||
| || p(p-2)
We raise both sides to the power of 1 and proceed by rearranging some terms:
d
|
12 lyrl
p-2
11m11p=2
1=1
l1vllp - 11x/1p
+
|Ns 2-
Ilull
1=1
llvel
1
1ya1
+
1
| 1 1y:1"
p 11B/1
p--2
p
i=1
p
2=1
2
+
1y:10-2 p-2
19:
|B
11
11
p
1=1
p
Y=1
i=1
d
llvll
+
2
PP-2
00.
2
wel PP
+
1
1/%
p-2
p
|1
|1
p
1=1
1=1
1=1
y/s
2-
xz +
l1vi1
2-2
1vv P
1=1
1=1
35

---

We can arrive at our result by realizing that the last three terms are equal to || - vllo(w) and the middle two terms are equal to (Vʃ(v), x - v). Observe that af
2
Ms 1yvl" 1yr1=~2 Therefore,
dy:
Illll
d
2y My 1yil" 1
d
| 2
11
(xg - -b) +
1/ 1
1yll
11y1
2
1yi1" 0il000200 + l1v1 11- ==1
lvlly 1=1
1
-Ivlll, + (V.(v), x - 5) + (C(y)a, 2) - (C(y)a, v) + (C(y)v.))
1
|1vl + (V/(v), x 1/ (C()((x y), y)
1
|| (V.((), v\
1 y1(200)
2
Then f g² satisfies Equation Lemma E.15. Suppose p 2 1. Let g Rd - IR be g(x) |1
with the following curvature mapping:
C(v) = 2V 2Vgy)
Proof. By Lemma F2 g is absolutely convex for 2 1. Therefore, g2 satisfies Equation (5) with curvature mapping C.
E.4 Lower and upper bound examples
Lemma E.16. Let G be symmetric positive semi-definite matrix. Let f RRd R where
f(x) | Then satisfies Assumption with curvature mapping C(y) = 2G and constant
Lc = O.
Proof. We start by computing:
llyll 2|1y/12 + 1ly 2
- -1I=|0 + || + llvll 21ly + |lvll
||>r + |lyll 2 (G (Gy. (Ga,.)
| --
& + llvle 2 (Gy, v) + (Gy, + (Ga,
| l + llvl2 + (Gy, - (Gy, v) + (Gy, v) - (Gy, x) + (Gx,2)
- | I/ + |/>l + (2Gy, - x -) + (Gy, v) (Gy, x) + (Ga,æ) 1
| la + 1Ivl + (2Gy, v) 2 v 2
Rearranging the terms we get
|| = llvila + (2Gy, - x
y) + - 2| vlla
= 11vll (Vf(v), x v) 2 ||0 y 2 2oo
.Rd - R with g(z) -|=01p Let f = 9². Then f satisfies Assumption 2.7 with constant Lc 2(p and either of the two curvature mappings:
Lemma E.17. Letp 2 2. Suppose
2
B 1or1
Diag(lu1 p-2
1
B(y) = 2Vg(y)
36

---

Proof. In Lemma E.14, we proved that f satisfies inequality ( with the abovementioned curvature mappings. Now we will show that f smooth so it satisfies inequality (6). For p 2. it is clear that f' is 2msohhh. We focus on the case where > 2.
Since p > 2 we have that < < 2 where q = p-1 is strongly-convex with respect to the Lg norm with = q I. We also know that Lp norms are decreasing function of p. Therefore, h(x)) 2 ||=|| is also strongly-conver with respect to the L2
Kakade et al. [012 proved that /1z)) = 2 |
norm because |
u12 I || - -
1
| ス |wll (Vh(y), x v) 2 || y/1
2 |ull + (Vh(v). x y) + 20112 || 1112
The Frenchel conjugate of 2 11-11g is 2 |1-11p because the dual norm of 11-11, is 11-11p- Kakade et al. [0112] showed that is p-strongly-conve then the Frenchel conjugate of is -mooth. Therefore,
| L-smooth with L ا-و = p Thus, (xx ||==1 is smooth with constant 2(p 1).
Lemma E.18. Suppose a, b and a + 0 and b > 0. The function f:: R. - R defined as
f(x) Voxa +b
satisfies the upper and lower bounds in Assumption 2.1 with C(y)
2ay² f(y)
and Le V8a.
Proof. Observe that x² + 3² > 2z²y². Multiply both sides by ab we get ab(2² + 8²) 2 2abr
Then we add a² d²xty² + b² to both sides,
d² d² + abx² + aby² + 6² 2 a² d² + 2abr"y² + b².
We can write this equivalently as,
(ax² + b)(" + b) 2 (b + 12²²
Then taking the square root of both sides,
Vaxt (ay + bb 2 b + ax²y² = and + b - az + +ax2y²
Rearranging the terms,
Vaxt + byay +b2 ay + - an + ax² y²
= ay² A + b 2ny 4 + ax y + ay
= ay² + b + 2ary' 2ny 3 + ax² - -2axy² + ay
anf + +bb + 2ny (x y) ?n?22² - 2xy + y²)
= ay + b + 2ay (x y) + / 2ay (2 y)
Divide both sides by Vay + to obtain our result,
2ay²
1 2ay²
a b 2 v oo +b+
(x v) +
(x y)² 2 Vari + b
Vay* +
To compute Lc, note that f is L-smooth so we can find an upper bound on f" which is given by Lc = V8a.
Lemma E.19. Suppose 8 > 0. Suppose h : IR + R is such that:
11x2
| < 8
h(x) [((1]|
|>| > 8
37

---

Let f = h? Then f satisfies 2.1 with constant Lc = 28 and curvature mapping
2 8
1 - 8 y > 6
C(u)
Notice that Le is less than the L-smoothness constant of f. which is 382 (the tightest bound on the second derivative of f).
Proof. First, we will prove that satisfies inequality 5). We will split the proof into four cases and prove the inequality holds in each case.
Case |z] 10l S 8. We know x² 10² y2 . We divide both sides by 4 and rearrange the terms,
1
1 +
4 V0¹ y² + y
"²
4
2
2
2
11
"¹ + 24
2
2²yy
+ xy 3 - xy
1
1/ 5² + ry +
2x²² - 2ny + n²)
2
1
4 10- - (x 1) +
2
(xx y)²
We have our result because f'(y) y² for ly 5.
Case [x]| 2 8 and |y| S 6. For any |// S define r RR + as the following.
yº +
81
n²²y² 2
r(x)
+
x²1²
83h |x||
4
First, we need to show that r(x) 2 0. Suppose x 2
When x = 6,
y²
82
8
1
r(x)
(1² 22)20. 0.
4
4
4
Therefore, for x > 8, if we show that r' (x) 2 0 then r(x) 2 0. By simple computation, we get that
ayy²
r' (x) 26 83
2
Since x 2 8 then obviously x inequality by 8 we get that
N
30 so fx - N 0. Rearranging the terms and multiplying the entire
28 σ 83 .662
2 0.
It is easy to show that
x² 2 82 because |y| S 8. Therefore,
r' (x) 252x 83 ry 2 28 83
x262
20
2
Now suppose x < -8. Observe that r( r(-8) = (()) 2 0. Thus, if we show that for x S (5) S
then r(x) 2 0. For < -ō, we have that
xy²
r((x) = 28 x + 83
2
Notice that y² < 8 because lu| < 8. Then we have that 282 this inequality by x we obtain,
2
36"
Multiplyyng both sides of
2²
38
383
28
83
2
2
The inequality was reversed because < -6 < 0 and the second inequality also follows from x S -8. Rearranging the terms in this inequality we see that
xyy
r' (x)
28- 83
2
38

---

Therefore, we have shown that r(x: 2 0 for arbitrary absy S 6. we have that
Then by rearranging the terms in
x²x² 58 | + 84
y
z²y² 2
2
4
4
The left-hand side is equal to (( 100 = f(z). In the previous case, we showed that the
right-hand side is equal to tv² - (x - v) + 1 - y)²² Therefore, we have our result.
Case |x] 1v| 2 8. First, we show that the following inequality holds:
x² 2ry + x²² 20 |a||
y/ y
2 0.
(39)
For x, y 2 8 and x, y S -6 it is easy to show because (x - -1²² 2 0. Now suppose x 2 5 and y S -. Then we must show that
x² 2xy + 122 46x 2 0.
Since y S - we have that (ar y²² 2 (xr + 8)2. Therefore,
(x - y)² 45x 2 (x + 5)² 46x = (x - 5)3² 2 0.
Now suppose S - and y 2 6. Similar to before, need show
2ny x² 2ny + 3²² + 46x 2
Since 2 8 we obtain 4ry < 48x by multiplying both sides by 4r and reversing the incquality because x S -ō < O. Therefore.
(x= y)² + 45x 2 (a - y)² + 4ry = (x + y)² 2 0.
As result, we have shown inequality
39 holds. We can rewrite the inequality as
x22
ry +
y²
5 |z)
+ 5x y/
20. 0.
2
2
lyl
Moving some terms to the right-hand side we get,
82
y²
82
2
ry lv|
x² - 5 |x|
+
2
+
xy
+
4
2
4
2
|y
2
+ 2xy
8
.y
2n²
x²
xy
y²
2
Recall, that ('(2) 28 (1yl
50)
Observe that we can factor the left-hand side of the inequality we get our result:
lg 8²
and after multiplying both sides by
82
[x]|
2
1
2 8²
|v|
1
5
+ 28axy
82 xV
- 252 + 53 [vl
82 1²
82 -5axy +
2 y²
2
[y]
2
52
lvv
1
5
2
+ 28²
|vl|
2
11 (r y) + 2 (x
(x - y)²
2
|y]
2
The case where |a|| < 6, 1ol one can show that
2 8 is similar to the previous cases. Using some elementary calculus,
4
8
2 8
8212
8ay
+ 83 20
2 4
2
Rearranging the terms above directly leads to the result.
Now we show that f satisfies inequality (6) with Le 28" In the case where |yy 2 ö, Lc + C(y) 382 is the L-smoothness constant of so the inequality holds. We consider the case where |y| S 8. Case |a]] |y] < 8. Then zy < |zy| by (x 8) we obtain,
< 52 so x2 + ry S 282. Adding 3² to both sides and multiplying
(x - vv= + 282) 2 (xr 2x² + xy + v²) = =13² - n"² (x v).
39

---

By Lemma E.8 we have our result.
Case
|r|| 2 ly < 8. We must show that the following inequality holds:
y² x²y²² + 28 xy - 84 00 0.
4
We leave out the details of the calculations. The proof is similar to the same case for showing the lower bound. We can define polynomial in for arbitrary ly/ S. 6. Then we show that this polynomial less than 0 for 2 by computing the value at ó and show that the derivative is negative for 2 8 We proceed similarly for I -5. By rearranging and manipulating the terms in the above inequality we can arrive our result. These calculations are similar to the previous cases so we exclude them for brevity.
40

---

Absolutely Convex Functions
Discussing the theory constructions derived from Assumption 2.1 introduced 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 Φ IR + absolutely convex if and only if:
( 2 (6()) + (Vo(z), y - x)
Vz, y E R.
(40)
Our first statement is Lemma that establishes caleulus in the spirit of Lemma 5.1 in the main text. Lemma F.1. Let 6, 01,00 02 Then
Rd + R be absolutely convex, and let A E _d b E IRd and a Z 0.
(i) @ + is absolutely convex.
(ii) a& is absolutely convex.
(iii) di + 62 is absolutely convex.
(iv) (bAr + b) is absolutely convex.
Proof. We prove each statement:
+ i (x) = o(x) + a 2 + (Vol), ((y) (V y)
+) + + (V +a
(ii (xx) = aσ(x) a (
+ (o M\
+ + ma
+ +
- --)
(iii ob0p-:/::hhh10000010000000000110
231
(iv) ((x) b) 10
10(Ay
b)+
(Ve(z), 8) ( ( b), ((())
F1 Examples
Lemma F22. Letp2 1. Then Φ R R where (xx) ||=r|lp is absolutely convex.
Proof. We already know that & convex so we show that
b(v) (Voly), v) S 6(x).
where
8d(v) Oy:
yll. for y E Rd.
Observe that
yi Valval 1-2
(0(v), x y) =
|0|| p P- - (x: Vi).
We make use Holder's inequality which is stated below for r, s 2 0.
Σ Jxs trte
For any v. y E IRd and with r= = I and 8 =
we have that,
p-1
Σ loolleal
|
Σ 1a6a
41

---

Simplifying this expression we obtain,
p-1
d
d
d
a llvi po- -
Σ
120/
Σ
1
p-1
((2))
dt
= ||00|p
Σ
leal
||2/|| 11yllp
We can obtain a lower bound on the term,
2% llye 1p-1
Σ
ba 1
(aaa%e 10
d
Tyyh 19:12
Therefore,
| 1y 1
23yll9n 1 P-2
Now add 11y11p- Dam 1 to both sides of the inequality get
d
|| |==||||1 + llyl
Vil p
aylhi 1/ p-2 Σ
vi 1u 1 Σ 3.yil Iva p-2
i=1
d
(v Mi p-2 x.yllui 10- 2) = Σ
U1 Bi 10 2(y - xz)
d
Ye lel 12: - ve).
Now divide both sides of this inequality by 11u11
ya llss 11mslp-2 12-2
| + |1v|lp 2
(1:; - y1).
||
1=1
By rearranging the terms we get our desired inequality
Vilvi p-2
-Illlp
-ul (x+ - 91) S |101|pp-
llvl
Lemma F.3. There exists an absolutely convex function : R - IR such that the derivative of f = 6² is not Lipschitz continuous. Namely,
|
x(x)
+1
05
(-z) 3 +1
-1<><0
42

---

Proof. Firstly, by simple computation we can show that Ø" 2 0 so á is convex. Observe that If'l S 3 and 24 Also notice that @ bounded below by 2 Therefore, by Lemma F.16
absolutely convex.
From brief computation,
obtain,
2 (3 (3 |
x P121 0
(z)
3(2 +1z
3((-z) 1)(=))
<I<><0
Now suppose by contradiction that / Lipschitz continuous. Then there exists /. > such that for all x; y E Rd
fx(x) f'(1))
S L.
x y)
Specifically, this holds for and y have
(f) ('(')
1f(()))
3x 3x
yl
[x]
[
3x.2 + 3x
3x +
L.
V
We can find an small enough such that consequence, f' is not Lipschitz continuous.
3 v=
L. Therefore, the incquality cannot hold. As
Lemma F4. Let 8 0. Then f. l. defined below are absolutely convex.
I 6(x)
x
f(x) (1)==011 1+
82
5((xr 2
T
2
Note that f is the pseudo-Hubee Huber loss function and 6 is the Huber loss function.
Proof. Both the Huber loss and pseudo- loss functions well-known examples of convex loss functions. The minimizer of f and é is x, = O.
From simple computation obtain that [x(()) < 1 for all x E IR,
f(x)
x
4
= 1.
Also, we know that for all R.
22
x2
f(x) = 8/
81
x
|z].
Therefore, by Lemma F.16 is absolutely convex.
By computing the derivative of Φb, we can show that | (x)) for all x R. Now we show that ((x) 2 8 jr].
When x > we can simply observe that ((x) |xr. Now consider the case where x S 8. We have that,
(|0) 8)2 0.
Expanding the square we get,
2 28 | + 82 2 0.
Rearranging the terms and dividing by we see that,
52
(xx)
2
8 l=]
2
Hence, by Lemma F.16 & is absolutely convex.
43

---

0 leads to Lemma F.5. Let a > 0 and b 2 0. Then Ø : R + R where ((x) vaz² + is absolutely convex.
Proof. Notice that z, 0. Also by simple computation we know can show that f is convex,
ab
(x)
20 0.
(ax² + b)
We can compute an upper bound on the derivative of f.
(')x)
a.r
az
Va.
V Vax² +
V Var²
Then.
x(z) ax 2 + 2 Var vav vālzi
Since (xx) 2 Va |z). by Lemma F.16 f is absolutely convex.
Lemma F6.. The function á IR + R, defined as follows
o(x) 1+1+
2 0
I- I x<0
absolutely convex.
Proof. Observe that x. 0. By simple computation, we can show that d²(x) 2 0 for all IR,
x 2 0
("(x)
(a++)) [1-2}
<<0-
Similarly the previous examples, we compute an upper bound on R
(x+1)> x
(xxx)
0
is clear that [d(( < for all x E R. It is easy to shoiw d(x) 2 |x)) For x 2 0, we have
Φ(x) x
2 2+1 2
For x < 0, we have
(xx) =
2 x.
Therefore, by Lemma F.16 o is absolutely convex.
F.2 Functions with zero minimum
Absolutely convex functions have some interesting properties when their minimum is 0. Lemma E7. If db is absolutely convex, then the following statements are equivalent:
1. ((0) 0.
2. d(x) (Vo(z),z).
3. à is homogeneous of degree 1.
Proof. We establish three implications:
ii) i Pick any If ((0) = 0, then using Equation 440 with
(Ó(u) (oly)) w) which implies <(v) (Vo(y), v).
(ii) = (iit) We start by substituting d(y) (Vó(y), 8) and d(x) =(Vo(z), into <(x) 2 )()) + (Vo(g), x y) to get,
((z) (Vo(z),)) (Vo(v).)) + (Voly). y) (Vo(v).z)
44

---

This means that,
x(x) = max (g. x).
seQ
where Q = (V)(y) E RR As consequence, for any 2 and a E R² we get
x(tx) = max (g. tx) = t max (g. x) = tœ((x).
SEQ
gEQ
(iti) + (i) Choose any x E R2 and Then 6(0) x(tx) = tő(z) 0Ø(2) =
Lemma F.8. Let o Rd 7 R be absolutely convex. Suppose there exists an 2, E IR such that (xx)) Then
<(x) - (Vo(z), 2.).
Proof. From absolute convexity, we have that
0 S 10(x) +
x(xx) 0.
So
<(x) + (Vo(I), x) O.
Simply rearranging we get our result,
Φ(x) = (V - x) = (Vo(z), x- x.)
Lemma F.9. Let : R + be absolutely corvex. Suppose there exists an Ie TK such that
((x,) 0. Also, suppose that o is differentiable everywhere but Then it must be that
-m(p x..) (m(x - x.-) x > I
x < x.
((x) = m |r x.I
(41)
for some E Rzo-
Proof. We have that f(x = o(x + )r_) is absolutely convex. It is also homogeneous of degree one since f(0) O. Define U1 {a
x > 0} and U22 {ar E IR x < 0}.
By homogeneity, for any t > and æ E U1 we have that ftz) = tx)).. Differentiating both sides with respect we get f'(tx:) f' (x)). This means that for any U1 have that J'(x:) mi for some m, E TR. Since U1 is a connected open set, we have that f(x) = m4æ for x E U1.
By similar reasoning, for x E U2. f'(x) m2 for some m2 E R. Also then, f(x) = m2x for I U2.
Now consider x E Uj and U2. By absolute convexity we know that
m = f(x) 2 ffv) + (z) - y)1 = |m2y + +22(1 - y)l = |maal 2 mm2 |z]]
Then ma 2 |m2 [x] |mza which comes from the fact that Un so x 0 and thus 1. Similarly,
m2y = f(v) + x)1 = |mr + mi (v x)1 |m1y] 2 [/
Then [m]] 5 m2 2
Tpl m because y U2 so y and thus _ -11
1>]
Since 0 < |m 5 -m2 we get m2 S 0. Also because |ma] S my it must be that ma = - where
my > 0.
45

---

For brevity, we set = mi and so we have that
3 < 0
f(z)
x >>> 0 mE
By definition we have that ((x) = f(x - -x,). Therefore, we obtain our desired result
<(x) = [-m(x u - xz)) m(( x.)
x x- I+ < 0 I. > 0
Lemma F.10. Suppose that Φ: Rd > is absolutely convex and Φ(0) = 00 Then @ sub-additive, ( + y) - ((2) + o(y).
Proof. By Lemma E7
we know Φ is positively homogeneous of degree one. Also because ø is convex we have that for any 0 S a S 1,
ò(ar (1 11--a) a)yy S aΦ(x)) + - a))(y).
Selecting a 2
1 x² 20) 1 2 x(x) + 1
2 20(1).
(42)
By homogeneity of øb
/ [ + v) S Φ
5 2
By combining the previous inequality with inequality
42 and multiplying by 2 we get our result.
Lemma F11. Suppose that Φ Rd > is absolutely convex and @(0) = 0. Then the epigraph of ò convex cone.
Proof. Now we show that epi øi is a convex cone. Suppose (x, (1) E epi ø and (2,)2) E epi Φb Suppose a O and 0. Then
dax + By) I d(ox) + ((By) = aΦ(r)) + 3Φ(y) S aun + 812.
The first inequality is from sub-additivity and the first equality is from homogeneity, Therefore, (ax + By, ap1 + Bpz) E epi é so epi é is a convex cone.
Lemma F.12. Suppose that o : Rdd + R is absolutely convex and ((0) = 0. Then & is even, i.e.
(xx) = 6(-x),
Yx Rd
(43)
Proof. By absolute convexity we have that for any x, E Rd
(Vo(z), = δ(z) 2 p(v) + (V I - y
Φ(y) (Vo(y), x) + (Vp(y), -
((v) + (Vo(v), x) - (V v)
((v) + (Vo(y).)) +(y))
xV)(
(44)
Similarly,
<(y) = (Vo()), v\ 2 Vo)()).))1
(45)
Now subtitute y = x into
x(x) 2 (Vo(=2), = (V O x) = [0(-x) = 6(-x),
where the last equality because absolutely convex functions are non-negative. Substituting y into 45
((-x)= 2 (VΦ(.), -a)l =V) ((x).
Therefore, 6(x) = =(=2).
46

---

F.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 F..mmaFF.13ani and useful result for validating examples in Lemma...o
Lemma F.13. Let f I E defined as follows, f() + b(x ro)) for some b, xn E R with b + 0. Then for any C > 0. There exists IT, 22 E R with 22 2 21, f(xi) = f(22) = G.
[222 21 [6]
2c and (x22
and ('(x1)
Proof. By simply solving the equation f(x) = c, we get that
c - a
x2
+ I05
b
21
TO-
b
Thus,
a
2c
[22
31 b
+ 30
b
b
Suppose without loss of generality that b > O. Then ('(22) ob > 0 and f'(x1) cb < 0.
Lemma E14. Suppose : RR + R is a convex function that not constant with minimizer V..- Suppose lower bounded by f(x) |a + b(x Tn)l for a, b, zo E R and # O. For any > Φ(x.)
there exists an x! such that 6(x') = c. and |x' x. v 20
M
Proof. By Lemma F.13 there exists T2, such that [12 - x1 foj and f(z))= = f(z2) = c.
We also know that x2 > xi and that ('(12) 2 0 and ('(x1) S 0. will show that 21 < I. < 022
Suppose by contradiction that 2 Since ʃ is a linear function with slope ('(22) on the interval [22, xc) we get
f(x.) f(22) + ((2)) x2) 2 f(22) = σ(x,),
which is contradiction because is supposed to be lower bound on Φ The first inequality follows from the fact that (x, - x2) 2 0. A similar argument follows if the assumption v, S 21 is made.
Soc = [(x)) S (xx1) and (xx,) c. By the Intermediate Value Theorem, there exists x' E (x4)))))) such that (b(²) c
Thus 1 < x' <x, x2. Therefore, jx' - x.. 1 22 -1|= 2c with o(x') C.
Lemma F.1. Suppose o : + R is absolutely convex and has a minimizer x., Then there exists an M E R such that lØ' (a:) M for all IR i.e. | is bounded.
Proof. If 6 is constant then its derivative is bounded so we consider the case where & is not constant.
We will do a proof by contradiction. Let c R such that c > Φ(x.). Let cx.) (ō(x.) c c|
Note that
2
By continuity of 6 at x, there must be a such that if | x.l S 8 then (Ø(x) ((x+)) S c. Suppose that [o'| is unbounded. Therefore, there exists a sequence of numbers yn. E such that lim 1 (ym))
For any let (x) (6(u)) + d' (v. (x v.)) Since ø is absolutely convex, fn. must be a lower bound on Φb By Lemma F.14 there exists an H. such that d(xx,) = c and Ixr,. x.a 5 [y. any Vn.
2c for
Since IØ' is unbounded we can choose a N such that [aN) S 6. Thus JNN x. S 6. Therefore, (Ø(x.) - Φ(xN)) ) = lx(x.) cl S e.
But this contradicts the fact that (0(x.) cl >
47

---

Lemma F.16. Suppose o R + R is convex and has a minimizer at x., = O. Suppose o' is bounded. If o can be lower bounded by h(x) m |z| where ( (y)) m for all y E then & is absolutely convex.
Proof. Suppose without loss of generality < x. = 0. Since ø is convex we have that d'(y) S 000 by monotoncity of ( Since m is bound on d' we get
m (v)
(46)
Since is a lower bound on ø we also know that.
( 2 -yy 2 0.
(47)
Now let ((x) = (0(y) + (0( y)1- Denote x² as the point where f(x") = 0. On the interval (-o0, x²), is equal to the line tangent to e at point y. So by convexity, is lower bound on on the interval (-oc, x"I. It remains to show that f lower bounds & on the interval oo).
o(v) First, we show that x" = क66ा + x+ 0.
0. We can take the reciprocal of inequality
(46) to
obtain,
('))- Multiply this inequality by (47 get, yy S
('(v)" We can do this because
<(y)
the terms on both sides of the inequalities are positive. Rearranging we can see that x² 2 0.
Suppose x E [x". oo). On this interval, f a line with slope -o' (y) passing through the point (x", 0). Thus
f(x) -6' (z) z²). Since x" 0 we know that x" < Multiply this inequality by m 2 -0(()) 2 0 to get that - o' (x) - x²) S ma. Since h(z) = mac lower bound o we have that -06 0l (3) x²) s Φ(x). Therefore, is lower bound ø for arbitrary y < 0 so we are done.
rewrite
A similar argument can be made for 2 0, the signs will be flipped at each step.
A direction of potential interest for future developments is how to bobsolutely-convxiifi given function. Below, we prove the propotypical case of functions from IR to E. In words, any convex function lifted high enough is absolutely convex.
Lemma F.17. Suppose f R + R is a convex function. Then ((x) = f(x) + B is non-negative for ba with max (I ([(b) and 3 alb-a)
f(a)+
2
Proof. is sufficient to show that (xx) 2 0 for E [a,
o(z) f(z) + a<b a) {(a) + f(b)
2
f(x) f(a) aax - a)
+ f(x) - f(b) a(x
2
Dy(x, a) (x(,,
2 2
2 0.
Lemma F.18. Suppose f :R
IR - is a convex function. Then for any interval (a, b) there exists B, such that (xx) fz) + absolutely convex on (a, b).
Proof. As is convex by convexity of f. is sufficient to show that for every x, [a, bj:
((x) < <(y) + d' (x) y)-
From Lemma E.17 we have p(x) 2 0, so is sufficient to consider the case when d'(y)(x y) s
Having a, 3 from Lemma F.17
Case 1: o' (v) < 0 and 2 y-
48

---

From the convexity of ő it follows that:
<(y) + (1) - y) - (o(a) + d'(a((z - a)) = Do( + (o'(y) -'(a))( - y)
0.
Hence, (a) S a by construction, implying:
Φ(a) a( - S x1)) +
remains to show that:
((x) + x(a) a(x - a) = f(x) + f(a) + + a(x - a)
f(z) +(b)+ 0) a(r (r= a)
f(x) f(b) -a(r b)
2 Dr(x,b)
2 O.
Case 2: d'y)) 2 0 and S y. In analogy with the previous case:
((b) + - b) 61)) + y).
Therefore, is sufficient to show that:
((x) + o(b) + a(x b) f(x) + f(b) (()) 23 b)
f(x)
a) a(r b) f(x) - [(z))((a)+af) +a(r-
Dy(x,a) 0.
It is useful to remind the fllowing standard result for sub-gradients. The proof is in the referenced book.
Lemma F.19 (Lebourg Mean Value Theorem [Clarke 1990]). Suppose R R is Lipschitz on any open set containing the line segment [x, y). Then there exists an a E (),y) such that
x(z)
d(y) E (Dó(a), y)
Lemma F22. Suppose ó: R + R is absolutely convex. Let M E IR be the bound on the subgradient of é. ie. oo' (x) S M. Fix a y E R. Then for any x 2 y we have that
((y) + M(x v) Φ(x).
Similarly, for any S y,
6(y) - M(x - y) 2 x(z).
Proof. We prove the first claim. Suppose 2 3/
Since is convex, it locally Lipschitz i.e. Lipschitz on x). By Lebourg's ' MVT we know there
exists E (y, .r) such that d(x) o(y) = g(x y) where g dø(c). Note that s M. So,
g(x y) S M(x y) because y 2 Therefore,
((x) Q(y) M(x 1)- v)-
Rearranging this expression we obtain ((x) < (vv) + M( - y)-
The proof of the second claim follows the same format and uses the fact that 9 2 -M instead.
49

---

Lemma F.21. Suppose o : R - IR is absolutely convex. Let M E IR be such that 1@') S M. Then the following limits exist and are equal
lim (d(x)) 20000
x- 10((x)
lim
Proof. First, we show that lim ( (z)
exists.
Let } be an arbitrary sequence such that Zn - co. Since & is convex the sequence {1o (rn)) is monotonically increasing. Also, it is bounded above. Therefore, by the Monotone Convergence Theorem there exists an L1 IR
lim [x(x))] = L1 and L1 2 10'1. 7-00
Since zn is arbitrary it must be that limg-xo (0'(z) L1 A similar argument can demonstrate that there exists an Lg E R with L2] 2 lo'| and limg---o (x)x) L2)-
Now we show that 7, = |/2.. We will do this by contradiction. Suppose without loss of generality that In_ > Lul and that L <
There exists an > 0 such that L1 > LL2. Now there also exists an N such that for any >> N we have that ( (y) Lı| < e. So L1 - (3()).).
By absolutely convexity of Φ. function f(x) = (o(y) + ('v - y) a lower bound on ø. Let x. be the value where fxx)) 0.
Define ((z) -o'((y) xy). which is the line passing through the point (azg 0) with slope -O().. Observe that for x E (-xx, N... ((x) = f(x) so l is lower bound on ø in that interval. Define (x)) -In - cx x.) to be the line passing through (Ir,, 0) with slope - (In -c). For Fe.
(x)) < ((x) because L1 < d'()). Therefore, hı (ar) < Φ(x) for x E (-0
Define (x) = (xx)) + L2(x x.). Since L2 0, by Lemma F.20 the function h2 is upper
bound on @ for any x < Ze.
By caleulation determine an F; such that h1 (z;) h2 (2;) where
T; (L2 L1
((Tx)
L2 + 11
Now we show that I; S Tg- Note that d is absolutely convex so -6(20) S 0. By adding (I2 + Ta c)x, both sides of this inequality obtain
LL + L1 - ((zo)= S (L + 11 -E)
Dividing by T22 + Tn we get
L2 + L1 c) - 6(zv)
=
S Tag
L2 + L1
Let x < x.. So hz) hz - (L1 c) - xz) and 12(z)) = (xx) + L2(x - x;). Observe L2 Multiplying both sides of this inequality by x - x, which less than 0 and then adding h(x;)) to both sides again we see that (x) > hz(a)).
that - (L1 E) < La because L2 < 0 and L1
Therefore, for any < 24 < Ze. we have that (x) > hz(x). This is a contradiction because on the interval -0,0 hy is a lower bound so d(x) Z h1(x) and he is an upper bound so l2(xx) 2 ((x).
Lemma F.22. Suppose 6: IR + is absolutely convex. Suppose it has a minimum point T.. Suppose there exists a f1, E IR such that y1 x. < y/ and for every y Vr, o'(y) mm and for every y' 2 V2. ('(y') = m2. Then mi = m2.
Proof. Note that since ò is convex it has monotonicly increasing derivative. Therefore, mi 0 since y < x. and m2 > O since y' > T.. Let f(x) = (Φ()) ) + mı(r (x y1)l be the tangent cone to y1. Then define line 1x(x)) |mal (x + d(v1) vI) which is line that has the same slope as ʃ and intersects the vertex of f. Note that h is lower bound on by absolute convexity.
my
50

---

Lemma F.2. Suppose Φ R + R be absolutely convex and assume o' = inf ER Φ(x) < cc. Then there exists an 2x E R such that Φ(x,) S ((x) for any R.
Proof. Suppose E IR is arbitrary. Choose y I and by absolute convexity we have that 1 (y) (z)(z y)1 S Φ(x). We can rearrange the terms on the left side and take the limit to see that
lim (d(y) - d' (w)y ('())r) xc.
|a|-000
since only the last term which is linear depends on æ. Therefore, we have that 1/11/2/ ((x) = oo.
This demonstrates that ø is coercive. Now let Zi be sequence such that ((In) - f Suppose that lim,-soe [mn| = oc. Then by coercivity, we get that a., ((xn) = infty which is a contradiction with the fact that 6* S 00. Thus must be that limn-soe [xn| = r for some E R. Let B, fxr R
|x| r) which is compact because it is closed and bounded. Since In E B, and every sequence in a compact set has a convergent subsequence, so there exists an E B, s.t. Ine + Z.. By continuity of (because it is convex function) we obtain f = -om ((Fm)) = f(x.).
E4 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 rewriting of Lemma 7.1 in the main text.
Lemma E224. Suppose & : Rd + R is absolutely convex and has a minimizer T.. Then there exists M E R such that [|Vo(>)) ll2 M for all x E Rd
Proof. If à is the constant function then its gradient is bounded so we consider the case where Φ is constant.
2 We will do a proof by contradiction. Let c ((x.). Let e = )= Note that (ø(x,.) - cl > e.
Suppose 5 > 0. Observe that since ø is convex on IRd is continuous on I&d and in particular is
continuous x., Therefore, there exists 5 > 0 such that if [r. x S 6 then (Ø(x.) 6(x) e.
Suppose that Vol is unbounded. So, there exists a sequence of points yn E Rd such that [o(()]l, = co.
lim n-
Let (z) (o(,,) + ( (Vógg,), vn)) Since is absolutely convex, fn must be lower bound on 6. We can proceed similarly to the proof of bounded gradients in IR (Lemma F.155 by considering the restriction of and á to specific lines. This allows to find sequence of points 2, that lie on those lines and In + T..
Define La to be the line that passes through x. in the direction of Vo(yn). Let $lc, : be the restriction of Φ to the line L,, and similarly, fa r.,, R. + R be the restriction of fa to I,, Note that the function fn|r,, l.., is of the form la + b(x zo)] where //V(())) for some zn E IR. Let Tt E R be the minimizer of ølL, Then by Lemma, there exists a point, In E Iy such that IL,, (T.)
2. and 1= Fnl < [ Observe that .¹ corresponds T.. Also, In can be mapped to point on E Rd which lies the line In and ((x,) and |a., -xxl [o This holds for each yn-
Since Vo( )l2 is unbounded we can find an N such that jr. INl < 8. Therefore, (ó(x.) ((x,)) (d(x.) - cl S c. However, this contradicts the fact that (o(x.) - >
Lemma F.25. The maximun of a constant and absolutely convex function is absolutely convex.
Proof. Let a E R and f be absolutely convex and g == max{ff at. We split the argument in some sub-steps.
(Trivial case) Since absolutely convex functions are always positive, it follows that if a S 0 then g(z) max(f(x), a} = f(x) and is absolutely convex.
51

---

(Second case) Let a > O. 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. reamains to show that:
wts ( 2 ((x) (Vg(y), y) Vz,y = ( g(x) (Vly),
0 Vz, y.
(48)
For convenience, we will show the last version is positive for different choices of x; y. Recall that always positive so for arbitrary (z, y)there are four regions identified by the strips [0, a); (a, 20) iover which the values fx),, can fall.
Additionally, recognize that for & E R² we have Vg(z) = V max (ax = (())2 Vf(z). Let us treat all the cases in separate ways If [(x) S a and (w)
have the expression 2a 2 0 by construction.
f()) > a and f(y < a we have the expression:
f(x) + 0;
(49)
again, by construction.
If f(x) a and f(y) > a we have a (V)))(Vf(y))=== - since we assumed f is absolutely convex.
If fx) 2 and f()
has:
f(x) + f())+ (V)))(V(())))))) 0,
(50)
which follows by the assumed strong convexity f.
remark Let x+ = arg min S. for an absolutely convex function f. Observe that one can always use, for any y # T., + x.:
f(z) 2 If(y) + (Vf(y), -)
(51)
Lemma F.26. Suppose Rd A function o Fd + IR is absolutely convex if and only if the function f + l. defined as f(t) o(x tv) absolutely convex for all Rd.
Proof.
(=) Suppose f(t) is an absolutely convex function for any 2, E Rd We already know that will be convex only need to show that for all y, RR.
(<x)) I <(v) (Vo(y), y)--
Note that (t) = (Vø( + to), v). Select x = y and -- y. Since f is absolutely convex, the following inequality will hold,
(11 - f(0) + (0) 0) (() + f' = Φ(y) + (Vo(y), - y).
We have our result because f(1) = Φy + v) = ((=)
(+=) Suppose & is absolutely convex. Let xr R be arbitrary. We know already that f is convex. So we just need to show that for any 8, / E IR we have that
((()) < (s) + (t( - 8).
By absolute convexity of ó we know that,
-o(x tv) Φ(x st) + (Vo( + su), to (x sv))
=( + sv) + (Vo( + su), to -s))
Φ(x st) (Vo( + st), u) (8-8)
((s) (1))+((s)(() (3)((( s).
Since f(t) 6(x + tv) we have our result.
'In principle, at a there is singularity, avoid doing this computation since the non- con-ifferentiable detinition of absolute convexity is satisfied for the max function.
52

---

G Extra Experiments
G.1 Regression with squared Huber loss
In this experiment we optimize the function
f(x) = Σ (a 6:),
where a, Rd, b, E R are the data samples associated with regression problem, and is the Huber loss function. We run the experiments with C(x) for absolutely convex functions 7.1
Polyak
LCD1
LCD2
LCD3
Figure 5: Regression on housing dataset.
(a)
10
(h)
10
(c)
10
Polyak
LCD1
LCD2
LCD3
Figure 6: Regression on mpg dataset.
15
(a) 6
10
(b) 8 10
(c) 5 10
Figures 5 show that the algorithms using the C(x) matrix perform much better than the Polyak method. We observe very fast convergence of both LCD3 and LCD2, regardless of ó. Contrary, 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.
G.2 Ridge regression
We consider the following objective function:
f(x) = > (a, -.)2 + A|
where ay E R2d, by E RR are the data samples associated with a regression problem. By we understand the smoothness constant of linear regression instance, excluding the regularizer.
In Figures 7 7 C(x)) is associated with the regularizer, and it becomes a multiple 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 Lg regularizer that is the Polyak's method.
consistent improvement of LCD2
Figures D 10 show results with C(x) = 2 A A, which a lower bound on the main part the objective. In this circumstance, LCD1 becomes the Newton's method, and converges in one step. As anticipated the main text, LCD3 can diverge. Finally, LCD2 performs in a very consistent way, and converges in exactly 15 steps across all the setups.
53

---

Polyak
LCD1
LCD2
LCD3
Figure 7: Ridge regression on housing dataset; C(x) = 2X.
301
(a) A 7-100-
(b)
100
(c) T. 10
Polyak
LCD1
LCD2
LCD3
Figure 8: Ridge regression on mpg dataset; C(x) 2X.
107
107
16-
10
12"
12"
10m
100
150
10
135
(a) A = 10
(b) X
10
(c) A L 10
Polyak
LCD1
LCD2
LCD3
Figure 9: Ridge regression housing dataset; C(x) 2 A A.
n
m
10--
Borations
10
RoraBons
20
30
30
33
10 3
10
-
(c) L 10
3
Polyak
LCD1
LCD2
LCD3
Figure 10: Ridge regression on mpg dataset; C(x) A ATA.
121
301
(a) L
(b)
10
(c) L 10 2
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should
54

---

follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (I sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" it is perfectly acceptable to answer "[No] provided proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset used"). In general, answering "[No] or "[NA]" is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often
nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims made the abstract about our methods have proofs and our empirical results are encouraging.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We point out assumptions and limitations in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
55

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex: system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof'
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are stated in the introduction and proofs are provided in appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The paper provides a thorough description of the experimental setup including the type of model that used and all of the hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
56

---

If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., . a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Although we don't provide code, common and standard experimental setups in ML such as logistic regression. Additionally, we provide a thorough description of methods and the experimental setup the results can be faithfully reproduced.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so &o is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g.. for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ //apss.cc/pulic/guidde http://iiiggiide//oeeeeeeee
ssionoolicyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
57

---

6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All experimental details are in the experiments section and additional technical details are in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our paper focuses convex optimization algorithms, which typically do not employ statistical significant tests. We demonstrate the empirical performance of our methods across various ML setups against baselines.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Compute resources used are provided in the experiments section.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
58

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp://neete httppp::////uuppp.pppee wttppbllic.ttiicccc..eeleeellell
Answer: [Yes]
Justification: The research is in convex optimization theory and adheres to the NeurIPS code of conduct.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
59

---

Justification:
Not applicable to our research.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswithcode com/ datasets has curated licenses for some datascts. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
60

---

Answer:
[NA]
Justification:
Our work does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to LLM policy (nttps://neura) http://pp..p./ooeeeeeen///////// for what should or should not be described.
61


Reviews:
[{"review_id": "URLkozohzj", "reviewer": "Reviewer_NYA3", "summary": "This article introduces a new class of functions that simultaneously generalize/restrict convexity and L-smoothness and derive better optimization (minimization) algorithms for these functions. The key idea is to introduce the existence of a local quadratic curvature term and a fixed constant L that allows one to both upper bound and lower bound a function f.  The lower bound is a linear approximation to f at x plus the local curvature term, while the upper bound is the same linear approximation plus a higher curvature term equal to the original plus L times an identity matrix.   When the curvature map is 0, then the lower bound generalizes/restricts convexity, while the upper bound generalizes L smoothness. \n\nThe article then continues to exploit the properties of this class of functions to yield new optimization algorithms that can exploit the existence of the local curvature map.  They derive 3 algorithms:\n\nLocal curvature descent 1 (LCD1):  minimize the upper bound.  This generalizes gradient descent with constant step size 1/L.\n\nLocal curvature descent 2 (LCD2):  Euclidean projection onto an ellipsoid in which the lower bound is less than the (known) minimal value of f.  This generalizes gradient descent with Polyakov step-size which also requires knowledge of the known minimum value.  \n\nLocal curvature descent  3 (LCD3): this is LCD2 with Euclidean projection replaced by a projection determined by the local curvature term, which has a closed form solution.\n\nThe paper nicely derives convergence rates and proves them for LCD1 and LCD2. \n\nThey then show that their new class of functions is not trivially empty or uninteresting by constructing general classes of functions for which a local curvature term satisfying the two requisite inequalities exists.  These include for example, Huber loss, L_p regularized logistic regression, squared p-norm, and sums of squares of absolutely convex functions.  \n\nFinally they perform numerical experiments on L2 regularized logistic regression and show that some of their LCD algorithms exhibit faster convergence than GD with Polyak step size.", "questions": "You have shown a few examples of classes of functions that satisfy your assumption 2.  I would love to understand better how to understand how general this class is.  Are there even more qualitatively different optimization problems that people care about in practice that satisfy your assumptions? I suspect this is a difficult question though.  But anything that can be said here would improve the significance and impact of the paper.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1) The new class of functions introduced seems quite nice.  \n2) The convergence proofs for two of their algorithms are solid results. \n3) Showing the class of functions is not trivially empty/uninteresting is nice. \n4) The paper is reasonably clearly written. \n5) The numerical experiments are relatively extensive at least on the limited classes of functions that satisfy their assumption. \n\nWeaknesses:\n\n1) The field of optimization theory really needs to focus on more natural classes of functions that appear in practice.  It is less clear how natural the class of functions introduced is.  For example, most functions we are interested in are not convex. \n2) The method does not extend to stochastic methods, but that can safely be considered out of scope as an entirely new paper would have to be written to cover that.\n3) Their algorithms that perform well, namely LCD2 and LCD3 require knowledge of the known minimum value.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for spending the time and effort engaging with our work. We appreciate that the reviewer found our convergence proofs of LCD1 and LCD2 to be solid results and our numerical experiments to be relatively extensive on functions that satisfy our assumption.\n\n## Justifying Local Curvature\n\n> The field of optimization theory really needs to focus on more natural classes of functions that appear in practice. It is less clear how natural the class of functions introduced is. For example, most functions we are interested in are not convex.\n\nWe acknowledge the reviewer's concern that the relevance of convex optimization theory for modern machine learning is not initially apparent. However, we would like to politely push back on this assertion, as developing theory in the convex setting is important for understanding methods and can lead to insights in more complex regimes, such as the non-convex case. Various adaptive methods that are the workhorse for modern machine learning, such as Adagrad (and its variants such as Adam) were developed with theory in the convex setting. Other powerful adaptive step sizes such as the MM step-size [6] and the Polyak step size were developed with theory for the convex setting. \n\nFurthermore, we believe that Assumption 2.1 offers a natural way to incorporate a notion of curvature into the classical framework of convexity and smoothness without going down the route of fully-fledged second order methods. We demonstrate its applicability through several relevant examples in convex optimization, including $p$-norms, convex loss functions, and squares of absolutely convex functions, where this notion of local curvature can be effectively exploited to design adaptive algorithms with superior performance. Interestingly, some curvature matrices arising in these examples often exhibit special structure,such as being diagonal—which is particularly relevant in machine learning settings. For instance, recent work [5] has shown that the Hessians of deep neural networks often have a block-diagonal structure. A better understanding of these diagonal patterns can facilitate the design of more efficient and scalable adaptive optimization methods.\n\n\n## Extensions to Stochastic Setting\n\nWe agree that extensions to the stochastic setting are a very interesting and natural research direction that can be explored in future work. Specifically, one could explore the case of finite-sum minimization where we only have access to a stochastic version of the local curvature matrix. \n\n## Knowledge of $f^\\star$\n\nWe acknowledge the reviewer’s comment that requiring knowledge of the minimum value poses a potential limitation. We would like to clarify that in many modern machine learning settings, this requirement may not be as restrictive as it initially appears.There has been a growing body of work on stochastic Polyak step sizes for finite sum minimization $\\min_x \\sum_{i=1}^n f_i(x)$ where the requirement is relaxed to knowing each individual $f_i^\\star$. This relaxation is particularly relevant for overparameterized models, which are now widespread. In such models, the training data can often be fit exactly, implying that $f_i^\\star = 0$. As a result, future extensions of our work, particularly in the stochastic setting, can benefit from utilizing these techniques. Another well-known example where we know that value of the global $f^\\star$ is binary classification with linearly separable data ($f^\\star = 0$). \n\nAdditionally, when the value of $f^\\star$ is not known we can estimate it as $f_{\\text{best}} - \\gamma^k$ where the sequence $\\gamma^k > 0$, $\\gamma^k \\to 0$, $\\sum_k \\gamma^k = \\infty$ and $f_{\\text{best}}$ refers to the smallest objective value in the trajectory so far [1]. Furthermore, several works have proposed strategies to employ the Polyak step size in the stochastic setting for finite sum minimization without knowledge of $f_i^\\star$. A common approach is introducing slack constraints, i.e. finding the smallest possible $s \\in \\mathbb{R}$ such that $f_i(x) \\leq s$ [2] [3] [4] . Stochastic Polyak methods require knowledge of each $f_i^\\star$, which is a weaker condition than knowing the global $f^\\star$. \n\n## Questions\n\n> I would love to understand better how to understand how general this class is. Are there even more qualitatively different optimization problems that people care about in practice that satisfy your assumptions? I suspect this is a difficult question though. But anything that can be said here would improve the significance and impact of the paper.\n\nWe believe that exploring the sum of squares of absolutely convex functions, $\\phi_i$, has a lot of potential,\n$$\nf(x) = \\sum_{i=1}^n \\phi_i(x)^2, \\quad \\mathbf{C}(x) = \\sum_{i=1}^n \\nabla\\phi_i(x)\\nabla_i\\phi(x)^T.\n$$\nFor example, if $\\phi_i(x) = a_i^Tx - b$ (which is absolutely convex), we obtain linear regression with $C(x)$ as the Hessian, so interestingly, our methods reduce to Newton's method. Instead, notice that if we select a specific $i$ we have that $C_i(x) := \\nabla\\phi_i(x)\\nabla_i\\phi(x)^T$ satisfies Equation (5) in Assumption 2.1 since for all $x \\in \\mathbb{R}^d$,\n\n$$\n0 \\preceq C_i(x) \\preceq \\mathbf{C}(x).\n$$\n\nAlthough $C_i$ produces a looser lower bound, it is still a valid curvature matrix and is cheaper to compute than the full curvature matrix, which can be the Hessian in special cases. This opens up possibilities to explore the empirical performance and convergence properties of methods that randomly select indices/data points to form local curvature matrices. Such a family of methods would be relevant to large-scale machine learning problems (where $n$ is large) where forming or inverting the Hessian/full curvature matrix is not computationally feasible. \n\nAnother interesting result is that our class of functions leads to a convergence rate of $O(\\frac{L_C}{k})$ for LCD1 and LCD2. We could have problems where $L_C << L$, which results in our methods having better convergence rates than their classical counterparts. To provide intuition with a simple example, consider $f(x,y) = 50\\delta^2x^2 + h(y)^2$ where $\\delta > 0$ and $h$ is the Huber loss function. Then $f$ is L-smooth with $L = 100\\delta^2$. Additionally, $f$ satisfies Assumption 2.1 with $L_C = 3\\delta^2$ and,\n$$\nC(x,y) = \n\\begin{bmatrix}\n100 & 0 \\\\\\\\\n0 & g(y)\n\\end{bmatrix}\n$$\nwhere $g(y) = |y|$ if $|y| \\leq \\delta$ and $g(y) = \\delta^2$ otherwise. \n\n## Concluding remarks\n\nWe thank the reviewer for their time and effort in reviewing our paper. We hope that our rebuttal here answers all the great points raised by the reviewer, allowing them to potentially upgrade their score if our responses merit it. We are also more than happy to answer any further questions that arise in the rebuttal period. Please let us know.\n\n\n## References\n\n[1] Stephen Boyd. Lecture notes: Subgradient methods, Jan. 2014.\n\n[2] R. M. Gower, A. Defazio, and M. Rabbat. Stochastic Polyak Stepsize with a Moving Target, Sept. 2021.\n\n[3] R. M. Gower, M. Blondel, N. Gazagnadou, and F. Pedregosa. Cutting Some Slack for SGD with Adaptive Polyak Stepsizes, May 2022.\n\n[4] S. Li, W. J. Swartworth, M. Takác, D. Needell, and R. M. Gower. SP2: A Second Order Stochastic Polyak Method, July 2022.\n\n[5] Dong et al. \"Towards Quantifying the Hessian Structure of Neural Networks\" 2025. \n\n[6] Malitsky and Mishchenko, \"Adaptive Gradient Descent without Descent\". 2019\n\n[5] Dong et al. \"Towards Quantifying the Hessian Structure of Neural Networks\" 2025."}, {"review_id": "XKFH0eST52", "reviewer": "Reviewer_GhWH", "summary": "The paper considers iterative procedures for minimizing convex functions that satisfy growth conditions that are more general than standard (strong) convexity and smoothness. The contributions of this paper are in proposing these new growth conditions and methods that leverage this in the manner of gradient descent for smooth functions.", "questions": "1. How does (5) compare with self-concordance?\n\n2. Backtracking line search can also be viewed as taking advantage of the local curvature (depending on the criterion used for backtracking), so how does this method compare to backtracking line search for convex, smooth functions?\n\n3. While the conciseness of the update for LCD2 is nice, it would be useful to see how $\\beta_{k}$ is defined without having to refer to the appendix as it is an essential part of the update. It is also not immediately obvious why LCD2 becomes GD with Polyak stepsize when $\\mathbf{C} = 0$ -- perhaps this has to do with the form of $\\beta_{k}$ which emphasizes the need to include it in the main text.\n\n4. How is LCD3 defined when $C$ is non-invertible? Is it the case that there might be more than one solution to the problem, and in that case would any solution work?\n\n5. I can see how LCD1 would be a descent method (i.e., ensures continuous decrease), but can the same be said for LCD2?\n\n6. Comparing against Polyak's method for problems with $L_{3}$ regularization in Figures 3 and 4 is not a fair comparison in my opinion; considering this is not a setting where the gradients are not bounded (see https://arxiv.org/pdf/1905.00313 for a discussion). I think it helps point out how the local curvature conditions might be useful and it would have been more interesting to see a comparison against (damped) Newton's method or a quasi-Newton method.\n\n7. How can you potentially circumvent the $\\mathcal{O}(d^{3})$ cost for $\\mathbf{C}^{-1}$ in the methods, especially relative to Newton's method which also suffers from the same complexity. This leads me to another question (stated below).\n\n8. The elegance of the Newton's method / quasi-Newton method is that with an oracle for Hessians and gradients, the method is pretty much black-box. In this case, there is a need to identify $\\mathbf{C}$ for a given problem specification, and the authors discuss the case of $\\|.\\|_{p}$. Can identifying $\\mathbf{C}$ be more \"automatic\" in some way?\n\n9. Why is the BB method behaving so irregularly? Is it an implementation difficulty or a procedural issue with BB?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Notwithstanding the comments on writing below, I think the paper is very clear and easy to understand. I think stating the results for when $\\mathbf{C}(x) \\succeq \\mu I$ is useful, and provides a more comprehensive picture. I think the notions of growth proposed are interesting and different to the more canonical ideas in convex optimization. The methods proposed are rather interesting too and original, particularly LCD2 and LCD3.\n\n### Writing\n\nI think the paper can be organized a little better; there are a variety of items scattered across many sections in the paper. Here are some remarks that the authors can perhaps use to improve their manuscript.\n\n1. The summary of contributions can be made more concise given the page limit, and I feel that the section could be renamed to be more representative of the key assumption which is new.\n\n2. The calculus of these properties, and examples of functions (including absolutely convex functions) satisfying the new growth conditions in (5) and (6) can be discussed as a subsections of the new Section 2 proposed above.\n    - The property about square of an absolutely convex function being convex is interesting and should be included with Lemma 7.1.\n\n3. The LCD method can discussed right after with theorems proving convergence guarantees in the following section, followed by an empirical section.\n\nIn my mind, this has a cleaner presentation of the contributions of this work.", "was_revised": true, "final_justification": "I have had positive discussions with the authors and would recommend acceptance.", "rebuttal": "We thank the reviewer for engaging with our paper during the review period!  We are glad that the reviewer found our notions of growth to be different to the more canonical ideas in convex optimization and our methods interesting and original. We now address the reviewer's concerns. \n\n## Improving Organization\n\nWe appreciate the reviewer's detailed feedback on the organization of our paper. In particular, we will modify the section regarding summary of contributions and update Lemma 7.1 to include that the square of an absolutely convex function is convex which the reviewer found to be interesting.\n\n## Questions\n\n> How does (5) compare with self-concordance?\n\nSelf-concordance requires the function to be thrice differentiable and bounds the third derivative (which measures change in curvature) in terms of the second derivative i.e. $|f'''(x)| \\leq |f''(x)|^\\frac{3}{2}$. Specifically, self-concordance allows for better convergence analysis of Newton's method and related quasi-Newton methods. Although the self-concordance property bounds change in curvature, it is a different concept from (5). Assumption 2.1. does not involve the third derivative, but from Lemma E.6 and E.10 in the Appendix, we do know that,\n\n$$C(x) \\preceq \\nabla^2 f(x) \\preceq C(x) + L_C\\cdot I.$$\n\nWhile the local curvature matrix provides bounds on the Hessian, it does not say anything about third-order information. \n\n> While the conciseness of the update for LCD2 is nice, it would be useful to see how is defined without having to refer to the appendix, as it is an essential part of the update. It is also not immediately obvious why LCD2 becomes GD with Polyak stepsize when C = 0. Perhaps this has to do with the form of which emphasizes the need to include it in the main text.\n\nWe acknowledge the reviewer's concern regarding the clarity of the update step of LCD2. When minimizing a convex function $f$, the Polyak step size corresponds to projecting the current iterate, $x_k$, onto the halfspace,\n$$\n\\mathcal{L}(x_k) = \\\\{x \\in \\mathbb{R}^d \\ | \\ f(x_k) + \\langle\\nabla f(x_k), x - x_k \\rangle \\leq f^\\star \\\\}.\n$$\nThis projection problem can be solved in closed form, and the update step corresponds to GD with Polyak step size.  \n\nThe update step of LCD2 corresponds to projecting the current iterate, $x_k$ onto the ellipsoid,\n$$\n\\mathcal{L}_C(x_k) = \\\\{x \\in \\mathbb{R}^d \\ | \\ f(x_k) + \\langle\\nabla f(x_k), x - x_k \\rangle + \\frac{1}{2}\\langle C(x_k)(x-x_k), x - x_k \\rangle \\leq f^\\star \\\\}.\n$$\nWhen $C = 0$, our assumption reduces to convexity and L-smoothness and $\\mathcal{L}_C(x_k)$ becomes $\\mathcal{L}(x_k)$. Then it is easy to see that the projection problems are the same so LCD2 reduces to GD with Polyak step size. However, LCD2 does not have a closed-form update step as the reciprocal of $\\beta_k$ is a unique root of a scalar equation that does not have a closed-form solution. We will update Section 3.2 of the paper to include the more detailed explanation above. \n\n> How is LCD3 defined when C is non-invertible? Is it the case that there might be more than one solution to the problem, and in that case would any solution work?\n\nIn that special case, we can use the pseudo-inverse of $C(x_k)$ instead which means that there is not a unique solution. \n\n> I can see how LCD1 would be a descent method (i.e., ensures continuous decrease), but can the same be said for LCD2?\n\nIt is true that LCD2 and LCD3 are not guaranteed to decrease the function value at each step. LCD2 and LCD3 project the current iterate onto the localization set, which does not guarantee descent. For a specific example, it is well known that GD with Polyak step size is not a descent method [1] and LCD2 reduces to polyak step size when $C = 0$. \n\n> Comparing against Polyak's method for problems with regularization in Figures 3 and 4 is not a fair comparison in my opinion;  considering this is not a setting where the gradients are not bounded.\n\nWe acknowledge the reviewer's concern about the unbounded gradients in some of our experiments. However, the Polyak step size is special and interesting because it is very robust in many settings, including problems that are not L-smooth or do not have bounded gradients. Many works have proposed stochastic extensions of the Polyak step size to train neural networks. Therefore, we do believe it is interesting and appropriate to compare how LCD2 and LCD3 (which are extensions of Polyak step size with local curvature) perform in the $L_3$ regularization setting. \n\n> How can you potentially circumvent the cost for O(d^3) in the methods, especially relative to Newton's method which also suffers from the same complexity. This leads me to another question (stated below)\n\nWe acknowledge the concern regarding the $O(d^3)$ computational cost associated with matrix inversion. However, in many of our examples, the curvature matrices often exhibit special structure, such as being diagonal, or even rank-one, which allows for efficient computation of $(C(x_k) + \\beta_k I)^{-1}$. \n\n>The elegance of the Newton's method / quasi-Newton method is that with an oracle for Hessians and gradients, the method is pretty much black-box. In this case, there is a need to identify C for a given problem specification, and the authors discuss the case of $||\\cdot||_p$. Can identifying C be more \"automatic\" in some way?\n\nWe appreciate the reviewer’s question regarding the potential for automatically determining the local curvature matrix  $C$. While this is an interesting and valuable direction, it falls outside the scope of the present work. We comment that for curvature matrices of the form $C(x) = \\mu(x) \\cdot I$, it may be feasible to perform power iteration on the Hessian at current iterate $x_k$ to obtain an estimate of the local strong convexity constant, $\\mu(x_k)$. \n\nWe focus on the setting where such a curvature matrix is assumed to be available. The main contribution of our work is introducing and demonstrating the value of this assumption. First, we show that in many convex optimization problems such as p-norms, certain convex loss functions, and squares of absolutely convex functions, the curvature matrix is readily available. Next, under these local curvature assumptions, we develop theoretically grounded adaptive algorithms such as LCD2 that improve upon their classical counter-parts such as GD with Polyak step size. \n\nExploring heuristic or data-driven methods for approximating C is indeed an intriguing direction, and we view this as promising future work. However, our current contribution and focus is developing principled algorithms built on rigourous theoretical foundations. \n\n\n> Why is the BB method behaving so irregularly? Is it an implementation difficulty or a procedural issue with BB?\n\nThe BB step size does not have convergence guarantees for convex smooth problems. Therefore, for certain problems, the BB step size method may behave irregularly. \n\n## Concluding Remarks\n\nWe thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their questions and concerns, and we kindly ask the reviewer to consider a fresher evaluation of our paper if the reviewer is satisfied with our responses. We are also more than happy to answer any further questions that arise. \n\n## References\n\n[1] Stephen Boyd. Lecture notes: Subgradient methods, Jan. 2014."}, {"review_id": "2pWh36ANMI", "reviewer": "Reviewer_bXSH", "summary": "Look at a series of methods for optimizing functions with known point-wise quadratic lower bounds.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper proposes a class of functions that generalize convexity by introducing a flexible quadratic lower bound into the usual lower and upper linearization bounds used in the analysis of optimization methods. The paper is well written and easy to read, clearly explaining the concepts introduced and providing detail where necessary. \n\nI have a few concerns with this paper that make me lean towards rejection. \n\n1. The actual matrix correction used regularizes the C matrix with $L\\cdot I$, which for any interesting practical problem means that the actual step taken will be overwhelmingly corrected by $L\\cdot I$ not C, essentially becoming a diagonal step. This is just far too conservative to make for an interesting step size. This is why the rates obtained are just the same as you would get using a simple 1/L step size for LCD1 - the step will behave virtually the same as that step!\n\n2. LCD2 is a trust region method, i.e. the reduction to a 1D optimization over the beta parameter to set the step size is just well known trust region theory. This relation needs to be fleshed out in the paper. The existing theory developed in this area in the last 4 decades is enormous.\n\n3. LCD3 is interesting, but without either theory for it, or far more comprehensive experiments, the investigations for that method is not sufficient for publication. A paper focused on this method, with further developments would be interesting, but requiring knowledge of f* still makes it a niche method.\n\n4. The set of problems where C is known and tractable is very small, and the further requirement that we know either L or f* narrows the set even further. It looks like it won't be easier to compute than the Hessian in various practical cases (such as logistic regression). A Hessian based trust-region baseline would need to be included if that's the problem being focused on.\n\nI would be very (pleasantly) surprised if the proposed methods outperform LBFGS, the standard approach for solving non-stochastic optimization problems without complex constraints. Since matrix-calculations are used in formulations LCD2-3, a comparable SOTA quasi-newton approach would be a good comparison point. The baseline methods used are not generally SOTA and are interesting for different reasons. Polyak for its universality (good rates for non-smooth, which LBFGS struggles with), and MM for it's lack of any tuning parameters.\nIn the case where $C \\propto I$, a line search baseline would be appropriate.", "was_revised": true, "final_justification": "See comments", "rebuttal": "We are appreciative of the time and effort the reviewer spent engaging with our work. We are glad that the reviewer found LCD3 to be an interesting method and our work to be well written and easy to read. We now address the reviewer's concern.\n\n## $L_\\mathbf{C}$-smoothness vs $L$-smoothness\n> The actual matrix correction used regularizes the C matrix with L, which for any interesting practical problem means that the actual step taken will be overwhelmingly corrected by L not C, essentially becoming a diagonal step...This is why the rates obtained are just the same as you would get using a simple 1/L step size for LCD1 - the step will behave virtually the same as that step!\n\nFirstly, we emphasize that our rates are based on $L_\\mathbf{C}$ and we know that $L_\\mathbf{C} \\leq L$ for functions that are smooth. Also, we would like to highlight that our goal is to leverage local curvature information to develop methods with adaptive step sizes.  To that end, only one of our methods, LCD1, which is an analog of GD with constant step size, employs $L_C$ in the update step. LCD2 uses an adaptive term $C(x_k) + \\beta_k I$, and LCD3 is also a fully adaptive method that does not depend on $L_C$. Furthermore, it is not the case that the update step is dominated by $L_C$. To illustrate this point, we consider a simple ill-conditioned example. Let $0 < \\delta < 100$ and $h: \\mathbb{R} \\to \\mathbb{R}$ be the huber loss,\n$$\nh(y) = \n\\begin{cases}\n\\frac{1}{2}y^2 &  |y| \\leq \\delta,  \\\\\\\\\n\\delta(|y| - \\frac{1}{2}\\delta) &| y| > \\delta\n\\end{cases}\n$$\n\nLet $f(x,y) = 50 \\delta^2x^2 + h(y)^2$. Then $f$ is L-smooth with $L = 100\\delta^2$. Additionally, $f$ satisfies Assumption 2.1 with $L_C = 3\\delta^2$ and,\n$$\nC(x,y) = \n\\begin{bmatrix}\n100 & 0 \\\\\\\\\n0 & g(y)\n\\end{bmatrix}\n$$\nwhere $g(y) = |y|$ if $|y| \\leq \\delta$ and $g(y) = \\delta^2$ otherwise. Therefore, we can see that the update step of LCD1 will not be dominated by $L_C \\cdot I$ term everywhere. Furthermore, we also have that $L_C << L$ and the gap can be made arbitrarly larger. The convergence rates we obtain for LCD1 and LCD2 are based on $L_C$ and not the classical $L$ smoothness constant. Therefore, we obtain better convergence rates up to constants than GD with constant or Polyak step size, especially when $L_C << L$. Furthermore, analogous to the polyak step size, LCD2 can often perform better in practice than suggested by the theoretical convergence rate.\n\n## LCD2 vs trust-region methods\n> LCD2 is a trust region method, i.e. the reduction to a 1D optimization over the beta parameter to set the step size is just well known trust region theory. \n\nWe recognize the reviewer’s observation regarding potential connections between LCD2 and trust region methods.  However, we respectfully disagree with the claim that LCD2 is a trust-region method. Trust region methods minimize a quadratic approximation of $f$ subject to a local radius constraint,\n$$\n\\text{min}_x \\ \\{f(x_k) + \\langle\\nabla f(x_k), x - x_k \\rangle + \\frac{1}{2}(x - x_k)^T \\nabla^2 f(x)(x-x_k)\\} \\\\ \\quad \\text{s.t.} \\ ||x - x_k||_2 \\leq \\Delta_k,\n$$\n\nwhere $\\Delta_k$ is the region radius. On the other hand, the update step of LCD2 is projection onto an ellipsoid,\n\n$$\n\\text{min}_x \\ ||x - x_k||_2^2 \\\\\n\\text{s.t.} \\ f(x_k) + \\langle\\nabla f(x_k), x - x_k \\rangle + \\frac{1}{2} \\langle C(x_k)(x- x_k), x - x_k \\rangle \\leq f^\\star\n$$\n\nInstead of minimizing a quadratic function subject to a norm constraint on $x - x_k$, we are minimizing $||x - x_k||_2^2$ subject to a quadratic constraint. While there are some similarities in form, the underlying optimization problems are different.\n\nTo solve the constrained optimization problem in the update step of LCD2, we apply standard techniques from optimization theory. We derive the corresponding dual problem in terms of a scalar Lagrange multiplier. This reduces the update step to finding the unique root of a 1D function (which is different than the 1D function you would obtain from the trust-region method). We show that Newton’s method can be used to find the root, with guaranteed convergence, as detailed in Appendix C.1, where we also note similar derivations appear in trust-region literature [5]. However, the use of Lagrange multipliers and Newton’s rooting finding method are general tools and are not exclusive to trust-region methods. While the projection onto the ellipsoid in our case also reduces to a scalar root-finding problem—resembling a trust-region step in form, this similarity alone does not make LCD2 a trust-region method. \n\n## LCD3 + Evaluations\n\n> LCD3 is interesting, but without either theory for it, or far more comprehensive experiments, the investigations for that method is not sufficient for publication. \n\nWe provide many experiments demonstrating the superior empirical performance of LCD3. We perform logistic regression, linear regression, and Huber loss regression experiments with various regularizers across several datasets. Our experimental evaluations are based on standard setups and commonly used datasets in convex optimization literature. \n\n> The set of problems where C is known and tractable is very small, and the further requirement that we know either L or f* narrows the set even further. It looks like it won't be easier to compute than the Hessian in various practical cases (such as logistic regression). A Hessian-based trust-region baseline would need to be included if that's the problem being focused on.\n\nWe understand the reviewer's concern but politely disagree. Our assumptions regarding local curvature are weaker than the well-studied strong convexity and smoothness in the literature, and recover convexity and smoothness as a special case. Also, we show interesting examples satisfying our assumptions, which are not strongly convex or smooth. \n\nAdditionally, in many cases, the curvature matrix is diagonal e.g. for $p$-norms, so it is easier to compute than the full Hessian for $p$-norm regularized problems. For objective functions expressed as a sum of squared absolutely convex functions $\\phi_i$, we have,\n$$\n\\begin{equation}\nf(x) = \\sum_{i=1}^n \\phi_i(x)^2, \\quad \\mathbf{C}(x) = \\sum_{i=1}^n \\nabla\\phi_i(x)\\nabla_i\\phi(x)^T.\n\\end{equation}\n$$\nComputing the sum of outer products may be cheaper than forming the full Hessian. Notably, even computing this sum over a mini-batch of indices $S \\subset \\{1, \\dots, n\\}$ yields a valid curvature matrix: $\\sum_{i \\in S} \\nabla\\phi_i(x)\\nabla_i\\phi(x)^T$ satisfying Equation (5). Computing a mini-batch curvature matrix is more efficient, allowing for scalable approximations to the full curvature matrix in large-scale settings. A concrete instance of this setup is linear regression, where  $\\phi_i(x) = a_i^\\top x + b$ (which is absolutely convex), demonstrating a practical scenario. \n\nOur empirical focus is on comparing our methods to classical counterparts like gradient descent with the Polyak step size, as our approaches extend these adaptive strategies. In our experimental settings, such as regularized logistic regression, where the curvature matrix comes from the regularizer rather than the full Hessian, our methods still outperform adaptive baselines, including in wall-clock time, demonstrating the practical benefit of employing a readily available local curvature matrix.\n\n## Knowledge of $f^\\star$\nWe acknowledge the reviewer’s comment that requiring knowledge of the minimum value poses a potential limitation for LCD2 and LCD3, which are extensions of the Polyak step size. We would like to clarify that in many modern machine learning settings, this requirement may not be as restrictive as it initially appears. There has been a growing body of work on stochastic Polyak step sizes for finite sum minimization $\\min_x \\sum_{i=1}^n f_i(x)$ where the requirement is relaxed to knowing each individual $f_i^\\star$. This relaxation is particularly relevant for overparameterized models, which are now widespread. In such models, the training data can often be fit exactly, implying that $f_i^\\star = 0$. As a result, future extensions of our work, particularly in the stochastic setting, can leverage these developments to broaden applicability. In light of this, we respectfully disagree that our methods are niche as there is a lot of promise for optimization methods in machine learning that use $f^\\star$. \n\nAnother well-known example where we know that value of the global $f^\\star$ is binary classification with linearly separable data ($f^\\star = 0$). Additionally, when the value of $f^\\star$ is not known we can estimate it as $f_{\\text{best}} - \\gamma^k$ where the sequence $\\gamma^k > 0$, $\\gamma^k \\to 0$, $\\sum_k \\gamma^k = \\infty$ and $f_{\\text{best}}$ refers to the smallest objective value in the trajectory so far [1]. Furthermore, several works have proposed strategies to employ the Polyak step size in the stochastic setting for finite sum minimization without knowledge of $f_i^\\star$. A common approach is introducing slack constraints, i.e. finding the smallest possible $s \\in \\mathbb{R}$ such that $f_i(x) \\leq s$ [2] [3] [4] . Stochastic Polyak methods require knowledge of each $f_i^\\star$, which is a weaker condition than knowing the global $f^\\star$. \n\n## Concluding remarks\n\nWe hope that our responses were sufficient in clarifying all the great questions asked by the reviewer. We thank the reviewer again for their time, and we politely encourage the reviewer to consider updating their score if they deem that our responses in this rebuttal merit it.\n\n## References\n\n[1] Stephen Boyd. Lecture notes: Subgradient methods, Jan. 2014.\n[2] R. M. Gower, A. Defazio, and M. Rabbat. Stochastic Polyak Stepsize with a Moving Target, Sept. 2021.\n[3] R. M. Gower, M. Blondel, N. Gazagnadou, and F. Pedregosa. Cutting Some Slack for SGD with Adaptive Polyak Stepsizes, May 2022.\n[4] S. Li, W. J. Swartworth, M. Takác, D. Needell, and R. M. Gower. SP2, July 2022.\n[5] Nocedal and Wright. \"Numerical Optimization\". 2006"}, {"review_id": "Yoj4xF85qn", "reviewer": "Reviewer_ch1b", "summary": "This paper introduces notions of local/relative convexity and smoothness that generalize existing notions in the literature (See, for example _RSN: Randomized Subspace Newton_ by Gower _et al_). Three algorithms are proposed which exploit this property, two of which have accompanying theoretical guarantees. A practical discussion of functions possessing these properties follows, and then the paper concludes with some illustrative numerical experiments.", "questions": "In line 85, with respect to SP2, what is a localization set? Is it as defined in eq 7?\n - Consider adding a remark immediately below Assumption 2.1 explaining how your definition of local curvature relates to the relative smoothness and relative convexity of Gower.\n - Example 6.1: why would one want to consider the squared Huber loss? Are there any papers in the literature that do so? Similarly, perhaps a bit more motivation for absolutely convex functions could be provided.\n - In figures 2 and 3, how do you compute the ground truth solution $x^{\\star}$? Is this the solution to the regularized binary classification problem? Moreover, I think $f(x_k) - f_{\\star}$ would be a more reasonable thing to plot on the y axis, as this aligns better with your theorems.\n - I think the right hand side of equation 19 is missing a factor of $-2$. \nTypos:\n - _line 69_ 'and a performing a linear solve' should be 'and performing a linear solve'.\n - line 274: 'zre' should be 'are'\n - line 284: 'thregularizer' should be 'the regularizer'\n - _line 312_: 'performance.The' should be 'performance. The'\n - _line 872_: 'Lemma B.1' should be 'By lemma B.1'", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n - This paper is easy to read. I greatly appreciate the layout; the use of short sections and paragraph makes following along very easy. \n - The literature review is current and informative, without overwhelming the reader with unnecessary citations.\n - The proposed algorithms are interesting and appear easy to implement (at least when $C$ is diagonal). \n - Overall, an interesting paper, which leaves many further research directions open to the reader.\n\n### Weaknesses\n - Due to the length of the submission, I did not check the proofs closely, although they seem reasonable. I did find some minor typos (see questions), so I encourage the authors to address these and also double check their proofs. \n - See \"questions\" for some minor points.", "was_revised": true, "final_justification": "I maintain my original score, and think this paper is worth accepting. I thank the authors for answering my questions, and for implementing some of my suggestions.", "rebuttal": "We thank the reviewer for the time and effort they spent reading and engaging with our paper. We are glad that the reviewer found our paper and proposed algorithms to be interesting. \n\n## Relative smoothness \n\n> Consider adding a remark immediately below Assumption 2.1 explaining how your definition of local curvature relates to the relative smoothness and relative convexity of Gower. \n\nThank you for this suggestion. In the final paragraph of the subsection, we have a sentence that states the discussion of related assumptions is in Appendix A. In Appendix A, we provide a detailed explanation about the connection to relative convexity and smoothness. We will modify this sentence to explicitly state that we discuss relative convexity and smoothness in the appendix. \n\n## Questions\n> Example 6.1: why would one want to consider the squared Huber loss? Are there any papers in the literature that do so? Similarly, perhaps a bit more motivation for absolutely convex functions could be provided.\n\nWe provide the squared Huber loss as an example of a simple function that satisfies our assumption with $L_C \\leq L$ and provides intuition about this new class of functions. The square of the Huber loss is not strongly convex because $f''(x) = 0$ at $x = 0$. However, the function has a non-zero curvature matrix elsewhere, which can be employed by our algorithms. So this is a simple example where a function is not strongly convex (a common assumption in optimization) but satisfies our assumption with a non-trivial $\\mathbf{C}(x)$ curvature matrix. In our assumption, the curvature matrix is allowed to vary with $y$, which makes it much more flexible. So, many functions relevant to optimization are included in this new class. The intuition regarding absolutely convex functions follows similarly. \n\n> In figures 2 and 3, how do you compute the ground truth solution x^*? Is this the solution to the regularized binary classification problem? Moreover, I think would be a more reasonable thing to plot on the y axis, as this aligns better with your theorems.\n\nFor these experiments, we first run Newton's method to determine the approximate $x^*$. The update step of LCD2 and Polyak step size method involves projections onto localization sets and is guaranteed to satisfy $||x_{k+1} - x^\\star||_2 \\leq ||x_k - x^\\star||_2$. We plot $||x_k - x^\\star||_2$ to highlight this fact. \n\n> I think the right hand side of equation 19 is missing a factor of -2. \nThank you for verifying. That is a typo; the factor of -2 comes from Lemma B.1.\n\nWe appreciate the reviewer for finding the typos and have corrected them in an updated manuscript.  \n\n## Concluding Remarks\n\nWe thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their questions and concerns, and we kindly ask the reviewer to consider a fresher evaluation of our paper if the reviewer is satisfied with our responses. We are also more than happy to answer any further questions that arise."}]

Author rebuttal:

Meta-review: Consider the problem of minimizing a convex differentiable function over $\mathbb{R}^d$. This paper proposes a novel assumption, Assumption 2.1, which replaces the squared Euclidean norm terms in the standard smoothness and strong convexity assumptions with norms defined with respect to $C(x) + LI$ and $C(x)$, respectively, for some $L > 0$. Here, $C(x)$ is a positive-definite matrix-valued mapping. The paper then analyzes two algorithms, LCD1 and LCD2, which are analogous to vanilla gradient descent and gradient descent with the Polyak step size, respectively. It also proposes the LCD3 algorithm, which lacks a convergence guarantee but performs well in numerical experiments.

The proposed assumption is novel, natural, and interesting. I believe it provides valuable insights into understanding adaptive step sizes in convex optimization. The significance of the assumption is supported by several examples in Sections 6 and 7, though they are arguably quite similar. The suggestion of utilizing the proposed assumption by adding a regularizer in Section 6 is reasonable, but $L_p$-norm regularizers for $p > 2$ are not very popular. The algorithm LCD2 inherits the limitation of the Polyak step size in that it requires knowledge of $f_\star$, as pointed out by Reviewer bXSH.

Both Reviewer GhWH and Reviewer bXSH are concerned with the comparison to quasi-Newton methods. The authors have shown in the rebuttal that their algorithms are competitive with L-BFGS.

Given the above, and the observation that three out of the four reviewers gave a score of 4, reflecting a conservative attitude toward accepting this paper, I suggest accepting this paper as a poster but would not mind if my recommendation were bumped down.
Decision: Accept (poster)