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

This paper proposes the Accelerated Proximal Alternating Predictor-Corrector (APAPC) algorithm, which successfully integrates Nesterov acceleration into primal-dual splitting for convex nonsmooth optimization by leveraging dual strong convexity to achieve optimal $O(1/t^2)$ sublinear and accelerated linear convergence rates while ensuring weak convergence to a saddle-point solution.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy valley (the Optimization Problem). This valley isn't just a simple bowl; it has three distinct features:

1. A smooth, rolling hillside you can feel with your feet (Function $f$).
2. A patch of thick, sticky mud that makes it hard to move unless you follow a specific path (Function $g$).
3. A series of invisible fences or walls that you must not cross, which are defined by a complex map (Function $h$ and Operator $K$).

Your goal is to find the absolute bottom of this valley as quickly as possible.

The Old Way: The Careful Hiker

For years, the standard method to solve this was like a careful hiker. Every step, the hiker looks at the slope, takes a small step down, checks the mud, and checks the fences.

• The Problem: This is safe, but it's slow. If the valley is huge, the hiker takes thousands of tiny steps.
• The "Nesterov" Idea: In the 1980s, a mathematician named Nesterov suggested a trick: Momentum. Instead of just looking at where you are, look where you were and where you are going. If you are running downhill, don't stop to check your footing at every single step; keep your momentum going, but be smart about it. This is like a skier who leans into a turn to pick up speed.

The Challenge: The "Spinning" Valley

The paper authors explain that while this "skier" trick works great on simple hills, it becomes a nightmare in a Primal-Dual setting (where you are navigating both the terrain and the invisible fences simultaneously).

Imagine the valley is actually a spinning carousel.

• If you try to run fast (add momentum) on a spinning carousel, you get dizzy. You might spin out of control, overshoot the bottom, and crash into the fences.
• Previous attempts to add "Nesterov momentum" to these complex problems often failed because the "spin" (the interaction between the terrain and the fences) made the algorithm unstable. It would oscillate wildly and never settle.

The Solution: The "APAPC" Algorithm

The authors introduce a new algorithm called APAPC (Accelerated Proximal Alternating Predictor–Corrector). Think of this as a Smart Ski Team with a unique strategy.

Here is how they make the "skier" work on the "spinning carousel":

1. The Predictor (The Scout)

Before the main team moves, a Scout runs ahead to guess the best path.

• In the paper: This is the "Predictor" step. The algorithm guesses where the solution might be based on the current momentum.

2. The Corrector (The Anchor)

The Scout might be a bit too optimistic. The Main Team then checks the Scout's guess against the "sticky mud" and the "fences."

• In the paper: This is the "Corrector" step. It adjusts the Scout's guess to ensure it actually fits the rules of the problem.

3. The Secret Sauce: The "Dual" Stabilizer

This is the paper's biggest breakthrough.

• The Analogy: Imagine the spinning carousel has a counter-weight on the other side. If the team starts to spin too fast (instability), the counter-weight pulls them back to the center.
• In the paper: The authors realized that the "fences" (the dual problem) have a property called Strong Convexity. This acts like that counter-weight. By exploiting the stability of the fences, they can safely let the "skier" (the main part of the algorithm) run much faster without falling off the carousel.

What Does This Achieve?

1. Speed:

   • Old Hiker: Takes $1000$ steps to find the bottom.
   • APAPC: Takes roughly $30$ steps.
   • The Math: They proved the speed goes from $1/t$ to $1/t^2$. If you double the time, you get four times the accuracy, not just twice.

2. Versatility:

   • It works whether the valley is a gentle slope (General Convex) or a steep, narrow funnel (Strongly Convex).
   • It handles three different types of "fences": smooth walls, rigid bars, and linear constraints (like "you must stay on this specific line").

3. Stability:

   • Unlike previous "fast" methods that might crash, this one is guaranteed to eventually stop exactly at the bottom of the valley (convergence).

Why Should You Care?

This isn't just about math theory. This algorithm is a new engine for:

• Medical Imaging: Reconstructing clear MRI scans from noisy data faster.
• Machine Learning: Training AI models that are huge and complex without waiting weeks for them to finish.
• Engineering: Optimizing power grids or traffic flow in real-time.

