I-LAMM FOR SPARSE LEARNING: SIMULTANEOUS CONTROL OF ALGORITHMIC COMPLEXITY AND STATISTICAL ERROR.

Area of Science:

• Computational statistics
• Optimization theory
• High-dimensional data analysis

Background:

• Fitting high-dimensional models often involves a trade-off between algorithmic complexity and statistical error.
• Nonconvex optimization problems present significant challenges in achieving both efficiency and accuracy.

Purpose of the Study:

• To propose a novel computational framework, iterative local adaptive majorize-minimization (I-LAMM), for fitting high-dimensional models.
• To simultaneously control algorithmic complexity and statistical error in nonconvex optimization.
• To provide theoretical guarantees for optimal statistical performance and controlled algorithmic complexity.

Main Methods:

• I-LAMM employs a two-stage approach based on local linear approximation of folded concave penalized quasi-likelihood.
• The first stage solves a convex program with coarse precision for an initial estimator.
• The second stage refines the estimator by iteratively solving convex programs with increasing precision.

Main Results:

• Theoretical analysis establishes a phase transition in iteration complexity: sublinear in the first stage, linear in the second.
• Demonstrates optimal statistical performances and controlled algorithmic complexity for a broad class of nonconvex problems.
• Establishes a contraction property showing iteration effects on statistical errors and provides optimality guarantees under weak assumptions.

Conclusions:

• I-LAMM offers a robust algorithmic solution for high-dimensional statistical modeling with nonconvex objectives.
• The framework achieves superior performance with weaker signal strength requirements compared to existing methods.
• Numerical results validate the theoretical findings, supporting the efficacy of I-LAMM.