Week 1 Introduction: Optimisation problems in

Data Science
MATH3191/5191 Mathematical Optimization for Data Science

A/Prof. Vera Roshchina

School of Mathematics and Statistics, UNSW Sydney

Term 3 2024

1/36
What is this course about?
We focus on mathematical foundations of optimisation methods
in data science.
Huge problems mean that computation heavy methods (Newton’s
method, interior-point methods) can’t be used, instead the focus is
on fast and computationally inexpensive optimisation techniques.
We will focus on neat, simplified mathematical ideas.
Some optimisation hot topics in modern data science do not have
(as yet) a well-understood mathematical content.
We will mostly study convex continuous optimisation problems,
since most data science problems are either in this class or are
solved using convex optimisation algorithms.

2/36
Course Learning Outcomes (CLOs), *=MATH5191 only
■ State and explain fundamental mathematical principles behind the
optimisation techniques used in data science.
■ Recognise typical optimisation models used in data science and the
factors influencing performance of standard optimisation algorithms
on these models. *Perform mathematical analysis to make an
informed choice of an optimisation model and solution technique
based on the type of the problem and computational constraints.
■ Apply standard optimisation techniques to specific problems and
estimate their efficiency taking into consideration the problem’s
parameters and computational constraints. *Modify standard
methods or design new optimisation techniques to suit specific
problems.
■ Demonstrate competence in mathematical presentation and
communication skills, *support decisions using mathematical
argument and references.
■ *Critically evaluate emerging methods and applications, by
comparing the new approaches to well-known techniques, identifying
strengths, disadvantages and knowledge gaps.
3/36
Assessment Structure

4/36
Tentative schedule of topics by week

1. Introduction: Optimisation problems in Data Science

2. Optimisation Modelling
3. Gradient Methods
4. Acceleration and Complexity of First-Order Methods
5. Stochastic Gradient Descent and other techniques
6. Flexibility Week
7. Dealing with Constraints
8. Nonsmooth Optimisation
9. Duality and dual methods
10. Review of alternative and emerging optimisation techniques.

5/36
Introductions

Lecturer: A/Prof. Vera Roshchina [Link]@[Link]

Lectures:
■ 2–4pm Mondays
■ 2–4pm Thursdays
Tutorial on Wednesdays (1pm or 2pm, Lawrence theatre)
Lectures will be recorded.
Please bring a laptop to tutorials.
Please use Moodle Forum for questions!

6/36
Textbooks, lecture notes and other resources

Textbooks
All textbooks are available from the UNSW library
■ Stephen Wright and Benjamin Recht, Optimization for Data
Analysis (2022)
■ Stephen Boyd, Lieven Vandenberghe, Convex Optimization
(2004)
■ Yuri Nesterov, Lectures on Convex Optimisation (2018)
■ Michael W. Mahoney, John C. Duchi, and Anna C. Gilbert,
The mathematics of data (2018)

Lecture notes
Lecture notes will be made available before each lecture.
Tutorial problems
Tutorial problems will be posted before each tutorial.

7/36
This week’s goals

■ Optimisation modelling: identifying the objective function,

variables, constraints and parameters in typical data science
problems.
■ Choosing an appropriate optimisation model for a given task.
■ Identifying the mathematical structure of an optimisation
model.

8/36
Data Science Problems
What problems in Data Science are mathematical problems?

Which ones of these problems are optimisation problems?

What are you expecting to learn in this course?

9/36
What is optimisation?

Optimisation is about choosing the best option out of available

ones.
Mathematically this usually means maximising or minimising a
real-valued function over a set of feasible values.
The function is called the objective function, and the restrictions
placed on the feasible values are called constraints.
The variables in an optimisation problem encode the feasible
choices. When we assign the values to these variables that satisfy
the constraints and maximise or minimise the objective function,
we call this assignment an optimal solution.
An optimisation problem may also have model parameters.

10/36
Support vector machines
Support vector machine (SVM) is a binary linear classifier.
Given a (finite) set of labelled data points (with two labels), an
SVM constructs a linear function that separates the two classes
(the class is determined by the sign of the function). This
separator can be used to assign labels to unlabelled data.

11/36
Support Vector Machines: separable case
Given two finite subsets A = {a1 , a2 , . . . , ak } and
B = {b1 , b2 , . . . , bm } of Rn , our goal is to find a linear function

h(x) = u · x + β,

where u · x = u (1) x (1) + u (2) x (2) + · · · u (n) x (n) such that

u · ai + β < 0 ∀i ∈ {1, . . . , k},

