Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+

• URL: http://arxiv.org/abs/2406.10407v2
• Date: Wed, 7 Aug 2024 20:10:14 GMT
• Title: Suboptimality bounds for trace-bounded SDPs enable a faster and scalable low-rank SDP solver SDPLR+
• Authors: Yufan Huang, David F. Gleich,
• Abstract summary: Semidefinite programs (SDPs) are powerful tools with many applications in machine learning and data science. SDP solvers are challenging because by standard the positive semidefinite decision variable is an $n times n$ dense matrix. Two decades ago, Burer and Monteiro developed an SDP solver that optimized over a low-rank factorization instead of the full matrix.
• Score: 3.7507283158673212
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semidefinite programs (SDPs) and their solvers are powerful tools with many applications in machine learning and data science. Designing scalable SDP solvers is challenging because by standard the positive semidefinite decision variable is an $n \times n$ dense matrix, even though the input is often $n \times n$ sparse matrices. However, the information in the solution may not correspond to a full-rank dense matrix as shown by Barvinok and Pataki. Two decades ago, Burer and Monteiro developed an SDP solver $\texttt{SDPLR}$ that optimizes over a low-rank factorization instead of the full matrix. This greatly decreases the storage cost and works well for many problems. The original solver $\texttt{SDPLR}$ tracks only the primal infeasibility of the solution, limiting the technique's flexibility to produce moderate accuracy solutions. We use a suboptimality bound for trace-bounded SDP problems that enables us to track the progress better and perform early termination. We then develop $\texttt{SDPLR+}$, which starts the optimization with an extremely low-rank factorization and dynamically updates the rank based on the primal infeasibility and suboptimality. This further speeds up the computation and saves the storage cost. Numerical experiments on Max Cut, Minimum Bisection, Cut Norm, and Lov\'{a}sz Theta problems with many recent memory-efficient scalable SDP solvers demonstrate its scalability up to problems with million-by-million decision variables and it is often the fastest solver to a moderate accuracy of $10^{-2}$.

Related papers

• A practical, fast method for solving sum-of-squares problems for very large polynomials [10.645318208507213]
  Sum of squares (SOS) optimization is a powerful technique for solving problems where the positivity of as must be enforced. Our goal is to devise an approach that can handle larger, more complex problems than is currently possible.
  arXiv  Detail & Related papers  (2024-10-21T12:47:42Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs. USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
  arXiv  Detail & Related papers  (2023-12-19T02:27:22Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Lossy compression of matrices by black-box optimisation of mixed-integer non-linear programming [1.1066593559733056]
  In edge computing, suppressing data size is a challenge for machine learning models that perform complex tasks such as autonomous driving. Efficient lossy compression of matrix data has been introduced by decomposing it into the product of an integer and real matrices. In this paper, we improve this optimisation by utilising recently developed black-box optimisation algorithms with an Ising solver for integer variables.
  arXiv  Detail & Related papers  (2022-04-22T08:58:36Z)
• FKreg: A MATLAB toolbox for fast Multivariate Kernel Regression [5.090316990822874]
  We introduce a new toolbox for fast multivariate kernel regression with the idea of non-uniform FFT (NUFFT) NUFFT implements the algorithm for $M$ gridding points with $Oleft( N+Mlog M right)$ complexity and accuracy controllability. The bandwidth selection problem utilizes the Fast Monte-Carlo to estimate the degree of freedom.
  arXiv  Detail & Related papers  (2022-04-16T04:52:44Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• 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)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)

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.