Convex optimization: Is gradient descent faster if a regularizer is added? 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.
 A: 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:

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.