u · bj + β > 0 ∀j ∈ {1, . . . , m}.

12/36
Support Vector Machines: a better separator
It is reasonable to require the kind of separation that provides a
gap between the two classes:

u · ai + β ≤ −1 ∀i ∈ {1, . . . , k},
u · bj + β ≥ 1 ∀j ∈ {1, . . . , m}.

13/36
Support Vector Machines: the best separator
We can define the best separator as the hyperplane that maximises
the distance from this hyperplane to the closest points from the
two classes.
This problem can be written as the following optimisation problem,

min ∥u∥2
u,β

s.t. u · ai + β ≤ −1 ∀i ∈ {1, . . . , k}
u · bj + β ≥ 1 ∀j ∈ {1, . . . , m}

14/36
What if the points can’t be separated?
■ minimise the classification error, or
■ separate with a nonlinear function

15/36
SVMs: soft margin
Loss function:

l(x, s) = max{s(u · x + β) + 1, 0}.

Now for the points in A we let s = 1

and for the points in B we let s = −1.
If a point a from A is classified correctly, then a · u + β ≤ −1, and
then
s(u · x + β) + 1 = x · u + β + 1 ≤ 0,
so that l(a, s) = 0. If a is misclassified, then a · u + β > −1, and so

s(u · x + β) + 1 = u · x + β + 1 > 0,

and the value of the loss function is l(a, s) = u · x + β + 1 > 0.

Similar analysis works for B.

16/36
Incorporating the hinge loss in the objective

Now we can add the hinge loss to our objective function.

The overall penalty is
X X
pA,B (u, β) = l(ai , 1) + l(bj , −1)
i∈{1,...,k} j∈{1,...,m}
X
= max{(ai · u + β) + 1, 0}
i∈{1,...,k}
X
+ max{−(bj · u + β) + 1, 0}.
j∈{1,...,m}

min λ∥u∥2 + pA,B (u, β),

u,β

where λ > 0 is a parameter of our choosing.

17/36
Support Vector Machines: nonlinear separation
Suppose that using a linear classifier is not a viable option. We can
consider a separating function from another class. For instance, we
can use a quadratic classifier.

Suppose that A, B ⊆ R2 , and we would like to find

p(x1 , x2 ) = a00 + a10 x1 + a01 x2 + a20 x12 + a11 x1 x2 + a02 x22

such that p(a) < 0 for a ∈ A, p(b) > 0 for b ∈ B.

18/36
Lifting to a higher-dimensional space
If we map our points x ∈ R2 to a higher dimensional space of
monomials, that is, consider a function φ(x) : R2 → R5 such that

x1
   x2 
x1  2

x= 7→ y = √ x1
,
x2  
 2x1 x2 
x22

then we can view the polynomial p as a linear function of y , that

is, p(x) = q(φ(x)) = q(y ), where
a11
q(y ) = a00 + a10 y1 + a01 y2 + a20 y3 + √ y4 + a02 y5 .
2
Now the lifted points φ(a1 , . . . , ak , b1 , . . . , bm ) can be separated in
R5 with a hyperplane q using an SVM, hence producing a
quadratic separating polynomial in R2 .
19/36
Using kernels

The kernel trick is about introducing a kernel function that

replaces the dot product. We can let

k(x, x ′ ) = φ(x) · φ(x ′ ).

For our function φ the kernel is

x ′1
   
x1
 x2   x ′ 2 
′ 2 ′2 ′ ′ 2
   
√ x1  · √ x 1  = x · x + (x · x )
k(x, x ) =    
 2x1 x2   2x ′ 1 x ′ 2 
x22 x ′ 22

There are many choices of kernel functions used in applications.

20/36
K-means clustering
Given a finite set of points P ⊆ Rn and a positive integer K we
would like to partition these points into K nonempty subsets
(clusters) C1 , C2 , . . . , CK such that the points in each cluster are
located as close as possible to the cluster’s mean,
1 X
µi = p ∀i ∈ {1, . . . , K }.
|Ci |
p∈Ci

21/36
K-means clustering: optimisation problem

We can write the optimisation problem as

K X
X
min ∥p − µi ∥2
C
i=1 p∈Ci
1 X
s.t. µi = p ∀i ∈ {1, . . . , K }
|Ci |
p∈Ci

