acceptodds
Under review as a conference paper at ICLR 2027

PAPF: Phase-Aware Polynomial Filtering for Fixed-Point Acceleration

Abstract

We propose phase-aware polynomial filtering (PAPF), a simple method for accelerating fixed-point iterations by exploiting the phases of local Jacobian eigenvalues. PAPF applies the degree-two filter , with , using two evaluations of the original operator per iteration. For firmly nonexpansive operators with a nonempty fixed-point set, the filter preserves averagedness and fixed points, guaranteeing global convergence for every fixed mixing parameter. Beyond this setting, we characterize precisely when PAPF improves the local convergence factor over the equal-cost baseline . For a differentiable map with Jacobian and spectral radius , such an improvement is possible if and only if every dominant eigenvalue satisfies . We derive closed-form optimal parameters for individual spectral modes and formulate parameter selection for the full spectrum as a one-dimensional convex problem. When the spectrum is unavailable, we propose an empirical parameter-selection procedure based on short residual probes, requiring no explicit Jacobian information. We apply the framework to primal–dual hybrid gradient iterations for quadratically regularized optimal transport and to the power method for nonsymmetric eigenvalue problems. Experiments on these applications and synthetic operators demonstrate reductions in operator evaluations in favorable spectral regimes and support the predicted dependence of acceleration on eigenvalue phase.

Primary area:
optimization
Keywords:
Fixed-point acceleration, Polynomial filtering, Nonexpansive operators, Spectral analysis, First-order optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_DdqPOpenReview ↗
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 Sα=αI+(1−α)T2S_\alpha=\alpha I+(1-\alpha)T^2, 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 T2T^2. For firmly nonexpansive operators with nonempty fixed-point sets, the paper establishes fixed-point preservation and global convergence for fixed 0<α<10<\alpha<1. 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 1.21.2–1.9×1.9\times speedups over T2T^2 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 TT, the PAPF update Sα=αI+(1−α)T2S_\alpha=\alpha I+(1-\alpha)T^2 is exactly Lookahead with k=2k=2 and mixing parameter αLA=1−α\alpha_{\mathrm{LA}}=1-\alpha (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 0<ρ=ρ(G)<10<\rho=\rho(G)<1, their condition for improving the spectral factor over kk 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 k=2k=2 and a Lookahead mixing parameter of 1−α1-\alpha, 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 T2T^2 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
AuthorsOpenReview ↗

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−α)T2S_\alpha=\alpha I+(1-\alpha)T^2 is Lookahead (Zhang et al., 2019) with k=2k=2 and slow step 1−α1-\alpha, and Theorem 2 is the case k=2k=2 of Proposition 1 of Ha & Kim (2022), including the condition on every dominant eigenvalue and the comparison with T2T^2 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=1k=1 against k=2k=2 at equal cost, and a rule without parameters.

  1. A sharp limit for FNE maps (Proposition 2, Remark 11). For every FNE map and every convex degree-two filter, the asymptotic speedup in operator calls is at most B(ρ)<3/2B(\rho)<3/2, with B(ρ)→9/8B(\rho)\to9/8 as ρ→1\rho\to1. This tells users of resolvent-type iterations (proximal point, Douglas–Rachford, extrapolated PDHG) how much two-step averaging can give. Ha & Kim show that Lookahead improves the proximal-point method on bilinear games; for k=2k=2 that map is the extremal instance of our bound. The cap is specific to k=2k=2 (Remark 10), holds for every sequence of parameters (new Remark 15), and is attained: for Douglas–Rachford on basis pursuit the predicted gain equals the cap (13%); the measured gain of the complete run is 3–12% (App. G.11).
  2. k=1k=1 versus k=2k=2 at equal cost (Proposition 3). Convex relaxed KM is Lookahead with k=1k=1. For a single dominant pair, wherever k=1k=1 helps in the right half-plane, k=2k=2 helps more, and the crossover angle tends to arccos⁡(−1/3)\arccos(-1/3). As you note, the full-spectrum winner can differ (Remark 12).
  3. From the criterion to an algorithm without parameters (new Algorithm 2, App. G.10; part 2/2). The criterion needs the spectrum; Algorithm 2 does not. In the Lookahead literature we found the slow step adapted from a curvature estimate (Zhang et al., Sec. 2.1), set heuristically from the alignment of displacements (Mordido et al., 2024), or selected from Jacobian eigenvalues (Sanyal et al., 2026). Algorithm 2 sets it in closed form from eigenvalue estimates that the residuals provide in every step. Its ingredients are known and attributed: the fit is the estimation step of Manteuffel's adaptive Chebyshev iteration (1978) and of Poon & Liang (2019), and the design is that of Iutzeler & Hendrickx (2019), who use a real eigenvalue. We did not find its use for the under-relaxation of T2T^2 with a complex pair; we add it, with Proposition 9 and the evidence that, without the spectrum, it needs 0.88–1.20 times the calls of the best fixed parameter on the paper's nine instances (Table 15).
  4. Nonsmooth and normalized maps. The active-set spectrum of PDHG for quadratic OT (App. C) and a tangent-space theorem for the normalized power method (App. D).

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.600.60–0.79×0.79\times at KKT residual 10−810^{-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 T2T^2 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:

  • Gain predicted: the rule needs fewer calls in every run (22 of 22). Heavy ball and Nesterov on logistic regression (LIBSVM): 1.05–7.66× in 8 of 48 runs (predicted gain above 2%). For heavy ball the criterion reads, to first order, κ(1−β)<2\kappa(1-\beta)<2 at step 1/L1/L, i.e., over-estimated momentum. Douglas–Rachford on basis pursuit: 3–12%.
  • No gain predicted: at most 1.63% more calls. PageRank on four SNAP graphs (up to 876k nodes) and Douglas–Rachford for the LASSO: the same calls in 29 of 30 runs; 36 momentum runs: more in 18. Our 15-node PageRank instance is not representative, and the revision says so.
  • No prediction computed (OT between MNIST digits, 12 runs): fewer calls in 4, more in 8, by at most 0.67%.

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).

