XLXingguo Li

Xingguo Li

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Xingguo Li has a total of 14 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • On Recoverability of Randomly Compressed Tensors With Low CP Rank

    by Shahana Ibrahim, Xiao Fu, Xingguo Li

    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.


  • Sketching Dictionary Based Robust PCA in Large Matrices

    by Xingguo Li, Jarvis Haupt

    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

    by Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, David Cox

    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.

  • Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization

    by Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, Tuo Zhao

    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.