Ci ̸= ∅, i ∈ {1, . . . , K },
K
[
Ci = P,
i=1
Ci ∩ Cj = ∅, i ̸= j, i, j ∈ {1, . . . , K }.

22/36
Neural Networks and Deep Learning

23/36
Neural Networks continued

A neural network is an oriented graph with a set of input and

output nodes. The signal that encodes data points is fed to the
input, and each node applies a composition of a linear
transformation and a sigmoid function, propagating the modified
signal to the next layer.
The network is ‘trained’ to produce the desired output: the linear
transformation used by each one of the nodes is adjusted
iteratively using an optimisation algorithm to get the output of the
network match the assigned data labels as close as possible.

24/36
Explicit description
Each node has a number of incoming edges, say k, and so receives
some input vector x ∈ Rk . A linear function Wx + g : Rk → Rm is
then applied to this vector (here m is the number of outgoing
nodes).
Finally an activation function transforms each coordinate to the
output vector that is propagated through the outgoing nodes,
   
y1 σ((Wx + g )1 )
y2   σ((Wx + g )2 ) 
y =.=  = σ(Wx + g ).
   
..
 ..   . 
yk σ((Wx + g )m )

25/36
Common activation functions

Sigmoid functions, for instance,

logistic function
1
σ(x) =
1 + e −x
ReLU (rectified linear unit)

f (x) = max{0, x} = x +

Softplus

f (x) = ln(1 + e x )

26/36
Neural networks continued

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.
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
∥yi − F (P, xi )∥2 ,
n
i=1

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

27/36
Why do neural networks work?
A simple answer: universal approximation theorems.

A classic example is Cybenko-Hornik theorem

Theorem A continuous function σ : R → R is not polynomial if
and only if for every compact K ⊂ Rn , every continuous function
f : K → Rm and ε > 0 there exist k, A ∈ Rk×n , b ∈ Rk ,
C ∈ Rm×k such that

sup ∥f (x) − C (σ ◦ (Ax + b))∥ < ε.

x∈K
28/36
Questions
What makes an optimisation problem ‘hard’ or ‘easy’ ?
What does it mean that an optimisation problem has a specific
structure? What are some examples of structure?
What is complexity of an optimisation problem?

29/36
Optimisation problems
A classic (continuous) optimisation problem and a general
formulation:

min f (x) min f (x)

s.t. gi (x) = 0 ∀i ∈ {1, . . . , k}, or s.t. x ∈S
hj (x) ≤ 0 ∀j ∈ {1, . . . , m}.

The objective function f : Rn → R is minimised or maximised over

a feasible set S ⊆ Rn . The objective function and the feasible set
may be represented in various ways.
A feasibility problem is an optimisation problem with a missing or
trivial objective (f (x) ≡ 0).

30/36
Some examples of a classic problem

Linear programming problem:

min c ·x
x∈Rn
s.t. Ax = b
xi ≥ 0 ∀i ∈ {1, . . . , n}

Projection onto a set defined by an inequality, for instance

min ∥p − x∥
x∈R3
s.t. ax12 + bx22 + cx32 ≤ 1.

31/36
An example of a semidefinite program

min x +y +z
x,y ,z
 
1 x y
s.t. x 1 z  ⪰ 0.
y z 1

32/36
Optimal solution and optimal value
Given an optimisation problem

min f (x)
s.t. x ∈S

we say that x is a feasible solution if x ∈ S. A feasible solution

satisfies the problem’s constraints, but doesn’t necessarily solve the
problem.
We say that a feasible solution x ∗ ∈ S is an optimal solution of
an optimisation problem if (given that we are minimising the
objective function f )

f (x ∗ ) ≤ f (x) ∀x ∈ S.

The optimal value of the problem is the value of the objective

function at an optimal solution, that is, v ∗ = f (x ∗ ), where x ∗ is an
optimal solution.
33/36
Types of Optimisation problems
The type of an optimisation problem is determined by the
properties of the objective function, the type of the feasible set and
their descriptions.
The objective function can be The feasible set can be

34/36
An optimisation problem can be ill-defined
An optimisation problem may not have a solution (because of this
it is actually more appropriate mathematically to write inf or sup
instead of min and max). Moreover, a problem can be infeasible!
The description of the feasible set may be more important than the
actual type of the feasible set as a geometric object.

35/36
Structure of the problem
Structure usually refers to the availability of mathematical tools
that help solving the optimisation problem.
For instance, if an objective function is separable
n
X
f (x) = fi (xi ),
i=1

we may be able to construct an efficient optimisation method that

only uses some of the components of this function on each step.
If the objective function is linear, and the constraints are linear
equalities and inequalities, then we have a linear programming
problem. We can use simplex or interior-point methods to solve
these problems.
If the problem is polynomial, we may be able to use the methods
of computational algebraic geometry to solve it exactly.
36/36