AuthorsOpenReview ↗

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 T2T^2 from the same post-burn-in point zˉ\bar z. Medians over the 20 starts, in operator calls (savings are medians of per-run differences, so the columns do not subtract exactly):

InstanceT2T^2 from zˉ\bar zlocked phasesaving before searchafter the 140-call search
Quad-OT 6×564476101328 (5.1%; range −10 to 1600)188 (2.9%)
Iris OT21204152115993 (28.3%)5853 (27.5%)
Quad-OT 50×503329633296 (fallback)0−140
Power method31891063080 (96.6%)2940 (90.5%)

Three findings:

  1. On the small OT instance the loss is the search cost. In 7 of the 8 runs that need more calls than T2T^2, the locked phase needs fewer (by 16–122 calls) but does not repay the search.
  2. Moderate probe gains translate when T2T^2 contracts measurably in the probe window. The probe-implied speedup is 1.331.33 on Iris against a realized 1.401.40, and 1.141.14 against 1.171.17 on Quad-OT 50×50, where a 2% margin over four updates can only certify speedups above 1.641.64. Where T2T^2 barely moves, the probe misleads: at n=m=200n=m=200 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).
  3. A break-even condition exists, but it is not the practical answer. In hindsight the search pays when (1−1/g)Nrem>140(1-1/g)N_{\rm rem}>140 (NremN_{\rm rem}: remaining T2T^2 calls, gg: 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 αk\alpha_k 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 1.03×1.03\times for Algorithm 1 against 1.89×1.89\times for the fixed parameter) the rule reaches 1.85×, and it needs fewer calls than T2T^2 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 αk=0\alpha_k=0 in every step of the plateau, where any α>0\alpha>0 slows the iteration, and filters afterwards: 24,674 calls against 33,356 for T2T^2 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). αk∈[0,12)\alpha_k\in[0,\tfrac12); 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, αk=α⋆\alpha_k=\alpha^\star of Lemma 1 (0 if the pair violates the criterion), and αk=0\alpha_k=0 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 O(d)O(d) 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 T2T^2.

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.

