- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies PAPF, a fixed-point iteration based on the filter , which combines the current iterate with the result of two applications of the base operator. A local Jacobian analysis gives a necessary and sufficient condition for improving the spectral convergence factor over the equal-cost baseline . For firmly nonexpansive operators with nonempty fixed-point sets, the paper establishes fixed-point preservation and global convergence for fixed . It also studies optimal mixing parameters, gives a sharp bound on spectral improvement within the convex degree-two filter family under firm nonexpansiveness, and compares PAPF with convex relaxed KM. When spectral information is unavailable, the authors use short residual probes to select a parameter and then keep it fixed. The paper provides conditional analysis of these probes and examples of their limitations. Experiments on quadratically regularized optimal transport, power-method problems for nonsymmetric matrices, and synthetic operators compare several methods by the operator evaluations needed to reach prescribed tolerances. The results show how the gains depend on spectral phase, parameter choice, and search overhead.
Critical strengths
1. Simple implementation.
Once the mixing parameter is fixed, each PAPF iteration requires two evaluations of the base operator and a weighted average. The update stores only a few additional vectors and does not require an explicit Jacobian. This makes it straightforward to implement around an existing fixed-point iteration.
2. Useful analysis of the method’s scope.
Proposition 2 gives a sharp bound on the spectral improvement attainable for FNE operators, and Remark 11 extends this bound to the convex degree-two filter family. Proposition 3 explains which spectral phases favor PAPF or convex relaxed KM at the level of a single conjugate eigenvalue pair. The paper also clearly distinguishes global convergence guarantees from local rate improvements and explains the limitations of short residual probes.
3. Careful empirical evaluation and cost accounting.
The experiments compare methods by operator evaluations, report fixed-parameter and adaptive results separately, and include the adaptive search overhead. They cover favorable and unfavorable spectral regimes, an FNE control, and matched-accuracy checks on the OT instances. With tuned fixed parameters, PAPF achieves approximately – speedups over on the tested OT maps without extrapolation. The paper also reports cases where adaptive selection fails to provide a benefit, helping readers assess both the demonstrated gains and the procedure’s practical limits.
Critical weaknesses
1. Substantial overlap with prior Lookahead theory.
For a deterministic base map , the PAPF update is exactly Lookahead with and mixing parameter (Zhang et al., 2019). The paper acknowledges that it does not introduce a new acceleration principle. More importantly, Theorem 2 is a direct specialization of Proposition 1 in Ha and Kim (2022).
For , their condition for improving the spectral factor over base iterations is
\operatorname{Re}(\lambda^k)<\rho^{2k}.$$ Setting $k=2$ gives $\cos(2\theta_j)<\rho^2$ for every dominant eigenvalue, exactly as in Theorem 2. Their Appendix C.2 also establishes the existence of an admissible mixing parameter. Thus, the prior result already covers both the condition on all dominant eigenvalues and the comparison at equal operator-evaluation cost. The claims in the Introduction and Appendix A that this criterion was previously uncharacterized require substantial revision and explicit attribution. **2. The remaining contributions do not yet establish a substantial advance.** The sharp FNE cap and the comparison with convex relaxed KM provide useful theoretical results. However, the KM comparison considers one eigenvalue pair at a time and does not directly determine which filter is better for a general spectrum (Remark 12). The experiments verify the proposed mechanisms, but provide more limited evidence of their practical benefit. The largest speedups over $T^2$ occur on instances with prescribed favorable spectral phases. These tests leave unclear how often comparable gains arise in applications. In the tested OT problems, the existing extrapolated Chambolle–Pock map requires fewer operator evaluations than PAPF applied to the map without extrapolation, even at matched KKT accuracy (Appendix G.2, Tables 4–5). PAPF therefore improves the chosen base map, but does not demonstrate an advantage over this existing OT solution method. Given the overlap in Theorem 2, I am not yet convinced that the remaining theoretical results and experiments establish a substantial advance beyond prior work. **3. Adaptive parameter selection does not consistently achieve the available gains.** The adaptive procedure is intended for cases where the Jacobian spectrum is unknown. It gives useful gains on several power-method and synthetic instances, as well as on Iris OT. However, its performance on the other OT instances is less convincing. On the warm-started small OT problem, the 20 repeated-initialization runs give a median adaptive speedup of only $1.03\times$, compared with $1.89\times$ for the fixed parameter. Eight runs require more evaluations than $T^2$, although the increases are small, at most 2.3% (Section 5.4 and Appendix G.8). On the Quad-OT $(50\times50)$ instance, the search falls back to $T^2$, missing the improvement achieved by a tuned fixed parameter while adding 140 search evaluations (Table 1). The main concern is the missed acceleration, together with the search cost. The theoretical results do not resolve this uncertainty. The true spectral objective is convex, but the short-probe objective need not be unimodal. Propositions 4 and 8 provide guarantees under specific assumptions; they do not guarantee that the implemented golden-section search finds a near-optimal parameter or reduces the total number of operator evaluations. The authors acknowledge these limitations, but the current evidence still leaves the practical benefits of adaptive selection inconsistent across the OT problems. **References** - Zhang et al. *Lookahead Optimizer: k steps forward, 1 step back.* NeurIPS 2019. [Paper](https://papers.nips.cc/paper_files/paper/2019/file/90fd4f88f588ae64038134f1eeaa023f-Paper.pdf). - Ha, J. and Kim, G. *On Convergence of Lookahead in Smooth Games.* AISTATS 2022. Proposition 1 and Appendix C.2. [Paper](https://proceedings.mlr.press/v151/ha22a/ha22a.pdf).Questions for authors
1. Relationship to prior Lookahead results.
With and a Lookahead mixing parameter of , Proposition 1 and Appendix C.2 of Ha and Kim (2022) appear to imply Theorem 2. This includes both the condition on every dominant eigenvalue and the comparison at equal operator-evaluation cost. Are there differences in assumptions or conclusions that prevent this reduction? If not, could the authors clarify the attribution and revise the novelty claims in Section 1 and Appendix A?
2. Remaining contributions and practical value.
If Theorem 2 follows from prior work, what new insights do the sharp FNE cap, the comparison with convex relaxed KM, and the probe-selection analysis provide? On the tested OT instances, the extrapolated Chambolle–Pock map uses fewer operator evaluations than PAPF applied to the map without extrapolation, even at matched KKT accuracy (Appendix G.2, Tables 4–5). Given this result, what practical use cases do the existing experiments support?
3. Adaptive selection: gains and search cost.
The paper reports a search overhead of 140 operator calls and gives an idealized break-even analysis in Appendix G.3. Using the existing OT and repeated-initialization results, could the authors separate the effects of search overhead from the performance of the selected parameter? In particular, how well do the improvements seen in short probes translate into actual savings in later iterations? Please compare against continuing with from the same post-burn-in state, and distinguish savings before and after including search costs. Do these results suggest a practical way to decide when the search is worth its cost? If not, how should its expected benefits be qualified?
Reference
Ha, J. and Kim, G. On Convergence of Lookahead in Smooth Games. AISTATS 2022. Proposition 1 and Appendix C.2. Paper.
3 comments
Response to Reviewer DdqP (2/2): adaptive selection (W3, Q3)
Q3: search cost versus selected parameter, as you asked. New App. G.9 compares with continuing from the same post-burn-in point . Medians over the 20 starts, in operator calls (savings are medians of per-run differences, so the columns do not subtract exactly):
| Instance | from | locked phase | saving before search | after the 140-call search |
|---|---|---|---|---|
| Quad-OT 6×5 | 6447 | 6101 | 328 (5.1%; range −10 to 1600) | 188 (2.9%) |
| Iris OT | 21204 | 15211 | 5993 (28.3%) | 5853 (27.5%) |
| Quad-OT 50×50 | 33296 | 33296 (fallback) | 0 | −140 |
| Power method | 3189 | 106 | 3080 (96.6%) | 2940 (90.5%) |
Three findings:
- On the small OT instance the loss is the search cost. In 7 of the 8 runs that need more calls than , the locked phase needs fewer (by 16–122 calls) but does not repay the search.
- Moderate probe gains translate when contracts measurably in the probe window. The probe-implied speedup is on Iris against a realized , and against on Quad-OT 50×50, where a 2% margin over four updates can only certify speedups above . Where barely moves, the probe misleads: at the candidate would have cost 25% more calls, and the fallback was correct. The probe overestimates where a mode that is not visible in the window limits the later rate (Table 12).
- A break-even condition exists, but it is not the practical answer. In hindsight the search pays when (: remaining calls, : speedup of the selected parameter; measured levels in Table 13). But on Quad-OT 50×50 the same search accepts harmful parameters in 5 of 6 runs started later in the transient, ties on a residual plateau, and accepts a useful parameter in 9 of 9 runs in the linear phase (Table 14). It fails through when it looks, and it looks once. As you note, Propositions 4 and 8 do not certify it; Proposition 8 quantifies why short probes fail.
The answer of the revision: no search (Algorithm 2, App. G.10). The residuals carry the same information in every step, and the rule uses it: in every step it recomputes from two eigenvalue estimates fitted to the residuals of the last three steps. It needs no spectral information, no search, no tunable constant and no extra operator call.
- The gap you point out closes. On the small OT instance (median for Algorithm 1 against for the fixed parameter) the rule reaches 1.85×, and it needs fewer calls than in all 20 runs (1.81–1.90×).
- Where Algorithm 1 fell back, the rule gains. On the random dual starts of Quad-OT 50×50 and Iris (fallback in 40 of 40 runs) it reaches 1.33× and 1.32×, more than the fixed parameter of Table 1 (1.18× and 1.26×). On Quad-OT 50×50 it sets in every step of the plateau, where any slows the iteration, and filters afterwards: 24,674 calls against 33,356 for and 27,884 for the best fixed parameter.
- Where no gain exists, it costs almost no calls. At most 0.43% more calls on the FNE controls (Algorithm 1: up to 102%), and at most 1.63% over all 484 runs on the paper's instances and on new problems (general comment).
- Guaranteed (Proposition 9). ; convergence for every such sequence, globally for FNE maps and locally under Assumption 1; for an affine map whose residual is carried by one pair, of Lemma 1 (0 if the pair violates the criterion), and if the Jacobian is symmetric.
- Not guaranteed. Speed: Proposition 9 gives convergence, not a rate. In synthetic stress tests, some of them adversarial, the largest loss we found is 12.2% (App. G.10). The rule adds arithmetic per step, so savings in calls are savings in time only when operator evaluations dominate the cost; on Quad-OT 50×50, where a PDHG step is cheap, the run with the rule takes longer than that of .
Algorithm 1 stays in the paper as submitted, with the qualification of findings 1–3 (App. G.9): its benefit depends on when the search is run and on a long remaining run. Where operator calls dominate the cost, we now recommend Algorithm 2.
We hope the two parts address W1–W3: the attribution is corrected, the contributions are restated, and the gap between fixed and adaptive parameters is closed in operator calls on the OT maps. We would be grateful if you would reconsider your assessment in light of the revision, and we are glad to answer further questions.
Thank you for the substantial revision and the detailed responses. After carefully examining the revised manuscript, I have updated my rating from 2 (Weak Reject) to 3 (Weak Accept).
The authors have addressed my main concerns satisfactorily.
First, the relationship between PAPF and Lookahead is now properly acknowledged, and the central spectral criterion is correctly attributed to Ha and Kim (2022). I consider my original concern regarding the novelty attribution resolved.
Second, the newly introduced Algorithm 2 is a meaningful improvement over the original adaptive procedure. In particular, its residual-based online parameter estimation, convergence guarantee, and exact recovery in the affine two-mode setting make the adaptive approach substantially more convincing. The repeated-initialization experiments also provide encouraging evidence of its effectiveness.
The remaining limitations concern the practical computational overhead and the incremental novelty of combining existing spectral estimation and online relaxation techniques. In particular, reductions in operator evaluations do not always translate into wall-clock speedups, and the method should be viewed as a specialized rather than general-purpose accelerator.
Overall, I believe the revised manuscript provides a useful contribution through its sharp FNE acceleration bound, equal-cost comparison with relaxed KM, and residual-based adaptive algorithm. While some limitations remain, the substantial improvements in the revision address my main reservations, and I now lean toward acceptance.
Response to Reviewer DdqP (1/2): prior work, attribution, and what the paper adds
Thank you for the careful review and for pointing us to Ha & Kim (2022), which we had missed.
W1 / Q1. You are right, and the revision attributes the result. For a deterministic map, Sα=αI+(1−α)T2 is Lookahead (Zhang et al., 2019) with k=2 and slow step 1−α, and Theorem 2 is the case k=2 of Proposition 1 of Ha & Kim (2022), including the condition on every dominant eigenvalue and the comparison with T2 at equal cost. Nothing prevents the reduction. The revision says so in the abstract, Section 1, the contribution list, the header of Theorem 2, the conclusion and App. A. It also attributes the single-pair optimum of Lemma 1(b,c), which is the minimizer in the proof of their Proposition 2, and the picture of Fig. 1(b). App. A now covers Zhang et al. (2019), Chavdarova et al. (2021), Ha & Kim (2022), Pethick et al. (2023) and Sanyal et al. (2026).
W2 / Q2. What the paper adds to the criterion: a sharp cap for FNE maps, k=1 against k=2 at equal cost, and a rule without parameters.
Practical use cases (W2, Q2). We agree on the OT comparison and do not claim an OT solver: the extrapolated Chambolle–Pock map needs fewer calls (0.60–0.79× at KKT residual 10−8). OT is our test bed because one problem yields a non-FNE and an FNE map. What the experiments support is PAPF as a wrapper that saves operator calls where the slow modes rotate, and time where those calls dominate the cost. On the three OT maps none of the accelerators of Table 3 (Anderson, Halpern, inertial KM, TKMA) exceeds 0.67 times the speed of T2 in calls, against 1.35–1.87× for the rule (Table 15). New App. G.11 tests how often gains arise, on 100 runs outside the paper's instances with the untuned rule:
The filter is not a general-purpose accelerator. With Algorithm 2 it can be applied without knowing which case holds: over 484 runs it needs at most 1.63% more operator calls when it does not help (stress tests and the arithmetic cost: part 2/2).