Solving variational inequalities with monotone operators on domains given by Linear Minimization Oracles

By Anatoli B. Juditsky, Arkadi Nemirovski. 2013

37 citations recorded by the source corpus.

The standard algorithms for solving large-scale convex–concave saddle point problems, or, more generally, variational inequalities with monotone operators, are proximal type algorithms which at every iteration need to compute a prox-mapping, that is, to minimize over problem’s domain X the sum of a linear form and the specific convex distance-generating function underlying the algorithms in question. (Relative) computational simplicity of prox-mappings, which is the standard requirement when implementing proximal algorithms, clearly implies the possibility to equip X with a relatively computationally cheap Linear Minimization Oracle (LMO) able to minimize over X linear forms. There are, however, important situations where a cheap LMO indeed is available, but where no proximal setup with easy-to-compute prox-mappings is known. This fact motivates our goal in this paper, which is to develop techniques for solving variational inequalities with monotone operators on domains given by LMO. The techniques we discuss can be viewed as a substantial extension of the proposed in Cox et al. (Math Program Ser B 148(1–2):143–180, 2014) method of nonsmooth convex minimization over an LMO-represented domain.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, methodology): “More recently, Juditsky and Nemirovski (2016) (see also Cox et al. (2015)) proposed a method to transform a VIP on Z where one has only access to a LMO, to a “dual” VIP on which they can use a projection-type method.”
Semi-Proximal Mirror-Prox for Nonsmooth Composite Minimization (2015, background): “The function f usually corresponds to an empirical risk, that is an empirical average of a possibly non-smooth loss function evaluated on a set of data-points, while x encodes the learning parameters.”
Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods (2019, methodology): “This setting has been extensively studied and different algorithms have been developed for finding a Nash equilibrium [46, 21, 44, 29, 40, 23, 26, 43, 18, 45].”
A Universal Primal-Dual Convex Optimization Framework (2015, methodology): “The sharp-operator in (2) is often much cheaper to process as compared to the prox operator [1, 12].”
Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators (2015, methodology): “This paper is a follow-up to our paper [1] and, same as its predecessor, is motivated by the desire to develop first-order algorithms for solving convex–concave saddle point problem (or variational inequality with monotone operator) on a convex domain X represented by linear minimization oracle (LMO”