Reviewer_t8FiOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies a fixed-point filter that mixes the current iterate with two applications of the original operator. It gives an exact local condition for when this filter beats the equal-cost two-application baseline. It also bounds the possible gain for firmly nonexpansive operators and proposes a residual-based search when the spectrum is unknown. Experiments cover optimal transport, a power-method example, and synthetic operators.

Critical strengths
  1. The paper compares methods by the number of operator calls and states clearly when its filter can and cannot help. The local criterion and the gain limit for firmly nonexpansive maps are informative.
  2. The experiments include competing accelerators and report cases where PAPF loses. This makes the scope of the results easier to judge.
Critical weaknesses
  1. The largest gains rely on favorable spectral examples and a best fixed parameter. In the larger optimal-transport test, the best fixed gain falls to about 1.08×, and the adaptive rule falls back to the baseline.
  2. The automatic parameter search costs about 140 extra operator calls and can miss a good parameter or accept a harmful one. This matters because the spectrum needed to choose the best fixed parameter is usually unavailable.
Questions for authors
  1. For the larger optimal-transport test, what causes the adaptive search to miss the beneficial fixed parameter? Is there a practical way to detect this before paying for the full search?
  2. How often does PAPF beat an existing optimized solver, such as the extrapolated Chambolle–Pock method, at matched solution accuracy?
  3. In which problem sizes and accuracy ranges does the adaptive search recover its setup cost?
2 comments
AuthorsOpenReview ↗

Response to Reviewer t8Fi

Thank you for the precise assessment. Your W2 and Q1 led to the main addition of the revision.

W2. The 140-call search is no longer needed. The revision adds Algorithm 2 (App. G.10; general comment, item 1): in every step it recomputes αk\alpha_k 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 iteration converges for every sequence it can produce, globally for FNE maps and locally under Assumption 1 (Proposition 9). On n=m=200n=m=200 and on Quad-OT 50×50, in operator calls:

T2T^2best fixed α\alphaAlgorithm 1Algorithm 2 (new)
n=m=200n=m=20028,90426,63629,044 (falls back)26,968
Quad-OT 50×5033,35627,88433,496 (falls back)24,674

Where the search fell back, the rule gains: at n=m=200n=m=200 most of what the tuned parameter gives, and on the 50×50 instance more than the best fixed parameter. Where it does not help, it costs little: in 384 runs, 25 of them on new OT instances, it needs fewer calls than T2T^2 in 316 and at most 0.43% more in the others (Algorithm 1 on the FNE controls: up to 102% more).

Q1. At n=m=200n=m=200 the fallback was right; on Quad-OT 50×50 the search misses because of when it looks, which 60 calls cannot show. At n=m=200n=m=200 the gain of the tuned parameter is a finite-horizon effect (Section 5.1), and the candidate of the search would have cost 25% more calls. On Quad-OT 50×50 a beneficial parameter exists, but the search runs at call 60, in a transient that is followed by a residual plateau until about call 14,600 and only then by a linear phase. Started later in the transient it accepts harmful parameters in 5 of 6 runs; on the plateau its probes tie; in the linear phase it accepts a useful parameter in 9 of 9 runs (Table 14). It fails through when it looks, and it looks once; beforehand, the burn-in residuals show only whether its acceptance test can be informative (App. G.9). Algorithm 2 needs no detection: on the plateau it sets αk=0\alpha_k=0 in every step, and it filters once the linear phase starts (Figure 11).

W1. The gains no longer rely on a best fixed parameter; their size still depends on the spectrum. At the default starts of Table 1 the rule reaches 1.87×, 1.35× and 1.46× over T2T^2 in calls on the three OT maps, against 1.91×, 1.20× and 1.42× for the tuned fixed parameters, and on all nine instances it needs 0.88–1.20 times the calls of the best fixed parameter, without the spectrum (Table 15). That the gain depends on the spectrum is the content of the theory: on the 25 new OT instances it is mostly small (Table 18). New App. G.11 tests this on 100 runs outside the paper's instances (general comment, item 3): the rule needs fewer calls in all 22 runs in which the Jacobian spectrum predicts a gain, and exactly the calls of the unfiltered method in 29 of the 30 PageRank and LASSO runs, where the theory rules a gain out.

Q2. On OT, extrapolated Chambolle–Pock remains the better solver; the other accelerators of Table 3 need more calls than T2T^2 there, the rule fewer. At KKT residual 10−810^{-8} the extrapolated map needs 0.600.60–0.790.79 times the calls of the best fixed-α\alpha PAPF on the non-extrapolated map (Table 5). OT is our controlled test of the theory (one problem yields a non-FNE and an FNE map), not a claim of a new OT solver. Anderson, Halpern, inertial KM and TKMA reach at most 0.67 times the speed of T2T^2 in calls on the three OT maps, against 1.35–1.87× for the rule (Table 15).

Q3. Algorithm 2 has no setup cost; the search recovers its cost only on long runs in which it accepts a parameter. For Algorithm 1 the measured break-even levels are in new Table 13: after the residual has dropped by 0.1–2.6 decades on the power-method and synthetic instances and by 2.3 decades on Iris, from the first level on the 6×5 instance, and never on Quad-OT 50×50 and n=m=200n=m=200, where it falls back. Size does not decide: of the two 50×50 instances it pays on Iris only (default start).

Limits, as stated in the paper. The rule has no rate guarantee; in synthetic stress tests, some of them adversarial, the largest loss we found is 12.2% (App. G.10). The rule adds O(d)O(d) 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 T2T^2.

Of the two results you found informative, the local criterion is the case k=2k=2 of Ha & Kim's (general comment, item 2); the gain limit for FNE maps is ours, and Douglas–Rachford on basis pursuit attains it in prediction (predicted gain 13%, the cap; measured 3–12%).

We hope the revision resolves W2 and narrows W1, and we would be grateful if you would take it into account in your final assessment.

This is an good paper. I've also carefully read the revised version, and I think most of my concerns have been addressed. Given the scope of the contributions, I'll keep my score at 3. thanks!

Reviewer_1wLjOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies a simple way to accelerate fixed-point iterations by combining the current iterate with the result of applying the original operator twice. The main contribution is a condition on the phases of the dominant Jacobian eigenvalues that characterizes when this method can improve the local convergence factor over two ordinary iterations. The paper also provides convergence guarantees for firmly non-expansive operators, analyzes the limits of the possible improvement, and proposes a residual-based procedure for choosing the mixing parameter. Experiments on optimal transport, power-method problems, and synthetic operators illustrate both successful acceleration and cases where the method provides little or no benefit.

Critical strengths

Strengths 1: The paper provides an interpretable explanation of when a simple modification can improve convergence. Comparing two ordinary operator evaluations makes the central comparison meaningful, since the proposed update also uses two evaluations.

Strengths 2: The evaluation openly reports limitations and unfavorable results. Comparisons with other accelerators, repeated initializations, and examples of failed parameter selection help distinguish the potential of the fixed filter from the reliability of the adaptive algorithm. This transparency strengthens the contributions.

Critical weaknesses

Weaknesses 1: The scope of acceleration appears restricted. PAPF relies on particular oscillatory patterns in the error dynamics, so it is unclear how broadly the method can improve general fixed-point iterations. Moreover, even in the setting where global convergence is guaranteed, the possible acceleration is limited. While the simplicity of the method is appealing, these restrictions may narrow its practical applicability.

