Control Interpretations for First-Order Optimization
Methods
Bin Hu

Laurent Lessard

arXiv:1703.01670v1 [] 5 Mar 2017

Abstract

Recent efforts have adopted a dynamical system (or
differential equation) perspective in analyzing acceleration for convex objectives [17, 23], though a more general
understanding of acceleration is still lacking (non-convex
objectives, inexact computations, etc). This paper aims
to bring new insights on how to accelerate first-order optimization methods for objective functions which are not
convex in general. Our main contributions are as follows:

First-order iterative optimization methods play a fundamental role in large scale optimization and machine learning. This paper presents control interpretations for such
optimization methods. First, we give loop-shaping interpretations for several existing optimization methods and
show that they are composed of basic control elements
such as PID and lag compensators. Next, we apply the
small gain theorem to draw a connection between the
convergence rate analysis of optimization methods and
the input-output gain computations of certain complementary sensitivity functions. These connections suggest that standard classical control synthesis tools may
be brought to bear on the design of optimization algorithms.

1

1. We pose the iterative optimization paradigm as an
output regulation problem, which lends itself to a
loop-shaping interpretation. In particular, we show
that several popular optimization algorithms may be
viewed as controllers which are composed of basic
PID or lag compensation elements. We also demonstrate that existing parameter tuning guidelines for
these optimization methods are consistent with the
loop-shaping design guidelines in control theory.

Introduction

First-order iterative optimization methods have been
widely applied in data science and machine learning [3,
16]. These methods only require access to first-order
derivative information, and iterate on the data until satisfactory convergence is achieved. For example, the gradient method is
xk+1 = xk − α∇f (xk ).

2. Using the small gain theorem [24], we draw a connection between the convergence rate analysis of optimization methods (under sector-bounded assumptions) and the input-output gain computation for a
particular complimentary sensitivity function. It follows that the design of optimization algorithms for
sector-bounded functions can be interpreted as H∞
state feedback synthesis. This explains why acceleration typically requires stronger function assumptions (not necessarily convexity) beyond just sectorbounded gradients.

(1)

Such simple methods are often favored over higher order
methods such as Newton’s method when the dimension
of the underlying space is large and computing Hessians
is prohibitively expensive.
There has been significant recent interest in finding ways to accelerate the convergence of the gradient
method while maintaining low iteration costs. For example, the Heavy-ball method includes an additional momentum term
xk+1 = xk − α∇f (xk ) + β(xk − xk−1 ).

A related line of research has emerged in the distributed
optimization literature [6, 8, 21, 22]. In [21, 22], a
continuous-time differential equation was used to describe the dynamics of distributed optimization, leading to a natural iterative algorithm which may be interpreted as a PI controller. In [8], event-triggered control methods were tailored for distributed optimization
over networks. In contrast with the work on distributed
optimization, the present work is concerned with controltheoretic properties and interpretations of a big class of
first-order optimization methods.
A second related line of research is the unified integral
quadratic constraint framework in [10], which provides
a numerical tool based on semidefinite programming for
use in analyzing optimization algorithms. In contrast

(2)

This slight modification can yield a dramatic improvement in worst-case convergence rate if f is quadratic.
A similar acceleration scheme, Nesterov’s accelerated
method, can improve the convergence rate for strongly
convex f with smooth gradients [10, 13]. These convergence results are derived on a case-by-case basis, and the
intuition behind the acceleration is still not fully understood.
1

L(L). For all f ∈ F(m, L), the following inequality holds
for all x ∈ Rp

T 


x − x?
−2mLIp (L + m)Ip x − x?
≥ 0 (7)
∇f (x)
(L + m)Ip
−2Ip
∇f (x)

with this work, the present work uses a small gain approach with a simple interpretation that interfaces with
existing results on complementary sensitivity integrals.
The paper is organized as follows. Section 2 explains
notation and problem formulation, Section 3 describes
our loop-shaping interpretation for first-order methods,
and Section 4 presents our main results involving the
small gain theorem and connections to complementary
sensitivity.

2
2.1

where Ip denotes the p × p identity matrix [10, Lemma
6]. On the other hand, a function satisfying the above
inequality may not belong to F(m, L), and may not even
be convex. The set of continuously differentiable functions satisfying (7) is denoted as S(m, L). This class
of functions has sector-bounded gradients, and includes
F(m, L) as a subset.

Preliminaries
Spaces and operators

2.3

Let `p2e denote the sequences x := (x0 , x1 , . . . ) ⊆ Rp , and
the set of square-summable sequences, so
let `p2 ⊆ `p2e be P
∞
if x ∈ `p2 , then k=0 kxk k2 < ∞ where kxk k2 := (xk )T xk

A classical way to solve (4) is the gradient descent
method, which uses the iteration (1) to gradually converge to x? . The intuition behind gradient descent
method is as follows. At each step k, we find a quadratic
approximation of f about xk , which hopefully captures
the local structure of f , and we solve the quadratic minimization problem


1
k
2
k
k T
k
kx − xk . (8)
min f (x ) + ∇f (x ) (x − x ) +
x∈Rp
2α

denotes the standard Euclidean norm. We will omit the
superscript p when it is implied by context. The gain of
a causal operator K : `2e → `2e is defined as
kKk :=

kKxk
x∈`2 ;x6=0 kxk
sup

(3)

In addition, K is said to be bounded if it has a finite
gain. Notice this gain is induced by `2 signals while the
operator K itself is defined on `2e . This definition makes
sense since any bounded operator on `2 to itself has a
natural causal extension to the operator from `2e to `2e .
Clearly, every bounded operator must map zero inputs
to zero outputs.
2.2

When f ∈ S(m, L), if α is chosen well, then there exists
a constant ρ ∈ (0, 1) and a constant c ≥ 1 such that
kxk − x? k ≤ cρk kx0 − x? k

Consider the unconstrained optimization problem
min f (x)

(4)

where it is assumed that there exists a unique x? ∈ Rp
satisfying ∇f (x? ) = 0. How to solve (4) and find x?
heavily depends on the assumptions about f . A simple
assumption is that f is quadratic. Two other common
assumptions are L-smoothness and strong convexity. A
continuously differentiable function f : Rp → R is Lsmooth if the following inequality holds for all x, y ∈ Rp

xk+1 = y k − α∇f (y k )
y k = (1 + β)xk − βxk−1
√

k∇f (x) − ∇f (y)k ≤ Lkx − yk.

m
kx − yk2 .
2

√

(10)

m
√ . When L/m is large, Neswhere α = L1 and β = √L−
L+ m
terov’s accelerated method guarantees a much faster convergence rate compared to the gradient descent method.
This fact was stated in [13, Theorem 2.2.3].
When f is a quadratic function, one can accelerate
the gradient descent method by incorporating a momentum term into the iteration, such as the Heavy-ball
method (2). Although the Heavy-ball method works extremely well for quadratic objective functions, it can fail
to converge for other functions in F(m, L); see [10, Section 4.6].
The intuitions behind Nesterov’s accelerated method
and the Heavy-ball method are still not fully understood.

(5)

We define L(L) to be the set of L-smooth functions. The
continuously differentiable function f is m-strongly convex if the following inequality holds for all x, y ∈ Rp
f (x) ≥ f (y) + ∇f (y)T (x − y) +

(9)

Thus the iterates {xk } converge exponentially to x? . By
convention, this is known as linear convergence in the
optimization literature. For example, we can choose α =
2
L−m
L+m and obtain ρ = L+m and c = 1. Another popular
choice is α = L1 , which leads to ρ = 1 − m
L and c = 1.
These results are formally documented in [10, Section
4.4]. It is emphasized that the proofs of these results
only require (7).
When f ∈ F(m,
one can achieve a better converq L),p
gence rate ρ = 1 − m
L using Nesterov’s accelerated
method:

Various objective functions in optimization

