acceptodds
Under review as a conference paper at ICLR 2027

Wasserstein Saddle-Free Newton: Saddle Escape and Local Spectral Convergence

Abstract

Extending saddle-free Newton methods to Wasserstein space requires controlling Hessian dependent operators along nonlinear transport trajectories and accounting for a Hessian spectrum that may accumulate at zero. We address these challenges through Wasserstein Saddle-Free Newton (WSFN), a second-order method for nonconvex optimization over Wasserstein space that preconditions the Wasserstein gradient by a regularized inverse squared Hessian operator. The resulting dynamics exploit curvature magnitude without reversing the repulsive effect of negative curvature, while retaining attraction along positive curvature directions, thereby avoiding a fundamental limitation of standard Wasserstein Newton dynamics. Whereas previous Wasserstein saddle escape results rely on perturbed first-order dynamics, WSFN uses curvature both to modify the deterministic transport and to construct the perturbation mechanism. Our analysis combines stability estimates for Hessian operators with a perturbative saddle escape argument to establish polynomial time convergence to approximate second-order stationarity under regularity of landscape assumptions. The contribution of the saddle curvature parameter improves from for prior perturbed first-order Wasserstein methods to . For benign landscapes, this further implies proximity to the set of global minimizers. The cubic dependence corresponds to the scale of the objective decrease that can be guaranteed from negative curvature under Lipschitz Hessian regularity. Near a minimizer, the possible absence of a uniform spectral gap prevents a uniform contraction result and instead calls for a spectral characterization. We prove geometric contraction of the linearized dynamics on positive curvature spectral bands bounded away from zero and polynomial decay under spectral source conditions. Together, these results connect quantitative saddle escape with the local spectral behavior of second-order Wasserstein dynamics.

Primary area:
optimization
Keywords:
Wasserstein optimization, saddle-free Newton, saddle point escape, second-order methods

Reviews

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

The paper introduces Wasserstein Saddle-Free Newton (WSFN), extending saddle-free Newton methods to optimization over probability measures. The authors establish a saddle-escape complexity bound of O~(ε−2+δ−3)\widetilde O(\varepsilon^{-2}+\delta^{-3}), improving the saddle-dependent contribution of previous first-order methods. They also characterize the local spectral convergence of the linearized dynamics. Numerical experiments illustrate the proposed method on several Wasserstein optimization problems.

Critical strengths

The extension of saddle-free Newton methods to Wasserstein space is mathematically interesting. In particular, the analysis of Hessian-dependent operators along nonlinear transport trajectories is technically nontrivial, and the improved saddle-escape bound represents a theoretical contribution under the stated assumptions.

Critical weaknesses

1. Restrictive assumptions and questionable applicability.

My main concern is Assumption 4.5, which appears substantially stronger than standard Hessian Lipschitz regularity.

In particular, if I am correct, its first inequality seems to force ∇∇μF(μ,⋅)\nabla\nabla_\mu F(\mu,\cdot) to be spatially constant μ\mu-almost everywhere. To see this, take μ=ν=(δa+δb)/2\mu=\nu=(\delta_a+\delta_b)/2 and consider the coupling

+\frac{t}{2}(\delta_{(a,b)}+\delta_{(b,a)}).$$ Assumption 4.5 then implies $$|\nabla\nabla_\mu F(\mu,a)-\nabla\nabla_\mu F(\mu,b)| \le L_M\sqrt{t}|a-b|.$$ Letting $t\to0$ forces equality of the two Hessians. The same argument extends to general measures. This excludes many standard Wasserstein objectives, including simple potential energies with nonconstant spatial Hessians, and apparently the regularized Coulomb MMD used in the main experiments. The examples provided to justify the assumptions essentially reduce to optimization over the mean of the distribution, with a vanishing multiplication Hessian. This raises serious doubts about the applicability and significance of the main theoretical guarantees. **2. Limited practical motivation and computational guarantees.** The motivation for using a computationally expensive second-order method is not sufficiently convincing. First, the complexity analysis counts exact Wasserstein transport steps without accounting for the cost of Hessian preconditioning or its numerical approximation. Consequently, the claimed improvement does not establish an actual computational advantage over first-order methods. Second, although the saddle-dependent contribution improves from $\widetilde O(\delta^{-4})$ to $\widetilde O(\delta^{-3})$, the total bound remains dominated by $\widetilde O(\varepsilon^{-2})$. Under the required regime $\varepsilon\lesssim\delta^2$, the leading complexity remains $\widetilde O(\delta^{-4})$. This substantially limits the significance of the improvement emphasized in the abstract. The numerical experiments also provide mixed evidence regarding wall-clock performance. Overall, it remains unclear when or why WSFN should be preferred to simpler first-order approaches. **3. Presentation** The manuscript is particularly lengthy and difficult to follow. Given that the underlying saddle-free Newton principle and much of the spectral analysis are already well established, the presentation could more clearly distinguish genuinely new Wasserstein-specific contributions from adaptations of existing theory. Moreover, I question whether the manuscript, in its current form, is well suited to a conference submission. Since the contributions are primarily theoretical, a careful verification of the mathematical arguments is particularly important. However, given the extensive appendices and the limited reviewing period, it seems difficult for reviewers to thoroughly assess the correctness of all the proofs. This raises concerns about whether the manuscript can receive the level of mathematical scrutiny it requires within the conference review process.
Questions for authors

