We present a hybrid algorithm for optimizing a convex, smooth function over the cone of positive semidefinite matrices. Our algorithm converges to the global optimal solution and can be used to solve general large-scale semidefinite programs and hence can be readily applied to a variety of machine learning problems. We…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “Semidefinite optimization”
New method trains quantized neural networks to global optimality.
problem Training optimal quantized neural networks is intractable due to combinatorial non-convex optimization.
method Convex optimization strategy using hidden convexity, semidefinite lifting, and Grothendieck's identity.
result Quantized NN problems can be solved to global optimality in polynomial-time.
New method speeds up k-means clustering using sketch-and-solve.
problem Efficiently solving k-means clustering for large datasets.
method Sketch-and-solve approach with Peng-Wei semidefinite relaxation.
result Provides high-confidence lower bounds on k-means optimal value.
We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With random measurements of a positive semidefinite matrix of rank and condition number …
In this paper, we propose a low-rank coordinate descent approach to structured semidefinite programming with diagonal constraints. The approach, which we call the Mixing method, is extremely simple to implement, has no free parameters, and typically attains an order of magnitude or better improvement in optimization pe…
Method provides bounds for sparse PCA and nuclear norm problems.
problem Semidefinite optimization problems (SDOs).
method Cutting-plane method with focus on initial outer approximation as a second-order cone approximation.
result Method provides bound gaps of 0.5-6.5% for sparse PCA problems with 1000 covariates and solves nuclear norm problems over 500x500 matrices.
Paper develops exact convex optimization for neural networks with polynomial activations.
problem Training two-layer neural networks with nonlinear polynomial activations.
method Exact convex optimization using semidefinite programming.
result Global optimization of neural networks is polynomial-time computable.
A new algorithm solves semidefinite programs using Langevin diffusion.
problem Optimizing semidefinite programs with diagonal constraints.
method Langevin diffusion on a product manifold of spheres.
result Langevin algorithm achieves ε accuracy in Ω(ε^-5) iterations.
AMP algorithms can be efficiently simulated by SDPs even with corrupted data.
problem Optimizing average-case optimization problems with corrupted data.
method Local statistics hierarchy semidefinite programs (SDPs) simulate AMP algorithms robustly.
result Robust guarantees for many AMP algorithms are offered, contrasting with strong lower bounds for SDPs.
In recent years, optimization theory has been greatly impacted by the advent of sum of squares (SOS) optimization. The reliance of this technique on large-scale semidefinite programs however, has limited the scale of problems to which it can be applied. In this paper, we introduce DSOS and SDSOS optimization as linear …
Bundle method solves low rank SDP problems without full matrix construction.
problem Solving semidefinite programming problems with low rank solutions.
method Applying bundle method to randomly sketch matrix optimization problems and using recent results on bundle methods.
result Algorithm produces solutions with low rank representation and convergence rates.
New approach for fair graph clustering using semidefinite relaxation.
problem Ensuring equitable representation in network analysis.
method Semidefinite relaxation approach for NP-hard optimization problem.
result Optimal accuracy-fairness trade-off achieved.
The binary symmetric stochastic block model deals with a random graph of vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability within clusters and across clusters. In the asymptotic regime of and for fixe…
Regularization vs. Relaxation: A conic optimization perspective of statistical variable selectioncs.LG
Variable selection is a fundamental task in statistical data analysis. Sparsity-inducing regularization methods are a popular class of methods that simultaneously perform variable selection and model estimation. The central problem is a quadratic optimization problem with an l0-norm penalty. Exactly enforcing the l0-no…
Paper tackles multi-label learning by improving SVR for positive semidefinite metrics.
problem Learning positive semidefinite metrics for multi-label and label distribution learning.
method Proposes two methods to overcome SVR's limitation in learning positive semidefinite metrics.
result Demonstrates new methods achieve favorable performance in multi-label and label distribution learning.
A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily availa…
New methods improve solving linear systems and preconditioning with reduced complexity.
problem Efficiently solving linear systems and preconditioning matrices.
method Developed structured semidefinite programming algorithms.
result Improved runtimes for preconditioning and solving linear systems.
The problem of detecting communities in a graph is maybe one the most studied inference problems, given its simplicity and widespread diffusion among several disciplines. A very common benchmark for this problem is the stochastic block model or planted partition problem, where a phase transition takes place in the dete…
New algorithm improves clustering accuracy without sacrificing scalability.
problem Improving clustering accuracy for large datasets.
method Nonnegative low-rank semidefinite programming with Burer-Monteiro factorization.
result Significantly smaller mis-clustering errors compared to existing methods.
Optimized projection-free algorithms for online learning: construction and worst-case analysismath.OC
Optimized algorithms for online learning with linear constraints improve performance and provide worst-case analysis.
problem Improving online learning algorithms for constrained optimization problems.
method Developed an optimized variant of an online Frank-Wolfe algorithm and used semidefinite programming for numerical analysis.
result No pure online Frank-Wolfe algorithm can have a better regret guarantee than O(T^3/4) without additional assumptions.
Paper develops zeroth and first order stochastic Frank-Wolfe algorithms for constrained optimization.
problem Optimization problems with difficult-to-project deterministic constraints and efficient projection constraints.
method Stochastic Frank-Wolfe algorithms with momentum and trimmed variants.
result Guaranteed fast convergence rates comparable to unconstrained problems.
New method for sparse kernel selection improves prediction accuracy.
problem Sparse Multiple Kernel Learning for binary classification.
method Alternating best response algorithm with semidefinite relaxations.
result Method outperforms state-of-the-art MKL approaches in prediction accuracy.
New algorithms optimize without knowing problem parameters.
problem Optimizing large-scale problems without knowing key parameters.
method Combining mirror descent with dual averaging techniques.
result Converges without prior knowledge of problem parameters.
We consider semidefinite programs (SDPs) of size n with equality constraints. In order to overcome scalability issues, Burer and Monteiro proposed a factorized approach based on optimizing over a matrix Y of size by such that is the SDP variable. The advantages of such formulation are twofold: the di…
Regularization techniques are widely employed in optimization-based approaches for solving ill-posed inverse problems in data analysis and scientific computing. These methods are based on augmenting the objective with a penalty function, which is specified based on prior domain-specific expertise to induce a desired st…
We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With random observations of a $n_1 \times n…
New method closes certification gap for adversarially trained models.
problem Certifying robustness of adversarially trained neural networks.
method Nonconvex low-rank SDP relaxation with polynomial-time optimization.
result Strong certifications comparable to SDP methods, but with fewer variables.
Optimal noise excitation for linear system identification reduces sample complexity.
problem Efficiently identifying linear systems with minimal data.
method Active learning algorithm using ordinary least squares and semidefinite programming.
result The proposed algorithm matches lower bounds on sample complexity for any active learning method.
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer--Monteiro factorization approach for solving SDPs. We show that all approximate local optima are global optima for the pe…
The paper trains neural networks with robustness guarantees using semidefinite constraints.
problem Training neural networks with robustness and stability guarantees.
method Exploiting the banded structure of semidefinite constraints, an efficient and scalable training scheme based on interior point methods is set up.
result The method allows for enforcing Lipschitz constraints in large-scale deep neural networks, as demonstrated in numerical examples.
Efficiently solves MRF inference problems with semidefinite programming.
problem Computing partition function or MAP estimate in binary and multi-class MRFs.
method Coordinate-descent-based fast semidefinite solver for SDPs.
result Substantially outperforms existing state-of-the-art methods in approximate inference.
The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are ob…
A new method speeds up community detection in graphs.
problem Efficiently detecting communities in large graphs.
method Subsampled semidefinite programming for faster clustering.
result Statistical limits of sketching for community detection established.
Denise learns a function to quickly decompose covariance matrices robustly.
problem Robustly decomposing covariance matrices for feature extraction.
method Deep learning for symmetric positive semidefinite matrices.
result Denise achieves state-of-the-art performance in decomposition quality and speed.
We introduce a model-free relax-and-round algorithm for k-means clustering based on a semidefinite relaxation due to Peng and Wei. The algorithm interprets the SDP output as a denoised version of the original data and then rounds this output to a hard clustering. We provide a generic method for proving performance guar…
The paradigm of multi-task learning is that one can achieve better generalization by learning tasks jointly and thus exploiting the similarity between the tasks rather than learning them independently of each other. While previously the relationship between tasks had to be user-defined in the form of an output kernel, …
New PSDMF algorithms derived from PR and ARM methods.
problem Positive semidefinite matrix factorization (PSDMF) challenges.
method Design PSDMF algorithms based on phase retrieval (PR) and affine rank minimization (ARM) methods.
result New PSDMF algorithms inherit numerical properties from PR and ARM methods.
New geometric framework for positive semidefinite matrices of fixed rank.
problem Statistical analysis of positive semidefinite matrices of fixed rank.
method Introducing a manifold with Riemannian geometry and Lie group structure.
result Analytical closed forms for geodesics and Fréchet means.
Testing whether a probability distribution is compatible with a given Bayesian network is a fundamental task in the field of causal inference, where Bayesian networks model causal relations. Here we consider the class of causal structures where all correlations between observed quantities are solely due to the influenc…
This work studies low-rank approximation of a positive semidefinite matrix from partial entries via nonconvex optimization. We characterized how well local-minimum based low-rank factorization approximates a fixed positive semidefinite matrix without any assumptions on the rank-matching, the condition number or eigensp…
Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial …
New approach to convex hulls for low-rank problems.
problem Characterizing convex hulls for low-rank sets.
method Matrix perspective function and orthogonal projection matrices.
result Strong relaxations for various low-rank problems.
Factor analysis, a classical multivariate statistical technique is popularly used as a fundamental tool for dimensionality reduction in statistics, econometrics and data science. Estimation is often carried out via the Maximum Likelihood (ML) principle, which seeks to maximize the likelihood under the assumption that t…
Semidefinite programs have recently been developed for the problem of community detection, which may be viewed as a special case of the stochastic blockmodel. Here, we develop a semidefinite program that can be tailored to other instances of the blockmodel, such as non-assortative networks and overlapping communities. …
We consider the problem of identifying underlying community-like structures in graphs. Towards this end we study the Stochastic Block Model (SBM) on -clusters: a random model on vertices, partitioned in equal sized clusters, with edges sampled independently across clusters with probability and within …
New research disproves a key conjecture in optimization.
problem Comparison of sampling methods in stochastic optimization.
method Reduction to noncommutative arithmetic-geometric mean inequality and application of noncommutative Positivstellensatz.
result The Recht-Ré conjecture is false for general n.
We propose a semidefinite programming (SDP) algorithm for community detection in the stochastic block model, a popular model for networks with latent community structure. We prove that our algorithm achieves exact recovery of the latent communities, up to the information-theoretic limits determined by Abbe and Sandon (…
Optimal recovery framework for non-IID data in Hilbert spaces.
problem Generalization in non-IID data scenarios.
method Optimal recovery perspective, semidefinite programming, kernel ridgeless regression.
result Optimal recovery formula coincides with kernel ridgeless regression in some cases.