Stanford EE364A Convex Optimization I Stephen Boyd I 2023 I Lecture 14

()

Gradient Descent

Gradient descent works poorly when the level sets are poorly conditioned (anisotropic) and works well when the level sets are well-conditioned (isotropic or spherical).
The efficiency or speed of gradient descent depends on how aspherical or anisotropic the sublevel sets are.
Steepest descent direction depends on the norm used.
Steepest descent in the Euclidean norm is precisely gradient descent.
The choice of the metric or norm for steepest descent makes a big difference in convergence.
It is desirable to use a norm that is aligned with the sublevel sets of the function.

Newton's Method

The Newton step involves using the Hessian (second derivative) of the function at the current point as a metric to determine the direction of steepest descent.
The Newton step can be thought of as a variable metric method, as the metric is changed at each step.
Another interpretation of the Newton step is to minimize a second-order approximation of the function.
The Newton step can also be derived by linearizing the optimality condition (gradient equals zero) and solving for the displacement.
In one dimension, the Newton step involves finding the zero-crossing of a linear approximation of the derivative.
Repeated application of the Newton step leads to rapid convergence to the minimum of a smooth convex function.
Newton's method uses the Newton step and the gradient to minimize a function.
The Newton decrement is the predicted decrease in the function when taking a Newton step.
The metric defined by the Hessian is a quadratic metric that is invariant under affine transformations.
Newton's method is independent of linear changes of coordinates.
Newton's method works exceptionally well for quadratic functions because it solves the entire problem in one step.
The convergence of Newton's method depends on the third derivative of the function.
Newton's method works exceptionally well when the third derivative of a function is small.
A small third derivative indicates that the function is close to quadratic.
The Lipschitz constant (L) is used to express the smallness of the third derivative.
If the norm of the gradient is larger than a certain number, Newton's method guarantees a fixed decrease in the function.
Once the norm of the gradient becomes smaller than that number, the convergence accelerates and becomes quadratic.
The damped Newton phase is followed by the quadratically convergent phase.
The maximum number of steps in the damped Newton step is determined by the function value minus the optimal value divided by gamma.
The number of iterations until reaching a certain level of suboptimality is proportional to the logarithm of the logarithm of the desired accuracy.
The classical analysis of Newton's method for optimization involves complex hypotheses and parameters that are often unknown in practical problems, making the convergence results useless.
The author criticizes the emphasis on theoretical convergence analysis rather than practical performance and suggests that many Western optimization convergence results are conceptually flawed.
Quasi-Newton methods and other variations of Newton's method can be used to approximate the Hessian matrix and make the method more practical.
The author argues that the convergence analysis of Newton's method is aesthetically embarrassing because it is not scale-invariant, while the actual code is.
The author encourages a focus on practical performance and simplicity in optimization methods, rather than overly complex theoretical analysis.

Practical Considerations

Newton's method is a powerful optimization algorithm that converges quadratically, meaning it rapidly approaches the optimal solution with each iteration.
It is particularly effective for smooth, unconstrained optimization problems.
Newton's method involves calculating the gradient and Hessian (matrix of second derivatives) of the objective function at each iteration to determine the search direction and step size.
Despite its efficiency, Newton's method can be computationally expensive, especially for large-scale problems with many variables.
Quasi-Newton methods are alternatives that approximate the Hessian and are often used in practice.
Newton's method is widely used in various fields, including machine learning, signal processing, and optimal control problems, where it can achieve high accuracy with relatively few iterations.

Advanced Analysis

The classical analysis of Newton's method has a less sophisticated analysis compared to the actual algorithm.
The issue with the classical analysis is that it says the third derivative is small in a way that is not affine independent.
Nesterov and Nemirovski introduced the concept of self-concordance, which is an affine invariant way of saying the third derivative is small.
Many practical functions are self-concordant, and Newton's method based on self-concordance has a simpler analysis.
Nesterov and Nemirovski's analysis of Newton's method based on self-concordance gives a complexity bound that is much better than the classical analysis.

Implementation Details

Newton's method reduces the solution of minimizing a smooth convex function to minimizing a sequence of quadratic functions.
Each iteration of Newton's method involves solving a linear system of equations.
If the Hessian matrix is structured, the linear system can be solved efficiently in linear time.
A variant of Newton's method called the "lazy Newton" method updates the Hessian matrix every 20 steps, which can save computation time.