# L2 norm optimization problem

I have an optimization problem where i need to find an image x, that is very close to x' such that:

1. monitor(x') is valid but monitor(x) is invalid. (output is valid when the neural network output is inside bounds of specific box).

2. x is same classified as x' by a neural network(their prediction class is the same).

Note that x is an image with (1,28,28,1) dimension and its transformed to an array with dim 784 in order to pass into a scipy solver.

The optimization problem is represented as follows:

Obj function: minimize L2 norm of (x'- x) with constraints:

1. prediction( transformed image of x) = prediction( transformed image of x')

2. monitor(x) = 0 (0 for invalid)

x is the optimization variable to be found and x' is the valid input passed

So I am using scipy to solve my problem, I tried local optimization (COBYLA and SLSQP) and global optimization(Sgho and differential evolution). I think my problem is non linear and non convex according to my constraints. But some resources pointed out that non convex constraints don't necessarily mean non convex problem.

"Depending on the problem, you may also try to solve it with a solver which give you just a local optimum if the problem is non convex (as ipopt, or bonmin if you have integer variables) and then compare the solution with that of a global MINLP solver as Couenne/BARON/SCIP. If the results are very different the problem is probably non convex. It could also be that some solver gives you as output the information about the convexity of the problem, but I am not sure about that."

Actually, local and global optimization gave me different results, and sgho was performing the best out of all. However all aren't always converging to successful solutions, but sgho performs best. I think this is because of my non linear and non convex constraints.

Is my choice for Sgho and differential evolution good? and so my problem is considered non convex right?

• The key question is what kind of functions prediction, transformed and monitor are. Your objective function is simple, but if these functions are complicated/nonlinear/non-convex/discontinuous, then the problem is difficult to solve. Feb 17, 2021 at 20:35
• So is it in this case nonconvex? yes i think its too compicated especially when having an image of dim 28*28, its hard to converge
– S i
Feb 18, 2021 at 22:45
• We don't know. If all of the three functions above are linear, then the problem is convex and easy. You really need to say more about what these functions are to know. Feb 19, 2021 at 16:09
• monitor is a function that checks if the output at a certain layer of the neural network of x is between a box bound. Transformed is just reshaping an array of 28*28 dimension to a (1,28,28,1) dimension image. Prediction is the predicted label of the image, it is also predicted via a neural network
– S i
Feb 19, 2021 at 17:48
• are they in this case linear?
– S i
Feb 22, 2021 at 8:44

Apparently, your goal is to minimize $$\|x'-x\|_2$$, subject to the conditions that $$m(x') < \ell$$ or $$m(x') > u$$ and $$f(x')$$ predicts the same class as $$f(x)$$, where $$f$$ is a neural network and $$m$$ is some internal value inside $$f$$.

This kind of problem has been considered in the literature on adversarial examples. I will describe a basic approach, and then suggest a more sophisticated approach.

We can decompose this into two optimization problems, one where the goal is to ensure $$m(x')<\ell$$ and one where the goal is to ensure $$m(x')>u$$. I suggest you solve each optimization problem separately. Let's focus on ensuring $$m(x')>u$$, for simplicity (everything can be applied to the other case).

One standard approach is to define two loss functions, $$\mathcal{L}_m$$ and $$\mathcal{L}_f$$, where $$\mathcal{L}_m$$ measures how badly we have failed to achieve our goal of $$m(x')>u$$ and $$\mathcal{L}_f$$ measures how badly we have failed to achieve of our goal of $$f$$ predicting the correct class. Then, define a single loss function $$\mathcal{L} = \mathcal{L}_m + \lambda_f \mathcal{L}_f + \lambda_d \|x' - x\|_2^2,$$ where $$\lambda_f,\lambda_d>0$$ are hyper-parameters, and solve the optimization problem

$$\min_{x'} \mathcal{L}$$

using gradient descent. You can you search over hyper-parameter settings to find the best solution. To turn this into a full solution, we need to describe how to define $$\mathcal{L}_m$$ and $$\mathcal{L}_f$$. One way to do that is to set

\begin{align*} \mathcal{L}_m &= \max(u-m(x'), -\varepsilon)\\ \mathcal{L}_f &= \max(\max \{ z(x')_{y'} \mid y' \ne y \} - z(x')_y, -\varepsilon), \end{align*}

where $$y$$ is the desired predicted class (i.e., the class predicted by $$f(x)$$), and $$z(x')_y$$ are the logits of $$f$$ on input $$x'$$ for class $$y$$, and $$\varepsilon>0$$ is a small constant (its exact value probably doesn't matter too much).

Another alternative is to use projected gradient descent. We pick a distance bound $$b$$, and minimize $$\mathcal{L}_m + \lambda_f \mathcal{L}_f$$ subject to $$\|x-x'\|_2 \le b$$. This can be solved by projected gradient descent, where after each gradient descent step we project to the $$L_2$$ ball of radius $$b$$ surrounding $$x$$. This requires us to choose a distance bound $$b$$; the natural way is to do binary search on $$b$$, to find the smallest $$b$$ for which a valid solution exists.

A more sophisticated method is to use orthogonal gradient descent, as proposed in the following paper:

Evading Adversarial Example Detection Defenses with Orthogonal Projected Gradient Descent. Oliver Bryniarski, Nabeel Hingun, Pedro Pachuca, Vincent Wang, Nicholas Carlini. arXiv:2106.15023.