Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking
Authors: Frederik Kunstner
Victor S. Portella
Mark Schmidt
Nick Harvey
Venue: NeurIPS 2023 poster (2023)
Keywords: line-search
gradient descent
hypergradient
adaptive methods
smooth
convex
optimization
preconditioning
TL;DR: We develop a multidimensional version of backtracking line-search to find per-coordinate step-sizes for gradient descent with strong theoretical guarantees.

Abstract: The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate step-sizes. We propose multidimensional backtracking, an extension of the backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the gradient with respect to the step-sizes, also known as hyper-gradients, yields separating hyperplanes that let us search for good preconditioners using cutting-plane methods. As black-box cutting-plane approaches like the ellipsoid method are computationally prohibitive, we develop an efficient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning.

Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking
Frederik Kunstner
Victor S. Portella
Mark Schmidt
Nick Harvey
(kunstner, vi victorsp, schmidtt, ni nickhar) @css ubc. ca University of British Columbia
Canada CIFAR AI Chair (Amii)*
Abstract
The backtracking line-search is effective technique to automatically tune the step-size in smooth optimization. guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none the existing methods provably competitive with the optimal per-coordinate step- sizes. We propose multidimenssional backtracking, an extension of the backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the gradient with respect to the step-sizes, also known as hyper- gradients, yields separating hyperplanes that let search for good preconditioners using cutting-plan methods. As black-box cutting-plan approaches like the el- lipsoid method are computationally prohibitive, we develop an efficient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires manual tuning.
1 Introduction
When training machine learning models, tuning the hyperparameters of the optimizer is often major challenge. For example, finding reasonable step-size hyperparameter for gradient descent typically involves trial-and-error or costly grid search. In smooth optimization, a common approach to set the step-size without user input a backtracking line-search: start with a large step-size, and decrease it when it is too big to make sufficient progress. For ill ill-conditioned problems. however, there are limits to the improvement achievable by tuning the step-size. Per-coordinate step-sizes-alss also known as diagonal preconditioners can drastically improve performance. Many approaches have been developed to automatically tune per-coordinate step-sizes. Those are often described as "adaptive" methods, but the meaning of this term varies widely, from describing heuristics that set per-coordinate step-sizes, to ensuring performance guarantees as if particular property of the problem were known in advance. Yet, even the simplest case of smooth and strongly convex deterministic problem where good fixed diagonal preconditioner exists (i.e., one that reduces condition number), none of the existing adaptive methods are guaranteed to find per-coordinate step-sizes that improve the convergence rate. We discuss approaches to adaptive methods in the next section.
Contribution. We propose multidimensional backtracking, an extension of the standard backtracking line-search to higher dimension, to automatically find good per-coordinate step-sizes. Our method recovers the convergence rate of gradient descent with the optimal preconditioner for the problem, up /2d factor where d the number of coordinates. This is direct generalization of the line-search guarantee, with a penalty depending on dimension due to the extra degrees of freedom, expected.
1.1 Adaptive step-sizes and preconditioning methods
Adaptive and parameter-free methods in online learning are an example where adaptive methods have well-defined meaning, AdaGrad (McMahan and Streeter, 2010; Duchi al., 2011) and Coin Betting (Orabona and Pál, 2016; Orabona and Tommasi, 2017) can adapt to problem-specific constants without user input and have strong guarantees, even in the adversarial setting. However,
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

this resilience to adversaries is double-edged sword: to satisfy this definition of adaptivity, AdaGrad uses monotonically decreasing step-sizes. While AdaGrad still converges at the desired asymptotic rate on smooth, Lipschitz functions (Ward et al., 2019; Li and Orabona, 2019), its performance can be worse than plain gradient descent. This motivated investigations of workarounds to avoid the monotonically decreasing updates, including augmenting the update with an increasing step-size schedule (Agarwal et al., 2020), a line-search (Vaswani et al., 2020), or modifying the update to the preconditioner (Defazio et al., 2022). Methods commonly used in deep learning, such as RMSProp and Adam (Hinton et al.. 2012; Kingma and Ba, 2015), are often motivated as adaptive by analogy to AdaGrad, but without decreasing step-sizes (e.g., Défossez et al., 2022, $4.3). This change is crucial for their practical performance, but nullifies their lnaane-learning adaptivity guarantees.
A Adaptive gain and hypergradient heuristics. Many heuristics that tune the hyperparameters of the optimization procedure use the gradient with respect to the hyperparameters, or hypergradients (Maclaurin et al., 2015). Methods have been proposed to tune the step-size (Masse and Ollivier, 2015), a preconditioner (Moskovitz et al., 2019), any hyperparameter (Baydin et al., 2018), or to maintain a model of the objective (Bae et al., 2022). "Stacking" such optimizers recursively has been shown to reduce the dependency on user-specified hyperparameters in practice (Chandra al., 2022). This idea pre-dates the hypergradient nomenclature; Kesten (1958) presents method to update the step-size based on the sign of successive gradients, and Saridis (1970) presents a control perspective for per-coordinate step-sizes, which can be cast hypergradient update to diagonal preconditioner! This approach has led to adaptive gain methods such as Delta-Delta and variants (Barto and Sutton, 1981; Jacobs, 1988; Silva and Almeida, 1990; Sutton, 1992a,b), and further developed using the sign of the hypergradient (Riedmiller and Braun, 1993), full-matrix updates (Almeida et al., 1999), a larger history (Plagianakos et al., 2001), updates in log-space (Schraudolph, 1999; Schraudolph et al., 2005), heuristics to adjust the outer step-size (Mahmood et al., 2012). or multiplicative weight updates (Amid al., 2022). While showing promising practical performance in some settings, existing methods often motivated from intuition rather than a formal definition of adaptivity, giving no guarantee that the tuned method will converge faster, if at all. Indeed, hypergradient methods are often unstable, and may require as much manual tuning as the original optimizer they are intended to tune.
Second-order methods. A classical approach to preconditioning is to use second-order information, as Newton's is method or its regularized variants (e-g.. Nesterov and Polyak, 2006). To avoid the load of computing and inverting the Hessian, quasi-Newton methods (Dennis and Moré, 1977) such as L-BFGS (Liu and Nocedal, 1989) fit an approximate Hessian using the secant equation. Variants using diagonal approximations have also been proposed, framed as Quasi-Cauchy, diagonal BFGS, or diagonal Barzilai-B -Brreein methods (Zhu et al., 1999; Andrei, 2019; Park et al., 2020), while other methods use the diagonal of the Hessian (LeCun et al., 2012: Yao et al., 2021). Some second-order and quasi-Nec quasi-Newton methods converge super linearly (although not the diagonal or limited memory variants used in practice), but those guarantees only hold locally when close to the minimum. To work when far from a solution, those methods require "globalization" modifications, such as regularization or line-search. Unfortunately, analyses of second-order methods do not capture the global benefit of preconditioning and instead lead to worse rates than gradient descent, as in the results of Byrd et al. (2016, Cor. 3.3), Bollapragada et al. (2018, Thm. 3.1), Meng al. (2020, Thm. 1), Yao al. (2021, Apx.), Berahas et al. (2022, Thm. 5.2), or Jahani et al. (2022, Thm. 4.9).
Line-searches. Adaptivity in smooth optimization is most closely related to line-searches. The standard guarantee for gradient descent on an L-smooth function requires a step-size of 1/L, but L is typically unknown. The backtracking line-search based on the Armijo condition (Armijo, 1966) approximately recovers this convergence guarantee by starting with a large step-size, and backtracking: halving the step-size whenever it does not yield sufficient improvement. However, line- searches are often overlooked in the discussion of adaptive methods, as they do not provide a way to set more than scalar siep-size. While tinesccacches can be shown to work in the stochastic overparameterized setting and have been applied to train neural networks (Vaswani et al., 2019), improvements beyond backtracking have been limited. Additional conditions (Wolfe, 1969), non-monotone relaxations (Grippo et al., 1986), or solving the line-search to higher precision (Moré and Thuente, 1 1994) can improve the performance in practice, but even an exact tine-search cannot improve the convergence rate beyond what is achievable with a fixed step-size (Klerk et al., 2017).
'The hypergradient with respect to a diagonal preconditioner P = Diag(p) ) is, by the chain rule, the element- wise product (0) of subsequent gradients, f - ( = v O Vf(x V
2

---

