1
$\begingroup$

I'm currently learning the basic variants of gradient descent for minimizing convex functions under various assumptions, such as Lipschitz, smooth, strongly-convex, ... .

I've found various sources online, such as these notes by Vishnoi, this book by Bubeck, and various others.

When I try to do the proofs on my own, after a while I figure out the tricks needed to successfuly analyze this or that variant, and I get some glimpses of geometric intuition, but there's also a lot of purely algebraic manipulation to get things to a form amenable to applying the right inequality.

Furthermore, the sources I've found so far don't really provide much geometric intuition, and don't really start the proofs with the question "OK, how would we prove that" to motivate the tricks, but just jump into the manipulations. It feels like there's something lacking to this approach, some geometric insight burried in the algebra.

Are you aware of sources that try to motivate things better, or is it just something you need to get used to after you've been doing it for a while?

Edit: in the comments people have asked for more specific examples. So here are some: in these notes by Vishnoi, the analysis of gradient descent for strongly-convex, bounded-gradient functions (section 1.5.3.) uses a trick of taking a weighted sum of certain inequalities coming from strong convexity at each step, with the weight being the step number. Another example would be the telescoping trick from section 1.5.1. How can we think more geometrically about why such tricks would be natural?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I would suggest a book on convex analysis to get more geometric insight. Rockafellar's "Convex analysis" is classical and the newer "Variational analysis by Rockafellar and Wets has more pictures. $\endgroup$
    – Dirk
    Nov 5, 2016 at 17:15
  • $\begingroup$ Can you point to a specific example, like a theorem statement? $\endgroup$
    – usul
    Nov 5, 2016 at 17:25
  • $\begingroup$ @usul: I just updated the question with some examples $\endgroup$
    – amakelov
    Nov 5, 2016 at 20:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.