Hello everyone,
I am a PhD student with a deep learning background. I am trying to find more robust deep learning models and I just came through defining the problem as a minimax problem as the attacker tries to maximize the loss function and the defender tries to minimize the risk of he attacker. I have just learned that this problem can be solved in three ways : 1- Lower bounds 2- Exact solutions 3- Upper bounds.
The problem is that I do not know how to get deeper in optimization in order to get a unique solution to the problem.
Can you recommend some resources or road-map for optimization, convex optimization, non-convex optimization, and robust optimization?
Dear Bader Rasheed,
I suggest you to see links and attached files on topic.
https://towardsdatascience.com/neural-network-optimization-7ca72d4db3e0
https://math.stackexchange.com/questions/1077700/solving-min-max-optimization-problems-in-original-ways-that-is-avoiding-the-fr
Conference Paper A novel method for solving min-max problems by using a modif...
Article Minmax regret solutions for minimax optimization problems wi...
Article Reference variable methods of solving min-max optimization problems
Best regards
Mohamed-Mourad Lafifi Thank you so much for your answer. The main problem is that I am not an optimization guy and I am struggling to read papers that show how to solve this problem directly. That is why I want to start by reading some optimization books that could make reading these papers easier.
Konstantin Kudryavzev Thank you so much for your suggestion, I will read it.
This is the direct procedure of fuzzy programming method. For solving minmax optimization problem, first you find an ideal solution using a simple mathematical programming techniques for example, solve using simplex method. Then formulate a pay-off matrix. After that determine the best upper bound and worst lower bound. From those values formulate a membership function corresponding to the given objective function. This membership function lies between 0 and 1 inclusive. The membership function evaluated is not greater than some augmented variable lambda. So, minimize this augmented lambda subject to the some constraints. However, the number of constraints now increases. For more information read about Fuzzy programming technique.
Adane Abebaw Thank you for your answer. Any recommendations for good materials?
Bi-level Mini-max problems can be solved with Benders (1962) decomposition. The inner maximization problem becomes the "subproblem" and the outer minimization becomes the "master" problem.
If the inner problem has all continuous variables, then you can try to formulate the dual of the inner maximization and get the inner minimzaiton of the dual variables. If the inner subproblem dual is possible, this would reduce your mini-max problem to a single level minimization problem.
Gary Lazzaro Thank you for your answer. Do I understand correctly that it's the same concept used in Stackelberg games? Is it possible to formulate the problem as a game and solve it?
Bader Rasheed : Bi-level mini-max problems could be thought of as a Stackelberg game. The Stackelberg game has a lead actor and a follower. In a game theoretic view, the first actor is the outer "master" problem (the min) , and the second actor forms the inner "subproblem" (the max).
In order to solve with a Benders-like approach, you begin by choosing a fixed action for the first actor (min) and then solve the subproblem (max). The subproblem solution then becomes fixed inputs to solve the master problem. You would iterate back and forth between subproblem and master problem to update the lower or upper bounds appropriately. Hopefully your problem instance will have bounds that converge.
Gary Lazzaro Thank you for the clarification. I will try this approach and tell you about the results. The problem is that the problem instance will not have bounds that coverage as the attacker will always come with new strategies or attacks (solutions for the inner min) and the defender will respond with new defenses ( solutions for the outer max)
A good place to start would be to make sure that you understand how to use linear programming to tackle two-player zero-sum games. See here:
https://econweb.ucsd.edu/~jsobel/172aw02/notes9.pdf
https://www.youtube.com/watch?v=feb9j65Iz4w
Adam N. Letchford Thank you for your answer. I added a picture clarifying the problem I am trying to solve. The problem is continuous and it is not possible to find finite strategies.
- Badges
- Science topic