Advanced Algorithms and Data Structures

16 Gradient descent: Optimization problems (not just) on graphs

This chapter covers

• Developing a randomized heuristic to find the minimum crossing number
• Introducing cost functions to show how the heuristic works
• Explaining gradient descent and implementing a generic version
• Discussing strengths and pitfalls of gradient descent
• Applying gradient descent to the graph embedding problem

If I mention a technique called gradient descent, does it ring a bell? You might not have heard of it, or maybe you recognize the name but can’t quite recall how it works. If so, that’s fine. If, however, I ask you about machine learning, classification problems, or neural networks, chances are that you know exactly what I’m talking about; and I bet these terms ...