Q1. Is the implication identified above for Assumption 4.5 correct? If so, can the authors provide meaningful Wasserstein optimization problems with nonconstant spatial curvature satisfying the assumptions, and clarify whether the theory applies to their numerical examples?

Q2. Can the authors provide an end-to-end computational complexity analysis accounting for the Hessian preconditioning step, or otherwise demonstrate a convincing computational advantage over first-order Wasserstein methods?

3 comments
AuthorsOpenReview ↗

Assumption 4.5 and applicability (Weakness 1 and Question 1)

We thank the reviewer for identifying an important restriction in Assumption 4.5 and for asking us to clarify the significance and scope of the results. The spatial constancy implication is correct. We address it directly below, together with the revised examples, additional experiments, and a clearer account of what the complexity result shows.

Because Assumption 4.5 is over every coupling, its first inequality forces a substantive restriction. Hence, an example with a nonconstant spatial multiplication Hessian cannot satisfy the assumption as stated. As suggested by the reviewer, we stated this implication explicitly in the revised paper.

Spatial constancy of MμM_\mu does not imply convexity of the objective or eliminate the need for saddle escape. Indeed, under Assumption 4.2, Mμ=0M_\mu=0 at critical measures in the relevant sublevel set, so Hμ=KμH_\mu=K_\mu and any negative curvature at such points comes entirely from KμK_\mu. The Gaussian Coulomb MMD example in Appendix B.1 explicitly exhibits this mechanism. Its nonglobal critical measures have a strictly negative eigenvalue of KμK_\mu, while MμM_\mu need not vanish away from criticality.

We would also like to highlight that these Hessian coupling conditions also appear in Yamamoto et al. (2025, Assumption 3, (13)-(14)): equation (14) is the same multiplication Hessian bound, and equation (13) is the corresponding integral kernel bound. Therefore, our improved saddle contribution is obtained without strengthening these Hessian coupling conditions relative to PWGF. This places the comparison within an existing regularity setting, while leaving the applicability restriction to be acknowledged explicitly.

Replacing the L2L^2 transport displacement by its L∞L^\infty counterpart would allow spatially varying curvature, provided measure dependence is controlled as well. However, this would give operator norm continuity in L∞L^\infty displacement, whereas our localization and Gaussian perturbation estimates control L2L^2 displacement. In particular, the Gaussian perturbation tool may fail. For instance, with μ=N(0,1)\mu=N(0,1) \begin{equation} \xi(x)=Zx,\quad Z\sim N(0,1), \end{equation} satisfies ∥ξ∥Lμ2=∣Z∣<∞\|\xi\|_{L^2_{\mu}}=|Z|<\infty, whereas ∥ξ∥Lμ∞=∞\|\xi\|_{L^\infty_{\mu}}=\infty almost surely. We also highlight the role of Lemma D.5, established by Kim and Suzuki (2024), which applies to L2L^2-valued Gaussian random elements. Therefore, a direct assumption substitution in the present proof would require both different perturbation tools and analysis. Relaxing these conditions remains an important direction.

The revision demonstrates that this restricted class nevertheless contains nonconvex problems with a nonzero multiplication Hessian and dependence on more than the mean. Appendix B.1 considers Coulomb MMD between Gaussian laws whose mean and variance depend on a latent law μ\mu. In particular, MμM_\mu is spatially constant but need not vanish. The model has strict saddles because at a nonglobal critical point, the transport field is a negative curvature eigenvector (Proposition B.12). Proposition B.9 verifies Assumptions 4.4, 4.5 globally, while Propositions B.11-B.14 verify gradient and Hessian control, and benignity on sublevels with confined variance.

In the revised manuscript, Section 5 presents the Gaussian Coulomb MMD experiment analyzed in Appendix B.1, replacing the original Coulomb MMD experiment. We verify Assumptions 4.2–4.5 for this model, but also for the matrix decomposition example in Appendix B.4, whose numerical results are presented in Appendix C.2. For both examples, the reported comparisons show that WSFN’s reduction in transport updates is accompanied by shorter elapsed times to reach small losses.

AuthorsOpenReview ↗

Complexity and computational evidence (Weakness 2 and Question 2)

We agree that counting exact Wasserstein transport steps does not provide an end-to-end computational advantage, and that the large gradient contribution still determines the leading order under ε≲δ2\varepsilon\lesssim\delta^2. This type of condition is typical for saddle escape analysis (see Theorem 5.2 in Yamamoto et al. (2025) and the observation they make in footnote 2).

Thus our improvement is in the cost of saddle episodes. With βsad=Θ(δ2)\beta_{\mathrm{sad}}=\Theta(\delta^2) and a stepsize τsad\tau_{\mathrm{sad}} independent of δ\delta, WSFN reduces the number of transport steps per episode from O~(δ−1)\widetilde O(\delta^{-1}) to O~(1)\widetilde O(1), while keeping an objective decrease of order Ω~(δ3)\widetilde\Omega(\delta^3).

Appendix I describes this fact. Proposition I.1 shows that the cubic available objective decrease scale is sharp, not that δ−3\delta^{-3} is an iteration complexity lower bound. Proposition I.2 constructs examples requiring Ω(ε−2)\Omega(\varepsilon^{-2}) steps in our large gradient phase under its stated stepsize restriction, with uniform regularity constants and a bounded initial objective gap. Thus this contribution cannot be uniformly improved for that phase under the present assumptions.

Note, however, that this is not an impossibility statement about other algorithms. As discussed in Remark 4.7, cubic regularization may provide a route to a total bound of O~(ε−3/2)\widetilde O(\varepsilon^{-3/2}) transport steps. This approach would define each update through a regularized optimization subproblem, instead of the explicit update (1), and would require addressing how that subproblem is solved. Proving such a guarantee in Wasserstein space remains a challenging direction for future work.

To test the saddle escape mechanism directly, the new Appendix C.4 and Figure 6 vary the negative curvature while keeping a positive curvature direction fixed. Across WSFN-PWGF paired trials, the two transports receive identical Gaussian perturbations and objective decrease thresholds. As δ\delta decreases, median WSFN acceptance times increase very slightly, whereas the matched PWGF crossing times increase very sharply (Panel A). Controls with fixed β\beta or a stepsize proportional to δ\delta recover the slowdown observed for PWGF. These results support the saddle episode mechanism we proved theoretically. However, they do not establish a global complexity bound or a wall-clock advantage.

The revised Section 5 also uses an exact representation for applying the full Hessian preconditioner to the gradient. It reports earlier WSFN progress in updates and favorable elapsed time behavior in this particular model. This identifies one setting in which preconditioning is inexpensive, but it is not evidence of general computational superiority.

The new experiments provide evidence of faster saddle escape in a controlled setting (Appendix C.4) and shorter elapsed times to reach small losses in the example of Section 5. These results motivate investigating conditions under which WSFN offers a provable computational advantage. Establishing an end-to-end complexity theorem that accounts for particle approximation, preconditioner application costs, and the accuracy required to preserve our convergence guarantees remains an important direction for future work.

AuthorsOpenReview ↗

Presentation and Wasserstein contribution (Weakness 3)

We agree that the central argument should be assessable without navigating an extensive appendix. Thus we have removed several background appendices, which do not affect the main paper, and reorganized the remaining material, reducing the manuscript from 107 to 99 pages while adding new assumption verifications and targeted experiments. The essential reading route is now: the operator estimates in Section 3.2 and Lemmas G.8, G.11, G.12, the localization and escape argument in Lemma H.3 and Propositions H.5 and H.7, and the iteration count in Theorem 4.6. Appendix H provides a proof roadmap.

The saddle-free Newton principle, the Gaussian perturbation construction, and the spectral calculus tools are established ingredients but we would like to highlight two important points.

(1) The saddle-free Newton principle is from Dauphin et al. (2014), who derive the method in finite dimensions and demonstrate its numerical benefits. Our contribution is to formulate and analyze regularized saddle-free Newton dynamics on Wasserstein space, where applying the inverse absolute Hessian requires additional operator level control.

Although ∣Hμ∣=(Hμ2)1/2|H_\mu|=(H_\mu^2)^{1/2} is well defined, it need not have a bounded inverse. Moreover, scalar Lipschitz continuity of the absolute value function does not imply operator Lipschitz continuity of A↦∣A∣A\mapsto |A|. This matters because the escape analysis must compare preconditioners along nonlinear transport trajectories, instead of only characterizing a fixed Hessian.

Therefore, we use (Hμ2+βI)−1/2(H_\mu^2+\beta I)^{-1/2}, which is bounded for every β>0\beta>0, and establish β\beta-dependent stability estimates and a controlled expansion of the preconditioned gradient on a common reference space (Lemmas G.11-G.12). These estimates support the nonlinear saddle escape guarantee. The distinction from ideal saddle-free Newton is summarized above Table 1 and developed in Appendix G.4.

(2) Although spectral tools are classical, their application here characterizes the local behavior of regularized second-order Wasserstein dynamics without assuming a uniform positive Hessian gap. This analysis explains which convergence rates can be expected from WSFN and why its second-order construction alone does not imply classical quadratic Newton convergence. Classical quadratic Newton guarantees rely on suitable regularity and a boundedly invertible local Hessian. In our setting, at an absolutely continuous minimizer, Hμ∗=Kμ∗H_{\mu^*}=K_{\mu^*} is compact on an infinite-dimensional space, so bounded invertibility on the full space is unavailable. Moreover, fixed-regularization WSFN has a different linearization from an exact Newton step as Table 1 shows.

Theorem 4.9 shows that the linearized iterates converge strongly to the kernel projection, while their operator norm remains one. Kernel components are unchanged by the linearized dynamics. If there are infinitely many positive eigenvalues, they accumulate at zero and their contraction factors approach one, precluding a common geometric contraction factor across all positive modes. For a finite-rank Hessian, however, the positive spectral component does contract geometrically. The theorem accordingly provides geometric contraction on positive spectral bands bounded away from zero and polynomial decay under spectral source conditions. These conclusions identify how the infinite-dimensional Hessian geometry governs the effectiveness and limitations of curvature preconditioning.

Appendix G.6 further clarifies the connection with Newton’s method, including quadratic convergence under additional assumptions for a spectrally projected Newton iteration on a fixed positive spectral subspace. The rates in Theorem 4.9 concern the linearization and transferring them to nonlinear WSFN requires the additional structural control discussed in Remark 4.10.

We would appreciate a reassessment in light of these explicit assumption verifications, the targeted saddle escape evidence, and the clarified scope of the theoretical contribution.

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

Paper proposes Wasserstein Saddle-Free Newton (WSFN) for nonconvex optimization over probability measures. The update uses the regularized preconditioner (Hμ2+βI)−1/2(H_\mu^2+\beta I)^{-1/2}, where HμH_\mu is the Wasserstein Hessian. Its linearization contracts positive-curvature directions while keeping negative-curvature directions unstable. Near a point with small gradient norm, the algorithm adds Gaussian perturbations with covariance Kμ2K_\mu^2, where KμK_\mu is the integral component of the Hessian.

