Lewis Liu

Lewis Liu

Optimization, Algorithms, Probability, Statistics

Selected Publications

Spectrum Truncation Power Iteration for Agnostic Matrix Phase Retrieval

Published in IEEE Trans. on Signal Processing (To appear), 2021

We formulate agnostic matrix phase retrieval as a rank-restricted largest eigenvalue problem by applying the second-order Stein’s identity, and propose a new spectrum truncation power iteration (STPower) method to obtain the desired matrix efficiently. Also, we show a favorable rank recovery result by adopting the STPower method, i.e., a near-optimal statistical convergence rate under relatively general model assumptions from a wide range of applications.

Recommended citation: Liu, L., Lu, S., Zhao, T. & Wang, Z. Spectrum Truncation Power Iteration for Matrix Phase Retrieval. IEEE Trans. on Signal Processing, 2021+. http://lewis-algo.com/files/TSP_matrix.pdf

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets

Published in OPT 2020 @ NeurIPS., 2020

We introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, norm-independent analysis of Frank-Wolfe. Based on our analysis, we propose an affine invariant backtracking line-search. Interestingly, we show that typical backtracking line-searches using smoothness of the objective function surprisingly converge to an affine invariant step size, despite using affine-dependent norms in the computation of step sizes.

Recommended citation: Kerdreux, T., Liu, L., Lacoste-Julien, S., & Scieur, D. (2020). Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets. arXiv preprint. http://lewis-algo.com/files/aifw.pdf

Decentralized Policy Gradient Method for Mean-Field Linear Quadratic Regulator with Global Convergence

Published in Workshop on Real World Experiment Design and Active Learning at ICML 2020, 2020

We present the first decentralized policy gradient method (MF-DPGM) for mean-field multi-agent reinforcement learning, where exchangeable agents of a large team communicate via a connected network. We also give a rigorous proof of the global convergence rate of MF-DPGM by studying the geometry of the problem and estimating one-step progress under a decentralized scheme.

Download here