On the Local Linear Convergence of Operator Splitting Methods for Conic Programming
summary
The gist
Operator-splitting methods such as the primal-dual hybrid gradient method (PDHG) and the alternating direction method of multipliers (ADMM) often exhibit linear convergence on conic programs…
In short
This work investigates why operator-splitting methods like PDHG and ADMM converge linearly to optimal solutions for conic programs under specific geometric conditions. It identifies strict complementarity and quadratic facial violation as key conditions that guarantee this fast convergence when starting near an optimal point, providing a verifiable error-bound framework.
Key concepts
- Strict Complementarity (SC)
- This condition means that for every constraint in the optimization problem, at least one constraint is active (binding) at the optimal solution. It is a strong geometric property that simplifies the structure of the conic program and is crucial for ensuring linear convergence of splitting methods.
- Quadratic Facial Violation (QFV)
- This condition relates to how well a point violates the boundary defined by a symmetric cone. QFV ensures that when initialized close to an optimal solution, the violation of this boundary grows quadratically. This growth is essential for establishing the necessary error bounds for linear convergence.
- Metric Subregularity
- This is a regularity condition on the saddle-point mapping related to the primal-dual formulation. It essentially means that the mapping behaves nicely near an optimal point, implying that small changes in input lead to predictably bounded changes in the output. This property is equivalent to local linear convergence for PDHG and ADMM.
- Operator Splitting Methods (PDHG/ADMM)
- These are iterative algorithms designed to solve complex optimization problems by breaking them down into simpler subproblems. They alternate between solving different parts of the problem, such as primal and dual steps. The paper focuses on proving when these methods achieve linear convergence rather than just slower sublinear rates.
Terminology used across episodes
This episode discusses
- On the Local Linear Convergence of Operator Splitting Methods for Conic Programming · Paper Radio
- CuClarabel: GPU Acceleration for a Conic Optimization Solver
- On the Asymptotic Superlinear Convergence of the Augmented Lagrangian Method for Semidefinite Programming with Multiple Solutions
- Second-order growth, tilt stability, and metric regularity of the subdifferential
- Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
- Clarabel: An interior-point solver for conic programs with quadratic objectives
- Local linear convergence of the primal-dual hybrid gradient algorithm for semidefinite programming · Paper Radio
- Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity · Paper Radio
- GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity
- A Practical GPU-Enhanced Matrix-Free Primal-Dual Method for Large-Scale Conic Programs · Paper Radio
- On the Infimal Sub-differential Size of Primal-Dual Hybrid Gradient Method and Beyond
- On a Unified and Simplified Proof for the Ergodic Convergence Rates of PPM, PDHG and ADMM
- Restarted Halpern PDHG for Linear Programming
- An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
- Error bounds for perspective cones of a class of nonnegative Legendre functions
The paper
On the Local Linear Convergence of Operator Splitting Methods for Conic Programming · Read on arXiv
Lijun Ding, Haihao Lu, Jinwen Yang
University of California San Diego · MIT · University of Chicago
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming".
Emmy: Here's the gist of the paper. Operator-splitting methods such as the primal-dual hybrid gradient method (PDHG) and the alternating direction method of multipliers (ADMM) often exhibit linear convergence on conic programs, although general theory guarantees only sublinear rates <ref:2608.16054#pg2>.
Ada: This paper identifies two geometric conditions – strict complementarity and quadratic facial violation – that explain this local behavior <ref:2608.16054#pg4>.
Emmy: Identification of Geometric Conditions The authors identify two geometric conditions for local linear convergence of operator splitting methods for conic programs: strict complementarity (SC) and quadratic facial violation (QFV) <ref:2608.16054#pg4>.
Ada: These conditions imply that PDHG or ADMM converge linearly to an optimal solution when initialized sufficiently close to the converging strictly complementary solution <ref:2608.16054#pg4>.
Title and authors: Ada: So, we're talking about this paper titled "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming" by Haihao Lu and Jinwen Yang. This work looks at how fast algorithms like PDHG or ADMM converge when they are solving conic programs.
Emmy: It’s really about those methods that split the problem into smaller pieces, and they often settle into linear convergence, even though general theory only promises a slower, sublinear rate in most cases.
Kolya: So what’s the core idea here? Are we finding a way to get better than that slow sublinear rate under certain conditions?
Ada: Exactly. The authors identify two specific geometric conditions—strict complementarity and quadratic facial violation—that explain why those methods behave linearly locally, provided you start close enough to the correct solution.
Emmy: That sounds structural. It suggests that the geometry of the problem itself dictates whether we get a fast convergence rate or just a slow one over time.
Kolya: So what does strict complementarity mean in this context? Is it just a condition on how many variables are active at the optimum?
Ada: Not exactly, though it's related. In simple terms, strict complementarity means that at the optimal point, you don't have redundant constraints or variables that are essentially doing nothing.
Emmy: And then they pair that with something called quadratic facial violation—that’s a way of describing how the faces of the cone behave near the optimum.
Kolya: So what does quadratic facial violation imply for the actual optimization process when you're running PDHG or ADMM? Does it just make things converge faster, or does it change *how* they converge?
Ada: It changes how they converge. When both conditions are met, the paper shows that PDHG and ADMM actually converge linearly to that optimal solution if you initialize them close enough to the strictly complementary solution.
Emmy: That's a big deal because most of the time, we just get those sublinear rates from theory, but this suggests practical performance can be much better when the problem has this specific structure.
Kolya: So if I’m running a huge optimization problem and I know my setup meets these conditions, does that mean I can actually expect a predictable speed of convergence?
Title and authors: Ada: Yes, you can. The paper provides a way to verify this local linear convergence using what they call a primal-dual error-bound framework. This framework is key because it links the geometric properties directly to the actual growth of the functions involved in the algorithm.
Emmy: That framework seems like it connects three different concepts together—growth, error bounds, and metric subregularity—into one verifiable path.
Kolya: And what does this unified framework actually tell us about those growth conditions? Does it simplify things for someone trying to set up an experiment?
Ada: It shows that strict complementarity and quadratic facial violation imply uniform quadratic growth of both the primal function and the dual function near the solution. This is a concrete starting point for analysis.
Emmy: And then they establish an equivalence between three different conditions: that uniform quadratic growth, and this localized smoothed gap, and metric subregularity on the primal-dual formulation are all locally equivalent.
Kolya: If those three things are equivalent locally, what does that mean for choosing which one to check during a run? Does it make debugging easier?
Ada: It means you only need to verify one of them to guarantee the others hold locally, which is really helpful because metric subregularity is often a condition we can actually measure.
Emmy: And then they show that metric subregularity itself provides the unified argument for local linear convergence of both PDHG and ADMM, which is pretty neat.
Kolya: So the paper essentially says: if your problem has strict complementarity and quadratic facial violation, you get a verifiable path showing local linear convergence via metric subregularity. That’s a strong claim when you consider how many real-world problems we deal with.
Ada: And they extend this idea to composite optimization by generalizing those geometric conditions to something called quadratic subdifferential violation, or QSV.
Emmy: That generalization is what allows these fast convergence rates to apply to a wider class of problems, moving beyond just standard conic programming.
Kolya: So for someone using these methods on more complex composite settings, the paper suggests that if you can satisfy the generalized conditions, you can still expect that local linear convergence behavior.
Ada: Right. The paper also looks at how we can improve this convergence further by looking at acceleration techniques like restart schemes and Halpern schemes.
Emmy: Those acceleration methods aren't just adding speed; they actually improve the dependence on how far away you are from the solution, moving it towards a linear rate more robustly.
Title and authors: Kolya: So if I’m trying to push the practical performance of these solvers, do these acceleration schemes give me a real boost beyond what those initial geometric conditions provide?
Ada: They do. Using their unified form for operator splitting, they show how restart and Halpern acceleration can improve the local rate dependence from something quadratic to linear under those specific initialization assumptions.
Emmy: It’s about showing that the simple restart mechanism isn't just a brute-force speed boost; it has a theoretical grounding in this local convergence theory.
Kolya: So to wrap up, this paper on "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming" gives us two geometric conditions—strict complementarity and quadratic facial violation—that explain local linear convergence. It provides a verifiable error-bound framework linking those conditions to uniform quadratic growth and metric subregularity.
Ada: And it shows that under these conditions, PDHG and ADMM converge linearly when initialized correctly close to the solution.
Emmy: It connects the geometry of the cone structure directly to the convergence rate of our solvers, which is a really useful connection for understanding algorithm behavior in practice.
Kolya: For me, what matters is that they give us this unified framework, because it lets us check three different conditions—growth and subregularity—to see if we can guarantee that local linear convergence.
Ada: And they broaden the scope by generalizing this to composite optimization using quadratic subdifferential violation, which makes these fast solvers applicable to more complex structures.
Emmy: It’s a solid piece of work because it doesn't just state a result; it builds an entire structure for verifying that convergence behavior.
Kolya: And the fact that they include acceleration methods shows they’re thinking about how we can actually use this theory to make solvers faster in real applications.
Ada: So, this paper, "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming," gives us a concrete tool—the geometric conditions and the error-bound framework—to understand when operator splitting methods achieve linear convergence locally.
Emmy: It suggests that understanding the underlying geometry of the problem is a direct path to understanding why our algorithms perform well.
Kolya: We can apply this when we are dealing with large-scale conic problems, especially in those settings where strict complementarity holds, and it gives us a solid theoretical foundation for those empirical successes.
The paper's summary: Ada: So, we're looking at this paper on "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming," and essentially, they’ve put together a framework to explain why things like PDHG and ADMM converge linearly when you get close to the right answer.
Emmy: It’s about finding those specific geometric shapes in the problem—things like strict complementarity and quadratic facial violation—that make these algorithms behave predictably instead of just crawling toward the solution slowly.
Kolya: What's interesting is how they build this error bound framework, it’s not just a claim; it connects the geometry to actual growth rates of functions, which gives us something verifiable.
Ada: Exactly. They show that if those geometric conditions hold, you get uniform quadratic growth in both the primal and dual augmented Lagrangian functions near the solution. That's their starting point for the whole analysis.
Emmy: Then they prove that this uniform quadratic growth is equivalent to another condition called metric subregularity on the primal-dual formulation, which is really useful because we can actually measure that subregularity.
Kolya: And then they show that this metric subregularity is locally equivalent to the other two conditions, and finally, that it’s what guarantees the local linear convergence for both PDHG and ADMM. That’s a lot of linking together.
Ada: It means you don't need to check every single condition separately; if you check one of those three—growth or subregularity—you know the other two must also be true locally, and that’s what leads to linear convergence.
Emmy: And they even show how restart schemes and Halpern schemes can improve this local rate dependence, showing that a simple restart mechanism can push the convergence rate from quadratic up to linear under those initialization assumptions.
Kolya: That acceleration part is interesting because it shows that the theory isn't just about getting a slow linear rate; it’s about making sure you get the best possible local rate using existing tools.
Ada: It really changes how we think about these solvers in practice, moving them from being just "fast" to being predictably fast when we know the problem has that right geometry.
Emmy: So this paper gives us a concrete map: if your setup has strict complementarity and quadratic facial violation, you can verify local linear convergence through a specific set of measurable conditions.
Kolya: It’s definitely useful for people who are running these methods on large-scale conic problems because it gives them the theoretical backing to expect better performance than just the general sublinear rates we usually see in theory.
Ada: And they even extend this to composite optimization by generalizing those geometric conditions, which means this isn't just a niche result for standard conic programs; it applies to more general problem structures as well.
Emmy: So the big picture here is that we can use the underlying geometry of the constraint set to design smarter algorithms that converge much faster than what general convergence theory predicts.
The paper's improvements: Ada: So, we’ve talked about how strict complementarity and quadratic facial violation explain why these operator splitting methods converge linearly locally, and now we're looking at what they suggest can be done with this framework.
Emmy: The authors point out that their error-bound framework isn't just a static proof; it’s a tool for understanding the actual mechanics of the iteration, showing exactly what drives that linear behavior.
Kolya: And I think the real strength is in how they link metric subregularity to those growth conditions, because metric subregularity is something we can actually check numerically, which makes this whole process more practical for checking if a specific problem has those good properties.
Ada: Right. They show that this equivalence means you have three different things—the growth of the augmented Lagrangians, the gap growth, and that metric subregularity—and they all point to the same local linear convergence result.
Emmy: It simplifies the design process because you can target one of those conditions directly to ensure everything else holds locally, which is a big structural win for anyone trying to build a solver.
Kolya: And beyond just verifying it, they introduce acceleration techniques like restart schemes and Halpern schemes, which are ways to push that local convergence rate even higher.
Ada: Those acceleration methods aren't just about making things faster; they show how we can improve the dependence on how far away you are from the solution, moving it from something quadratic to something linear more robustly.
Emmy: It’s about showing that those simple restart mechanisms have a theoretical grounding in this local convergence theory, not just empirical speed bumps.
Kolya: So this suggests that we can use acceleration not just as a brute force speed boost, but as a mechanism informed by the underlying geometry of the problem to achieve better rates.
Ada: It means if you know your problem has those right geometric properties, you have a clear path to not only convergence but also optimal scaling for the iteration process itself.
Emmy: This opens up possibilities for designing solvers that adapt their step size or restart frequency based on how close they are getting to that strictly complementary solution.
Kolya: So the implication is that this isn't just about proving a theorem; it’s about providing an actionable blueprint for building next-generation optimization algorithms for those types of problems.
Ada: Indeed, and they extend all this to composite optimization by generalizing the conditions, meaning these fast solvers aren't limited only to standard conic programs anymore.
Conclusion: Ada: So we've covered how strict complementarity and quadratic facial violation explain the local linear convergence of operator splitting methods for conic programming, and now we’re wrapping up this discussion on "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming."
Emmy: It really boils down to finding geometric conditions that force these iterative solvers into a predictable, fast convergence path when you start near the answer.
Kolya: I still think that error-bound framework is the most important part because it gives us a way to actually verify those growth rates we're talking about without just taking our word for it.
Ada: Exactly. It connects the geometry of the problem directly to measurable properties of how much the primal and dual functions are growing near that solution point, which is a solid path for researchers.
Emmy: And by showing that three different conditions—growth, gap growth, and metric subregularity—are locally equivalent, they’ve given us a unified target condition for linear convergence.
Kolya: That unification is key because it means you only need to check one of those things to be sure the others are there too. It simplifies the algorithm design process significantly for anyone trying to set up these solvers.
Ada: It really does, and they even show how restart schemes can improve that local rate dependence, pushing convergence from quadratic toward linear under certain initialization assumptions.
Emmy: That acceleration part is interesting because it suggests we can use simple mechanisms within the operator splitting structure to get a better scaling behavior for our algorithms.
Kolya: It’s about showing that these acceleration techniques aren't just brute force speed bumps; they have a theoretical basis in this local convergence theory.
Ada: So this paper, "On the Local Linear Convergence of Operator Splitting Methods for Conic Programming," gives us a concrete tool—those geometric conditions and the error-bound framework—to understand when these methods achieve linear convergence locally.
Emmy: It suggests that understanding the underlying geometry of the problem is a direct path to understanding why our algorithms perform well in practice.
Kolya: We can apply this when we are dealing with large-scale conic problems, especially in those settings where strict complementarity holds, and it gives us a solid theoretical foundation for those empirical successes.
Ada: And they extend all this to composite optimization by generalizing the conditions to quadratic subdifferential violation, which means these fast solvers aren't limited only to standard conic programs anymore.
Emmy: It’s about showing that we can use the structure of the constraint set itself to design smarter solvers that converge much faster than general convergence theory predicts.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.19309-Small Prime Primitive Roots in Arithmetic Progressions
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors