# How do I check if a loss function can achieve its minimum?

For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its minimum. But for a penalized objective $g(\beta)= ||Y-X\beta||^2+\lambda\sum_{j=1}^p|\beta_j|$ with $\lambda > 0$, does $g(\beta)$ achieve its minimum? How do I prove/disprove this in general?

TL;DR: The property you are looking for is coercivity. This is satisfied for the example in your question (as are properties 1 and 3 below), and hence yes, the penalized objective attains its minimum.

The classical proof of existence of minimizers of (a very general class of) functionals is the so-called direct method of the calculus of variations (originally due to Hilbert and developed in its current form by Tonelli). For the sake of completeness, I give the full version in infinite-dimensional spaces, but you can ignore the fine details if you are only interested in finite-dimensional problems. If you are interested in the full details, I have a set of lecture notes on nonsmooth optimization at https://arxiv.org/abs/1708.04180. (Not that this is the best reference; it's just that I know it's in there.)

Let $X$ be a reflexive Banach space (in particular, $\mathbb{R^N}$) and $F:X\to \mathbb{R}\cup \{+\infty\}$ (this allows including hard constraints into the functional). If $F$ is

1. proper (meaning that it is not equal to $\infty$ everywhere),

2. coercive (meaning $\|x\|\to\infty$ implies $F(x)\to \infty$), and

3. weakly lower semicontinuous (meaning if $x_n \to x$ weakly, then $F(x)\leq \liminf_{n\to\infty} F(x_n)$),

then the minimum of $F$ over $X$ is attained in some $\bar x\in X$ (for which $F(\bar x)<\infty$).

The proof is fairly simple and uses these properties in a straightforward way:

1. Since $F$ is proper, the set $\{F(x):x\in X\}\subset\mathbb{R}$ attains an infimum $M:=\inf_{x\in X} F(x)<\infty$ (although $M=-\infty$ may be possible). By the definition of the infimum, there exists a sequence $\{x_n\}_{n\in\mathbb{N}}\subset X$ with $$F(x_n) \to M = \inf_{x\in X} F(x).$$ Such a sequence is called minimizing sequence. Note that from the convergence of $\{F(x_n)\}_{n\in\mathbb{N}}$ we cannot conclude the convergence of $\{x_n\}_{n\in\mathbb{N}}$ (yet).

2. Suppose now that $\{x_n\}_{n\in\mathbb{N}}$ were unbounded, i.e., that $\|{x_n}\|_X\to\infty$ for $n\to \infty$. The coercivity of $F$ then implies that $F(x_n)\to \infty$ as well, in contradiction to $F(x_n)\to M<\infty$ by definition of the minimizing sequence. Hence, the sequence is bounded and thus contains a weakly (in finite-dimensional spaces, strongly) converging subsequence $\{x_{n_k}\}_{k\in\mathbb{N}}$ with limit $\bar x\in X$. (This limit is a candidate for the minimizer.)

3. From the definition of the minimizing sequence, we also have $F(x_{n_k})\to M$ for $k\to\infty$. Together with the weak lower semicontinuity of $F$ and the definition of the infimum we thus obtain \begin{equation*} \inf_{x\in X} F(x) \leq F(\bar x) \leq \liminf_{k\to\infty} F(x_{n_k}) = M = \inf_{x\in X} F(x)<\infty. \end{equation*} This implies that $F(\bar x)<\infty$ and that $\inf_{x\in X} F(x)=F(\bar x)> -\infty$. Hence, the infimum is attained in $\bar x$ which is therefore the desired minimizer.

Note how these three properties serve to exclude the obvious counterexamples:

1. excludes the obviously degenerate case that there's nothing to minimize over and is clearly satisfied for any real-valued functional;

2. excludes exactly your counterexample $f$; for $g$, you have $$g(\beta) = \|{Y-X\beta}\|_2^2 + \lambda \|\beta\|_1 \geq C\|\beta\|_1,$$ and hence the penalized objective is indeed coercive.

