flâneur

Effortless optimization through gradient flows – Machine Learning Research Blog

francisbach.com · 3,299 words · saved by 1 readers

Optimization algorithms often rely on simple intuitive principles, but their analysis quickly leads to a lot of algebra, where the original idea is not transparent. In last month post, Adrien Taylor explained how convergence proofs could be automated. This month, I will show how proof sketches can be obtained easily for algorithms based on gradient descent. This will be done using vanishing step-sizes that lead to gradient flows. The intuitive principle behind gradient descent is the quest for local descent. We thus need to characterize the local behavior of the function we aim to optimize. This is what gradients are for. In this blog post, I will consider minimizing a function 𝑓 f over ℝ 𝑑 Rd . Assuming 𝑓 f is differentiable, a first order Taylor expansion of 𝑓 f around a point 𝑥 x leads to 𝑓(𝑥+𝛿)=𝑓(𝑥)+∇𝑓(𝑥 ) ⊤ 𝛿+𝑜(‖𝛿‖), f(x+δ)=f(x)+∇f(x)⊤δ+o(‖δ‖), for any norm ‖⋅‖ ‖⋅‖ on ℝ 𝑑 Rd , where ∇𝑓(𝑥)∈ ℝ 𝑑 ∇f(x)∈Rd is the gradient of 𝑓 f at 𝑥 x , composed

Optimization algorithms often rely on simple intuitive principles, but their analysis quickly leads to a lot of algebra, where the original idea is not transparent. In last month post , Adrien Taylor explained how convergence proofs could be automated. This month, I will show how proof sketches can be obtained easily for algorithms based on gradient descent. This will be done using vanishing step-sizes that lead to gradient flows . Gradient as local information The intuitive principle behind gradient descent is the quest for local descent. We thus need to characterize the local behavior of the

related reading