New Splitting Algorithms Tame Tricky Weakly Convex Optimization Problems

Optimization is the invisible engine behind modern science and technology, from training machine-learning models to reconstructing images from noisy signals. For decades, researchers have favored convex optimization problems, whose curved landscapes guarantee that any local minimum is also the global best answer. But real-world models increasingly demand objective functions that break convexity while retaining enough structure to be solvable. A new study published in Frontiers in Applied Mathematics and Statistics addresses precisely this middle ground, presenting two related algorithms for a class of problems known as weakly convex minimization, along with convergence guarantees that are notably more permissive than those previously available.

The work, authored by Shenghan Mei and Yifei Lou of the University of North Carolina at Chapel Hill and Chengyu Ke and Miju Ahn of Southern Methodist University, targets composite problems in which the objective is the sum of two parts: a smooth convex function, typically measuring how well a model fits the data, and a weakly convex term that may be non-smooth, usually encoding desired structure such as sparsity or robustness. Weak convexity is a relaxed notion: a function is weakly convex if adding a suitable quadratic term makes it convex. The smallest such curvature correction is called the weak convexity modulus, and it plays a central role throughout the new theory.

This seemingly modest relaxation covers an impressive range of practical models. Popular non-convex regularizers used in statistics and signal processing, including the smoothly clipped absolute deviation penalty, the minimax concave penalty, logarithmic regularization, and the transformed l1 penalty, all fall into the weakly convex category. Because these penalties can shrink small coefficients all the way to zero without the heavy bias of the classic l1 penalty, they are prized for feature selection in high-dimensional settings such as gene expression analysis and large-vocabulary text classification. Yet their non-convexity means standard convex toolboxes no longer apply, and researchers must carefully design algorithms whose behavior can still be guaranteed.

The team’s first contribution is to apply the alternating direction method of multipliers, or ADMM, to an unconstrained version of this composite problem. ADMM is a splitting technique with roots in the 1970s: it introduces an auxiliary variable to split the problem, then alternates between minimizing over each block while a dual variable enforces agreement between them. The elegance of the approach is that each subproblem can become convex even though the original problem is not. The authors prove a key proposition showing that if the penalty parameter rho is at least as large as the weak convexity modulus, both the non-smooth subproblem and the smooth subproblem are individually convex and therefore solvable by standard methods such as gradient descent or Newton’s method.

Why prefer ADMM over simpler first-order alternatives such as proximal gradient, majorization-minimization, or difference-of-convex algorithms? The authors point out that those methods take a single gradient step on the smooth term, with a step size capped by its Lipschitz constant, which can be conservative when that constant is large or hard to estimate. ADMM instead solves the smooth-term subproblem to high accuracy at each outer iteration, which in practice can produce faster progress. However, this accuracy comes at a price: the smooth subproblem often has no closed-form solution, forcing the algorithm to run an expensive inner iterative solver at every outer iteration, and these nested loops can dominate the total runtime.

To eliminate the bottleneck, the researchers developed a linearized ADMM variant, LADMM. The idea is to replace the smooth function in the subproblem with its first-order approximation, meaning a linearization around the current iterate. This preserves the splitting structure and leaves the other subproblem and dual update untouched, while turning the expensive subproblem into a single closed-form gradient step. The result is an algorithm with dramatically cheaper iterations. The trade-off is theoretical: linearization introduces a lagged-gradient effect, because the update relies on a gradient evaluated at the previous point rather than the current one, and this effect must be controlled carefully in any convergence proof.

The convergence analysis is where the paper makes its most distinctive technical contribution. Prior non-convex ADMM analyses, such as the influential work of Hong and colleagues, typically require the non-convex term to be differentiable with a Lipschitz-continuous gradient, an assumption that non-smooth weakly convex regularizers violate. Others rely on the Kurdyka-Lojasiewicz property or semi-algebraic structure. The new work instead develops a sufficient-decrease argument that directly leverages the weak convexity modulus, yielding explicit and verifiable parameter conditions: for ADMM, rho must exceed both the modulus and the Lipschitz constant of the smooth gradient, while LADMM needs the stronger condition rho larger than the maximum of the modulus and two expressions involving the Lipschitz constant. For LADMM, the authors also introduce a modified augmented Lagrangian, augmented with an auxiliary quadratic correction sequence that absorbs the lagged-gradient effect and restores a monotone decrease property.

