Descent Direction Optimization Algorithms
摘要
This chapter provides a comprehensive overview of optimization algorithms designed to minimize convex surrogate loss functions, with a particular focus on direction of descent methods. It begins by establishing the essential conditions required for these algorithms to converge to the minimizer of a convex objective, emphasizing the importance of choosing appropriate descent directions and step sizes. The chapter explores the Gradient algorithm in detail, describing its operation in both full batch mode, which uses the entire dataset for high accuracy, and online mode, which processes individual data points for greater computational efficiency. Central to the discussion are the Wolfe conditions, which ensure that each iteration achieves a sufficient decrease in the objective function and that the step size remains appropriate, thus guaranteeing convergence when the loss function has a Lipschitz continuous gradient. Beyond basic gradient descent, the chapter examines advanced optimization techniques such as the Quasi-Newton method, which accelerates convergence by approximating the Hessian matrix using the BFGS formula, and line search methods that optimize step size selection through Wolfe conditions and backtracking strategies. The conjugate gradient method is also discussed for its effectiveness in large-scale problems, employing conjugate directions to enhance efficiency. Additionally, the Nesterov accelerated gradient method is introduced, which improves upon traditional gradient descent by incorporating a momentum term that anticipates future gradients. The chapter concludes with a discussion of the proximal gradient method, particularly valuable for problems where the objective function can be separated into smooth and non-smooth components. Overall, the chapter bridges theoretical foundations and practical considerations, illustrating how modern optimization algorithms achieve robust, scalable, and efficient solutions for a wide range of machine learning tasks.