- 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 , 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
- 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.
- 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
- 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.
- 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
- 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?
- 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?
- 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
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.
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.