acceptodds
Under review as a conference paper at ICLR 2027

W-LALM: A Linearized Augmented Lagrangian Method for Constrained Optimization in Wasserstein Space

Abstract

Many problems in inference, sampling, and scientific calibration require learning a probability law subject to linear expectation constraints. The natural extension of Wasserstein proximal gradient (WPG) to this problem enforces the constraints inside its Jordan–Kinderlehrer–Otto (JKO) subproblem, which can turn an otherwise tractable backward step into a constrained transport problem. Primal–dual sampling methods avoid this difficulty by moving feasibility into a multiplier update, but their guarantees cover averaged or distributional quantities rather than the full primal–dual sequence, and they do not exploit composite objectives whose nonsmooth part admits a tractable JKO resolvent. We propose the Wasserstein linearized augmented Lagrangian method (W-LALM), which keeps the original unconstrained JKO step and handles feasibility through an explicit step on the smooth part of the augmented Lagrangian together with a multiplier update. Our analysis is built on transport plans rather than transport maps, since optimal Monge maps need not exist for the discrete measures used in particle implementations. This representation yields a plan-based Lyapunov descent estimate, convergence of the full primal–dual sequence to a saddle point under generalized-geodesic convexity, and an iteration complexity for the squared residual of a plan-valued Wasserstein Karush–Kuhn–Tucker (KKT) condition that we introduce. W-LALM matches or improves upon the terminal objective of the strongest feasible baseline, while being 8–38 faster than the constrained-JKO variant of WPG and up to two orders of magnitude faster than the Euclidean augmented-Lagrangian baseline.

Primary area:
optimization
Keywords:
Wasserstein optimization, constrained optimization, augmented Lagrangian method, global convergence, iteration complexity

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_67M3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies minimizing V-energy + entropy H(\mu) over Wasserstein space, subject to a linear moment constraint. It proposes W-LALM, a Wasserstein linearized augmented Lagrangian method. Each iteration consists of 3 steps:

  1. an explicit pushforward step on V + linearized multiplier and penalty term;
  2. a JKO step on H alone;
  3. a dual ascent on multipliers.

The theory has 4 parts:

  1. a plan-based Lyapunov descent inequality (Theorem 4.1);
  2. convergence of the whole sequence to a saddle point in weak topology (Themrem 4.2)
  3. a characterization of saddle points by a plan-valued Wasserstein KKT system (Theorem 4.3)
  4. an iteration complexity for a plan-valued KKT residual (Theorem 4.4)

Experiments on two generalized-Bayes calibration problems demonstrate that W-LALM reaches the same objectives as constrained JKO baseline faster. The speedup comes from cheaper inner iteration, not fewer outer iterations.

Critical strengths
  • Keeping the JKO step for H unchanged while moving the constraint into the explicit step is a good design (commonly used in ADMM for Euclidean).
  • The analysis is careful and rigorous. Optimal maps need not exist, and the proof handles this throughout.
  • the first order theory is useful. The plan-valued KKT system proved equivalent to the saddle-point condition gives a checkable stationary notion.
  • Experimental results show the efficiency of the proposed method.
Critical weaknesses
  • Once the glued plan is introduced, the Lyapunov proof is almost a line-by-line transcription of the Euclidean linearized ALM proof. In particular, some Wasserstein ingredients are established, such as the gluing lemma, JKP three-point inequality, the WPG analys pattern of Salim et al (2020). Thus, the paper would be stronger if it mentioned explicitly which steps of the proof requires new ideals/techniques.
  • The linear-mean constraint is very special, because the constraint depends only on the mean, and the Lagrangian is unconstrained composite problem with a slightly modified potential. Would it be able to extend more general settings?
  • The theory assumes exact JKO steps on continuous measures but the implementation differs in the following ways: 1) particle supports are fixed during JKO step with only reweighing, 2) the entropy is replaced by the discrete surrogate, 3) the weight problem is solved with entropic Sinkhorn which is inexact and regularized. These are not covered by the theory developed in this paper.
  • The experiment evaluation is narrow. There are only two datasets, and fewer particles than dimensions, leading to very coarse representation of posterior.
  • No study of how results depends on gamma, rho, beta or Sinkhorn regularization is shown.
  • The only rate is for the KKT residual. For linearized ALM in Euclidean space, one would expect the rates for the objective gap and the feasibility violation.
  • Strong convexity is not used. In Euclidean space, when V is strongly convex, linear convergence would be natural result.
Questions for authors

See the weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 67M3 (Part 1/2)

We thank the reviewer for recognizing the analysis, the KKT characterization, and the computational motivation. We respond to each of the seven concerns in the order of the review.

The questions below summarize the review; the corresponding original labels are retained for reference.


Q1 (Comment 1. New analysis beyond Euclidean linearized ALM).

Identify which proof steps require new work, given the established gluing lemma, JKO inequalities, and WPG analysis.

A1. We agree that gluing, Wasserstein proximal inequalities, and Euclidean ALM identities are established tools. The result here requires combining them for the proposed primal-dual update.

The forward displacement and JKO coupling are glued through a common intermediate measure, then combined with a comparison coupling in a common multi-marginal plan. This gives the Plan EVI adapted to the two-stage update. The ensuing estimates control the primal displacement together with consecutive moment residuals, allowing the Euclidean multiplier update to enter a corrected Lyapunov inequality. The full-sequence argument also uses the Wasserstein weak topology. Lemma C.7 states the Plan EVI, and Theorem C.8 establishes the corrected Lyapunov estimate used in the convergence proof. These identify the update-specific estimates separately from the standard ingredients.


Q2 (Comment 2. The special structure of linear mean constraints).

Explain whether the analysis extends to more general constraints.

A2. The current theory concerns AEμ[X]−b=0A\mathbb E_\mu[X]-b=0. Nonlinear moments give a position-dependent multiplier force, while variance, quantile, and inequality constraints require additional analysis. We have stated the scope of the current guarantees and identified nonlinear constraints as future work in the Conclusion.


