Sample Average Approximation with Sparsity-Inducing Penalty for High-Dimensional Stochastic Programming.

Area of Science:

• Optimization
• Stochastic Programming
• Statistical Learning

Background:

• Traditional sample average approximation (SAA) for stochastic programming (SP) requires a polynomial number of samples relative to problem dimensions for accurate optimization.
• High-dimensional statistical learning often deals with problems where the dimension is not polynomially bounded by the sample size.

Purpose of the Study:

• To investigate a modified SAA scheme using folded concave penalty (FCP) for sparse or approximately sparse solutions in SP.
• To demonstrate a significant reduction in sample size requirements for approximating global solutions in convex SP.
• To discuss the applicability of FCP regularizers for nonconvex SPs.

Main Methods:

• Applying a folded concave penalty (FCP) to a sample average approximation (SAA) formulation in stochastic programming.
• Solving the FCP-regularized SAA formulation locally.
• Analyzing the sample size requirements for approximating the global solution of convex SPs.

Main Results:

• The FCP-regularized SAA approach significantly reduces the required number of samples for convex SPs.
• Sample size requirements are reduced to poly-logarithmic in the number of dimensions when using FCP.
• The study discusses the efficacy of FCP for nonconvex SPs and its implications for high-dimensional sparse M-estimators.

Conclusions:

• The proposed FCP-regularized SAA method offers a more sample-efficient approach to solving stochastic programs, particularly those with sparse solutions.
• This method has practical implications for high-dimensional statistical learning, enabling robust performance even when dimensions exceed sample size polynomially.
• The findings suggest a more flexible and efficient framework for tackling complex optimization and learning problems in high dimensions.