# Applying KKT conditions

This is in relation to this paper

I am looking for ways to optimize Recall @ fixed Precision ($R@P$) for a machine learning problem and i didnt want to use accuracy as a proxy for $R@P$. Upon research i came across this paper:

It goes as follows:

*here $f(b)$ will be the model (classifier) that thresholds at $b$. i.e. $f(b) < b$ are negative samples rest are positive samples

1. Creating building block bounds:

Precision ($P(f_b)) = \dfrac{t_p(f_b)}{t_p(f_b) + f_p(f_b)}$

Recall $(R(f_b)) = \dfrac{t_p(f_b)}{t_p(f_b) + f_n(f_b)} = \dfrac{t_p(f_b)}{|Y^+|}$

where $t_p, f_p, f_n$ are true positives, false positives and false negative counts respectively:

$$t_p(f_b) = \sum_{i \in |Y^+|}\mathbb{1}_{f(x_i) \geq b}$$

$$f_p(f_b) = \sum_{i \in |Y^-|}\mathbb{1}_{f(x_i) \geq b}$$

where $\mathbb{1}$ is the indicator function

Now, lower bound $t_p$ and upper bound $f_p$ by first writing them in terms of the zero-one loss and then replacing that loss by log-loss or hinge-loss

$$t_p(f_b) = \sum_{i \in |Y^+|}(1 - l_{01}(f_b, x_i, y_i))$$

$$f_p(f_b) = \sum_{i \in |Y^-|}l_{01}(f_b, x_i, y_i) \tag1$$

Now, these quantities are bound by replacing $l_{01}$ by loss function $l(f_b, x_i, y_i)$ which are $l_{01}$'s convex upper bounds (example: log-loss, hinge loss.. here i will write with hinge loss)

$$t_p(f_b) = \sum_{i \in |Y^+|}(1 - l(f_b, x_i, y_i)) \leq t_p(f_b)$$

$$f_p(f_b) = \sum_{i \in |Y^-|}l(f_b, x_i, y_i) \geq f_p(f_b)\tag2$$

**Now hinge loss is ${\displaystyle \ell (y)=\sum _{t\neq y}\max(0,1+\mathbf {w} _{t}\mathbf {x} -\mathbf {w} _{y}\mathbf {x} )}$ which is convex in the final output (logits) of the network that get fed into the loss function but not in the parameters of the model (for example deep neural network) **

Now coming back to the problem at hand which is to maximize recall at fixed minimum precision

$$R@P_\alpha = \underset{f}{max} R(f) s.t. P(f) \geq \alpha$$

this is a difficult combinatorial problem, hence we instead try to maximize its lower bound

$\underset{f,b}{max} \dfrac{1}{|Y^+|}{t_p(f)}$ s.t. $t_p(f) \geq \alpha(t_p(f) + f_p(f))$

this is turned into a tractable optimization surrogate, we use (2) to lower bound $t_p$ and upper bound $f_p$:

$\overline{R@P_\alpha} = \underset{f,b}{max} \dfrac{1}{|Y^+|}{t_{p_l}(f)}$ s.t. $t_{p_l}(f) \geq \alpha(t_{p_l}(f) + f_{p^u}(f))$

Now, The author says $\overline{R@P_\alpha}$ is a concave lower bound for $R@P_\alpha$ (lemma 4.1 in paper hyperlinked). Which i dont have an issue with. But $\overline{R@P_\alpha}$ is concave in the outputs of $f$ and not in the parameters of $f$

Now, the authors proceed as follows:

$$\overline{R@P_\alpha} = \underset{f}{max}(1-\dfrac{\mathbb{L^+}(f)}{|Y^+|}) s.t.(1-\alpha)(|Y^+| - \mathbb{L^+}(f)) \geq \alpha\mathbb{L^-}(f)$$

from now we denote, the loss on positive samples as $\mathbb{L^+}(f) = \sum_{i \in |Y^+|}l(f_b, x_i, y_i)$ and loss on negative samples as $\mathbb{L^-}(f) = \sum_{i \in |Y^-|}l(f_b, x_i, y_i)$

Now, $|Y^+|$ is constant for the data observed

so, the previous equation is equivalent to $$\underset{f}{min}{\mathbb{L^+}} s.t. \alpha\mathbb{L^-} + (1- \alpha)\mathbb{L^+} \leq(1-\alpha)|Y^+|\tag3$$

Sorry for the long post. But here lies the part that i cannot understand:

(3) is transformed using lagrange's multiplier theory to the following equivalent objective:

$$\underset{f}{min}\underset{\lambda}{max} \mathbb{L^+} + \lambda(\dfrac{\alpha}{1-\alpha}{\mathbb{L^-}} + \mathbb{L^+} - |Y^+|)$$

And the final suggestion by the authors is to tackle this saddle point problem by gradient descent

$$f^{t+1} = f^{t} - \gamma\nabla L(f^t, \lambda^t))$$ $$\lambda^{t+1} = \lambda^{t} + \gamma\nabla L(f^t, \lambda^t))$$

Where $L(f, \lambda) = (1+\lambda)\mathbb{L^+}(f) + \lambda(\dfrac{\alpha}{1-\alpha}{\mathbb{L^-}}(f) - \lambda|Y^+|$

But, this entire explanation assumes that loss is convex in the parameters of the model which is clearly not the case. Any help is greatly appreciated. Been struggling with this for almost 2 days now. Many many many thanks