Q3 (Comment 3. Exact theory versus the particle implementation).

Fixed support, discrete entropy, and inexact regularized Sinkhorn solves are outside the exact continuous theory.

A3. We agree that fixed support, weight entropy, Sinkhorn regularization, and finite inner accuracy are not covered by the original exact-law theorem. The revised experiments use two entropy-only regression settings and twelve Gaussian moment-model settings.

The entropy Gaussian update is available in closed form. For product-Gaussian input, the second-moment models admit an exact finite-dimensional continuous-JKO reformulation, solved to numerical tolerance. Appendix D.1 also verifies that the diagonal forward map and mean translations preserve product-Gaussianity throughout the iteration. We distinguish this exact reduction from exact numerical solution; the exact-law theorem does not itself provide an inexact-JKO convergence guarantee. Explicit or numerically certified references permit direct checks of means, covariances, W2W_2 distance, feasibility, and KKT residuals. Appendix D.2, Eq. (79), gives the outer Gaussian residual, and Table 5 independently checks one constrained subproblem.


Q4 (Comment 4. Breadth of the experimental evaluation).

Two datasets and a limited particle representation provide narrow empirical evidence.

A4. We have revised the two entropy-only regression experiments and added twelve Gaussian moment-model settings, with continuous Gaussian representations and direct distributional accuracy checks. Table 4 reports the complete twelve-setting screening results, including cases where CWPG is faster. W-LALM has a median paired runtime advantage in eight of the twelve settings; we do not claim a universal advantage for coupled models.

Controlled constraint-count study. On NOAA East linear hinge, we fix d=2560d=2560, the objective, initial law, and algorithm parameters. Constraints are nested. CWPG uses adaptive Newton–CG throughout.

mmW-LALM (ms)CWPG (ms)Paired ratioOuter steps W / C
500123.83150.551.1760–65 / 9–10
1000219.48483.112.0757–64 / 8–10
1500266.29820.603.1047–61 / 7–9
2000348.391280.393.7057–66 / 7–8

Times are medians of four per-instance timing medians. Ratios are medians of paired per-instance ratios; outer steps are ranges across instances. Each instance has one untimed warm-up and five timing repetitions. All 160 runs meet W2W_2 error ≤10−5\le10^{-5}, feasibility ≤10−8\le10^{-8}, and outer KKT residual ≤10−5\le10^{-5}. Setup and reference computation are excluded from timing. These results locate the advantage in the cost of the coupled backward solve in this controlled study, despite CWPG taking fewer outer steps. Table 3 and Appendix D.6 report the results and protocol.

AuthorsOpenReview ↗

Response to Reviewer 67M3 (Part 2/2)

Q5 (Comment 5. Sensitivity to algorithm and solver parameters).

Study gamma, rho, beta, and Sinkhorn regularization.

A5. On exact-Gaussian Wine, we have tested 14 configurations with five repetitions each. All 70 runs meet feasibility 10−810^{-8}, KKT residual 10−510^{-5}, and the motion–feasibility stopping threshold 10−510^{-5}.

  • Step size γ\gamma. Increasing the admissible fraction from 0.25 to 0.99 reduces outer steps from 381 to 93.
  • Penalty ρ\rho. At a common admissible step size, outer steps decrease from 298 at ρ=0.05\rho=0.05 to 136 at both ρ=0.4\rho=0.4 and ρ=0.8\rho=0.8.
  • Entropy coefficient β\beta. All five tested values terminate in 93 steps in this instance. This is consistent with termination being governed mainly by the mean/multiplier dynamics here; it does not imply general insensitivity to β\beta.

The revised continuous experiments use no Sinkhorn regularization. Table 6 and Appendix D.2 report the sensitivity configurations and terminal residuals. Appendix D.5 describes the retained particle baselines separately, including their empirical moments and the weight entropy used by Proximal-ALM.


Q6 (Comment 6. Objective-gap and feasibility rates).

Provide objective and feasibility rates in addition to KKT-residual complexity.

A6. The existing Lyapunov estimate also yields O(1/N)O(1/N) ergodic objective and feasibility bounds. These can be stated for a recursively averaged measure under the current assumptions.

Fix a base measure σ∈dom⁡Φ\sigma\in\operatorname{dom}\Phi, such as μ1\mu_1. Let μˉ1=μ1\bar\mu_1=\mu_1. For N≥2N\ge2, choose a generalized geodesic νtN\nu_t^N, with base σ\sigma, from μˉN−1\bar\mu_{N-1} to μN\mu_N along which Φ\Phi is convex, and set μˉN=ν1/NN\bar\mu_N=\nu_{1/N}^N. Generalized-geodesic convexity ensures that this recursive construction has finite objective. The construction may depend on the admissible couplings chosen.

First moments interpolate affinely, and recursive convexity gives

C(μˉN)=1N∑j=1NC(μj),Φ(μˉN)≤1N∑j=1NΦ(μj).\mathcal C(\bar\mu_N)=\frac1N\sum_{j=1}^N\mathcal C(\mu_j),\qquad \Phi(\bar\mu_N)\le\frac1N\sum_{j=1}^N\Phi(\mu_j).

Write hj⋆=Φ(μj)−Φ(μ⋆)+⟨λ⋆,C(μj)⟩≥0h_j^\star=\Phi(\mu_j)-\Phi(\mu^\star)+\langle\lambda^\star,\mathcal C(\mu_j)\rangle\ge0. Summing the Lyapunov inequality yields

∑j=1Nhj⋆≤E~0⋆2γ.\sum_{j=1}^N h_j^\star\le\frac{\widetilde E_0^\star}{2\gamma}.

Meanwhile, the multiplier update and the Lyapunov bound give

C(μˉN)=λN−λ0ρN,∥λN−λ⋆∥≤ργE~0⋆.\mathcal C(\bar\mu_N)=\frac{\lambda_N-\lambda_0}{\rho N},\qquad \Vert\lambda_N-\lambda^\star\Vert\le\sqrt{\frac\rho\gamma\widetilde E_0^\star}.

With the constant used in Theorem C.13,

Bλ=∥λ0−λ⋆∥+ρE~0⋆/γρ,∥C(μˉN)∥≤BλN.B_\lambda=\frac{\Vert\lambda_0-\lambda^\star\Vert+\sqrt{\rho\widetilde E_0^\star/\gamma}}{\rho},\qquad \Vert\mathcal C(\bar\mu_N)\Vert\le\frac{B_\lambda}{N}.

Combining recursive convexity with the saddle-gap estimate, and using the saddle inequality for the lower bound, gives

\Phi(\bar\mu_N)-\Phi(\mu^\star)&\ge-\Vert \lambda^\star\Vert \,\Vert \mathcal C(\bar\mu_N)\Vert ,\\ \Phi(\bar\mu_N)-\Phi(\mu^\star)&\le\frac{\widetilde E_0^\star}{2\gamma N}+\Vert \lambda^\star\Vert \,\Vert \mathcal C(\bar\mu_N)\Vert . \end{aligned}$$ Thus, $$\Vert \mathcal C(\bar\mu_N)\Vert =O(1/N),\qquad |\Phi(\bar\mu_N)-\Phi(\mu^\star)|=O(1/N).$$ These results are now stated in Theorem 4.5, with explicit constants and proof in Theorem C.13. Theorem C.13 additionally gives an $O(1/N)$ bound on the average squared constraint violation. These rates concern the averaged measure; they do not assert a general last-iterate $O(1/N)$ rate. In the Dirac specialization, the construction gives $\bar\mu_N=\delta_{N^{-1}\sum_{j=1}^N x_j}$, recovering the Euclidean Cesàro average. --- ***Q7 (Comment 7. The role of strong convexity).*** *Discuss whether strong convexity of V permits a linear rate.* **A7.** Our results establish primal-dual convergence and KKT complexity under convexity. A linear primal-dual rate may require additional regularity beyond strong convexity of $V$ alone. The Conclusion identifies faster rates as future work.
Reviewer_67M3OpenReview ↗

Thank you for the rebuttal.

Thank the authors for clarification. I'd like keep my score. Good luck.

Reviewer_3uHuOpenReview ↗
Rating
2
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This is a highly technical theoretical paper that is on the topic of learning a probability law (i.e., trying to optimize over a probability measure) subject to certain types of constraints (linear expectation constrains). The basic idea of Lagrange multipliers for optimization appears to inform the authors' development of their method, W-LALM, a linearized augmented Lagrangian method, in Wasserstein space. The key argument of the theory, in my opinion, is that the residual (which is defined based on a KKT system) appears decays like O(1/N) on average. Compared to the related methods highlighted in Table 1, W-LALM is demonstrated on a few numerical experiments to have some meaningful performance advantages (e.g., up to 38 times faster than CWPG). The speedups are unsurprising given the theoretical justification of the method but nonetheless validate the authors' implementation.

Critical strengths
  1. The proposed W-LALM method, in the absence of constraints, reduces to WPG, so I appreciate that the authors are effectively generalizing that method here, and the close connections to WPG. However, the paper makes a useful observation that - with linear expectation constraints present - the constraints don't have to go inside the JKO step, and their alternative W-LALM formulation (see around L1509 in the revised manuscript) proposes a more efficient strategy. This is borne out by the numerical results.

  2. The method seems correct to the best of my knowledge (looking primarily at the statements and proofs in Appendix C). Furthermore, the stopping rules for the method (Section 5 and Appendix D) are straightforward since the KKT residual comes from the iterates directly. Moreover, the analysis with transport plans is rather elegant and brings something distinct from the prior literature (see Table 1).

Critical weaknesses
  1. Although the experiments appear to show the performance of W-LALM, I have some substantial concerns. The solution of Equation 1 is a Gaussian (with known covariance) in the case of a quadratic potential and the entropy. In the authors' particle approach used in their numerical experiments, the spread of the particles is not really constrained - the forward step appears to be contracting particles toward a min where all the particles just collapse at one point. PD-LMC has a gap that looks suspiciously like βd/2\beta d/2 (average extra energy of samples from a true Gaussian). I suggest the authors run the exact Gaussian version of the method and do fairer comparisons rather than just this particle-based strategy that may be making PD-LMC look unnecessarily bad.

  2. I am not convinced that the constrained JKO step is computationally hard for a linear expectation constraint. For instance, if you just constrain the mean for example, the constrained step would end up just look like the unconstrained version plus a translation. The CWPG baseline that the authors report seems to solve a constrained reweighting problem that Table 3 reports as being a big chunk of the computational expense. Is that really necessary for CWPG? Can it just be a step followed by a translation instead and get performance comparable to W-LALM? Related to this point, adding an example H and the constraint interact (meaningfully) might help illuminate what's going on here.

  3. I am not sure about the impact of the theoretical analyses in this work. For instance, what is the advantage of the plan-based analysis versus the map-based analysis used in other works (per Table 1), besides interest? And although I recognize the novel combinations in the present work, it appears there's a lot of analysis carried from linearized ALM (He 2020), WPG, and Naldi 2021. I'm not sure that is really fixable and is more of just a judgment call about the work, but perhaps the contributions and novelty can be better clarified by the authors.

Minor:

  • Can you double check Remark C.8 - it appears to apply C.7 to the functional from C.4, but that doesn't satisfy Assumption 2.1 from my reading?
  • Figure 1 appears to plot stopping residual but its axis is labeled as KKT residual - typo or did I misread?
  • Step size, Sinkhorn regularization, and PD-LMC step size are not given - can these be added?
Questions for authors
  1. Per point #1 above, could the authors add comparisons of all methods to the known Gaussian solution? Can the authors also report how the particles were initialized for the numerical tests?

  2. Per point #2 above, how does W-LALM compare with CWPG, if you implement CWPG as an unconstrained step + a translation? Can you find/show some examples (perhaps as suggested above) where W-LALM is clearly faster still?

  3. If the authors are able to run the exact Gaussian version of W-LALM, can you report the KKT residual of Theorem 4.4 along with the iterations? Ideally also on a problem that is not strongly convex?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 3uHu (Part 1/2)

