3
$\begingroup$

I am not sure if this is a true statement or not but there appears to be an intuition around this among experts in the field that I do not quite understand.

The idea is: Given a convex optimization problem that will be solved using gradient descent, it is sometimes advantageous to add an extra term to the objective function (the regularizer). On Wikipedia, it suggests that regularizers are good to avoid overfitting but in our case, the problem is simply finding an optimal $x^*$ that minimizes a convex function $f(x)$ so this doesn't seem to apply.

So in what sense is adding a regularizer better for convex optimization? How can one prove, for instance, that convergence is faster if we add this term? I realize this is perhaps a basic and broad question so references are fine too, if an answer is too big to fit in the scope of this site.

$\endgroup$

1 Answer 1

6
$\begingroup$

Yes, there are situations where regularization can speed up convergence of gradient descent. But, if you add a regularization term to the objective function, you will no longer be optimizing the same function, and the solution will differ. This is an intended effect when regularization is used to impose inductive bias in a learning problem (e.g. when seeking to avoid overfitting). But, this may be undesirable if your goal is simply to speed up convergence in an optimization problem. In that case, you'd be better off addressing the problem by changes to the optimization algorithm rather than the objective function. That's outside the scope of this question, but briefly, take a look at Newton, quasi-Newton, and conjugate gradient methods. Also note that preconditioning can speed up optimization for same reasons described below for regularization.

To answer the original question...

How regularization can speed up convergence

One situation where regularization can speed up gradient descent occurs when the objective function contains long, narrow valleys whose walls are steeply sloped, but whose floor slopes only gradually toward the minimum. In this case, the steepest descent direction at most locations points toward the valley floor. Gradient descent will make only slow progress toward the minimum (due to the shallow slope in that direction), and might oscillate back and forth between the walls (due to their steepness). See the left example plot below.

Some forms of regularization change the objective function to be more bowl-shaped. In this case, steepest descent directions point more toward the minimum, and the slope along valley floor is increased. Here, gradient descent can make faster progress toward the minimum. See the right example plot below.

Example

Here's a simple example: solving for linear regression coefficients in 2 dimensions. $X$ contains Gaussian inputs with highly correlated columns. $y$ contains targets, generated as a linear function of the inputs, plus i.i.d. Gaussian noise.

Ordinary least squares (unregularized) is used in the left plot:

$$\min_{w} \ \|y - X w\|^2$$

Ridge regression ($\ell_2$ regularization) is used in the right plot:

$$\min_{w} \ \|y - X w\|^2 + \lambda \|w\|^2$$

The gradient descent path (starting from the same initial point) is shown superimposed on the objective function:

enter image description here

Highly correlated inputs make the ordinary least squares objective function highly elongated. $\ell_2$ regularization makes the objective function more bowl-shaped, and gradient descent requires fewer iterations to converge (17 vs. 100). Note that the solution is different as a consequence of the regularization term.

$\endgroup$
3
  • $\begingroup$ Great answer, thank you! Just one follow up - I'm thinking of the case where we impose a constraint on the search space, say $x>0$, so now the search space with the constraint is smaller. Now rewrite the problem by imposing a penalty term when the constraint is violated i.e. $f(x) \rightarrow f(x) + \alpha g(x)$. where $\alpha\geq 0, g(x)<0$ only if $x>0$. This also looks like a regularization and yes the new solution is different as you pointed out but is this also a correct way of seeing why adding that regularization term makes things more efficient by reducing the size of the search space? $\endgroup$ Feb 20, 2019 at 10:56
  • 1
    $\begingroup$ It's true that a constrained problem can sometimes be rewritten in an equivalent penalized/langrangian form and vice versa. For example, the $l_2$ penalized problem I mentioned is equivalent to constraining the weights to lie within a hypersphere centered at the origin (whose radius is inversely related to the penalty strength). Barrier methods are also somewhat related. But, I'm not so sure about the "size of search space" explanation. I think that imposing constraints (or penalties) will restrict the search space, but may not necessarily affect convergence speed. $\endgroup$
    – user20160
    Feb 20, 2019 at 12:47
  • 1
    $\begingroup$ For instance, in the regression example I plotted, imposing nonnegativity constraints wouldn't have any effect on convergence, as we never leave the positive region of parameter space. $\endgroup$
    – user20160
    Feb 20, 2019 at 12:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.