Provably Faster Gradient Descent via Long Steps

Introduction

This work proposes a new analysis technique for gradient descent, establishing a path toward provably better convergence guarantees for smooth, convex optimization than is possible with existing approaches based on constant stepsizes. Instead, our theory allows for nonconstant stepsize policies, periodically taking larger steps that may violate the monotone decrease in objective value typically needed by analysis. In fact, contrary to the common intuition, we show periodic long steps, which may increase the objective value in the short term, provably speed up convergence in the long term, with increasingly large gains as longer and longer steps are periodically included. This bears a similarity to accelerated momentum methods, which also depart from ensuring a monotone objective decrease at every iteration.

Establishing this requires a proof technique capable of analyzing the overall effect of many iterations at once rather than the typical (naive) one-iteration inductions used in most first-order method analyses. Our proofs are based on the Performance Estimation Problem (PEP) ideas of , which cast computing/bounding the worst-case problem instance of a given algorithm as a Semidefinite Program (SDP). We show that the existence of a feasible solution to a related SDP proves a descent guarantee after applying a corresponding pattern of nonconstant stepsizes, from which faster convergence guarantees follow. Our technique is very similar to that first proposed by Altschuler’s Master’s thesis [4, Chapter 8] which established repeating stepsize patterns of length two or three with faster contractions towards the minimizer for smooth, strongly convex minimization. Most existing PEP literature uses computer-solves to guide the search for tighter convergence proofs and inform the development of new, provably faster algorithms . Here computer outputs are directly used to constitute the proof, but are large (up to tens of thousands of rational numbers) and so may provide less guidance or intuition.

By tight, we mean a matching problem instance exists that attains the above inequality. Using stepsizes between one and two, this rate can be improved by another factor of two (see ). Stepsizes beyond length two have very little prior theory as one can no longer guarantee a decrease in objective value at each iteration.

Here we provide an analysis technique capable of handling nonconstant stepsizes, periodically longer than one can guarantee descent for, finding increasingly fast convergence (in terms of constants) follows. For example, consider gradient descent alternating stepsizes $h=(2.9,1.5,\ 2.9,1.5,\ \dots)$. Such a scheme is beyond the reach of traditional descent-based analysis as one may fear the stepsizes of $2.9$ can increase the function value individually more than the $1.5$ is guaranteed to decrease it. Regardless, we show this “long step” converges with

for every even $T>0$. See our Theorem 3.2 characterizing many such alternating stepsize methods. The $+O(1/T^{2})$ terms throughout this work are only used to suppress two universal constants, namely above, we show there exist constants $\bar{s}$ and $C$ such that all even $T>2\bar{s}$ have bound $LD^{2}/(2.2\times T-C)$.

In Theorem 2.1, we give a convergence guarantee for any straightforward stepsize pattern $h$ of

Table 1 shows straightforward stepsize patterns with increasingly fast convergence guarantees, each proven using a computer-generated, exact-arithmetic semidefinite programming solution certificate. Future works identifying longer straightforward patterns and other tractable families of nonconstant, periodically long stepsize policies will surely be able to improve on this work’s particular guarantees.

The analysis of such nonconstant, long stepsize gradient descent methods has eluded the literature, with only a few exceptions. In 1953, Young showed optimal, accelerated convergence is possible for gradient descent when minimizing a smooth, strongly convex quadratic function by using a careful nonconstant selection of $h_{i}$. Namely, Young set $h_{0}\dots h_{T-1}$ as one over the roots of the $T$-degree Chebyshev polynomialA nice summary of this is given by the recent blog post .. Few works have shown faster convergence from long steps beyond quadratics. Two notable works have done so for smooth, strongly convex minimization:

Oymak showed substantial speed-ups for strongly convex functions with special bimodal structured Hessians. Closely in line with this work’s reasoning, several recent Master’s and doctoral theses have addressed the optimal design and analysis of one, two, or three steps of gradient descent. The theses of Daccache and Eloi provide exhaustive characterizations of gradient descent’s objective gap after two or three steps for smooth convex optimization. Their results do not provide a mechanism to be applied inductively, so no convergence rates follow from repeatedly applying the studied patterns. For strongly convex optimization, Altschuler [4, Chapter 8] used PEP techniques to derive the optimal patterns of length $t=1,2,3$ for contracting either the distance to optimal or the gradient’s norm. Inductively applying their improved contractions, one arrives at the same moral takeaway advanced by this work: SDP-based analysis can prove faster convergence follows from periodically taking longer steps, potentially violating descent. Importantly, their length two and three patterns are optimal, meaning their patterns give the best possible contraction factor. Note their patterns differ from those presented here, only being optimal for strongly convex problems. The primary contribution in this work is identifying a tractable analysis technique for general smooth, convex optimization and showing increasing performance gains for increasingly large $t>3$, continuing in this seventy-year-old direction.

