0
$\begingroup$

Suppose I have the following objective function

$$ L = \frac{1}{|X|}\sum_{x \in X} \| \hat{y} - y \|^2_2 + \lambda \|w\|_2^2 $$

where $X$ are my data, $\hat{y}$ the prediction, $y$ the target, $\lambda$ the regularization coefficient, and $w$ the model's parameters.

In Machine Learning we use regularization to obtain models that can hopefully generalize to unseen data. But, what is the role of regularization in optimization?

$\endgroup$
4
  • 1
    $\begingroup$ It's not so much optimization, since the optimal $\textbf{w}$ can be solved analytically, but rather for numerical stability. See here: math.stackexchange.com/questions/3100267/… $\endgroup$
    – Tom Chen
    Feb 14, 2019 at 22:43
  • 1
    $\begingroup$ What do you mean by “pure optimization”? $\endgroup$
    – David M.
    Feb 14, 2019 at 23:12
  • $\begingroup$ @DavidM. The optimization done by Mathematicians, where the main aim is to fit the training set $\endgroup$
    – Karl Alexius
    Feb 15, 2019 at 9:41
  • $\begingroup$ @TomChen Thank you, this is what I was looking for...could you please point me to a reference paper? $\endgroup$
    – Karl Alexius
    Feb 15, 2019 at 9:42

2 Answers 2

Reset to default
4
$\begingroup$

The closest that "pure optimization" gets to regularization is probably the field of Robust Optimization, which aims to improve performance on unseen data by arming an adversary with the ability to perturb your solution ex-post. That is, you make a decision, then nature gets to selects the worst-case realization from some uncertainty set to change the problem slightly, but you are aware of what nature is going to do when you make your decision, so you make a better decision with respect to unseen data.

Indeed, in linear regression, the following robust linear regression problem:

\begin{align*} \min_{w} \ \max_{\Delta: \Vert \Delta \Vert_F \leq \lambda} \ \frac{1}{\vert X \vert} \sum_x \Vert (\Delta+X)w-y\Vert_2^2, \end{align*} is directly equivalent to your original problem, by duality!

See this paper: https://www.sciencedirect.com/science/article/abs/pii/S0377221717302734 for more information on this.

$\endgroup$
3
$\begingroup$

One idea is that adding a regularization term $\lambda \|x\|^2$ to the objective function in a convex optimization problem ensures that the new objective function $f$ is strongly convex. This allows the use of optimization algorithms which require an assumption of strong convexity.

For example, since $f$ is strongly convex, its convex conjugate $f^*$ which appears in the dual problem is guaranteed to be differentiable, and this is helpful when using a gradient-based algorithm to solve the dual problem.

$\endgroup$
2
  • $\begingroup$ But if the function used to compute $\hat{y}$ is not convex, adding $\lambda ||w||^2$ does not make the the whole function $L$ convex. Right? $\endgroup$
    – Karl Alexius
    Feb 15, 2019 at 9:35
  • $\begingroup$ @KartAlexius that is correct, nonconvex + strongly convex is not necessarily even convex. However, convex + strongly convex is strongly convex, which was the original claim of littleO $\endgroup$
    – Kwame Gonzales
    Feb 15, 2019 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .