A Two-Stage Approach for Learning a Sparse Model with Sharp Excess Risk Analysis

This paper aims to provide a sharp excess risk guarantee for learning a sparse linear model without any assumptions about the strong convexity of the expected loss and the sparsity of the optimal solution in hindsight. Given a target level for the excess risk, an interesting question to ask is how many examples and how large the support set of the solution are enough for learning a good model with the target excess risk. To answer these questions, we present a two-stage algorithm that (i) in the first stage an epoch based stochastic optimization algorithm is exploited with an established O(1/epsilon) bound on the sample complexity; and (ii) in the second stage a distribution dependent randomized sparsification is presented with an O(1/epsilon) bound on the sparsity (referred to as support complexity) of the resulting model. Compared to previous works, our contributions lie at (i) we reduce the order of the sample complexity from O(1/epsilon(2)) to O(1/epsilon) without the strong convexity assumption; and (ii) we reduce the constant in O(1/epsilon) for the sparsity by exploring the distribution dependent sampling.