If true, this would likely yield convergence rates on the order of $O(1/(T\log(T)))$, strictly improving on the classic $O(1/T)$ guarantee. If such long patterns exist, one natural question is how close to the optimal $O(1/T^{2})$ rate attained by momentum methods can be achieved by gradient descent with long steps. The numerics of [13, Figure 2] suggested a $O(1/T^{1.178})$ rate may be possible. The theory of Lee and Wright showed asymptotic $o(1/T)$ convergence for constant stepsize gradient descent (although no improved guarantees in finite-time were given), which also motivates the possibility for improved finite-time convergence guarantees.

Cyclic, periodically long stepsizes have been used in neural network training schedules . Our results only apply to convex, deterministic problems. New techniques handling nonconvexity and stochasticity would need to be developed to describe the effect of long steps in such settings of machine learning.

Outline. In the remainder of this section, we informally sketch how our proof technique proceeds. Then Section 2 formally introduces our notion of straightforward stepsize patterns, showing that any such pattern has a guarantee of the form (1.4). Section 3 shows the existence of a solution to a certain semidefinite program implies straightforwardness. Section 4 concludes by outlining several future directions of interest enabled by and hopefully able to improve on this work.

Our analysis works by guaranteeing a sufficient decrease is achieved after applying the whole pattern $h=(h_{0},h_{1},\dots,h_{t-1})$ of $t$ steps (but not necessarily descending at any of the intermediate iterates). Our notion of straightforward stepsize patterns aims to ensure that for all $\delta>0$ small enough, if $f(x_{0})-f(x_{\star})\leq\delta$, then $x_{t}$ will always attain a descent of at least

For constant stepsizes equal to one, this amounts to $f(x_{0}-\nabla f(x_{0})/L)\leq f(x_{0})-\delta^{2}/LD^{2}$, a classic descent result that holds for all $L$-smooth convex $f$.

To prove a descent lemma like (1.5), one can take a direct combination of several known inequalities. This is a well-known approach, equivalent to providing dual solutions to the dual of the associated performance estimation problem. We are given the equalities $x_{k+1}=x_{k}-(h_{k}/L)\nabla f(x_{k})$ and $\nabla f(x_{\star})=0$ and as inequalities an initial distance bound

and for any $x_{i}$ and $x_{j}$ with $i,j\in\{\star,0,1,2,\dots t\}$, convexity and smoothness imply[33, (2.1.10)]

For any nonnegative multipliers $v(\delta),w(\delta),\lambda_{i,j}(\delta)\geq 0$ (parameterized by the initial objective gap $\delta$), one can combine these inequalities to conclude that on every $L$-smooth convex function, gradient descent (1.3) with stepsizes $h$ satisfies

Our proof then proceeds by showing carefully selected functions $w(\delta),v(\delta),\lambda(\delta)$ reduce this inequality to guaranteeing (1.5). We find to prove our guarantees in Table 1, it suffices to set $v(\delta)=\frac{\sum_{i=0}^{t-1}h_{i}}{LD^{4}}\delta^{2}$, $w(\delta)=1-\frac{2\sum_{i=0}^{t-1}h_{i}}{LD^{2}}\delta$, and use a linear function $\lambda(\delta)=\lambda+\delta\gamma$. For this choice of $v(\delta)$ and $w(\delta)$, our Theorem 3.1 shows (1.6) implies (1.5) if $(\lambda,\gamma)$ is feasible to a certain SDP. Hence, proving a $t$ iteration descent lemma of the form (1.5) can be done by semidefinite programming. Our Theorem 2.1 then completes the argument by showing such a periodic descent guarantee implies the guarantee (1.4).

Straightforward Stepsize Patterns

To analyze a given stepsize pattern, we first aim to understand its worst-case problem instance. We do so through the “Performance-Estimation Problem” (PEP) framework of . Given a pattern $h$ and bounds on smoothness $L$, initial distance to optimal $D$, and initial objective gap $\delta$, the worst final objective gap able to be produced by one application of the stepsize pattern is given by