We thank the reviewer for the careful proof checking and detailed comments. We agree that particle-weight entropy does not represent continuous Boltzmann entropy. We have replaced the original discrete-objective comparison and withdrawn the large-speedup claim for the entropy-only experiments. We answer W1/Q1 and W2/Q2 together.

The questions below summarize the review; the corresponding original labels are retained for reference.


Q1 (W1 and Q1. The continuous target, Gaussian accuracy, and initialization).

The weight-entropy implementation can favor particle collapse. Compare every method against the analytic Gaussian mean and covariance, and state the initialization.

A1. We evaluated all four methods against the same analytic reference for each dataset. Mean error is ∥m−m⋆∥2\Vert m-m^\star\Vert _2; covariance error is ∥Σ−Σ⋆∥F\Vert \Sigma-\Sigma^\star\Vert _F.

DatasetMethodMean errorCovariance error
WineW-LALM9.81×10−69.81\times10^{-6}2.55×10−112.55\times10^{-11}
WineCWPG9.69×10−69.69\times10^{-6}2.85×10−112.85\times10^{-11}
WinePD-LMC2.83×10−22.83\times10^{-2}8.93×10−38.93\times10^{-3}
WineProximal-ALM3.31×10−83.31\times10^{-8}1.06×10−21.06\times10^{-2}
ConcreteW-LALM3.97×10−63.97\times10^{-6}6.60×10−106.60\times10^{-10}
ConcreteCWPG9.81×10−69.81\times10^{-6}4.19×10−94.19\times10^{-9}
ConcretePD-LMC2.97×10−22.97\times10^{-2}9.46×10−39.46\times10^{-3}
ConcreteProximal-ALM4.68×10−74.68\times10^{-7}1.10×10−21.10\times10^{-2}

For V(x)=12x⊤Qx−p⊤x+cV(x)=\frac12x^\top Qx-p^\top x+c, the reference has Σ⋆=βQ−1\Sigma^\star=\beta Q^{-1}. Its mean minimizes 12m⊤Qm−p⊤m\frac12m^\top Qm-p^\top m subject to Am=bAm=b. Thus covariance accuracy is checked against the continuous target directly. Proposition C.4 gives the analytic reference; Tables 2 and 7 report continuous-method and four-method accuracy, respectively. We no longer interpret the lower discrete-surrogate objective in the original Table 2 as evidence of a better solution to the continuous problem.

Implementation and initialization. W-LALM and CWPG use continuous Gaussian updates, starting from the same mean and covariance 2.25βQ−12.25\beta Q^{-1}. The mean is the initial particle mean. The original 140 particles are bootstrap ridge estimates recentered at the training ridge estimate.

PD-LMC and Proximal-ALM retain their original particle implementations; the latter retains weight entropy. Their errors use the empirical mean and full covariance with normalized weights. Appendix D.5 specifies the particle initialization, empirical covariance, and PD-LMC step-size and noise schedule. We include them as diagnostics against the analytic target. They do not establish a general accuracy ranking between exact-law optimization and finite-particle sampling.

The continuous methods recover both moments accurately. Both also meet feasibility ≤10−8\le10^{-8}: W-LALM gives 3.07×10−113.07\times10^{-11} / 6.19×10−96.19\times10^{-9} on Wine / Concrete; CWPG gives 1.69×10−161.69\times10^{-16} / 2.57×10−162.57\times10^{-16}.


Q2 (W2 and Q2. Translation-based CWPG and a coupled example).

For entropy and mean constraints, use an unconstrained JKO step followed by translation. Test whether an advantage remains when the constraint interacts with H.

A2. For H=βEnt⁡\mathcal H=\beta\operatorname{Ent}, translation invariance and the mean/centered decomposition of W22W_2^2 give an exact constrained JKO step by an unconstrained update followed by translation. We have adopted this implementation.

DatasetW-LALMCWPG
Wine4.37 ms4.43 ms
Concrete4.45 ms3.50 ms

The computational costs are comparable in this model.

A setting with constraint–functional interaction. We have added models with second-moment hinge or squared-hinge penalties. Their continuous JKO problem has an exact finite-dimensional reformulation in the means and standard deviations. Appendix D.1 shows that the diagonal quadratic forward map and mean translations preserve the required product-Gaussian inputs. The unconstrained problem is separable; Am=bAm=b introduces coupling and can change the optimal variances. These reduced subproblems are solved to numerical tolerance.

We have tested direct Newton, fixed-tolerance Newton–CG, and adaptive Newton–CG for the structured multiplier solve, with multipliers warm-started from the preceding outer step. Parameters are selected on a development instance. Direct-KKT and Clarabel independently verify the same constrained subproblem. Paired median runtime ratios CWPG/W-LALM are 2.48, 2.32, and 2.10 on NOAA East linear hinge, Coded SST West linear hinge, and Coded SST East squared hinge.

AuthorsOpenReview ↗

Response to Reviewer 3uHu (Part 2/2)

A2 (continued).

A controlled study fixes d=2560d=2560, the objective, initialization, and parameters while varying nested constraint sets. For m=500,1000,1500,2000m=500,1000,1500,2000, paired median ratios are 1.17, 2.07, 3.10, and 3.70. Adaptive Newton–CG is used throughout. Four held-out instances and five timed repetitions after warm-up give 160 runs; all meet reference-distance 10−510^{-5}, feasibility 10−810^{-8}, and outer KKT residual 10−510^{-5}.

Thus, the revised computational claim is restricted to the tested coupled settings. Table 3 reports representative cases and the controlled constraint-count study; Table 4 reports all twelve screening settings. W-LALM has a median paired runtime advantage in eight of the twelve settings, so coupling alone does not guarantee a speed advantage.


Q3 (W3. Theoretical contribution, transport plans, and scope).

Clarify the contribution beyond Euclidean ALM and WPG, the need for plans when entropy admits maps, and the restriction to mean constraints.

A3. We agree that the algorithm builds on Euclidean linearized ALM and Wasserstein proximal gradient, and that gluing is a standard tool. The contribution we claim is the coupled primal-dual analysis for this splitting.

The forward displacement and JKO optimal coupling are glued through their common intermediate marginal and combined with a comparison coupling. The resulting Plan EVI places the two-stage primal displacement and the consecutive constraint residuals on a common plan. Combining it with the multiplier update yields the corrected Lyapunov estimate used for full-sequence convergence and plan-valued KKT complexity. Lemma C.7 gives the Plan EVI, and Theorem C.8 gives the corrected Lyapunov estimate; these support Theorems 4.2 and 4.4. The revised manuscript distinguishes these estimates from the standard Wasserstein tools.

We also agree that entropy iterates can admit transport maps. The plan formulation removes a map-existence assumption from the general analysis, which permits atomic or singular measures. Our present constraints are AEμ[X]=bA\mathbb E_\mu[X]=b. Variance, quantile, nonlinear-moment, and inequality constraints require additional analysis and are outside the current guarantees.


Q4 (Q3. KKT residuals in an exact Gaussian, non-strongly-convex test).

Run the exact Gaussian version and report the residual in Theorem 4.4 along the iterations, including a non-strongly-convex problem.

A4. We compute the residual defined in Theorem 4.4 directly. The added three-dimensional example is

V≡0,H(μ)=α2(Eμ∥X∥2−τ)+,Eμ[X1]=b,b2<τ.V\equiv0,\qquad \mathcal H(\mu)=\frac\alpha2\bigl(\mathbb E_\mu\Vert X\Vert ^2-\tau\bigr)_+,\qquad \mathbb E_\mu[X_1]=b,\qquad b^2<\tau.

The objective has a nontrivial feasible flat region with nonunique minimizers, and is not strongly convex. Its JKO step is given by radial scaling and preserves Gaussian laws, avoiding particle and Sinkhorn approximations.

After 53 iterations:

QuantityTerminal value
Feasibility $\Vert \mathcal C(\mu_k)\Vert $6.95×10−106.95\times10^{-10}
Theorem 4.4 residual Rk\mathcal R_k7.50×10−107.50\times10^{-10}
W2(μk,μ⋆)W_2(\mu_k,\mu^\star)6.95×10−106.95\times10^{-10}

Because minimizers are nonunique, the reference is the analytic limiting Gaussian selected by this initialization. Appendix D.4 gives the initialization, parameters, radial update, and limiting law; Appendix D.2, Eq. (79), gives the Gaussian residual formula. Figure 1 reports feasibility, stationarity, the raw KKT residual, and the averaged squared KKT residual. The O(1/N)O(1/N) guide applies to the averaged squared quantity in Theorem 4.4.


Q5 (Minor point 1. The Dirac specialization).

The Dirac-supported functional does not satisfy the assumptions of Theorem C.7.

A5. We agree that the Dirac-supported functional fails the dense-domain assumption. Remark C.6(2) now presents this case as an algebraic specialization of the update, rather than a direct application of the general full-sequence theorem.


Q6 (Minor point 2. The residual label in Figure 1).

The plot appears to show a stopping residual rather than the theoretical KKT residual.

A6. The original plot combined a feasible-coupling motion cost with constraint violation and was a stopping statistic. We have replaced it with Figure 1, which reports the actual Theorem 4.4 residual and its averaged square, alongside feasibility and stationarity.


Q7 (Minor point 3. Reproducibility details).

The step sizes, Sinkhorn regularization, and PD-LMC schedule are insufficiently specified.

A7. Appendices D.1–D.3 specify the continuous solver, step sizes, repetitions, and stopping thresholds; Appendix D.5 gives the PD-LMC step-size and noise schedule. Section 5 references these details. The revised continuous experiments use no Sinkhorn regularization. Code, configurations, and run scripts will be released after the anonymous review period.

Reviewer_3uHuOpenReview ↗

Response to authors' rebuttal

I thank the authors for their comments and for the major changes evidently made to the manuscript. My minor comments were all addressed in this revised version.

