Random Convex Programs with L₁-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 δ representing uncertainty in the optimization problem. After sampling N instances δ⁽¹⁾, δ⁽²⁾, …, δ(N) of the random variable δ, the random convex program can be written as follows: minₓ maxᵢ L(x,δ⁽ⁱ⁾). The fundamental feature of this program is that its value L^N = maxᵢ L(x^N,δ⁽ⁱ⁾), where x^N is the solution, remains guaranteed when x^N is applied to the vast majority of the other unseen instances of δ; that is, L(x^N,δ) ≤ L^N 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 L₁-regularization in random convex programs and show that L₁-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.