🔢 mathematics

An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

This paper introduces iR2N, an inexact modified proximal quasi-Newton method for nonconvex regularized optimization that achieves global convergence with $O(\epsilon^{-2})$ complexity by allowing controlled inaccuracies in function, gradient, and proximal operator evaluations to significantly reduce computational effort.

Original authors: Nathan Allaire, Sébastien Le Digabel, Dominique Orban

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nathan Allaire, Sébastien Le Digabel, Dominique Orban

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley. This is the daily life of a computer scientist working in the field of optimization. Their job is to teach machines how to make the best possible decisions, whether that's finding the most efficient route for a delivery truck, reconstructing a blurry photo, or tuning the parameters of a complex biological model. The "valley" is a mathematical landscape where every location represents a possible solution, and the height represents how "good" or "bad" that solution is. The goal is to slide down to the very bottom.

Usually, these valleys are tricky. They aren't just smooth hills; they have jagged cliffs, sharp corners, and hidden traps. In math-speak, this means the functions describing the landscape are "nonsmooth" and sometimes "nonconvex" (meaning they have multiple local dips that look like the bottom but aren't). To navigate this, computers use special tools called proximal operators. Think of these as a magical compass that, when you are stuck on a jagged cliff, tells you exactly how to step onto the nearest flat ground. However, calculating the direction of this compass perfectly can be incredibly slow and expensive, like trying to measure the wind with a ruler made of diamond. Sometimes, the data itself is fuzzy or incomplete, like trying to map a coastline from a satellite image that is slightly out of focus. The big question in this corner of science is: Can we still find the bottom of the valley if we use a slightly blurry compass and accept some fuzzy measurements, without getting lost forever?

This paper introduces a new method called iR2N (Inexact Regularized Quasi-Newton), which is like giving the hiker a pair of smart, adaptive boots that know when to be precise and when to take a shortcut. The authors, Nathan Allaire, Sébastien Le Digabel, and Dominique Orban, propose that we don't always need to calculate the perfect step or the exact shape of the terrain. Instead, iR2N allows the computer to take "inexact" steps—approximations that are "good enough" for the moment.

The core idea is a balancing act. Imagine you are walking down a mountain in the dark. A traditional method insists on checking your exact position with a laser every single step, which takes forever. iR2N says, "Let's just estimate where the ground is, take a step, and if we feel like we're sliding the wrong way, we'll adjust." The method uses a "regularization" term, which acts like a safety tether, ensuring that even if the steps are rough, the hiker doesn't wander off into the abyss. The paper proves mathematically that even with these fuzzy steps and approximate measurements, the hiker will still eventually reach the bottom of the valley. In fact, they show that the time it takes to get there (the "complexity") is just as good as if they had used the perfect, expensive laser measurements all along.

The researchers didn't just dream this up; they built a working version of iR2N in a programming language called Julia and tested it on three different types of "mountains." First, they tried a problem called Basis Pursuit Denoising, which is like trying to clean up a noisy audio recording to find the original song. Second, they tackled Matrix Completion, similar to finishing a puzzle where many pieces are missing, like reconstructing a damaged image. Finally, they tested it on the FitzHugh-Nagumo inverse problem, which involves figuring out the hidden settings of a neuron's electrical activity based on observed data.

In these tests, they played with a "knob" called $\kappa_s$ (kappa-s), which controls how precise the steps must be. When they turned the knob to allow for lower precision (a small $\kappa_s$ ), the computer spent much less time calculating each individual step. However, this comes with a trade-off: because the steps are rougher, the algorithm often needs to take more total steps (outer iterations) to reach the bottom. Despite this increase in the number of steps, the total time to solve the problem often dropped significantly. For example, in the image reconstruction test, using lower-precision steps (small $\kappa_s$ ) cut the solution time from over 300 seconds down to about 94 seconds in some configurations, while still finding a solution that looked almost identical to the one found with perfect calculations. Even when the data itself was fuzzy (simulating real-world noise), the method adapted by becoming more precise only when it was stuck, saving massive amounts of time.

The paper explicitly rules out the idea that you must have perfect data to get a perfect result. They argue against the notion that inexactness inevitably leads to failure or getting stuck. Instead, they show that controlled inexactness is a feature, not a bug. However, they are careful to note that this works best when the "sloppiness" is managed correctly; if you are too sloppy for too long, the algorithm might stall. They also clarify that while their method is proven to work for a wide class of problems, finding a global minimum (the absolute lowest point) for certain non-convex shapes is still a hard problem that their method tackles with a "multi-start" strategy (trying from different places) rather than a guaranteed single-shot solution.

Ultimately, iR2N is a testament to the power of "good enough." It suggests that in the world of complex optimization, we can save significant computational effort and time by embracing approximation, provided we have a smart strategy to know when to be precise and when to let the math slide. The authors provide a free, open-source tool for anyone to try this out, proving that sometimes, the fastest way to the bottom of the valley is not to look down at your feet with a microscope, but to keep moving with a steady, adaptable stride.

Technical Summary: An Inexact Modified Quasi-Newton Method for Nonsmooth Regularized Optimization

Problem Statement
The paper addresses the nonsmooth regularized optimization problem:
$\min_{x \in \mathbb{R}^n} f(x) + h(x)$
where $f: \mathbb{R}^n \to \mathbb{R}$ is continuously differentiable (potentially nonconvex) and $h: \mathbb{R}^n \to \mathbb{R} \cup \{+\infty\}$ is proper, lower semi-continuous, and potentially nonconvex. The function $h$ acts as a regularizer to promote specific solution properties, such as sparsity.

