Optimization

From the speed camera to gradient descent, then objectives and constraints up to the widest margin (SVM)

In this chapter, you will learn to

• Read a derivative as a rate of change, and a gradient as a direction
• Minimise a function step by step (gradient descent) and tune the step size
• Frame a problem as an objective under constraints

Tools: NumPy

13 exercises

Each exercise is graded automatically, in your browser. The full statements are available once you have an account.

1. What this is for in real life

   Whenever you look for "the best" (cheapest, fastest, fewest mistakes), you are optimising, and training an AI is nothing more than that. - Training an AI. A large language model has billions of settings.…

2. The speed radar

   You are building a speed radar. A camera records a car's position (in meters) every second. The police want to know the speed at every instant: "how far the car moves per second". Write a function…

3. Sensor noise

   Your radar's GPS sensor is not perfect. The position measurements contain small errors. You are given noisy_positions, a numpy array of 100 position measurements taken every 0.1 seconds (dt = 0.1). The car is…

4. Which way to go?

   A delivery drone flies over a city. Each position $(x, y)$ has a delivery cost given by a function cost(x, y) that you can call (but whose formula you do not know). To decide where to go, the drone must know how the…

5. The autopilot

   You will now build an autopilot for the drone. Starting from an initial position, the drone must reach the point of minimum cost on its own. It cannot see the whole map: at each instant, it only knows the rates of…

6. The capricious slider

   The gradient descent algorithm is simple: compute the slope, take a step the other way. But how large should the step be? You are given three cost functions f1, f2, f3 and a function…

7. The booby-trapped polynomial

   Minimize: $h(x) = x^4 - 4x^2 + x + 3$ over $[-3, 3]$. Print your best $x$. To succeed: achieve $h(x) < -2$. Will the method that has served you so far ("The autopilot", "The capricious slider") work directly? Explore…

8. The labyrinth

   The function labyrinthe(v) takes a 10-dimensional numpy vector and returns a "danger level". A gradient descent from the origin $v = (0, ..., 0)$ converges to a score of about 8.0. But there are much safer…

9. What does it mean to optimize?

   From the very beginning, you have been optimizing without always naming it: finding the line that minimizes the error, the parameters that minimize the loss… Let's put a word on it. An optimization problem…

10. Finding the dip

    You are given a list costs of cost functions. Each element is a pair (cost, grad): - cost(x) returns the cost (a number) at the point x = [x0, x1]; - grad(x) returns the gradient of cost at x (a vector of…

11. Closest, without going over

    You are given a point target = [c0, c1] and a budget c. Find the point x = [x0, x1] that is as close as possible to target (in the sense of distance), but whose coordinates must not sum to more than…

12. The widest margin

    Two clouds of points must be separated: X (coordinates, 2 columns) and y (labels +1 or -1). Many lines separate them without error, but we want the best one: the one that stays as far as possible from…

13. Explain the fine

    You have used the penalty method twice: to stay within a budget (“as close as possible, without going over”), then for the widest margin (the SVM's hinge loss). Now explain why it works: in your own words…