Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming

• URL: http://arxiv.org/abs/1811.01198v9
• Date: Mon, 22 Sep 2025 12:31:19 GMT
• Title: Asymmetric Burer-Monteiro Factorization with Theoretically Sound Penalty for Semidefinite Programming
• Authors: En-Liang Hu,
• Abstract summary: A symmetric Burer-iro factorization (BMF) is used to solve large-scale semidefinite programs (SDPs)<n>We show that the resultant asymmetric BMF is multi- convex$ optimization.
• Score: 0.7614628596146601
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the solving of large-scale semidefinite programs (SDPs), the symmetric Burer-Monteiro factorization (BMF) offers an economical low-rank solution of the form $XX^\top$. However, BMF turns a convex SDP into a more difficult nonconvex optimization problem in some cases, which limits the use of off-the-shelf convex optimization algorithms. To alleviate this problem, we convert symmetric BMF to its asymmetric counterpart involving $XY^\top$, and use a penalty with parameter $\gamma$ to encourage $X$ and $Y$ to be close. We show that the resultant asymmetric BMF is multi-convex, and thus convex optimization can again be used to solve the subproblems involving $X$ and $Y$ in an alternating manner. More importantly, to ensure that $X=Y$ on convergence, we derive theoretically sound conditions for exact $\gamma$ that are independent of both the application problem and underlying algorithm. Experiments demonstrate that the proposed method is more advantageous over existing related approaches.

Related papers

• Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
  We study robust Markov decision processes (RMDPs) with general policy parameterization under s-rectangular and non-rectangular uncertainty sets.<n>We prove novel Lipschitz and Lipschitz-smoothness properties for general policy parameterizations that extends to infinite state spaces.<n>We design a projected gradient descent algorithm for s-rectangular uncertainty and a Frank-Wolfe algorithm for non-rectangular uncertainty.
  arXiv  Detail & Related papers  (2026-02-11T21:44:20Z)
• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  Existing approaches for the Extended Adversarial (SEA) model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$.<n>We develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters.
  arXiv  Detail & Related papers  (2025-10-06T10:53:37Z)
• Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms [26.645423762494985]
  We consider the problem of minimizing a difference of (smooth) convex functions over a compact convex feasible region $P$.<n>We empirically show that constrained DC problems can be efficiently solved using a combination of the Blended Pairwise Gradients (BPCG) algorithm.
  arXiv  Detail & Related papers  (2025-07-23T14:22:42Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions [41.43895948769255]
  We show a class of non-smooth non-asymptotic fairness problems in the form of $min_x[yin Yphi(x, y) - max_zin Zpsix(x, z)]$. We propose an envelope approximate gradient SMAG, the first method for solving these problems, provide a state-of-the-art non-asymptotic convergence rate.
  arXiv  Detail & Related papers  (2024-05-28T20:52:46Z)
• 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)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• Black-Box Min--Max Continuous Optimization Using CMA-ES with Worst-case Ranking Approximation [22.576922942465142]
  A popular approach updates $x$ and $y$ simultaneously or alternatingly. Existing approaches fail if $f$ is not Lipschitz smooth and strongly convex-concave around the optimal solution. We propose minimizing the worst-case objective function $F(x)=max_yf(x,y)$ directly using the covariance matrix adaptation evolution strategy.
  arXiv  Detail & Related papers  (2022-04-06T08:03:39Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Block majorization-minimization with diminishing radius for constrained nonsmooth nonconvex optimization [8.386501595252]
  Block majorization-minimativeization (BMM) is a simple iterative algorithm for constrained nonnegative surrogates.<n>We show that BMM produces a novel first-order optimality measure for various algorithms.<n>We also demonstrate that the additional use of diminishing radius can improve the convergence rate of BMM in many instances.
  arXiv  Detail & Related papers  (2020-12-07T07:53:09Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  We prove that the least squares estimator is computable via solving a constrained convex programming (QP) problem with $(n+1)d$ variables and at least $n(n-1)$ linear inequality constraints. For solving the generally very large-scale convex QP, we design two efficient algorithms, one is the symmetric Gauss-Seidel based alternating direction method of multipliers (tt sGS-ADMM), and the other is the proximal augmented Lagrangian method (tt pALM) with the subproblems solved by the semismooth Newton method (t
  arXiv  Detail & Related papers  (2020-02-26T11:18:43Z)

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.