Multiplicative Updates for Online Convex Optimization over Symmetric
Cones
- URL: http://arxiv.org/abs/2307.03136v1
- Date: Thu, 6 Jul 2023 17:06:43 GMT
- Title: Multiplicative Updates for Online Convex Optimization over Symmetric
Cones
- Authors: Ilayda Canyakmaz, Wayne Lin, Georgios Piliouras, Antonios Varvitsiotis
- Abstract summary: We introduce the Symmetric-Cone Multiplicative Weights Update (SCMWU), a projection-free algorithm for online optimization over the trace-one slice of an arbitrary symmetric cone.
We show that SCMWU is equivalent to Follow-the-Regularized-Leader and Online Mirror Descent with symmetric-cone negative entropy as regularizer.
- Score: 28.815822236291392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online convex optimization where the possible actions are trace-one
elements in a symmetric cone, generalizing the extensively-studied experts
setup and its quantum counterpart. Symmetric cones provide a unifying framework
for some of the most important optimization models, including linear,
second-order cone, and semidefinite optimization. Using tools from the field of
Euclidean Jordan Algebras, we introduce the Symmetric-Cone Multiplicative
Weights Update (SCMWU), a projection-free algorithm for online optimization
over the trace-one slice of an arbitrary symmetric cone. We show that SCMWU is
equivalent to Follow-the-Regularized-Leader and Online Mirror Descent with
symmetric-cone negative entropy as regularizer. Using this structural result we
show that SCMWU is a no-regret algorithm, and verify our theoretical results
with extensive experiments. Our results unify and generalize the analysis for
the Multiplicative Weights Update method over the probability simplex and the
Matrix Multiplicative Weights Update method over the set of density matrices.
Related papers
- Online Variational Sequential Monte Carlo [49.97673761305336]
We build upon the variational sequential Monte Carlo (VSMC) method, which provides computationally efficient and accurate model parameter estimation and Bayesian latent-state inference.
Online VSMC is capable of performing efficiently, entirely on-the-fly, both parameter estimation and particle proposal adaptation.
arXiv Detail & Related papers (2023-12-19T21:45:38Z) - Convex Parameter Estimation of Perturbed Multivariate Generalized
Gaussian Distributions [18.95928707619676]
We propose a convex formulation with well-established properties for MGGD parameters.
The proposed framework is flexible as it combines a variety of regularizations for the precision matrix, the mean and perturbations.
Experiments show a more accurate precision and covariance matrix estimation with similar performance for the mean vector parameter.
arXiv Detail & Related papers (2023-12-12T18:08:04Z) - Manifold Gaussian Variational Bayes on the Precision Matrix [70.44024861252554]
We propose an optimization algorithm for Variational Inference (VI) in complex models.
We develop an efficient algorithm for Gaussian Variational Inference whose updates satisfy the positive definite constraint on the variational covariance matrix.
Due to its black-box nature, MGVBP stands as a ready-to-use solution for VI in complex models.
arXiv Detail & Related papers (2022-10-26T10:12:31Z) - Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints.
The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution.
We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
arXiv Detail & Related papers (2022-10-21T13:19:45Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression.
Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates.
The proposed approach is implemented in the R package probe.
arXiv Detail & Related papers (2022-09-16T19:15:50Z) - Characterization of variational quantum algorithms using free fermions [0.0]
We numerically study the interplay between these symmetries and the locality of the target state.
We find that the number of iterations to converge to the solution scales linearly with system size.
arXiv Detail & Related papers (2022-06-13T18:11:16Z) - On Riemannian Optimization over Positive Definite Matrices with the
Bures-Wasserstein Geometry [45.1944007785671]
We comparatively analyze the Bures-Wasserstein (BW) geometry with the popular Affine-Invariant (AI) geometry.
We build on an observation that the BW metric has a linear dependence on SPD matrices in contrast to the quadratic dependence of the AI metric.
We show that the BW geometry has a non-negative curvature, which further improves convergence rates of algorithms over the non-positively curved AI geometry.
arXiv Detail & Related papers (2021-06-01T07:39:19Z) - 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) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
We design regularization-free algorithms for the high-dimensional single index model.
We provide theoretical guarantees for the induced implicit regularization phenomenon.
arXiv Detail & Related papers (2020-07-16T13:27:47Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based.
The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM)
We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
arXiv Detail & Related papers (2020-06-23T01:34:18Z) - Nonconvex Matrix Completion with Linearly Parameterized Factors [10.163102766021373]
Parametric Factorization holds for important examples including subspace and completion simulations.
The effectiveness of our unified nonconstrained matrix optimization method is also illustrated.
arXiv Detail & Related papers (2020-03-29T22:40:47Z)
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.