Difference-of-convex learning: optimization with non-convex sparsity functions

2018-08-13This dissertation contains three individual collaborative studies for sparse learning problems and presents each work as a separate chapter. In Chapter 2, followed by Introduction, we study a bi-criteria Lagrangian formulation involving non-convex and non-differentiable functions which surrogate the discrete sparsity function. We introduce a unified difference-of-convex formulation applicable to most of the existing such surrogates and study d(irectional)-stationary solutions of the non-convex program. We provide conditions under which the d-stationary solutions of the problem are the global minima possibly of a restricted kind due to non-differentiability. The sparsity properties of the d-stationary solutions are investigated based on the given model constants. Generalized and specialized results for such properties of the stationary solutions are provided according to the specific choices of the sparsity functions. In Chapter 3, we introduce a new constraint system for sparse variable selection problems. Such a system arises when there are logical conditions among certain model variables that need to be incorporated into their selection process. Formally, extending a cardinality constraint, an affine sparsity constraint (ASC) is defined by a linear inequality with two sets of variables: one set of continuous variables and the other set represented by their nonzero patterns. We study an ASC system consisting of finitely many affine sparsity constraints. We investigate fundamental structural properties of the solution set of such a non-standard system of inequalities, including its closedness and the description of its closure, continuous approximations and their set convergence, and characterizations of its tangent cones for use in optimization. Based on the obtained structural properties of an ASC system, we investigate the convergence of B(ouligand)-stationary solutions when the ASC is approximated by the sparsity functions. Our study lays a solid mathematical foundation for solving optimization problems involving these affine sparsity constraints through their continuous approximations. In the fourth and final chapter, we investigate the relationship between the sparse sample average approximation (SAA) problem and the expectation minimization problem where the expected model loss is minimized over an unknown data distribution. The connection is analyzed through two measures of interests: a d-stationary solution of the sparse SAA problem and a point which satisfies a verifiable condition and is possibly the optimal solution of the underlying problem. We derive a bound for the distance between the solutions and a prediction error bound measuring the difference between the model outcomes generated by the two solutions. We further investigate conditions under which the support of a given d-stationary solution achieves no false inclusion and no false exclusion. A noteworthy point is that the former kind of inclusion is shown for any arbitrarily given subset of indices. The presented results generalize the existing theory developed based on the optimal solution of a convex program by relaxing requirement of the global optimum and employing general model and loss functions with non-convex sparsity surrogates