I - 34151 Trieste Italy

*(+39) 040 2240 111*

*pio@ictp.it*

Asymptotic errors for convex penalized linear regression beyond Gaussian matrices and extension to the generalized linear model

Starts 14 Apr 2020 14:00

Ends 14 Apr 2020 15:00

Central European Time

ZOOM MEETING

Meeting ID: 475-819-702

Please note that the best option is for participants to download the Zoom Application from www.zoom.us/download and join the meeting with the Zoom Meeting ID 475-819-702
Join Zoom Meeting
https://zoom.us/j/475819702

We consider the problem of learning a coefficient vector x0 ∈ RN from noisy linear observations y=Fx0+w∈RM in the high dimensional limit M,N → ∞ with α ≡ M/N fixed. We provide a rigorous derivation of an explicit formula —first conjectured using heuristic methods from statistical physics— for the asymptotic mean squared error obtained by penalized convex regression estimators such as the LASSO or the elastic net, for a class of very generic random ma- trices corresponding to rotationally invariant data matrices with arbitrary spectrum. The proof is based on a convergence analysis of an oracle version of vector approximate message-passing (oracle-VAMP) and on the properties of its state evolution equations. Our method leverages on and highlights the link between vector approximate message-passing, Douglas-Rachford splitting and proximal descent algorithms, extending previous results obtained with i.i.d. matrices for a large class of problems. We illustrate our results on some concrete examples and show that even though they are asymptotic, our predictions agree remarkably well with numerics even for very moderate sizes.

We then show how the same proof can be extended to the generalized linear model using an oracle version of generalized vector approximate message passing (oracle-GVAMP) and a more elaborate convergence proof based on Lyapunov arguments from control theory.