Solving smooth min-min and min-max problems by mixed oracle algorithms

Abstract

In this paper, we consider two types of problems that have some similarity in their structure, namely, min-min problems and min-max saddle-point problems. Our approach is based on considering the outer minimization problem as a minimization problem with inexact oracle. This inexact oracle is calculated via inexact solution of the inner problem, which is either minimization or a maximization problem. Our main assumptions are that the problem is smooth and the available oracle is mixed: it is only possible to evaluate the gradient w.r.t. the outer block of variables which corresponds to the outer minimization problem, whereas for the inner problem only zeroth-order oracle is available. To solve the inner problem we use accelerated gradient-free method with zeroth-order oracle. To solve the outer problem we use either inexact variant of Vaydya's cutting-plane method or a variant of accelerated gradient method. As a result, we propose a framework that leads to non-asymptotic complexity bounds for both min-min and min-max problems. Moreover, we estimate separately the number of first- and zeroth-order oracle calls which are sufficient to reach any desired accuracy.

References in corpus (14)

• Explaining and Harnessing Adversarial Examples
• Generative Adversarial Networks
• Ensemble Adversarial Training: Attacks and Defenses
• Robust Adversarial Reinforcement Learning
• A Universal Catalyst for First-Order Optimization
• An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Gradient-Free Methods for Saddle-Point Problem
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Accelerated methods for composite non-bilinear saddle point problem
• About accelerated randomized methods
• Universal method with inexact oracle and its applications for searching equillibriums in multistage transport problems
• Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model

Cited by in corpus (3)

• Randomized gradient-free methods in convex optimization
• Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey
• Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables