Gradient Descent & Newton's Method | Cornell CS4780 Machine Learning

Added:

Derivative-Free Optimization and Neuroevolution

While Gradient Descent and Newton’s method rely on calculating derivatives (gradients and Hessians) of a loss function, they struggle when the objective function is non-differentiable, discontinuous, highly noisy, or lacks analytical gradients. Derivative-Free Optimization (DFO) and Neuroevolution offer a powerful alternative paradigm. Methods such as Genetic Algorithms, Evolution Strategies (ES), and Particle Swarm Optimization search the parameter space by evaluating the objective function directly, mimicking biological evolution or physical processes. In reinforcement learning and complex neural network training, neuroevolution has shown competitive performance to gradient-based methods. It avoids issues like vanishing or exploding gradients and does not require backpropagation, making it highly parallelizable and robust to local minima in rugged, non-smooth landscapes where traditional calculus-based optimization fails.

Multivariable calculus, including gradients, partial derivatives, and Taylor series approximations.
Linear algebra fundamentals, particularly vectors, matrices, and the definition of a Hessian matrix.
Basic machine learning terminology, specifically the concepts of loss functions, cost functions, and hypothesis spaces.
Foundational optimization concepts, such as identifying local versus global extrema and understanding convex functions.
Stochastic Gradient Descent (SGD) and mini-batch gradient descent for scaling optimization to massive datasets.
Advanced adaptive optimization algorithms widely used in deep learning, such as AdaGrad, RMSProp, and Adam.
Quasi-Newton methods (like BFGS and L-BFGS) which approximate the Hessian matrix to bypass high computational costs.
Constrained optimization techniques, including Lagrange multipliers and the Karush-Kuhn-Tucker (KKT) conditions.
The application of optimization in training deep neural networks, addressing issues like vanishing gradients and saddle points.
52.8K views770likes49:18@kilianweinberger698Original Release: 2018-07-11

This lecture explains how to minimize loss functions in machine learning through iterative optimization methods. Gradient descent uses the negative gradient direction (w_new = w_old - α∇L(w)) to iteratively approach the minimum, with learning rate α chosen carefully to ensure convergence. Newton's method improves upon this by incorporating the Hessian matrix (second derivatives) to take larger, more direct steps toward the minimum, converging much faster once close to the optimum. However, Newton's method requires computing and inverting the Hessian, which is computationally expensive and can lead to divergence if starting far from the minimum. The recommended practical approach combines both methods: use gradient descent initially to approach the minimum reliably, then switch to Newton's method for rapid final convergence.