Note without loss of generality, $x^{(i)}_{\star}=0$ and $f^{(i)}(x^{(i)}_{\star})=0$. Then one can easily check $\lambda f^{(1)}+(1-\lambda)f^{(2)},\lambda x_{0}^{(1)}+(1-\lambda)x_{0}^{(2)},\lambda x_{\star}^{(1)}+(1-\lambda)x_{\star}^{(2)}$ is feasible to the problem defining $p_{L,D}(\lambda\delta^{(1)}+(1-\lambda)\delta^{(2)})$. Consequently, taking the supremum over choices of $f^{(i)},x_{0}^{(i)}$ gives concavity as

Generally, the worst-case functions $f$ attaining (2.1) can be nontrivial. To find a tractable family of stepsizes for analysis, we focus on ones where this worst-case behavior is no worse than a simple one-dimensional setting: Consider the one-dimensional (nonsmooth) convex function linearly decreasing from $x_{0}$ to $x_{\star}$ and constant thereafter. That is, given $L,D,\delta$, consider the problem instance $f(x)=\max\{\delta x/D,0\}$, $x_{0}=D$, and $x_{\star}=0$. Provided $\delta$ is small enough (i.e., $\delta\leq LD^{2}/\sum_{i=0}^{t-1}h_{i}$), the gradient descent iteration $x_{k+1}=x_{k}-\frac{h_{k}}{L}\nabla f(x_{k})$ has

where $\delta_{k}=f(x_{k})-f(x_{\star})$ denotes the objective gap. In this example, gradient descent spends all $t$ iterations moving straight forward in a line along the slope. So the descent achieved is just controlled by the objective’s slope $\delta_{0}/D$ (squared) and the total length of steps taken $\sum_{i=0}^{t-1}h_{i}/L$.

We say that a stepsize pattern $h$ is straightforward if its worst-case behavior (over all smooth functions, as defined in (2.1)) is no worse than this one-dimensional piecewise linear setting for $\delta$ small enough. Formally, we say that a stepsize pattern $h$ of length $t$ is straightforward if for some $\Delta\in(0,1/2]$,

Note straightforwardness provides no guarantees on the intermediate objective values at iterations $k=1,2,\dots t-1$. We show in our theorem below descent at every $t$th iteration. To allow for some numerical flexibility, we say a pattern is $\epsilon$-straightforward if for some $\Delta\in(0,1/2]$, all $\delta\in[0,LD^{2}\Delta]$ have value function bounded by $p_{L,D}(\delta)\leq\delta-\frac{\sum_{i=0}^{t-1}(h_{i}-\epsilon)}{LD^{2}}\delta^{2}$.

where $\bar{s}=\left\lceil\frac{\log\left(\frac{f(x_{0})-f(x_{\star})}{LD^{2}\Delta}\right)}{\log(1-\sum_{i=0}^{t-1}(h_{i}-\epsilon)\Delta)}\right\rceil$. In particular, suppressing lower-order terms, this guarantee is

Consider first $s=0$. The first case of (2.4) follows from the definition of straightforwardness as $\delta_{t}\leq p_{L,D}(\delta_{0})\leq\delta_{0}-\frac{\sum_{i=0}^{t-1}(h_{i}-\epsilon)}{LD^{2}}\delta_{0}^{2}$. For the second case of (2.4), first note that $p_{L,D}(\cdot)$ is concave by Lemma 2.1. Then since $p_{L,D}(0)=0$ and $p_{L,D}\left(LD^{2}\Delta\right)\leq LD^{2}\left(\Delta-\sum_{i=0}^{t-1}(h_{i}-\epsilon)\Delta^{2}\right)$, every $\delta_{0}>LD^{2}\Delta$ must have

As a result, applying the sequence of steps from the straightforward pattern $h$ from $x_{0}$ yields $\delta_{t}\leq\delta_{0}$. Hence $\|x_{t}-x_{\star}\|\leq D$ since $x_{t}$ lies in the initial level set $\{x\mid f(x)\leq f(x_{0})\}$. Thus the above reasoning can apply inductively, giving the claimed recurrence.