With these tools, the team proves that both algorithms generate iterates with subsequences converging to directional stationary points of the original problem. A directional stationary point is one where the directional derivative of the objective is non-negative in every feasible direction, a notion often stronger than ordinary critical points in general non-convex optimization. A key structural insight of the paper is that for this weakly convex composite class, directional stationarity, critical-point stationarity, and Clarke stationarity all coincide, because the objective admits a difference-of-convex decomposition with a differentiable concave component. This equivalence means that proving convergence to one type of stationary point automatically secures the other two, giving the guarantees unusually broad scope for a non-smooth non-convex setting.

The theory was stress-tested in three numerical case studies, all run in MATLAB on a modest laptop. The first two involve classic low-dimensional benchmark functions, the Three-Hump Camel and the Six-Hump Camel, compared against gradient descent, heavy ball, and Nesterov’s accelerated gradient. LADMM was the fastest method in both tests: on the Three-Hump Camel it averaged 0.0086 seconds versus roughly 0.10 seconds for gradient descent, while ADMM, despite requiring nearly twice the total iterations of gradient descent owing to inner solves, still converged several times faster. Contour plots of the trajectories revealed why: ADMM’s alternating updates of two variables produce widely spaced early steps that descend more effectively than single-variable gradient methods, even when the total iteration count is higher.

The third and most consequential experiment tackled a high-dimensional sparse logistic regression model with logarithmic regularization, a weakly convex penalty well suited to classification tasks where features outnumber samples. Here the proposed methods competed against a majorization-minimization scheme, a proximal linearized ADMM, the proximal alternating linearized minimization method known as PALM, and a standard DC algorithm. Over 30 random instances, LADMM achieved the lowest average computation time at about 0.46 seconds, roughly 3.7 times faster than ADMM, while matching the best baselines in accuracy, precision, and recall, all around 0.97, and attaining the smallest proximal-gradient mapping residual, a measure of closeness to directional stationarity. A scaling study from 50 to 300 features showed LADMM’s advantage widening dramatically, with a majorization-minimization baseline needing nearly 670 seconds at the largest size versus half a second for LADMM.

The authors are candid about the limits of their results. The convergence guarantees are subsequential rather than full-sequence results, extending them would require additional assumptions such as the Kurdyka-Lojasiewicz property, and the theory assumes subproblems are solved exactly, leaving inexact updates as important future work. They also note that the theoretical lower bounds on the penalty parameter can be conservative in practice, since stable convergence was observed even below the threshold, and they call for adaptive strategies for tuning rho. One experimental variant that linearizes the weakly convex term itself is not yet covered by the analysis, another open thread. Even so, the combination of explicit, checkable parameter conditions, three coinciding notions of stationarity, and striking empirical speedups makes this framework a compelling blueprint for the next generation of algorithms operating in the vast, structured territory between convex and fully non-convex optimization.

Subject of Research: Alternating direction methods of multipliers for weakly convex composite optimization

Article Title: ADMM and linearized ADMM for weakly convex minimization

Article References: Mei, S., Ke, C., Lou, Y., & Ahn, M. (2026). ADMM and linearized ADMM for weakly convex minimization. Frontiers in Applied Mathematics and Statistics, 12, Article 1898659. https://doi.org/10.3389/fams.2026.1898659

Image Credits: AI Generated

DOI: 10.3389/fams.2026.1898659

Keywords: ADMM, linearized ADMM, weakly convex optimization, convergence analysis, directional stationary point, non-convex optimization, splitting methods, sparse logistic regression, regularization, nonsmooth optimization, machine learning, optimization algorithms