🔢 mathematics

Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions

This paper introduces MELMO, a Moreau envelope smoothing algorithm utilizing linear minimization oracles that achieves explicit convergence trade-offs and establishes $O(k^{-1/3})$ rates for composite stationarity in weakly convex optimization problems with non-Euclidean structures.

Original authors: Farid Najar

Published 2026-08-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Farid Najar

Original paper licensed under CC BY 4.0 (https://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

The Art of Smooth Sailing on Rocky Terrain

Imagine you are trying to find the lowest point in a vast, foggy landscape. In the world of computer science and machine learning, this "landscape" is a mathematical map of a problem, and the "lowest point" is the perfect solution. Usually, these maps are smooth hills and valleys, making it easy for computers to slide down to the bottom. But sometimes, the terrain is jagged and full of sharp cliffs—these are "non-smooth" problems. They are incredibly useful for things like cleaning up blurry photos or finding hidden patterns in data, but they are a nightmare for standard algorithms because they can't slide down a cliff; they just get stuck or bounce off.

To solve this, mathematicians have developed a trick called "smoothing." Think of it like pouring a thick layer of soft foam over the jagged rocks. The foam makes the surface smooth enough for a computer to slide down, but the foam is just a temporary helper. The real goal is to reach the bottom of the original rocky terrain, not just the bottom of the foam. The challenge is figuring out how thick the foam should be: too thick, and you're sliding on a fake hill that doesn't lead to the real solution; too thin, and the computer can't slide at all. This paper dives into how to manage that foam and, more importantly, how to steer the computer when the ground isn't flat and round like a ball, but has strange, specific shapes like a diamond or a star.

The Paper's Big Idea: MELMO

The researcher, Farid Najar, introduces a new algorithm they call MELMO (Moreau Envelope Smoothing with Linear Minimization Oracles). If that sounds like a mouthful, think of it as a smart, adaptable hiker who knows how to use a temporary ramp (the foam) to get down a mountain, but also knows how to change their walking style depending on the shape of the ground beneath their feet.

Most computer programs assume the ground is "Euclidean," which is a fancy way of saying it's like a flat, round ball where the shortest path is a straight line. But in many modern problems, like organizing a massive library of images or compressing data, the ground is actually shaped like a diamond or a star. If you try to walk in a straight line on a diamond-shaped field, you might miss the best spots entirely. MELMO is special because it uses a "Linear Minimization Oracle" (LMO). Imagine the LMO as a magical compass that doesn't just point "down," but points in the best possible direction for the specific shape of the ground you are standing on. It allows the algorithm to take steps that respect the unique geometry of the problem, whether that means finding a sparse solution (one with many zeros) or a low-rank solution (one that is simple and compact).

The paper proves that MELMO works by carefully balancing two things: how fast the "foam" (the smoothing) disappears and how big the steps the computer takes are. The author shows that if you tune these two knobs just right, the algorithm can find a good solution surprisingly fast. They found two main "modes" for tuning:

The Balanced Mode: This is a steady, reliable pace. It guarantees that the computer gets closer to the solution at a rate of $O(k^{-1/4})$ (meaning the error shrinks as the number of steps $k$ increases).
The Aggressive Mode: This mode focuses on smoothing the path quickly. It gets to a smooth solution even faster ( $O(k^{-1/3})$ ), but the final check on the original rocky terrain is slightly slower ( $O(k^{-1/4})$ ).

The researcher also created a "checkpoint" system. Instead of just guessing when to stop, MELMO can calculate a specific certificate that says, "We are now within a certain distance of the perfect answer." They proved that with a specific restart strategy, the algorithm can find this certificate in $O(\epsilon^{-3})$ steps, which matches the state-of-the-art bound for this specific type of certificate complexity derived in the paper.

What the Experiments Showed

To see if MELMO actually works in the real world, the team tested it on three different tasks:

Sparse Low-Rank Matrix Factorization: This is like trying to reconstruct a giant puzzle where some pieces are missing, but you know the final picture should be simple and have many blank spaces. MELMO was tested on five different datasets. The results showed that the "Balanced Mode" was very competitive, often beating standard methods on datasets like "Camera" and "Football." However, on the "Olivetti" dataset, the "Aggressive Mode" stumbled, suggesting that moving too fast can sometimes make the algorithm lose its way on certain types of terrain.
Image Denoising: Here, they tried to clean up a noisy photo. They found that MELMO could produce clearer images than older methods, especially when using a specific geometric "compass" (the spectral norm). Interestingly, a version of MELMO that restarted its journey periodically (the "epoch-wise" version) was better at staying true to the original problem's details.
Masked Matrix Recovery: This was a test where the algorithm had to guess missing numbers in a grid. This experiment was crucial because it perfectly matched the mathematical rules the theory was built on. Here, MELMO with a "spectral" compass (which looks at the overall shape of the data) was faster at finding the solution in the early stages than any other method.

The Verdict

The paper doesn't claim that MELMO is a magic wand that solves every problem instantly. In fact, the author is careful to point out that the "Aggressive Mode" can fail if the problem is tricky, as seen in the Olivetti dataset results. They also note that while the theory is strongest for certain types of problems, the method still works well in practice even when the strict mathematical conditions aren't perfectly met (like in the image denoising test).

Ultimately, MELMO suggests that by combining a smart smoothing technique with a geometry-aware compass, we can solve complex, jagged optimization problems more efficiently than before. It doesn't just slide down the hill; it knows exactly how to walk on the specific shape of the hill to get to the bottom faster and more accurately. For anyone building machine learning models that need to find patterns in messy, high-dimensional data, this approach offers a promising new way to navigate the terrain.

Technical Summary: Variable Smoothing for Weakly Convex Problems with Non-Euclidean Directions

Problem Statement

The paper addresses the composite minimization problem:
$\min_{x \in \mathbb{R}^n} F(x) = f(x) + g(Tx)$
where:

$f \in C^{1,1}(\mathbb{R}^n)$ is a Lipschitz-smooth function (data fidelity).
$g: \mathbb{R}^m \to \mathbb{R}$ is a Lipschitz-continuous, $\rho$ -weakly convex function that may be non-smooth (regularizer).
$T: \mathbb{R}^n \to \mathbb{R}^m$ is a linear operator.

This class of problems arises frequently in machine learning and signal processing, including LASSO variants with non-convex penalties (MCP, SCAD), low-rank matrix recovery, total variation denoising, and robust statistical estimation. The primary challenge lies in optimizing objectives where the non-smooth component $g$ is also non-convex, rendering standard convex optimization techniques inapplicable. Furthermore, the author argues that standard Euclidean geometry often fails to capture the specific structural biases (e.g., sparsity, low-rankness) required in modern applications, necessitating methods that adapt to non-Euclidean geometries.

Methodology: MELMO

The author proposes MELMO (Moreau Envelope Smoothing with Linear Minimization Oracles), an algorithm that integrates two key components:

Moreau Envelope Smoothing: To handle the non-smooth and weakly convex component $g$ , MELMO replaces $g$ with its Moreau envelope $g_\beta$ . For a smoothing parameter $\beta > 0$ , $g_\beta$ is continuously differentiable with a Lipschitz gradient, provided $\beta \leq 1/(2\rho)$ (for $\rho > 0$ ). This transforms the original non-smooth problem into a sequence of smooth surrogate problems.
Linear Minimization Oracles (LMOs): Instead of using standard Euclidean gradient steps, MELMO utilizes an LMO to determine the update direction. Given a gradient vector, the LMO solves a linear minimization problem over the unit ball of a chosen norm $\|\cdot\|$ . This allows the algorithm to adapt to problem-specific geometries (e.g., spectral norm for low-rank matrices, $\ell_1$ norm for sparsity) without requiring projection onto constraint sets.

The update rule at iteration $k$ is:
$x_{k+1} = x_k + \gamma_k \cdot \text{LMO}(\nabla F_{\beta_k}(x_k))$
where $\gamma_k$ is the step size and $\beta_k$ is the smoothing parameter. The algorithm supports $\delta$ -inexact LMOs, accommodating cases where the exact oracle is computationally expensive (e.g., approximating the spectral norm LMO via Newton-Schulz iterations).

Key Contributions

1. Theoretical Convergence Analysis

The paper establishes a family of convergence bounds parameterized by the step-size schedule ( $\gamma_k \propto k^{-p}$ ) and the smoothing schedule ( $\beta_k \propto k^{-q}$ ). The analysis explicitly characterizes the trade-off between optimizing the smoothed surrogate and recovering stationarity for the original composite problem.

Balanced Regime: With $(p, q) = (7/12, 1/3)$ , the method achieves an $O(k^{-1/4})$ rate for both the smoothed-gradient norm and a composite stationarity proxy.
Smoothed-Gradient-Favoring Regime: With $(p, q) = (2/3, 1/4)$ , the smoothed-gradient norm converges at $O(k^{-1/3})$ , while the composite proxy remains at $O(k^{-1/4})$ .
Horizon-Dependent Rate: If the horizon $K$ is known, constant schedules yield an $O(K^{-1/3})$ rate for the composite proxy.

2. Epoch-wise Certification

To address the issue where the minimum gradient norm and the minimum proximal gap might occur at different iterations, the author introduces an Epoch-wise MELMO variant. This version tracks the best iterate within epochs and restarts from a point with a non-worsening objective value.

Using power schedules, this variant provides computable $\epsilon$ -proxy certificates with $O(\epsilon^{-4})$ complexity.
Using epoch-constant schedules with restarts, the complexity improves to the state-of-the-art $O(\epsilon^{-3})$ .
Under the assumption that $T$ is surjective, these certificates translate to near-stationarity for the original problem.

3. Empirical Evaluation

The method is evaluated on three tasks:

Sparse Low-Rank Matrix Factorization: Using the spectral norm geometry (via Muon-style updates).
Total Variation Image Denoising: Comparing spectral, $\ell_2$ , and nuclear norm geometries.
Masked Matrix Recovery: A problem satisfying all theoretical assumptions (globally Lipschitz gradient, surjective $T$ ).

Results

Theoretical Findings

The analysis confirms that MELMO unifies variable smoothing techniques with non-Euclidean optimization. The derived rates demonstrate that one can tune the schedules to prioritize either the smoothness of the surrogate or the fidelity to the original non-smooth objective. The epoch-wise variant successfully converts asymptotic guarantees into explicit, computable stopping criteria.

Experimental Findings

Matrix Factorization: The balanced schedule $(7/12, 1/3)$ generally outperformed Euclidean baselines (variable smoothing and subgradient methods) on four of five datasets (Camera, Football, Synthetic, Spectrometer at lower ranks). However, the more aggressive schedule $(2/3, 1/4)$ showed instability on the Olivetti dataset, resulting in significantly higher objective values.
Denoising: In image denoising, all MELMO geometries (spectral, $\ell_2$ , nuclear) outperformed the subgradient baseline in terms of SSIM. The $\ell_2$ geometry performed best, followed by spectral (comparable to variable smoothing), with nuclear being the weakest. The epoch-wise variant demonstrated faster reduction in the proximal gap (fidelity term) compared to the regular variant.
Masked Matrix Recovery: MELMO variants, particularly those using the spectral LMO, reduced the objective value faster in early iterations compared to baselines. The $\ell_2$ -LMO variant achieved the lowest final penalized objective. The subgradient method consistently underperformed across metrics. Notably, MELMO does not require prior knowledge of the gradient Lipschitz constant $L_{\nabla f}$ for step-size selection, unlike some baselines.

Significance and Claims

The paper claims to fill a gap in the optimization landscape by combining Moreau envelope smoothing for weakly convex composite problems with geometry-aware updates via LMOs.

Unification: It bridges the gap between variable smoothing methods (typically Euclidean) and conditional gradient methods (typically constrained).
Practicality: The method offers a flexible framework where the choice of geometry (norm) directly influences the structural properties of the solution (e.g., sparsity or low-rankness).
Robustness: While theoretical guarantees are strongest under surjective $T$ and globally Lipschitz gradients, the author notes that the method performs competitively even in settings where these strict assumptions do not fully hold (e.g., image denoising), suggesting practical robustness beyond the theoretical bounds.
Limitations: The author modestly notes that while the balanced schedule is generally robust, aggressive schedules can lead to instability on specific datasets. Furthermore, the denoising experiments are presented as empirical extensions where the strongest theoretical guarantees (regarding surjectivity) do not strictly apply.

The work concludes by suggesting that extending this framework to stochastic settings is a natural direction for future research to broaden applicability to large-scale machine learning.