acceptodds
Under review as a conference paper at ICLR 2027

Afterimage Slow Regions in First-Order Methods for Linear Conic Programming

Abstract

First-order methods for linear conic programming often stall on long plateaus. Existing analyses characterize when during a run or on which problem instances slow convergence occurs; we instead ask where in the state space slow convergence is present. We introduce the slow region family for parameterized averaged fixed-point iterations. On a slow region, one step moves the state by only a small fraction of its distance to the fixed-point set, so an orbit starting there keeps almost its initial distance for arbitrarily many iterations. We then develop the afterimage principle to construct them. A center family and a nearby petal family share the same limit parameter, so their residual fields become close, while their fixed-point sets or forward drifts stay far apart. The petal geometry then certifies a slow region for the center. We verify the standing assumptions for ADMM, sGS-ADMM, and PDHG, and give an LP, SOCP, and SDP gallery showing how varied slow regions can be.

Primary area:
optimization
Keywords:
first-order optimization, conic programming, operator splitting, ADMM, PDHG, convergence analysis, degeneracy, slow convergence

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_WKo6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies where slow convergence occurs in the state space of first-order methods for linear conic programming. It introduces a slow region family SεS_\varepsilon, characterized by a uniformly vanishing ratio between the one-step fixed-point residual and the distance to the corresponding fixed-point set. This condition implies that trajectories initialized in the region retain a nonvanishing fraction of their initial distance to the fixed-point set for an increasing number of iterations. The proposed afterimage principle constructs such regions by comparing a target problem with a nearby reference problem. Their residual fields remain close while their fixed-point or drift structures differ substantially. The paper develops sufficient conditions involving face selection, Hölder-sensitive displacement, and fixed points escaping to infinity.

Critical strengths
  1. Unified theoretical framework. The paper provides a principled way to characterize and certify slow-convergence regions across different first-order methods. This connection between spatial residual properties and iteration lower bounds provides a quantitative lower bound on the number of iterations for trajectories initialized in these regions.
  2. Broad coverage of degenerate settings. The framework accommodates nonpolyhedral cones and reference problems without fixed points, including pathological drift behavior. The diverse examples demonstrate its flexibility beyond standard LP settings.
Critical weaknesses
  1. Limited evidence of the framework's additional theoretical value. Although the general results are mathematically meaningful, constructing the certificates still relies heavily on hand-designed examples and prior knowledge of solution geometry. It remains unclear what new conclusions the framework enables beyond existing error-bound and sensitivity analyses. The paper is also relatively hard to follow, as the dense notation and specialized constructions obscure the main conceptual contributions.
  2. Limited validation of predictive power. The experiments mainly illustrate constructed slow regions, but provide less direct evidence that the certificates quantitatively predict convergence behavior. In particular, the tightness of the iteration lower bounds and their relationship to observed plateau durations remain insufficiently established.
Questions for authors
  1. Can the authors further clarify how broadly the sufficient conditions in Theorems 2.9–2.11 apply beyond the constructed examples? In particular, are there broader classes of conic programs where these conditions naturally arise?
  2. How does the choice of the reference problem affect the resulting slow-region certificates, particularly when multiple petals are possible, as in Example 3.3? Are there general principles for selecting informative petals?
  3. Can the authors further clarify how the theoretical iteration lower bounds relate to the observed slow-convergence behavior in the experiments? In particular, how informative are these bounds about the actual convergence time scales?
2 comments
AuthorsOpenReview ↗

Response to Reviewer WKo6 (1/2)

We thank the reviewer. The two weaknesses are that the framework has not shown what it adds beyond error bounds, and that its certificates have not been tested against observed convergence. The revision (blue text) adds two real-world problems, a procedure for computing the petal from a run, a remark on the residual as a backward error, and a readability pass on Section 2, with code, data and logs in the supplementary material.

Weakness 1: theoretical value beyond error bounds, hand-designed examples, and readability. On error bounds, the new remark in Appendix A.3 says that for ADMM with fixed A, every state z is an exact KKT point of the nearby problem (A, AX, c − P_A^⊥(c − S)), where (X, S) is the pair recovered from z, and that the residual is equivalent, up to constants, to the data distance to that problem. So the residual is a backward error in the data, and the ratio of Definition 2.3 divides it by a forward error in the state. This is a reformulation of Lemmas A.1–A.2, not a new theorem. Its use is to separate two questions: where the nearest solved problem is, which is algebra from the state, and whether its fixed-point set is far from the center's, which is geometry and the content of Theorems 2.9–2.11. The relation to error bounds is one-way: a slow region forces the error-bound constant to blow up, but not conversely, as a two-line example in Section 2 shows. What the certificate adds to an error-bound constant is a uniform bound on a named region and the neighboring problem that explains it, and the petal's face geometry then gives the exit time.

On hand-designed examples, the two new instances are real problem classes rather than constructions, a forestry planning LP from the Netlib collection and the second-order moment relaxation of a binary quadratic program, the model behind max-cut, and in both the petal is read off the run. On STOCFOR1 the dual pair freezes while the primal moves along an edge, the nearest cost that makes the frozen dual optimal is the petal cost, and the orbit rides the petal's fixed-point set from iteration 1,727 to 73,474. On the SDP the same computation on each of four plateaus gives four petals, checked in floating point and only approximately so on the first, a cascade of four afterimage families with nested tie sets.

On readability, Section 2 now paraphrases each definition, gives a proof sketch of Proposition 2.4, moves the notation block to the appendix, and uses the motivating LP of Section 1 to illustrate the afterimage definition. We have also built an anonymous companion page (https://nameless-lab-f94e.pm3z5lev.workers.dev/) that explains the paper with eight animations, from the two-variable LP through the three mechanisms to the two real-world runs.

Weakness 2: predictive power and tightness. We tested this on both instances in three ways. First, the horizon: on STOCFOR1, Proposition 2.4 with β = ½ and the ratio at the entry state (1.026 × 10⁻⁵) guarantees that the distance to V^c stays above half its entry value for at least 48,738 iterations, and the first iteration below half is 48,741 iterations later. With β = 0.9 the numbers are 9,747 and 9,748. The bound is nearly attained because the displacement is constant and points almost exactly toward V^c. In general it is only a lower bound. Second, the modulus: on the SDP the bound, computed from the petal displacement and the distance of the plateau to X⋆, agrees with the measured ratio to two digits on the two clean interior plateaus (2.2 × 10⁻⁴ and 2.5 × 10⁻⁴), and on the last plateau, which ends at X⋆, it applies to truncations and agrees as well up to 170 iterations before the exit. On STOCFOR1 the family bound ρ_ε ≤ 7.5 × 10⁻⁵ ε/ε₀ holds along the whole center family, and the measured ratio lies between 1.0 × 10⁻⁵ and 3.9 × 10⁻⁵. Third, the duration: the end of a ride is predicted from a single state by the petal's face geometry, 73,474 from the state at iteration 2,000 on STOCFOR1, and 5,141.6, 8,936.0 and 22,169.7 against the observed 5,142, 8,937 and 22,170 on the SDP, from 1,142, 1,937 and 7,170 iterations earlier. The scripts that produce these numbers, with their logs, are in the supplementary material.

AuthorsOpenReview ↗

Response to Reviewer WKo6 (2/2)

Question 1: broader classes. The mechanism has a plain description for ADMM: the dual pair freezes at a point that is dual feasible for a nearby cost while the primal moves on a face of the feasible set, so the frozen dual is an exact certificate for the wrong problem. Two settings produce it. For LP, it is a nominal cost close to one whose optimal face is an edge rather than a vertex. On STOCFOR1 the petal lowers the timber-revenue coefficients to 37–39% of nominal, and at that price the model is indifferent along an edge of harvest schedules. For moment relaxations, it is an objective close to one with tied minimizers. The four SDP petals have 7, 4, 3 and 2 tied minimizers, and the nested tie sets explain the cascade. These are two instances and a mechanism, not a theorem about either class. The LP result is also operator-specific, because Ruiz scaling with σ = ‖b‖/‖c‖ removes this plateau and a smaller σ brings another cascade (Appendix A.4.8). For PDHG we have no comparable statement.

Question 2: choice of petal, and Example 3.3. With A, σ and the data norm fixed, the petal of a state is determined as the nearest problem for which the state is an exact KKT point. States are exact fixed points of this shared petal exactly when AX and P_A^⊥S are constant on the region, and a frozen dual pair is one sufficient condition for that. In Example 3.3 the two regions have the two petals of the example as their nearest problems, each certifies its own region with its own exponent, and Proposition 2.5 combines them with modulus max(ρ¹, ρ²). On the SDP the same happens along one orbit, with four petals in sequence and nested tie sets. Which petal an orbit visits first we cannot predict, and this is listed as open.

Question 3: bounds versus observed time scales. To summarize Weakness 2: the modulus bound agrees with the measured ratio to two digits on the two interior plateaus and on the last one away from its endpoint, the horizon of Proposition 2.4 is within three iterations of the observed half-distance time on STOCFOR1, and the exits are predicted to within one iteration. The horizon is a lower bound on the retained distance rather than an estimate of the exit or convergence time, although it is nearly attained on a straight ride toward the fixed-point set, as here.

Reviewer_fc8rOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the slow convergence behavior of first-order methods for linear conic programming, including linear programming (LP), second-order cone programming (SOCP), and semidefinite programming (SDP). Unlike existing analyses that primarily characterize slow convergence through iteration complexity, local convergence rates, or problem conditioning, the authors introduce a spatial perspective that identifies regions of the state space where first-order methods exhibit slow progress.

The paper introduces the concept of a slow region (SR) family, characterized by a vanishing ratio between the fixed-point residual and the distance to the fixed-point set. The authors establish that iterates initialized in such regions remain relatively far from the fixed-point set for an increasing number of iterations as the problem parameter approaches a limiting value. The main theoretical contribution is the afterimage principle, which constructs slow regions by comparing two nearby parameterized problem families, referred to as the center and petal families. Although their fixed-point residual mappings become arbitrarily close, their fixed-point sets or forward drift structures may exhibit substantially different geometric behavior. The authors exploit this discrepancy to establish sufficient conditions for slow convergence.

Three representative mechanisms are analyzed: face selection, Hölder sensitivity, and escape of fixed points to infinity. The framework is developed for averaged fixed-point operators and specialized to ADMM, symmetric Gauss–Seidel ADMM (sGS-ADMM), and PDHG. A collection of examples involving LP, SOCP, and SDP illustrates the proposed framework and its theoretical predictions.

Critical strengths

The authors proposed a novel and intersting perspective on slow convergence in this submission. The paper provides an interesting spatial interpretation of slow convergence in first-order optimization algorithms. Rather than focusing exclusively on convergence rates along individual trajectories, the proposed framework identifies regions of the state space associated with slow progress. This viewpoint complements conventional convergence analyses based on error bounds, metric subregularity, and problem conditioning. The definition of slow region families applies to a broad class of parameterized averaged fixed-point iterations. The standing assumptions are clearly stated, and the authors establish several useful properties, including persistence away from the fixed-point set, finite unions, and thickening of slow regions. These results give the proposed concept a mathematically systematic foundation.

The authors also presented Interesting geometric interpretation through the afterimage principle. The center–petal construction is conceptually appealing. It explains how nearby optimization problems can exhibit similar residual fields while possessing significantly different asymptotic structures. The three sufficient conditions in Theorems 2.9–2.11 illustrate different mechanisms through which this discrepancy produces slow convergence.

Moreover, the theoretical results of this submission can be applied to multiple optimization algorithms. The authors verify the proposed assumptions for ADMM, sGS-ADMM, and PDHG. This strengthens the generality of the framework and demonstrates that the underlying phenomenon is not restricted to a particular optimization algorithm. The authors also presented multiple diverse illustrative examples in this submission. The LP, SOCP, and SDP examples provide useful geometric illustrations of the theoretical results. In particular, the motivating LP example clearly demonstrates how a small perturbation can cause the fixed-point set to collapse while leaving the residual field nearly unchanged. The figures help communicate the proposed mechanism.

Critical weaknesses

The major weakness of this submission is the unclear connection between the proposed spatial characterization and actual convergence complexity. The main concern is that the proposed slow region definition is based on the ratio ρϵ\rho_{\epsilon}. Although this ratio provides a meaningful characterization of the residual field, its relationship with the actual convergence behavior of an optimization algorithm is not fully explained. Proposition 2.4 establishes that iterates initialized in a slow region remain relatively far from the fixed-point set for a number of iterations proportional to 1/ρϵ1 / \rho_{\epsilon}. However, the analysis does not characterize whether typical trajectories enter these regions or how frequently these regions influence practical convergence. It would strengthen the paper to establish more explicit connections between the slow region geometry, the initialization, and the overall iteration complexity.

Moreover, the proposed framework is primarily descriptive rather than algorithmically actionable. The afterimage principle offers an explanation for slow convergence, but it is unclear how the proposed results could be used to improve existing optimization algorithms. For example, can the slow regions be detected using quantities available during ADMM or PDHG iterations? Can the characterization motivate adaptive step sizes, preconditioning, restarting, or other acceleration strategies? Without such connections, the practical significance of the framework remains somewhat limited. Also The construction of slow regions relies heavily on carefully designed parameterized examples. Theorems 2.9–2.11 provide sufficient conditions for constructing slow region families, but applying these results requires considerable information about the fixed-point sets or forward drift of nearby problems. In particular, the center–petal construction may be difficult to implement for a general conic optimization problem, since identifying a suitable petal family can itself require substantial analytical effort. The paper would benefit from a more systematic procedure for constructing petal families or identifying candidate slow regions from problem data.

The relationship with existing error-bound and conditioning theories could also be developed further. The paper observes that the slow region modulus is closely connected to the deterioration of residual-based error bounds. This raises an important question regarding the theoretical novelty of the proposed framework relative to existing results on metric subregularity, Hoffman bounds, and conditioning. The authors should more explicitly distinguish the information provided by slow region families from that already available through parameter-dependent error-bound constants. For example, does the afterimage principle provide quantitatively sharper estimates, or identify slow regions that cannot be conveniently characterized through existing error-bound techniques?

Finally, the numerical evaluation on practical optimization problems need some improvements. The numerical illustrations are primarily based on low-dimensional, analytically constructed examples. While these examples effectively illustrate the geometric phenomena, they do not establish how frequently the proposed slow regions arise in realistic optimization applications. Experiments on larger LP, SOCP, or SDP instances would substantially strengthen the empirical evidence. In particular, it would be useful to examine whether the proposed geometric characterization explains convergence plateaus observed in practical first-order solvers.

Questions for authors

The three theorems 2.9 to 2.11 establish sufficient conditions for the existence of afterimage slow regions. It would be interesting to understand how restrictive these conditions are. Are there examples where the slow region modulus converges to zero but no suitable petal family can be constructed using the proposed mechanisms? A discussion of possible necessary conditions, or a characterization of the limitations of the afterimage principle, would strengthen the theoretical contribution.

2 comments
AuthorsOpenReview ↗

Response to Reviewer fc8r (1/2)

We thank the reviewer for a careful reading. The framework was spatial and descriptive, with no evidence on real-world problems and no procedure for finding a petal. The revision (blue text) adds two real-world instances, a procedure for the petal, a remark on the residual as a backward error, and a paragraph on error bounds. The code, data and logs are in the supplementary material, and an anonymous companion page (https://nameless-lab-f94e.pm3z5lev.workers.dev/) walks through the argument and the two runs with animations.

Weakness 1: connection to actual convergence, and whether orbits enter these regions. We still cannot prove that typical orbits enter afterimage regions, and the conclusion says so. Two cold-start runs do enter them, and on STOCFOR1 there is a local reason why an orbit that comes near the region stays on it.

On STOCFOR1 (Netlib, 117 × 165 after slacks, unscaled, τ = 1, σ = 0.1), the ADMM map from the all-zero start joins a straight segment at iteration 1,727 and rides it to iteration 73,474. The segment is the fixed-point set of a petal LP. Theorem 2.9 certifies the part of it at distance at least 1,740 from the far endpoint, which holds the states up to iteration 60,000, with ρ_ε ≤ 7.5 × 10⁻⁵ ε/ε₀. Proposition 2.4 with β = ½ guarantees at least 48,738 iterations before the distance halves, and the observed number is 48,741. The bound is nearly attained because the constant displacement points almost exactly toward V^c. The end of the ride, predicted from the petal's face geometry and the state at iteration 2,000, is 73,474. The rank facts behind the petal and the center and the endpoint certificates are verified in exact rational arithmetic, by a script included in the supplementary material. On the SDP instance (N = 211, m = 16,171), 71% of the 27,756 iterations lie on four plateaus. On the two clean interior ones the modulus bound agrees with the measured ratio to two digits (2.2 × 10⁻⁴ and 2.5 × 10⁻⁴), and the three clean exits are forecast within one iteration from 1,142, 1,937 and 7,170 iterations earlier. These are two instances, not a statistic.

The orbit stays for a local reason: on the sign cell of the STOCFOR1 segment the ADMM map is affine with a normal linear part, with eigenvalue 1 along the segment and all other eigenvalues of modulus at most 0.98572. As long as the reference point stays on the segment and the orbit stays in the cell, every transverse component contracts at that rate while the map translates along the segment. All 480 random perturbations of norm up to 100 returned to within 10⁻⁶ of the segment within 8,000 iterations, and all 40 of norm 1,000 and 3,000 within 60,000. This explains the stall after entry but not the arrival from zero, which remains an observation.

Weakness 2: actionability. Detection uses three quantities that every ADMM code computes: in these runs the primal residual falls to 10⁻¹² while the dual residual and the step between iterates stay constant to working accuracy. With the primal feasible and the dual pair (y, s) frozen, the state is an exact KKT point of the petal with cost c_p = Aᵀy + s. The petal cost is algebraic, but predicting the end of the stall needs the petal's face geometry, which we obtained from the petal's optimal partition and one LP solve for the endpoint on STOCFOR1, and by a generalized eigenvalue computation on the SDP. We do not claim a general one-solve procedure, and we have no PDHG analogue. On step size and scaling, six penalties from 0.01 to 3 ride the same edge of STOCFOR1, for 717,859 iterations down to 1,425, roughly in proportion to 1/σ, and at σ = 10 no straight stretch forms. Ruiz equilibration with σ = ‖b‖/‖c‖ removes the plateau, and σ ten times smaller brings a six-petal cascade back (Appendix A.4.8). So the afterimage belongs to the operator, and changing σ or the scaling moves it. An online rule has not been tested and is left as future work.

Weakness 3: a systematic procedure. Both instances use the procedure of Section 4. By Lemma A.1, z is a fixed point of (A, b, c′) iff AX = b and c′ − S ∈ ran(Aᵀ), where (X, S) is the pair recovered from z. On a plateau the primal is feasible and the dual pair is frozen, so the costs for which every state is an exact KKT point form the affine set S + ran(Aᵀ), and the nearest one to c is c_p = c − P_A^⊥(c − S). By Theorem 2.2 the center residual on the petal's fixed-point set is the constant −τσ(c − c_p), which gives the straight ride and its speed. The procedure is conic, and on the SDP it yields petals that are relaxations of perturbed polynomials with tied minimizers, and on each plateau the number of tied minimizers equals the rank of the primal iterate.

AuthorsOpenReview ↗

Response to Reviewer fc8r (2/2)

Weakness 4: relation to error bounds. The new paragraph in Section 2 and the remark in Appendix A.3 make three points. First, the relation is one-way: a slow region forces the best error-bound constant on it to blow up, but a large error-bound constant can come from a single point, since for T_ε = diag(1 − ε, ½) and S_ε = {e₁, e₂} the error-bound constant is 1/ε while the modulus is ½. Second, for ADMM with fixed A the residual at any state is, up to constants, the smallest change of (b, c) under which that state is an exact KKT point, so the residual is a backward error in the data and the ratio of Definition 2.3 divides it by a forward error in the state. This is a reformulation of Lemmas A.1–A.2, not a new result. Third, the certificate adds the region and the neighboring problem that explains it, and the petal's face geometry adds the exit time. STOCFOR1 shows the difference, since the ratio is 10⁻⁵ on the segment and 3 × 10⁻³ in the later linear regime, so one constant for the instance would say nothing about where the stall is or when it ends. We do not claim sharper constants than a tight error bound on the same region.

Weakness 5: practical instances. Neither instance is a construction like the gallery. STOCFOR1 is a forestry planning model from the Netlib collection, and the SDP is the second-order moment relaxation of a binary quadratic program, the relaxation behind max-cut and many other combinatorial problems, with Gaussian coefficients. Both are small by solver standards, so the new examples establish occurrence with certificates rather than prevalence. Every number can be checked against the logs and input data in the supplementary material.

Question: how restrictive are the conditions, and are there necessary conditions? For ADMM with fixed A, the remark answers pointwise: up to its two constants, the ratio at z is small if and only if the change of (b, c) that makes z an exact KKT point is small compared with the distance from z to the fixed-point set of the center. It does not answer the family question, since Definition 2.8 needs one petal for a whole region. States are exact fixed points of one shared petal exactly when AX and P_A^⊥S are constant on the region, for which a frozen dual pair is one sufficient condition and the second region of Example 3.3 is another case. Theorems 2.9–2.11 then give three ways a shared petal produces a vanishing modulus. The list is not exhaustive, because Region 2 of each of Examples 3.3 and 3.4 falls outside it and is certified from the definitions. A necessary characterization, and anything for PDHG or for perturbations of A, remain open.

Reviewer_XqGXOpenReview ↗
Rating
1
Confidence
1
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

In the paper the authors stress, that for linear conic program problems the convergence in several regions is significantly slower. They pose the question, whether this can be characterized and get a positive answer to that. With general assumption, that describes several optimization methods, they describe several cases, when there is a slow region. They also show the examples of problems with provided in advance slow convergence regions.

Critical strengths

1)The definition of slow region for the algorithm (family of algorithms) is novel and appealing. Considering narrower problem classes is beneficial to our understanding of real-life algorithm performance.

Critical weaknesses

1)The paper is incredibly difficult to read, starting from the section 2.1. It's not clear, whether there were any efforts done to review the LLM-written text. It's nearly impossible to understand the key points of the paper.

