Optimization for Machine Learning: Frank-Wolfe Algorithm

This lecture covers the Frank-Wolfe algorithm, a projection-free optimization method reducing non-linear to linear optimization. It was invented in 1956 by Marguerite Frank and Philip Wolfe. The algorithm is sparse and always feasible, making it suitable for various applications. The lecture explains the algorithm's properties, stepsize variants, examples like Lasso Regression, and its convergence in O(1/ɛ) steps. It also discusses the duality gap and affine invariance. The proof of convergence in O(1/ɛ) steps is detailed, emphasizing the algorithm's scalability and efficiency.