1
$\begingroup$

In supervised machine learning, we typically take a Risk Minimization (RM) point of view when formulating a problem. So, what we typically solve for is the following:

$$ R^L(h) = \underset{h\in\mathcal{H}}{\text{min}}\,\mathbb{E}_{(x,y_x)\sim\mathcal{D}} \Big[ L(h(x), y_x)\Big]$$

where $h(\cdot): \mathbb{R}^m \to \mathbb{R}^d$ ($m$- dimension of input/feature vector and $d$ denotes the number of classes for the classification task) denotes a classifier function, $\mathcal{H}$ is hypothesis class/family of classifiers (essentially a Hilbert space over functions on $\mathbb{R}^m$), $L: \mathbb{R}^d \to \mathbb{R}^+$ is a loss function, and $(x,y_x)$ are i.i.d. samples from a distribution $\mathcal{D}$.

In practice, however, one often employs what's called Regularized Risk Minimization (RRM):

$$ R_\Omega^L(h) = \underset{h\in\mathcal{H}}{\text{min}}\,\mathbb{E}_{(x,y_x)\sim\mathcal{D}} \Big[ L(h(x), y_x) + \lambda\Omega(h)\Big]$$

where $\Omega: \mathcal{H} \to \mathbb{R}^+$ is a differentiable regularization function.

I want to understand under what necessary and/or sufficient conditions can the minimizers of $R^L(h)$ and $R_\Omega^L(h)$ be the same. That is, under what conditions do we get:

$$ \text{arg}\, \underset{h\in\mathcal{H}}{\text{min}} \, R^L(h) = \text{arg}\, \underset{h\in\mathcal{H}}{\text{min}} \, R_\Omega^L(h)$$

Is it even possible in the first place?

$\endgroup$
4
  • $\begingroup$ Welcome to MathOverflow :) Can you provide a little more detail about the context of your problem? I think that in order to elicit helpful answers, you may need to specify e.g. what $\mathcal{H}$ is (I assume it's some Hilbert space of functions on $\mathbb{R}^d$), which loss functions you're considering, whether $\Omega$ is a semi-norm or something more exotic, whether you're interested in sufficient conditions, necessary conditions or both etc. $\endgroup$
    – DCM
    Oct 19, 2020 at 19:08
  • $\begingroup$ Hi @DCM , sorry for the mess; I am new to this community. Thanks for the comments. I have edited the questions. I think it's better now. $\endgroup$
    – Deep Patel
    Oct 19, 2020 at 19:39
  • $\begingroup$ I think this probably practically never happens, but to prove that is probably difficult and almost certainly thankless task. $\endgroup$ Oct 19, 2020 at 20:43
  • $\begingroup$ Yeah, I am thinking the same, @IosifPinelis. But I thought that one could perhaps, for some special classes of functions, prove/disprove it. $\endgroup$
    – Deep Patel
    Oct 20, 2020 at 5:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.