Iterative Reweighted Optimization for Non Smooth Objectives

121 concepts114 papers1 proposal

In machine learning and signal processing, we frequently encounter a frustrating trade-off between what we want to mathematically enforce and what we can computationally solve. We want true sparsity, which is ideally measured by the non-convex $\ell_0$ norm, but optimizing it directly is NP-hard. We want robustness to outliers, which leads us to non-smooth $\ell_1$ or $\ell_p$ norms, but their sharp corners break standard gradient descent.

The traditional escape hatch is convex relaxation—swapping the $\ell_0$ norm for an $\ell_1$ norm, or squaring an $\ell_1$ norm to make it smooth. However, this introduces significant estimation bias. Iterative Reweighted Optimization offers a more elegant way out. Instead of altering the problem to fit our solvers, it alters the solver to fit the problem. By approximating a difficult non-smooth or non-convex objective as a sequence of weighted, easily solvable subproblems, it allows us to optimize complex structures with the speed and stability of classical methods.

The Core Intuition: Local Surrogates via Duality

Why does iterative reweighting work? The core idea relies on the Majorization-Minimization (MM) framework. If an objective function is difficult to minimize directly, we can construct a simpler "surrogate" function that upper-bounds the true objective and touches it exactly at our current estimate. Minimizing this surrogate guarantees a step forward on the true objective.

In iterative reweighting, this surrogate is constructed by exploiting concave duality or local quadratic approximations. For instance, David P. Wipf et al. demonstrated that complex log-determinant terms in Automatic Relevance Determination can be expressed as a minimum over upper-bounding hyperplanes via concave duality. This mathematical transformation turns a daunting non-convex problem into a sequence of weighted $\ell_1$ problems (like the Lasso).

Similarly, Cuixia Gao et al. and Léa Laporte et al. leveraged MM frameworks to decompose highly non-convex penalties (such as exponential-type or minimax concave penalties) into manageable, weighted convex subproblems. By updating the weights at each step based on the gradient or supergradient of the original penalty, the algorithm smoothly guides the parameters toward a high-quality local or global optimum.

Driving Sparsity via Adaptive Penalization

To understand how this mechanism enforces sparsity more effectively than standard methods, consider the problem of recovering a sparse signal. A standard $\ell_1$ penalty applies the same weight to all coefficients, penalizing large, important signals just as heavily as small, noisy ones.

Iterative reweighting fixes this "punishment bias." In the framework proposed by Yves Wiaux for compressive imaging, the algorithm solves a sequence of weighted $\ell_1$ problems where the weights are inversely proportional to the magnitude of the coefficients from the previous iteration:

$$w_i^{(t+1)} = \frac{1}{|x_i^{(t)}| + \epsilon}$$

If a coefficient is large, its weight becomes tiny in the next round, allowing it to grow uninhibited. If a coefficient is small, its weight explodes, forcing it aggressively down to zero.

This adaptive feedback loop allows algorithms to approximate non-convex sparsity metrics with remarkable fidelity. For example, Daniel Strohmeier et al. utilized an iterative reweighting scheme to solve non-convex $\ell_{0.5}$-quasinorms for brain source reconstruction, eliminating the "ghost sources" that plague standard convex estimators. The same principle allows Pinghua Gong et al. to approximate the ideal $\ell_0$ norm via a multi-stage weighted convex framework, and enables the authors of Successive Concave Sparsity Approximation for Compressed Sensing to decompose concave sparsity objectives into stable linear programming subproblems.

From Least Squares to Robust and Structured Norms

The most famous incarnation of this idea is Iteratively Reweighted Least Squares (IRLS). The beauty of least squares ($\ell_2$ minimization) is that it has a closed-form analytical solution. IRLS exploits this by approximating non-smooth norms as a sequence of weighted quadratic problems.

For example, an $\ell_1$ norm $|x|$ can be rewritten as $\frac{x^2}{|x|}$. If we freeze the denominator $|x|$ using the estimate from the previous iteration, the problem becomes a weighted $\ell_2$ objective. Su-In Lee et al. combined this insight with Least Angle Regression to solve $\ell_1$-regularized logistic regression orders of magnitude faster than standard solvers. Alina Ene et al. extended this to general $\ell_p$ regressions, utilizing a primal-dual framework to achieve optimal iteration complexity while maintaining a simple implementation.

This quadratic approximation trick scales beautifully to structured and matrix-valued norms:

  • Joint and Structural Sparsity: Feiping Nie et al. applied iterative reweighting to solve joint $\ell_{2,1}$-norms for robust feature selection, bypassing complex interior-point methods. Deguang Kong et al. used a similar strategy to optimize exclusive group $\ell_{2,1}$-norms, transforming complex structural constraints into simple weighted least-squares tasks.
  • Low-Rank Matrix Recovery: Just as the $\ell_1$ norm is a relaxed proxy for vector sparsity, the nuclear norm is a proxy for matrix rank. Canyi Lu et al. introduced the Iteratively Reweighted Nuclear Norm (IRNN), which updates weights for singular values based on the supergradients of non-convex penalties, ensuring that large singular values preserve signal while small ones are pruned. Similarly, Edouard Grave et al. leveraged a variational representation of the trace norm to optimize the Trace Lasso via a series of computationally efficient weighted least-squares updates.

Integrating with Splitting and Linearization Frameworks

As optimization problems grow to massive scales or incorporate complex linear constraints, solving a full convex subproblem at every iteration can become a bottleneck. To address this, modern research integrates iterative reweighting directly into operator-splitting frameworks like the Alternating Direction Method of Multipliers (ADMM).

The key insight here is linearization. Instead of re-solving a complex subproblem from scratch, algorithms can linearize the smooth or outer components of a composite non-convex objective. Tao Sun et al. proposed an Iteratively Linearized Reweighted ADMM, which approximates the non-convex part linearly at each iteration. This ensures that each ADMM step remains a simple, weighted convex update while still guaranteeing convergence to a critical point.

In a similar vein, Aivar Sootla combined the Convex-Concave Procedure with iterative reweighting to break down non-convex network reconstruction problems into a distributed sequence of weighted Lasso problems, avoiding the memory walls of centralized optimization.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_iterative_reweighted_optimization_5c7a4a53,
  title = {iterative reweighted optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-reweighted-optimization/rdr_5c7a4a53f8c147e087b74fdab764afef},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_iterative_reweighted_optimization_5c7a4a53_v1,
  title = {iterative reweighted optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-reweighted-optimization/rdr_5c7a4a53f8c147e087b74fdab764afef/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake