New Computational and Statistical Aspects of Regularized Regression with Application to Rare Feature Selection and Aggregation

A large portion of estimation procedures in high-dimensional statistics and machine learning have been designed based on principles and methods in continuous optimization. In this pursuit, incorporating prior knowledge on the target model, often presented as discrete and combinatorial descriptions, has been of interest in the past decade. Aside from many individual cases that have been studied in the literature, a number of general frameworks have been proposed. For example, [Bach et al., 2013, Obozinski and Bach, 2016] define sparsity-related norms and their associated optimization tools from support-based monotone set functions. On the other hand, several unifications have been proposed for the purpose of providing estimation and recovery guarantees. A et al., 2012] which connects the success ofwell-known example is the work of [Chandrasekaran norm minimization in model recovery given random linear measurements to the notion of Gaussian width [Gordon, 1988]. However, many of the final results of these frameworks (excluding discrete et al., 2013]) are quantities that are hard to compute; even evaluating theapproaches such as [Bach norm. Therefore, many a time computational aspects of these norms and their associated quantities are treated on a case by case basis. In fact, a unified framework for turning discrete descriptions into continuous tools for estimation, that 1) provides a computational suite of optimization tools, and 2) is amenable to statistical analysis, is largely underdeveloped.