However, in perusing the comments from the other reviewers, I see similar larger concerns being identified, and I'm not sure that the revised manuscript version really overcomes them. For example, I appreciate the authors' candor and more experimetns around W-LALM vs. CWPG (I'm looking at your comments as well as e.g. Table 4 in the new version). However, by the authors' admission, and along the lines of my initial remark, it seems like W-LALM only outperforms methods like CWPG in certain scenarios, like when you have constraint-functional interaction. This limits the impact of the present method.

I also understand that the main claimed theoretical contribution is the coupled primal-dual analysis. I am not fully convinced of the impact of this contribution on the broader community. While I recognize that is a subjective judgment, I also feel like the paper's exposition could be framed a bit better (especially in the abstract, introduction, and conclusions) to convince the reader of potential broader appeal or how the work will inform future research directions (besides obvious potential extensions of the present work such as handling nonlinear constraints).

In light of these considerations, I hesitate to raise my score at this time.

AuthorsOpenReview ↗

Response to Reviewer 3uHu

Thank you for reading the revised manuscript again and for confirming that the earlier minor concerns have been addressed. We appreciate your suggestion to explain more clearly the broader significance of the analysis.

Computational scope. The revised experiments clarify the design trade-off: W-LALM is particularly useful when incorporating the constraint into the JKO step substantially increases the cost of the backward solve, while CWPG remains competitive when that constrained step is already inexpensive.

The analytical difficulty and its resolution. The main theoretical issue arises from a structural difference between Euclidean and Wasserstein splitting. In a Euclidean space, cross-update terms can be handled through identities such as

2⟨x−y,x−z⟩=∥x−y∥2+∥x−z∥2−∥y−z∥2,2\langle x-y,x-z\rangle=\|x-y\|^2+\|x-z\|^2-\|y-z\|^2,

because all iterates and displacements live in the same linear space.

For the Wasserstein update, however,

W22(ηk+1,ν)=inf⁡π∈Γ(ηk+1,ν)∫∥z−w∥2 dπ,W_2^2(\eta_{k+1},\nu)=\inf_{\pi\in\Gamma(\eta_{k+1},\nu)}\int \|z-w\|^2\,d\pi,

and

W22(ηk+1,μk+1)=inf⁡π~∈Γ(ηk+1,μk+1)∫∥z−y∥2 dπ~W_2^2(\eta_{k+1},\mu_{k+1})=\inf_{\widetilde\pi\in\Gamma(\eta_{k+1},\mu_{k+1})}\int \|z-y\|^2\,d\widetilde\pi

are optimized over different coupling sets. Hence the two squared transport costs cannot simply be expanded as if they were Euclidean squared norms of vectors in a common space.

Our joint-plan construction resolves exactly this issue. It preserves the optimal coupling required for the negative JKO transport cost, preserves the old-iterate/reference optimal marginal needed to recover W22(μk,ν)W_2^2(\mu_k,\nu), and uses a feasible coupling for the remaining comparison cost. This gives

W22(ηk+1,ν)−W22(ηk+1,μk+1)≤∫(∥z−w∥2−∥z−y∥2) dβk,W_2^2(\eta_{k+1},\nu)-W_2^2(\eta_{k+1},\mu_{k+1})\le\int\left(\|z-w\|^2-\|z-y\|^2\right)\,d\beta_k,

so that the two squared displacements can now be expanded under the same integral. The resulting cross term connects the Wasserstein primal displacement with the Euclidean multiplier update.

For W-LALM, this construction leads to the Plan EVI and the corrected primal--dual Lyapunov estimate, which in turn support full-sequence convergence and the plan-valued KKT complexity result. The contribution lies in the update-specific construction that determines which marginals must remain optimal, which comparison terms require only feasible couplings, and how these transport relations combine with the multiplier dynamics.

Beyond the convergence theorem for W-LALM itself, the analysis identifies a structural difficulty that does not arise in Euclidean splitting: quantities required by the same cross-update energy estimate may be realized on different transport couplings. The joint-plan construction provides a concrete mechanism for recovering the required energy relation.

There are two further implications. First, because the argument is formulated with transport plans rather than* Monge maps, it does not require optimal transport maps for the relevant comparisons and can therefore accommodate atomic or singular measures whenever the other assumptions of the analysis are satisfied. Second, for related multistep Wasserstein methods whose Euclidean counterparts rely on cross-update energy identities, the same viewpoint suggests starting from the target descent estimate and identifying which transport costs must be represented jointly. This viewpoint provides a concrete route toward Wasserstein counterparts of the Primal--Dual Hybrid Gradient (PDHG) method, Douglas--Rachford splitting, and the Alternating Direction Method of Multipliers (ADMM), as well as toward more general constraint structures.

Given the limited time remaining in the rebuttal period, we have made a focused revision rather than a full restructuring of the paper. Specifically, we have added the following discussion, highlighted in blue in the revised manuscript:

  • the analytical difficulty caused by the fact that the relevant Wasserstein transport costs arise from different couplings;
  • the role of the joint-plan construction in recovering the cross-update energy relation required by the primal--dual analysis;
  • the potential relevance of this viewpoint to the analysis of related multistep Wasserstein splitting methods.

We will continue to refine the abstract and introduction in a subsequent revision so that these points and the broader significance of the theoretical contribution are presented more clearly and prominently. We hope the present additions already make the scope and significance of the theoretical contribution clearer.

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

The paper proposes a JKO-WPG method for constrained optimization in Wasserstein spaces. The authors solve the well-known problem of minimizing energy functionals over probability distributions, incorporating linear expectation constraints. The proposed approach introduces an augmented Lagrangian that incorporates the constraints through Lagrange multipliers and a quadratic penalty. First, the authors update the particle positions using a gradient step that accounts for both the potential energy and the constraint violations. They then perform an unconstrained JKO proximal step for the remaining energy functional. Finally, the Lagrange multipliers are updated based on the remaining constraint violations. This strategy is validated on an experiment constructed using generalized Bayesian polynomial regression with linear expectation constraints, evaluated on the Wine Quality Red and Concrete Compressive Strength datasets.

Critical strengths

I believe the main strength of the paper lies in its theoretical contributions. Although the proposed method represents an incremental extension of existing JKO and Wasserstein proximal-gradient formulations, the authors provide theoretical guarantees for optimization under linear expectation constraints, which I consider valuable.

Critical weaknesses

Below I list my two main concerns:

[W1] Baselines design and evaluation protocol. My first concern is regarding how the CWPG baseline was constructed. The CWPG implementation enforces the linear expectation constraint exclusively through particle weights, which may considerably restrict the feasible set or even make it impossible to find a solution satisfying the constraints. Moreover, alternative constraint-enforcement strategies exist, such as projecting particle locations onto the feasible moment set. Since the proposed method's computational advantage is partly attributed to avoiding constrained weight optimization, the authors should clarify how this particular baseline design influences the comparison. In addition, I have concerns about how well the proposed method satisfies the feasibility constraints in practice. The stopping criterion (rkr_k equation after equation 7) combines transportation cost with constraint violation, making it difficult to assess whether the methods achieve comparable levels of feasibility. Reporting constraint violations separately would provide a clearer comparison.

[W2] Clarification of assumptions. Assumption 2.1(3) requires the existence of a saddle point (μ⋆,λ⋆)(\mu^\star,\lambda^\star), but the authors do not clearly explain under which conditions this assumption is satisfied. In particular, the existence of an optimal feasible distribution and a corresponding Lagrange multiplier does not necessarily follow from Assumptions 2.1(1)-(2). The authors should provide sufficient conditions guaranteeing the existence of such a saddle point, or at least discuss how this assumption can be verified for the problems considered in the experiments. This would help clarify the applicability and limitations of the theoretical guarantees that follow from this statement.

I also encourage the authors to improve the overall organization and presentation of the paper. In its current form, the Introduction is overly dense, and some mathematical notation is introduced without proper definitions, as in the case of IC=0I_{\mathcal{C}=0}. Additionally, Figure 1 is never referenced in the text. I believe the paper would benefit from a general restructuring, particularly by making the Introduction less technical and focusing more on motivating the problem and presenting the main contributions before introducing the mathematical details.

Overall, I believe the paper makes a good contribution, although it is not particularly outstanding as it builds upon two already well known formulations. Given the concerns outlined in the weaknesses above, I lean toward weak rejection. I hope the authors can address these points during the rebuttal, as their clarifications could help improve my assessment of the paper.

Questions for authors

[Q1] Could the authors clarify how the d=110d=110 parameterization and the 50 and 100 linear expectation constraints are constructed for the two datasets? In particular, given that only 140 particles are used, how is feasibility of the CWPG weight subproblem ensured, and how does the number of constraints affect the performance of the compared methods?

6 comments
AuthorsOpenReview ↗

Response to Reviewer RvLk(Part 1/2)

We thank the reviewer for recognizing the theoretical contribution and for the constructive suggestions. We address W1, W2, the presentation comments, and Q1 below. We have replaced the original fixed-support baseline with continuous constrained-JKO solves and withdrawn the large-speedup claim for the entropy-only experiments.

The questions below summarize the review; the corresponding original labels are retained for reference.


Q1 (W1. Baseline design and separate feasibility evaluation).

The fixed-support CWPG may restrict feasibility; alternative constraint enforcement could change the comparison. Constraint violation should be reported separately.

A1. Entropy-only case. For H=βEnt⁡\mathcal H=\beta\operatorname{Ent}, the reviewer is correct that translation invariance and the mean/centered decomposition of W22W_2^2 give an exact constrained JKO step: perform the unconstrained step, then translate the mean onto Am=bAm=b. We implemented this CWPG and continuous Gaussian W-LALM.

DatasetW-LALM timeCWPG time
Wine4.37 ms4.43 ms
Concrete4.45 ms3.50 ms

The terminal feasibility residuals ∥Amk−b∥2\Vert Am_k-b\Vert _2 are:

DatasetW-LALMCWPG
Wine3.07×10−113.07\times10^{-11}1.69×10−161.69\times10^{-16}
Concrete6.19×10−96.19\times10^{-9}2.57×10−162.57\times10^{-16}

Both meet 10−810^{-8}. CWPG enforces feasibility at each constrained backward step; W-LALM achieves feasibility through its primal-dual updates. The two methods have comparable cost in this model. The revised manuscript reports reference-distance, feasibility, and KKT residuals separately.

When the constraint interacts with H\mathcal H. We have added continuous Gaussian models with second-moment hinge or squared-hinge penalties. Their unconstrained JKO solve is coordinate-wise separable, while Am=bAm=b couples the coordinates and can change the optimal variances. The paired median CWPG/W-LALM runtime ratios are 2.48, 2.32, and 2.10 on NOAA East linear hinge, Coded SST West linear hinge, and Coded SST East squared hinge, respectively.

Table 4 reports all twelve screening settings, including cases where CWPG is faster. W-LALM has a median paired runtime advantage in eight of the twelve settings; the claimed benefit is model-dependent.

We use

H(μ)=βEnt⁡(μ)+∑iφi(Eμ[Xi2]),\mathcal H(\mu)=\beta\operatorname{Ent}(\mu)+\sum_i\varphi_i(\mathbb E_\mu[X_i^2]),

where β>0\beta>0 and φi(t)\varphi_i(t) is either αi2(t−τi)+\frac{\alpha_i}{2}(t-\tau_i)_+ or αi4(t−τi)+2\frac{\alpha_i}{4}(t-\tau_i)_+^2, with αi≥0\alpha_i\ge0.

For product-Gaussian input η=N(z,diag⁡(r2))\eta=\mathcal N(z,\operatorname{diag}(r^2)), the continuous JKO problem reduces exactly to

Jη(m,s)=∥m−z∥2+∥s−r∥22γ−β∑ilog⁡si+∑iφi(mi2+si2),J_\eta(m,s)=\frac{\Vert m-z\Vert ^2+\Vert s-r\Vert ^2}{2\gamma}-\beta\sum_i\log s_i+\sum_i\varphi_i(m_i^2+s_i^2),

minimized over m∈Rdm\in\mathbb R^d, s∈(0,∞)ds\in(0,\infty)^d, with Am=bAm=b added for CWPG. Gaussian maximum entropy and the coordinate-wise Wasserstein lower bound justify the reduction. Appendix D.1 shows that the diagonal quadratic forward map and mean translations preserve product-Gaussian inputs. The reformulation is exact; the reduced problem is solved to numerical tolerance.

We tested damped Newton with a direct solve, fixed-tolerance Newton–CG, and adaptive Newton–CG. Each multiplier trial shifts the JKO input, solves the separable proximal problem, and adjusts the multiplier to satisfy the moment equation. Multipliers are warm-started from the preceding outer step. Configurations and step sizes are selected on a development instance before held-out evaluation.

Direct-KKT and CVXPY/Clarabel independently check the same constrained subproblem. The single-step subproblem KKT residuals are 2.71×10−132.71\times10^{-13} for the multiplier method, 3.33×10−153.33\times10^{-15} for Direct-KKT, and 9.60×10−89.60\times10^{-8} for Clarabel, with numerically consistent solutions. The runtime comparison uses the structured multiplier solver. Its continuous constrained-JKO formulation is derived in Appendix D.3, Eq. (81); Table 5 reports the independent solver check.


AuthorsOpenReview ↗

Response to Reviewer RvLk(Part 2/2)

Q2 (W2. Sufficient conditions for saddle-point existence).

Assumptions 2.1(1)–(2) do not imply Assumption 2.1(3). Give sufficient conditions and verify them for the experiments.

A2. We agree that Assumption 2.1(3) does not follow from (1)–(2). A sufficient condition is attainment of the finite constrained optimum, together with a proper convex perturbation value function

v(y)=inf⁡μ: AEμ[X]=yΦ(μ)v(y)=\inf_{\mu:\,A\mathbb E_\mu[X]=y}\Phi(\mu)

satisfying b∈ri⁡(dom⁡v)b\in\operatorname{ri}(\operatorname{dom}v). Then g∈∂v(b)g\in\partial v(b) exists. Taking λ⋆=−g\lambda^\star=-g, we obtain, for every ν\nu,

Φ(ν)≥v(AEν[X])≥Φ(μ⋆)+⟨g,AEν[X]−b⟩.\Phi(\nu)\ge v(A\mathbb E_\nu[X])\ge\Phi(\mu^\star)+\langle g,A\mathbb E_\nu[X]-b\rangle.

This is the required saddle inequality. The sufficient-condition argument is stated in Remark 2.2; Propositions C.4 and C.5 verify saddle-point existence for the quadratic–entropy and quadratic moment-penalty models, respectively.

Verification for the revised quadratic–entropy–moment models. Let V(x)=12x⊤Qx−p⊤x+cV(x)=\frac12x^\top Qx-p^\top x+c, Q≻0Q\succ0, and let AA have full row rank. The penalties above are finite, convex, nonnegative, and nondecreasing. The objective is convex under probability mixtures, so vv is convex.

Replacing a finite-objective distribution by the Gaussian with the same mean and covariance preserves its quadratic and second-moment terms and does not increase its Boltzmann entropy. Attainment therefore reduces to minimizing, up to a constant,

F(m,Σ)=12m⊤Qm−p⊤m+12tr⁡(QΣ)−β2log⁡det⁡Σ+∑iφi(mi2+Σii)F(m,\Sigma)=\frac12m^\top Qm-p^\top m+\frac12\operatorname{tr}(Q\Sigma)-\frac\beta2\log\det\Sigma+\sum_i\varphi_i(m_i^2+\Sigma_{ii})

over Am=bAm=b, Σ≻0\Sigma\succ0. Since Q≻0Q\succ0 and the penalties are nonnegative, sublevel sets bound mm and bound the covariance eigenvalues above and away from zero. These finite-dimensional sublevel sets are compact, proving attainment.

For every yy, the Gaussian with mean A⊤(AA⊤)−1yA^\top(AA^\top)^{-1}y and covariance II is feasible and has finite objective. The global lower bound then gives dom⁡v=Rm\operatorname{dom}v=\mathbb R^m. Hence ∂v(b)≠∅\partial v(b)\ne\varnothing, and the supporting-multiplier argument applies. For general H\mathcal H, saddle-point existence remains an additional assumption.


Q3 (Presentation. Introduction, notation, and Figure 1).

The Introduction is dense, some notation is undefined, and Figure 1 is not referenced.

A3. We have streamlined the Introduction and defined the constraint indicator at first use. We have added the Gaussian reduction in Appendix D.1 and the saddle-point arguments in Remark 2.2 and Propositions C.4–C.5. Section 5.2 explicitly references Figure 1 and Appendix D.4.


Q4 (Q1. Regression parameterization, feasibility, and constraint count).

Explain d=110, the 50/100 constraints, feasibility with 140 particles, and the effect of the constraint count.

A4. Both regression models use d=110d=110: the first 110 entries of a deterministic monomial feature list, including the intercept. The original 140 particles are bootstrap ridge estimates recentered at the training ridge estimate. The rows of AA are the leading eigenvectors of the training design Gram matrix, transposed, and b=Aθholdoutb=A\theta_{\mathrm{holdout}}, using an independent calibration-set ridge estimate. Wine and Concrete use m=50m=50 and m=100m=100.

For fixed supports, feasible weights exist exactly when

b∈conv⁡{Au1,…,AuN}.b\in\operatorname{conv}\{Au_1,\ldots,Au_N\}.

Thus, N>mN>m alone is insufficient. We have adopted continuous constrained-JKO solves, whose Gaussian formulation is feasible for our full-row-rank matrices: m=A⊤(AA⊤)−1bm=A^\top(AA^\top)^{-1}b satisfies the constraint for any positive standard deviations.

Controlled constraint-count experiment. We fix d=2560d=2560, the objective, initialization, and algorithm parameters on NOAA East linear hinge. Nested constraint sets use the first mm rows of one row-orthonormal matrix generated by Gaussian QR, with right-hand sides from the same four held-out SST fields.

mmW-LALM (ms)CWPG (ms)Paired ratioOuter steps W / C
500123.83150.551.1760–65 / 9–10
1000219.48483.112.0757–64 / 8–10
1500266.29820.603.1047–61 / 7–9
2000348.391280.393.7057–66 / 7–8

Times are medians of four per-instance medians; ratios are medians of paired per-instance ratios. Each instance has one untimed warm-up and five timed repetitions. All 160 runs meet W2(μk,μ⋆)≤10−5W_2(\mu_k,\mu^\star)\le10^{-5}, feasibility ≤10−8\le10^{-8}, and outer KKT residual Rk≤10−5\mathcal R_k\le10^{-5}. Setup and reference computation are excluded.

We use ρ=4L\rho=4L, γ=0.99/(L+3ρ/4)\gamma=0.99/(L+3\rho/4) for W-LALM and γ=0.99/L\gamma=0.99/L with adaptive Newton–CG for CWPG, where L=max⁡iqiL=\max_iq_i and ∥A∥=1\Vert A\Vert =1. No parameters are retuned across mm. CWPG takes fewer outer steps, but its coupled backward solve becomes more costly as the constraint system grows. Section 5.2, Table 3, and Appendix D.6 report this controlled study.

I thank the authors for their detailed response. I have also reviewed the discussions with the other reviewers and the revised manuscript. Overall, I believe the rebuttal has shown that the proposed W-LALM method performs behind than CWPG, as evidenced by the updated Table 2. This, together with the assumptions required for the method to operate (as discussed in W2), makes me lean toward rejection.

I still believe the theoretical idea is interesting and has potential, but its practical implementation requires further improvement. Therefore, I have decided to maintain my original score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.