Why is the regularization term *added* to the cost function (instead of multiplied etc.)?

Question

Whenever regularization is used, it is often added onto the cost function such as in the following cost function. $$ J(\theta)=\frac 1 2(y-\theta X^T)(y-\theta X^T)^T+\alpha\|\theta\|_2^2 $$ This makes intuitive sense to me since minimize the cost function means minimizing the error (the left term) and minimizing the magnitudes of the coefficients (the right term) at the same time (or at least balancing the two minimizations).

My question is why is this regularization term $\alpha\|\theta\|_2^2$ added onto the original cost function and not multiplied or something else which keeps the spirit of the motivation behind the idea of regularization? Is it because if we simply add the term on it is sufficiently simple and enables us to solve this analytically or is there some deeper reason?

Answer 1

It has quite a nice intuition in the Bayesian framework. Consider that the regularized cost function $J$ has a similar role as the probability of a parameter configuration $\theta$ given the observations $X, y$. Applying the Bayes theorem, we get:

$$P(\theta|X,y) = \frac{P(X,y|\theta)P(\theta)}{P(X,y)}.$$

Taking the log of the expression gives us:

$$\log P(\theta|X,y) = \log P(X,y|\theta) + \log P(\theta) - \log P(X,y).$$

Now, let's say $J(\theta)$ is the negative¹ log-posterior, $-\log P(\theta|X,y)$. Since the last term does not depend on $\theta$, we can omit it without changing the minimum. You are left with two terms: 1) the likelihood term $\log P(X,y|\theta)$ depending on $X$ and $y$, and 2) the prior term $ \log P(\theta)$ depending on $\theta$ only. These two terms correspond exactly to the data term and the regularization term in your formula.

You can go even further and show that the loss function which you posted corresponds exactly to the following model:

$$P(X,y|\theta) = \mathcal{N}(y|\theta X, \sigma_1^2),$$ $$P(\theta) = \mathcal{N}(\theta | 0, \sigma_2^2),$$

where parameters $\theta$ come from a zero-mean Gaussian distribution and the observations $y$ have zero-mean Gaussian noise. For more details see this answer.

---

¹ Negative since you want to maximize the probability but minimize the cost.

Answer 2

Jan and Cagdas give a good Bayesian reason, interpreting the regularizer as a prior. Here are some non-Bayesian ones:

• If your unregularized objective is convex, and you add a convex regularizer, then your total objective will still be convex. This won't be true if you multiply it, or most other methods of combining. Convex optimization is really, really nice compared to non-convex optimization; if the convex formulation works, it's nicer to do that.

• Sometimes it leads to a very simple closed form, as wpof mentions is the case for ridge regression.

• If you think of the problem you "really" want to solve as a problem with a hard constraint $$ \min_{\theta : c(\theta) \le 0} J(\theta) ,$$ then its Lagrange dual is the problem $$ \min_\theta J(\theta) + \lambda c(\theta) .$$ Though you don't have to use Lagrange duality, a lot is understood about it.

• As ogogmad mentioned, the representer theorem applies to the case of an additive penalty: if you want to optimize $f$ over a whole reproducing kernel Hilbert space of functions $\mathcal H$, then we know that the solution to optimization over the whole space $$ \min_{f \in \mathcal H} J(f) + \lambda \lVert f \rVert_{\mathcal H}^2 $$ lies in a simple finite-dimensional subspace for many losses $J$; I don't know if this would hold for a multiplicative regularizer (though it might). This is the underpinning of kernel SVMs.

• If you're doing deep learning or something non-convex anyway: additive losses give simple additive gradients. For the simple $L_2$ regularizer you gave, it becomes very simple weight decay. But even for a more complicated regularizer, say the WGAN-GP's loss $$ \sum_{x,y} \underbrace{f_\theta(x) - f_\theta(y)}_\text{the loss} + \lambda \underbrace{\mathbb{\hat E}_{\alpha \sim \mathrm{Uniform}(0, 1)} \left( \lVert \nabla f_\theta(\alpha x + (1 - \alpha) y) \rVert - 1\right)^2}_\text{the regularizer}, $$ it's easier for backpropagation to compute gradients when it only has to consider the sum of the loss and the complicated regularizer (considering things separately), instead of having to do the product rule.

• Additive losses are also amenable to the popular ADMM optimization algorithm, and other "decomposition"-based algorithms.

None of these are hard-and-fast rules, and indeed sometimes a multiplicative (or some other) regularizer might work better (as ogogmad points out). (In fact, I just the other day submitted a paper about how something you could interpret as a multiplicative regularizer does better than the WGAN-GP additive one above!) But hopefully this helps explain why additive regularizers are "the default."

Answer 3

You want to minimize both terms in the objective function. Therefore, you need to decouple the terms. If you multiply the terms you can have one term large and the other very low. So, you still end up with a low value of the objective function, but with an undesirable result.

You may end up with a model that has most variable close to zero with no predictive power.

The objective function, which is the function that is to be minimized, can be constructed as the sum of cost function and regularization terms.

In case both are independent on each other, you get the values illustrated in the first figure for the objective. You see in case of the sum, there is only one minimum at (0, 0). In case of the product you have ambiguity. You have a whole hyper-surface equal to zero at (x=0 or y=0). So, the optimization algorithm can end up anywhere depending on your initialization. And it cannot decide which solution is better.

Answer 4

You can try other binary operations ($\max,\min,\times$) and see how they compare.

The problem with $\min$ and $\times$ is that if the error is $0$, then the regularized penalty will end up being $0$. This allows the model to overfit.

The problem with $\max$ is that you end up minimizing the "harder" of the two penalties (training error or regularization) but not the other.

In contrast, $+$ is simple and it works.

You might ask why not other binary operations? There's no argument that could rule them out, so why not indeed?

Answer 5

I think you have a valid question. To give you a proper answer you will have to understand the probabilistic nature of the problem.

In general the problem we are trying to solve is the following: Given data $D$ what is the distribution of hypotheses that explains this data. When we say hypothesis we mean a PDF (at least in this context). And a distribution of hypotheses is a PDF of PDFs, i.e., $p(H | D)$.

1. $p(H | D)$ is a distribution over hypotheses given $D$. If we can find this then we can select one among these hypotheses, for example the one with the highest probability, or we may choose to average over all of them. A somewhat easier approach is to attack the problem from a different direction using the Bayes' Theorem.

   $$p(H|D) = \frac{p(D|H)\times p(H)}{p(D)}$$

2. $p(D|H)$ is one of the hypothesis, it is also called likelihood. $p(H)$ is the distribution of the hypotheses in our universe of hypotheses before observing the data. After we observe the data we update our beliefs.

3. $p(D)$ is the average of the hypotheses before we updated our beliefs.

Now if we take the $-\log$ of both sides of Bayes' equation we get:

$$-\log [p(H|D)] = -\log [p(D|H)] -\log [p(H)] + \log [p(D)]$$

Usually $p(D)$ is difficult to calculate. The good thing is it doesn't affect the result. It is simply a normalization constant.

Now for example if our set of hypotheses $p(D|H)$ is a bunch of Gaussians with $p(y|X,\theta)\sim N(\theta X,\sigma)$ where we don't know $\theta$, but assume to know $\sigma$ (or at least assume that it is a constant), and moreover hypotheses themselves are distributed as a Gaussian with $p(H) = p(\theta) \sim N(0,\alpha^{-1} I)$ then plugging everything above looks something like:

$$-\log [p(H|D)] = \text{bunch of constants} + \frac{1}{2}(y-\theta X)^2 + \frac{1}{2}\alpha||\theta||^2 + {\rm constant}$$

Now if we minimize this expression we find the hypothesis with the highest probability. Constants don't affect the minimization. This is the expression in your question.

The fact that we used Gaussians doesn't change the fact the regularization term is additional. It must be additive (in log terms or multiplicative in probabilities), there is no other choice. What will change if we use other distributions is the components of the addition. The cost/loss function you have provided is optimal for a specific scenario of Gaussians.

Answer 6

Ridge is a very convenient formulation. In contrast to the probabilistic answers, this answers does not give any interpretation of the estimate but instead explains why ridge is an old and obvious formulation.

In linear regression, the normal equations give $\hat{\theta} = (X^TX)^{-1} X^T y$

But, the matrix $X^TX$ is sometimes not invertible; one way to adjust it is by adding a small element to the diagonal: $X^TX + \alpha I$.

This gives the solution: $\tilde{\theta} = (X^TX + \alpha I)^{-1} X^T y$; then $\tilde{\theta}$ does not solve the original problem but instead the ridge problem.

Answer 7

I think there is a more intuitive reason as to why we can't multiply by the regularisation term.

Lets take our penalty function to the regular penalty function multiplied by a regularisation term like you suggest.

$$J(θ)=(\frac{1}{2}(y−θX^T)(y−θX^T)^T)α‖θ‖^2_2$$

Here we create a global minimum of the penalty function where $α‖θ‖^2_2=0$. In this case our model can produce high errors between the prediction and the data but it doesn't matter, if the model parameter weights are all zero our penalty function is zero $J(θ=0)=0$.

Since, unless our model is completely perfect, the term $(\frac{1}{2}(y−θX^T)(y−θX^T)^T)$ can never be zero (the probability that there exists a set θ to make our model 'perfect' is negligible for real data), then our model should always tend train towards the solution θ=0.

This is what it will return unless it gets stuck in a local minimum somewhere.