7
$\begingroup$

My loss has two parts, say L1 and L2. I want to minimize both, and at the same time I need to constrain that L1 should be always greater than L2 (L1>L2). Is the following correct?

loss = L2 - L1

$\endgroup$
15
$\begingroup$

This isn't exactly what you've asked for, but it's a very easy solution to implement in neural network libraries like keras, tensorflow and pytorch.

The main idea is to penalize the loss whenever the inequality $L_1 > L_2$ is violated. This inequality is violated whenever $L_2 \ge L_1$;on the other hand, we don't want to penalize the loss at all when $L_1 > L_2$. This describes a ReLU function in $L_1, L_2$:

$$ \min L_1 + L_2 + \lambda\text{ReLU}(L_2 - L_1) $$

The hyper-parameter $\lambda>0$ controls how steep the penalty should be for violating the inequality.

This loss doesn't guarantee that the inequality is satisfied, but it is an improvement over minimizing $L_1 + L_2$ alone.

This loss is just a composition of functions readily available in modern neural network libraries, so it's simple to implement.

In comments, jkpate makes the following suggestion:

Notice that if you incorporate a maximization over $\lambda$, then we do get exactly what the poster asked for because we now have a two-player formulation of the Lagrange dual to the original constrained optimization problem. Essentially, rather than setting $\lambda$ be fixed, we allow the penalty for a violation to grow. See Cotter et al. "Two-Player Games for Efficient Non-Convex Constrained Optimization" (2019) for the theory and https://github.com/google-research/tensorflow_constrained_optimization for a Tensorflow implementation.

If I understand correctly, this allows the estimation procedure to select a good value of $\lambda$, rather than the user fixing a particular value ahead of time and worrying about whether that fixed value is a good choice.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is pretty much what I would think of as well, though I was typing up $RELU(L_2 - L_1)^2$ as the penalty term. I've done this in practice for constrained minimization problems. It's a bit fussy, but can work out. $\endgroup$ – Matthew Drury Apr 30 at 19:42
  • 1
    $\begingroup$ @MatthewDrury it might be worth adding your answer just because I’m interested in understanding why you prefer to square it. I’ve never used a loss like this so I’m just spitballing. $\endgroup$ – Sycorax Apr 30 at 20:47
  • 5
    $\begingroup$ Notice that if you incorporate a maximization over $\lambda$, then we do get exactly what the poster asked for because we now have a two-player formulation of the Lagrange dual to the original constrained optimization problem. Essentially, rather than setting $\lambda$ be fixed, we allow the penalty for a violation to grow. See Cotter et al. (2019) for the theory and github.com/google-research/tensorflow_constrained_optimization for a tensorflow implementation. $\endgroup$ – jkpate May 1 at 11:10
  • $\begingroup$ @jkpate This is a good find! I can edit my answer to add this, but on the other hand, I think if you wrote an answer summarizing these findings, you'd get several upvotes. I know you'd get one from me. $\endgroup$ – Sycorax May 4 at 12:37
12
$\begingroup$

That will likely give you unexpected results. Minimizing your loss will incentivize your algorithm to minimize L2, but to maximize L1. There is no incentive to minimize L1.

It sounds like you have a constraint minimization problem: minimize L1+L2, subject to L1>L2. This is very common in optimization software, but less so in ML fitting software. You will likely need to feed this into your modeler in some tool-specific way, if such a constraint can be modeled at all.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

No, that is not correct. If you want to minimize both, definitely you should write L1+L2, but not L2-L1.

This is because in L2-L1, we can always make L1 to be huge (maximize L1) to make the final loss small.

The problem can be formulated to

$$\text{minimze} ~~L_1+L_2$$ $$\text{st.}~ L_2 -L_1 >0$$

And in many case, if we want to emphasize one loss than another we can use a weighted sum where

$$\text{minimze} ~~\alpha L_1+ (1-\alpha)L_2$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I would try to follow the Kuhn-Tucker problem setup for inequality constrained optimization. Here's how its objective is set as a Lagrangian: $$L(x,\lambda)=L_1(x)+L_2(x)+\lambda(L_2(x)-L_1(x))$$

You need to find a saddle point where $\nabla L=0$, then $x$ will be the optimum. Normally, in optimization we don't like saddle points though, because they're not optima. However, in this case we're optimizing both $x$ and $\lambda$, not just $x$, so the saddle point is what we need.

Maybe experiment with Newton's method optimizer in your Neural Net. Unlike some other optimizers, such as SGD, this one is attracted to saddle points. I like @Sycorax answer where he uses ReLU. However, I believe than Kuhn-Tucker lagrangian will be more efficient if you manage to convine your NN that saddle points are Ok. The reason being is that ReLU will have a flat gradient everywhere where $L_1>L_2$, so the speed convergence must be relatively lower. At the same type ReLU is obviously a no brainer to setup in any NN.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.