OPTIMAL COMPUTATIONAL AND STATISTICAL RATES OF CONVERGENCE FOR SPARSE NONCONVEX LEARNING PROBLEMS.

Area of Science:

• Statistical Learning Theory
• Optimization
• Machine Learning

Background:

• Penalized M-estimators often involve nonconvex optimization, making global solutions computationally intractable.
• Existing methods struggle with efficient computation of the full regularization path and refined statistical guarantees.

Purpose of the Study:

• To develop an approximate regularization path-following method for solving learning problems with nonconvex objective functions.
• To provide unified theoretical analysis of statistical and computational properties for local solutions.

Main Methods:

• Proposed an approximate regularization path-following algorithm.
• Developed a unified analytic framework for theoretical analysis.
• Derived explicit rates of convergence for computational and statistical properties.

Main Results:

• The algorithm achieves a global geometric rate of convergence for the full regularization path, optimal for first-order methods.
• Refined iteration complexity bounds characterize performance across the regularization path.
• Sharp sample complexity analysis and exact support recovery are provided for approximate local solutions.

Conclusions:

• The proposed method efficiently computes the full regularization path with optimal computational rates.
• The statistical analysis offers improved sample complexity and oracle properties for the final estimator.
• Nonconvex penalties are shown to yield superior statistical performance in penalized M-estimation.