Optimization Online


Consistency Bounds and Support Recovery of D-stationary Solutions of Sparse Sample Average Approximations

Miju Ahn (mijua***at***smu.edu)

Abstract: This paper studies properties of the d(irectional)-stationary solutions of sparse sample average approximation (SAA) problems involving difference-of-convex (dc) sparsity functions under a deterministic setting. Such properties are investigated with respect to a vector which satisfies a verifiable assumption to relate the empirical SAA problem to the expectation minimization problem defined by an underlying data distribution. We derive bounds for the distance between the two vectors and the difference of the model outcomes generated by them. Furthermore, the inclusion relationships between their supports, sets of nonzero valued indices, are studied. We provide conditions under which the support of a d-stationary solution is contained within, and contains, the support of the vector of interest; the first kind of inclusion can be shown for any arbitrarily given set of indices. Some of the results presented herein are generalization of the existing theory for a specialized problem of $\ell_1$-norm regularized least squares minimization for linear regression.

Keywords: nonconvex optimization, sparse learning, difference-of-convex program, directional stationarity

Category 1: Convex and Nonsmooth Optimization



Entry Submitted: 12/29/2018
Entry Accepted: 12/30/2018
Entry Last Modified: 11/25/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society