The main result is a high-probability guarantee for reaching an (ε,δ)(\varepsilon,\delta)-approximate second-order critical point in

O~(Fmin⁡(ε−2+δ−3))\widetilde O\left(F_{\min}(\varepsilon^{-2}+\delta^{-3})\right)

exact measure-valued transport steps, under the stated regularity and parameter conditions. Compared with PWGF (Yamamoto et al., 2025), the saddle-related term improves from O~(δ−4)\widetilde O(\delta^{-4}) to O~(δ−3)\widetilde O(\delta^{-3}). This comes from shorter saddle episodes, not a larger guaranteed decrease per episode. With an additional benign-landscape assumption, the output is close to the global minimizer set.

The paper also analyzes local linearized dynamics near a minimizer. It proves geometric contraction on positive spectral bands separated from zero and polynomial decay under source conditions. These results do not establish corresponding convergence rates for the nonlinear iteration.

The experiments use finite-particle implementations with Lanczos approximations. WSFN often improves loss per update, although the wall-clock results are mixed. The numerical experiments do not implement the full perturbation and stopping procedure analyzed in the theorem.

Critical strengths

1. The nonlinear saddle-escape analysis is the strongest part of the paper.

The spectral multiplier is straightforward to understand, but it only describes the frozen linearization. The harder problem is showing that the unstable direction still produces escape when the Hessian and preconditioner change along the transport trajectory.

The authors address this by comparing operators on a common reference space, bounding the variation of the preconditioner, and controlling the nonlinear error during saddle episodes. I found this part more convincing than the spectral motivation alone.

Relative to PWGF, the deterministic transport now uses the full Hessian rather than leaving curvature information only in the perturbation mechanism. The analysis needed to make that change work is a meaningful theoretical contribution.

2. The paper gives a useful account of what curvature normalization can actually improve.

The authors separate the number of steps needed to amplify a negative-curvature direction from the amount of objective decrease available near a saddle. This explains why the episode duration improves while the cubic decrease scale remains.

I also appreciate that authors state the limits of the local spectral result and do not claim nonlinear convergence rates from the linearized estimates alone.

Critical weaknesses

1. Assumption 4.5 seems to restrict the multiplication Hessian much more than the paper discusses.

Let

Aμ(x)=∇∇μF(μ,x).A_\mu(x)=\nabla\nabla_\mu F(\mu,x).

In Assumption 4.5, the first inequality must hold for every coupling γ∈Π(μ,ν)\gamma\in\Pi(\mu,\nu). Take ν=μ\nu=\mu and consider

γt=(1−t)(Id,Id)♯μ+t(μ⊗μ),t>0.\gamma_t = (1-t)(\mathrm{Id},\mathrm{Id})_{\sharp}\mu+ t(\mu\otimes\mu), \qquad t>0.

Its transportation cost satisfies

=t\iint\|x-y\|^2\,d\mu(x)d\mu(y) \longrightarrow0.$$ However, for any $t>0$, the $\gamma_t$-essential supremum of $\|A_\mu(y)-A_\mu(x)\|$ still includes the full $\mu\otimes\mu$ component. Its value is therefore independent of $t$. Under the natural lifted interpretation of the norm, Assumption 4.5 forces $$A_\mu(x)=A_\mu(y) \quad \mu\otimes\mu\text{-a.e.}$$ In other words, $M_\mu(x)$ must be spatially constant almost everywhere. The authors acknowledge that Assumption 4.5 is stronger than ordinary spatial Lipschitz continuity, but this consequence is not discussed. The explicit examples in Propositions B.6 and N.1 both have $M_\mu=0$. This also raises a question about the experiments. For example, the multiplication component of the regularized Coulomb MMD Hessian in Appendix C generally depends on particle position, as seen from Equation (4). I am therefore unsure which of the numerical objectives are covered by the global theorem. I consider this an applicability concern rather than a demonstrated proof error, but it matters for my assessment. **2. The saddle-escape improvement is real, but its effect on the total bound and practical cost is limited.** The improvement from $\widetilde O(\delta^{-4})$ to $\widetilde O(\delta^{-3})$ concerns the saddle-episode contribution. Theorem 4.6 also requires approximately $$L_H\varepsilon\lesssim\delta^2.$$ Thus, in the admissible regime, $$\varepsilon^{-2}\gtrsim\delta^{-4}.$$ The large-gradient term still determines the leading polynomial order of the total transport-step bound. The authors acknowledge this in Remark 4.7 and Appendix N, so I do not consider it an omission. It does make the headline improvement less consequential for the full optimization problem. I am also not convinced that fewer transport steps necessarily mean a computational advantage. Each WSFN step requires an inverse-square-root Hessian action, which is approximated with Lanczos iterations in the experiments. The extra cost often offsets the improvement per update. The experimental results are mixed. WSFN performs well on the regularized Coulomb MMD example, but in-context feature learning strongly favors first-order methods in elapsed time. The ResNet and matrix-decomposition experiments also show that better progress per update does not consistently lead to better runtime. Finally, these experiments do not directly test the predicted dependence of saddle-episode duration on $\delta$. They use prescribed perturbations rather than Algorithm 1's stopping and acceptance rules.
Questions for authors
  1. Could the authors clarify the effective scope of Assumption 4.5? (can the authors give an example with a nonconstant multiplication Hessian that still meets the assumptions, or explain why such an example is not needed for their target applications?)
  2. Can the authors provide evidence that isolates the claimed saddle-escape mechanism? The main gain is the reduction of saddle-episode duration from O~(δ−1)\widetilde O(\delta^{-1}) to O~(1)\widetilde O(1). A controlled example with a tunable negative-curvature eigenvalue would be useful. I would be interested in the measured episode length as δ\delta changes, ideally comparing WSFN with PWGF under the actual stopping and acceptance rules.