Weaknesses 2: Automatic parameter selection does not ensure lasting improvement. The proposed procedure chooses the mixing parameter from short-term residual reductions, but a parameter that looks favorable over a short interval may not improve the overall convergence process. The authors acknowledge this limitation. However, it remains unclear when a practitioner without spectral information can reliably trust the selected parameter.

Questions for authors

Questions 1: I understand that some application experiments fall outside the assumptions of the main theoretical result. To what extent, then, does the proposed theory explain the observed improvements? Clarifying the distinction between results that are consistent with the theory and results directly supported by it would help me assess the scope of the theoretical contribution.

Questions 2: Improvement over the original iteration does not establish itself a reason to prefer PAPF over other acceleration methods. Given the mixed comparative results, under what conditions do PAPF’s simplicity and low overhead provide a meaningful reason to choose it? Please clarify how broadly the evidence presented supports this practical choice.

Questions 3: The existence of a beneficial α and the ability to find a useful α without spectral information appear to be separate issues. Given that short-term observations may not translate into lasting improvement, how reliably does the current automatic procedure realize the theoretical benefit of the fixed filter? How this gap affects the method’s practical applicatbility?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 1wLj

Thank you for the review. The distinction you draw in W2 and Q3 identified the weakest part of the submission, and resolving it became the main addition of the revision.

W2 / Q3. A new rule closes the gap between the existence of a good α\alpha and finding it without spectral information. You are right that the procedure of the submission could not be trusted: Algorithm 1 looks at the iteration once, for a few steps, and what it sees then need not last (new App. G.9). The revision adds Algorithm 2 (App. G.10; general comment, item 1): in every step it recomputes αk\alpha_k 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. A practitioner can trust it for three reasons:

  1. Convergence does not depend on what it selects. αk∈[0,12)\alpha_k\in[0,\tfrac12) in every step, and the iteration converges for every such sequence: globally for FNE maps, locally under Assumption 1 (Proposition 9).
  2. It is exact in the model case. For an affine map whose residual is carried by one conjugate pair it returns the optimal α⋆\alpha^\star of Lemma 1, and αk=0\alpha_k=0 (plain T2T^2) if the pair violates the criterion or the Jacobian is symmetric.
  3. It realizes the benefit of the fixed filter. Median speedup over T2T^2 in operator calls, 20 random starts per map:
fixed α\alpha of Table 1 (spectrum or grid)Algorithm 1Algorithm 2 (new)
Quad-OT 6×51.89×1.03×; more calls than T2T^2 in 8 of 20 runs1.85×; fewer calls in all 20
Quad-OT 50×501.18×falls back in 20 of 201.33×; fewer calls in all 20
Iris OT1.26×falls back in 20 of 201.32×; fewer calls in all 20
FNE controls (no gain on these maps)–up to 102% more callsat most 0.43% more

So the rule now obtains the gain of the fixed filter on these maps, also where the search had fallen back, and on all 484 runs on the paper's instances and on new problems it never needs more than 1.63% more calls than T2T^2. There is no rate guarantee: the gain depends on the spectrum, and in synthetic stress tests, some of them adversarial, the largest loss we found is 12.2% (App. G.10).

W1. We agree that the scope is restricted; with the rule, a user need not know whether a problem is in scope. The restriction is the content of the theory: only slow modes that rotate can be damped (Theorem 2, the criterion of Ha & Kim), and on FNE maps the gain is at most B(ρ)<3/2B(\rho)<3/2 (our Proposition 2). New App. G.11 applies the untuned rule to 100 runs outside the paper's instances. Wherever the Jacobian spectrum predicts a gain, the rule needs fewer calls (22 of 22 runs): up to 7.66× for momentum methods with over-estimated momentum, 3–12% for Douglas–Rachford on basis pursuit. Where the theory rules out a gain (PageRank on graphs with up to 876k nodes, LASSO), it needs exactly the calls of the unfiltered method in 29 of 30 runs.