Summary

The authors took a known "speed boost" (Nesterov momentum) that was too dangerous to use on complex, multi-constraint problems. They built a stabilizer (using the dual problem's strength) that allows the algorithm to run at high speed without crashing. The result is a Smart Ski Team that can navigate the most treacherous, spinning valleys faster and more reliably than anyone else.

Technical Summary

1. Problem Statement

The paper addresses structured convex optimization problems of the form:
$$\min_{x \in X} \Psi(x) := f(x) + g(x) + h(Kx)$$
where:

• $X$ and $U$ are real Hilbert spaces.
• $f: X \to \mathbb{R}$ is convex and $L_f$-smooth (gradient is Lipschitz continuous).
• $g: X \to \mathbb{R} \cup \{+\infty\}$ and $h: U \to \mathbb{R} \cup \{+\infty\}$ are proper, lower semicontinuous convex functions (potentially nonsmooth).
• $K: X \to U$ is a nonzero bounded linear operator.

The Core Challenge: While proximal splitting algorithms (like PDHG, Condat–Vũ, PAPC) efficiently solve such problems by handling $f$, $g$, and $h$ separately, accelerating their convergence with respect to the smooth term $f$ is notoriously difficult. Primal-dual methods exhibit "rotational dynamics" in the product space $X \times U$; naively applying Nesterov momentum often destabilizes the algorithm, leading to divergence.

Specific Assumption: The authors focus on the case where $g(x) = \frac{\mu_g}{2}\|x\|^2$ (i.e., $g$ is a quadratic, potentially strongly convex term). This assumption allows for a specific decoupling of momentum that generalizes to the nonsmooth composite term $h \circ K$.

2. Methodology: The APAPC Algorithm

The authors propose the Accelerated Proximal Alternating Predictor–Corrector (APAPC) algorithm. It integrates Nesterov-type acceleration into the Primal-Dual Alternating Predictor-Corrector (PAPC) framework.

Key Design Features:

• Decoupled Momentum: Unlike standard FISTA or Accelerated Gradient Descent (AGD) where the momentum is applied directly to the iterate, APAPC maintains a "history-accumulating" sequence ($z_t, v_t$) and a "momentum-smoothed" estimate ($x_t, u_t$).
• Predictor-Corrector Structure:
  1. Prediction: Compute an intermediate primal variable $\hat{z}_t$ using the gradient of $f$ evaluated at a momentum-weighted point $y_t$.
  2. Dual Update: Update the dual variable $v_{t+1}$ using the proximity operator of $h^*$.
  3. Correction: Update the primal variable $z_{t+1}$ using the new dual variable.
  4. Momentum Step: Compute the next estimates $x_{t+1}$ and $u_{t+1}$ as weighted averages of the current and previous iterates, controlled by a sequence $(a_t)$.
• Stabilization via Dual Strong Convexity: The acceleration is stabilized by exploiting the strong convexity of the dual problem. The momentum parameter $a_t$ is capped based on the strong convexity modulus of the dual, preventing the rotational instability that plagues naive acceleration in primal-dual spaces.

3. Key Contributions

A. Unified Lyapunov Framework

The authors develop a unified single-step Lyapunov inequality analysis. This framework:

• Handles both general convex ($\mu_g=0$) and strongly convex ($\mu_g > 0$) regimes simultaneously.
• Decouples the parameters of the primal ($\mu_g$) and dual ($\mu_{h^*}$ or properties of $K$) problems.
• Proves that simply capping the momentum parameter $a_t$ achieves optimal linear convergence in the strongly convex case without needing complex parameter tuning.

B. Comprehensive Convergence Rates

The paper establishes optimal convergence rates across three distinct regimes where the dual problem is strongly convex:

1. Smooth $h$ ($h$ is $L_h$-smooth):

   • Sublinear: $O(1/t^2)$ convergence rate for the Lagrangian gap when $\mu_g = 0$.
   • Linear: Accelerated linear convergence when $\mu_g > 0$. The complexity scales as $\mathcal{O}\left(\sqrt{\frac{L_f}{\mu_g} + \frac{\|K\|^2 L_h}{\mu_g}} \log(1/\epsilon)\right)$, which is optimal.

2. $K^*$ Bounded Below ($\lambda_{\min}(KK^*) > 0$):

   • This regime covers cases where $h$ is not smooth but the operator $K$ has a bounded inverse on its range.
   • Sublinear: $O(1/t^2)$ rate.
   • Linear: Accelerated linear convergence with complexity scaling involving $\sqrt{\frac{L_f \|K\|^2}{\mu_g \lambda_{\min}(KK^*)}}$.

3. Linearly Constrained Problems ($Kx = b$):

   • A special case where $h$ is the indicator function of a linear constraint.
   • The algorithm achieves $O(1/t^2)$ for the objective gap and $O(1/t)$ for the constraint violation (which can be improved to $O(1/t^2)$ with penalty methods).
   • Linear convergence is established when $\mu_g > 0$.

C. Point Convergence (Weak Convergence of Iterates)

A significant theoretical contribution is the proof of weak convergence of the iterates $(x_t, u_t)$ to a saddle-point solution.

• Historically, proving iterate convergence for accelerated methods (like FISTA) in infinite-dimensional spaces was an open problem.
• Leveraging recent breakthroughs (Jang & Ryu, 2025; Boţ et al., 2025), the authors prove that under the condition that the dual solution is unique and the sequence is bounded, the primal iterates $x_t$ converge weakly to a solution $x^*$.
• This is the first such proof for a fully split, accelerated primal-dual algorithm.

4. Results and Complexity Analysis

The paper provides a comparative table of complexity (iteration counts to reach accuracy $\epsilon$):

Regime	Condition	Sublinear Rate ($O(1/t^2)$)	Linear Rate (Strong Convexity)
Smooth $h$	$h$ is $L_h$-smooth	Theorem 3.3	Corollary 3.4: $\mathcal{O}\left(\sqrt{\frac{L_f}{\mu_g} + \frac{\|K\|^2 L_h}{\mu_g}} \log \frac{1}{\epsilon}\right)$
Bounded $K^*$	$\lambda_{\min}(KK^*) > 0$	Theorem 3.8	Corollary 3.9: $\mathcal{O}\left(\sqrt{\frac{L_f \|K\|^2}{\mu_g \lambda_{\min}}} + \frac{\|K\|^2}{\lambda_{\min}} \log \frac{1}{\epsilon}\right)$
Linear Constraints	$Kx = b$	Theorem 3.11	Corollary 3.13: Similar to Bounded $K^*$ but with $\lambda^+_{\min}$

Comparison with State-of-the-Art:

• PAPC (Non-accelerated): Scales linearly with condition numbers (e.g., $L_f/\mu_g + \|K\|^2/\lambda_{\min}$).
• APAPC (Proposed): Scales with the square root of the condition numbers, matching the optimal Nesterov acceleration rate.
• ACV (Accelerated Condat-Vũ): While ACV exists, APAPC offers a different structural approach (predictor-corrector) and provides the first iterate convergence guarantees for this class of fully split accelerated methods.

5. Significance and Impact

1. Breaking the Acceleration Barrier: The paper successfully overcomes the "rotational dynamics" barrier in primal-dual splitting, demonstrating that Nesterov acceleration can be seamlessly integrated if the dual problem's strong convexity is leveraged to stabilize the primal updates.
2. Theoretical Rigor: It provides a unified analysis that covers sublinear and linear regimes, offering a complete picture of convergence behavior. The proof of weak iterate convergence is a major theoretical milestone for the field of convex optimization.
3. Practical Applicability: The algorithm is "fully split," meaning it only requires evaluations of $\nabla f$, $K$, $K^*$, and proximal operators of $g$ and $h$. It does not require inverting operators or solving subproblems, making it suitable for large-scale signal processing, image reconstruction, and machine learning.
4. Future Directions: The authors identify that extending this to a general nonsmooth $g$ (not just quadratic) remains an open challenge, likely requiring more complex splitting schemes (like PD3O). They also suggest future work on stochastic variants and randomized implementations.

In summary, this paper presents a robust, theoretically sound, and optimal algorithm for a broad class of structured convex problems, bridging the gap between the efficiency of splitting methods and the speed of Nesterov acceleration.