The primary challenge addressed is the computational cost or infeasibility of obtaining exact evaluations of $f$ , its gradient $\nabla f$ , and the proximal operator of $h$ . Such inexactness arises in scenarios including:

Discretization of differential or integral operators.
Stochastic sampling in machine learning (sums of large numbers of terms).
Iterative procedures for evaluating proximal operators that lack closed-form solutions (e.g., $\ell_p$ -norm total variation, nonconvex $\ell_p$ -pseudo norm balls).
Multi-precision floating-point arithmetic.

Methodology: The iR2N Algorithm
The authors introduce iR2N (Inexact Regularized R2N), a modified proximal quasi-Newton method that extends the R2N algorithm of Diouane et al. [26] to handle inexact evaluations.

Core Mechanism: At each iteration, iR2N computes a step by approximately minimizing a model consisting of a quadratic approximation of $f$ , a model of $h$ , and an adaptive quadratic regularization term.
Inexactness Handling:
- Objective and Gradient: The algorithm utilizes approximations $\tilde{f}$ and $\tilde{\nabla}f$ . The error bounds are assumed to scale with the step size (specifically, $|f(x) - \tilde{f}(x)| \leq \kappa_f \|s\|^2$ and $\|\nabla f(x) - \tilde{\nabla}f(x)\| \leq \kappa_\nabla \|s\|$ ).
- Proximal Operator: The subproblem involves a proximal operator that is evaluated inexactly. The method employs a variant of the proximal-gradient method (called iR2) to solve the subproblem. Crucially, the iterative process for the proximal operator can be terminated early.
Stopping Criterion for Proximal Steps: A key innovation is the stopping condition for the inner proximal solver. Instead of requiring convergence to a global minimizer, the process stops when the norm of the current iterate $\|\tilde{s}_{k,cp}\|$ exceeds a fraction $\kappa_s$ of an upper bound $M_k$ on the norm of the exact Cauchy step. This condition is weaker than standard requirements in the literature (e.g., Rockafellar's summable error criteria) but sufficient for convergence.
Acceptance Criteria: The algorithm uses a ratio of achieved to predicted decrease (based on inexact evaluations) to accept or reject steps, updating a regularization parameter $\sigma_k$ dynamically.

Key Contributions

Algorithm Design: The formulation of iR2N, which integrates inexact evaluations of the objective, gradient, and proximal operators within a modified quasi-Newton framework.
Convergence Analysis:
- Global Convergence: Under standard assumptions (Lipschitz continuity of $\nabla f$ , boundedness of the Hessian approximation, and specific inexactness conditions), the authors prove that a first-order stationarity measure converges to zero.
- Complexity: The paper establishes a worst-case evaluation complexity of $O(\epsilon^{-2})$ to reduce the stationarity measure below $\epsilon > 0$ . This matches the complexity of the exact R2N method, demonstrating that inexact evaluations do not degrade the asymptotic worst-case performance.
Practical Implementation of Inexactness: The authors provide specific theoretical bounds on the norm of the exact Cauchy step for three challenging regularizers:
- $\ell_p$ -norm ( $1 \leq p < \infty$ ).
- $\ell_p$ -total variation ( $1 \leq p < \infty$ ).
- Indicator of the nonconvex $\ell_p$ -pseudo norm ball ( $0 < p < 1$ ).
  These bounds allow for the construction of effective early-stopping conditions for the inner iterative solvers.
Software: An efficient implementation in Julia, integrated into the open-source package RegularizedOptimization.jl.

Results
Numerical experiments were conducted on three problem classes:

Basis Pursuit Denoising (BPDN): Using an $\ell_p$ -norm regularizer.
Matrix Completion: Using an $\ell_p$ -total variation regularizer.
FitzHugh-Nagumo Inverse Problem: Using a nonconvex $\ell_p$ -pseudo norm ball indicator.

The experiments varied the inexactness parameter $\kappa_s$ (controlling the quality of the proximal step) and, in one case, the accuracy of the objective/gradient evaluations (via ODE solver tolerances).

Performance: For small values of $\kappa_s$ (allowing coarser proximal steps), the method significantly reduced the computational time per iteration. While this sometimes increased the number of outer iterations slightly, the net result was a substantial reduction in total CPU time compared to "exact mode" (where proximal operators are solved to high precision).
Robustness: The solutions obtained in inexact mode were found to be essentially identical to those in exact mode, successfully recovering sparse supports and reconstructing signals.
Inexact Gradients: When applied to the FitzHugh-Nagumo problem with inexact gradients (controlled by an adaptive tolerance scheme), the method maintained convergence and achieved significant time savings, provided the accuracy was increased sufficiently on unsuccessful iterations.

Significance and Claims
The paper claims that iR2N offers great flexibility in optimization scenarios where exact evaluations are either too costly or unavailable. The primary significance lies in demonstrating that controlled inexactness can be exploited to reduce computational effort significantly without compromising the theoretical convergence guarantees or the worst-case complexity order.

The authors emphasize that their approach allows for the use of iterative procedures for proximal operators that can be stopped early, a feature particularly valuable for nonconvex regularizers (like the $\ell_p$ -pseudo norm ball) where global minimization of the proximal subproblem is difficult or impossible. The work bridges the gap between theoretical complexity analysis and practical computational efficiency in nonsmooth, nonconvex optimization.

More like this