x∈Rp

Review of first-order optimization methods

(6)

Note that we recover ordinary convexity in (6) if m = 0.
We define F(m, L) to be the set of functions that are both
L-smooth and m-strongly convex. The class F covers a
large family of objective functions in machine learning,
including `2 -regularized logistic regression [20], smooth
support vector machines [9], etc. Clearly, F(m, L) ⊂
2

Hence, there is no intuitive way to modify these methods
to accelerate the convergence when optimizing more general functions, i.e. f ∈ S(m, L) or f ∈ S(m, L) ∩ L(L).
Gaining intuition for these methods can be beneficial for
designing accelerated schemes for more general classes of
objective functions.
Finally, it is worth mentioning that every optimization
method mentioned in this section can be cast as the feedback interconnection Fu (P, K) as shown in Fig 1. Here,
P := ∇f is a static nonlinearity and K is a linear timeinvariant (LTI) system (the algorithm).

The above inequality is important for further analysis of
optimization methods.
2.4

The key analysis tool in this paper is the small gain theorem, which is now briefly reviewed. Suppose two causal
operators P : `2e → `2e and K : `2e → `2e both map zero
input to zero output. Let [P, K] denote the feedback
interconnection of P and K illustrated in Fig. 2:

v = Pu + e
(13)
u = Kv + r.

- ∇f
u

Input-output stability and small gain theorem

v
K



r

Figure 1: Feedback representation for the optimization
method Fu (∇f, K).

d?


e

The interconnection [P, K] is said to be well-posed if
the map (u, v) 7→ (r, e) defined by (13) has a causal
inverse on `2e . It is (input-output) stable if it is wellposed and this inverse causal map from (r, e) to (u, v) is
bounded. Clearly, u, v ∈ `2 for all r, e ∈ `2 if [P, ∆] is
stable. Well-posedness holds only if the solutions to (13)
have no finite escape time. The small gain theorem states
the following [7, 24].

(11)
k

- P

Figure 2: Feedback interconnection with exogenous inputs

ξ k+1 = Aξ k + Bv k
k

u

v
K 

Feedback representations for optimization methods are
discussed in [10, Section 2]. In [10], P is a static nonlinear operator that maps u to v = P u as v k = ∇f (uk ).
However, this is not a bounded operator since it does not
map zero inputs to zero outputs. For the convenience of
our discussion, we will choose P to be the operator which
maps u to v = P u as v k = ∇f (uk + x? ) where x? is the
unique point satisfying ∇f (x? ) = 0. Then this choice of
P leads to a bounded operator. One can perform a state
shifting argument to the feedback representations in [10]
and cast all the mentioned optimization methods as
uk = Cξ k

-d
6

Theorem 1 (small gain theorem). Suppose P and K
are bounded causal operators and [P, K] is well-posed. If
kP kkKk < 1, then [P, K] is input-output stable.

?

v = ∇f (u + x )
where (A, B, C) are the state matrices of K. For example, to rewrite the gradient descent method (1), one can
set ξ k = uk = xk − x? and v k = ∇f (xk ) = ∇f (uk +
x? ). Then (1) can be cast as (11) with (A, B, C) =
(Ip , −αIp , Ip ). Notice here ξ k = xk − x? and hence the
convergence rate of the optimization algorithm is equivalent to the rate at which ξ k goes to 0. The optimization
method converges to the optimum x? at a rate ρ if and
only if the model (11) drives ξ k to 0 from any initial conditions at the same rate ρ. Using similar arguments, Nesterov’s accelerated method and the Heavy-ball method
can be written as (11). In these two cases, the associated
state matrices for K are the same as (2.5) and (2.7) in
[10], although the states have been shifted by x? . When
f ∈ S(m, L), the inequality (7) imposes a sector bound
on the input/output pair of P . Let v = P u. Then the
following inequality holds for all k
 
 k T 
u
−2mLIp (L + m)Ip uk
≥ 0.
(12)
(L + m)Ip
−2Ip
vk
vk