Q1. Seven instances are supported by the theory; the larger OT instances are only consistent with it (new App. G.12). Supported: the seven instances of Table 1 that satisfy the assumptions (affine and power maps, small OT); predicted and measured speedups agree within 5% on six (97 vs. 87 on the seventh). Consistent only, reported as empirical: the two 50×50 OT instances and n=m=200n=m=200, where the assumptions fail (unit eigenvalues). The speed of Algorithm 2 is empirical beyond the model case; its momentum speedups are 1.00–1.16 times the predicted ones (8 runs).

Q2. Choose PAPF when operator evaluations dominate the cost and the slow modes may rotate. With Algorithm 2 it is then a wrapper without parameters, with O(d)O(d) memory and global convergence for every FNE map without a safeguard. The rule adds O(d)O(d) arithmetic per step, so where a step of TT is cheap, as for PDHG, saved calls need not be saved time (on Quad-OT 50×50 they are not). In calls, none of the accelerators of Table 3 (Anderson, Halpern, inertial KM, TKMA) speeds up the three OT maps (at most 0.67 times the speed of T2T^2; the rule: 1.35–1.87× at the default starts). It is not a general-purpose accelerator: other methods remain better in specific cases, which the paper reports (Anderson on the power method, TKMA on PageRank, relaxed KM for phases beyond about 109.5∘109.5^\circ, extrapolated Chambolle–Pock on OT).

In short, relative to the version you rated: (i) parameter selection no longer rests on a one-time observation and has a convergence guarantee; (ii) the method can be applied without knowing the spectrum, at a cost of at most 1.63% more operator calls in 484 runs; (iii) App. G.12 separates supported from empirical results. We hope this resolves your main concerns and would be grateful if you would reconsider your assessment.

What I considered in my first review was whether the adaptive parameter selection could lead to meaningful improvements, even from the perspective of users who do not know the spectrum.

In particular, it is concerned whether the coefficients selected for a short observation interval would remain effective in following convergence process. Nevertheless, I accept that your revision adequately addresses the main concerns I asked, regarding the reliability of selection and its practical applicability.

  • Fisrt, The Algorithm 2 addresses the limitations of first version of the method that depends on an one short observation by updating the mixing coefficients at each step using residuals. It was helpful that it operates without a separate parameter search or additional operator calls and also guarantees convergence under the given conditions.
  • Second, due to explanation between cases directly supported by theory and larger OT cases that must be interpreted as empirical results, I gained a explicit understanding of the relationship between theory and experiments.

Adding to this, additional validation of problems over the existing experiments and the explanation that PAPF can be considered when operator evaluation costs are high also helped in assessing its practical value.

I appreciate that improving the explanation and method, conducting many additional, thorough experiments on questions. Thanks to these efforts, I could have clearer understand both the contributions and limitations of the paper, resulting more positive evaluation on this paper. I think this is a good paper by linking theoretical analysis to practical application.

In conclusion, I would like to update the rating from 2 to 3(weak accept).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision (to all reviewers and the AC)

We thank the three reviewers for their careful reviews. A revised PDF is uploaded (changes in blue). It makes three changes.

1. A new rule selects the parameter without a search and without spectral information (all reviewers). All three reviews find Algorithm 1 unreliable: its search costs 140 operator calls, can miss a good parameter, and can accept a harmful one. New App. G.9 shows why: it looks at the iteration once, and the outcome depends on when. New App. G.10 adds Algorithm 2, which looks in every step: a least-squares fit to the residuals of the last three steps gives two eigenvalue estimates of the squared Jacobian, and αk\alpha_k is the best parameter for them (the closed form of Lemma 1 for a conjugate pair). It needs no spectral information, no search, no tunable constant and no extra operator call.

  • Guaranteed (Proposition 9). αk∈[0,12)\alpha_k\in[0,\tfrac12), and the iteration converges for every such sequence: globally for firmly nonexpansive (FNE) maps, locally under Assumption 1. For an affine map whose residual is carried by one conjugate pair, the rule returns the optimal α⋆\alpha^\star of Lemma 1, and 00 (plain T2T^2) if the pair violates the criterion or the Jacobian is symmetric.
  • Measured. Median speedup over T2T^2 in operator calls:
