Tutorial 4 Problems
CSC311, Fall 2021
1 Gradient Descent Intuition
Suppose we are trying to optimize the loss function f (x) = 12 xT Ax, where x ∈ R2 4 0 1
Copyright By PowCoder代写 加微信 powcoder
1.LetA= 0 1 andx0= 1
What are the first two iterates of gradient descent, with a learning rate η = 0.1?
(Solution:
xn+1 = xn − η∇f(xn) = xn − ηAxn
xn= 0 (1−η)n x0 0.6 0.36
= (I − ηA)xn 1−4η 0
= 0 1−ηxn (1−4η)n 0
So in general:
givingusx1 = 0.9 andx2 = 0.81 .
Note that the later parts of this problem are good for building intuition but less important for purposes of the course. You can get more detailed explainations in the first part of the Distill article: https: //distill.pub/2017/momentum/ )
2. For which learning rates will gradient descent converge? The convergence speed is determined by how the error decreases in the “slowest” direction. What learning rate leads to the fastest convergence? (Solution: Weneed|1−4η|<1and|1−η|<1. Thisholdswhenη∈(0,21).
The convergence rate is given by max{|1 − 4η|, |1 − η|}. We want to choose η to minimize this rate, which happens when they are equal. From |1 − 4η| = |1 − η|, we get a learning rate η∗ = 0.4. This is where we “bounce around” in the direction of higher curvature. )
3. Suppose we choose the optimal learning rate. How many steps of gradient descent does it take for both components to be less than 1e-3 (0.001)?
(Solution: This occurs when (0.6)n < 0.001, or log0.6(0.001) ≈ 13.52. So 14 iterations. )
4. Repeat the previous two parts with A = 0 1 .
(Solution: The optimal learning rate is now 2 . Notice it is much smaller when there is a larger 101
difference between the two directions. For part (c), we now have log 99 (0.001) ≈ 345.37. So 346 101
iterations. )
2 Sum of Convex Functions
Prove that the sum of two convex functions is convex.
(Solution: Let f and g be convex functions. Consider h = f + g. We have
h(λx + (1 − λ)y) = f(λx + (1 − λ)y) + g(λx + (1 − λ)y)
≤ λf(x) + (1 − λ)f(y) + λg(x) + (1 − λ)g(y)
= λh(x) + (1 − λ)h(y) for all x, y and λ ∈ (0, 1). So h is convex. )
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com