The small gain theorem can be used to check the inputoutput stability of [P, K] when the gains of P and K are
both known. Note that there are exogenous signals r,
e in the setup of [P, K] and zero initial conditions on
K to ensure that K maps the zero input to a zero output. In contrast, Fu (P, K) allows any initial condition
for K, so the optimization method Fu (P, K) can be initialized at any initial condition ξ 0 ∈ Rn . For any optimization method Fu (P, K) described by (11), one can
form an associated interconnection [P, K] by adding the
signals (r, e) and fixing the initial condition of K to be
zero, since the nonlinear static map P is set up in a way
to map zero inputs to zero outputs. An important connection between the internal stability of Fu (P, K) and
the input-output stability of [P, K] has been stated in [2,
Proposition 5]. Consequently, one may apply the small
gain theorem for the convergence rate analysis of optimization methods.
3

3

Loop-shaping interpretations for
optimization methods

plant P becomes a linear operator in this case. However,
the lag compensator increases the slope of the loop gain
near the crossover frequency, which may have a detrimental effect on the robustness of the closed loop. This
qualitative observation is confirmed by the fact that the
Heavy-ball method may fail to converge at all if the objective function is relaxed to include more general strongly
convex functions [10].
Unlike the Heavy-ball method, Nesterov’s accelerated
method performs well when applied to strongly-convex
objective functions. A control interpretation is that Nesterov’s accelerated method includes derivative control to
decrease the slope of the loop gain near the crossover
frequency, which significantly improves the robustness of
the algorithm for certain classes of nonlinearities. To
see the derivative controller in Nesterov’s accelerated
method, rewrite (10) as

This section presents basic control interpretations for the
gradient descent method, Nesterov’s accelerated method,
and the Heavy-ball method with the hope of shedding
light on the general principles underlying the design of
first-order methods. The goal of the optimization method
is to find x? satisfying ∇f (x? ) = 0. Hence the optimization method may be viewed as a controller that regulates the plant “∇f ” to zero. When viewing ∇f as the
plant one wants to control, the unconstrained optimization problem (4) is an output regulation problem, and
the LTI part K in the first-order optimization method
can be viewed as a controller. The key issue for this output regulation problem is that the equilibrium point x?
is unknown.
Transfer functions for the controller K are listed in
Table 1. We use the symbol ⊗ to denote the Kronecker
product. These products appear because the controllers
corresponding to our algorithms of interest are repetitions of a single-input-single-output (SISO) system.

y k+1 = y k + β(y k − y k−1 ) − α∇f (y k )
− αβ(∇f (y k ) − ∇f (y k−1 ))

The last term is a difference of the plant output ∇f , and
can be viewed as a derivative control.
Nesterov’s method may also be interpreted as lag compensation together with integral action, as in the Heavyball case. The corresponding controller is



(1 + β)z − β
−α
,
(16)
K = Ip ⊗
z−1
z−β

Table 1: Transfer function K(z) for first-order methods
Optimization Method

Controller K

Gradient Descent

Ip ⊗

−α
z−1

Heavy-Ball

Ip ⊗

−αz
z 2 −(1+β)z+β

Nesterov’s Method

Ip ⊗

−α(1+β)z+αβ
z 2 −(1+β)z+β

(15)

β
, and this helps increase the
which has a zero at z = 1+β
slope of the Bode plot near the crossover frequency. The
control interpretations for different optimization methods
are summarized in Table 2.

For the gradient descent method, K is a pure integrator. Hence, the gradient descent regulates the nonlinear
plant P via pure integral control. Integral action is necessary since the algorithm must converge to x? , which
amounts to having zero steady-state error when K tracks
a step input.
The Heavy-ball method (2) differs from gradient descent in the inclusion of an additional momentum term.
This momentum term may be viewed as a lag compensator. The Heavy-ball method corresponds to the following controller:



−α
z
K = Ip ⊗
(14)
z−1
z−β

