On the simplicity and conditioning of low rank semidefinite programs
- URL: http://arxiv.org/abs/2002.10673v2
- Date: Fri, 23 Jul 2021 03:56:03 GMT
- Title: On the simplicity and conditioning of low rank semidefinite programs
- Authors: Lijun Ding, Madeleine Udell
- Abstract summary: It is often known that the exact solution to a SDP with perfect data recovers the solution to the original low rank matrix recovery problem.
It is more challenging to show that an approximate solution to the SDP formulated with noisy problem data acceptably solves the original problem.
In this note, we identify a set of conditions that we call simplicity that limit the error due to noisy problem data or incomplete convergence.
- Score: 28.71984085513293
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Low rank matrix recovery problems appear widely in statistics, combinatorics,
and imaging. One celebrated method for solving these problems is to formulate
and solve a semidefinite program (SDP). It is often known that the exact
solution to the SDP with perfect data recovers the solution to the original low
rank matrix recovery problem. It is more challenging to show that an
approximate solution to the SDP formulated with noisy problem data acceptably
solves the original problem; arguments are usually ad hoc for each problem
setting, and can be complex.
In this note, we identify a set of conditions that we call simplicity that
limit the error due to noisy problem data or incomplete convergence. In this
sense, simple SDPs are robust: simple SDPs can be (approximately) solved
efficiently at scale; and the resulting approximate solutions, even with noisy
data, can be trusted. Moreover, we show that simplicity holds generically, and
also for many structured low rank matrix recovery problems, including the
stochastic block model, $\mathbb{Z}_2$ synchronization, and matrix completion.
Formally, we call an SDP simple if it has a surjective constraint map, admits a
unique primal and dual solution pair, and satisfies strong duality and strict
complementarity.
However, simplicity is not a panacea: we show the Burer-Monteiro formulation
of the SDP may have spurious second-order critical points, even for a simple
SDP with a rank 1 solution.
Related papers
- Reweighted Solutions for Weighted Low Rank Approximation [47.790126028106734]
Weighted low rank approximation (WLRA) is an important yet challenging primitive with applications ranging from statistical analysis to signal processing.
In this work, we introduce a new relaxed solution to WLRA which outputs a matrix that is not necessarily low rank, but can be stored using very few parameters.
Our central idea is to use the weight matrix itself to reweight a low rank solution, which gives an extremely simple algorithm with remarkable empirical performance.
arXiv Detail & Related papers (2024-06-04T15:50:35Z) - Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
We study the embedded feature selection problem in linear Support Vector Machines (SVMs)
A cardinality constraint is employed, leading to a fully explainable selection model.
The problem is NP-hard due to the presence of the cardinality constraint.
arXiv Detail & Related papers (2024-04-15T19:15:32Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
We provide minimax upper and lower bounds on the sample complexity for learning near-optimal policies in a discounted CMDP.
We show that learning CMDPs is as easy as MDPs when small constraint violations are allowed, but inherently more difficult when we demand zero constraint violation.
arXiv Detail & Related papers (2022-06-13T15:58:14Z) - Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
One of the main queries on such models is to identify the SDPWCSP Function on Cost of a Posteri (MAP) Networks.
We consider a traditional dualized constraint approach and a dedicated dedicated SDP/Monteiro style method based on row-by-row updates.
arXiv Detail & Related papers (2021-11-24T13:38:34Z) - 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) - A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs)
We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all.
We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
arXiv Detail & Related papers (2021-06-24T13:46:09Z) - STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One
Semidefinite Relaxations [27.353023427198806]
We consider solving high-order semidefinite programming relaxations of nonconstrained optimization problems (POPs)
Existing approaches, which solve the SDP independently from the POP, either cannot scale to large problems or suffer from slow convergence due to the typical uneneracy of such SDPs.
We propose a new algorithmic framework called SpecTrahedral vErtices (STRIDE)
arXiv Detail & Related papers (2021-05-28T18:07:16Z) - Probabilistic Simplex Component Analysis [66.30587591100566]
PRISM is a probabilistic simplex component analysis approach to identifying the vertices of a data-circumscribing simplex from data.
The problem has a rich variety of applications, the most notable being hyperspectral unmixing in remote sensing and non-negative matrix factorization in machine learning.
arXiv Detail & Related papers (2021-03-18T05:39:00Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems.
The most important feature of our framework is that only a subset of the constraints is processed at each iteration.
Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z)
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.