Preconditioned primal-dual dynamics in convex optimization: Non-ergodic convergence rates

Vassilis Apidopoulos, Cesare Molinari, Juan Peypouquet, Silvia Villa

This paper, recently published by researchers from Greece, Italy, and the Netherlands, explores a sophisticated way to speed up and stabilize the "continuous-time" versions of optimization algorithms. By introducing time-varying preconditioning, the authors show how to turn oscillating, non-convergent systems into fast, reliable solvers for complex convex problems.

TL;DR

The authors introduce a preconditioned continuous-time dynamical system for solving primal-dual optimization problems. By using "asymptotically antisymmetric" preconditioners, they ensure that the system's trajectory converges directly to a solution (non-ergodic convergence) with fast, tunable rates, overcoming the stability issues of traditional Arrow-Hurwicz flows.

What Problem Does This Paper Address?

Many problems in machine learning, imaging, and control take the form $\min f(x) + g(Ax)$. To solve these, we often use "primal-dual" methods that handle the functions $f$ and $g$ separately.

In the world of continuous-time dynamics (where we model algorithms as differential equations), the standard approach is the Arrow-Hurwicz flow. However, this flow has a major weakness: it often fails to converge to a single point. Instead, the trajectories tend to "orbit" or rotate around the solution forever. While the average of the trajectory might converge (ergodic convergence), the actual state of the system at any given time does not. This paper seeks to "restore" convergence by borrowing the concept of preconditioning from discrete-time algorithms and applying it to these continuous-time systems.

Methods

The authors propose a dynamical system defined by: $$P(t)\dot{z}(t) + Mz(t) \ni 0$$ Where $z$ represents the primal and dual variables, $M$ is the operator representing the optimization problem, and $P(t)$ is a time-varying preconditioner.

The key technical contributions include:

  • Preconditioner Design: They define $P(t)$ as a block matrix involving scalar functions ($\alpha, \beta, \gamma, \delta$) that can evolve over time.
  • Antisymmetry: They focus on "antisymmetric" preconditioners (where the off-diagonal terms are negatives of each other). This specific structure is what breaks the "rotational" behavior of standard flows.
  • Lyapunov Analysis: The authors use "energy estimates" (Lyapunov functions) to prove that the duality gap—a measure of how far we are from the optimal solution—vanishes over time.
  • Parameter Tuning: They show that by choosing specific growth rates for the preconditioner parameters, they can achieve different speeds of convergence.

Datasets

The paper validates its theoretical findings using synthetic numerical experiments implemented in the Julia programming language:

  • Quadratic Minimization: A 100-dimensional problem with a random matrix $A$.
  • Linearly Constrained Quadratic: A 50-dimensional problem where the goal is to minimize a quadratic function subject to $Ax = b$.
  • LASSO: A classic sparse regression problem (20x40 dimensions) used to test the system on non-differentiable functions.

Key Insights and Ideas

  • Breaking the Cycle: The "aha moment" is that preconditioning isn't just for speed; in continuous time, it's a tool for stabilization. The antisymmetric structure effectively "damps" the oscillations that plague standard primal-dual dynamics.
  • Non-Ergodic is Better: Most continuous-time proofs only show that the average of the path is good. This paper proves the current state of the path is good, which is much more practical for real-world implementation.
  • Tunable Convergence: The speed of the algorithm is directly linked to how the preconditioner evolves. By tuning a single function ($\zeta(t)$), a user can achieve sublinear, linear, or even faster convergence rates.
  • Robustness to Parameters: For linearly constrained problems, the convergence rates are surprisingly "oblivious" to the specific non-diagonal coefficients used, suggesting the method is robust to hyperparameter choices.

Key Results

  • Fast Rates: For linearly constrained problems, the authors established linear convergence rates ($O(e^{-t})$), matching and generalizing previous specialized results.
  • General Convergence: In the general case, they proved that if the preconditioner parameters are chosen such that their integral diverges, the system is guaranteed to reach a primal-dual solution.
  • Numerical Superiority: In all tests (Quadratic, Constrained, and LASSO), the antisymmetric preconditioned system significantly outperformed both the standard Arrow-Hurwicz flow and symmetric preconditioned versions in terms of how quickly the duality gap reached zero.

Limitations and Future Work

  • Pointwise Convergence: While the authors prove the duality gap goes to zero and limit points are solutions, they haven't yet proven that the trajectory always converges to a unique point (though they provide a sufficient condition for it).
  • Bilinear Coupling Only: The current theory is limited to problems with linear operators ($Ax$). Extending this to nonlinear coupling in convex-concave Lagrangians remains an open challenge.
  • Selection Bias: In problems with multiple possible solutions, it is unclear if the choice of preconditioner "biases" the system toward a specific solution (e.g., the one with the smallest norm).

Summary updated

Abstract

We introduce and analyze a continuous primal–dual dynamical system in the context of the minimization problem f ( x ) + g ( A x ) , where f and g are convex functions and A is a linear operator. In this setting, the trajectories of the Arrow–Hurwicz continuous flow may not converge, accumulating at points that are not solutions. Our proposal is inspired by the primal–dual algorithm by Chambolle and Pock (2011), where convergence and splitting on the primal–dual variables are ensured by adequately preconditioning the proximal-point algorithm. We consider a family of preconditioners, which are allowed to depend on time and on the operator A , but not on the functions f and g , and analyze asymptotic properties of the corresponding preconditioned flow. Fast convergence rates for the primal–dual gap and optimality of its (weak) limit points are obtained, in the general case, for asymptotically antisymmetric preconditioners, and, in the case of linearly constrained optimization problems, under milder hypotheses. Numerical examples support our theoretical findings, especially in favor of the antisymmetric preconditioners.
BibTeX
@inproceedings{apidopoulos2025preconditioned,
  author = {Vassilis Apidopoulos and Cesare Molinari and Juan Peypouquet and Silvia Villa},
  title = {{Preconditioned primal-dual dynamics in convex optimization: Non-ergodic convergence rates}},
  booktitle = {Nonlinear},
  year = {2025},
  doi = {10.1016/j.nahs.2025.101674},
}

Loading related content...

Figure