Average-case Acceleration for Bilinear Games and Normal Matrices
- URL: http://arxiv.org/abs/2010.02076v1
- Date: Mon, 5 Oct 2020 15:13:37 GMT
- Title: Average-case Acceleration for Bilinear Games and Normal Matrices
- Authors: Carles Domingo-Enrich, Fabian Pedregosa, Damien Scieur
- Abstract summary: We show that for zero-sum bilinear games the average-case optimal method is the optimal method for the minimization of the Hamiltonian.
We specialize it to matrices with eigenvalues located in a disk and show a provable speed-up compared to worst-case optimal algorithms.
- Score: 35.14328074551363
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Advances in generative modeling and adversarial learning have given rise to
renewed interest in smooth games. However, the absence of symmetry in the
matrix of second derivatives poses challenges that are not present in the
classical minimization framework. While a rich theory of average-case analysis
has been developed for minimization problems, little is known in the context of
smooth games. In this work we take a first step towards closing this gap by
developing average-case optimal first-order methods for a subset of smooth
games. We make the following three main contributions. First, we show that for
zero-sum bilinear games the average-case optimal method is the optimal method
for the minimization of the Hamiltonian. Second, we provide an explicit
expression for the optimal method corresponding to normal matrices, potentially
non-symmetric. Finally, we specialize it to matrices with eigenvalues located
in a disk and show a provable speed-up compared to worst-case optimal
algorithms. We illustrate our findings through benchmarks with a varying degree
of mismatch with our assumptions.
Related papers
- $\ell_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points [20.82938951566065]
We show that any second-order stationary point (and thus local minimizer) of the problem is actually globally optimal.
Our techniques can potentially be applied to analyze the optimization landscapes of a variety of other more sophisticated nonsmooth learning problems.
arXiv Detail & Related papers (2024-10-07T13:25:37Z) - Learning the Positions in CountSketch [49.57951567374372]
We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem.
In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
arXiv Detail & Related papers (2023-06-11T07:28:35Z) - A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion [15.128477070895055]
We propose a novel method for 1-bit matrix completion called Majorization-Minimization Gauss-Newton (MMGN)
Our method is based on the majorization-minimization principle, which converts the original optimization problem into a sequence of standard low-rank matrix completion problems.
arXiv Detail & Related papers (2023-04-27T03:16:52Z) - Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization
Problems [19.930021245647705]
Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning.
In this paper we consider standard convex relaxations for such problems.
We prove that under a textitstrict complementarity condition and under the relatively mild assumption that the nonsmooth objective can be written as a maximum of smooth functions, approximated variants of two popular textitmirror-prox methods.
arXiv Detail & Related papers (2022-06-23T08:10:54Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function.
We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
arXiv Detail & Related papers (2021-09-30T19:17:35Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm.
We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound.
We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
arXiv Detail & Related papers (2021-01-19T04:24:23Z) - On the Efficient Implementation of the Matrix Exponentiated Gradient
Algorithm for Low-Rank Matrix Optimization [26.858608065417663]
Convex optimization over the spectrahedron has important applications in machine learning, signal processing and statistics.
We propose efficient implementations of MEG, which are tailored for optimization with low-rank matrices, and only use a single low-rank SVD on each iteration.
We also provide efficiently-computable certificates for the correct convergence of our methods.
arXiv Detail & Related papers (2020-12-18T19:14:51Z) - Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank
Constraints [3.179831861897336]
We provide a framework for solving low-rank optimization problems to certifiable optimality.
Our framework also provides near-optimal solutions through rounding and local search techniques.
arXiv Detail & Related papers (2020-09-22T08:59:06Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching.
We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
arXiv Detail & Related papers (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems.
We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms.
Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
arXiv Detail & Related papers (2020-02-21T17:45:32Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
We study the performance of iterative sketching for least-squares problems.
We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections.
These techniques may be applied to other algorithms that employ randomized dimension reduction.
arXiv Detail & Related papers (2020-02-03T16:17:50Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.