Optimizing Non-Convex and Non-Smooth Sparsity Constraints

196 concepts181 papers1 proposal

Sparsity is a highly desirable property across machine learning, signal processing, and robotics. Whether the goal is to compress a massive neural network to run on an edge device, identify a handful of critical features in a high-dimensional genomic dataset, or design a robotic controller that minimizes actuator wear, the core objective remains the same: find a solution where as many parameters as possible are exactly zero.

However, enforcing sparsity introduces severe mathematical challenges. The ideal mathematical formulation relies on the $L_0$ "norm" (which counts the number of non-zero entries), but its discrete, non-convex, and non-smooth nature breaks standard optimization toolkits. To bypass this, researchers have historically relied on convex relaxations like the $L_1$ norm. While computationally convenient, these approximations often introduce unwanted bias or fail to yield truly sparse solutions in complex scenarios.

To achieve exact sparsity without combinatorial explosions, a prominent research direction focuses on non-convex sparsity optimization. By designing tighter non-convex relaxations and specialized optimization algorithms, researchers are learning how to navigate these treacherous mathematical landscapes effectively.


The Geometry of the Sparsity Dilemma

To understand why non-convex sparsity optimization is necessary, we must first look at why standard gradient-based optimization fails when confronted with true sparsity.

The ideal metric for sparsity is the $L_0$ pseudonorm. If you plot the $L_0$ error landscape for a single parameter, it resembles a step function: it is exactly zero when the parameter is zero, and exactly one everywhere else.

L0 Penalty
   ▲
 1 │ ─────────   ─────────
   │           │
   │           │
 0 ┼───────────■───────────► Parameter Value

As noted by Chang-Ti Huang et al. and Sulin Liu et al., the gradient of this function is zero almost everywhere. If an optimizer lands on any non-zero value, the gradient provides absolutely no information about which direction to move to reach zero. This makes direct $L_0$ optimization an NP-hard combinatorial problem.

The traditional workaround is the $L_1$ norm (Lasso), which replaces the step function with a V-shaped absolute value function. Because the $L_1$ norm is convex, it can be optimized globally. However, it introduces two major drawbacks:

  1. The "Kink" Problem: The $L_1$ norm is non-differentiable at exactly zero. As John Duchi points out, standard subgradient methods frequently overshoot or dance around this point of non-differentiability, resulting in parameters that are very small but not truly zero.
  2. Structural Mismatch: In many physical and structural systems, $L_1$ relaxations fail fundamentally. For example, in "hands-off" optimal control (where a controller should remain completely inactive for as long as possible), Masaaki Nagahara et al. demonstrated that $L_1$ relaxations fail to produce the required sparse, "bang-off-bang" behavior in singular control scenarios.

Bridging the Gap with Non-Convex Relaxations

If $L_1$ is too loose and $L_0$ is mathematically intractable, can we construct functions that sit between them? Non-convex sparsity optimization achieves this by dropping the requirement of global convexity to better mimic the geometry of $L_0$.

Ratios of Norms

One elegant approach is to use the ratio of the $\ell_1$ and $\ell_2$ norms ($\ell_1/\ell_2$), or its square, known as the $\tau_2$-model. As explored by Jianqing Jia et al., the ratio of norms acts as a scale-invariant sparsity promoter.

Intuitively, while the $\ell_1$ norm penalizes large values linearly, dividing by the $\ell_2$ norm ensures that the penalty flattens out for larger coefficients. This prevents the optimization from penalizing true, large underlying signals while aggressively pushing background noise to zero. The cost of this precision is a highly non-convex, fractional optimization landscape that standard solvers cannot handle directly.

Adaptive and Exponential Penalties

Another strategy involves using smooth, non-convex functions that dynamically alter their shape during optimization. Cuixia Gao introduced an Exponential-Type Penalty (ETP) that bridges the gap between $L_1$ and $L_0$. By adjusting an adaptive tuning parameter, the penalty can initially behave like a smooth $L_1$ function to find the right neighborhood of the solution, and then gradually sharpen into an $L_0$-like step function to enforce exact sparsity without introducing estimation bias.


Constructing a better non-convex penalty is only half the battle; we also need algorithms capable of finding global or high-quality local minima within these rugged landscapes. Modern frameworks rely on three core algorithmic mechanisms:

1. Homotopy Continuation

Homotopy methods avoid local minima by solving a sequence of gradually hardening optimization problems. Instead of tackling the non-convex $L_0$ objective directly, the algorithm begins by solving a simple, convex $L_1$ problem.

Once the convex solution is found, the algorithm smoothly deforms the objective function toward the true non-convex target. Mingkang Zhu et al. successfully paired this homotopy strategy with a nonmonotone Accelerated Proximal Gradient (nmAPG) method, allowing them to find highly sparse, imperceptible adversarial perturbations that completely baffle deep neural networks.

2. Support Projection and Hard Thresholding

Rather than waiting for a gradient to slowly push a parameter to zero, projection methods explicitly force sparsity by snapping parameters to zero based on their magnitude.

Continuous Value ──► [ Hard Thresholding / Support Projection ] ──► Exact Zero

Jiahui Yu demonstrated that by incorporating a "support projection" operator into proximal gradient descent, it is possible to achieve Nesterov’s optimal $O(1/k^2)$ convergence rate—a speed typically reserved for perfectly smooth, convex functions—even when optimizing the non-smooth, non-convex $\ell_0$ regularization problem. To scale this to massive datasets, Guannan Liang et al. combined hard thresholding with stochastically controlled variance reduction, decoupling the computational complexity from the total number of samples.

3. Smooth Reparameterization

A third, highly pragmatic approach is to change the coordinate system to smooth out the non-differentiable "kinks" entirely. A prominent example of this is the spred (Sparsity by Redundancy) framework.

Instead of optimizing a weight $w$ under an $L_1$ penalty, the authors reparameterize the weight as the product of two redundant variables ($w = u \cdot v$). This algebraic trick transforms the sharp, non-differentiable kink of the absolute value function into a smooth, differentiable landscape. This allows standard Stochastic Gradient Descent (SGD) to seamlessly converge to exact zero values, unlocking state-of-the-art neural network pruning without requiring specialized proximal solvers.


Applications and Impact

The ability to reliably optimize non-convex sparsity constraints has unlocked significant breakthroughs across diverse domains:

  • Adversarial Machine Learning: Real-world physical threats to AI systems are inherently sparse—such as a few dead pixels on a camera sensor or a small sticker on a stop sign. Xuyang Zhong et al. leveraged efficient non-convex sparse-PGD attacks to find these minimal, critical failure points. Because their method is computationally efficient, it can be integrated directly into adversarial training, yielding models with robust defense against real-world sparse attacks.
  • Robotics and Control: In complex humanoid robots or satellite systems, activating every joint or thruster continuously is highly inefficient. By embedding non-convex, sparsity-inducing penalties directly into the Differential Dynamic Programming framework, Traiko Dinev et al. enabled automated joint selection and realistic "on/off" thruster behaviors, allowing robots to discover energy-efficient trajectories naturally.

By moving beyond the limitations of convex approximations and developing algorithms tailored to non-smooth, non-convex geometries, researchers have turned what was once considered an intractable theoretical ideal into a highly practical toolkit for modern engineering.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_sparsity_optimization_e13b3ad8,
  title = {non-convex sparsity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-sparsity-optimization/rdr_e13b3ad843994ed1bf40358a8a332cef},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_convex_sparsity_optimization_e13b3ad8_v1,
  title = {non-convex sparsity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-sparsity-optimization/rdr_e13b3ad843994ed1bf40358a8a332cef/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake