6 citations · 16 across the 10 of their papers we have counts for
10 papers
Scalable Second-order Riemannian Optimization for -means Clustering
Peng Xu, Chun-Ying Hou, Xiaohui Chen +1
Clustering is a hard discrete optimization problem. Nonconvex approaches such as low-rank semidefinite programming (SDP) have recently demonstrated promising statistical and local…
Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
Gavin Zhang, Salar Fattahi, Richard Y. Zhang
In practical instances of nonconvex matrix factorization, the rank of the true solution is often unknown, so the rank of the model can be overspecified as $r>r^{\st…
Complexity of Chordal Conversion for Sparse Semidefinite Programs with Small Treewidth
Richard Y. Zhang
If a sparse semidefinite program (SDP), specified over matrices and subject to linear constraints, has an aggregate sparsity graph with small treewidth, then ch…
Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming
Yubo Zhuang, Xiaohui Chen, Yun Yang +1
-means clustering is a widely used machine learning method for identifying patterns in large datasets. Recently, semidefinite programming (SDP) relaxations have been proposed fo…
Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent
Gavin Zhang, Hong-Ming Chiu, Richard Y. Zhang
Non-convex gradient descent is a common approach for estimating a low-rank ground truth matrix from noisy measurements, because it has per-iteration costs as low as $O(…
Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxations
Hong-Ming Chiu, Richard Y. Zhang
Adversarial training is well-known to produce high-quality neural network models that are empirically robust against adversarial perturbations. Nevertheless, once a model has been…
Simple Alternating Minimization Provably Solves Complete Dictionary Learning
Geyu Liang, Gavin Zhang, Salar Fattahi +1
This paper focuses on the noiseless complete dictionary learning problem, where the goal is to represent a set of given signals as linear combinations of a small number of atoms fr…
Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion
Gavin Zhang, Hong-Ming Chiu, Richard Y. Zhang
The matrix completion problem seeks to recover a ground truth matrix of low rank from observations of its individual elements. Real-world matrix completion is…
Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
Richard Y. Zhang
We consider minimizing a twice-differentiable, -smooth, and -strongly convex objective over an positive semidefinite matrix , under the assumption…
Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification
Gavin Zhang, Salar Fattahi, Richard Y. Zhang
We consider using gradient descent to minimize the nonconvex function over an factor matrix , in which is an underlying smooth convex cost funct…