Source-linked AI summary
Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms
Amir Beck, Yonina C. Eldar
TL;DR
The paper studies minimizing general continuously differentiable, possibly nonconvex objectives under sparsity constraints, where standard optimality theory does not directly apply. It derives feasibility, stationarity, and coordinate-wise conditions, then develops three algorithms whose convergence and guarantees are analyzed. The methods provide convergent approaches to points satisfying the corresponding necessary optimality conditions, with sparse-simplex methods offering stronger guarantees but higher per-iteration cost.
Problem
The paper addresses optimality and algorithmic difficulties caused by minimizing a possibly nonconvex differentiable function under a nonconvex, discontinuous ℓ0 sparsity constraint.
Method
It derives basic feasibility, L-stationarity, and coordinate-wise optimality conditions and develops iterative hard thresholding plus greedy and partial sparse-simplex algorithms.
Results
The algorithms converge so that their limit points satisfy the corresponding necessary optimality conditions, with sparse-simplex methods targeting stronger coordinate-wise optimality.
Takeaways & Limitations
The paper provides a uniform framework for analyzing and solving sparsity-constrained optimization across general differentiable objectives and sparse-recovery models.
Takeaways & Limitations
The greedy sparse-simplex method can require O(s · n) one-dimensional minimization procedures per iteration, while IHT requires a Lipschitz-gradient assumption and knowledge of its constant.
Abstract
from arXiv · showhide
This paper treats the problem of minimizing a general continuously differentiable function subject to sparsity constraints. We present and analyze several different optimality criteria which are based on the notions of stationarity and coordinate-wise optimality. These conditions are then used to derive three numerical algorithms aimed at finding points satisfying the resulting optimality criteria: the iterative hard thresholding method and the greedy and partial sparse-simplex methods. The first algorithm is essentially a gradient projection method while the remaining two algorithms are of coordinate descent type. The theoretical convergence of these methods and their relations to the derived optimality conditions are studied. The algorithms and results are illustrated by several numerical examples.
1 Introduction
The paper formulates sparsity-constrained minimization for general continuously differentiable, possibly nonconvex objectives and develops optimality conditions and algorithms for this setting. It presents a uniform framework motivated by sparse recovery problems from linear and quadratic measurements.
- The central problem minimizes a continuously differentiable function subject to an ℓ0 sparsity constraint, without assuming convexity.The ℓ0 norm counts nonzero components, while the constraint is nonconvex and discontinuous.
- The motivating applications include compressive sensing, sparse recovery from quadratic measurements, and phase retrieval.These settings involve recovering sparse vectors or images from linear, quadratic, or Fourier-magnitude measurements.
- Existing approaches include convex ℓ1 relaxations, greedy pursuit methods, semidefinite relaxation, and alternating projections, with scalability or inner-solver limitations noted for some methods.
- Classical nonconvex optimality results do not cover sparsity constraints because they are neither convex nor continuous.
- The framework derives basic feasibility, L-stationarity, and coordinate-wise optimality conditions for the general problem.It also establishes implications between these conditions, including that stronger coordinate-wise conditions imply L-stationarity and basic feasibility.
- The paper develops iterative hard thresholding and sparse-simplex algorithms, then studies their convergence and relationships to the derived optimality conditions.
2 Necessary Optimality Conditions
The paper develops necessary optimality conditions for differentiable optimization over nonconvex, discontinuous sparsity constraints. It shows how basic feasibility, L-stationarity, and coordinate-wise optimality relate, including stronger conditions and finite-candidate results under additional assumptions.
- Basic Feasibility: Basic feasibility requires zero partial derivatives on the support of a feasible point and is necessary for every optimal solution.The condition is weak because many basic feasible vectors need not be optimal.
- Special Case: For least-squares objectives with an s-regular matrix, the number of basic feasible points is finite.Thus, only finitely many points are suspected to be optimal solutions in this setting.
- L-Stationarity: Under a Lipschitz-gradient assumption, every optimal solution is L-stationary for any L > L(f), and L-stationarity implies basic feasibility.The condition becomes more restrictive as L decreases and depends on the chosen parameter.
- L-Stationarity: L-stationarity requires Lipschitz continuity of the gradient and knowledge of a Lipschitz bound, motivating a stronger condition without these requirements.The paper introduces coordinate-wise optimality as an alternative necessary condition.
- Coordinate-Wise Minima: Every optimal solution is a CW-minimum, and every CW-minimum is a basic feasible vector.Under Assumption 2, CW-minima are also stationary at a level no greater than L(f).
- Coordinate-Wise Minima: In the numerical example, only x3, x6, and x8 satisfy the relevant 6-stationarity threshold, while x6 is the only CW-minimum and global optimum.The example also notes that CW-minima need not always be globally optimal.
3 Numerical Algorithms
The paper develops three algorithms for sparse-constrained optimization: IHT, greedy sparse-simplex, and partial sparse-simplex methods. They target stationarity or coordinate-wise optimality, with convergence guarantees under stated assumptions.
- The proposed algorithms are iterative hard thresholding, greedy sparse-simplex, and partial sparse-simplex methods.They are designed to achieve necessary optimality conditions developed earlier.
- IHT generalizes iterative hard thresholding to general objectives under Assumption 2 and targets L-stationary points.The method coincides with the established IHT method for f ≡ fLI under ∥A∥2 < 1.
- The greedy sparse-simplex method is a coordinate descent algorithm that optimizes one or two variables producing the largest objective decrease.Its support changes by at most one index.
- The greedy sparse-simplex method has limit points that are CW-minima, a stronger condition than L-stationarity for L ≥ L2(f).It does not require Assumption 2 or knowledge of the Lipschitz constant, but exhaustive index exploration can be costly.
- The partial sparse-simplex method avoids exhaustive index search through a simple selection rule and is guaranteed under Assumption 2 to converge to L2(f)-stationary points.
3.1 The IHT Method
The IHT method enforces L-stationarity through a fixed-point or gradient-projection-style iteration. Its function values converge, and its accumulation points are L-stationary under L > L(f), although larger L can admit non-optimal stationary points.
- The IHT method uses a fixed-point iteration to enforce the L-stationarity condition.Its general step is equivalent to an hL-based relation.
- The IHT convergence theory relies on Assumption 2 and requires knowledge of the Lipschitz constant L(f).
- With constant stepsize 1/L and L > L(f), IHT generates a nonincreasing sequence of function values, strictly decreasing whenever an iterate changes.
- Every accumulation point of IHT is L-stationary when the constant stepsize is 1/L with L > L(f).
- For f ≡ fLI and an s-regular matrix A, the entire IHT sequence converges to an L-stationary point.This strengthens the general accumulation-point result for the least-squares case.
- Increasing L from 250 to 500 increases the chance that IHT converges to the non-optimal L-stationary point.
- In a quadratic example, L ∈ [L(f),196) guarantees convergence to the global optimum, whereas L ≥ 196 permits convergence to a non-optimal L-stationary point.The non-optimal point is (−1/12, 0)T, while the optimum is (0, −9/16)T.
- Another example shows that, regardless of L, IHT can converge to a non-optimal solution.
3.2 The Greedy Sparse-Simplex Method
The greedy sparse-simplex method selects coordinates producing the largest objective decrease and performs one-dimensional minimizations, yielding strong convergence guarantees. Its limit points are CW-minima, and under Assumption 2 they are also L2(f)-stationary, though exhaustive coordinate searches increase per-iteration cost.
- Unlike IHT, the method does not require Assumption 2 or knowledge of a Lipschitz constant, while retaining stronger limit-point optimality conditions.When Assumption 2 holds, its limit points satisfy L2(f)-stationarity without requiring Lipschitz-constant information.
- The greedy sparse-simplex method generates a non-increasing sequence of objective values and stops only at CW-minima.Equality between consecutive objective values occurs only when the iterate is unchanged and is a CW-minimum.
- Every accumulation point of the generated sequence is a CW-minimum of (P).Under Assumption 2, every accumulation point is consequently L2(f)-stationary.
- The method can correct support choices and continue updating values after the support stabilizes, ultimately converging to the least-squares solution on the final support.This correction mechanism distinguishes it from matching pursuit, which does not remove selected support elements under comparably broad conditions.
- In the sparse least-squares example, the method converged to the true optimal solution with more than 80% probability and avoided BF vectors that were not L2(f)-stationary.Across 1000 random starts, only three of ten BF vectors were possible greedy-method limit points because only three were CW-minima.
3.3 The Partial Sparse-Simplex Method
The partial sparse-simplex method simplifies index selection relative to the greedy method by considering a limited set of coordinate updates. Its limit points are L2(f)-stationary under Assumption 2, but need not be CW-minima.
- The partial sparse-simplex method avoids exhaustive index searches through a simple selection rule for coordinate updates.At full support, it compares the best supported-coordinate decrease with replacing the smallest-magnitude support variable using a large-gradient nonsupport variable.
- The method generates a non-increasing sequence of function values, and every accumulation point is a basic feasible vector.It coincides with the greedy sparse-simplex method whenever the current support has fewer than s elements.
- Under Assumption 2, every accumulation point of the partial sparse-simplex method is L2(f)-stationary.This guarantee is stronger than the stationarity result stated for IHT, but it does not imply CW-minimality.
- The partial method can improve its success probability by using multiple initial vectors and selecting the result with the best objective value.In the sparse least-squares comparison, it performed much better than either IHT setting but was slightly inferior to the greedy method.
- In the quadratic-equations experiment, greedy sparse-simplex outperformed partial sparse-simplex in success probability, while both methods were tested across sparsity levels s = 3, 4, . . . , 10.The experiments used 100 random initial vectors for each sparsity level.
4 Proofs of Convergence Theorems
The convergence proofs show that accumulation points of the algorithm-generated sequences satisfy increasingly strong stationarity or coordinate-wise optimality conditions. Under the stated assumptions, boundedness and finiteness arguments further support convergence of the full sequence for the iterative hard thresholding method.
- Proof strategy: The convergence arguments rely on nonincreasing, lower-bounded function values and continuity to pass limiting inequalities to accumulation points.These properties make the successive decrease vanish and permit the stationarity or coordinate-wise conditions to hold at the limit.
- Iterative hard thresholding: Accumulation points of the iterative hard thresholding sequence are L-stationary and therefore also BF vectors.The proof first establishes boundedness, then extracts a convergent subsequence whose accumulation point satisfies the stationarity condition.
- Iterative hard thresholding: Finiteness of BF vectors provides a positive separation distance used to prove convergence of the entire iterative hard thresholding sequence.The argument rules out persistent departures from the selected accumulation point.
- Greedy sparse-simplex method: Every accumulation point of the greedy sparse-simplex sequence is a CW-minimum, including cases where its support has size s or less than s.The proof treats active and inactive coordinates separately and uses the method's coordinate updates to establish coordinate-wise optimality.
- Partial sparse-simplex method: For the partial sparse-simplex method, active coordinates at an accumulation point satisfy one-dimensional optimality, implying zero partial derivatives on those coordinates.The proof identifies 0 as a minimizer of the corresponding coordinate-restricted function.
- Sparse-simplex convergence: Under Assumption 2, the sparse-simplex method yields full stationarity when accumulation points have support smaller than s.Lemma 4.1 supplies the bound needed to show that the gradient converges to zero in the under-saturated-support case.