On the Local Linear Convergence of Operator Splitting Methods for Conic Programming
Listen
Radio episode about this paper
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.
Lijun Ding, Haihao Lu, Jinwen Yang
University of California San Diego · MIT · University of Chicago
math.OC
Submitted: 2026-08-17
Updated: 2026-10-31
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 96/100
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…
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
Summary
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. p. 016054#pg2>. This paper identifies two geometric conditions – strict complementarity and quadratic facial violation – that explain this local behavior <ref:2608. p. 016054#pg4>.
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>. 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. p. 016054#pg4>. The paper shows that strict complementarity (SC) holds unconditionally for LP, common generic settings [28], and many more structural applications [19] while quadratic facial violation (QFV) holds unconditionally for symmetric cones (including the first four cones in Table 1), and other cones under SC or generic assumptions <ref:2608. p. 216054#pg5>.
Verifiable Error-Bound Framework
A central contribution is providing a verifiable primal-dual error-bound framework for establishing local linear convergence <ref:2608.16054#pg4>. This framework has three components:
-
Implication of SC and QFV: In Proposition 1, strict complementarity and QFV imply uniform quadratic growth of the primal and dual augmented Lagrangian functions <ref:2608. p. 216054#pg5>.
-
Equivalence of three conditions: In Section 4, the paper proves that uniform quadratic growth of the augmented Lagrangian functions, quadratic growth of the extended smoothed gap, and metric subregularity are locally equivalent <ref:2608. p. 216054#pg6>.
-
A unified form for analyzing local linear convergence: Proposition 4 provides a short proof that metric subregularity yields local linear convergence of PDHG and ADMM <ref:2608. p. 216054#pg6>.
Local Convergence on Conic Programs
The paper establishes that under strict complementarity and QFV, PDHG or ADMM converges linearly to an optimal solution when initialized sufficiently close to (or converges to) this solution <ref:2608.16054#pg4>. This provides a theoretical explanation for the strong empirical performance of these methods in conic programming, and covers previous local linear convergence results on SDP [42, 41] as a special case <ref:2608. p. 216054#pg4>. The authors also discuss acceleration via restart and Halpern schemes in the same setting <ref:2608. p. 216054#pg4>.
Generalization to Composite Optimization
The analysis extends to a class of convex composite programs by proper generalization of the two geometric conditions, called quadratic subdifferential violation (QSV) <ref:2608.16054#pg4>. The generalized strict complementarity and QFV yield the local quadratic-growth and metric-subregularity properties needed for linear convergence <ref:2608. p. 216054#pg4>.
Equivalence Between Regularity Conditions
The paper proves the equivalence between three local regularity conditions for the primal-dual formulation (P-D): uniform quadratic growth of the primal and dual augmented Lagrangian functions, quadratic growth of a localized smoothed primal-dual gap, and metric subregularity of the saddle-point mapping <ref:2608.16054#pg6>. This equivalence is crucial because it allows the uniform augmented Lagrangian growth established in Proposition 1 to be transferred directly into metric subregularity of the saddle-point subdifferential, and hence into the error-bound condition used in the local linear convergence analysis <ref:2608. p. 116054#pg6>.
Local Linear Convergence on (P-D) and Acceleration
Using metric subregularity obtained from strict complementarity and QFV, the paper proves local linear convergence of PDHG and ADMM for solving (P-D), described in detail <ref:2608.16054#pg6>. The authors further show how restart and Halpern acceleration improve the local rate dependence, based on their unified operator-splitting form <ref:2608. p. 316054#pg6>.
Generalization to Convex Composite Optimization
The results generalize seamlessly to the convex composite setting without any modification <ref:2608.16054#pg6>. In this setting, the equivalence result on the conditions for local linear convergence, Theorem 1, and the acceleration continue to hold for (Pc) without any change in their statements and proofs <ref:2608. p. 216054#pg6>. Under strict complementarity and QSV, the three equivalent conditions continue to hold as well as the local linear convergence and acceleration <ref:2608. p. 216054#pg6>.
Conclusion
In this paper, they establish a unified framework for showing local linear convergence for operator-splitting type methods (OSM), including PDHG and ADMM <ref:2608.16054#pg4>. The framework consists of three components: (1) strict complementarity and quadratic facial/subdifferential violation implies uniform quadratic growth of augmented Lagrangian, (2) equivalence of three conditions for local linear convergence of OSM, with one being the uniform quadratic growth of augmented Lagrangian, and (3) a unified argument for the local linear convergence of OSM under one of the three equivalent conditions <ref:2608. p. 216054#pg4>.
Acknowledgments
Haihao Lu is partially supported by AFOSR Grant No. FA9550-24-1-0051 and a Sloan Research Fellowship <ref:2608. p. 016054#pg4>. Jinwen Yang is partially supported by AFOSR Grant No. p. 0 FA9550-24-1-0051 <ref:2608. p. 016054#pg4>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Strict complementarity and quadratic facial violation enable operator splitting methods like PDHG and ADMM to achieve linear convergence when initialized sufficiently close to an optimal solution, improving practical performance over general sublinear guarantees. This allows for faster convergence in solving large-scale conic optimization problems compared to standard first-order methods under favorable geometric conditions.
-
A unified primal-dual error bound framework allows researchers to verify the necessary growth conditions (uniform quadratic growth of augmented Lagrangians, quadratic growth of a localized smoothed gap, and metric subregularity) through a verifiable path from strict complementarity and cone geometry. This framework provides a concrete tool for analyzing why operator splitting methods behave linearly in practice.
-
The equivalence between uniform quadratic growth of augmented Lagrangian functions, the quadratic growth of the localized smoothed gap, and metric subregularity on the primal-dual formulation (P-D) allows for a single, verifiable condition to guarantee local linear convergence. This simplifies algorithm design by providing a clear target condition to aim for in complex optimization scenarios.
-
The analysis extends to convex composite optimization by generalizing geometric conditions to quadratic subdifferential violation, leading to equivalent conditions and local linear convergence for operator splitting methods in composite settings. This allows the application of these fast-converging algorithms to more general and complex problem structures beyond standard conic programming.
-
Restarted Halpern schemes can be integrated with the established local linear convergence theory to achieve accelerated convergence rates, showing that restart mechanisms can improve the local rate dependence from quadratic to linear under specific initialization assumptions. This enables faster practical solutions by using a simple restart mechanism within the iterative process of operator splitting methods.
Sources
- 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
- Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity
- 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
- 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
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise