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 δ. This paper studies random convex programs in which there is uncertainty in the objective function. Specifically, let L(x, δ) 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 δ(1), δ(N) of the random variable δ, the random convex program can be written as follows: minx maxi L(x, δ(i)). The fundamental feature of this program is that its value LN* = maxi L(xN*,δ(i)), where xN* is the solution, remains guaranteed when xN* is applied to the vast majority of the other unseen instances of δ; that is, L(xN*, δ) ≤ LN* holds with high probability with respect to the uncertain variable δ. This generalization property has justified a systematic and rigorous use of randomization in robust optimization. In this paper, we introduce L1-regularization in random convex programs and show that L1-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. [ABSTRACT FROM AUTHOR]