Norm Penalties as Constrained Optimization

A penalty as a limit on size

Think of packing a suitcase for a flight with a weight limit. The limit does not tell you which items to leave out. It only fixes the total. Inside the limit you choose freely, and the best choice is the one that fits the trip and the limit together.

A norm penalty works in the same way. Training minimizes a loss plus a price for size, , and the price has a penalty strength . Equation 7.25 writes the penalized cost:

In the book, is a norm of the parameters, and is the penalized cost that training minimizes. The loss is still the same loss, so the penalty only changes which solution wins.

Predict first. The penalty strength grows from 0 to 3. What happens to the region of weights that the penalty allows?

Choose an answer, then move the penalty strength.

The demo below uses a loss with its bottom at = (2, 1). The dashed rings are the loss. The dashed violet circle is a limit ball, the region of weights that the penalty allows. Its radius is set by the penalty strength, and the readout states it.

For this demo the loss has the same curvature in both directions. Then the best weight with the penalty is divided by , and the limit ball has radius . This derivation is added here and is not printed in the book. It turns the strength into a radius, which is the idea behind Equation 7.28.

Equation 7.28 says that once the strength is fixed, training with the penalty is exactly the training problem with the penalty as a term in its cost:

So a penalty can be read as a limit on the weights. Larger gives a smaller limit ball, and smaller gives a larger one. The book notes that we rarely know the radius in advance, because it depends on the loss. The shape of the region follows the norm. An L2 norm gives a ball, and an L1 norm gives a region of limited L1 norm, which in two dimensions is a diamond.

Checkpoint. With = (2, 1) and , what is the radius of the limit ball?

Answer, then check the demo.

The Lagrangian and the penalty strength

Suppose you want the penalty to enforce a limit directly: the size must stay below a constant . The book builds the generalized Lagrange function , which is the loss plus a multiplier times the amount by which the limit is broken. The multiplier is , a Karush–Kuhn–Tucker (KKT) multiplier, and it must be zero or larger:

Think of a thermostat that controls cooling. When the room is hotter than the set point, the cooling is turned up. When the room is cooler, the cooling is turned down. The multiplier is that cooling. It rises while the size is above the limit and falls while the size is below it. Cooling cannot run in reverse, just as cannot go below zero.

The solution is found by minimizing over the weights and maximizing over the multiplier, as Equation 7.27 says:

The book states the rule in words. Whatever the method, must increase whenever is above , and decrease whenever it is below. Any positive pushes down, and the optimal pushes it down only as far as the limit.

Predict first. Start with = 0 and a weight size of 5, which is above a limit of 1. What does the first update do to ?

Choose an answer, then press one step below.

The demo below takes the simplest update that follows the book's rule. This update rule is added here and is not printed in the book. The strength moves by times the amount by which the size is above or below the limit, and it is never allowed below zero. The size here is the squared length of the weights, , for the same loss as before.

Each step moves the penalty strength towards the value where the squared length of the weights equals the limit. Near that value the strength stops changing, and that is the point where the constraint is met exactly. A larger update size reaches it in fewer steps, but a large one overshoots. With a large limit it can swing between two values without settling, so try a few sizes.

Checkpoint. If the squared length is below the limit, which way does move?

Answer, then check the readout.

Explicit limits and reprojection

There is another way to use a limit. Instead of a penalty, take an ordinary gradient step on and then project the result back to the nearest point that satisfies the limit. The projection is written . Projection changes a weight only when the step has carried it outside the region, so the limit is enforced directly.

Imagine walking on a field with a fence around it. You take your step downhill, and if the step crosses the fence you move back to the nearest point on the fence. Inside the fence you never move back.

The book gives two reasons for preferring this to a penalty. A penalty can trap a non-convex training run in a small-weight setting, which leaves dead units whose weights are all tiny. A penalty also keeps pulling weights towards the origin even when the loss does not need it. Explicit limits with reprojection avoid both problems, and they also stop the weights from growing without bound when the learning rate is high.

Predict first. The loss is smallest at = (2, 1), which lies outside a limit of radius 1. Where does projected descent end up?

Choose an answer, then press run.

The demo starts at the origin. Each step moves the point a fraction of the way towards , then projects it back if it has left the limit. Once the point touches the edge, the projection holds it there while the loss keeps pulling outwards. The limit only does work when the path reaches it.

Checkpoint. Why does projection avoid the dead-unit problem that a penalty can cause?

Answer, then check the demo.

One limit for each column

In a neural network the weights form a matrix, one column for each hidden unit. The book recommends a limit on the norm of each column, rather than on the norm of the whole matrix. This was introduced by Srebro and Shraibman and used with a high learning rate by Hinton and colleagues. Each column is one hidden unit, so one unit with very large weights cannot dominate the others.

A column limit is like a separate allowance for every shelf in a warehouse. One overloaded shelf is trimmed to its allowance, while the lightly loaded shelves are left alone. A single allowance for the whole warehouse would trim every shelf in proportion, including the empty ones.

The book notes that if this limit were turned into a penalty, it would need a separate multiplier for each hidden unit, with each one updated on its own. In practice, column norm limitation is always an explicit limit with reprojection.

Predict first. Under the per-column rule with a limit of 1, a column of length 3 and a column of length 0.2 are projected. What happens to each?

Choose an answer, then switch the rule.

The demo has three columns, each with two entries. The per-column rule shrinks only the columns longer than the limit, and it scales each of them to exactly the limit. The whole-matrix rule computes the length of all the entries together and scales every column by the same factor.

Checkpoint. Under the per-column rule with a limit of 1, what is the length of a column of length 2.5 after projection?

Answer, then check the demo.

• A norm penalty is a limit on the size of the parameters in disguise. Equation 7.28 says that a fixed penalty strength gives the same problem as training with the penalty in the cost.
• The penalty strength is a Lagrange multiplier. It must rise while the limit is broken, fall while it is met, and never go below zero.
• An explicit limit takes a step downhill and then projects back inside the limit. It acts only when the weights try to leave the region.
• A column limit gives each hidden unit its own allowance, so one unit with large weights does not dominate the others.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 7.2 (pages 237–238), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.