Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization

• URL: http://arxiv.org/abs/2501.02942v2
• Date: Fri, 17 Oct 2025 20:54:29 GMT
• Title: Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization
• Authors: Ryan Cory-Wright, Jean Pauphilet,
• Abstract summary: We construct an analogous relax-then-round strategy for low-rank optimization problems.<n>For a given $n times m$ semi-orthogonal matrix, we derive a purely multiplicative approximation ratio for our algorithm.<n>We extend our approach to generic low-rank optimization problems by developing new semidefinite relaxations.
• Score: 2.0052993723676895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-round strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme that obtains provably near-optimal solutions, building on the blueprint from Goemans and Williamson for the Max-Cut problem. For a given $n \times m$ semi-orthogonal matrix, we derive a purely multiplicative approximation ratio for our algorithm, and show that it is never worse than $\max(2/(\pi m), 1/(\pi(\log (2m)+1)))$. We also show how to compute a tighter constant for a finite $(n,m)$ by solving a univariate optimization problem. We then extend our approach to generic low-rank optimization problems by developing new semidefinite relaxations that are both tighter and more broadly applicable than those in prior works. Although our original proposal introduces large semidefinite matrices as decision variables, we show that most of the blocks in these matrices can be safely omitted without altering the optimal value, hence improving the scalability of our approach. Using several examples (including matrix completion, basis pursuit, and reduced-rank regression), we show how to reduce the size of our relaxation even further. Finally, we numerically illustrate the effectiveness and scalability of our relaxation and sampling scheme on orthogonally constrained quadratic optimization and matrix completion problems.

Related papers

• Zeroth-Order Methods for Stochastic Nonconvex Nonsmooth Composite Optimization [51.63258496873442]
  Previous works on composite optimization problem requires the major part to smoothness or some machine learning examples which excludes such two approximate smoothness points respectively.<n>In this work we propose two new algorithms for such problem.<n>We show that these algorithms are effective using numerical experiments.
  arXiv  Detail & Related papers  (2025-10-06T02:35:42Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  We propose a smooth variant of the min-max problem based on the augmented Lagrangian. The proposed algorithm scales better with the number of objectives than subgradient-based strategies.
  arXiv  Detail & Related papers  (2025-03-16T11:05:51Z)
• Global Optimization: A Machine Learning Approach [7.052596485478637]
  Bertsimas and Ozturk (2023) proposed OCTHaGOn as a way of solving black-box global optimization problems. We provide extensions to this approach by approximating the original problem using other MIO-representable ML models. We show improvements in solution feasibility and optimality in the majority of instances.
  arXiv  Detail & Related papers  (2023-11-03T06:33:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Slowly Varying Regression under Sparsity [5.22980614912553]
  We present the framework of slowly hyper regression under sparsity, allowing regression models to exhibit slow and sparse variations. We suggest a procedure that reformulates as a binary convex algorithm. We show that the resulting model outperforms competing formulations in comparable times across various datasets.
  arXiv  Detail & Related papers  (2021-02-22T04:51:44Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• 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)
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning [3.511851311025242]
  We propose a primal-dual algorithm to optimize the primal and dual variables iteratively. We prove convergence of the proposed algorithm and show its non-asymptotic convergence rate. Preliminary experimental results on an optimal fund selection problem in fund of funds management showed its efficacy.
  arXiv  Detail & Related papers  (2020-05-19T03:31:01Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)

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.