10a
Optimality gap
Per-coordinate stepsizes
T-0
10"
T-30
GD+LS
10'
T-45
GDGD
10
T-55
10"
Box MB
Ellpsood MB
10"12
200
Gradient evaluations
Coordinate
Figure I: Multidimensional backtracking can find the optimal diagonal preconditioner. Example on linear regression where the optimal preconditioner can be computed. Left: Performance of Gradient Descent (GD), optimally preconditioned GD (P.GD) with line-search (+LS), and Multidi- mensional Backtracking (MB) with the strategies in Section 5. The ellipsoid variant can outperform the globally optimal preconditioner by selecting preconditioners that leads to more local progress. Right: Optimal per-coordinate step-sizes (+) and the ones found by MB (box) across iterations.
1.2 Summary of main result: adaptivity to the optimal preconditioner
Our approach is inspired by the work discussed above, but addresses the following key limitation: none of the existing methods attain better global convergence rates than a backtracking line-search. Moreover, this holds even on smooth convex problems for which good preconditioner exists.
We generalize the backtracking line-search to handle por-coord step-sizes and find a good pre- conditioner. As in quasi-Newtor methods, we build a preconditioner based on first-order information. However, instead of trying to approximate the Hessian using past gradients, our method searches for a preconditioner that minimizes the objective function at the next step. Our convergence result depends on the best rate achievable by an optimal diagonal preconditioner, similarly to how methods in online learning are competitive against the best preconditioner in hindsight, However, our notion of optimality is tailored to smooth strongly-convex problems and does not require decreasing step-sizes as in AdaGrad. Our update to the preconditioner can be interpreted as hypergradient method, but instead of heuristic update, we develop a cutting-plane method that uses hypergradients to guarantee a good diagonal preconditioner. Our main theoretical contribution is summarized below.
Theorem 1.1 (Informal). On smooth, strongly-come coneexx function f in d dimensions, steps accepted by multidimensional backtracking guarantee the following progress
V2d - (1-2)))) ) (
11-111
((x+1)) -(x))))((x))-)
where K. is the condition number achieved by the optimal preconditioner defined in Section 2. The number of backtracking steps is at most linear in d and logarithmic in problem-specift constants.
Multidimensional backtracking finds per-coordinate step-sizes that lead to a provable improvement over gradient descent on badly conditioned problems that can be improved by diagonal precondition- ing, i.e., if the condition number of f at least /2d- K,. Moreover, this guarantee is worst-case, and multidimensional backtracking can outperform the globally optimal preconditioner by finding better local preconditioner, as illustrated on ill-conditioned linear regression problem in Figure 1.
To find a competitive diagonal preconditioner, we view backtracking line-search as a outting-plane method and generalize it to higher dimensions in Section 3. In Section we show how use hypergradients to find separating hyperplanes in the space of preconditioners, and in Section 5 we develop an efficient cutting- plane methods tailored the problem. In Section 6, we illustrate the method through preliminary experiments and show it has consistent performance across problems.
Notation. We use standard font weight d, n, for sealars, bold x, y for vectors, and capital bold P. A for matrices. We use p pi]] for the i-th entry of p, use @ for element-wise multiplication, and define p² = O p. We use = Diag(p) to denote the diagonal matrix with diagonal p. and p = diag( to denote the vector of diagonal entries of P. We say A is larger than B, A 2 B, if A - B is positive semidefinite. A Diag(a), = Dbag(b), the ordering > is equivalent to a 2 b[i] for all which we write > b. We use for the identity matrix and 1 for the all-ones vector.
3

---

2 Optimal preconditioning and sufficient progress
Consider a twice-differrentabbl function f: I2d + I that is L-smooth and j-strrongly convex," 2 i.e.
/ 10-yll y112 - f(y) - f(x) - (Vf(x), - - L xx|? for all x,y, or pl 3 (x) 3 II for all x. We measure the quality of preconditioner P by how well P-1 approximates the Hessian (x). We define optimal diagonal preconditioner for f as
P. arg d,digonl K
such that -P-1 f² = p-1 for all x,
(I)
and denote by K. the optimal x above, related and known measure for the convergence rate of preconditioned methods is x (px///"((xpP_?? (Bertsekas, 1999, $1.3.2). Moreover, (1) reduces to the definition of optimal preconditioning for linear systems (Jambulapati et al.. 2020; Qu et al., 2022) when f is quadratic. Alternatively, the optimal preconditioner be viewed as the matrix P. such (x, that f is 1-smooth and maximally strongly-conves in the norm ||x|I P, 1x).
1 - - yll f(y) - f(x) - (Vf(x).y x) S lly - x1Ip-,, -
for all x,y.
(2)
k.
Similar definitions of smoothness and conge-iy relative to a matrix are common in coordinate descent methods (e.g.. Qu et al., 2016; Safaryan an al., 2021), where the matrices are assumed be known priori. If we knew P., preconditioned gradient descent using P. would converge at the rate
f(z P.Vf(x)) f(x.) < (1 -= -(xx)) f(x.)).
where minimizes f. We do not know P. and will be searching for good approximation.
For the standard backtracking line-search on L-smooth functions, the goal is to find a step-size that works as well as I/L without knowledge of L. To do so, we can start with a large step-size a > I/2 and check the Armijo condition: the step-size a makes progress as f were 1/a-smooth, that is,
f(x - a V - f(x - [
(3)
If the condition is satisfied, we take the step VV(().. By the descent lemma, (Bertsekas, 1999, A.24), the condition is satisfied if a S 1/1. So the condition fails, we know a too large and can decrease a. For diagonal preconditioners, the Armijo condition checks whether the preconditioner makes sufficient progress in the norm induced by P-1, as if f were I-smooth in Equation (2), that is,
f - (V)(x) < f(x) - [
As with a scalar step-size, sufficient progress holds for any matrix P that satisfies v2f(x) P
3 Multidimensional Backtracking
The typical presentation of the backtracking line-search maintains a step-size and decreases when the Armijo condition fails (e.g.. Nocedal and Wright, 1999, Alg 3.1). We instead take the following non-standard view, which generalizes more naturally to high dimension; as maintaining a set containing the optimal step-size, and using bisection narrow down the size of the set. Starting with an interval S [0, Ormax] containing I/r, we pick a candidate step-size a by "backtracking" by y from the largest step-size in S, taking m0 balance two properties;
1. Large progress: If the candidate step-size satisfies the Armijo condition and the step is accepted, the value of f decreases proportionally a in (3). To maximize the progress, 7 should be large.
2. Volume shrinkage: If the candidate step-size fails the Armijo condition, we learn that a > l/2 and can cut the interval S' m0 To ensure the interval shrinks fast, y should be small.
Taking 7 1/2 balances both properties; is at least 1/2 as large any step-size in S, and we can halve the interval if the Armijo condition fails. We do not use amax as a candidate since, although the largest in S, it would give no information to update the interval in case it failed the Armijo condition.
For multidimensional backtracking, we can check whether a candidate preconditioner yiclds sufficient progress with Equation (4) instead of the Armijo condition, and replace the intervals by sets of diagonal preconditioners. The high-level pseudocode is given in Figure 2, where each iteration either leads to improvement in function value shrinks the sets of potential step-sizze/precondiitonne.s
'While we use strong convexity and sice-differentiabbllyy of f to define the optimal preconditioner, those assumptions can be relaxed to only rely the PL inequality (Polyak, 1963; Lojasiewicz. 1963) (see Appendix B).

---

Backtracking line-search
Multidimensional Backtracking
Input: starting point xo, backtracking coefficient ? set So
Input: starting point xe, hacktracking coefficient set So of preconditioners containing the optimal P..
[0, ] containing the optimal step-size I/L.
Iterate for 0, 0..,..,
Iterate for in O, 1. T
Pick step-size Or, roa max
Pick stop-sizes P. = CANDIDATE(S:, 7, xx) If (xx, Pt) satisfy the Armijo condition (4)
(t)
If ae) satisfy the Armijo condition (3)
Accept x,+1 X (xx
Accept X,+1 X, P, (x)
Keep max step-size 0+411 at Otherwise,
max
Keep set S1+1 S. Otherwise,
Don't move, X:+1 = Xt
Don't move, X
Cut max step-size 1--1 "yat
Cut set S CUT(S,,,
(t)
Output: X
Output: XT
Figure 2: Pseudocode for the backtracking line-search and multidimensional backtracking, We view backtracking maintaining set of step-sizes, testing progress on ff or reduce the size of the set. Steps marked by (f), are the subject of Sections 3-5.
each iteration that either make
To complete the algorithm, we need to define the steps marked as (f) to select preconditioners that lead to large progress when the step is accepted, while significantly reducing the search space when the preconditioner does not yield sufficient progress. For computational efficiency, we want methods that take (d) time and memory like plain gradient descent.
3.1 Guaranteed progress competitive with the optimal preconditioner
We start by formalizing the progress guarantee. If P. satisfies the Armijo condition (4) at x,, the func- tion value decreases by at least (xx [ If we can guarantee that (xx > l for some y 0, we can recover the convergence rate of gradient descent preconditioned with up to factor of y. However, we do not know P., but know a set S, that contains preconditioners we have not yet ruled out, including P.. To guarantee that P. is competitive with P., we can enforce that P. is competitive with all the preconditioners in St, as captured by the following definition.
Definition 3.1 (7-competitive candidate preconditioners). matrix P. Se is 7-competitive in S.. for a gradient (x(x). if [x+ 2 > for any Q E S,-
P. y-competitive, then it competitive with P. as maxqes, [V 2 [VV IR: How- ever, this is a strong requirement. To illustrate what competitive ratios are attainable, we show in Appendix that even the optimal preconditioner P. might only be 1/a-competitive, as other precondi- tioners can lead to more local progress depending (xx)). whereas P. is fixed global optimal preconditioner. This also suggests that selecting preconditioner that guarantees more local progress may lead to better performance, which we take advantage of to ensure
1/v2a competitive ratio.
To see how ensure a competitive ratio, consider the case where S contains diagonal preconditioners whose diagonals come from the box B(b) = {p Rg. < b). To select candidate precondi- tioner that 7-comeetitive in S, we can backtrack from the largest vector B(b) by some constant 1, and take P Diag(b) While a large 7 leads to more progress when the step is accepted, we will see that we need small y to ensure the volume shrinks when the step is rejected.
We can obtain the convergence rate of Theorem 1.1 depending on and the optimal preconditioned condition number K, if we ensure P. E St and that P; is ycompetiiivv for all t.
Proposition 3.2. Let Pa, K. be an optimal preconditioner and condition number for (1). If the set S. from the algorithm Figure 2 contains P., and P. S, y-competitive (Definition 3. then
(
f((x)))
whenever the candidate step leads to sufficient progress and is accepted.
Proof. The proof relies on three inequalities. (a) The iterate X yields sufficient progress (Eq. 4), (b) any accepted preconditioner P; is --competitive in S, and thus with P., and (c) f is 1/x.-strongly convex in || p which implies K. (x+)))) 2 fxx)) f(x.). Combining those yields
(e) f(x++1) & f(x)) |vf(x))
(8)
f(x)) - 7 [Vf())) I (9) f(x)) Y (f(x)) f(x.)).
Rx
Subtracting fxx,) both sides yields the contraction guarantec.
5

---

P
P
"1
..
(a) Failing the Armijo condition cuts the interval in half in one di- mension, only removes 1/2d of the volume in d dimensions.
(b) Half-space Hss (v) obtained by using the hypergradient when fail- ing the Armijo condition P in Proposition 4.2.
(c) Stronger half-space H> (u) de- scribed by Proposition 4.3, remov- ing P' > for any ruled out by M> (v) in Proposition 4.2.
Figure 3: Lack of information from the ordering and separating hyperplanes.
Separating hyperplanes in higher dimensions
In one dimension, if the step-size a does not satisfy the sufficient progress condition (3), we know > I/1. and can rule out any a' 2 We are looking for generalization to higher dimensions: if the queried preconditioner fails the sufficient progress condition, we should able to discard all larger preconditioners, The notion of valid preconditioners formalizes this idea.
Definition 4.1 (Valid preconditioner). preconditioner P valid if ( = for all x, which guarantees that P satisfies the sufficient progress (4) condition, and invalid otherwise.
Validity is global property: a preconditioner P might lead to sufficient progress locally but still be invalid. Using the partial order, if P is invalid then any preconditioner P' > P is also invalid. However, this property alone only discards an exceedingly small portion the feasible region in high dimensions. Consider the example illustrated in Figure 3a: if the diagonals are in box B(b), the fraction of volume discarded this way if (1/2) Diag(b) is invalid is only 1/2".
To efficiently search for valid preconditioners, we show that if f is convex, then the gradient of the sufficient progress condition gives separating hyperplane for valid preconditioners. That is, it gives a vector u E Rd such that if E RRS. satisfies (u. p) > 1. then (iag(p) is invalid, as illustrated in Figure 3b. We use the following notation to denote normalized half-spaces:
Hz (u) == (pER (u. > 1} and
Hz((u) == {p R (u.p) 1}.
Proposition 4.2 (Separating hyperplane in preconditioner space). Suppose Q Diag(q) > 0 does not lead to sufficient progress (4) at x, and let h(q)) be the gap in the sufficient progress condition,
h(q) = f(x QVf(x)) f(x) + ] / 1|2 >
Then Diag(p) for any in the following half-space satisfies h(p) > 0 and also invalid,
EpeR' : p) (Vh(g), q) h(g)),
(5)
This half-space is equal to H (v) with v given by v = Vh((a/((Vi(())aa)) -1)))) or
(Lgg g og f(x) (g Qg) f(xt)*
x+
with
(6)
(g.g+) = (Vf(x), Vf(x)))
Proof idea. If f convex, then h also is. Convexity guarantees that h(()) h(q) + (Vh(g),
for any p. A sufficient condition for h(p) > 0, which means p is invalid, is whether h(q) (Vh(q), p q) 0 holds. Reorganizing yields Equation (5), and Equation (6) expresses the half- space in normalized form, Hz (v), expanding à in terms of f. its gradients, and Q
The half-space in Proposition 4.2 is however insufficient to find good enough autting-planess as uses convexity to invalidate preconditioners but ignores the ordering that if P is invalid, any P' > P also invalid. If such preconditioners are not already ruled out by convexity, we can find stronger half-space by removing them, as illustrated in Figure 3c. We defer proofs to Appendix C.
Proposition 4.3 (Stronger hyperplanes). If Hf)s(v) (v) half-space given by Proposition 4.2, then (u) where u = max(v, (v, 0} element-wise is stronger half-space in the sense that Ht (v) S Hi (u), and H (u) contains only invalid preconditioners.

---

B(bb)
B(bb))
B(b++1)
u
P
Pt
(a) Minimum-volune box containing the intersection. We maintain sets of low-complexity by computing the minimum- volume box B(b++1) containing the intersection of the initial box B(be) and the half-space H. (u,) obtained from Proposition 4.3 when the preconditioner P, fails to yield sufficient decrease.
(b) Need sufficient backtracking. If the candidate preconditioner P, selected inside the initial box (bbb)) is not close enough there might not be box smaller than B(b,) that contains the intersection.
Figure 4: Minimum-volume enclosing boxes
5 Cutting-plane methods
The multidimensional backtracking method is in fact a hyperplanes (from Proposition 4.3) to search for valid preconditioness. The canonical example is the ellipsoid method (Yudin and Nemirovski, 1976; Shor, 1977), but its computational cost is (2(d)) in Rd We now describe cutting- -lanne methods with three desirable properties: the preconditioners have good competitive ratios, the feasible set shrinks significantly when backtracking, and the computational cost is (dd). There are many details, but the overall idea is similar to the ellipsoid method.
method that uses separating
simple warm-up: boxes. Consider the case when So consists of diagonal matrices with diagonals in the box B(ba) [p& E Igg p S bo). We pick candidate preconditioner by backtracking from the largest point B(ba) by some constant 7 < I, taking P = 7 Diag (bo). If P satisfies the Armijo condition (4), take gradient step. If does not, compute the vector ug as in Proposition 4.3, and obtain a half-space H- (u)) that contains only invalid preconditioners. We then know we only need to search inside So n H- (ug). However, maintaining the set S n Hlg(u)) n... n H (u,) would be too complex to fit in (d) time or memory. To reduce complexity, we define S.+1 as the box B(b,+1) of minimum volume containing B(b,) n H& (u,). as illustrated in Figure 4a. Due to this restriction, we might not be able to find a smaller set; the original box B(b,) may already be the minimum volume box containing B(b,) n (u,) if u, does not cut deep enough, as illustrated in Figure 4b. However, with enough backtracking (7 < 1/d), we can show that the new box is smaller. This yields the following subroutines fill in the gaps of Figure 2 (detailed in Appendix D)
CANDIDATE(S, 7, xx) == 7 Diag(ba)) (br), CUT(S, P,) = (Dagg()): : Pa E B(b++1)},
(7)
where S. = B((,)) and b,+1 == min 3/u, element-wise, which give the following guarantees.
Theorem 5.1. Consider the multidimensiooal backtracking from Figure 2 initialized with set So = (Dag p): p E B(bb)} containing P., with the subroutines in Equation (7) with 7 = 1/2d. Then: (a) P. St, (b) the candidate preconditioner P, is 1/2s-comeeeitive in St for any t, and
(c) Vol(B(br++)) S atc Vol(B(b:)) when P. fails Equation (4).
In particular, CUT is not called more than d d'log411 (Lllbblloo) times.
Proof idea. To guarantee that the box shrinks, we have guarantee that the half-space H (1t) cuts deep enough. We know that the half-space has to exclude the query point P,, i.e. (Pr: U1) 2 1, by Proposition 4.2 and that u, 2 by Proposition 4.3. Querying P. sufficiently close to the origin, by taking 7 = 1/2d, is then enough to guarantee the decrease. To bound the total number of cuts, we note that the sets B(b,) have minimum volume Volmin- they have contain the valid preconditioners. The number of cuts is at most loge (Vol((B (Vo((B(b))) ( for e = d + 1. We then bound Vol(B(bo)) < [lbolls and Volmin 2 1/1." as (1/r.I is a valid preconditioner.
5.1 Multidimensional Backtracking with Centered Axis-aligned Ellipsoids
We now improve the competitive ratio from (11/a) to O(1/aa) by switching from boxes to ellipsoids. Whereas general ellipsoids would require ((d2) complexity (as they involve dxd matrix), we consider centered, axis-aligned ellipsoids, defined by diagonal matrix A = Diag(a) (a), of the form {a)) = {p E IRg. : |||||A S 1}, where || = (p. Ap). As preconditioners are non-negative, we consider only the positive orthant of the ellipsoid. For simplicity, refer to those sets ellipsoids.
7

---

Candidate preconditioner. In the box example, we selected the candidate preconditioner by back- tracking from the largest preconditioner in the box. With an ellipsoid, there is no largest preconditioner. We need to choose where to backtrack from. To ensure the candidate preconditioner P is competitive (Definition 3.1), we backtrack from the preconditioner that maximizes the progress [VV
( A A |
arg max (a
(where Vf(x)² V o Vx()))
(8)
This lets us pick the preconditioner that makes the most progress for the current gradient, and will let us improve the competitive ratio by allowing a backtracking coefficient of 1/vá instead of 1/a.
Cutting. To complete the algorithm, we need to find new set E(b(+1) with smaller volume which contains the intersection of the previous set {(;)) and the half-space Hg (u,). Unlike the box approach, the minimum volume ellipsoid has no closed form solution. However, if we backtrack sufficiently, by a factor of < 1/vá, we can find an ellipsoid guaranteed to decrease the volume.
Lemma 5.2. Consider the ellipsoid E(a) defined by A = Diag(()) for a E B p Let p E E(a) be a point sufficiently deep inside the ellipsoid, such that |p|] A 1/v2d, and (u) be a half-space obtained from Proposition 4.3 at P. The intersection {aa n (()) is contained in the new ellipsoid
E(a" (a. u});
where
a (a, = - -1-
X Ed-1 1
l =
|| A
which has a smaller volume, Vol(E(a (a, u)) S (ol(E where c V =2 0.91.
Proof idea. The new ellipsoid in (9) is convex combination between E(a) and the minimum volume ellipsoid containing the set { p E Rd (u, pp)> S 1] where |p| is the clement-wise absolute value of p. The choice of À in (9) not optimal, but suffices guarantee progress as long as ||p|| is small. A similar approach was used by Goemans et al. (2009) to approximate submodular functions, although they consider the polar problem of finding a mexiimum-volume enclosed ellipsoid. The full proof and discussion on the connections to the polar problem are deferred to Appendix D.
O
To improve the cuts, we can refine the estimate of À in Lemma 5.2 by minimizing the volume numerically. We include this modification, detailed in Appendix D, in our experiments in Section
Overall guarantees. We can now define the two subroutines for the ellipsoid method, and obtain the main result that we stated informally in Theorem 1.1. by combining the guarantees of the ellipsoid approach with the convergence result of Proposition 3.2.
Theorem 5.3. Consider the multidimensional backtracking from Figure initialized with the set So = (Diag(p): : p {(a)] containing P.,, given by some scaling on >> 0 of the uniform vector, ag = ogl. For Sr, let A, = Diag(a:). Define the subroutines
A. A P. CANDIDATE(S X1) 7 [V(())) A,1 CUT(S,, = (Diag()) E E(a" "aattaa (a,, u,))
where un is the vector given by Proposition 4.3 when P, fails the Armijo condition at Xt, and a is computed as in (9). If 1/V2d, then: (a) P. E for all (b) the candidate preconditioners P, are 1/ //zd-competiitiee in S,, and (c) CUT is called no more than 12d log L/oo) times.
6 Experiments
To illustrate that multidimensional backtracking finds good preconditioners and improves over gradient descent on ill-conditioned problems even when accounting for the cost of backtracking, we run experiments on small but very ill-conditioned and large (d 108) problems.
As examples of adaptive gain and hypergradient methods, we include RPROP (Riedmiller and Braun, 1993) and GD with a hypergradient--un update). As examples of approximate second-order methods, we include diagonal BB (Park et al., 2020) and preconditioned GD using the diagonal of the Hessian. We use default parameters, except for the hypergradient method GD-HD, where we use 10-10 as the initial step-size instead of 10 to avoid immediate divergence. We include AdaGrad (diagonal), but augment it with a line-search as suggested by Vaswani et al. (2020), to make it competitive in the deterministic setting.
step-size (GD-HD, Baydin al. 2018, multiplicative
Line-searches and forward steps. For all methods that use a line-search, we include a forward step, common heuristic in line-scarch procedures to allow for larger step-sizes when possible, although
8

---

Linear cpusmall
Logistic Breast-cancer
Logistic News20
GD+LS
104
10'
101
Ellipsold MB
Optimallyy gap
10'
Diag. Hesslan-LS
10
10
Diag. BB-NMLS
109
10
10-3
Diag. AdaGrad-LS
RPROP
10
10
10-9
GD-HD (mult.)
1500
1000
1000 1500
figrad
figradi evals
figrad
Figure 5: Multidimensionall backtracking finds good preconditioner, when there is one. Exper- iments on regularized linear and logistic regression on small but ill-conditioned datasets, cpusmall and breast-cancer (left, middle), and the large dataset News20 (right, d s 10%). Methods used: Gradient Descent (GD) Multidimensional Backtracking (MB) with ellipsoids, diagonal Hessian, diagonal BB, and diagonal AdaGrad all of which use line-search (+LS)- RPROP, and GD with hypergradient-tune step-size (GD-HD) using the multiplicative update. Details in Appendix E.
can increase the number of backtracking steps. When step-size or preconditioner accepted, we increase the size of the set, allowing for larger (scalar or per-coordinate) step-sizes by factor of 1.1.
Performance comparison. To capture the overhead of backtracking and provide fair evaluation, Figures and 5 compare performance per function and gradient evaluations (see Appendix E.I).
On small but extremely ill Ill-oonitioned problems, our method is the only one that gets remotely close to being competitive with preconditioning with the diagonal Hessian only using first- order information. The diagonal Hessian is very close to the optimal preconditioner for those problems. On the cpusmall dataset, it reduces the condition number from k ze 5 1013 to = 300, while K2 = 150. All other methods struggle to make progress and stall before a reasonable solution is achieved, indicating they are not competitive with the optimal preconditioner.
On large regularized logistic regression on News20 (d R 10%), gradient descent performs relatively better, suggesting the problem less ill-conditioned begin with (the regularized data matrix has condition number K & 10*). Despite the bound of (dd) backtracking steps, methods finds a reasonable preconditioner within 100 gradient evaluations. Despite the high dimensionality, improves over gradient descent when measured in number of oracle calls.
Using plain gradient updates on the hyperparameters GD-HD leads to unstable behavior, but diagonal BB and even RPROP, perform remarkably well on some problems- even outperforming preconditioning with the diagonal Hessian, which uses second-order information. However, they fail on other ill-conditioned problems, even when a good diagonal preconditioner exists. This pattern holds across other problems, as shown in Appendix Multidimensional backtracking demonstrates robust performance across problems, clear advantage of having worst-case guarantees.
7 Conclusion
We designed multidimensional backtracking, efficient algorithm to automatically find diagonal preconditioners that are competitive with the optimal diagonal preconditioner. Our work provides definition of adaptive step-sizes that is complementary to the online learning definition. While online learning focuses on the adversarial or highly stochastic setting, we define and show how to find optimal per-coordi step- in the deterministic smooth convex setting. We show it is possible to build provably robust methods to tune preconditioner using hypergradients. While our specific implementation uses souting-planes, the general approach may lead to alternative algorithms, that possibly tune other hyperparametens with similar guarantees.
The main limitation of our approach is its reliance on the convex deterministic setting. The results might transfer to the stochastic overparametrized regime using the approach of Vaswani et al. (2019), but the non-convex case seems challenging. It is not clear how to get reliable information from aatting-plane perspective using hypergradients without convexity. As the first method to provably find competitive preconditioners. there likely modifications that lead to practical improvements while preserving the theoretical guarantees. Possible ideas to improve practical performances include better ways perform forward steps, using hypergradient information from accepted steps (which are currently ignored), or considering alternative structures to diagonal preconditioners.

---

Acknowledgments and Disclosure of Funding
We thank Aaron Mishkin for helpful discussions in the early stages of this work, and Curtis Fox and Si Yi (Cathy) Meng for providing comments on an early version of the manuseript, and for the feedback from anonymous reviewers. This research was partially by the Canada CIFAR AI Chair Program, the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grants RGPIN-2022-03669, and Borealis Al through the Borealis Al Global Fellowship Award.
References
Naman Agarwal, Rohan Anil, Elad Hazan, Tomer Koren, and Cyril Zhang (2020). Disentangling Adaptive Gradient Methods from Learning Rates. arXiv/2002.1 1ttp://002..180..3 1803.
Lufs B. Almeida, Thibault Langlois, José F. M. Amaral, and Alexander Plakhov (1999). "Parameter adaptation in stochastic optimization". In: On-line learning in neural networks, pp. 111-134.
Ehsan Amid, Rohan Anil, Christopher Fifty, and Manfred K. Warmuth (2022). Step-size Adaptation
Using Exponentiated Gradient Updatex. Presented at the ICML Workshop Beyond First Order Methods in ML Systems.
Neculai Andrei (2019). "A diagonal quasi-Newton updating method for unconstrained optimization". In: Numerical Algorithms 81.2, pp. 575-590.
Larry Armijo (1966). "Minimization of functions having Lipschitz continuous first partial derivatives". In: Pacific Journal of mathematics 16.1, pp. 1-3.
Juhan Bae. Paul Vicol, Jeff Z. HaoChen, and Roger B. Grosse (2022). "Amortized Proximal Opti- mization". In: NeurlPS, pp. 8982-8997.
Andrew G. Barto and Richard S. Sutton (1981). Goal Seeking Components for Adaptive Intelli- gence: An Iniiill Assessment. Tech. rep. SEWAL-TR-81-1005 (Appendix C). Air Force Wright Acronautical Laboratorics/AAionics Laboratory.
Atilim Güneş Baydin, Robert Cornish, David Martinez-Rubio Mark Schmidt, and Frank Wood (2018). "Online Learning Rate Adaptation with Hypergradient Descent". In: ICLR.
Albert S. Berahas, Majid Jahani, Peter Richtárík, and Martin Takáë (2022). "Quasi-Newton methods for machine learning: forget the past, just sample". In: Optimization Methods and Software 37.5, pp. 1668-1704.
Dimitri P. Bertsekas (1999). Nonlinear Programming. Athena Scientific.
Raghu Bollapragada, Dheevatsa Mudigere, Jorge Nocedal, Hao-Jun Michael Shi, and Ping Tak Peter Tang (2018). "A Progressive Batching L-BFGS Method for Machine Learning". In: ICML, pp. 619- 628.
Richard H. Byrd, Samantha L. Hansen, Jorge Nocedal, and Yoram Singer (2016). "A Stochastic Quasi-Newton Method for Large-Scale Optimization". In: SIAM Journal on Optimization 26.2. 2, pp. 1008-1031.
Kartik Chandra, Audrey Xie, Jonathan Ragan-Kelley, and Erik Meijer (2022). "Gradient Descent: The Ultimate Optimizer". In: NeurlPS, pp. 8214-8225.
Chih-Chune Chang and Chih-Jen Lin (2011). "LIBSVM: A Library for Support Vector Machines".
In: ACM Transatctions on Intelligent Systems and Technology 2.3.
Aaron Defazio, Baoyu Zhou, and Lin Xiao (2022). Grad-GradaGrad? A Non-Monotone Adaptive
Stochastic Gradient Method. arXiv/2206.0690
Alexandre Défossez, Leon Bottou, Francis Bach, and Nicolas Usunier (2022). "A Simple Convergence Proof of Adam and Adagrad". In: Transactions Machine Learning Research.
John F. Dennis and Jorge Moré (1977). "Quasi-Newton methods, motivation and theory"". In: SIAM review 19.1, pp. 46-89.
Steven Diamond and Stephen Boyd (2016). "CVXPY: A Python-embedded modeling language for convex optimization". In: Journal of Machine Learning Research 17.83, pp. 1-5.
Dheeru Dua and Casey Graff (2017). UCI Machine Learning Repository.
10

---

John C. Duchi, Elad Hazan, and Yoram Singer (2011). " "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization". In: Journal of Machine Learning Research 12, pp. 2121- 2159.
Gary William Flake and Steve Lawrence (2002). "Efficient SVM Regression Training with SMO". In: Mach. Learn. 46.1-3, pp. 271-290.
Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, and Vahab Mirrokni (2009). "Approximat- ing submodular functions everywhere". In: ACM-SIAM SODA 2009, pp. 535-544.
Luigi Grippo, Francesco Lampariello, and Stephano Lucidi (1986). "A Nonmonotone Line Search Technique for Newton's Method", In: SIAM Journal on Numerical Analysis 23.4, pp. 707-716.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky (2012). Neural Networks for Machine Learning. lecture 6.
Robert A. Jacobs (1988). "Increased rates of convergence through learning rate adaptation", In: Neural Networks 1.4, pp. 295-307.
Majid Jahani, Sergey Rusakov, Zheng Shi, Peter Richtárik, Michael W. Mahoney, and Martin Takac (2022). "Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information", In: ICLR.
Arun Jambulapati, Jerry Li, Christopher Musco, Aaron Sidford, and Kevin Tian (2020). Fast and Near-Optimal Diagonal Preconditioning. arXiv/2008.011222
Hamed Karimi, Julie Nutini, and Mark Schmidt (2016). "Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojjsiiwicz Condition". In: ECML, pp. 991-
S. Sathiya Keerthi and Dennis DeCoste (2005). "A Modified Finite Newton Method for Fast Solution of Large Scale Linear SVMs In: Journal of Machine Learning Research 6.12. pp. 341-361.
R. Kelley Pace and Ronald Barry (1997). "Sparse spatial autoregressions". In: Statistics & Probubility Letters 33.3. pp. 291-297.
Harry Kesten (1958). "Accelerated Stochastic Approximation", In: The Annals of Mathematical Statistics 29.1, pp. 41-59.
Diederik P. Kingma and Jimmy Ba (2015). "Adam: A Method for Stochastic Optimization". In: ICLR.
Etienne de Klerk, François Glineur, and Adrien B. Taylor (2017). "On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions". In: Optimization Letters 11.7, pp. 1185-1199.
Yann LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller (2012). "Efficient BackProp". In: Neural Networks: Tricks of the Trade Second Edition. Vol. 7700. pp. 9-48.
David D. Lewis, Yiming Yang. Tony G. Rose, and Fan Li (2004). "RCVI: A New Benchmark Collection for Text Categorization Research", In: Journal of Machine Learning Research 5, pp. 361-397.
Xiaoyu Li and Francesco Orabona (2019). "On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes". In: AISTATS 2019, pp. 983-992.
Dong C. Liu and Jorge Nocedal (1989). "On the limited memory BFGS method for large scale optimization". In: Mathematical programming 45.1-3, pp. 503-528.
S. Lojasiewiez (1963). "Une propriété topologique des sous-ensembles analytiques réels". In: Les Équations aux Dérivées Partielles, pp. 87-89.
Dougal Maclaurin, David Duvenaud, and Ryan P. Adams (2015). "Gradient-based Hyperparameter Optimization through Reversible Learning". In: ICML, pp. 2113-2122.
Ashique Rupam Mahmood, Richard S. Sutton, Thomas Degris, and Patrick M. Pilarski (2012). "Tuning-fie free step-size adaptation". In: ICASSP, pp. 2121-2124.
Pierre-Y Masse and Yann Ollivier (2015). Speed learning on the fly. arXiv/1511.02540.
H. Brendan McMahan and Matthew J. Streeter (2010). "Adaptive Bound Optimization for Online Convex Optimization". In: COLT, pp. 244-256.

---

Si Yi Meng. Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste- Jaclite-Juliin (2020).
"Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation". In: A/S- TA7S, pp. 1375-1386.
Jorge J. Moré and David J. Thuente (1994). "Line search algorithms with guaranteed sufficient decrease". In: ACM Transactions on Mathematical Software (TOMS) 20.3, pp. 286-307.
Ted Moskovitz, Rui Wang, Janice Lan, Sanyam Kapoor, Thomas Miconi, Jason Yosinski, and Aditya Rawal (2019). First-Order Preconditioning via Hypergradient Descent. arXiv/990000840
Yurii E. Nesterov and Boris T. Polyak (2006). "Cubic regularization of Newton method and its global performance". In: Mathematical Programming 108.1, pp. 177-205.
Jorge Nocedal and Stephen J. Wright (1999). Numerical Optimization. Springer.
Francesco Orabona and Dávid Pál (2016). "Coin Betting and Parameter-Free Online Learning". In: NeurlPS, pp. 577-585.
Francesco Orabona and Tatiana Tommasi (2017). "Training Deep Networks without Learning Rates Through Coin Betting". In: NeurIPS, pp. 2160-2170.
Youngsuk Park, Sauptik Dhar, Stephen P. Boyd, and Mohak Shah (2020). "Variable Metric Proximal Gradient Method with Diagonal Barzilai- Borwein Stepsize". In: ICASSP, pp. 3597-3601.
Barzilai-Borwein
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala (2019). "PyTorch: An Imperative Style, High-Performance Deep Learning Library". In: NeurIPS, pp. 8024 8035.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer,
R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay (2011). 1). "Scikit-learn: Machine Learning in Python". In: Journal of Machine Learning Research 12, pp. 2825-2830.
Vassilis P. Plagianakos, George D. Magoulas, and Michael N. Vrahatis (2001). "Learning rate adapta- tion in stochastic gradient descent". In: Advances in Convex Analysis and Global Optimization: Honoring the Memory of C. Caratheodory (1873-1950), pp. 433 444.
Boris T. Polyak (1963). "Gradient methods for minimizing functionals". In: 2. Vyčisl. Mat Mat. Fiz. 3, pp. 643-653.
Zhaonan Qu, Wenzhi Gao, Oliver Hinder, Yinyu Ye, and Zhengyuan Zhou (2022). Optimal Diagonal Preconditioning: Theory and Practice. arXiv/2209.00880
Zheng Qu, Peter Richtárík, Martin Takáe, and Olivier Fercog (2016). "SDNA: Stochastic Dual
Newton Ascent for Empirical Risk Minimization". In: ICML,, pp. 1823-1832.
Martin A. Riedmiller and Heinrich Braun (1993). "A direct adaptive method for faster backpropaga- tion learning: the RPROP algorithm". In: ICNN, pp. 586-591.
Mher Safaryan, Filip Hanzely, and Peter Richtárik (2021). "Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization", In: NeurIPS, pp. 35688-25702.
George N. Saridis (1970). "Learning Applied to Successive Approximation Algorithms". In: IEEE
Transactions on Systems Science and Cybernetics 6.2, pp. 97-103.
Nicol N. Schraudolph (1999). "Local gain adaptation in stochastic gradient descent". In: ICANN, 569-574 vol.2.
Nicol N. Schraudolph, Douglas Aberdeen, and Jin Yu (2005). "Fast Online Policy Gradient Learning with SMD Gain Vector Adaptation". In: NeurIPS, pp. 1185-1192.
Naum Z. Shor (1977). "Cut-off method with space extension in convex programming problems". In: Cybernetics 13.1, pp. 94-96.
Fernando M. Silva and Luis B. Almeida (1990). "Acceleration techniques for the backpropagation algorithm". In: Neural Networks, pp. 110-119.
12

---

Richard S. Sutton (1992a). "A "Adapting Bias by Gradient Descent: An Incremental Version of Delta- Bar- Bar-Delta". In: Proceedings of the 10th National Conference on Artificial Intelligence, San Jose, CA, USA, July 12-16, 1992, pp. 171-176.
Richard S. Sutton (1992b). "Gain adaptation beats least squares". In: Proceedings of the 7th Yale workshop on adaptive and learning systems, 166.
Pinar Tüfekci (2014). "Prediction of full load electrical power output of a base load operated combined cycle power plant using machine learning methods". In: International Journal of Electrical Power & Energy Systems 60, pp. 126-140.
Sharan Vaswani, Frederik Kunstner, Issam Laradji, Si Yi Meng, Mark Schmidt, and Simon Lacoste-Julien (2020). Adaptive Gradient Methods Converge Faster with Over-Parameterization (and you can do a line-search). arXiv/2006.0665 06635.
Sharan Vaswani, Aaron Mishkin, Issam H. Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien (2019). "Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates". In: NewrlPS, pp. 3727-3740.
Pauli Virtanen, Raif Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors (2020). "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python". In: Nature Methods 17, pp. 261-272.
Rachel Ward, Xiaoxia Wu, and Léon Bottou (2019). "AdaGrad stepsizes: sharp convergence over nonconvex landscapes". In: ICML, pp. 6677-6686.
Philip Wolfe (1969). "Convergence conditions for ascent methods". In: SIAM review 11.2. pp. 226- 235.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoney (2021). "AdaHessian: An Adaptive Second Order Optimizer for Machine Learning.. In: AAA/ 35.12. pp. 10665-10673.
I--Cheng Yeh (1998). "Modeling of strength of high-performance concrete using artificial neural networks". In: Cement and Concrete Research 28.12, pp. 1797-1808.
David B. Yudin and Arkadi S. Nemirovski (1976). "Informational complexity and effective methods for the solution convex extremal problems". In: Ékonom. Mat. Metody 12.2, pp. 357-369.
Ciyou Zhu, Richard H. Byrd, Peihuang Lu, and Jorge Nocedal (1997). "Algorithm 778: L-BFGS-B: Fortran Subroutines for Large-Scale const-Constrained Optimization". In: ACM Transactions on Mathematical Software 23.4, pp. 550-560.
M. Zhu, John L. Nazareth, and Henry Wolkowiez (1999). "The Quasi-Cauchy Relation and Diagonal Updating". In: SIAM Journal on Optimization 9.4, pp. 1 119--1204.
13

---

Supplementary Material
Contents
A Full pseudocode of the algorithms
15
A.1
Subroutines for standard backtracking line-search
17
A.2
Separating hyperplanes used by multidimensional backtracking
17
A.3
Multidimensional backtracking using boxes
18
A.4
Multidimensional backtracking using ellipsoids Implementable pseudocode
19
A.5
21
Optimal preconditioners, valid preconditioners and competitive ratios
23
B.1
Defining optimal preconditioners without difieddiferenntiabiity strong-conn convextty
24
B.2 Valid and optimal preconditioners with singular matrices
24
B.3 Best competitive ratio achievable by the optimal preconditioner
25
C Separating hyperplanes
27
C.1 Stronger hyperplanes
27
C.2 Separating hyperplanes for invalid preconditioners
28
Cutting-plane methods
29
D.I Boxes
29
D.2 Axis-aligned ellipsoids
30
Experiments
36
E.1
Performance comparison
38
E.2 Additional results
38
Code available
14

---

A Full pseudocode of the algorithms
We first give with a generic version using the subroutines INITIALIZE, CANDIDATE and CUT, to be specialized for the backtracking line-search (Figure 8). multidimensional backtracking using boxes (Figure 10), and ellipsoids (Figure 11). The generic pseudocode written in terms of preconditioners, but also applies to the step-size version, which constrained to isotropic diagonal preconditioners, that is, preconditioners in the set {aI: a E R
consider looking for preconditioner
Although we write the pseudocode maintaining at each iteration abstract set of preconditioners S, the only information the algorithm needs to maintain on each iteration for the implementation the different cases is
For the line-search:
the current maximum step-size Omax defining the interval of valid step-sizes, [0, amax] such that the of preconditioners is S {al [0, 0max );
For multidimensional backtracking with boxes: the vector b defining the maximum corner of the box B(b) = {p R :p b} used define
the candidate diagonals preconditioners in the set S = (Diag(p) E B(b));
For multidimensional backtracking with ellipsoids:
the vector defining the axis-aligned ellipsoid {(a) = {p E RR. (p. Diag(a)p) S 1} used to define the candidate diagonal preconditioners in the set S = (Diag(p) p E(a)).
The pseudocode in Figure 6 updates (xe, Se) to (X411,441) each iteration, and ensures that either the function value decreases, f(x+11) < fxx)), or the volume decreases, Vol(S(41) < Vol(S.).
We give alternative pseudocode in Figure 7, which defines iterations updates the iterates X, that decrease the function value, and uses a while-loop to backtrack. Since it more closely resemble standard ways backtracking line-search is described, some reader may find it casier understand. We stress, however, that this still the same algorithm as Figure 6 but written differently.
The pseudocode in Figures 6-11, are expressed in modular form to highlight how the algorithm works and its similarity to a line-search. In Appendix A.5, we give a more directly implementable pseudocode of multidimensional backtracking in both box and ellipsoid variants solcly relying vector notation.
15

---

Figure 6: Generic pseudocode for the line-search or multidimensional backtracking, uses the subroutines INITIALIZE, CANDIDATE, CUT defined in the later sections.
Backtracking Preconditioner Search with Sets
Input:
A starting point X E R4:
A backtracking coefficient [0;
A scalar co > larger than the optimal preconditioner, i.e., such that col.
S. = INITIALIZECO)
Iterate for in 0,I,..,,
P. CANDIDATE(SS 7, Vx(()))
If f(x: - -.V(f(x)) Σ f(x)) (xx))
// //miio condition Equation (4)
(x141, = (x- (.)
Otherwise,
S.+1) = (x,, CUT(S,, x,, P.))
Output: XT
Figure 7: Alternative pseudocode for the line-search or multidimensional backtracking. Uses
while-loop for backtracking and only updates the iterates X, when they lead to progress.
Backtracking Preconditioner Search with Sets while-loop variant
Input:
A starting point Xp Rd.
A backtracking coefficient E [0, 1]:
A scalar co 0 larger than the best preconditioner, that is, P. I C...
Initialize the S INITIALIZE(CO)
Iterate for in 0, 1,..,,TT--TT -
6 CANDIDATE(S,, y, Vf(x;))
While f(x; (x S f(xx) - (xxx)
// //Armijo condition Equation (4)
+ CUT(S, P,)
P. + CANDIDATE(S, vf((x))
X X - P.Vf(xx)
Output: Xy
16

---

A.1 Subroutines for standard backtracking line-search
Implementation the subroutines for standard backtracking line-search. Although written in terms of sets, the algorithm only needs to maintain the maximum step-size in the interval [0, amax at each iteration. The corresponding preconditioners are the matrices {aI a E [0, amax]]
Figure 8: Specialization of the subroutines for the backtracking line-search
INITIALIZE(CO)
Input: A scaling co larger than the optimum step-size, that is, such that 1/L S co.
Output:
Set of preconditioners S = {al: a E [0, col}.
CANDIDATE(S,
Input:
Set of scalar preconditioners S [al: [0, 0max]]: Backtracking coefficient y E [0, 1];
Current iterate x Rd
//Not used for the step-size version.
Output:
Preconditioner 70mmax
CUT(S, P)
Input:
Set of scalar preconditioners S = {aI E [0, Oraax]] Current iterate x E IR;; Preconditioner P I that failed the Armijo condition at x.
//Not used for the step-size version.
Output: Set of scalar preconditioners with reduced interval, S {al: a E [0, apad)) }
A.2 Separating hyperplanes used by multidimenssonal backtracking
Both versions multidimensional backtracking need direction to update the of precondi- tioners in the CUT subroutine. We define the subroutine SEPARATiNGHHVPERPAAN in Figure 9, The description of the separating hyperplane and their properties can be found in Section and Appendix C.
Figure 9: Separating hyperplane used by both variants of multidimenssinnl backtracking.
SEPARATTING/YPPPPPLANNEG xx P) for diagonal preconditioners
Input:
Current iterate x E Rd:;
Diagonal preconditioner P Diag(p) that failed the Armijo condition x.
= x - PVf(x)
g Vx(x)
g Vf(xt)
(5g - g Og
//Separating hyperplane from Proposition 4.2
f(x) -xxx)
(g, Pg
Output: u = max (o,x(v element-wise
// Stronger hyperplane from Proposition 4.3
17

---

A.3 Multidimensional backtracking using boxes
The implementation of multidimensional backtracking with boxes only needs to maintain a vector b, representing the maximum step-size for each coordinate that has not been ruled out, in the box (()). The associated sets of preconditioners are
B(b) {p Rg p - b),
== (Diag(p) B(b)).
The description of boxes and the theoretical guarantees when using them in multidimensional backtracking be found in Section 5 and Appendix D.1. The subroutines used by the algorithm with boxes are:
INITIALIZE: initializes b to cg so that the diagonal preconditioner cp is in So.
CANDIDATE: backtracks from the largest diagonal in ((b). returning Diag(b).
SEPARATINGHHPEEPP.LEE computes the vector u defining the half-space of invalid pre- conditioners Hz(u)) obtained when the preconditioner P fails the Armijo condition at x as described in Proposition 4.2 and Proposition 4.3.
CUT: returns the minimum volume box B(b+) containing the intersection B(b) 0 Hg(u).
Figure 10: Specialization of the subroutines for multidimensional backtracking with boxes
INITIALIZE(cO)
Input:
A scalar co such that coI larger than the optimal diagonal preconditioner, i.c., 3 col.
Output:
Set (Diag(p): E B(b)) with ((b) {p E R p S b} where b co
CANDIDATE(S,,,.5
Input:
Set of preconditioners S (Diag(p): B(b)) with B(b) = (p Rd < b); Backtracking coefficient 7 E [0, 1];
Current iterate Rdd.
//Not used for the box version.
Output:
Preconditioner y Diag(b)
CUT(S,
Input:
Set of preconditioners S (Diag(p): B(b)) with B(b) = (p IRd :p S b); Backtracking coefficient 7 E [0, 1];
Preconditioner Poad that failed the Armijo condition at
SUPARATINGHYPEEPPAEENN Pbwd) b = max(b, 1/u}
//Minimum volume box B(b*) containing B(b) Hz(u)
Output: Set diagonal preconditioners = (Diag(p): : E BBb+)):
18

---

A.4 Multidimensional backtracking using ellipsoids
The implementation only needs to maintain a vector a representing the diagonal matrix defining the (centered, axis ailiined)) ellipsoid ((a) and the associated set of preconditioners S given
{aa) {p E R (p, Diag(a)p) S 1}.
S = (Dia(()) p E {a))).
The description of the ellipsoids and their properties can be found in Section 5 and Appendix D.2. The subroutines used by the algorithm with boxes are:
INITIALIZE: initializes to (?/cc)) so that col E E(a), implying the diagonal precondi- tioner coI in S.
CANDIDATE: backtracks from the diagonal preconditioner in S that maximizes the gradient norm. Let (a) be the set of candidate diagonals and define A Diag(a). The subroutine returns y max, where
P max
arg max V (x)) PES
Writing this in terms of the diagonal vector Pmax = diag(P mmxx) yields
arg max (x) lisgg())) Diag(p)*
Pmax
PEε(a)
||D|A S A Vf(x(( VV[()]l
arg max (VS(()?
P
where Vf(x)² Vx(x) O Vx(x).
SEPARATINGHYPERPP.NN computes the vector u defining the half-space of invalid pre- conditioners H- (u) obtained when the preconditioner P fails the Armijo condition at x as described in Proposition 4.2 and Proposition 4.3.
CUT: returns an ellipsoid & (a+t) containing the intersection of (H) (u) with guaranteed volume decrease from E()). As there no closed-for form solution for the minimum volume ellipsoid, we set at convex combination between the original ellipsoid {(a) and the minimum volume axis-aligned ellipsoid containing Hz (u), given by {uu)). that is,
8 dd 1
= Aa
A)u²,
where
X = 7 -
and
l : || |
(10)
where A = diag a). Although the above choice of À has guaranteed volume decrease, can find better value of X by solving the minimum volume ellipsoid as function numerically, Namely, approximating
X arg min log(det(A Diag((a)) (1 A) Diag(u?)))
0<λ<ι
In our experiments, we start with as in (10) and, starting from it, we solve the above minimization problem numerically using L-BFGS-B (Zhu al., 1997) in SciPy (Virtamen al., 2020). This preserves the theoretical guarantee while improving empirical performance.
19

---

Figure 11: Specialization of the subroutines for multidimensional backtracking with ellipsoids
INITIALIZE(Co)
A scalar > 0 such that CoI is larger than the optimal diagonal preconditioner, i.e., P, 3 CoI. Input:
Output: S = (Diag(p): -p E(a)) with E(a) = {p E Rg (p, Diag(a)p) - 1] for _
deg
CANDIDATE(S,
Input:
A set S = (Diag(p) E {(a) where E(a) = {p Rg. (p. Diag(()()) & 1}, and
a E TRd
Backtracking coefficient y E [0, 1];
Current iterate x E Rd.
d = Vx(x) VS(x)
A -d
//Where A = Diag(a)
max
||d|| A-1
Output: Preconditioner y Diag (Pmax)
CUT(S, x, P)
Input:
A set S (Diag(p): P E E(a)), where {(a) {p TRg. (p. Diag(a)p) S 1). and
a E RR..:
Current iterate Rdd; Preconditioner Pmud that failed the Armijo condition at x.
SERARATTINGHYPPRRRANNN.C. Phat) [ul] 2 d-1 à 2-1
(or numerically solve X = arg mino<e<1 (og(det(cDiag(C) + (1 c) Diag(u?)))
a Xa (1 -)u
//Approx. min. volume ellipsoid E(a+) containing E(a) (u)
Output: The set S (Diag(p) p E(at)}
20

---

A.5 Implementable pseudocode
The pseudocode Figures 6-11 are expressed a modular form to highlight how the algorithm works and its similarity to line-search. In this section, give more directly implementable pseudocode of multidimensional backtracking, in both the box and ellipsoid variants, using mostly vector notation. Scalar operations on vectors such u/a, Vu, u² are understood to be taken element-wise
Multidimennional backtracking using boxes
Direct implementation
Input:
Function optimize f: Rd R Starting point Xn E I A scalar for the scale of initial set of preconditioners co > Backtracking coefficient y < 1/a.
= Col
//Initialize box
Iterate for in 0, I,...
xb
//Get candidate preconditioner
= vf(x:) x = XG Pi o og
//Get candidate point
While f(x²t) ) > f(x:) - 2 (g) p.)
//Ariijo condition fails
g/ fx(x;t)
//Get next gradient to compute
d = { 8: gr
//the separating hyperplane direction,
fxx) - f(x;) P..
//the normalization constant, //and truncate it
u, = max(d, /d//c 0} (element-wise)
b = 1/ max(1/b, } (element-wise)
//Find new minimum volume box. //(oc-free min(b, 1/u3)
p: = =>=bb
//Pick next candidate preconditioner
x = Xx - P: o g:
//and next candidate point
X:+1 x
// Accept new point
Output: X;
21

---

Multidimensional backtracking using ellipsoids
Direct implementation
Input:
Function optimize f: R : Starting point X E IR'd; A scalar for the scale of initial of preconditioners co > Backtracking coefficient < 1/Va
1/(dc))
//Initiaiize ellipsoid
Iterate for in 0, I,...
V (x:) Pt gi /a (element-wise)
//Get candidate preconditioner //normalize it
Pt /P:/ /all (element-wise)
x x. P. o gr
//Get candiddte point
While f(x!' > f(xi) (g). PP)
// //Ariijo condition fails
g: vf(x;)) )
//Get next gradient to compute
d, (5g. gi) o ge
//the separating hyperplane direction,
6, fxx,) - [(x;" - g o Pt. g
//the normalization constant, //and truncate it
u, max /d./c,, 0} (clement-wise)
take
((d-1) where (u², 1/a) d(e-1)
//Approx. min, vol. new ellipsoid
or
find À by numerically minimizing ((A) where (()) Σí log(Aa(i] (t?))
//Find better approximation of min. //of volume of new ellipsoid
a Aa + X)ur
//New ellipsoid
P: g// /a (clement-wise)
//Get new candidate preconditioner, //normalized,
p. 7P:/ g? / (element-wise)
x = X
P: g:
//and new candidate point
X,41 = x
Acceptp new point
Output: X;
22

---

Function
Valld Preconditioners
2-
2.0-
M/
1.5-
2 0-
6' 1.2-
0.4
0.0
Figure 12: Set of valid diagonal preconditioners (step-sizes P1 and p2) for the quadratic in Equa-
tion (11). Preconditioned gradient descent larger step-size in the first coordinate.
B Optimal preconditioners, valid preconditioners and competitive ratios
In Section 2, we defined the optimal preconditioner as the preconditioner that is the best overall approximation to the inverse Hessian. Formally, we define the optimal diagonal preconditioner P, as
P. == arg min such that 1 =p- p-1 for all x.
One way to interpret this definition is that P.- is the tightest diagonal approximation f²
We remark that we not need f be daronglyy)connee to define the theoretically optimal step-size of 1/r. for gradient descent. Thus, one may wonder why we need strong-convexity (although we relax this to requiring f to be PL Appendix B.1) to define what an optimal preconditioner is in (I).
The main difference between the scalar step-size and per-coordinate step-sizes settings is whether the "largest" step-size or preconditioner is well-defined. In the scalar setting, the largest step-size that guaranteed to lead to progress everywhere (i.e., step-size that satisfies the Armijo condition (3) for all x) is well-defined and equal a, = 1/2 for L-smooth function f. Equivalently,
11) sup (V3 XER*
= sup 0: V2
where Amax (V2 (x)( is the largest eigenvalue of fxx... But in the case of preconditioners, the ordering on positive definite matrices is not complete, so there is no single "largest" preconditioner P that satisfies fxf < P-1. We can still describe "good" preconditioners, that are guaranteed to satisfy the Armijo condition (Equation (4)) everywhere; this is the notion valid preconditioners defined in Definition 4.1, which in set notation is V = {P > V2f(x) 3 P-1}. With this definition, we can consider the set of valid preconditioners P for which there are no bigger valid preconditioners, that is, P (P V A'' E V preconditioners, that is, distinct matrices A, B E P that neither A > B nor A < B hold.
P < P'). However, P contains incomparable
Let us look at example with quadratic function (illustrated in Figure 12)
.5
.1
f(x) = 2 (x, Ax)
with Hessian
A
(11)
11
1.0
There are many preconditioners that are valid, for example using the per-coordinate step-sizes
.91
0 P
2.0 0 0.0
0..0 0
1.75
0
PL ~
P2
P
.1
0
1.0
O
0.87
The preconditioner Pz corresponds the I/L step-size, P1 and Pa take the largest possible step- size in each coordinate, and P. is the optimal preconditioner according to Equation (1). Those preconditioners are not comparable to each other, as neither PA x nor P. < P hold. Instead of looking at the matrices themselves, we use in (1) the condition number of P ( a measure of quality P. This allows for a well-defined optimal preconditioner as this condition number can be maximized.
as
Upp to invertibility issues which we address in the next subscction. "Our definition is slightly different, but both notions equivalent for positive definite P.
23

---

B.1 Defining optimal preconditioners without twice-diiferrentiabblyy or strong-convexity
Although we used pific-differeetiabiltty of f to define the optimal preconditioner, this is not necessary. If f is not eiie-diifereentable but still strongly-conye the defimition in Equation (1) can be replaced by Equation (2), as finding the P-norm under which the function is most strongly-convex.
P.
arg min P=O, diagonal
{
| f(y) f(x)- (Vf(x)) S $ -
f(y) f(x) (Vf().. x),
such that
for all x,y.
To avoid strong-convexity, we can instead use the PL inequality. A function f is P-PL if
1 2
| 2 f(x) s(x.)-
(12)
This property is implied by j--troong convexity. We refer to the work of Karimi et al. (2016) for the properties of PL functions and its relation to other assumptions. To adapt Equation (12) to our results, we can measure the PL constant in the norm induced by P, and say that f is μ-PL in Il-Ipp p if
11 1
f(x) - f(x.).
(13)
# 2
We use this inequality in the convergence proof in Proposition 3.2 since it is a consequence of strong- croong-convexity.. As this property is the only property of coong-conyyxity needed for our results, we can adapt our results to be competitive with the optimal preconditioner defined using the PL inequality, using the definition
P.
arg min PHO, diagonal
(14)
1 [V) f(x) - (Vf(x),y b -x| for all x.
for all
such that
If ʃ is μoPL and L-smooth, Equation (14) has a feasible solution at P = 1/r. number x = 4/n- The constraint based on the μ--L condition in Equation (14) weaker than the definition using strong-convexity. as strong-convexity implies the PL inequality. The optimal preconditioner defined using the PL inequality (14) might thus achieve lower condition number than the one using strong- convexity (1). For example, the quadratic fxx = (1/2)x,, Ax) with positive semi-definite A is not strongly convex if the smallest eigenvalue of A is O. The optimal preconditioner in Equation (1) is ill-defined (or has condition number K. = oo). In contrast, the optimal preconditioner defined using the PL inequality in Equation (14) has finite condition number, as P 1/LI is feasible solution with condition number L/xt..(A) where A (A) is the smallest non-zero eigenvalue of A. As our proofs only use the properties guaranteed by Equation (14), our results also apply to PL. functions.
B.2 Valid and optimal preconditioners with singular matrices
In the main text, we defined valid preconditioners (Definition 4.1) only for positive definite matrices for ease of presentation. The notion of valid preconditioners can be extended to general positive semidefinite matrices. In the diagonal case, the convention 1/0- + is a useful mental model but can cause inconsistencies (such as xo 0). To extend the notion of valid preconditioners to general positive semidefinite matrices, we can use the definition
Definition B.1. A preconditioner P = 0 is valid (/P1//2' 3 T for all x E TRd
The above is well-defined for all positive semidefinite matrices. An alternative to arrive at a definition closer to Definition 4.1 is to consider the projection matrix III onto the image of P. given by Tp = (P1/22t where pt is the Moore-Penrose pseudo-inverse of P. Using that, one can show that P valid (according to Definition B. if and only if
Hp V fx) Pl for all x Rd.
An example of a valid preconditioner that covered by Definition B.1 but not 4.1 is the all-zeroes matrix. Definition B.1 can seamlessly replace 4.1, and all the results follow similarly. Moreover, notice that the optimization problem defining the optimal preconditioner (1) may not attain minima on positive definite matrices when f is not strongly convex. In this case, can define an optimal
24

---

Function
Valid Preconditioners
21
1.25
14
1,20
0.75
2 0
0.00
Figure 13: Set of valid diagonal preconditioners (step-sizes P1 and p2) for the quadratic in Equa- tion (15). The set of valid preconditioners (Definition 4.1) is the white region in the right figure.
preconditioner as a limit point of sequence that attains in the limit the value in (1) by replacing the minimum with an infimum. In this case, an optimal preconditioner may be singular, but the results in the main body also follow seamlessly using this definition. We decided to restrict our attention to non-singular preconditioners in the main paper for ease of exposition, since when strongly-convex, an optimal preconditioner is always non-singular.
B.3 Best competitive ratio achievable by the optimal preconditioner
In Section we mentioned that the optimal preconditioner P. could be only 1/a-competitive. In fact, the competitive ratio of P. can be arbitrarily bad. The reason for this is that the competitive ratio does not compare against P.,, but rather against any P in the set S of potentially valid preconditioners. Moreover, this definition only takes into account the norm [f | fixed x, while the optimal preconditioner needs to have large norm for all x.
For example, consider the scalar step-size case. If our current interval of candidate step-sizes to try is S [0, 1] but the optimal step-size a, is small, let us say a, 1/10, then a, only 1/10-competitive in S. The motivation for this definition of competitive ratio that cannot check whether is large compared to a, (as we do not know a.) but we can more easily ensure that a candidate step-size a is 1/2 1/2-competitive in [0, 1)).
7-competitive in S (for example
In the previous example, the bad competitive ratio of a. in was mostly due to the fact that was large and that, for some step sizes larger than a, could satisfy the Armijo condition (3). Even if a, is globally optimal, we could make more progress by using larger step-size they were to be accepted, and we have not yet ruled out those step-sizes. However, S shrinks, it may eventually converge to the interval [0, iJ. which case the optimal step-size a. would be 1-competitive.
In high dimensions however, the optimal preconditioner can have competitive ratio of 1/a even when comparing only against valid preconditioners. 5 This is because the competitive ratio is defined using the P-norm of the gradient, and we need to take the direction of the gradient into account. For example, consider the quadratic function (illustrated Figure 13)
1
f(x) = 2
(x, Ax)
where
A
(15)
with cigenvalues {2,0) as A = |-1, 1]. The following three preconditioners are all valid:
1 0
[0 0 0
1/2
P
P:
1 and
P.
0
1/2
The preconditioner P, takes the largest possible step-size in the first coordinate and ignores the second, while P. does the opposite. They not good global preconditioners, each ignores one coordinate. Yet, they can make much more progress (i.e., the objective value may decrease more) than the optimal preconditioner P. the gradient is very skewed towards one coordinate. This implies that
'How small the set St can get is bounded by construction. The cutting plane procedure in Sections and only remove invalid preconditioners. The valid preconditioners contained in the initial set So will always be in S., along with possibly preconditioners that have not been deemed invalid over the course of optimization.
25

---

P. may be only 1/2-compeiitive in (P1. P2) for some since
if Vf
then
[[V/(x)) =, [V = 0, [V =1/2,
and Vf)
then
[V/(()]
[V = 1, [V = 1/2
The preconditioner P. is still better choice globally (i.e, for all x) since it ensures optimal worst- case linear rate in preconditioned gradient descent. But there better preconditioners that depend on the current gradient. We exploit this in the ellipsoid variant of multidimensional backtracking improve our competitive ratio. We backtrack from the preconditioner that maximizes the local progress guarantees ensure l/va competitive ratio, while ensuring volume shrinkage of the set of candidate preconditioners when we call CUT, the preconditioner fails the Armijo condition.
26

---

C Separating hyperplanes
In this section, prove Propositions 4.2 and 4.3 on existence and strengthening of separating hyperplanes for valid preconditioners.
General idea. Let us start with summary of the separating hyperplanes used search for good preconditioners as discussed in Sections and 4. The goal of the separating hyperplanes to give us ways to shrink the initial of potential preconditioners S to narrow in valid preconditioners using the cutting-plane methods in Section 5. At each iteration we are looking for preconditioners P that satisfy the Armijo condition at x given by
f(x fV)()) f(x) 1V
If P fails the Armijo condition, we conclude that P is invalid. To obtain more information, we look the condition as a function of the (diagonal of the) preconditioner, and define the gap function at x,
(p)) f(x Diag(p)Vf(x)) f(x) 2 (x) Diag(p)
Vp E R
Then, h(p) < 0 P (p) satisfies the Armijo condition and h(p) > 0 otherwise. Any preconditioner Diag(q) such that h(q) > 0 guaranteed to be invalid. We can use the gradient of h at p and convexity to find half-space such that one side contains only preconditioners with h(p) > 0. In this section, we show how to construct such half-space, and strengthen them using the partial order matrices, which is needed ensure volume shrinkage of our cutting plane methods.
C.1 Stronger hyperplanes
In the main body we presented the strengthening of separating hyperplanes via truncation (Proposi- tion 4.3) after the result of existence of separating hyperplanes (Proposition 4.2). Here, we prove more general lemma on strengthening half-spaces of invalid preconditioners first, as it is useful in simplifying the proof of Proposition 4.2. Proposition 4.3 follows directly from the following lemma.
Lemma C.1. Let Hy be the intersection of the non-negative orthant R and the half-space defined by the vector v E IR and coefficient a >
Hv,a {p E K (v, > a).
Define u = maxxvv00 and let Hu.o be defined similarly as above, that is,
Ha,a == (p E R$. (u. > a).
Hf only contains diagonals of invalid preconditioners, that is, Diag(p) is invalid for any E Hy, Then Hv Hu,a and Hu,a only contains diagonals of invalid preconditioners.
Proof. Inclusion Hv, S. Hu,a. We have that (p, v) > a implies (p, u) > for any p E Rg. since
(v.p) = 1: v
Σ vipl +
Σ 4: v/1
vippli S
Σ
viip[[]
Σ
u = (u, p).
1: v
Hu. only contains invalid diagonals. Let Pu E Hu.a. We can show that Diag(Pu) is invalid by finding pv E Hy.a such that Diag(pv) = Diag(Pul Since (iag(pv) is invalid by assumption, this would imply that Diag(pul is also invalid. To find pv,
truncate the entries of Pu as
P P
if vf 2 0 otherwise,
Vi (l.....d).
Then Pv Hv.a since (u, Pu) (u, pv) (V, and Diag(pa) > Diag(pv), as desired.
'One may worry that our original definition valid preconditioners has a division by if any entry of the preconditioner is 0 as preconditioner is valid if fx) < P (Definition 4.1). It is enough to use the convention that 1/0- = +oo, although this might lead to inconsistencies. In Appendix B.2 we discuss a more general definition without the of infinities.
27

---

C.2 Separating hyperplanes for invalid preconditioners We are now position to prove Proposition 4.2.
Proof of Proposition 4.2. Throughout the proof, we shall denote by P the matrix Diag(p). If f is convex, then h also is since the map p E IR + f(x (x)( is the composition of an affine transformation and convex function, and [
(x), (fxx())V((x)) is linear in p.
Convexity of h yields the inequality
h(p) 2 h(q) (Vh(g). q), Vp E RS
This implies that if p is such that h(q) + (Vh(g), P q) > 0. then h(p) > 0. which implies that Diag(p) is an invalid preconditioner. Rearranging conclude that Diag(p) is invalid for all p in the set in (5), i.e., in
{pe R (Vh(q).p) (Vh(g). h(q))
(16)
We express the above half-space
Vh(g)
Hz(v) (p: (p.v) 13 for
-)
Yet, for H₂ (v) to be equivalent to the set in (16) or even to be well-defined, we need to ensure (Vh(q).q) q) h((q) > To see that this holds, note first that by convexity of h and that fact that
h(0)) = 0 we have
A(0) h(q) + (Vh(q), q) (Vh(g), - 0) h(q) 2 -h(0) =0
To show that the last inequality is strict, assume that (Vh(q), (
((()) = for the sake of contradiction. By Lemma C.1, the half-space H = {p R ([Vh(x) +. P) > 0} contains max(Vh(x) Vh(x),00 0} entry wise. However,
only diagonals of invalid preconditioners, where [Vh(x)]_ = max
(1/1)1 H. [Vh(x)]+ 2 0 and should be invalid, which is contradiction since is L-smooth and 1/rII is valid. Therefore, (Vh(g), q - 0) - -((g) > 0.
Finally, we can write in terms of f and Q. To do first define x x QVf(x), and the gradients different points by g == (x()) and g Vf(xt). Then, by the chain-rule,
Vh(q) = - Vf(x QVf(x)) o Vf(x) + Vf(x) Vf(x) = g ogg 2
2
which implies
(h(()).)) hh(q)= = =gg Qg) 2 gg Qg) f(x*) + f(x) + gg. Qg)
= f(x) (g* Qg) f(xt)
Plugging these equations in the definition of v yields
Vh(q)
(gg g
(V((g).)) - h(q) f(x) - (g* Qg) f(xt)
Remark on assumptions of Proposition 4.2. One may have noticed that we never use the assump- tion that Q fails the Armijo condition (i.e., that h(q) 0) in the proof of the proposition. In fact, the proposition holds for any q E R8 However, and crucially for our application, we have that q is in the half-space H.s (u) of invalid diagonals from Proposition 4.2. multidimensional backtracking. is the diagonal of a preconditioner Diag( q) that failed the Armijo condition h(q) > 0. Since is close to the origin in multidimensional backtracking, we can ensure the half-space H. (u) contains significant portion of our current set of candidate preconditioners, leading to significant shrinkage of the set of candidate preconditioners whenever CUT is invoked.
28

---

D Cutting-plane methods
D.1
Boxes
Given box B(b) for some b E RSo and vector E RR our cutting plane method needs to find box B(b+) that contains B(b) n My (u) which, hopefully, has smaller volume than (b)).
The next lemma gives formula for the minimum volume box for any u, which is used in the main text to define CUT in Equation (7), Moreover, we show that if the half-space H> (u) is close enough to the origin (since otherwise we might have b- b). then we have a significant volume decrease.
Lemma D.I. Lei b E Rg. and q E B(b). Les R Then the box B(b+) with minimum volume that contains B(b) n Hg (u) is given by (using the convention that 1/uli] = +o0 if u[i] 0)
Vi (1....,, d), Moreover, if (4/2) . b is excluded by the half-space, that is, b E (u),), then Vol(B(bt)) 5 (4/(+1)) Vol(B(bb)).
b [ == min min(b 1/uli,
(17)
Proof. Formula for bt. Finding the minimum volume box containing BBb) n Hg (u),
b+ = arg min Vol(B(c)) s.t. B(b) n Hg(u) C B(c),
cER
is equivalent to finding the solution to the following optimization problem:
arg min b
II
cli]
s.t.
max pE
plil S c[ij] for each i {L....,d}.
CERd
As the constraints separate over the coordinates, the minimization can be done for each coordinate separately. As the function is increasing in c(i), the minimum is achieved by making all the constraints tight, which giver the formula for b+ in the statement of the lemma.
Volume decrease. Let us prove the second part of the statement. Thus, assume for the remainder of the proof that (1/2d) b E H- (u). We first show that Vol(B(b )) I (4/(+11) Vol(B(( if we assume that the update from (bb) to B(b+) shrinks the box in only one coordinate, i.e.,
I= {ie [d:
b[i] > 1/uis] {i [d: b [+] * blil} has exactly one element.
(18)
Assume the above holds and I = {j}. Then, as (1/2d) b E H (u) implies (u, (1/2a)b) > 1,
1 << (u, b)) < 2d [u [bbjاbb + +d-1) = (d + n S blil.
This together with the fact that b x [i] = b[i] for all i * and b b+]] = 1/ubl yields
Vol(B(b+)) II b M ufil
II blq <
1 d
II bll
1 d+1 Vol(B(b)).
To complete the proof, only need to show we may assume (18) holds. Assume the opposite, that is, that there are two distinct coordinates that shrink from b+ to b. We will show that the volume shrinks more, meaning the above bound also applies. Formally, assume there are j, k I that are distinct. For this part, it will be useful to denote by b (u) the point defined in Equation (17) for given vector We will show while maintaining the property (1/2))b E Hs (u') and such that b (u') [t]] A b[i] for all i E I (5). which makes (18) follow by induction. Indeed, define u' E IRd by
construct u' IRg. such that Vol(b (o()) S Vol(b((u')
bb
bb] ). (19)
1
n' [ == u for & kj,
n' = bbi " and u [k] [[a]]
b(k]]
First, note that (1/2)) b E Hy (u') since
(u' b) = (ui]( - u(ii) + (u'(A) - b()))(())
= -bbi
1
uli]]
b [bp
b )) [[[]
)b[k]
b[j]
b
29

---

and, thus, 1 < (u, (122))b (u', (1/2))b) Let us now show that Vol(B(b*(u)) -
Vol(B(b (u') ()) Since b* b* [u)li] b* b²() for & {j. k) we have Vol(BB(b (+) [u]
Vol(B(b+(u))) b+(''Db]
b+(''
min(bb]),
min[b(k], 4/(())
min(b)))
min b k). (1)
V/ubi
1/u[k]
(since j, k E I and by (19))
bbil
1/u([s]
bbi
u[k]
+
uli]
b]
1
[M]]]
b b]k
bbj
[b[k)u[k + b[j]u[ي] 1).
[[k]b[[]
To get that Vol(b (u)) Vol(b (u))). show that last line is bounded by < 1. Using the and = b[k]] [A]] we want to show that
substitution a = b 1
a + B
aB B+1 = - 1033)13-11 0.
aB
This holds if a >> 1 and B > 1, is implied by j. k E I since = bljjul > 1 and B b
b [ 1. simple induction shows we may assume (18) holds. To see that (a + - o < 1, note that L
Equipped with the above lemma, we are in position to prove Theorem 5.1.
Proof of Theorem 5.1. Property (a), holds by induction because, for any u, used call CUT, we have P H.g (u,) since P is valid and since by Proposition 4.2 the half-space H (u,) contains only diagonals of invalid preconditioners. For (b), fix E (1,.... T) and recall that in this case we have S, Diag (P): p B(b;)) and P, (1/2a) Diag( The competitive ratio of 1/2d follows since Diag(b,) (b,) is the preconditioner that maximizes [x+ Ip for P E B(b.). Finally, for (c) by Lemma D.1 we have that every call to CUT makes the volume of the set decrease by 1/c 1/(d+1).
Moreover, one can easily verify that b 2 min(//2, bofi] for all i f1.....,d d} since B((12)11 contains only diagonals of valid preconditioners. Therefore, for b [i] = min(1/t. bo[i]] the volume of B(b;) cannot be smaller than B(bmin) for all iteration t. Therefore, the number of times CUT is invoked is more than
Vol( Vol()(bb))
boli] bmin [i]
logg
loge
II
loga ((Iboolloll. D) dl d (Ilolllo
Vol(B()))in))
as desired.
D.2 Axis-aligned ellipsoids
We now analyze the cutting-plane method using axis-aligned ellipsoids. Interestingly, the results that we prove in this sections are connected to some of the results from Goemans et al. (2009) via polarity theory. We defer a discussion on this connection to the end of this section.
Different from the main body, it will be helpful for the analysis of the method and proofs of the results to not restrict ellipsoids to the non-negative orthant, as was done in the main text for ease of exposition. For any symmetric positive definite matrix A Rdxd define the ellipsoid given by A by
E(A) == (x E Rdd: (x, Ax) S 1}.
When A is diagonal, say that E(A) ) is axis-aligned. Moreover, may slightly overload notation by defining {(a) := (Diag(()).
General ellipsoids. Although we are ultimately interested in working solely with ellipsoids defined by diagonal matrices, we will start by looking at more general ellipsoids, and then exploit symmetry our case to derive the result in Lemma 5.2. We start with an ellipsoid E(A) where A a positive definite matrix. Then, given a vector E Idd are interested in finding an ellipsoid the intersection
30

---

(AL
E(A)
{ o u
Figure 14: Illustration of the ellipsoids in Theorem D.2 in the left. In the right an illustration of the symmetrized intersection of halfspaces S(u) used in the proof of Lemma 5.2 together with the ellipsoid E (u @ u) used in the convex combination in the lemma.
of (A) with the half-spaces defined by u and -u that contain the origin, that is, the set
E(A) n (x e R²: (x, u) 1) {x g -xxx, u) 1} = E R (xx, u> < 1}.
The following theorem shows how to find an ellipsoid that contains the above intersection, and how to guarantee its volume is smaller than (A) if u is large enough. Interestingly, note that
(x RRd (x, u < 1} (x E Rd ((x, u})² <1} = =((u²))
The set ((u 1) is degenerate ellipsoid, in the sense that it is compact set, and any p orthogonal to u contained E(mu) Still, the next theorem shows how to find a convex combination {(A) and E C(uuT )auu))wiih which --whchh always contains E(A) n {(uu)) ((uu))-that than E(A) if is large enough. The following result can be (2009, Lemma 2).
that is guaranteed to have volume smaller
the polar result of Goemans et al.
Theorem D.2. Let A E Redxd be positive definite and let u E Rd. Let X E (0, 1) and define
L(A, u) = XA + (1 A)uuT
Then E(A) ( (EL((A, u)) and
A V x V
Vol(E(T(A, u))) In particular, ifl ||ul]2-1 and
2) Xa VoI(E(A))
L d-1
(20)
d
1-1¹
then X E (0, and Vol(E(I(AA = vu( Vol(E(A)) where
1
d-1
d
d/2
(d-1)/2
vu(u)=
V Ad 8-1
i
d
d-1
E (0,
(21)
Proof. First, note that for any p E(A) n E(uu))) and any X (0, we have
(p. L(A u)p) Ap. + A) u) s A + (1-X)=1 =
Thus, E(L(A, uj) C E(A) n T(uu)). For the volume decrease, recall that for ellipsoids E(A) we have Vol(E(A)) VetrA))(A) where Va2 is the volume of the unit sphere in Rd. By the matrix- determinant lemma, we have
1 (u, Au,A-'u) -u) dec(AA) = (1+ 1-2 e) det(AA).
det(L(A, = 1+ X
31

---

Therefore,
1
x
Vol(E(L(A.u)) Finally, for À defined as in (20) we have
dd VVo(E(A))
V A (1 2) - 2a VVo(E(A)).
V
(1 1-2 2)
1 1 A 1+ A -1=++ E(d 10111 1)) d(e - 1)
=1+ (d(e-1) 1) ((dd-)
-
1 e
d(t - 1) E(d ((d-1) 1)
{(d ( 1)
=1+ d(e 1) [(d
t-d f-1
.
1 d-1 d-1'
{(d - 1)
which yields the desired formula for va(u).
On the norm of u. The above theorem has a requirement on the norm of the vector u that defines the half-space H. (u). However, in our cutting plane method we obtain from Proposition 4.2 and Proposition 4.3, which do not have any guarantees on the norm of u explicitly. Crucially, at any given iteration t of multidimensionall backtracking with ellipsoids,
select candidate preconditioner P. = Diag(P:) such that |P A = 1/v2a. Then, if it fails the Armijo condition in (4) and u, is as given by Proposition 4.2, then we have P. E H2 (uz), that is, the separating hyperplane excludes Pt- As we will show, this implies that ||ul|a-1 is large.
Lemma D.3. Let A E Raxd be positive definite and p E IRg be such that ||pl| S Y for some O. Let u E I2 be such that p E (u)) Then ||ul] A-1 > 1/7.
Proof. For the sake of contradiction, assume ||uil 1 S 1/7. Then ||u|| - -lPlIA S 1. Thus, by the Cauchy- Saach-SSchwartz inequality,
(u, p) = AA AA-1/2
1/2 u, A p)) - 1/ || 1/2 |/ ||u|| ||
|plAA S.
This is contradiction since p H- (u) and, therefore, (u, p) >
On the volume decrease. Although the formula va(u) in Equation (21) can be hard to interpret, we show simple bound when ||u||3 A 2 2d.
Lemma D.4. Let A Raxd be positive definite matrix and Rdd be such that ||lll > For c = d/L E (0, we have va(u)= S et-et-e, where va is defined as in (21). In particular, if
||ul]2 > d, then vu(u)= I V2//2.
Proof. Define f = ||1| 10lla-11 > and c = d/2 E (0, 1). Then,
8 (d-1)
d d L 1
(d-1)
=c (
d/c 1
(d-1)
va(u)² =
d- I
d
i d-1
d c (d-1)
(1
1-c
(d-1)
ct.et-c
d
=c
d-
where the last inequality follows since + x. I et for all x E R. In particular, note that c E (0, 1) + --e-e is increasing since the derivative of the mapping is positive on (0, 1). Thus, if ||lla 2d, then and e e--c < (1/2)- e/22
Exploiting symmetry. Let us now exploit symmetry to avoid using non-diagonal matrices in our ellipsoids. We use the notion of axis-aligned sets in the next few results. A set X C Idd is axis-aligned if for any point p E X, the reflections of p along the axes are also contained in X. Formally, for any s E {=1]d, we have that if p E X. then Diag(s) p E X. Furthermore, with slight abuse of notation define Diag ()) Diag diag(A)) ()). That is, Diag (A) is the diagonal matrix whose diagonal entries match those of A. The idea is that the set (p Rg. Diag(p) is valid) of diagonals of valid preconditioners contained in the neg-tege orthant. Yet, we can extend it by reflecting it over each of the axes. Although this may seem counter-intuitive, this translates the structure of our problem
32

---

into symmetry among all orthant, and this can be exploited elegantly. Formally, the set of diagonals of valid preconditioners reflected over each axis is given by set
P P= (pc E _ Diag((p)) is valid],
where ppl is the entry-wise absolute value of E Rd The following lemma shows that when looking for low volume ellipsoids that contain axis-aligned set, we restrict out attention to axis-aligned ellipsoids, defined by diagonal matrix. The following lemma can be seen as the polar statement of Goemans al. (2009, Proposition 3.1), with the benefit of not requriring any matrix inversions.
Lemma D.5. Let X C. IRd be an axis-aligned convex set and ler A E Rdxd be pasitive definite matrix such that X C E(A). Then X C ((iiag (A)) and Vol(E(Diag( (A)) I VVo(E(A)).
Proof. Let us start by showing that X' _ (Diag A)). We use the notation Diag(v) - X' to denote the set Diag(v) X == (Digg(v)
E X}. Since X' is axis-aligned, have
X' = Diag(s) A' S Diag(s) E( E(A) = (SDiag(s) A Diag(s)), Therefore, X' contained each of the 2 ellipsoids of the form ((Diag(s) A Diag(s)). Thus,
E {+1]
X
E(Diag(s) Diag(s)) 3
Σ
Diag(s) Diag(s)
2d
sEf113a
SE[11]
where the last inclusion follows since, for any set of positive definite matrices M, one may verify that (MMME Ç ((///M) EMEM M). Finally, note that
Diag(s) Diag(s) Diag(A). 1E
Indeed, let i,j .I, d]. If = j. then Diag(()))) Aig for any [#1]d, If i * j. then
Σ #E(+1)
(Diag(s)A Diag(s))i.
Σ
(Diag(s). A Diag(s))is
Σ
(Diag(s) A Diag(s))s
=
3E (+1) #a1
aE(=1)" s[(==[]]
= 2d (- A,,) 2d Ai, =0
Let now show that (olag(Diag(AA)) < Vo)(E(A)). Note that log(Vol(E(A))) log( (T)((E())) 2 log (A). Since log det(-)
concave over positive definite matrices.
have
log deta(Dia((A)) log del
Σ
2d
sE(=13d
2
2d
Σ
log det Diag(s)A (iaggs)))ia((ss)
= 2d
2d log det(A) = log det (A).
8E(=1]a
Therefore,
log (o(ool(((Diag(A))) log((Vl(E(I))) log (eiagag
S log( (oo(())(E(())) log det(A)
log((Vo(E(A)))
which implics that (ol(E(Diag(A))) < Vol(E(A)).
We are now in position to prove Lemma 5.2, which follows directly from the previous two results.
Proof of Lemma 5.2. By the assumptions in Proposition 4.2 we have that P = Diag(p) fails the Armijo condition 4 condition and, thus, H2 (u). This together with the assumption that |Pll A < 3/v2a imply via Lemma D.3 that ||u|| A 2 2d. This allows us to use Theorem D.2 to find new ellipsoid containing E(a) n H (u) with the required volume decrease by Lemma D.4.
33

---

Yet, this ellipsoid may not be axis aliined We shall exploit the symmetry described in Lemma D.5 to show that the axis-aligned ellipsoid E(a (a, u)) enjoys the same guarantees.
Formally, we need (aa (a, u)) to contain (a) n Hgg (u). Since 2 O, we have
H (u) _ S(u) = {p R: Diag(s)
Mg (u) for all s E (=1)").
Thus, it suffices for ((a (a. u to contain ((a))S(()) From Theorem D.2 we know that (a)) is contained in the ellipsoid given by the matrix À Di)g(a) + (1 Ajuu for any X, in particular for À in (20) since ||lla > vd. Since S(u) is axis-aligned, we can exploit symmetry using Lemma D.5, which tells that {a) n nS(u) is contained in the ellipsoid given by the matrix
Diag Diag((a) + (1 A)un Diag(a"* (a, u));
as desired. Finally, the bound on the volume follows by Theorem D.2 and the bound on vu(u) given by Lemma D.4 since ||ul|A-I 2 22d.
Finally, we are position to prove Theorem 5.3, which follows almost directly from Lemma 5.2.
Proof of Theorem 5.3. Note that (a) holds by induction and since, by Proposition 4.2, have diag(P") E Hgg (u,) for any u, used call to CUT. For (b), fix t {1...., T) and recall that in this have S. = Diag(p): p {(a)). As described in (8), may verify that Diag(qī) for q. given by
q [ A,
maximizes
/aatimzzes//Vf(xx/// [[V[(x)) for P Sr. Since
P. = CANDIDATE(S,, 1/v2d,x,) = 22d Diag (q:);
conclude that P. is 1/v0 ///ap-coeeeiiivvee For (c), first note that may assume (4/x)1 E(o To see that, assume 11/r)1 & E(oo)), implying and > T.2. this case, any candidate preconditioner computed by CANDIDATE always valid and, thus, we never call CUT. To see this, let Ao agl be the matrix defining the initial ellipsoid. Then, by the definition of CANDIDATE for ellipsoids we have that Po- Diag(Po) is such that
Poll = ao aoolPol [Pol
00 2
21
Therefore, poli] S 1/1. for (1...., d). which implies that Po valid since Po 3 I.
Let us look now at the case (1/1)1 T) Therefore, B(/r1) S E(a,) for all iterations t. Since the minimum volume ellipsoid containing the box B((/))1)) the unit sphere of radius 1/z, that is, E((4//a)1). Therefore, Vol(E(a.)) 2 Vol(E((L*/a))) Moreover, every time we call cut the volume of the ellipsoid goes down by 1/c = Ve/v2. Therefore, the total number of calls to CUT is more than
Vol(E(ao1)) loge Vol(E(((//a1)))
L
L
loge
log doo
12d
d/2 day
log(e)
cn
since log(c) 2 1/12.
Refining the choice of A. Although we have shown in Lemma 5.2 choice a that guarantees volume decrease, it may be sub-optimal. The choice of À in Equation (20) is inherited from the non-symmetric case in Theorem D.2. Although Lemma 5.2 and Theorem D.2 match when u has only non-zero entry, should expect better choices of X, leading to more volume shrinkage, to be possible in Lemma 5.2. Although we have not found choice of that is dependent on u that generically improves upon (20), in practice
solve for better À numerically, by directly
minimizing the volume of the resulting ellipsoid,
min Vol(E(Aa + (1 X) Diag(uu)) T))) 0<X<1
min 0<X<1
Σ log(Aa(() + +11 A)u(d?²).
34

---

As the problem is one-dimensional. numerical solvers can often find near-optimal solutions. By warm-starting numerical solver with the À defined in (20), we can guarantee that the resulting ellipsoid leads to smaller volume and we do not lose our worst-case theoretical guarantees.
Connection to the polar problem and related work. Our results have interesting connection to some of the results from Goemans et al. (2009), via the use of polarity theory. Here we give quick overview of their work and the connection to our cutting plane methods. Goemans al. (2009) shows techniques to approximate some polyhedron P C IR" (a polymatroid being one of the main examples) from inside by some ellipsoid & (A). Their algorithm maintains an ellipsoid & ((A) C P and tries to iteratively enlarge it. They assume access to an oracle such that, at each iteration, either finds a point u E that is sufficiently far from { ). meaning |u| A > vd + for some 0, or guarantees that E (A) "approximates well" P from inside in the sense that ||u|| S (Vr + e)/a for all E P. where a > is some approximation factor. In their algorithm, when the oracle finds point u E P such that ||u|| > vd the algorithm needs to find an ellipsoid E(A (A+) such that
E(A+) C conv(E(A) {u,-u}),
(22)
where CDnv(D) is the convex hull of D. Interestingly, the polar problem is exactly what we need for out cutting plane method. More precisely, the polar set X of a set X' is given by X { 2 E R (2, x) < 1}. Then, by taking polars and using that E(A)* E(A -). we have that p' C {(A (A. Moreover, taking polar on both sides of (22) yields that an equivalent problem finding (A+)-1 such that
E((A+) 2 (
f(A= [ =
That is, the problem is the one of finding smaller ellipsoid E((A+) [)=) that contains E(A ((--)) 0 [z: (u, z) S 1}, which is broadly the goal of the subroutine CUT,
35

---

Table 1: Datasets used our experiments, including number of samples n and dimension and
order of magnitude of the condition number of the regularized system (x(X X + +1/II) and condition number of the system when using the optimal diagonal preconditioner, N..
Dataset
Repository/Source
d
cpusmall
LIBSVM, Delve (comp-activ)
8 192
12
1013
10a
california-housing
Scikit/StatLib, Kelley Pace and Barry (1997)
20 640
8
10
10*
power-plant
UCI, Tüfekci (2014)
9 3668
4
10
10
concrete
UCL, Yeh (1998)
1 030
8
109
10a
ig
LIBSVM, Flake and Lawrence (2002)
1 185
6
10a
10a
breast-cancer
UCI
569
32
10th
10a
australian
LIBSVM, Statlog
690
10
102
heart
LIBSVM, Statlog
270
13
107
10a
diabetes
UCI
10c
10a
ionosphere
UCI
351
34
10a
10a
news20
LIBSVM, Keerthi and DeCoste (2005)
19 996
355 191
1013
NA
rey1
LIBSVM, Lewis et al. (2004)
20 242
27
10
NA
E Experiments
Objective functiins
We Læ-regularized linear regression LUNEAR and Lg-regularized logistic regression LLoUssric (w), with regularization coefficient of 1. Given data matrix X E Raxdd target IR" for regression tasks and y E {0, 11 for classification tasks, and parameters w Rd,
LUNBAR (w) 1
Xw y/12 + _ =llwlp)
n1
2
11 y(i log(o((xx, w))) - (1 - y(i)) log(1 o((x, w)))
LLOCISTIC (w) = n Σ
|w]]
n 2
where x; is the ith row of and is the sigmoid function, (z)) - 1/1+expl- For all datasets, we add bias term by prepending a feature column of ones to X.
Datasets
We use the datasets listed in Table I, made available by LIBSVM (Chang and Lin, 2011), Scikit-Learn (Pedregosa et al., 201 I) and the UCI repository (Dua and Graff, 2017).
Data rescaling
We do not rescale, standardize or otherwise change any of the datasets beyond adding a bias term, as goal is to check whether preconditioned methods can handle badly scaled data.
Initializations
We consider two types of initializations. The first approximates a "best-case" scenario where we start from estimate with reasonable loss value despite the bad scaling of the data. We set w[i] except for the bias term w(0) which is set at the MLE of the non-regularized problem,
[0]
where ÿ Ei=ye ((i
for linear regression,
[0] log
where ÿ = -E [(i]
for logistic regression.
The results in the main text use this initialization. The second initialization takes w ~ ~0, I), giving starting point with potentially large loss. We give results using both initializations in the appendix.
36

---

Optimizers used
For the small linear regression problems, preconditioned gradient descent with the optimal preconditioner, pre-computed using the semidefinite formulation of Qu et al. (2022), solved using CVXPY (Diamond and Boyd, 2016) based the Matlab implementation of Qu et al.
https://github. cww wwwp//wwwx../ppppdpppppppo
Gradient descent with backtracking line-search with backtracking parameter = 1/2.
RPROP (Riedmiller and Braun, 1993) following the implementation and default hyperparameters
in PyTorch (Paszke et al., 2019) (starting step-size 10 increase step-size factor 77' 1.2,
decreasing step-size factor fj 0.5, minimum step-size of 10 and maximum step-size of 50).
https://github. www.cc/m/occccce pytorryooooooooo ch/
1/torehhopptim/ppprpppp.p
Hypergradient descent to set the step-size, using (S)GD-HD (the multiplicative variant, Baydin et al., 2018). The hypergradient step-size set to the default / 0.02 (Baydin et al., 2018, footnote 3). The initial step-size is set to 10 as otherwise most runs diverged immediately.
The diagonal Barzilai-Borweii method of Park al. (2020), using their non-monotonic line-search. We use the default parameters suggested; a starting step-size 10-6, regularization factor on the previous diagonal approximation μ 10 backtracking factor of 1/2 for the backtracking line-search and a window 15 steps for the non-me mom-otonn line-search. This line-search does not forward step the update can increase the preconditioner.
Preconditioned gradient descent using the diagonal Hessian, with a backtracking line-
AdaGrad (Duchi et al., 2011) but augmented with a backtracking line-search as suggested by Vaswani al. (2020) make competitive in the deterministic setting, following the Py PyTorch (Paszke et al., 2019) implementation.
https://githhnn com/ wwwpootcpyytoorttepppp.pop http://owr///ptoooo///oo///..... http:////........oooooooooo///a/
Line-search and forward steps
For all methods, the backtracking line-scarch augmented by forward step. When a step-size is accepted, it is increased by factor of 1.1 for the next step. For multidimensional backtracking, increase the set uniformly, taking b' = 1.1 b for the box and a' = a/v1.1 for the ellipsoid. The ellipsoid uses slightly smaller increase factor.
Hyperparameters for the line-search and multidimensional backtracking
For the backtracking line-searches used in gradient descent, preconditioned gradient descent and used augment the other algorithms, start the search initial step-size of 1020 and backtrack by factor of 1/2 when failing the Armijo condition, implemented generically as
f(x d) s f(x) (Vf(x), d)
For multidimensional backtracking, we initialize the sets such that the first preconditioner on the order of 10 II. Using the notation of Appendix A, we use the scaling factor co = d 10 for the box variant and co vd 10 for the ellipsoid variant. The first preconditioner tried by the box variant with backtracking factor 7 1/2d is then 1/2 10 "I and the first preconditioner tried by the ellipsoid variant (assuming the gradient is uniform, (x(x)) x 1) 1/v2 II
To increase factor of 1.1 1.1i in the one dinedsiioonnll case, the update the ellipsoid should be a' a/1.13.
37

---

Table Running times for parts of a backtracking update using the Ellipsoid variant (Figure 11) on RCVI. Average runtime over 100 calls. + standard deviations over 10 repeats.
Operation
Average runtime
std
Compute gradient, preconditioner and next iterate
24,4 ms
+0.2 ms
Compute hypergradient
12.6
+0.1
Compute CUT (using Lemma 5.2)
0.9 ms
+0.1 ms
Compute CUT (solving the convex combination with scipy. .appy.op optimize)
7.6 ms
#0.1 ms
E.1 Performance comparison
The algorithms we compare not have a unified notion an "iteration". For example, backtracking line-search and multidimensional backtracking do more work than plain gradient descent in between updates to the parameters. To make the performance comparison fair, the results in Figures and account for the overhead of backtracking by comparing the performance against the number of oracle calls, counting the number function and gradient evaluations.
This metric is good proxy for the work required by multidimensional backtracking. The majority of the computation cost of the "backtracking" part of the algorithm comes from computing the gradient at the next point (to compute the hypergradient). The overhead due to other operations such as the CUT method are minimal compared to gradient computations. Indeed, beyond the gradient computation, multidimensional backtracking only involves a few vector operations (see Figures 10 and 11). Even solving for the best convex combination numerically obtain tighter ellipsoids (as the CUT method in Figure 11) is faster than computing gradients. To illustrate this point, provide the running times for subsets backtracking update from multidimensional backtracking in Table 2.
E.2
Additional results
Figures 15-20 give additional results on small linear and logistic regression problems and large logistic regression problems. Multidimensional backtracking has a consistent performance across problems and does not suffer from the extremely bad conditioning of cpusmall or california-ouusing (linear regression) or australian, breast-cancer, diabetes and heart (logistic regression).
38

---

Figure 15: Runs small linear regression datasets with Bias initialization
cpusmall
10
Oplimallty SRP
10
10
500
1000
1500
2000
2500
3000
3500
4000
200
400
600
800
1000
1200
1400
Oracle calls (Function Gradiont oval.)
Iterations (Changes in x)
Califoria--husinng
Optimality gaip
10
10P
10-4-
10-2
500
1000
1600
2000
2600
3000
3600
4000
200
400
800
800
1000
1200
1400
Oradle calls (Funclion Gradient eval.)
Iterations (Changes x)
Power-plant
10
10*
Optimalty gap
10a
10a
10a
1000
1500
2000
3000
8500
4000
800
1000
1200
Oradle calls (Function Gradient eval.)
Iterations (Changes x)
Concrete
10a
10a
Optimallty
10'
10'
10-1-
10-1
1000
Oradle calls (Function Gradient eval))
Iterations (Changes x)
Mg
107-
10a
Oplimaliyy gap
10
10-1_
10-
10-+
500
1000
1600
2000
2500
3000
3600
4000
200
600
800
1000
1200
1400
Oradle (Function
eval.)
lterations (Changes x)
GD+LS
Dieg. Hesslan+LS
Diag. AdaGrad-LS
Ellipsoid
Dieg. BB-NMLS
RPROP
GD-HD (mult.)
39

---

Figure 16: Runs small linear regression datasets with Gaussian initialization
cpusmall
Optimallty gRP
1012
107
10¹
10*
10²
500
1000
1500
2000
2500
3000
3500
4000
200
400
600
800
1000
1200
1400
Oracle calls (Function Gradiont oval.)
Iterations (Changes in x)
Califoria--husiing
Optimality gap
10
10*
10a
10a
500
1000
1600
2000
2500
3000
3600
4000
200
400
800
800
1000
1200
1400
Oradle calls (Funclion Gradient eval.)
Iterations (Changes in x)
Power-plant
107-
Optimalty gap
10
10
101
1000
1500
2000
3000
4000
800
1000
1200
Oradle calls (Function Gradient eval.)
Iterations (Changes x)
Concrete
Optinally gap
101
10
10'
10"
1000
Oradle calls (Function Gradient eval.)
Iterations (Changes x)
Mg
Oplimalty gap
10
10a
10-1-
10-1-
10
4_
500
1000
1600
2000
2500
3000
3600
4000
200
600
800
1000
1200
1400
Oradle (Function
eval.)
lterations (Changes x)
GD+LS
Dieg. Hesslan+LS
Diag. AdaGrad-LS
Ellipsoid
Dieg. BB-NMLS
RPROP
GD-HD (mult.)
40

---

Figure 17: Runs small logistic regression datasets with Bias initialization
Breast-cancer
Opaiallty gap
10
10
10 40
10-11
10-11
200
400
600
800
1000
1200
1400
100
200
300
400
500
Oracle calls (Function + Gradiont oval.)
Iterations (Changes in x)
Australian
Optimality gaip
10
10"1
10
10:1-
10
10-2-
200
400
600
800
1000
1200
1400
100
200
300
400
600
Oracle calls (Funclion Gradient eval.)
Iterations (Changes in x)
Heart
Oplimality gap
10a
10
10-2-
10*
10-1
1000
1200
1400
300
400
500
Oracle calls (Function Gradient evall)
Iterations (Changes x)
Diabetes
10'
10"
10
10-2
Optimality
10.5
1400
Oradle calls (Function Gradient eval.)
Iterations (Changes x)
lonosphere
Oplimaliyy gap
10
10
10-5-
10:9
10-2
200
400
600
1000
1200
1400
100
300
400
500
Oracle (Function Gradient eval.)
lterations (Changes x)
GD+LS
Dieg. Hesslan+LS
Diag. AdaGrad-LS
Ellipsoid
Dieg. BB-NMLS
RPROP
GD-HD (mult.)
41

---

Figure 18: Runs small logistic regression datasets with Gaussian initialization
Breast-cancer
Oplimality gRP
10*
10.
10-
200
400
600
800
1000
1200
1400
100
200
300
400
500
Oracle calls (Function + Gradiont oval.)
Iterations (Changes in x)
Australian
101
Optimality gap
10º
10---
10
200
400
600
800
1000
1200
1400
100
200
300
400
600
Oradle calls (Funclion Gradient eval.)
Iterations (Changes in
Heart
10²
10a
Oplimality
10-1
10
10000
1200
1400
300
Oracle calls (Function Gradient
Iterations (Changes
Diabetes
Optimallty
10a
10-
10-3-
1400
Oradle calls (Function Gradient eval.)
Iterations (Changes x)
lonosphere
Oplimaliy gap
10
10-1
10-5
10-5
10
10-
200
400
600
1000
1200
1400
100
300
400
500
Oracle (Function Gradient eval.)
lterations (Changes x)
GD+LS
Dieg. Hesslan+LS
Diag. AdaGrad-LS
Ellipsoid
Dieg. BB-NMLS
RPROP
GD-HD (mult.)
42

---

Figure 19; Runs on large logistic regression datasets with Bias initialization
News20
Oplimality gaip
10"1
10
10
10-4-
200
400
800
1000
1200
1400
100
300 Iterations (Changes x)
500
Oracle calls (Function Gradiant evall)
RCV1
10
10
Oplimality
10-
10-2--
10
10
1400
Oradle calls (Function Gradient eval))
Iterations (Changes x)
GD+LS
Diag. Hessian.LS
Diag. AdaGrad-LS
Ellipsold MB
Diag. BB-NMLS
RPROP
GD-HD (mult.)
Figure 20: Runs on large logistic regression datasets with Gaussian initialization
News20
10a
Optimality gai
10a-
10P
10
200
400
800
1000
1200
1400
100
200
300
400
600
Oracle calls (Function Gradiont ovall)
Iterations (Changes x)
RCV1
Oplimality gap
10'
10
10-2-
10-2_
10 F_
1400
100
Oracle calls (Function Gradlent
Iterations (Changes x)
GD+LS
Diag. Hessian+LS
Diag. AdaGrad-LS
Ellipsoid MB
Diag. BB-NMLS
RPROP
GD-HD (mult.)
43


Reviews:
[{"review_id": "XIeciX0b69", "reviewer": "Reviewer_JVBS", "summary": "This paper presents a generalized backtracking line-search method, which estimates coordinate-wise stepsizes referred to as 'preconditioner' of gradient descent. Stemmed from the observation that any existing methods do not exceed the performance of backtracking line-search method, this paper designs a generalized backtracking line-search technique which is realized as a cutting plane method, whose separating hyperplane comes from the hypergradient, i.e., gradient with respect to hyperparameter of the algorithm, which is a stepsize in this case. Followed by the worst-case convergence analysis for smooth strongly convex function, the writers also provide experimental results illustrating the competitiveness of this method for ill-conditioned problems and robustness among problem classes.\n", "questions": "The 'CUT' subroutine, which is a 'backtracking' phase of this algorithm, can be called up to the number of iterations linear in dimension $d$, which can be large in considering large-scale problems. It has been illustrated in the experimental result that for large problems it recovers preconditioner quite fast, but I'm also curious on how much total overhead is caused by the subroutine `CUT'.\n\n\n (p.3 line 121) It seems there is a typo on notation regarding $d, n, \\\\alpha$.\n", "limitations": ".", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Section 4 contains the key insight of this work: that a failed preconditioner (defined as one that violates a Armijo-type condition) provides a cutting plane on the set of valid preconditioners. This is a very nice idea that is, as far as I know, novel, and I expect this work to lead to a lot of follow-up work. This is a new type of result and I think it is valuable.", "weaknesses": ".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for sharing in our excitement with the paper! \n\nPlease see the discussion of the overhead of `CUT` (also raised by reivewer eKZX) in the overall response.\n\nThanks you for spotting the typo on l.121, a sentence got eaten due to a version conflict."}, {"review_id": "30mr1FsPYA", "reviewer": "Reviewer_5i17", "summary": "This paper extends backtracking to multi-dimension. The authors propose a cutting plane method to find optimal per-coordinate step-sizes (in other words, to find an optimal preconditioner) for smooth convex optimisation. Experiments on ill-conditioned logistic regression problems show that the proposed algorithm can find good preconditioner and improve over vanilla gradient descent.  ", "questions": "None.", "limitations": "See weaknesses. ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper fills a potential gap in the optimization literature by proposing multidimensional backtracking. The proposed method is technically sound and seems to work well in practice.", "weaknesses": "I do not see any major issues with the paper, except maybe that it is a bit hard to follow and understand (even though the English is good). Maybe because I don't have enough background on the topic. I'm really sorry for the short review.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you for engaging with our paper during the review period! \n\n> This paper fills a potential gap in the optimization literature by proposing multidimensional backtracking\n\nWe emphasize that, beyond the specific algorithm presented, a contribution of our work is the development of a formal definition of adaptive per-coordinate step-sizes and a way to provably find them.\n\nAs mentioned in the introduction, existing definitions of adaptivity do not capture the benefits of preconditioning, even on simple linear regression problems. For example, the online learning definition used by AdaGrad forces the step-size to go to 0 and leads to poor performance in practice.\n\nWe believe that these ideas can lead to further work to improve adaptive methods.\n"}, {"review_id": "6x09jtwUp2", "reviewer": "Reviewer_hZtF", "summary": "This paper provides a backtracking approach for smooth convex optimization on a per-coordinate basis with a theoretical analysis that show the gain with respect to classical backtracking line-search and that compare to the optimal per-coordinate conditioners.", "questions": "None.", "limitations": "None.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is super well written and organized. The contribution is also significant as it is a building block of many problems in machine learning.\nIn general, further improving the \"adaptivity\" of optimization algorithms is essential to seamlessly apply theoretical results (i.e., optimal per coordinate step sizes) to operational purposes.", "weaknesses": "The only drawback might be focusing on smooth and strongly convex problems, but it is still a significant first step.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for sharing in our excitement with the paper! \n\nWe agree that one of the major drawbacks of our technique is the focus on the smooth, strongly-convex case. We do address the PL case as a relaxation of strong-convexity in the Appendix, and hope our work will lead to others exploring relaxations like the convex-only, non-convex, stochastic, and other cases."}, {"review_id": "BvHTjlWDhH", "reviewer": "Reviewer_eKZX", "summary": "The authors suggest incremental updates of $\\mathbf{x}$ for finding the minimum of strongly-convex function $f$ that guarantee decreasing $f(\\mathbf{x}_{t})-f(\\mathbf{x}_\\ast)$ based on only 1st-order gradient information. \n\nTheir idea is in each step,\n- choose a candidate matrix $\\mathbf{P}_t$ based on set $\\mathcal{S}_t$, and\n- check the condition (4), that guarantee sufficient decrease of the $f$, and\n- if the condition is satisfied:\n    - apply update $\\mathbf{x}_{t+1} = \\mathbf{x}_t - \\mathbf{P}_t\\nabla f(\\mathbf{x}_t)$\n    - $\\mathcal{S}_{t+1} = \\mathcal{S}_t$\n- else\n    - $\\mathbf{x}_{t+1} = \\mathbf{x}_t$\n    - update $\\mathcal{S}_{t+1} = \\text{cut}(\\mathcal{S}_t, \\mathbf{x}_t, \\mathbf{P}_t)$\n\nThey provide proofs for\n- approaching the optimal in Proposition 3.2\n- how to choose candidate and cut algorithm in Theorem 5.3, and its maximum number of calls.\n\nThey conduct some simple experiments in Section 6, and show the proposed algorithm's efficiency.", "questions": "- In line 129, the representation $\\nabla^2 f$ appears. Does it mean Hessian? or Laplacian?\n- Between line 197 and 198, the final inequality may be not $\\overset{(3)}{\\leq}$ but $\\overset{(4)}{\\leq}$ ?\n- In the caption of Figure 3(b), $\\mathcal{H}\\_{>}(\\mathbf{u})$ should be replaced by $\\mathcal{H}_>(\\mathbf{v})$ ?\n- In Figure 5, do the authors take the number of CUT into account?", "limitations": "They address the limitation, their method is only supported for convex deterministic setting.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "originality\n- considering backtracking using preconditioned matrix $\\mathbf{P}_t$ would be novel idea. But I'm not an expert of this field, and not so sure on the originality.\n\nquality\n- The proposed algorithm is supported by some proofs, and it shows good empirical results.\n\nclarity\n- Basically, the manuscript is readable.\n\nsignificance\n- The proposed algorithm seems be better than other baselines except for Diag. Hessian+LS, which uses information of 2nd order derivatives, i.e. Hessian, even the proposed algorithm uses 1st-order derivatives of $f$. It would be significant.", "weaknesses": "- The manuscript contains some typos.\n- I have a concern on Figure 5. The horizontal axis shows number of f/grad evals, but I guess the number of CUT calls should be also taken into account.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for engaging with our paper during the review period! \n\nPlease see the discussion of the overhead of `CUT` (also raised by reivewer JVBS) in the overall response. For the other points:\n\n> considering backtracking using preconditioned matrix $\\mathbf{P}_t$ would be novel idea. But I'm not an expert of this field, and not so sure on the originality.\n\nWe are not aware of prior work using similar approaches to estimate a preconditioner, or provide guarantees similar to the ones we present. We emphasize that, beyond the specific algorithm presented, a contribution of our work is the development of a formal definition of adaptive per-coordinate step-sizes and a way to provably find them.\n\nAs mentioned in the introduction, existing definitions of adaptivity do not capture the benefits of preconditioning, even on simple linear regression problems. For example, the online learning definition used by AdaGrad forces the step-size to go to 0 and leads to poor performance in practice.\n\nWe believe that these ideas can lead to further work to improve adaptive methods. \n    \n> In line 129, the representation $\\nabla^2 f(x)$ appears. Does it mean Hessian? or Laplacian?\n\n$\\nabla^2 f$ does refer to the Hessian. We will mention it on first appearance to avoid confusion.\n\n> Between line 197 and 198, the final inequality may be not (3) but (4)?\n \nThe numbers on the display math do not refer to equation numbers (which we assume is the confusion) but to the numbers `(1), (2), (3)` in the preceding paragraph. We will change those to `(a), (b), (c)` to disambiguate.\n\n> In the caption of Figure 3(b), $\\\\mathcal{H}\\_{>}(\\\\mathbf{u})$ should be replaced by $\\\\mathcal{H}\\_{>}(\\\\mathbf{v})$?\n\nIndeed, we will fix it."}]

Author rebuttal:

We thank all reviewers for engaging with our paper. We were very pleased to see reviewers JVBS and hZtF sharing in our excitement with the paper and appreciate the great feedback. We appreciate that reviewers 5i17 and eKZX truly engaged with our paper despite it being outside of their area of expertise.

If the reviewers have more feedback about which parts would benefit from more exposition to improve the presentation reach a broader audience, we would appreciate specific recommendations. This feedback would be valuable for future expositions of our work.

### On the overhead of CUT 

Reviewers eKZX and JVBS both asked for more details on the overhead of backtracking and the `CUT` operation. The results in Figure 1 and 5 account for the overhead of backtracking by showing the number of gradient evaluations. The majority of the computation cost of a backtracking step comes from computing the gradient at next point to compute the (hyper-)gradient. This is why our algorithm does not make progress at the start, as the first gradient evaluations are spent on backtracking.

The overhead of `CUT` is minimal compared to gradient computations as it only involves a few vector operations (see Figure 11 in Appendix A for the pseudocode). Even solving for the best convex combination numerically (see lines 287-288 or Appendix D) is faster than computing gradients. The table below gives running times fors parts of a backtracking update on RCV1 for the Ellipsoid version (average runtime over 100 calls, ±std over 10 repeats).

| Operation                                                                | Average runtime | ±std    |
|--------------------------------------------------------------------------|-----------------|---------|
| Compute gradient, preconditioner and next iterate                                                     | 24.4 ms         | ±0.2 ms |
| Compute hypergradient                                                    | 12.6 ms         | ±0.1 ms |
| Compute `CUT` (using Lemma 5.2)                                          |  0.9 ms         | ±0.1 ms |
| Compute `CUT` (using `scipy.optimize` to find the min. volume ellipsoid) |  7.6 ms         | ±0.1 ms |


Meta-review: I thank the reviewers for their comments. I took the discussion as well as the author feedback into consideration. there seems to be general consensus among the reviewers that the paper is good with positive reviews. I therefore will recommend acceptance of the paper.
Decision: Accept (poster)