Qiuwei Li

Qiuwei Li

Auto-generated profile, based on publicly available information

Qiuwei Li

Department of Electrical Engineering Colorado School of Mines CO USA

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 May 2018 in IEEE Transactions on Signal Processing
Verified
Journal Article
Closed access
ZZZhihui Zhu
Zhihui Zhu
QLQiuwei Li
Qiuwei Li
GTGongguo Tang
Gongguo Tang
MWMichael B. Wakin
Michael B. Wakin
This paper considers the minimization of a general objective function f(X) over the set of rectangular n $\times$ m matrices that have rank at most r. To reduce the computational burden, we factorize the variable X into a product of two smaller matrices and optimize over these two matrices instead of X. Despite the resulting nonconvexity, recent studies in matrix completion and sensing have shown that the factored problem has no spurious local minima and obeys the so-called strict saddle property (the function has a directional negative curvature at all critical points but local minima). We analyze the global geometry for a general and yet well-conditioned objective function f(X) whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence.

15 March 2018 in Information and Inference: A Journal of the IMA
Verified
Journal Article
Closed access
PDF file
QLQiuwei Li
Qiuwei Li
ZZZhihui Zhu
Zhihui Zhu
GTGongguo Tang
Gongguo Tang
This work considers two popular minimization problems: (i) the minimization of a general convex function f(X) with the domain being positive semi-definite matrices, and (ii) the minimization of a general convex function f(X) regularized by the matrix nuclear norm |$\|X\|_{*}$| with the domain being general matrices. Despite their optimal statistical performance in the literature, these two optimization problems have a high computational complexity even when solved using tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer and Monteiro to factor the low-rank variable |$X = UU^{\top } $| (for semi-definite matrices) or |$X=UV^{\top } $| (for general matrices) and also replace the nuclear norm |$\|X\|_{*}$| with |$\big(\|U\|_{F}^{2}+\|V\|_{F}^{2}\big)/2$|⁠. In spite of the non-convexity of the resulting factored formulations, we prove that each critical point either corresponds to the global optimum of the original convex problems or is a strict saddle where the Hessian matrix has a strictly negative eigenvalue. Such a nice geometric structure of the factored formulations allows many local-search algorithms to find a global optimizer even with random initializations.

5 January 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
ZZZhihui Zhu
Zhihui Zhu
QLQiuwei Li
Qiuwei Li
GTGongguo Tang
Gongguo Tang
MWMichael B. Wakin
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.

15 July 2020 in IEEE Signal Processing Letters
Verified
Journal Article
Closed access
SLShuang Li
Shuang Li
QLQiuwei Li
Qiuwei Li
ZZZhihui Zhu
Zhihui Zhu
GTGongguo Tang
Gongguo Tang
MWMichael B. Wakin
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.

11 July 2024 in SIAM Journal on Mathematics of Data Science
Verified
Journal Article
Closed access
DMD. McKenzie
D. McKenzie
HHH. Heaton
H. Heaton
QLQ. Li
Q. Li
SFS. Wu Fung
S. Wu Fung
SOS. Osher
S. Osher
WYW. Yin
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.

1 June 2019 in Signal Processing
Verified
Journal Article
Closed access
THTao Hong
Tao Hong
XLXiao Li
Xiao Li
ZZZhihui Zhu
Zhihui Zhu
QLQiuwei Li
Qiuwei Li