The Gaussian min-max theorem in the Presence of Convexity

Abstract

Gaussian comparison theorems are useful tools in probability theory; they are essential ingredients in the classical proofs of many results in empirical processes and extreme value theory. More recently, they have been used extensively in the analysis of non-smooth optimization problems that arise in the recovery of structured signals from noisy linear observations. We refer to such problems as Primary Optimization (PO) problems. A prominent role in the study of the (PO) problems is played by Gordon's Gaussian min-max theorem (GMT) which provides probabilistic lower bounds on the optimal cost via a simpler Auxiliary Optimization (AO) problem. Motivated by resent work of M. Stojnic, we show that under appropriate convexity assumptions the (AO) problem allows one to tightly bound both the optimal cost, as well as the norm of the solution of the (PO). As an application, we use our result to develop a general framework to tightly characterize the performance (e.g. squared-error) of a wide class of convex optimization algorithms used in the context of noisy signal recovery.

Significantly extended second version

References in corpus (6)

• A framework to characterize performance of LASSO algorithms
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO
• Meshes that trap random subspaces
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• Gordon's inequality and condition numbers in conic optimization

Cited by in corpus (1)

• Asymptotically Exact Error Analysis for the Generalized ${\ell }_2^2$-LASSO