Table 2: Control interpretations for first-order methods
Optimization Methods Control Structure
Gradient Descent
Heavy-Ball
Nesterov’s Method

Integral Control
Lag + Integral Control
Lag + PID Control

We now demonstrate that the design of state-of-the-art
optimization methods is actually consistent with general
loop-shaping principles from control theory. The loopshaping principle states that the low-frequency loop gain
should be sufficiently large to ensure good tracking performance while the high-frequency loop gain should be
small enough for the purpose of noise rejection. In addition, the slope of the loop gain near the crossover frequency should be flat (typically around −20 dB/decade)
to assure a proper phase margin and good robustness.
A thorough discussion on loop-shaping can be found in
standard references [4, 14, 15].
Given a function f ∈ F(m, L), the standard gradient
descent stepsize is α = L1 , and the standard parameter choice for Nesterov’s accelerated method is α = L1

The first term provides integral action to ensure zero
steady-state error as with the gradient method, while
the second term is a discrete-time lag compensator. The
lag compensation has the net effect of 1) boosting low1
, which imfrequency response by a factor of roughly 1−β
proves the tracking speed of the controller and hence the
convergence of the algorithm and 2) attenuating high1
frequency response by a factor of roughly 1+β
. It intuitively makes sense that the Heavy-ball method can
accelerate convergence for quadratic objectives, since the
4

√

√

m
√ . Other parameter choices, when f is
and β = √L−
L+ m
quadratic for example, are documented in [10, Proposition 1]. Fig. 3 shows the Bode plots of the resultant
controllers K (only the SISO part) for all these parameter choices under the assumption that m = 0.01 and
L = 1.

70

Magnitude (dB)

50

The Bode plots are consistent with the properties of
these optimization methods when a loop-shaping intuition is adopted. First, the gradient descent method with
the standard stepsize α = L1 is known to be slower than
other first-order methods when f is quadratic. This is
reflected in the Bode plot, which shows that the gradient
method has a relatively low gain particularly in the low2
frequency region. Using the optimal tuning of α = L+m
improves the gain slightly.

20

-10
90

Phase (deg)

75
60
45
30
15
0
10 -3

10 -2

10 -1

10 0

Frequency (Hz)

Figure 3: Bode plots of K for various first-order methods
with commonly-used parameter tunings.

4.1

New feedback representations for first-order
methods

The feedback representation (11) for first-order methods involves a nonlinear operator P which belongs to
the sector (m, L) (12). This does not coincide perfectly
with a gain bound since upper and lower bounds don’t
match. We will therefore, use a loop-shifted Fu (P 0 , K 0 )
that ensures the small gain condition on P 0 captures
the full sector. Choose P 0 to map u to v = P u as
2
v k = uk − m+L
∇f (uk + x? ). Then, substitute ξ k =
uk = xk − x? into the gradient descent method (1) to get
an alternative feedback interconnection

(17)


ξ k+1 = 1 −

(m+L)α
2



ξk +

(m+L)α k
v
2

(18)

uk = ξ k

It remains an open question as to how to choose an appropriate K(z) subject to different assumptions on the
objective function. Since acceleration schemes for the optimization of quadratic functions or functions in F(m, L)
already exist, we will focus on the case f ∈ S(m, L). We
will derive one connection between such an optimization
design problem and classical control synthesis theory.

4

30

0

In summary, the intuition brought by the traditional
loop-shaping theory is consistent with the known properties of the existing first-order methods. This suggests
that loop-shaping intuition may be used as a general
high-level guideline in the design of optimization methods. The control interpretations above also indicate that
classical PID tuning [1] can be used for optimization algorithm design. For example, one could drop the lag
compensation and simply use the PID controller:
−α(1 + β)z + αβ
z(z − 1)

40

10

Second, the optimal quadratic tuning for all three
methods leads to controllers whose crossover frequencies
are roughly at 0.5 Hz. Intuitively, such tuning places excessive weight on tracking performance and is very fragile
to noise at the output of the plant P . This is consistent
with the known robustness properties of these methods
as well. For example, the gradient method with α = L1
is known to be very robust to the noise in the gradient
2
computation while the gradient method with α = m+L
is
known to be fragile to such noise [10, Section 5.2]. Comparing the high frequency responses of these two cases
immediately leads to the same conclusion. Finally, the
slope of Bode plot at the crossover frequency supports
the fact that Nesterov’s method works for a larger class
of functions than the Heavy-ball method.

K(z) = Ip ⊗

Gradient, standard tuning
Nesterov, standard tuning
Gradient, optimal tuning for quadratics
Nesterov, optimal tuning for quadratics
Heavy-ball, optimal tuning for quadratics

60

k

k

v =u −

k

2
L+m ∇f (u

?

+x )

Direct manipulation of (7) shows that P 0 is in a sector
L−m
L−m
0
(− L−m
L+m , L+m ), which leads to gain bound kP k ≤ L+m .
Suppose K = Ip ⊗ K̄ where K̄ is a SISO LTI system. In
general, a loop transformation argument can be used to
show that any optimization method Fu (P, K) can also
be represented as Fu (P 0 , K 0 ) where K 0 = Ip ⊗ K̄ 0 and
2
K̄ 0 = K̄/(K̄ − m+L
). Consequently, the feedback interconnection (18) provides another way to model first-order
methods.

Analysis and design of optimization
methods using the small gain theorem

In this section, it is assumed that f ∈ S(m, L) and x? is
the unique point satisfying ∇f (x? ) = 0.
5

4.2

When ρ > 12 (1− κ1 ), K̄ 0 (ρz) is stable. In addition, one can
substitute z = 1 into (22) to obtain the peak frequency
response (the H∞ norm) of K̄ 0 (ρz). To ensure this norm
L+m
, one has the condition
is smaller than L−m

Main theorem

Our main approach is inspired by the loop transformation
used in [2, 5]. For any ρ ∈ (0, 1), the operators ρ+ and ρ−
are defined as the time-domain, time-dependent multipliers ρk , ρ−k , respectively. Here, superscripts indicate k-th
power. Define Kρ0 := ρ− ◦ K 0 ◦ ρ+ , and Pρ0 := ρ− ◦ P 0 ◦ ρ+ .
From [2, Section 3], one can conclude Fu (P 0 , K 0 ) converges at rate ρ if [Pρ0 , Kρ0 ] is input-output stable and
Kρ0 (z) = K 0 (ρz). Similarly, define K̄ρ0 := ρ− ◦ K̄ 0 ◦ ρ+ ,
and one has K̄ρ0 (z) = K̄ 0 (ρz). The main result of this
paper is stated below.

1+κ
κ+1
<
.
2ρκ − κ + 1
κ−1

Upon simplifying (23) together with ρ > 21 (1 − κ1 ), we
finally obtain ρ > 1 − κ1 , which is the linear convergence
rate for the gradient descent method when α = L1 .
Remark 1. A small technical issue in the above analysis is that the rate result proved by the small gain theorem is a strict inequality. This is due to the fact that
for LTI systems, input-output stability is slightly stronger
than the global uniform stability. See [5, Remark 1] for
a detailed explanation. This issue is negligible from a
practical standpoint.

