Topic 7: Some Required Concepts In Mathematics

Question 1

What is the notation if function F depends on certain parameters z

Answer 1

Fz (subscript z)

Question 2

⟨w,x⟩

Answer 2

The dot product between w and v
w1x1 + w2x2 + …+ wnxn

Question 3

What is Lipschitzness

Answer 3

A function F ∶ Rp → R is said to be L-Lipschitz if for all x,y:
|F(x) - F(y) | ≤ L|| x - y ||

magnitude of the gradient is bounded by a constant factor throughout its domain

Question 4

What is || x- y || notation

Answer 4

The distance (usually euclidean) between two vectors x and y

Question 5

Why is squared loss not lipschitz

Answer 5

There doesn’t exist a single Lipschitz constant that can bound the difference in function values for all pairs of input values
The key is that value L changes with every example

Question 6

What is lipschitzness in english terms

Answer 6

A function is lipschitz if it does not change too rapidly

Question 7

Is huber loss lipschitz

Answer 7

yes

Question 8

How can we informally describe a convex function F

Answer 8

F’s graph between any two points x1 and x2
always lie below the straight line joining the points (x1, F(x1)) and (x2, F(x2))

Question 9

What is Convexity

Answer 9

A function F:Rp -> R si convex is for all Real x,y and θ between [0,1]:

F(θx + (1 − θ)y) ≤ θF(x) + (1 − θ)F(y)

Question 10

When is a function “strictly convex”

Answer 10

If the convex equation never becomes an inequality (only <)

Question 11

When does the convex inequality always become an equality

Answer 11

At the end of the chord, at points θ = 0,1

Question 12

When is a function definitely not strictly convex

Answer 12

If at any point in the line it becomes a flat line (and is not curving up) eg. ReLU
Can still be convex though!!!

Question 13

What is the Convexity equation for differentiable functions

Answer 13

An at least once differentiable function F ∶ Rp → R is convex if ∀ x, y we have:
F(x) + ∇F(x)⊺(y − x) ≤ F(y)

ensures the function lies above the tangent line at (x, F(x))

Question 14

What is ∇F(x)

Answer 14

The gradient (1st derivative) of F(x)

Question 15

What is p⊺q

Answer 15

The dot product of vectors p and q
(p1q1 + p2q2+…+pnqn)

Question 16

A function is a differentiable convex function if…

Answer 16

for any point x, the tangent to the function at that point is below the graph of the function

Question 17

What is α−Strong Convexity

Answer 17

For some α > 0, a F: Rp -> R is α−Strongly Convex if:

F(x) - α/2 ||x||^2 is a convex function

Essentially adding α/2 x^2 to any convex function, yields a α-strongly convex function

Strongly convex functions are strictly convex and convex

Question 18

The larger the α…

Answer 18

The stronger the convexity

Question 19

How does the exponential loss function work

Answer 19

label can be +1 or -1
e^(-yh(x))
Where y = true label
and h(x) is predicted label

If y=1 and h(x) is negative -> loss function close to 1

If y=1 and h(x) is large and positive -> loss function close to 0

The exponential loss function penalises heavily when h(x) predicts wrong answers with high confidence

Question 20

What is Lipschtiz smoothness

Answer 20

For some β > 0, an at least once differentiable function F: Rp -> R is said to be β-smooth if

∥∇F(x) − ∇F(y)∥ ≤ β∥x − y∥

Eg F(x) = x^2 is smooth with β=2

Question 21

Lipschitz-Smoothness vs general smoothness

Answer 21

In analysis textbooks smoothness refers to a function being infinitely differentiable (eg F(x) = x^3) - this is not the same thing!

Question 22

What is strict convexity

Answer 22

f”(x) > 0
It will have a slope

straight lines cannot be strictly convex

Question 23

Do strongly convex functions have global minimums

Answer 23

always have one global minimum

Question 24

How many global minima do convex and strictly convex functions have

Answer 24

none or 1

Question 25

What can we say about the local minimum of a convex function

Answer 25

it is the global minimum

Question 26

What is Convergence (def 1)

Answer 26

A sequence of points xi ∀i = 1, 2, . . . in Rn will converge to the point x* if
limn→∞||xn - x*||2 = 0

Essentially as n tends to infinity, xn and x* are the same point

Question 27

What is ∥a − b∥2 (subscript 2) notation

Answer 27

The euclidean distance between vectors a and b

Question 28

What is x*

Answer 28

the “limit point”

Question 29

What is Convergence (more generalised def 2) we only need def 1 on this course

Answer 29

A sequence of points xi ∀i = 1, 2, . . . in Rn will converge to the point x* if (for all ε > 0)
||xn - x*||2 ≤ ε

Essentially “no matter how small of a distance ϵ you choose, eventually all the points in the sequence will be within ϵ distance from x*

Question 30

What is a Supremum

Answer 30

The “Least upper bound”
Let I be a subset of R. Suppose there exists an upper bound M on I s.t M ≤ M′ ∀ upper bounds M′ on I
Then M is the “least upper bound” on I and it’s called the “supremum” of I and is denoted as
sup I

Eg1 I = [0,1)
sup I = 1

Eg2 I = [0,1) U [1.5,2]
sup I = 2 = max I

Question 31

What is a maximum

Answer 31

Let I be a set, when sup I ∈ I we call it the “maximum” of I, max I

Question 32

What is an Infimum

Answer 32

The “Greatest lower bound”
Let I be a subset of R. Suppose there exists a lower bound m on I s.t m ≥ m′, ∀ lower bounds m′ on I
Then m is the “greatest lower bound” on I and it’s called the “infimum” of I and is denoted as
inf I

Eg1 I = [0,1)
inf I = 0 = min I

Eg2 I = [0,1) U [1.5,2]
inf I = 0 = min I

Question 33

What is a minimum

Answer 33

Let I be a set, when inf I ∈ I we call it the “minimum” of I, min I

Question 34

What is the spectral norm of a matrix

Answer 34

Denoted as ||A||subscript2
Tells you how much a matrix can stretch any unit vector in its domain
Eg if you have a matrix that is just a column vector, its spectral norm is the length of the vector

Question 35

What is the spectral radius of a matrix

Answer 35

The largest absolute value of its eigenvalues
(maximum amount by which a matrix can stretch or compress vectors)
eg λ1 = 0.5, λ2 = 3
3 is the spectral radius

Question 36

What is a Span

Answer 36

Given a finite set of vectors v1,…,vk

Span ({v1,…,vk}) = Σ wivi

The span of a set of vectors is all the different combinations you can make by stretching, shrinking, or rotating those vectors in different ways

We call the set of vectors the “spanning set” for the vector space

Question 37

What does the spanning set e1 = [10] and e2 = [01] mean

Answer 37

It is a 2-dimensional space
Every vector in this space can be written as a linear combination of e1 and e2

Question 38

What is Dimension

Answer 38

Given a finite set of mutually orthogonal vectors z1,…,zp

p = dimension(Span({z1,…,zp})

The number of dimensions described by the vector set

{z1, . . . , zp} is an instance of a basis of Span({z1, . . . , zp})

eg dimension 3

Question 39

What is Basis

Answer 39

The smallest set of spanning vectors that is needed to be able to describe every direction in the space
Eg (e1,e2,z) -> the basis : (e1,e2)

Question 40

What does mutually orthogonal mean

Answer 40

A set of vectors where each vector is perpendicular (orthogonal) to every other vector in the set

Question 41

What is the Rank of a matrix

Answer 41

Given any m × n matrix T i.e T ∶ Rn → Rm:

rank(T) = dimension(Image(T))

How many different dimensions a vector v can move in after being transformed by matrix T

Eg M = 2x2 = [2 0] [0 1] = rank 2
D = 2x2 = [3 0] [0 0] = rank 1

count the number of non-zero rows in REF

Question 42

What is the image of a matrix

Answer 42

Given any m × n matrix T i.e T ∶ Rn → Rm:

Image(T) = {T[v] | v ∈ Rn}

The Image is all the points a vector v can be transformed to by matrix T

Question 43

What is “full rank”

Answer 43

if rank(T) = min{n,m}
Then T is of “full rank”

Eg matrix: 4 by 2 and it is rank 2 then its full rank

Question 44

What is the Null space of a Matrix

Answer 44

Given any m × n matrix T i.e T ∶ Rn → Rm:

Null Space(T) = {v ∈ Rn | T[v] =0}

All the vectors that get squished down to nothing when you transform them

Question 45

What is a kernel

Answer 45

Same as null space
Null Space(T) = ker(T)

Question 46

what does adding α/2 ||x||^2 do to the graph

Answer 46

makes it (α- strong convex) bounded by a paraboloid - a bowl/cup shape

Question 47

when is the rank of a matrix 0

Answer 47

when all elements of the matrix are 0