3 comments
AuthorsOpenReview ↗

Assumption 4.5 and coverage of the experiments (Weakness 1 and Question 1)

We thank the reviewer for recognizing the saddle escape improvement and for identifying two points that require clearer evidence, namely the effective scope of Assumption 4.5 and a controlled test of the episode duration prediction. We address both below.

We agree with the coupling argument. Assumption 4.5 forces ∇∇μF(μ,⋅)\nabla\nabla_\mu F(\mu,\cdot) to be spatially constant μ\mu-almost everywhere. An example with a spatially nonconstant multiplication coefficient cannot satisfy the assumption as stated. We made this implication explicit in the revised paper. Spatial constancy does, however, allow a nonzero coefficient that depends on μ\mu.

The same Hessian coupling conditions appear in Yamamoto et al. (2025, Assumption 3, (13)-(14)). Therefore, our comparison with PWGF retains these regularity conditions. We acknowledge their restrictive scope in interpreting both results.

Replacing the L2L^2 transport displacement by its L∞L^\infty counterpart would allow spatially varying curvature, provided measure dependence is controlled as well. However, this would give operator norm continuity in L∞L^\infty displacement, whereas our localization and Gaussian perturbation estimates control L2L^2 displacement. In particular, the Gaussian perturbation tool may fail. For instance, with μ=N(0,1)\mu=N(0,1) \begin{equation} \xi(x)=Zx,\quad Z\sim N(0,1), \end{equation} satisfies ∥ξ∥Lμ2=∣Z∣<∞\|\xi\|_{L^2_\mu}=|Z|<\infty, whereas ∥ξ∥Lμ∞=∞\|\xi\|_{L^\infty_\mu}=\infty almost surely. We also highlight the role of Lemma D.5, established by Kim and Suzuki (2024), which applies to L2L^2-valued Gaussian random elements. Therefore, a direct assumption substitution in the present proof would require both different perturbation tools and analysis. Relaxing these conditions remains an important direction.

The revised Appendix B.1 provides a nonconvex example with nonzero multiplication Hessian. It minimizes Coulomb MMD between Gaussian output laws whose mean and variance depend on the latent law μ\mu. At nonglobal critical points, KμK_\mu has a strictly negative eigenvalue (Proposition B.12). Thus, a constant or vanishing multiplication component does not make the objective convex or remove the saddle escape mechanism. Negative curvature can come entirely from KμK_\mu.

This Gaussian MMD objective replaces the Coulomb MMD objective in the original main experiment, and satisfies the assumptions. Proposition B.9 verifies Assumptions 4.4, 4.5 globally. Propositions B.11-B.14 prove Assumptions 4.2, 4.3 on confined sublevels, with sufficiently small stationarity thresholds. Appendix B.4 additionally verifies the assumptions for another example, namely the matrix decomposition objective tested in Appendix C.2. These results establish coverage of the objectives and initial sublevels.

AuthorsOpenReview ↗

Test of the saddle escape mechanism (Weakness 2 and Question 2)

We have added the requested controlled experiment in Appendix C.4 and Figure 6. For μ∈P2(R2)\mu\in\mathcal P_2(\mathbb R^2), it uses \begin{equation} F_\delta(\mu)=\gamma^3\left[\cos\left(\frac{m_{\mu,1}}{\gamma}\right)-1\right]+\frac12m_{\mu,2}^2, \quad \gamma=2\delta.
\end{equation} At the initial measure μˉ=N(0,I2)\bar\mu=\mathcal N(0,I_2), the negative and positive translation eigenvalues are −2δ-2\delta and 11, respectively. The Hessian Lipschitz constant is one uniformly in δ\delta. Thus, the experiment weakens the negative curvature while keeping a positive curvature direction fixed.

Across δ=2−j\delta=2^{-j}, j=3,…,11j=3,\ldots,11, we use paired trials for WSFN and PWGF. Both receive the same Gaussian field with covariance Kμˉ2K_{\bar\mu}^2, the same kick amplitude, and the same objective decrease threshold. With βsad=δ2\beta_{\mathrm{sad}}=\delta^2 and τsad=12\tau_{\mathrm{sad}}=\frac{1}{2}, their linearized unstable multipliers are \begin{equation} a_{\mathrm{WSFN}}=1+\frac1{\sqrt5}, \quad a_{\mathrm{PWGF}}=1+\delta.
\end{equation} The predicted distinction is uniform amplification for WSFN versus increasingly slow amplification for PWGF.

WSFN uses the episode parameters from Appendix H.2 and the acceptance rule of Algorithm 2. It tests the decrease relative to the stored pre-perturbation objective immediately after the kick and after each update, accepts the first successful state, and returns the stored measure if its budget expires.

All trials reach their thresholds within their respective budgets. Across the nine curvature values, the log-log slope of the ratio of the median counts against δ−1\delta^{-1} is approximately 0.9910.991. The slow growth in WSFN counts is consistent with the logarithmic factors hidden in O~(1)\widetilde O(1) (Panels A and B).