2
), and K 0 =
Theorem 2. Let K̄ 0 = K̄/(K̄ − m+L
L+m
0
0
Ip ⊗ K̄ . If kK̄ρ k < L−m , then the optimization method
Fu (P 0 , K 0 ) has a linear convergence rate ρ.

Proof. Notice P 0 is a pointwise nonlinearity, and hence
one can use the small gain condition on P 0 to show
kPρ0 k ≤ L−m
L+m (see Section 5.1 in [2] or Section IV.C
in [5] for detailed arguments). In addition, kKρ0 k =
L+m
kIp ⊗ K̄ρ0 k = kK̄ρ0 k < L−m
, and kKρ0 kkPρ0 k < 1. By
0
the small gain theorem, [Pρ , Kρ0 ] is input-output stable.
By [2, Proposition 5], Fu (P 0 , K 0 ) converges at rate ρ.

4.4

Recovery of rate results for gradient descent

As a sanity check, we apply Theorem 2 to recover convergence rate results for the gradient descent method applied
−α
to functions in S(m, L). Since K̄(z) = z−1
, we have
K̄ 0 (z) =
If α =

2
m+L ,

α(m + L)
2z − 2 + α(m + L)

(19)

it is straightforward to obtain
K̄ 0 (z) =

1
,
z

K̄ 0 (ρz) =

1
ρz

(20)

Clearly, K̄ 0 (ρz) is stable for any ρ > 0. Moreover,
kK̄ 0 (ρz)k = ρ−1 . By Theorem 2, the gradient descent
method converges for any ρ > L−m
L+m . This recovers the ex2
isting rate result for the gradient method with α = L+m
.
1
Another popular choice for α = L . In this case, the
shifted controller is given by
1+κ
K̄ 0 (z) =
(21)
2z − κ + 1
where κ :=

L
m

5

1+κ
2ρκz − κ + 1

Conclusion

This paper discussed connections between the analysis
of optimization algorithms and classical control-theoretic
concepts. Specifically, the gradient method, the Heavyball method, and Nesterov’s accelerated method were interpreted as combinations of PID and lag compensators.

is the condition number. Hence, one has
K̄ 0 (ρz) =

Connections to complementary sensitivity

2
), K̄ 0 (ρz) is
Since we have K̄ 0 (ρz) = K̄(ρz)/(K̄(ρz)− m+L
the complementary sensitivity function of the closed-loop
system Fu (K̄(ρz), − m+L
2 ). Accelerating optimization for
f ∈ S(m, L) requires finding the smallest ρ such that
there exists K̄(ρz) that stabilizes K̄ 0 (ρz) while ensuring
L+m
that kK̄ 0 (ρz)k < L−m
. One possible method would be
to perform a bisection search on ρ. For each ρ, we can
try to design K̄ to stabilize K̄ 0 (ρz) and minimize the
H∞ -norm of K̄ 0 (ρz) at the same time. This subproblem
may be reformulated as an H∞ state feedback synthesis
problem since K̄ always contains a pure integrator and
1
the state of the scaled dynamics ρz−1
is accessible at
every timestep. Consequently, the only design variable is
the state feedback gain, which happens to be the stepsize
of the gradient method. This explains why acceleration in
this case is difficult even given memory of past iterates.
It is worth noting that K̄(ρz) always has an unstable
pole at z = ρ−1 . There is a large body of discrete-time
complementary sensitivity integral results [11, 12, 18, 19]
which could potentially be used in studying the design
limits of K̄ under the analytic constraints posed by the
unstable pole at ρ−1 .
From the above connection, we can see that acceleration typically requires some function properties which
can be decoded as constraints involving dynamics. The
condition (7) is a static constraint, and it is hard to
design accelerated schemes with this single constraint.
However, it is still possible to accelerate non-convex optimization when other function properties are available,
e.g. f ∈ L(L).

The power of Theorem 2 is that it connects the convergence rate analysis of the optimization method to
an input-output gain computation on a SISO system
K̄ρ0 . Note that the `2 -induced norm (3) of a stable LTI
system is equal to its H∞ -norm [25]. In addition, we
have K̄ρ0 (z) = K̄ 0 (ρz). Hence we only need to verify
that K̄ 0 (ρz) is stable and then compare the H∞ -norm of
L+m
K̄ 0 (ρz) to L−m
.
4.3

(23)

(22)

6

A loop-shaping interpretation was also used to explain
several well-known robustness properties of these algorithms.
We invoked the small gain theorem to show that finding worst-case convergence rates for algorithms amounts
to computing the gain of a complementary sensitivity
function. In addition, we demonstrated a connection between H∞ state feedback synthesis and stepsize selections
of the gradient method. These observations are an encouraging first step toward leveraging tools from control
theory for the analysis and eventual synthesis of robust
optimization algorithms.

[12] C. Mohtadi. Bode’s integral theorem for discretetime systems. In IEE Proceedings D-Control Theory
and Applications, volume 137, pages 57–66, 1990.
[13] Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2003.
[14] N. Nise. Control systems engineering. John Wiley
& Sons, 2007.
[15] K. Ogata. Modern control engineering. PrenticeHall, 5th edition, 2010.
[16] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms.
Cambridge University Press, 2014.

References
[1] K. Ang, G. Chong, and Y. Li. PID control system analysis, design, and technology. IEEE Transactions on Control Systems Technology, 13(4):559–
576, 2005.

[17] W. Su, S. Boyd, and E. Candès. A differential
equation for modeling Nesterov’s accelerated gradient method: Theory and insights. In Advances
in Neural Information Processing Systems 27, pages
2510–2518, 2014.

[2] R. Boczar, L. Lessard, and B. Recht. Exponential
convergence bounds using integral quadratic constraints. In IEEE Conference on Decision and Control, pages 7516–7521, 2015.

[18] H. Sung and S. Hara. Properties of sensitivity and
complementary sensitivity functions in single-input
single-output digital control systems. International
Journal of Control, 48(6):2429–2439, 1988.

[3] S. Bubeck. Convex optimization: Algorithms and
complexity. Foundations and Trends R in Machine
Learning, 8(3-4):231–357, 2015.

[19] H. Sung and S. Hara. Properties of complementary
sensitivity function in SISO digital control systems.
International Journal of Control, 50(4):1283–1295,
1989.

[4] G. Franklin, J. Powell, and A. Emami-Naeini. Feedback control of dynamic systems. Pearson Higher
Education, Inc, 6th edition, 2010.

[20] C. Teo, A. Smola, S. Vishwanathan, and Q. Le. A
scalable modular convex solver for regularized risk
minimization. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
pages 727–736, 2007.

[5] B. Hu and P. Seiler. Exponential decay rate conditions for uncertain linear systems using integral
quadratic constraints. IEEE Transactions on Automatic Control, 61(11):3631–3637, 2016.

[21] J. Wang and N. Elia. Control approach to distributed optimization. In Allerton Conference on
Communication, Control, and Computing, pages
557–561, 2010.

[6] D. Jakovetić, J. Moura, and J. Xavier. Linear convergence rate of a class of distributed augmented
Lagrangian algorithms. IEEE Transactions on Automatic Control, 60(4):922–936, 2015.

[22] J. Wang and N. Elia. A control perspective for
centralized and distributed convex optimization. In
IEEE Conference on Decision and Control, pages
3800–3805, 2011.

[7] H.K. Khalil. Nonlinear Systems. Prentice Hall, third
edition, 2001.
[8] S. Kia, J. Cortés, and S. Martı́nez. Distributed convex optimization via continuous-time coordination
algorithms with discrete-time communication. Automatica, 55:254–264, 2015.

[23] A. Wibisono, A. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of
Sciences, 113(47):E7351–E7358, 2016.

[9] Y. Lee and O. Mangasarian. SSVM: A smooth
support vector machine for classification. Computational Optimization and Applications, 20(1):5–22,
2001.

[24] G. Zames. On the input-output stability of timevarying nonlinear feedback systems part one: Conditions derived using concepts of loop gain, conicity, and positivity. IEEE Transactions on Automatic
Control, 11(2):228–238, 1966.

[10] L. Lessard, B. Recht, and A. Packard. Analysis
and design of optimization algorithms via integral
quadratic constraints. SIAM Journal on Optimization, 26(1):57–95, 2016.

[25] K. Zhou, J.C. Doyle, and K. Glover. Robust and
Optimal Control. Prentice-Hall, 1996.

[11] R. Middleton. Trade-offs in linear control system
design. Automatica, 27(2):281–292, 1991.
7

