Week 3.

Gradient methods
MATH3191/5191 Mathematical Optimization for Data Science

A/Prof. Vera Roshchina

School of Mathematics and Statistics, UNSW Sydney

Term 3 2024

1/25
Introduction
We consider an unconstrained optimisation problem,

min f (x),
x∈Rn

where the function f : Rn → R is continuously differentiable.

2/25
Descent and ascent directions

Consider a function f : Rn → R. A point (direction) d ∈ Rn is called a descent

direction for f at x if there exists some t0 > 0 such that

f (x + td) < f (x) for t ∈ (0, t0 ).

If d ∈ Rn is a descent direction, and the function f is differentiable at x, then

f (x + td) − f (x)
f ′ (x; d) = ∇f (x) · d = lim ≤ 0.
t↓0 t

Ascent directions are defined similarly (with the opposite signs).

3/25
Descent directions for a smooth function
Theorem 2.1
If f : Rn → R is continuously differentiable, then any d ∈ Rn such that

f ′ (x; d) = ∇f (x) · d < 0

is a descent direction.

4/25
Steepest Descent Direction
The steepest descent direction is the one along which the function decreases the most
rapidly.

If we restrict the directions to unit vectors, then for a continuously differentiable

function f : Rn → R the steepest descent direction is the solution to the optimisation
problem
min ∇f (x) · d.
∥d∥=1

5/25
Steepest Descent Method
A steepest descent (or gradient descent) method takes steps along the steepest
descent direction, so for some continuously differentiable function f : Rn → R and a
starting point x0 ∈ Rn we let

xk+1 = xk − αk ∇f (xk ),

where αk > 0 is called the steplength.

6/25
Choosing the steplength

7/25
More on line search
Exact line search
min f (x k + αd)
α>0

Approximate line search

Backtracking line search

8/25
Constant steplength, L-smooth function
Recall that a function f : Rn → R is L-smooth if ∥∇f (x) − ∇f (y )∥ ≤ L∥x − y ∥ for
any x, y ∈ Rn . For an L-smooth function for any x, y ∈ Rn we have
L
f (y ) ≤ f (x) + ∇f (x) · (y − x) + ∥y − x∥2 .
2

9/25
Constant steplength, continued

10/25
Convergence to the solution
For a sequence of points (xk ) generated by the gradient descent method (for some
L-smooth function bounded from below) with α = 1/L, all accumulation points of (xk )
are stationary, that is, ∇f (x̄) = 0 for any accumulation point x̄.

11/25
Convex Case
Theorem 2.2
Suppose that f : Rn → R is convex and L-smooth, and assume that there exists a
(global) minimiser x ∗ of f on Rn . Then the steepest descent method with constant
steplength α = 1/L generates a sequence {xk }∞ k=0 that satisfies

L
f (xk ) − f (x ∗ ) ≤ ∥x0 − x ∗ ∥2 , k = 1, 2, . . . .
2k

12/25
Convex case continued

13/25
Strongly convex case
Recall that a continuously differentiable f : Rn → R is strongly convex with modulus
µ if
µ
f (y ) ≥ f (x) + ∇f (x) · (y − x) + ∥y − x∥2 .
2
Alternatively
1
f ((1 − α)x + αy )) ≤ (1 − α)f (x) + αf (y ) − µα(1 − α)∥x − y ∥2 .
2

14/25
Properties of strongly convex functions
Let f : Rn → R be continuously differentiable and strongly convex with modulus µ.
Then for any x ∈ Rn we have

∥∇f (x)∥2
f (x) − f (x ∗ ) ≤ ,
2µ
2
∥x − x ∗ ∥ ≤ ∥∇f (x)∥.
µ

15/25
Strongly convex case: proof continued

16/25
More on convergence with α = 1/L for strongly convex functions
Recall that if f is L-smooth and bounded from below, then
r
2L
∥∇f (xi )∥ ≤ (f (x0 ) − f¯) for some i ∈ {1, . . . , k − 1}.
k

If f is convex and L-smooth, and has a minimiser x ∗ , then

L
f (xk ) − f (x ∗ ) ≤ ∥x0 − x ∗ ∥2 , k = 1, 2, . . . .
2k
If f is continuously differentiable and strongly convex with modulus µ, and has a
minimiser x ∗ . Then for any x ∈ Rn we have
∥∇f (x)∥2
f (x) − f (x ∗ ) ≤ ,
2µ
2
∥x − x ∗ ∥ ≤ ∥∇f (x)∥.
µ
17/25
When the function is L-smooth and strongly convex

18/25
Example: logistic regression
Logistic regression is a classification problem where the classifier predicts the odds that
a data point belongs to one of two classes. We are given a training set of points
{(xi , yi )}ki=1 , with xi ∈ Rn for all i ∈ {1, . . . , k} and yi ∈ {−1, 1}. The classifier is an
‘odds’ function p,
1
p(x, u) = .
1 + e x·u
We want to choose u in such a way that p(xi , u) is close to 1 when yi = 1 and close to
0 when yi = −1.

19/25
Negative log-likelihood function
 
1 X X
L(u) = −  ln(1 − p(xj , u)) + ln(p(xj , u))
k
j:yj =−1 j:yj =1

20/25
Multiclass logistic regression
Assign an odds function pk to each class {1, . . . , N}. These functions are parametrised
by the vectors xk , so x = (x1 , . . . , xk ) ∈ Rn∗k .

e a·xk
pk (a, x) = PN , k ∈ {1, . . . , N}
a·xi
i=1 e

For the data (a1 , . . . , am ) the labels are

(
1 when aj in class k,
yjk =
0 otherwise

The goal is to have

pk (aj , x) ≈ 1 for yjk = 1,
pk (aj , x) ≈ 0 for yjk = 0.

21/25
We minimise negative log-likelihood:
m
" N N
!#
1 X X X
L(x) = − yji xi · aj − ln e a·xi
m
j=1 i=1 i=1

22/25
Example: backpropagation
Recall that the input propagating through a neural network mathematically means that
we consider compositions of functions of the form σ(Wx + g ), where W and g are the
variables that are adjusted through the learning process, and σ is an activation
function.
Denoting this composition F (P, x), where P is the set of all parameters, and
y = F (P, x) is the output generated by the neural network, for a labelled data set
{(xi , yi )}ni=1 the training optimises some predefined objective, for instance, the
quadratic loss
n
1X
f (P) := ∥yi − F (P, xi )∥2 ,
n
i=1

that needs to be minimised over all possible values of P.

23/25
Gradient of the objective
To construct a basic gradient descent method we need to calculate the gradient of the
objective function. We have
n n
!
1X 2 2X
∇P ∥yi − F (P, xi )∥ = (JP F (P, xi ))T (F (P, xi ) − yi ).
n n
i=1 i=1

The difficult part of this calculation is to evaluate the partial derivatives of F in terms
of the parameters.

24/25
Chain rule and backpropagation

25/25