RANDOM CONVEX PROGRAMS WITH L1-REGULARIZATION: SPARSITY AND GENERALIZATION

Random convex programs are convex optimization problems that are robust with respect to a finite number of randomly sampled instances of an uncertain variable delta. This paper studies random convex programs in which there is uncertainty in the objective function. Specifically, let L(x, delta) be a loss function that is convex in x, the optimization variable, while it has an arbitrary dependence on the random variable d representing uncertainty in the optimization problem. After sampling N instances delta(1), delta(2),..., delta(N) of the random variable delta, the random convex program can be written as follows: minx maxi L(x, d(i)). The fundamental feature of this program is that its value L* N = max i L(x* N, delta(i)), where x* N is the solution, remains guaranteed when x* N is applied to the vast majority of the other unseen instances of delta; that is, L(x* N, delta) = L* N holds with high probability with respect to the uncertain variable d. This generalization property has justified a systematic and rigorous use of randomization in robust optimization. In this paper, we introduce L-1-regularization in random convex programs and show that L-1-regularization boosts the above generalization property so that generalization is achieved with significantly fewer samples than in the standard convex program given above. Explicit bounds are derived that allow a rigorous and easy implementation of the method.