Paper proposes a method to estimate cluster number without prior knowledge.
problem Community detection in unlabeled networks.
method Semi-definite relaxations for estimating cluster number and matrix.
result Method recovers cluster number and matrix exactly with high probability.
We propose an SDP relaxation for the Gromov-Wasserstein distance, providing globally optimal solutions.
problem Matching objects between incomparable spaces using the Gromov-Wasserstein distance.
method Semi-definite programming (SDP) relaxation of the GW distance.
result The SDP relaxation provides globally optimal solutions for the GW distance in some instances.
Paper introduces new norms for rank-constrained optimization problems.
problem Rank-constrained optimization problems in various fields.
method Introduces a family of low-rank inducing norms and regularizers.
result Other low-rank inducing norms outperform nuclear norm in matrix completion problems.
Paper optimizes ADMM convergence with IQC for convex functions.
problem Optimizing convergence rate of ADMM for convex functions.
method Derived explicit solution for SDP convergence rate using IQC.
result General formulas for optimal ADMM parameter selection.
Improves scalability of Bayesian optimization for combinatorial spaces.
problem Optimizing expensive functions over large combinatorial spaces.
method Parametrized Submodular Relaxation (PSR) to solve AFO problems for BOCS.
result Significant improvements in scalability and accuracy for BOCS model.
This paper provides an explicit rate bound for over-relaxed ADMM.
problem Computing upper bounds on the convergence rate of ADMM.
method Reduces the problem to SDP and solves it analytically.
result Provides a general and explicit upper bound on the convergence rate of ADMM.
New methods for phase estimation in mixed signals, improving source separation.
problem Estimating phases of mixed complex signals from multichannel observations.
method Three approaches: heuristic, alternate minimization, and convex relaxation.
result Convex relaxation approach yields best results, including exact source separation.
Efficient PAC learning for contrastive linear representations is achieved.
problem Efficient PAC learning for contrastive linear representations.
method Relaxing the problem to a semi-definite program and using Rademacher complexity.
result First efficient PAC learning algorithm for contrastive learning.
This paper establishes a statistical versus computational trade-off for solving a basic high-dimensional machine learning problem via a basic convex relaxation method. Specifically, we consider the {\em Sparse Principal Component Analysis} (Sparse PCA) problem, and the family of {\em Sum-of-Squares} (SoS, aka Lasserre/…
Optimal neural network approximation for Wasserstein gradient direction via convex optimization.
problem Approximating Wasserstein gradient direction with limited data.
method Two-layer networks with squared-ReLU activations, SDP relaxation.
result Optimal approximation of Wasserstein gradient direction in two-layer networks.
New regularizer for machine learning using private data.
problem Machine learning with private data.
method Distributionally-robust optimization with locally-differentially-private datasets.
result New regularizer for training linear regression models.
Paper proposes a new covariance estimator ensuring positive semi-definite matrices.
problem Estimating spot covariance matrices while maintaining positive semi-definiteness.
method Modification of the Fourier covariance estimator with a symmetric positive semi-definite constraint.
result The estimator is consistent and produces accurate positive semi-definite matrices.
FORCE efficiently solves complex clustering problems with guaranteed optimality.
problem Efficiently clustering variables or points into groups using SDP relaxations.
method Combines primal first-order method with dual optimality certificate search.
result Guaranteed to find optimal solution for certain variable clustering problems.
Local algorithms perform well on SDP relaxations of graph bisection problems.
problem Understanding the performance of local algorithms on SDP relaxations of graph bisection problems.
method Used dual witness construction and harmonic measure on limiting Galton-Watson tree.
result Simple local algorithms are at most 8/9 suboptimal for graph bisection problems.
The paper characterizes Einstein 4-manifolds with semi-definite curvature and derives inequalities.
problem Characterizing Einstein 4-manifolds with semi-definite sectional curvature.
method Using pointwise inequalities involving scalar curvature and Weyl curvatures.
result Closed 4-dimensional Einstein metrics saturating the pointwise inequality are completely characterized.
Proves Gerber statistic is always non-negative.
problem Verifying the positive semi-definiteness of Gerber statistic.
method Analytical proof of both forms of Gerber statistic.
result Gerber statistic is positive semi-definite.
New algorithm for overcomplete ICA with reduced complexity.
problem Overcoming high computational complexity in overcomplete ICA.
method Estimates Hessians of cumulant generating function and uses SDP relaxation.
result Recovery of a mixing component at the rate k < p^2/4 with high probability.
Paper proposes a new method for clustering high-dimensional data.
problem Clustering high-dimensional data efficiently and accurately.
method Uses Semi-Definite Programming to estimate cluster matrix from pairwise distances.
result The method provides theoretical guarantees and outperforms existing techniques.
This paper proposes exact and approximation algorithms for Sparse PCA, improving interpretability and scalability.
problem Selecting a prespecified-size principal submatrix from a covariance matrix to maximize its largest eigenvalue.
method Proposes two exact mixed-integer SDPs and a mixed-integer linear program (MILP) for SPCA, analyzes theoretical optimality gaps, and develops approximation algorithms.
result The proposed algorithms achieve strong theoretical optimality and effective scalability, with continuous relaxations close to optimality and MILP solving small to medium-size instances.
The paper examines the optimality of kernel methods in high-dimensional clustering.
problem Understanding the optimality of kernel methods in high-dimensional data clustering.
method High-dimensional Gaussian clustering, exponential kernel function, kernel k-means, semi-definite relaxation.
result The exponential kernel function optimally recovers clusters in high-dimensional data, matching information-theoretic limits up to a factor of √2.
This paper presents a new method for dimensionality reduction and out-of-sample extension.
problem Dimensionality reduction and out-of-sample extension in high-dimensional data.
method Adaptive non-linear embedding using positive semi-definite kernel eigenvectors.
result The embedding method is more robust to outliers compared to spectral embedding.
Efficiently constructs prediction bands with minimal assumptions.
problem Uncertainty quantification for nonparametric, heteroscedastic data.
method Semi-definite programming for data-adaptive prediction bands.
result Strong non-asymptotic coverage properties with minimal distributional assumptions.
Paper studies community detection in censored hypergraphs using information theory.
problem Community detection in censored hypergraphs with missing values.
method Information-theoretic approach, polynomial-time algorithm, spectral algorithm with refinement.
result Derives information-theoretic threshold for exact recovery of community structure.
New approach to analyze matrix denoising using gradient flow and fixed point equations.
problem Positive semi-definite matrix denoising in extensive-rank and high-dimensional settings.
method Gradient flow and fixed point equations derived from linear pencil techniques of random matrix theory.
result Continuous phase transitions in the extensive-rank and high-dimensional regime.
Upper bound found for dimensions of subspaces where holomorphic sectional curvature vanishes.
problem Finding upper bounds for dimensions of subspaces where holomorphic sectional curvature vanishes.
method Connection with D'Angelo's work on complex subvarieties of real algebraic varieties and decomposition of polynomials into differences of squares.
result An upper bound for the dimensions of these subspaces is found.
Study proves Kählerness criteria for Hermitian surfaces under specific curvature conditions.
problem Determining when Hermitian surfaces are Kählener.
method Used explicit identities linking Strominger-Bismut Ricci curvatures to torsion, and Chern number identities.
result Proves several Kählerness criteria for compact Hermitian surfaces.
Unified framework for hyperparameter tuning in clustering problems.
problem Challenges in selecting hyperparameters for unsupervised learning, especially in clustering.
method A unified framework with provable guarantees for hyperparameter selection in various models.
result Framework outperforms other widely used tuning procedures in various settings.
Paper optimizes prices for better future profits using machine learning.
problem Optimizing prices to maximize future profit/revenue.
method Builds sales forecast formulas and constructs a binary quadratic programming optimization problem, then uses SDP relaxation for fast approximation.
result Simultaneously derives optimal prices for tens/hundreds of products with practical computational time, potentially improving gross profit by 8.2%.
Paper develops Riemannian geometry for SPSD matrices with DA applications.
problem Riemannian geometry of SPSD matrices for DA.
method Closed-form expressions, approximations of geodesic path, PT, canonical representation.
result Proposes an algorithm for DA with improved performance.
A new method for deep Wishart processes improves kernel-based models.
problem Inference in deep Wishart processes is challenging due to the need for flexible distributions over positive semi-definite matrices.
method Developed a novel approach to flexible distributions over positive semi-definite matrices using the Bartlett decomposition of the Wishart probability density. Used this to create an approximate posterior for the DWP.
result Improved performance of inference in the DWP compared to DGP with equivalent prior.
Method learns SDEs from data snapshots.
problem Learning drift and diffusion of SDEs from data.
method Two-step process: learn drift by expected value, learn diffusion by SDP.
result Validated on examples and simulations.
Paper uses SDP for community detection with side information.
problem Community detection in graphs with additional non-graph data.
method Formulates SDP relaxation for maximum likelihood node labeling with side information.
result SDP achieves same exact recovery threshold as maximum likelihood with side information.
Proposes DILATE and STRIPE++ for precise time series forecasting.
problem Non-stationary signals with sudden changes.
method Incorporates shape and temporal criteria in deep learning models.
result Improves precision in deterministic and probabilistic forecasting.
Paper tackles clustering with ordinal comparisons, achieving near-optimal results.
problem Clustering with ordinal comparisons when similarity measures are not available.
method Two-step procedure: estimate similarity matrix from comparisons, then apply SDP clustering.
result Near-optimal recovery of planted clustering using near-optimal number of comparisons.
This work improves grid observability using smart meter data.
problem Limited metering infrastructure leads to observability issues in distribution grids.
method Developed a coupled formulation of the power flow problem (CPF) and a coupled power system state estimation (CPSSE) problem to infer grid state.
result A necessary and sufficient criterion for local observability in radial networks was identified.
In this paper we present a slight modification of the Fourier estimation method of the spot volatility (matrix) process of a continuous Itô semimartingale where the estimators are always non-negative definite. Since the estimators are factorized, computational cost will be saved a lot.
New method learns nonsymmetric DPPs for better modeling diverse sets.
problem Nonsymmetric DPPs for better modeling diverse sets.
method Maximum likelihood estimation with a specific kernel decomposition.
result Improved predictive performance compared to symmetric DPPs.
Proposes a new method for publishing covariance matrices while maintaining privacy and preserving matrix properties.
problem Publishing covariance matrices while ensuring differential privacy and maintaining positive semi-definiteness.
method Uses a Wishart distribution to generate matrix noise for differential privacy in principal component analysis.
result Demonstrates better utility compared to the Laplace mechanism and provides a near optimal bound.
Introduce Collapsed Effective Operators for higher-order structures.
problem Existing spectral operators decompose topology into separate ranks, leaving practitioners to fuse information back to vertices.
method Introduce Collapsed Effective Operators via Schur complementation of a graded Laplacian.
result Preserves positive semi-definiteness, lowers system energy under higher-order connectivity.
A new imputation method estimates missing values by matching observed marginals from masked data.
problem Missing values in data undermine statistical and machine learning analysis.
method Estimates a distribution from masked observations using positive semi-definite kernel density estimation.
result The method yields both single and multiple imputations from the same fitted density, with statistical consistency and fast adaptive excess risk.
Unified approach to Bayesian inference with guarantees on covariance matrices.
problem Approximate Bayesian inference with PSD guarantees.
method Bayes-Newton methods extending Newton's method for optimisation.
result Novel algorithms with PSD covariance matrices.
The paper presents two schemes for sampling matrices from specific distributions on a manifold.
problem Sampling matrices from Gibbs distributions on the manifold of positive semi-definite matrices with fixed rank.
method Two explicit schemes based on Euler-Maruyama discretization of the Riemannian Langevin equation with Brownian motion on the manifold.
result Numerical validation of the schemes using specific energy functions and metrics.
Tseytlin has recently proposed that an action functional exists whose gradient generates to all orders in perturbation theory the Renormalization Group (RG) flow of the target space metric in the worldsheet sigma model. The gradient is defined with respect to a metric on the space of coupling constants which is explici…
New algorithm solves fair PCA, robust PCA, and sparse PCA problems efficiently.
problem Fair Principal Component Analysis (FPCA) to ensure fairness in PCA solutions.
method Iterative MM algorithm with SDP reformulation to quadratic program.
result Algorithm monotonically improves fairness objectives at each iteration.
New method for symmetric matrix completion using ReLU sampling.
problem Symmetric positive semi-definite low-rank matrix completion with deterministic entry-dependent sampling.
method ReLU sampling, gradient descent with tailored initialization.
result Gradient descent with tailored initialization achieves global minima.
New distances measure mixtures of Gaussians, useful in machine learning.
problem Comparing distributions with disjoint supports.
method Schoenberg-Rao distances based on concave Rao's entropy.
result Closed-form distances for mixtures of Gaussians.
Paper introduces a new kernel model for PSD-valued functions with theoretical guarantees and applications.
problem Enforcing positive semi-definiteness (PSD) in function models with good performance and theoretical guarantees.
method Kernel sum-of-squares model for PSD-valued functions, extending previous models for non-negative scalar functions.
result The model constitutes a universal approximator of PSD functions and can represent any smooth and strongly convex function.
Motivated by the results of B. Berndtsson, in this memoir we use the new estimates developed by W. He to extend a theorem of the second author on the existence of weak C1,1 geodesics between two smooth non-degenerate Kähler potentials to the case where the metrics on the end points may have singularities on some a…