The Many Faces of Regularization: from Signal Recovery to Online Algorithms

Wed, Jan 16, 2019, 4:30 pm
B205 Engineering Quadrangle
Center for Statistics and Machine Learning
Department of Electrical Engineering

In optimization, regularization plays several distinct roles. In the first part of the talk, we consider sample-efficient recovery of signals with low-dimensional structure, which is ill-posed without regularization. Choosing the right regularizer is key, and is well-understood for signals with a single structure: l1 norm for sparsity, nuclear norm for low rank matrices, etc.  However, in important problems such as sparse phase retrieval and sparse PCA, the desired signal exhibits several structures simultaneously, and a prevalent approach combines the regularizers that are sample-efficient for each individual structure. Our analysis challenges this prevalent approach: we prove that it can be highly suboptimal in the number of samples, thus new regularizers are needed for sample-efficient recovery.

Regularization is also employed for algorithmic efficiency. In the second part of the talk, we consider online resource allocation: sequentially allocating resources in response to online demands, with resource constraints that couple the decisions across time. Such problems arise in operations research (revenue management), computer science (online packing & covering), and e-commerce (“Adwords” problem in internet advertising). We examine primal-dual algorithms with a focus on the (worst-case) competitive ratio. We show how certain regularization (or smoothing) can improve this ratio, and how to seek the optimal regularization by solving an offline convex problem. This allows us to design effective regularization customized for a given cost function. The framework also extends to certain semidefinite programs, such as online D-optimal and A-optimal experiment design problems.

Maryam Fazel is an Associate Professor of Electrical and Computer Engineering at the University of Washington, with adjunct appointments in Computer Science and Engineering, Mathematics, and Statistics. Maryam received her MS and PhD from Stanford University, her BS from Sharif University of Technology in Iran, and was a postdoctoral scholar at Caltech before joining UW. She is a recipient of the NSF Career Award, UWEE Outstanding Teaching Award, UAI conference Best Student Paper Award (with her student), and coauthored a paper selected as a Fast-Breaking paper by Science Watch (2011). She co-leads the NSF TRIPODS Institute at UW on  Algorithmic Foundations for Data Science (ADSI) and is an associate editor of SIAM journals on Optimization and on Mathematics of Data Science.