Dimensionality Reduction of Affine Variational Inequalities Using Random Projections
We present a method for dimensionality reduction of an affine variational inequality (AVI) defined over a compact feasible region. Centered around the Johnson Lindenstrauss lemma, our method is a randomized algorithm that produces with high probability an approximate solution for the given AVI by solving a lower-dimensional AVI. The algorithm allows the lower dimension to be chosen based on the quality of approximation desired. The algorithm can also be used as a subroutine in an exact algorithm for generating an initial point close to the solution. The lower-dimensional AVI is obtained by appropriately projecting the original AVI on a randomly chosen subspace. The lower-dimensional AVI is solved using standard solvers and from this solution an approximate solution to the original AVI is recovered through an inexpensive process. Our numerical experiments corroborate the theoretical results and validate that the algorithm provides a good approximation at low dimensions and substantial savings in time for an exact solution.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality ReductionLEMMASimilar Papers 제목 키워드 기반
A Douglas-Rachford Splitting Method for Solving Monotone Variational Inequalities in Linear-quadratic Dynamic Games
This paper considers constrained linear dynamic games with quadratic objective functions, which can be cast as affine variational inequalities. By leveraging the problem structure, we apply the Douglas-Rachford splitting…
Forward-backward-forward methods with variance reduction for stochastic variational inequalities
We develop a new stochastic algorithm with variance reduction for solving pseudo-monotone stochastic variational inequalities. Our method builds on Tseng's forward-backward-forward (FBF) algorithm, which is known in the …
Min-Max Optimization Is Strictly Easier Than Variational Inequalities
Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality conditions. Is it possible to solve min-max p…
SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities
Variational inequalities are a broad formalism that encompasses a vast number of applications. Motivated by applications in machine learning and beyond, stochastic methods are of great importance. In this paper we consid…
Stochastic Variance Reduction for Variational Inequality Methods
We propose stochastic variance reduced algorithms for solving convex-concave saddle point problems, monotone variational inequalities, and monotone inclusions. Our framework applies to extragradient, forward-backward-for…