We distinguish these measurements from PWGF's scheduled decision. Figure 6 Panel D separately implements a scheduled PWGF episode with its own kick and threshold parameters and post-kick reference test. All scheduled decisions succeed. Figure 6 Panel C also shows that fixing β\beta or taking a WSFN stepsize proportional to δ\delta restores the slowdown observed for PWGF. These controls isolate the roles of curvature scaled β\beta and a stepsize independent of δ\delta.

AuthorsOpenReview ↗

Total complexity and elapsed time (Weakness 2)

We agree that, under the admissible relation LHε≲δ2L_H\varepsilon\lesssim\delta^2, the large gradient contribution remains dominant. This type of condition is typical for saddle escape analysis (see Theorem 5.2 in Yamamoto et al. (2025) and the observation they make in footnote 2). We emphasize that our improvement concerns episode duration, from O~(δ−1)\widetilde O(\delta^{-1}) to O~(1)\widetilde O(1), and hence the saddle contribution, from O~(δ−4)\widetilde O(\delta^{-4}) to O~(δ−3)\widetilde O(\delta^{-3}).

Proposition I.1 shows that the cubic available objective decrease scale is sharp, but we do not claim that δ−3\delta^{-3} is an iteration complexity lower bound. Proposition I.2 constructs examples requiring Ω(ε−2)\Omega(\varepsilon^{-2}) steps in our large gradient phase under its stated stepsize restriction, with uniform regularity constants and a bounded initial objective gap. Thus this contribution cannot be uniformly improved for that phase under the present restriction.

Note, however, that this is not an impossibility statement about other algorithms. As discussed in Remark 4.7, cubic regularization may provide a route to a total bound of O~(ε−3/2)\widetilde O(\varepsilon^{-3/2}) transport steps. This approach would define each update through a regularized optimization subproblem, instead of the explicit update (1), and would require addressing how that subproblem is solved. Proving such a guarantee in Wasserstein space remains a challenging direction for future work.

The theoretical contribution is the control of nonlinear Wasserstein trajectories needed to justify a saddle stepsize independent of δ\delta while retaining the cubic objective decrease guarantee. The linearized multiplier alone would not establish this result.

We also agree that fewer transport updates do not automatically imply lower computational cost. In the revised Gaussian example, the full preconditioner action on the gradient uses an exact eigendecomposition. In the scalar matrix example, it reduces to a scalar expression. Neither requires Lanczos. In both examples, the observed reduction in updates also translates into shorter elapsed times to reach small losses under the reported parameters. These results identify settings where the curvature structure makes preconditioning inexpensive.

The new experiments provide evidence of faster saddle escape in a controlled setting (Appendix C.4) and shorter elapsed times to reach small losses in the example of Section 5. These results motivate investigating conditions under which WSFN offers a provable computational advantage. Establishing results concerning complexity superiority that account for particle approximation, preconditioner application costs, and the accuracy required to preserve our convergence guarantees remains an important direction for future work.

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

Yamamoto et al. [1] use Hessian-guided stochastic perturbations to escape saddle points in polynomial time under suitable assumptions. However, the deterministic part of their algorithm does not use Hessian preconditioning. In this paper, the authors propose to also use curvature information in the deterministic part, taking inspiration from the Euclidean saddle-free Newton method.

They introduce a new algorithm, Wasserstein Saddle-Free Newton (WSFN). Under suitable assumptions, they prove approximate second-order stationarity and improve the saddle contribution to the iteration bound from O~(δ−4)\widetilde O(\delta^{-4}) to O~(δ−3)\widetilde O(\delta^{-3}). This does not improve the leading total bound in the parameter regime considered. Near a global minimum, they study the linearized dynamics. They show geometric contraction in directions with positive curvature bounded away from zero, and polynomial decay under additional conditions when positive curvatures can approach zero. These results do not directly give convergence rates for the full nonlinear algorithm. They illustrate the behavior of numerical variants of WSFN compared to PWGF [1], isotropic WGF, WGF, and a scalar control, with additional experiments in the appendix.

Critical strengths

The paper presents a new algorithm that combines Hessian-guided perturbations with Hessian preconditioning of the deterministic transport. I find this combination interesting: curvature information is used both to perturb the current iterate and to improve the subsequent transport. Adapting this idea to Wasserstein space and analyzing the resulting dynamics is a valuable contribution. The improvement in the saddle contribution to the iteration bound is also an interesting theoretical result. Although it does not improve the leading total bound in the regime considered, it gives a quantitative benefit of preconditioning for escaping saddle regions.

Critical weaknesses

• It is hard to assess the practical scope of the theoretical results. There are many different notations, constants, and parameter conditions, which makes it difficult to understand when the guarantees apply. Proposition B.6 gives an explicit example satisfying the assumptions, but it remains unclear to me which assumptions hold in the experimental settings. The setup of Figure 1 is interesting, and an experiment on a problem where the assumptions are verified would help connect the theory to the observed behavior.

• The experiments do not directly validate the main theoretical contributions. The numerical experiments differ from the algorithm analyzed in the paper. In particular, perturbations occur at fixed intervals instead of following the theoretical episode and stopping rules. In the experiments, the preconditioned direction is computed approximately. The authors acknowledge this approximation, but do not quantify its effect on the theoretical guarantees. • The improved saddle escape bound is not directly tested empirically. • Similarly, a comparison between the actual trajectory near a minimum and the predictions of the linearized dynamics would help assess how well the local analysis describes the observed behavior.

