A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization | Laurent Condat et al. | ResearchPod

Transcript: A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization

Alex: Welcome to another episode of ResearchPod. Sam, what paper are we discussing today?

Sam: This is a paper by Laurent Condat, Abdurakhmon Sadiev, and Peter Richtárik, titled "A Nesterov-Accelerated Primal-Dual Splitting Algorithm for Convex Nonsmooth Optimization." It proposes a new method called APAPC to speed up solving certain optimization problems. These are math problems where you adjust variables to minimize a total cost made of smooth parts—like a gently curving hill—and nonsmooth parts, like sudden cliffs or flat penalties that kick in sharply.

Alex: So this is about finding the best settings in problems with tricky, uneven costs, like cleaning up noisy images where you balance fitting the data smoothly but penalizing weird artifacts harshly? And the core puzzle is how to make the solver run faster?

Sam: Yes, exactly—think image denoising, where one term matches the blurry input smoothly, but others enforce sharp edges without oversmoothing. Standard solvers alternate updates between the main "primal" variables you're optimizing and related "dual" variables that enforce constraints, like two teams tugging a rope to find balance. They converge steadily but slowly.

Alex: Right, so these primal-dual methods handle the mix of smooth and rough costs well, but adding speed boosts causes trouble?

Sam: Precisely. The boost they're after is Nesterov acceleration, which works great alone: instead of stumbling downhill step-by-step, it builds momentum by predicting ahead a bit, like a skier leaning into the next turn for quicker descent. But in primal-dual setups, the back-and-forth between primal and dual creates rotational wobbles in the solution path—like a spinning top instead of straight-line progress—causing divergence if you add that momentum naively. The paper exploits strong convexity in the dual side—basically, the dual problem's cost has a reliable upward bowl shape—to steady those rotations and achieve faster convergence, twice the speed asymptotically.

Alex: Huh. So the hook is stabilizing that spin to unlock the acceleration without crashing?

Sam: That's the crux. Their unified analysis tracks distances to the optimum and a measure called the Lagrangian gap—how far the current guesses are from perfect primal-dual balance—proving it all shrinks reliably under three cases of dual strength. This sets up real gains for tasks like signal processing or machine learning constraints.

Alex: Okay, so they've got this foundation from speeding up single-problem solvers. How do they actually weave that momentum into the primal-dual back-and-forth without the whole thing spinning out?

Sam: They start with a building block called Accelerated Proximal Gradient Descent, or APGD for short. It solves simpler problems by predicting a step ahead with momentum, then corrects aggressively but damps it back with a weighted average of past points—like a runner who lunges forward boldly but pulls back to a safe average speed to avoid overshooting. The key trick for the full problem is their new APAPC algorithm, which slots this predictor-corrector structure right into the primal-dual loop. On the primal side, it uses APGD-style momentum for the smooth part; the dual side's strong convexity—which means its cost landscape has a reliable upward curve, like a deep bowl that always pushes back toward center—acts as a stabilizer to dampen the rotations.

A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization

Laurent Condat, Abdurakhmon Sadiev, Peter Richtárik

Apr 10, 2026·10:09·arxiv·Original Paper

Nesterov AccelerationPrimal-Dual SplittingAPAPC AlgorithmOptimal Convergence RatesSaddle-Point Weak ConvergencePrimal-Dual Optimization

Listen

10 min

Summary

A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization

This paper by Laurent Condat, Abdurakhmon Sadiev, and Peter Richtárik introduces APAPC (Accelerated Proximal Alternating Predictor–Corrector), a breakthrough algorithm that brings Nesterov acceleration to primal-dual splitting methods for solving structured convex optimization problems. These problems, common in signal processing, machine learning, and inverse problems, take the form:

\min_x f(x) + g(x) + h(Kx)

Here, $f$ is smooth and convex (like a data fidelity term), $g$ and $h$ are nonsmooth convex (regularizers or indicators), and $K$ is a linear operator (e.g., blurring or subsampling matrix). Traditional primal-dual methods like PDHG or Condat-Vũ split the problem using proximal operators and gradients, but accelerating them—especially w.r.t. the smooth $f$ —is tricky due to 'rotational dynamics' in the primal-dual space that destabilize momentum.

## Nesterov Acceleration in Primal-Dual Context

Nesterov acceleration boosts first-order methods from $O(1/t)$ to $O(1/t^2)$ convergence by adding momentum: instead of stepping from the current point $x_t$ , you predict an extrapolated point $\tilde{x}_t = x_t + \beta (x_t - x_{t-1})$ and step from there. In proximal gradient ( $\min f + g$ ), this works beautifully. But in primal-dual settings with $h(Kx)$ , the coupling via $K$ and $K^*$ creates oscillations that break naive momentum. The paper's key insight: exploit dual strong convexity (induced by $g(x) = \frac{\mu_g}{2} \|x\|^2$ ) to stabilize accelerated primal updates, allowing seamless integration into a forward-backward primal-dual scheme.

