2
$\begingroup$

I am currently reading the paper Exponential Convergence Rates in Classification (2005) by Vladimir Koltchinskii and Oleksandra Beznosova, and I'm having trouble following the proof of the main result, which is about the convergence rate of the Empirical Risk Minimizer to the Bayes Classifier. Let me introduce the relevant notations :

We are dealing with a binary classification problem, so there is a dataset of $n$ pairs $(X_i,Y_i)\in\mathcal X\times\mathcal Y$ where $\mathcal X\subseteq \mathbb R^d$ and $\mathcal Y = \{-1,1\}$. To learn a classifier on this dataset, we optimize the penalized Empirical Risk over a RKHS $\mathcal H$ of functions defined on $\mathcal X$. In other words, given our dataset, we set our classifier $\hat f_n$ as $$\hat f_n := \arg\min_{f\in\mathcal H}\ \underbrace{\frac 1 n\sum_{i=1}^n\ell(Y_if(X_i)) + \lambda\|f\|^2}_{\mathcal P_n(f)} \tag1$$ Where $\|\cdot\| $ is the norm induced by the RKHS inner product, $\lambda$ is a nonnegative real parameter and $\ell$ a smooth and convex loss function. So far so good.

Next, for some function $h\in\mathcal H$ (satisfying some assumptions that can be found on page 5), the authors define the function $\mathcal L_n$ as $$\mathcal L_n : \mathbb R\ni\alpha \mapsto \frac 1 n\sum_{i=1}^n\ell[Y_i(\hat f_n(X_i)+\alpha h(X_i))] + \lambda\|\hat f_n+\alpha h\|^2 = \mathcal P_n(\hat f_n + \alpha h)$$ One can clearly see that, because $\hat f_n$ is defined as a minimizer of $\mathcal P_n$, $\mathcal L_n$ is minimal at $\alpha = 0$.

What I am having trouble with however, is the claim (page 7) that because $\mathcal L_n(\alpha)$ is minimal at $\alpha = 0$ , we have

$$ \frac{\partial\mathcal L_n(\alpha)}{\partial\alpha}\bigg|_{\alpha=0} = 0\tag2$$

Furthermore, the authors seems to implicitly assume that the minimizer of $(1)$ is unique which is not immediately clear to me.

My question is thus the following : Why do we have $\partial_\alpha\mathcal L_n(0) = 0$ ?


Update : My background dealing with functional derivatives is basically non-existent, so there may be something obvious I am missing. Nonetheless, let me try to better illustrate what I don't understand :
After reading this introductory note by Frigyik, Srivastava and Gupta and the Wiki pages on Gâteaux and Fréchet derivatives, I got that the quantity $\partial_\alpha\mathcal L_n(0)$ is essentially the Gâteaux/Fréchet derivative of $\mathcal P_n$ at point $\hat f_n$, i.e. $$\frac{\partial\mathcal L_n(\alpha)}{\partial\alpha}\bigg|_{\alpha=0} = D\mathcal P_n(\hat f_n) $$ I also got that, if $\hat f_n$ is a (local) minimizer of $\mathcal P_n$, then $D\mathcal P_n(\hat f_n)$ has to be zero.

My issue however is that $\hat f_n$ is a minimizer of $\mathcal P_n$ only over the set $\mathcal H$, and there are no guarantees that it contains any (local) minimizer of $\mathcal P_n$ (as a functional over the (much) bigger set $\mathbb R^{\mathcal X}$). As an example, consider a non-zero function $g$ defined on $\mathcal X$ and consider the set $\mathcal G = \{\kappa g, \kappa\in\mathbb R\}$. If we define $$\hat g_n :=\arg\min_{g\in\mathcal G} \mathcal P_n(g)$$ We would conclude that $\hat g_n$ is a local minimum of $\mathcal P_n$ no matter what (non trivial) function $g$ was considered, which means that one could "artificially" create arbitrarily many (local) minimizers of $\mathcal P_n$ which seems very wrong.


Update 2 : To give a better "counterexample", consider the (convex) map defined on $\mathbb R^2$ as $\varphi : \vec x \mapsto \|\vec x\|_2^2$, and consider its restriction to the (convex) set $\mathcal S := \left\{\begin{pmatrix}x\\y\end{pmatrix} \in \mathbb R^2, 1\le y\le 2\right\}$. Clearly, $\vec 0$ is the only global minimizer of $\varphi$, and the only point at which its gradient is zero, but it is not in $\mathcal S$. It is not hard to see either that $$\arg\min_{\vec x\in\mathcal S} \varphi(\vec x) = \begin{pmatrix}0\\1\end{pmatrix} $$ So $(0,1)^T$ is a minimizer of $\varphi$ over $\mathcal S$, but the gradient at that point is not zero.

Similarly, I think it would be possible to build similar counterexamples for problem $(1)$, where $\hat f_n$ is a minimizer of $\mathcal P_n$ over $\mathcal H$ but the Gâteaux derivative at that point is not zero. My question thus remains the same : what conditions on the set $\mathcal H$ need to be made to ensure that the Gâteaux derivative at $\hat f_n$ is zero ? Are they satisfied for problem $(1)$ ?