2)Only toy examples are considered.

Questions for authors

1)What makes it interesting to construct families with slow convergence? Or is it given as an example, that slow region exist?

2)How can one detect the slow region of the problem beforehand, so the person will not stop the optimization process after a long stall?

1 comment
AuthorsOpenReview ↗

Response to Reviewer XqGX

We thank the reviewer. Both weaknesses are fair, and both led to changes in the paper.

Weakness 1: readability, and the LLM question. The mathematics and the text were developed and written by us. As the AI use statement says, we used language models to copy-edit and compress the exposition and to review the draft adversarially. The compression went too far in Section 2, which introduced all notation at once and put the formal machinery before the idea it serves. In the revision (blue text), the notation block has moved to the appendix, with a pointer at the start of Section 2. Each definition is followed by a sentence saying what it means, Proposition 2.4 has a proof sketch, and the motivating LP of Section 1 illustrates the afterimage definition. We have also built an anonymous companion page (https://nameless-lab-f94e.pm3z5lev.workers.dev/) that explains the paper with eight animations, from the two-variable LP of Section 1 through the three mechanisms of Section 2 to the two real-world runs. If some passages of the paper are still unclear, we would be glad to hear which ones.

Weakness 2: only toy examples. The revision adds two real-world problems (new Section 4, Appendices A.4.8 and A.4.9), with code, data and logs in the supplementary material.

The first is STOCFOR1, a forestry planning LP from the Netlib collection with 117 constraints and 165 variables after slacks, used unscaled. We run the paper's ADMM map from the all-zero start. After 1,727 iterations the orbit joins a straight segment and rides it until iteration 73,474, with the residual frozen at 0.129 while the distance to the fixed-point set falls only from 12,589 to 3,324, so the ratio of Definition 2.3 is about 10⁻⁵. The segment is the fixed-point set of a petal, an LP whose cost differs from STOCFOR1's by 0.14% in norm (it cuts the seven timber-revenue coefficients to 37–39% of their nominal values). Theorem 2.9 applies, and Proposition 2.4 guarantees that the distance stays above half its entry value for at least 48,738 iterations, against an observed 48,741.

The second is the moment relaxation of a binary quadratic program with 20 variables and Gaussian data, the SDP relaxation behind max-cut, with a 211 × 211 matrix variable and 16,171 constraints. The relaxation is exact and strictly complementary, so local theory gives linear convergence, yet ADMM from zero still needs 27,756 iterations, and 71% of them lie on four afterimage plateaus. The procedure gives a petal for each, read off the frozen dual slack and checked in floating point, only approximately so on the first, so the run carries a cascade of four petal families with nested sets of 7, 4, 3 and 2 tied minimizers. On the two clean interior plateaus the modulus bound agrees with the measured ratio to two digits, and the three clean exits are forecast to within one iteration from 1,142, 1,937 and 7,170 iterations earlier.

Both instances are small by solver standards, and the SDP's coefficients are Gaussian, as the paper states.

Question 1: why construct families with slow convergence? The families are the certificate rather than the goal. The center is the problem one solves, and the petal is a neighboring problem whose fixed-point set is far from the center's. The theorems say that on the petal's fixed-point set the center iteration is slow, and by how much. In Section 3 we chose both by hand to isolate each mechanism, whereas in the new examples the petal is computed from a stalled run, and the certificate then explains the stall's residual and ratio, while the petal's face geometry gives its length.

Question 2: how to detect a slow region before stopping. What we have is an in-run diagnosis rather than a pre-run detector. The signature uses quantities every ADMM code already has: in these runs the primal residual falls to 10⁻¹² while the dual residual and the step between iterates stay constant to working accuracy. With the primal feasible and the dual pair (y, s) frozen, the state is an exact KKT point of the petal with cost c_p = Aᵀy + s, and the stall lasts until the primal iterate reaches the boundary of the petal's optimal face. On STOCFOR1 the state at iteration 2,000 predicts the end of the ride at iteration 73,474, as observed. Computing that boundary needs the petal's face geometry, which took the petal's optimal partition and one LP solve on STOCFOR1 and a generalized eigenvalue computation on the SDP, so we do not claim a cheap universal forecast. On this instance the ride time shrinks roughly like 1/σ and at σ = 10 no straight stretch forms, which suggests a remedy, but an online rule is left as future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.