Questions for authors

Which of Assumptions 4.2–4.5 are known to hold for the objectives used in the experiments? Could you provide a controlled experiment following the theoretical perturbation and episode rules, ideally on an example with verified assumptions, to assess the predicted saddle escape improvement? Could you provide an experiment comparing the actual WSFN trajectory near a minimum with the trajectory predicted by the linearized dynamics? Would it be relevant to cite and discuss Paternain, Mokhtari, and Ribeiro (2019), “A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points,” which studies a related approach in the Euclidean setting?

6 comments
AuthorsOpenReview ↗

Which assumptions hold and where they are needed (Weakness 1 and Question 1)

We thank the reviewer for these concrete suggestions. We agree that the connection between the assumptions, the algorithm and the experiments should be easier to assess. The revision now includes verified objectives, experiments using the episode controller in Algorithm 1, and tests of both saddle escape and local linearized predictions.

Theorem 4.6 requires Assumptions 4.4, 4.5 globally and Assumption 4.2 on the initial sublevel. Assumption 4.3 is additionally needed for proximity to global minimizers in Corollary 4.8. The local analysis in Theorem 4.9 uses Assumptions 4.4, 4.5 at a fixed absolutely continuous global minimizer. We will add a compact guide distinguishing these requirements and the fixed problem constants from algorithmic parameters.

The two revised optimization examples have the following coverage:

ObjectiveAssumptions 4.2, 4.3Assumptions 4.4, 4.5
Gaussian Coulomb MMD (B.1; Section 5/C.1)Confined sublevels (B.9–B.12)Global (B.7)
Extended matrix decomposition (B.4/C.2)Global (B.18)Global (B.18)

Assumption 4.3 holds for the admissible stationarity thresholds specified in those results.

The Gaussian Coulomb MMD objective in Section 5 replaces the original Coulomb MMD experiment.

AuthorsOpenReview ↗

Agreement with the episode rules and preconditioner computation (Weakness 2)

The revised WSFN implementations in C.1-C.2 follow Algorithm 1. Perturbations are triggered by the small gradient test. Each episode stores the pre-perturbation state, draws a Gaussian field with covariance Kμ2K_\mu^2, and tests the prescribed objective decrease immediately after the kick and after every transport update. The first successful state is accepted. If the budget expires, the algorithm returns the stored state. This replaces the original fixed interval perturbation.

We have also chosen examples with explicit curvature representations. In the Gaussian MMD model (Section 5), the full Hessian preconditioner action on the gradient reduces to an exact eigendecomposition, keeping the multiplication component MμM_\mu. The scalar matrix example uses a closed-form expression. The controlled experiments in C.3-C.4 evaluate the population dynamics directly, without particle or Lanczos approximation. Therefore, these tests isolate the theoretical mechanisms without requiring an accuracy analysis for an iterative matrix solver. A general theorem covering inexact preconditioner actions remains a challenging and important direction for future work.

AuthorsOpenReview ↗

Validation of the saddle episode prediction (Weakness 3 and Question 2)

Appendix C.4 and Figure 6 introduce a controlled family whose saddle has eigenvalues −2δ-2\delta and 11, with Hessian Lipschitz constant one uniformly in δ\delta. Thus negative curvature varies while positive curvature remains fixed. The model has Mμ=0M_\mu=0 and satisfies the boundedness and coupling regularity conditions used in the episode analysis.

We use the per-episode parameter prescription of Appendix H.2, including βsad=δ2\beta_{\mathrm{sad}}=\delta^2 and τsad=12\tau_{\mathrm{sad}}=\frac{1}{2}, and measure actual WSFN acceptance times. Across trials at each curvature value δ\delta, both WSFN and PWGF receive identical Gaussian perturbations and the same objective decrease target. As δ\delta decreases, median WSFN acceptance times increase very slightly, whereas matched PWGF threshold crossing times increase very rapidly (Panel A). The ratio of the median counts has fitted log-log slope 0.9910.991 against δ−1\delta^{-1}, consistent with the predicted additional inverse curvature factor for PWGF (Panel B).

The WSFN unstable multiplier is 1+151+\frac{1}{\sqrt{5}}, whereas the PWGF multiplier is 1+δ1+\delta. Controls with fixed β\beta or a WSFN stepsize proportional to δ\delta restore the slowdown observed for PWGF (Panel C). We distinguish the matched PWGF crossing diagnostic from PWGF's published scheduled acceptance test (see Algorithm 2 in Yamamoto et al. (2025)), which is implemented separately in Figure 6 Panel D. Note that these are single-episode tests of the O~(1)\widetilde O(1) versus O~(δ−1)\widetilde O(\delta^{-1}) duration prediction.

Comments on the paper

5 comments
AuthorsOpenReview ↗

Response to rebuttal acknowledgement

Thank you for considering our response and revisions. We understand the difficulty of assessing extensive additions within the discussion period and will keep this clarification brief.

We agree that Assumption 4.5 remains restrictive. The revised examples show that the assumptions cover explicit nonconvex problems with saddles, including an objective depending on both mean and variance of the measure, with a nonzero multiplication Hessian MμM_\mu. These examples address the request in Question 1 to clarify the applicability of the theory to our numerical examples, by verifying the assumptions for the revised objectives. Although the restriction remains, these verifications show the previously missing connection between the theoretical assumptions and the experiments.

The theoretical contribution is the control of Hessian preconditioning along nonlinear Wasserstein trajectories, giving the improved saddle contribution and the local spectral characterization. The large gradient contribution remains unchanged, and we do not provide an end-to-end computational advantage.

Nevertheless, the shorter elapsed times reported in Section 5 and Appendix C.2 provide evidence of a computational advantage in the tested settings, offering a preliminary empirical response to the alternative requested in Question 2. Together with the controlled saddle escape experiments in Appendix C.4, these findings provide a promising starting point for identifying conditions under which an end-to-end computational advantage can be proved. As discussed in our rebuttal, such an analysis would need to account for particle approximation, preconditioner application costs, and the accuracy required to preserve the convergence guarantees.

The additional example verifications and experiments were introduced to address the applicability and computational questions raised by the reviewer. We appreciate that their inclusion also increases the assessment burden, and take the remaining presentation concern seriously.

To help us address the original soundness concern precisely, could the reviewer identify any particular theorem or assumption verification that remains mathematically questionable? This would help us distinguish a specific issue requiring correction from the remaining concerns about applicability, significance, and presentation, which we recognize are separate.

Thank you for your follow-up and your positive assessment. We are glad that our response addressed most of your concerns, and we appreciate your recommendation to improve the presentation. If there are particular aspects that you think would benefit most from revision, we would be grateful for your suggestions and would be happy to address them.

AuthorsOpenReview ↗

General summary of the discussion period

We thank the reviewers for their feedback and engagement. For ease of assessment, we summarize the main points addressed during the discussion.

  1. Assumptions and verified examples. We explicitly acknowledge that Assumption 4.5 forces spatial constancy of the multiplication Hessian.
  • As explained in the paper and rebuttal, the same Assumption 4.5 was previously used in the analysis of PWGF. Retaining these conditions provides a common basis for comparison and shows that our improved saddle escape guarantee is obtained without strengthening these regularity requirements.

  • We also explained why the proposed relaxation of Assumption 4.5, allowing spatially varying multiplication Hessians does not directly support our perturbation analysis: it requires L∞L^\infty control of transport displacements, whereas our localization and Gaussian perturbation estimates provide L2L^2 control. Our rebuttal also provides a counterexample showing that an Lμ2L^2_\mu-valued Gaussian perturbation can have infinite Lμ∞L^\infty_\mu norm almost surely. Thus, additional assumptions or a new analysis are needed. Therefore, we view Assumption 4.5 as a trade-off within the present proof setting. It restricts the class of admissible objectives while providing the operator norm control that supports the natural L2L^2-Wasserstein localization and Gaussian perturbation analysis.

  • As requested by all reviewers, Appendix B provides assumption verifications for the revised Gaussian Coulomb MMD and matrix decomposition examples. The Gaussian example depends on both mean and variance (not only on the mean) and permits a nonzero multiplication Hessian. These examples illustrate applicability within their setting and connect the assumptions to the revised experiments.

  1. Agreement between the analyzed algorithm and the experiments. The revised experiments in Section 5 and Appendix C.2 use the perturbation triggering the gradient and episode acceptance rules, as requested by two reviewers. Their curvature structure permits explicit preconditioner application, avoiding Lanczos approximations. This addresses the concerns about fixed interval perturbations and uncontrolled preconditioner approximation in the original experiments.

  2. Saddle escape and computational evidence. As requested by two reviewers, Appendix C.4 directly tests the predicted improvement in episode duration as negative curvature decreases, with controls isolating the roles of β\beta and stepsize. Section 5 and Appendix C.2 also report shorter elapsed times to reach small losses in the tested settings. We clarify that the theoretical improvement concerns the saddle contribution, from O~(δ−4)\widetilde O(\delta^{-4}) to O~(δ−3)\widetilde O(\delta^{-3}). The O~(ε−2)\widetilde O(\varepsilon^{-2}) contribution remains unchanged, for the reasons discussed in the paper and in our rebuttal. Although an end-to-end computational complexity theorem remains open, the new experiments provide encouraging evidence in the tested settings and motivate investigating conditions under which WSFN offers a provable computational advantage.

  3. Local spectral predictions. As requested by one reviewer, Appendix C.3 compares nonlinear trajectories with the predicted linearized dynamics and examines nonlinear generation of kernel components.

  4. Contribution and presentation. Our responses clarify the relationship with Euclidean saddle-free Newton methods, including Paternain, Mokhtari, and Ribeiro (2019). As clarified in our rebuttal, the paper’s main contribution is theoretical.

  • The saddle-free Newton principle is from Dauphin et al. (2014), who derive the method in finite dimensions and demonstrate its numerical benefits. Our contribution is to formulate and analyze regularized saddle-free Newton dynamics on Wasserstein space, where applying the inverse absolute Hessian requires additional operator level control. We develop a Wasserstein analysis that controls Hessian operators along nonlinear transport trajectories to prove the improved saddle escape guarantee.

  • Although spectral tools are classical, their application here characterizes the local behavior of regularized second-order Wasserstein dynamics without assuming a uniform positive Hessian gap. This analysis explains which convergence rates can be expected from WSFN and why its second-order construction alone does not imply classical quadratic Newton convergence.

  • To our knowledge, the improved saddle escape guarantee and the accompanying spectral characterization of local linearized convergence are new for regularized second-order methods in Wasserstein space.

  • We acknowledged the remaining presentation concerns and further streamlined the paper, reducing its total length from 107 to 75 pages.

We hope this summary helps the reviewers and area chair assess the contribution, the supporting evidence, and the remaining limitations.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.