$\endgroup$
4
  • $\begingroup$ You seem to have understood why the derivative is zero. Regarding the uniqueness of the solution it does not matter. If there are multiple global minimizers on $\mathcal{H}$, just pick one of them and use that one. Finally, regarding$H$. Yes, it is true that the optimal solution will depend on your choice for $\mathcal{H}$ but it does reflect what really happens in practice and how things are computed. We have no ways to solve the problem in its full generality but we may be able to do so if we put constraints on the families of functions; e.g. by looking for a minimizer in $\mathcal{H}$. $\endgroup$
    – KBS
    Mar 14, 2022 at 0:55
  • $\begingroup$ @KBS thank you for your comment, but I am still not convinced, because a point being a minimizer of the function over an arbitrary subset doesn't imply that the derivative at that point will be zero. See my latest edit for an illustration of what I mean. $\endgroup$ Mar 14, 2022 at 21:58
  • 1
    $\begingroup$ Yes, I guess they either assume the existence of a minimizer in the interior of the set or there is an property that I am missing (possibly at the level of RKHS). I guess that the issue with your counterexample is that you consider is that you are bounded in $y$ and that may not occur for $\mathcal{H}$. Indeed, the set $\mathcal{H}$ may be sufficiently general (and permissive) so that the a minimizer always lies within. I did some research and it seems that the optimization problem is very standard and I would suspect that its properties to be well-known. You can also contact the authors. $\endgroup$
    – KBS
    Mar 14, 2022 at 22:38
  • 2
    $\begingroup$ Likely cannot do better than the answer below, it seems that all you need is that the point at which the maximum or minimum occurs, is in the interior of the set over which you're performing the maximization/minimization. Once it's in the interior, then you can ensure that it's approached from all directions. Note that $0$ is in the interior of $(-\epsilon,\epsilon)$ which is the domain of $\mathcal L_{n}$. In the other situations, the minimizer is either not in the interior (update 2), or possibly not in the set of interest(update 1) at all. $\endgroup$ Mar 19, 2022 at 4:15

2 Answers 2

3
+100
$\begingroup$

This is related to the notion of directional derivative. As you note, $\hat f_n$ is a minimizer of $\mathcal{P}_n$ over $\mathcal{H}$. It follows, that, starting from $\hat f_n$, the functional $\mathcal{P}_n$ is flat in all directions. In other words: For all directions $h\in\mathcal{H}$ (and this is what you also write in the post) it holds that the directional derivative of $ \mathcal{P}_n$ in $\hat f_n$ in direction of $h$ is zero and this is exactly the derivative the paper talks about.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks for your answer ! After thinking about it a bit more, I see that I was wrong in my interpretation of the Fréchet (directional) derivative as an equivalent of the gradient. If anything, that would be the Gâteaux derivative. In particular, I see that in my "counterexample", the directional derivative does vanish at $(0,1)^T$, even if the gradient doesn't. So, to sum it up : $\mathcal L_n$ is a differentiable function achieving a (local) minimum at $\alpha = 0$ which is an interior point, so its derivative at that point has to vanish. Simple as that ! Am I correct ? $\endgroup$ Mar 19, 2022 at 14:57
  • $\begingroup$ @StratosFair I'll wait for the response of Dirk above, but according to me that's definitely correct. If your point of minimum isn't an interior point, the directional derivative is still $0$ in every possible direction that you can approach it from. Of course, there's one point that we've glossed over, which is : what is the domain of $\mathcal L_n$? From the paper, though, it seems that it is at least some open interval around $0$ : which is enough to see that the complete derivative at $0$ exists and is $0$ . $\endgroup$ Mar 20, 2022 at 4:20
  • $\begingroup$ The zoo of notions of derivatives is quite large and for different situations different notions are useful. In the original question you could even use the Gateaux derivative since the domain of definition is a normed space (even Hilbert). In your counterexample you could use directional derivatives or (since objective and domain are convex) the subgradient. In other situations you have to resort to the Karush-Kuhn-Tucker optimality conditions for constrained optimization. $\endgroup$
    – Dirk
    Mar 20, 2022 at 21:16
2
$\begingroup$

Fact 1: Let $a < b$ be real numbers, and let $f : (a, b) \to \mathbb{R}$ be a function. If $x_0\in (a, b)$, $f$ is differentiable at $x_0$, and $f$ attains either a local maximum or local minimum at $x_0$, then $f'(x_0) = 0$.
(Proposition 10.2.6, Page 259, "Analysis I", Terence Tao.)

Since $\alpha = 0$ is a minimizer of $\mathcal{L}_n(\alpha)$, if $\mathcal{L}_n(\alpha)$ is differentiable at $\alpha = 0$, then we have $$\mathcal{L}'_n(0) = 0.$$ (Note: We only need $\mathcal{L}_n(\alpha)$ to be differentiable at the point $\alpha = 0$. We don't need $\mathcal{L}_n(\alpha)$ to be differentiable on an open interval contained zero.)

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, the argument was as simple as that ! I will accept it as it directly answers the question asked in the post, but I'll award the bounty to Dirk as his answer was most helpful in getting a better understanding of the concept of functional derivative :) $\endgroup$ Mar 21, 2022 at 0:14
  • $\begingroup$ @StratosFair Fine :). You are welcome. $\endgroup$
    – River Li
    Mar 21, 2022 at 0:20

You must log in to answer this question.

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