Next, we show this recurrence implies the claimed convergence guarantee (2.3). Suppose first, $\delta_{st}$ is larger than $LD^{2}\Delta$. Then applying the pattern $h$ contracts the objective gapInterestingly, this contraction factor is independent of $L,D$. As a result, problem conditioning plays a minimal role in this initial phase of convergence. Instead, only $h$ and the associated straightforwardness parameter $\Delta$ matter., inductively giving $\delta_{st}\leq(1-\sum_{i=0}^{t-1}(h_{i}-\epsilon)\Delta)^{s}\delta_{0}$. After at most $\bar{s}$ executions of the stepsize pattern, one must have $\delta_{st}\leq LD^{2}\Delta$. Afterward, for any $s>\bar{s}$, the objective gap decreases by at least

Solving this recurrence with the initial condition $\delta_{\bar{s}t}\leq LD^{2}\Delta$ gives

2 Faster Convergence for Straightforward Patterns given Growth Bounds

Consider any $L$-smooth, convex objective $f$ satisfying (2.5). If $h=(h_{0},\dots,h_{t-1})$ is $\epsilon$-straightforward with parameter $\Delta\in(0,1/2]$, then gradient descent (1.3) has, for any $T=st$

when $q=2$ and when $q>2$ and $s>\bar{s}:=\left\lceil\frac{\log\left(\frac{f(x_{0})-f(x_{\star})\mu^{2/(q-2)}}{q^{2/(q-2)}(L\Delta)^{q/(q-2)}}\right)}{\log(1-\sum_{i=0}^{t-1}(h_{i}-\epsilon)\Delta)}\right\rceil$ has

Let $D_{k}=\sup\{\|x-x_{\star}\|\mid f(x)\leq f(x_{k})\}$ denote the size of each level set visited by gradient descent. The growth bound (2.5) ensures $D_{k}\leq(\frac{q}{\mu}\delta_{k})^{1/q}$. Then the recurrence (2.4) implies

One can bound this recurrence relation by the maximum of the two cases. If $q=2$, both cases give a contraction and so

Solving this recurrence gives linear convergence until the objective gap is less than $\left(\frac{q^{2/q}L\Delta}{\mu^{2/q}}\right)^{\frac{q}{q-2}}$ is reached, which must occur by iteration $\bar{s}$, and then afterwards gives a sublinear convergence rate (for example, see [34, Lemma A.1] for this calculation), giving the claim. ∎

Note that the above bound for the case of $q>2$ is independent of $D$. Asymptotically, this is reasonable as better bounds on distance to optimal are eventually available, namely $(\frac{q}{\mu}\delta_{k})^{1/q}$. One could give a bound depending on $D=D_{0}$ early onby using the stronger bound $D_{k}\leq\min\{(\frac{q}{\mu}\delta_{k})^{1/q},D_{0}\}$. However, once the gap is small enough for the first term to dominate, the bound will again be independent of $D_{0}$.

Certificates of Straightforwardness

All that remains is to show how one can certify the straightforwardness of a stepsize pattern. We do this in two steps. First, Section 3.1 shows that $p_{L,D}(\delta)$ is upper bounded by an SDP minimization problem using previously developed PEP techniques. Hence straightforwardness is implied by showing the SDP corresponding to each $\delta\in[0,LD^{2}\Delta]$ has a sufficiently good feasible solution. Second, Section 3.2 shows that another semidefinite programming feasibility problem can certify that such an interval of solutions exists.

We first reformulate the infinite-dimensional problem (2.1) as a finite-dimensional nonconvex quadratically constrained quadratic problem (see (3.1)), relax that formulation into an SDP (see (3.2)), and then upper bound the SDP by its dual problem (see (3.3)). This process was been developed by and is carried out in our particular setting below.

Step 1: A QCQP reformulation. First, as proposed by Drori and Teboulle , one can discretize the infinite-dimensional problem defining $p_{L,D}(\delta)$ over all possible objective values $f_{k}$ and gradients $g_{k}$ at the points $x_{k}$ with $k\in I_{t}^{\star}:=\{\star,0,1,\dots t\}$ as done below. Using the interpolation theorem of Taylor et al. , this is an exact reformulation rather than a relaxation, giving

where, without loss of generality, we have fixed $x_{\star}=0,f_{\star}=0,g_{\star}=0$.

Step 2: An SDP relaxation. Second, one can relax the nonconvex problem (3.1) to the following SDP as done in . We follow the particular notational choices of , which recently considered globally, numerically optimizing gradient descent’s stepsizes with fixed total iterations, defining

with the following notation for selecting columns and elements of $H$ and $F$:

This notation ensures $x_{i}=H\mathbf{x}_{i}$, $g_{i}=H\mathbf{g}_{i}$, and $f_{i}=F\mathbf{f}_{i}.$ Furthermore, for $i,j\in I_{t}^{\star}$, define

Step 3: The upper bounding dual SDP. Third, note the maximization SDP (3.2) is bounded above by its dual minimization SDP by weak duality, giving

Although it is not needed for our analysis, equality holds here as well (i.e., strong duality holds) due to [2, Theorem 6].

2 An SDP Feasibility Certificate that implies Straightforwardness

We restrict our search for dual certificates bounding $p_{1,1}(\delta)$ to a special case, which we numerically observed to hold approximately at the minimizers of (3.3): given $\delta$, fix $v=\sum_{i=0}^{t-1}(h_{i}+\epsilon)\delta^{2}$ and $w=1-2\sum_{i=0}^{t-1}h_{i}\delta$. Noting this fixed variable setting has $v+\delta w=\delta-\sum_{i=0}^{t-1}(h_{i}-\epsilon)\delta^{2}$, $\epsilon$-straightforwardness follows if one can show feasible solutions with these fixed values exist.

Observe that $Z_{h,\epsilon}(\lambda,\delta)$ is nearly linear: the first entry has the only nonlinear behavior, depending quadratically on $\delta$, with the rest depending only linearly on $\lambda$. Written in block form, we denote

This lemma alone does not directly enable the computation of a convergence-proof certificate. One would need certificates of feasibility for the infinitely many sets given by each $\delta\in[0,\Delta]$. The following theorem shows that the existence of such solutions can be certified via a single feasible solution to yet another semidefinite program.

Let $(\lambda,\gamma)\in\mathcal{S}_{h,\epsilon,\Delta}$. We prove this by showing $\lambda^{(\delta)}:=\lambda+\delta\gamma\in\mathcal{R}_{h,\epsilon,\delta}$ for every $\delta\in[0,\Delta]$ by Lemma 3.1. This amounts to verifying the three conditions defining $\mathcal{R}_{h,\epsilon,\delta}$ for each $\lambda^{(\delta)}$.

First, we check $\sum_{i,j\in I_{t}^{\star}:i\neq j}\lambda^{(\delta)}_{i,j}a_{i,j}=a_{\star,t}-\left(1-2\sum_{i=0}^{t-1}h_{i}\delta\right)a_{\star,0}$. The first equality defining $\mathcal{S}_{h,\epsilon,\Delta}$ ensures this for $\lambda^{(0)}=\lambda$. Adding $\delta$ times the second equality defining $\mathcal{S}_{h,\epsilon,\Delta}$ establishes the equality for every $\lambda^{(\delta)}$ as $\sum_{i,j\in I_{t}^{\star}:i\neq j}(\lambda^{(\delta)}_{i,j}+\delta\gamma_{i,j})a_{i,j}=a_{\star,t}-\left(1-2\sum_{i=0}^{t-1}h_{i}\delta\right)a_{\star,0}$. Second, we check nonnegativity $\lambda^{(\delta)}\geq 0$. This follows by noting $\lambda^{(\delta)}$ is a convex combination of $\lambda$ and $\lambda+\Delta\gamma$, which are nonnegative by construction. Finally, we check the nonlinear (but nearly linear) condition $Z_{h,\epsilon}(\lambda^{(\delta)},\delta)\succeq 0$. We consider the block-form (3.5) of this semidefinite inequality, seeking

Since $m_{h}(\lambda)=0$, using the linearity of $m_{h}$ and $M_{h}$, the above can be expanded to equal

Rescaling the first row and column by $1/\delta$ gives an equivalent condition, which is now linear in $\delta$,

When $\delta=0$ or $\Delta$, this condition is explicitly ensured by the definition of $\mathcal{S}_{h,\epsilon,\Delta}$. Then the linearity and convexity of this condition imply it holds for all intermediate $\lambda^{(\delta)}$, completing the proof. ∎

Note computing a member of $\mathcal{S}_{h,\epsilon,\Delta}$ does not correspond to solving a particular performance estimation problem. Instead, each member provides a “line segment” of solutions to a series of the performance estimation problems $p_{L,D}(\delta)$ for an interval of possible $\delta$ values.

3 Certificates of Straightforwardness Proving Guarantees in Table 1

First, we prove the claimed guarantees for the $t=2$ and $t=3$ stepsize patterns of Table 1 by presenting exact members of $\mathcal{S}_{h,0,\Delta}$. Then, to handle larger values of $t$, we present a simple rounding approach able to produce members of $\mathcal{S}_{h,\epsilon,\Delta}$, often with $\epsilon$ around the accuracy of our SDP solves $\approx 10^{-9}$. This approach produced rational-valued certificates proving the rest of the claimed convergence guarantees in Table 1.

The exact rational arithmetic verifying the correctness of all certificates $(\lambda,\gamma)$ was done in Mathematica 13.0.1.0. Note that the entries in these certificates for $t\geq 7$ are entirely computer-generated and lack real human insight. As an example for reference, the certificate for $t=7$ is included in the appendix. Larger certificates are impractical to include here. For example, our $t=127$ guarantee is certificate $(\lambda,\gamma)$ has $32640$ nonzero entries. Certificates for every pattern in Table 1 and exact verifying computations are available at github.com/bgrimmer/LongStepCertificates.

For any $\eta\in(0,3)$, the stepsize pattern $h=(3-\eta,1.5)$ is straightforward. Hence gradient descent (1.3) alternating between these two stepsizes has every even $T$ satisfy

For any $\eta\in(0,3)$, consider the selection of $(\lambda,\gamma)$ given by

It suffices to show for some $\Delta\in(0,1/2]$, $(\lambda,\gamma)\in\mathcal{S}_{h,0,\Delta}$. One can easily verify the needed equalities and nonnegativities hold for all $0\leq\Delta\leq 1/(6-\eta)$. The first positive semidefiniteness condition of $(\lambda,\gamma)\in\mathcal{S}_{h,0,\Delta}$ amounts to checking every $\eta\in(0,3)$ has

Since this convex condition is linear in $\eta$, it suffices to check it at $\eta=0$ and $\eta=3$. Moreover, for any $\eta\in(0,3)$, note this matrix has exactly two zero eigenvalues with associated eigenvectors spanning $(1/2,1/2,1,0)$ and $(1/2,1/2,0,1)$. The second positive semidefiniteness condition amounts to checking an update to this matrix of size $\Delta$ remains positive semidefinite, namely $\begin{bmatrix}\sum_{i=0}^{t-1}(h_{i}+\epsilon)&m_{h}(\gamma)^{T}\\ m_{h}(\gamma)&M_{h}(\lambda+\Delta\gamma)\end{bmatrix}$ which equals

must be positive semidefinite. One can check this added matrix term is positive semidefinite on the subspace spanned by $(1/2,1/2,1,0)$ and $(1/2,1/2,0,1)$ (again by checking when $\eta=0$ and $\eta=3$ and then using convexity). As a result, positive semidefiniteness is maintained for $\Delta$ small enough. Exact arithmetic verifying all of these claims are given in the associated Mathematica notebook. Hence $(\lambda,\gamma)\in\mathcal{S}_{h,0,\Delta}$, proving the main claim by Theorem 3.1 and the claimed convergence guarantee by Theorem 2.1. ∎

The stepsize pattern $h=(1.5,4.9,1.5)$ is straightforward. Hence gradient descent (1.3) cycling through these three stepsizes has every $T=3s$ satisfy

This result is certified with $\Delta=10^{-4}$ by the following exact values for $(\lambda,\gamma)\in\mathcal{S}_{h,0,\Delta}$ of

Based on numerical exploration, we conjecture that patterns of the form $(3-\eta,1.5)$ are the longest straightforward patterns of length two and $(1.5,5-\eta,1.5)$ are the longest of length three.

The above value of $\epsilon$ is the smallest value with $(\hat{\lambda},\hat{\gamma})\in\mathcal{S}_{h,\epsilon,\Delta}$, since by considering their Schur complements, the two needed positive semidefinite conditions hold if and only if

The stepsize patterns of lengths $t\in\{7,15,31,63,127\}$ in Table 1 are all $\epsilon$-straightforward for $\epsilon\in\{10^{-9},10^{-9},10^{-11},10^{-3},10^{-4}\}$ with $\Delta\in\{10^{-5},10^{-6},10^{-8},10^{-7},10^{-8}\}$. Hence the convergence guarantees claimed in Table 1 hold for each corresponding “long step” gradient descent method.

Certificates $(\hat{\lambda},\hat{\gamma})\in\mathcal{S}_{h,\epsilon,\Delta}$ (produced via the above procedure) with exact arithmetic validation are available at github.com/bgrimmer/LongStepCertificates. ∎

Future Directions

Building on existing performance estimation ideas, we have demonstrated an analysis technique capable of proving convergence of gradient descent using nonconstant, long stepsize patterns, which gain in strength as longer patterns are considered. This runs contrary to widely held intuitions regarding constant stepsize selections and the importance of monotone objective decreases. Instead, we show that long-run performance can improve by periodically taking (very) long steps that may increase the objective value in the short term. We accomplish this via computer-generated proof certificates bounding the effect of many steps collectively by providing solutions for a sequence of related performance estimation problems. We conclude by discussing a few possible future improvements on and shortcomings of this technique.

Possible Extension to More Families of Gradient Methods. Often, analysis techniques for gradient descent and its accelerated variants extend rather directly to constrained minimization or minimizing composite objectives $f(x)+r(x)$ by utilizing projections and proximal operators. PEP techniques naturally extend to these settings. Drori [35, Theorem 2.7 and 2.9] shows the tight convergence rate for projected gradient descent is strictly worse than the unconstrained setting, having rate $LD^{2}/4T$ instead of (1.2). A similar (small) worsening of the optimal rate also holds for accelerated proximal gradient methods . This difficulty appears to extend to our straightforward analysis technique. Figure 2 shows the length two and three stepsize patterns that numerically satisfy a generalized notion of straightforwardness for gradient descent, projected gradient descent, and proximal gradient descent. The set of “straightforward” patterns for constrained is strictly smaller and composite yet strictly smaller. Consequently, strictly less aggressive stepsizes than Table 1 would be required for future projected or proximal extensions.

The PEP framework has previously been successfully employed in handling settings of inexact gradients and relatively smooth optimization (via Bregman divergences) . Determining the degree to which utilizing periodic long steps can improve the convergence of inexact, Bregman, and stochastic variations of gradient descent also provides interesting future directions.

Future Improvements in Analysis Techniques. Future works may improve our analysis by considering other Lyapunov functions. The distance to optimal and norm of the gradient were both used in [4, Chapter 8]. Our proofs are only concerned with the eventual decrease of the objective gap. The analysis of optimal accelerated and subgradient methods relies additionally on the decreasing distance to a minimizer or a decreasing combination thereof. Identifying better Lyapunovs and stepsize patterns guaranteed to eventually decrease them may lead to stronger guarantees.

Future Improvements in Computational Aspects. We observed that numerically computed primal optimal solutions to (3.2) were rank-one for all considered straightforward patterns. This corresponds to the worst-case objective function being essentially one-dimensional. This is in line with many prior PEP-based analyses finding one-dimensional Huber functions often attain the worst-case performance. This property was not used herein but could likely be leveraged to enable customized solvers for evaluating $p_{L,D}(\delta)$ and checking membership of $\mathcal{S}_{h,0,\Delta}$. Such improvements in tractability for SDPs with rank-one solutions have been studied widely and may enable the search for longer, provably faster straightforward stepsize patterns than shown here.

As another avenue of improvement, note that any certificates produced by using floating point arithmetic followed by a rounding step (as done here) will likely lose a small $\epsilon$ amount in the guarantee. The use of an algebraic solver, like SPECTRA , could enable the automated production of exact certificates of straightforwardness as well as being able to certify when $\mathcal{S}_{h,0,\Delta}$ is empty.

The author thanks Jason Altschuler for conversations at the Simons Insitute in Spring 2017 about the preliminary ideas subsequently developed in his excellent Master’s thesis work, Fanghua Chen for preliminary discussions based on numerical observations that motivated this work, and Adrien Taylor and Axel Böhm for providing useful feedback on the initial presentation of this work. The openly released Performance Estimation Problem Branch-and-Bound software of was especially helpful in early explorations and building intuitions.

References

Below is a certificate $(\hat{\lambda},\hat{\gamma})\in\mathcal{S}_{h,\epsilon,\Delta}$, completely computer generated, proving a $LD^{2}/(3.1999999\times T)$ rate for the pattern of length $t=7$ in Table 1. Given the length of these $9\times 9$ matrices, we display their first five and last four columns separately below. Exact calculations verifying the feasibility of these values are given in the associated publicly posted Mathematica notebook.