Not All Feasibility Repairs Are Equal: Non-Expansive Retractions for Warm-Started Solvers

Warm-starting a combinatorial solver from a learned dual prediction is a three-stage pipeline: predict, repair to feasibility, then run a primal-dual algorithm from the repaired point. The first and third stages are well studied; the second is treated as plumbing. It is not. We show that the standard two-sided greedy repair (move both endpoints of a violated constraint by the full residual) is a non-expansion onto the feasible set simultaneously in every $\ell_p$ norm, $p \in [1,\infty]$: it moves no further from any feasible point than the prediction already was. This holds for arbitrary, not necessarily bipartite, systems $y_i + y_j \ge w_{ij}$, and in the packing direction as well. The end-to-end constant of Dinitz et al. tightens from $3$ to $1$ (via their own movement lemma for their repair; via the $\ell_1$ case for the two-sided mirror). The property is delicate: we show that two natural alternatives, the textbook "project down to feasibility" repair and the variant that splits the excess between the endpoints as evenly as integrality allows, both fail it by a factor of at least $3$. Finally we exhibit a family on which the same greedy operator is order-independent in $\ell_1$ but order-dependent in $\ell_0$, with both scan orders producing identical dual gaps, so no $\ell_1$-based analysis can tell them apart. This matters because Chen et al.'s $\ell_0$-parameterised runtime is proved for a feasible input and does not survive composition with an $\ell_1$-guaranteed repair. We then give the fix: under a decreasing-weight scan the constraints that fire form a matching, so at most $2\min(|A|,|B|)$ coordinates move from a cold start, independent of the larger side, and we prove the sharp warm-start bound $\|y^* - \mathcal{R}_{\downarrow}(\hat{y})\|_0 \le \|y^* - \hat{y}\|_0 + 2\min(|A|,|B|) - 1$, which collapses to $+1$ for $|A| = 1$ (sharp; the $+1$ fails for $\min(|A|,|B|) \ge 2$). Proofs are given where we have them; the remaining cold-start envelope is conjectured and verified against enumerated faces. Code reproducing every number will be made publicly available.