QLQiuwei Li

Qiuwei 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

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


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


Latest Publications

  • Three-Operator Splitting for Learning to Predict Equilibria in Convex Games

    by D. McKenzie, H. Heaton, Q. Li, S. Wu Fung, S. Osher, W. Yin

    Systems of competing agents can often be modeled as games. Assuming rationality, the most likely outcomes are given by an equilibrium, e.g., a Nash equilibrium. In many practical settings, games are influenced by context, i.e., additional data beyond the control of any agent (e.g., weather for traffic and fiscal policy for market economies). Often, the exact game mechanics are unknown, yet vast amounts of historical data consisting of (context, equilibrium) pairs are available, raising the possibility of learning a solver that predicts the equilibria given only the context. We introduce Nash fixed-point networks (N-FPNs), a class of neural networks that naturally output equilibria. Crucially, N-FPNs employ a constraint decoupling scheme to handle complicated agent action sets while avoiding expensive projections. Empirically, we find that N-FPNs are compatible with the recently developed Jacobian-free backpropagation technique for training implicit networks, making them significantly faster and easier to train than prior models. Our experiments show that N-FPNs are capable of scaling to problems orders of magnitude larger than existing learned game solvers. All code is available online.


  • Open Access

    A Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization

    by Xiao Li, Zhihui Zhu, Qiuwei Li, Kai Liu

    The symmetric Nonnegative Matrix Factorization (NMF), a special but important class of the general NMF, has found numerous applications in data analysis such as various clustering tasks. Unfortunately, designing fast algorithms for the symmetric NMF is not as easy as for its nonsymmetric counterpart, since the latter admits the splitting property that allows state-of-the-art alternating-type algorithms. To overcome this issue, we first split the decision variable and transform the symmetric NMF to a penalized nonsymmetric one, paving the way for designing efficient alternating-type algorithms. We then show that solving the penalized nonsymmetric reformulation returns a solution to the original symmetric NMF. Moreover, we design a family of alternating-type algorithms and show that they all admit strong convergence guarantee: the generated sequence of iterates is convergent and converges at least sublinearly to a critical point of the original symmetric NMF. Finally, we conduct experiments on both synthetic data and real image clustering to support our theoretical results and demonstrate the performance of the alternating-type algorithms.

  • A super-resolution framework for tensor decomposition

    by Qiuwei Li, Ashley Prater, Lixin Shen, Gongguo Tang

    This work considers a super-resolution framework forovercomplete tensor decomposition. Specifically, we view tensor decomposition as a super-resolution problem of recovering a sum of Dirac measures on the sphere and solve it by minimizing a continuous analog of the $\ell _1$ norm on the space of measures. The optimal value of this optimization defines the tensor nuclear norm. Similar to the separation condition in the super-resolution problem, by explicitly constructing a dual certificate, we develop incoherence conditions of the tensor factors so that they form the unique optimal solution of the continuous analog of $\ell _1$ norm minimization. Remarkably, the derived incoherence conditions are satisfied with high probability by random tensor factors uniformly distributed on the sphere, implying global identifiability of random tensor factors.


  • A Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization

    by Xiao Li, Zhihui Zhu, Qiuwei Li, Kai Liu

    The symmetric Nonnegative Matrix Factorization (NMF), a special but important class of the general NMF, has found numerous applications in data analysis such as various clustering tasks. Unfortunately, designing fast algorithms for the symmetric NMF is not as easy as for its nonsymmetric counterpart, since the latter admits the splitting property that allows state-of-the-art alternating-type algorithms. To overcome this issue, we first split the decision variable and transform the symmetric NMF to a penalized nonsymmetric one, paving the way for designing efficient alternating-type algorithms. We then show that solving the penalized nonsymmetric reformulation returns a solution to the original symmetric NMF. Moreover, we design a family of alternating-type algorithms and show that they all admit strong convergence guarantee: the generated sequence of iterates is convergent and converges at least sublinearly to a critical point of the original symmetric NMF. Finally, we conduct experiments on both synthetic data and real image clustering to support our theoretical results and demonstrate the performance of the alternating-type algorithms.


  • The Global Optimization Geometry of Low-Rank Matrix Optimization

    by Zhihui Zhu, Qiuwei Li, Gongguo Tang, Michael B. Wakin

    This paper considers general rank-constrained optimization problems that minimize a general objective function ${f}( {X})$ over the set of rectangular ${n}\times {m}$ matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize $ {X}$ into $ {U} {V} ^{\mathrm {T}}$ where $ {U}$ and $ {V}$ are ${n}\times {r}$ and ${m}\times {r}$ matrices, respectively, and then optimize over the small matrices $ {U}$ and $ {V}$ . We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find ${n}\times {r}$ and ${m}\times {r}$ matrices $ {U}$ and $ {V}$ such that $ {U} {V} ^{\mathrm {T}}$ approximates a given matrix $ {X}^\star $ . Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where $\mathrm {rank}( {X}^\star) = {r}$ , but also for the over-parameterization case where $\mathrm {rank}( {X}^\star) < {r}$ and the under-parameterization case where $\mathrm {rank}( {X}^\star) > {r}$ . These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.


  • The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery Without Regularization

    by Shuang Li, Qiuwei Li, Zhihui Zhu, Gongguo Tang, Michael B. Wakin

    Low-rank matrix recovery is a fundamental problem in signal processing and machine learning. A recent very popular approach to recovering a low-rank matrix X is to factorize it as a product of two smaller matrices, i.e., X = U V, and then optimize over U, V instead of X. Despite the resulting non-convexity, recent results have shown that many factorized objective functions actually have benign global geometry---with no spurious local minima and satisfying the so-called strict saddle property---ensuring convergence to a global minimum for many local-search algorithms. Such results hold whenever the original objective function is restricted strongly convex and smooth. However, most of these results actually consider a modified cost function that includes a balancing regularizer. While useful for deriving theory, this balancing regularizer does not appear to be necessary in practice. In this work, we close this theory-practice gap by proving that the unaltered factorized non-convex problem, without the balancing regularizer, also has similar benign global geometry. Moreover, we also extend our theoretical results to the field of distributed optimization.


  • The Local Geometry of Orthogonal Dictionary Learning using L1 Minimization

    by Qiuwei Li, Zhihui Zhu, Michael Wakin, Gongguo Tang

    Feature learning that extracts concise and general- izable representations for data is one of the central problems in machine learning and signal processing. Sparse dictionary learning, also known as sparse coding, distinguishes from other feature learning techniques in sparsity exploitation, allowing the formulation of nonconvex optimizations that simultaneously uncover a structured dictionary and sparse representations. Despite the popularity of dictionary learning in applications, the landscapes of these optimizations that enable effective learning largely remain a mystery. This work characterizes the local optimization geometry for a simplified version of sparse coding where the L1 norm of the sparse coefficient matrix is minimized subject to orthogonal dictionary constraints. In particular, we show that the ground-truth dictionary and coefficient matrix are locally identifiable under the assumption that the coefficient matrix is sufficiently sparse and the number of training data columns is sufficiently large.

  • Open Access

    Provable Bregman-divergence based Methods for Nonconvex and Non-Lipschitz Problems

    by Qiuwei Li, Zhihui Zhu, Gongguo Tang, Michael B. Wakin

    The (global) Lipschitz smoothness condition is crucial in establishing the convergence theory for most optimization methods. Unfortunately, most machine learning and signal processing problems are not Lipschitz smooth. This motivates us to generalize the concept of Lipschitz smoothness condition to the relative smoothness condition, which is satisfied by any finite-order polynomial objective function. Further, this work develops new Bregman-divergence based algorithms that are guaranteed to converge to a second-order stationary point for any relatively smooth problem. In addition, the proposed optimization methods cover both the proximal alternating minimization and the proximal alternating linearized minimization when we specialize the Bregman divergence to the Euclidian distance. Therefore, this work not only develops guaranteed optimization methods for non-Lipschitz smooth problems but also solves an open problem of showing the second-order convergence guarantees for these alternating minimization methods.

  • Open Access

    Optimized Structured Sparse Sensing Matrices for Compressive Sensing

    by Tao Hong, Xiao Li, Zhihui Zhu, Qiuwei Li

    We consider designing a robust structured sparse sensing matrix consisting of a sparse matrix with a few non-zero entries per row and a dense base matrix for capturing signals efficiently We design the robust structured sparse sensing matrix through minimizing the distance between the Gram matrix of the equivalent dictionary and the target Gram of matrix holding small mutual coherence. Moreover, a regularization is added to enforce the robustness of the optimized structured sparse sensing matrix to the sparse representation error (SRE) of signals of interests. An alternating minimization algorithm with global sequence convergence is proposed for solving the corresponding optimization problem. Numerical experiments on synthetic data and natural images show that the obtained structured sensing matrix results in a higher signal reconstruction than a random dense sensing matrix.