3. excludes functions such as $$f(t) = \begin{cases} t^2+1 & t\leq 0 \\ t^2 & t>0 \end{cases}$$ for which the infimum is $0$, but this is not attained for any $t\in \mathbb{R}$. In $\mathbb{R}^N$, you don't need to worry about the difference of weak and strong convergence; in particular, the property is satisfied for any continuous $F$ (such as all your examples).

Note that convexity didn't play any role here; what this buys you is that any minimizer is a global minimizer (which is unique if the function is strictly convex). Also, convex functions are weakly lower semicontinuous if they are strongly lower semicontinuous even in infinite-dimensional spaces, where the former is a stronger property than the latter.

• Very interesting to learn this. Do you mean $F$ has to maintain properties 1-3 or at least one of three? $f$ satisfies property 3 but it doesn't attain its minimum as you implied. A proof will be helpful and a reference for studying will be appreciated as well. – John Smith May 9 '18 at 10:55
• Yes, all three properties are necessary as the examples show. I've included the proof and (shameless plug) a link to my lecture notes where this topic is treated in detail. – Christian Clason May 9 '18 at 11:14
• Very grateful for the detailed answer. – John Smith May 9 '18 at 11:32
• @JohnSmith Yes, that was a typo (as was $\mathbb{R^N}$), which I've just corrected -- thanks! And yes, $X$ is closed -- that is included in the assumption that $X$ is a Banach space. And $\mathbb{R}^N$ is indeed closed (as well as open), it's just not bounded -- but that is not necessary if $F$ is coercive. (Note that any hard constraint $x\in C \subsetneq X$ is included in $F$ by setting the value to $\infty$ outside $C$ -- if $C$ is bounded, $F$ is automatically coercive. If $C$ is weakly closed (or convex and closed), $F$ is also weakly lower semicontinuous.) – Christian Clason May 10 '18 at 7:39
• You'd have to argue as follows: First argue that $\min_{\beta \in \mathbb{R}^n} f(\beta) = \min_{\beta \in \mathrm{ker} X^{\bot}} f(\beta)$, where $\mathrm{ker} X^{\bot}$ is the orthogonal complement of the kernel. Since $\mathrm{ker} X^{\bot}$ is closed, then you can apply the theorem to this new formulation, where $f(\beta)$ is coercive (by construction). – Christian Clason Jun 13 '18 at 15:24

The only thing you can in general say about convex optimisation problems is: If there is a local minimum, this is the global minimum.

It can be relaxed to: If the function has a stationary point, and is convex, this stationary point is a global minimum. Stationary points $\beta^*$ are such that fulfill $\nabla f(\beta^*) =0$. Your function is a sum of two convex functions, which makes it convex. Your function is non-differentiable in $0$. However, it may still have a stationary point $\beta^*$ that is not $0$. If you find such a stationary point, you are done.

In your case, we have $$g(\beta)= \|Y-X\beta\|^2+\lambda\sum_{j=1}^p|\beta_j|,$$ this implies $\nabla g(\beta) = -2(Y-X\beta)X + \nabla h(\beta)$, where the $h(\beta) = \lambda\sum_{j=1}^p|\beta_j|$ and $$(\nabla h(\beta))_j = \begin{cases}\lambda, &\beta_j \geq 0 \\ -\lambda, &\beta_j < 0\end{cases}.$$ Now you "just" have to find $\beta^*$, which may be easier with a semi-smooth Newton method.

• this does not quite answer the OP's question because you a priori assume the existence of a local minimizer $\beta$ (a proof that such a $\beta$ exists is what the OP is asking for) – GoHokies May 9 '18 at 11:34
• I don’t. I clarified that. I assume that the function is convex, which I argue, and give steps to check whether it has a stationary points - which is has or hasn’t, depending on the actual parameters. – Jonas May 9 '18 at 12:00
• @jonas But you want to have $\beta_j^*=0$ for as many $j$ as possible (while still matching $Y$ sufficiently well) -- that is the whole point of using this penalty term! And you haven't actually given a way to check a priori that a stationary point exists. (Running a numerical algorithm is not a suitable way, since you have no guarantee that it'll work in practice -- in fact, most convergence proofs assume the existence of a stationary point to show that it convergences to that. If you try to compute something that doesn't exist, you can expect it to blow up in your face...) – Christian Clason May 10 '18 at 8:15