## The APAPC Algorithm

APAPC is an accelerated version of the Proximal Alternating Predictor–Corrector (PAPC) method. It alternates primal and dual updates with prediction-correction steps and Nesterov momentum on the primal side:

Dual update: $\bar{u}^{k+1} = \mathrm{prox}_{\gamma h^*} (u^k - \gamma K \bar{x}^k)$
Primal prediction: Use momentum to extrapolate $\tilde{x}^{k+1} = x^k + \beta_k (x^k - x^{k-1})$
Primal correction: $x^{k+1} = \mathrm{prox}_{\gamma g} (\tilde{x}^{k+1} - \gamma (\nabla f(\tilde{x}^{k+1}) + K^* \bar{u}^{k+1}))$

Stepsizes $\gamma, \tau$ satisfy $\gamma \in (0, 2/L_f)$ and $\gamma \tau \|K\|^2 \le 1$ , offering larger ranges than competitors like Condat-Vũ (CV). This fully splits the problem: only needs $\nabla f$ , $\mathrm{prox}_g$ , $\mathrm{prox}_h$ (or $h^*$ ), $K$ , $K^*$ . When $K=I$ , it recovers accelerated three-operator splitting (TOS).

## Optimal Convergence via Lyapunov Analysis

Using a unified Lyapunov framework, the authors prove:

$O(1/t^2)$ sublinear rates for the primal objective gap and dual feasibility, optimal for smooth+nonsmooth composite problems.
Accelerated linear convergence ( $O((1 - \sqrt{\mu/L})^t)$ ) in three regimes of dual strong convexity: | Regime | Condition | Interpretation | |--------|-----------|----------------| | (i) Smooth $h$ | $h$ $L_h$ -smooth | $h^*$ strongly convex | | (ii) $K^*$ bounded below | $\mu_K > 0$ ( $\inf \|Kx\|/\|x\|>0$ ) | Full rank $K$ | | (iii) Linear constraints | $h = \iota_C$ (indicator) | Feasibility problems |

The Lyapunov function combines objective errors, squared distances to optima, and a novel correction term to handle momentum stability.

## Weak Convergence and Broader Impact

Primal-dual iterates $(x^k, u^k)$ converge weakly to a saddle-point $(x^*, u^*)$ satisfying KKT conditions $0 \in \nabla f(x^*) + \partial g(x^*) + K^* u^*$ , $0 \in \partial h^*(u^*) - K x^*$ . This leverages recent accelerated gradient descent results. The work generalizes PD3O/PDDY algorithms, improves stepsize flexibility over CV/PAPC, and characterizes primal-dual condition number scaling, with acceleration reducing dependence from linear to square-root. Applications span imaging (TV denoising), ML (structured SVMs), and control.

In sum, APAPC makes Nesterov acceleration practical for a wide class of nonsmooth problems, closing a long-standing gap in proximal splitting methods.

Abstract

We investigate the integration of Nesterov-type acceleration into primal-dual methods for structured convex optimization. While proximal splitting algorithms efficiently handle composite problems of the form $\min_x f(x)+g(x)+h(Kx)$, accelerating their convergence with respect to the smooth term $f$ is notoriously challenging due to the rotational dynamics in the primal-dual space. In this paper, we overcome this barrier by proposing the Accelerated Proximal Alternating Predictor-Corrector algorithm (APAPC), focusing on the setting where $g(x)=\frac{μ_g}{2}\|x\|^2$. Our analysis reveals that Nesterov momentum can be seamlessly integrated into a primal-dual forward-backward scheme by exploiting the strong convexity of the dual problem to stabilize the accelerated primal updates. Using a unified Lyapunov framework, we establish optimal $O(1/t^2)$ sublinear convergence rates, as well as accelerated linear convergence when $μ_g > 0$, across three regimes of dual strong convexity: (i) when $h$ is smooth, (ii) when the linear operator $K^*$ is bounded below, and (iii) for linearly constrained optimization. Furthermore, leveraging recent results on accelerated gradient descent, we characterize the weak convergence of the primal-dual iterates to a saddle-point solution.

A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization: Research Paper Podcast

A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization

Listen

A Nesterov-Accelerated Primal–Dual Splitting Algorithm for Convex Nonsmooth Optimization

## Nesterov Acceleration in Primal-Dual Context

## The APAPC Algorithm

## Optimal Convergence via Lyapunov Analysis

## Weak Convergence and Broader Impact