TL;DR
This paper introduces a novel algorithmic framework, SSQP, for a challenging class of optimization problems involving composite $L_q$ minimization over polyhedra. The key contribution is the first-ever worst-case iteration complexity guarantee for solving these problems, which are notoriously difficult and appear in various real-world applications.
What Problem Does This Paper Address?
The paper tackles the problem of minimizing a composite function of the form $f(x) + h(x)$ over a polyhedral set $X$, where $f(x)$ is a non-smooth, non-convex, and non-Lipschitzian $L_q$ norm (with $0 < q < 1$) and $h(x)$ is a smooth function. This specific problem structure, particularly the $L_q$ norm with $q<1$, arises in numerous applications like machine learning, signal processing, and wireless communications, often related to finding sparse solutions or identifying important components. However, the non-convexity and non-Lipschitzian nature of the $L_q$ norm, combined with general polyhedral constraints, makes these problems theoretically intractable (strongly NP-hard) and algorithmically challenging. Existing methods often struggle with these complexities or lack theoretical guarantees.
Methods
The authors propose a Smoothing Sequential Quadratic Programming (SSQP) framework. The core idea is to approximate the non-smooth $L_q$ term with a smooth function, transforming the original problem into a sequence of smoother, albeit still challenging, subproblems. At each outer iteration, a smoothing parameter is reduced. For each smoothed problem, the framework approximately solves a convex Quadratic Program (QP) subproblem. This QP subproblem is constructed using a local quadratic upper bound of the smoothed objective function. The paper also derives Karush-Kuhn-Tucker (KKT) optimality conditions for local minimizers of the original problem and develops a lower bound theory for these minimizers.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Strong NP-Hardness: The paper establishes that even the unconstrained version of this problem is strongly NP-hard, highlighting the inherent difficulty of finding global minimizers.
- KKT Conditions for Non-Lipschitzian Problems: Deriving and analyzing KKT conditions for non-Lipschitzian, non-convex problems is a significant theoretical contribution, providing a foundation for understanding local optimality.
- SSQP Framework: The proposed SSQP framework offers a systematic way to handle the non-smoothness and non-Lipschitzian nature by iteratively smoothing the objective and solving approximate convex QPs.
- Worst-Case Iteration Complexity Guarantee: This is a major breakthrough. The paper provides the first theoretical guarantee on the number of iterations required to find an $\epsilon$-KKT point, which is crucial for algorithm design and analysis.
- Flexibility in QP Solving: The framework allows for approximate solutions to the QP subproblems, with a specific "shrink projection gradient step" shown to be sufficient for achieving the desired complexity, making the algorithm more practical.
Key Results
- The paper proves that the composite $L_q$ minimization problem over a general polyhedron is strongly NP-hard.
- It derives KKT optimality conditions for local minimizers of this problem.
- A lower bound theory for local minimizers is established.
- The proposed SSQP framework is shown to return an $\epsilon$-KKT point within $O(\epsilon^{q-4})$ iterations. This is the first such guarantee for this class of problems.
- The framework is shown to be applicable to various related problems, including $L_1$ minimization and sparse recovery problems, as special cases.
Limitations and Future Work
- Theoretical Focus: The paper is primarily theoretical, focusing on complexity analysis and optimality conditions. While the framework is proposed, empirical performance on real-world problems is not demonstrated.
- Approximation of QP: While the framework allows for approximate QP solutions, the exact nature and efficiency of solving these QPs in practice are not deeply explored.
- Generalization: The authors suggest that the techniques can be generalized to problems with other non-Lipschitzian regularizers and to problems where the unknown variable is a positive semidefinite matrix. Future work could explore these generalizations and their practical implications.
- Comparison with Existing Methods: While a comparison with SQR algorithms is provided for specific cases, a broader empirical comparison with other state-of-the-art methods on benchmark problems would be valuable.
Summary updated