Xingguo Li
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Xingguo Li has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
- Jarvis Haupt
Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN, USA
2 shared publications - David Daniel Cox
MIT-IBM Watson AI Lab
1 shared publication - Han Liu
Center for Foundation Models and Generative AI Northwestern University 60208 Evanston IL USA
1 shared publication - Junwei Lu
Griffith University
1 shared publication - Kaidi Xu
City University of Hong Kong, Hong Kong, China
1 shared publication - Mingyi Hong
University of Minnesota, Minneapolis, MN, USA
1 shared publication
Latest Publications
- 17 June 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Letters
- Vol. 27 (10709908) , 1125-1129
On Recoverability of Randomly Compressed Tensors With Low CP Rank
Our interest lies in the recoverability properties of compressed tensors under the canonical polyadic decomposition (CPD) model. The considered problem is well-motivated in many applications, e.g., hyperspectral image and video compression. Prior work studied this problem under a variety of assumptions, e.g., that the latent factors of the tensor are sparse and that the compressing matrix follows a joint absolutely continuous distribution. These results leverage analytical tools such as CPD uniqueness and algebraic geometry—which are elegant. In this work, we offer an alternative result: We show that if the tensor is compressed by a subgaussian linear mapping, then the tensor is recoverable if the number of measurements is on the same order of magnitude as that of the model parameters. Unlike existing results, our proof is based on deriving a restricted isometry property (R.I.P.) under the CPD model via set covering techniques, and thus exhibits a flavor of classic compressive sensing. The new recoverability result enriches the understanding to the compressed CP tensor recovery problem. It offers theoretical guarantees for recovering tensors whose elements are not necessarily sparse; the compressing matrix is also not restricted to continuous matrices under our framework. The newly derived covering number for tensors with low CP rank may also benefit future research, e.g., sketching based tensor compression for reducing computational burden.
- 17 June 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Signal Processing Letters
- Vol. 27 (10709908) , 1125-1129
On Recoverability of Randomly Compressed Tensors With Low CP Rank
Our interest lies in the recoverability properties of compressed tensors under the canonical polyadic decomposition (CPD) model. The considered problem is well-motivated in many applications, e.g., hyperspectral image and video compression. Prior work studied this problem under a variety of assumptions, e.g., that the latent factors of the tensor are sparse and that the compressing matrix follows a joint absolutely continuous distribution. These results leverage analytical tools such as CPD uniqueness and algebraic geometry—which are elegant. In this work, we offer an alternative result: We show that if the tensor is compressed by a subgaussian linear mapping, then the tensor is recoverable if the number of measurements is on the same order of magnitude as that of the model parameters. Unlike existing results, our proof is based on deriving a restricted isometry property (R.I.P.) under the CPD model via set covering techniques, and thus exhibits a flavor of classic compressive sensing. The new recoverability result enriches the understanding to the compressed CP tensor recovery problem. It offers theoretical guarantees for recovering tensors whose elements are not necessarily sparse; the compressing matrix is also not restricted to continuous matrices under our framework. The newly derived covering number for tensors with low CP rank may also benefit future research, e.g., sketching based tensor compression for reducing computational burden.
- 1 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 10, 702-706
Sketching Dictionary Based Robust PCA in Large Matrices
In this paper, our goal is to rapidly locating a few outliers and recover a low dimensional space spanned by inliers, with the particular interest when the outliers have known basis. A simple two-step approach is proposed based on a sketching procedure with theoretical guarantees for the performance. We show that exact identification of the outliers and recovery of the subspace can be achieved using sketched samples as few as the rank plus the number of outliers, ignoring logarithmic factors. This results in significant improvement on both sampling and computational efficiency. Comprehensive numerical experiments are provided to show the efficiency of our proposed method.
- 1 November 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 10, 702-706
Sketching Dictionary Based Robust PCA in Large Matrices
In this paper, our goal is to rapidly locating a few outliers and recover a low dimensional space spanned by inliers, with the particular interest when the outliers have known basis. A simple two-step approach is proposed based on a sketching procedure with theoretical guarantees for the performance. We show that exact identification of the outliers and recovery of the subspace can be achieved using sketched samples as few as the rank plus the number of outliers, ignoring logarithmic factors. This results in significant improvement on both sampling and computational efficiency. Comprehensive numerical experiments are provided to show the efficiency of our proposed method.
- Open Access
ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
The adaptive momentum method (AdaMM), which uses past gradients to update descent directions and learning rates simultaneously, has become one of the most popular first-order optimization methods for solving machine learning problems. However, AdaMM is not suited for solving black-box optimization problems, where explicit gradient forms are difficult or infeasible to obtain. In this paper, we propose a zeroth-order AdaMM (ZO-AdaMM) algorithm, that generalizes AdaMM to the gradient-free regime. We show that the convergence rate of ZO-AdaMM for both convex and nonconvex optimization is roughly a factor of $O(\sqrt{d})$ worse than that of the first-order AdaMM algorithm, where $d$ is problem size. In particular, we provide a deep understanding on why Mahalanobis distance matters in convergence of ZO-AdaMM and other AdaMM-type methods. As a byproduct, our analysis makes the first step toward understanding adaptive learning rate methods for nonconvex constrained optimization. Furthermore, we demonstrate two applications, designing per-image and universal adversarial attacks from black-box neural networks, respectively. We perform extensive experiments on ImageNet and empirically show that ZO-AdaMM converges much faster to a solution of high accuracy compared with $6$ state-of-the-art ZO optimization methods.Open AccessZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
The adaptive momentum method (AdaMM), which uses past gradients to update descent directions and learning rates simultaneously, has become one of the most popular first-order optimization methods for solving machine learning problems. However, AdaMM is not suited for solving black-box optimization problems, where explicit gradient forms are difficult or infeasible to obtain. In this paper, we propose a zeroth-order AdaMM (ZO-AdaMM) algorithm, that generalizes AdaMM to the gradient-free regime. We show that the convergence rate of ZO-AdaMM for both convex and nonconvex optimization is roughly a factor of $O(\sqrt{d})$ worse than that of the first-order AdaMM algorithm, where $d$ is problem size. In particular, we provide a deep understanding on why Mahalanobis distance matters in convergence of ZO-AdaMM and other AdaMM-type methods. As a byproduct, our analysis makes the first step toward understanding adaptive learning rate methods for nonconvex constrained optimization. Furthermore, we demonstrate two applications, designing per-image and universal adversarial attacks from black-box neural networks, respectively. We perform extensive experiments on ImageNet and empirically show that ZO-AdaMM converges much faster to a solution of high accuracy compared with $6$ state-of-the-art ZO optimization methods. - 27 March 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (6) , 3489-3514
Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
We propose a general theory for studying the landscape of nonconvex optimization with underlying symmetric structures for a class of machine learning problems (e.g., low-rank matrix factorization, phase retrieval, and deep linear neural networks). In particular, we characterize the locations of stationary points and the null space of Hessian matrices of the objective function via the lens of invariant groups. As a major motivating example, we apply the proposed general theory to characterize the global landscape of the nonconvex optimization in low-rank matrix factorization problem. We illustrate how the rotational symmetry group gives rise to infinitely many nonisolated strict saddle points and equivalent global minima of the objective function. By explicitly identifying all stationary points, we divide the entire parameter space into three regions: (R 1 ) the region containing the neighborhoods of all strict saddle points where the objective has negative curvature; (R 2 ) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and (R 3 ) the complement of the above regions, where the gradient has sufficiently large magnitude. We further extend our result to the matrix sensing problem. Such global landscape implies that strong global convergence guarantees for popular iterative algorithms with arbitrary initial solutions.
- 27 March 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (6) , 3489-3514
Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
We propose a general theory for studying the landscape of nonconvex optimization with underlying symmetric structures for a class of machine learning problems (e.g., low-rank matrix factorization, phase retrieval, and deep linear neural networks). In particular, we characterize the locations of stationary points and the null space of Hessian matrices of the objective function via the lens of invariant groups. As a major motivating example, we apply the proposed general theory to characterize the global landscape of the nonconvex optimization in low-rank matrix factorization problem. We illustrate how the rotational symmetry group gives rise to infinitely many nonisolated strict saddle points and equivalent global minima of the objective function. By explicitly identifying all stationary points, we divide the entire parameter space into three regions: (R 1 ) the region containing the neighborhoods of all strict saddle points where the objective has negative curvature; (R 2 ) the region containing neighborhoods of all global minima, where the objective enjoys strong convexity along certain directions; and (R 3 ) the complement of the above regions, where the gradient has sufficiently large magnitude. We further extend our result to the matrix sensing problem. Such global landscape implies that strong global convergence guarantees for popular iterative algorithms with arbitrary initial solutions.