fixed α\alpha of Table 1 (from the spectrum or a grid)Algorithm 1 (submission)Algorithm 2 (new)
Quad-OT 6×5, 20 starts1.89×1.03×; more calls than T2T^2 in 8 runs1.85×; fewer calls in all 20
Quad-OT 50×50, 20 random dual starts1.18×falls back in 20 of 201.33×; fewer calls in all 20
Iris OT, 20 random dual starts1.26×falls back in 20 of 201.32×; fewer calls in all 20
Power-method and synthetic instances, 180 runs9–88×4.4–12.8×8.8–79×
FNE controls (no gain on these maps), 60 runs–up to 102% more callsat most 0.43% more

Without the spectrum, the rule needs 0.88–1.20 times the calls of the best fixed parameter at the default starts of the paper's nine instances (Table 15), and it gains where the search fell back. Where no gain exists it costs little: in 384 runs (the paper's instances with random starts and controls, 25 new OT instances) it needs fewer calls than T2T^2 in 316 and at most 0.43% more in the others.

2. Theorem 2 is now attributed to Ha & Kim (AISTATS 2022); Reviewer DdqP is right. For a deterministic map our filter is Lookahead with k=2k=2, and Theorem 2 is the case k=2k=2 of their Proposition 1. The revision says so in the abstract, Section 1, the contribution list, the header of Theorem 2, the conclusion and App. A. The contributions are restated as what the paper adds for nonexpansive fixed-point maps: the sharp cap B(ρ)<3/2B(\rho)<3/2 for FNE maps (Proposition 2), the equal-cost comparison with relaxed KM (Proposition 3), and the choice of the parameter from residuals (Algorithms 1 and 2).

3. Evidence outside the paper's instances (all reviewers). New App. G.11 applies the untuned rule to 100 runs outside the paper's instances: PageRank on SNAP graphs, heavy ball, Nesterov and Douglas–Rachford on LIBSVM data, OT between MNIST digits, and basis pursuit on random instances. Wherever the Jacobian spectrum predicts a gain, the rule needs fewer calls (22 of 22 runs): up to 7.66× for heavy ball and 10% for Nesterov with over-estimated momentum on logistic regression, and 3–12% for Douglas–Rachford on basis pursuit (predicted: 13%, the cap of Proposition 2). Where the theory rules out a gain (PageRank on SNAP graphs with up to 876k nodes; Douglas–Rachford for the LASSO), it needs exactly the calls of the unfiltered method in 29 of 30 runs. Over the 100 runs it needs more calls than the unfiltered method in 27, by at most 1.63%; Algorithm 1 in 93, by up to 137%. New App. G.12 lists which results of the paper the theory certifies.

Limits, as stated in the paper. The rule has no rate guarantee, and the gain depends on the spectrum: on 25 new OT instances its median is 3% (best fixed parameter of a hindsight grid: 1%; Table 18). In synthetic stress tests, some of them adversarial, the largest loss we found is 12.2% (App. G.10). The rule adds O(d)O(d) arithmetic per step (1.02–3.4 times the time of a T2T^2 step on the three maps we timed in MATLAB), 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 T2T^2. Its ingredients are known and cited in App. A (Manteuffel 1978; Iutzeler & Hendrickx 2019; Poon & Liang 2019).

Unchanged: the title, Algorithm 1, Tables 1–10. The main text is 10 pages; the abstract is edited (attribution, contributions, the rule). The rule, Proposition 9 and its proof take two pages of App. G.10. Algorithm 1 stays in the main text because the reviews refer to it; in the final version Algorithm 2 and Proposition 9 would move there.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.