There is a summation-index misprint. On the native PDF, paper page 3, equation (4) has $X^k$ inside a sum indexed by $j$. The intended telescoping estimate has $X^j$ inside that sum; this is the estimate proved below and used in part (d). The index mismatch is present in the original PDF, rather than being introduced by the transcription.

Take the expectation of the supplied conditional expectation bound (3), using the tower property:Rearranging and forming a telescoping sum givesBecause $x^{\ast }$ is a global minimizer, $f(X^k)\ge f(x^{\ast })$ for every realisation. Hence the corrected equation (4) isAll expectations at a finite iteration are finite here: a deterministic starting point and finitely many choices of the sampled index produce only finitely many possible iterates. The bound controls accumulated squared gradients, with an additive contribution from the stochastic gradient noise floor.

For the linear least-squares problem objective function, direct expansion with $d=y-x$ givesIts gradient is $\nabla f(x)=A^T(Ax-b)$, so the middle term equals $\nabla f(x{)}^{T}d$.

Use the supplied thin singular value decomposition $A=US{V}^T$. Since $U^{T}U=I_n$, the linear map $w\mapsto Uw$ preserves the Euclidean norm. The square matrix $V$ is an orthogonal matrix, so $\Vert V^{T}d\Vert =\Vert d\Vert$. ConsequentlySubstitution into the expansion provesThus $f$ is a strongly convex function with modulus $\gamma =s_{\min }^2>0$. This modulus is sharp: choose $d=V{e}_i$ for an index attaining the smallest singular value. The Hessian matrix is $A^{T}A=V{S}^2{V}^T$, so the same conclusion says that its smallest eigenvalue is $s_{\min }^2$.

Let $d=y-x$ and take $0<t\le 1$. Rearrange the defining inequality for a strongly convex function, applied to $x+td$:Because $f$ is differentiable at $x$, its directional derivative in direction $d$ isTaking the limit in the rearranged inequality givesThis is the supporting affine function inequality strengthened by a positive squared Euclidean distance. Differentiability at $x$ alone suffices; no derivative at $y$ is used.

Fix $x$, and write $p=x-\alpha G_{\alpha }(x)$ and $g=G_{\alpha }(x)$. The supplied subgradient relation gives $v=v_{\alpha }\in \lambda \partial \psi (p)$ with $g=\nabla f(x)+v$. The evaluation point in $\nabla f$ is $x$, whereas $v$ is a subgradient at the new point $p$.

Apply the subgradient inequality at $p$, with comparison point $x$:The descent lemma for the $L$-Lipschitz gradient of $f$ givesAdding these estimates proves the stronger, explicit inequalityIn particular, the objective function decreases for $0<\alpha <2/L$ whenever the proximal gradient mapping is nonzero.

To justify the requested big O notation, we must check that $g$, which depends on $\alpha$, stays bounded. Suppose $\partial (\lambda \psi )(x)$ is nonempty, and choose a fixed $w$ in this subdifferential. This holds for a finite-valued convex function on ${\mathbb{R}}^n$, including both norms in parts (a) and (b). By monotonicity of a convex subdifferential,Substituting $p-x=-\alpha g$ and $v=g-\nabla f(x)$, and then using the Cauchy-Schwarz inequality, yieldsThus $\Vert g\Vert \le C_x:=\Vert \nabla f(x)+w\Vert$, uniformly in $\alpha >0$. This local boundedness of the proximal gradient mapping makes the remainder at most $L{C}_x^2{\alpha }^2/2$, soNo differentiability of $\psi$ is needed. If an proper extended-real function is allowed as the regularization term, the subdifferential condition at $x$ is a qualification for this uniform remainder; the preceding explicit descent inequality remains the useful statement whenever its quantities are finite.

Set $g_j=G_{1/L}(x^j)$, $r_j=\Vert x^j-x^{\ast }{\Vert }^2$ and ${\delta }_j=\varphi (x^j)-\varphi (x^{\ast })$. Here $g_j$ is the proximal gradient mapping, $r_j$ is a squared Euclidean distance, and ${\delta }_j\ge 0$ because $x^{\ast }$ is a global minimizer. The update gives $x^{j+1}=x^j-g_j/L$.

First use the supplied inequality (1) with $z=x^j$:Thus the objective function values, and hence the errors ${\delta }_j$, are nonincreasing. Next use (1) with $z=x^{\ast }$:Expansion of the squared Euclidean norm givesso the last bound is exactly ${\delta }_{j+1}\le L(r_j-r_{j+1})/2$.

The telescoping sum over $j=0,\dots ,k-1$ therefore givesSince each summand is at least ${\delta }_k$, we obtain the proximal gradient objective error boundThe bound holds for the last iterate. The monotonicity of the objective function values is what converts an averaged estimate into this last-iterate estimate.

Again write $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$, and let $z_{\ell }$ denote its $\ell$th block of $k$ coordinates. The block mixed norm in this part makes the proximal operator separate over blocks. For a single block, its minimiser solvesAt a nonzero $u$, the gradient of the Euclidean norm is $u/\Vert u\Vert$. The subgradient optimality condition therefore becomesThus $u$ points in the direction of $z_{\ell }$ and $\Vert z_{\ell }\Vert =\Vert u\Vert +\tau$. This yields $u=(1-\tau /\Vert z_{\ell }\Vert )z_{\ell }$ when $\Vert z_{\ell }\Vert >\tau$.

At zero, the subdifferential of the Euclidean norm is the closed Euclidean unit ball: the subgradient inequality is $q^{T}w\le \Vert w\Vert$ for every $w$, which is equivalent to $\Vert q\Vert \le 1$ by the Cauchy-Schwarz inequality and the choice $w=q$. Hence zero solves the subgradient optimality condition exactly when $\Vert z_{\ell }\Vert \le \tau$. This also covers $z_{\ell }=0$ and avoids division by zero.

The resulting radial soft thresholding isIf $y_{\ell }$ is the corresponding block of $x$, the required proximal gradient mapping isWhole blocks can become zero, while nonzero blocks retain their direction after the gradient step. For a block of size one, radial soft thresholding agrees with the soft-thresholding operator in part (a).

Put $z=x-\alpha \nabla f(x)$ and $\tau =\alpha \lambda$. The proximal operator for the L1 norm separates into independent scalar minimization problems:The subgradient optimality condition is $0\in p_i-z_i+\tau \partial |p_i|$. By the subgradient of the absolute value, a positive solution must satisfy $p_i=z_i-\tau >0$, and a negative solution must satisfy $p_i=z_i+\tau <0$. At zero, the subgradient optimality condition holds exactly when $|z_i|\le \tau$. The squared term makes the objective function a strictly convex function, so these cases give its unique minimiser.

Thus the proximal operator is the soft-thresholding operatorConsequently the requested proximal gradient mapping, rather than just the proximal operator, isThe corresponding proximal gradient method update is $x_i^{+}=S_{\alpha \lambda }(x_i-\alpha {\partial }_{i}f(x))$. Small coordinates are set exactly to zero. When $\lambda =0$, the soft-thresholding operator is the identity and the proximal gradient mapping reduces to $\nabla f(x)$.

A finite first moment suffices for the velocity, but may not suffice for the printed potential. For example, $W(z)=|z{|}^2/2$ has all the stated properties. If $\mu$ is the law of $(S,0)$ with density $2s^{-3}$ on $s\ge 1$, then $\mathbb{E}S=2$ but $\mathbb{E}{S}^2=\infty$, and $(W\ast \mu )(x)=\infty$ for every $x$. Thus the literal definition of $V$ needs a finite second absolute moment, or another hypothesis ensuring integrability of $W$.

For the specified class ${\mathcal{P}}_1$, define the velocity fields directly by $b_{\mu }=K\ast \mu$ and $b_{\hat{\mu }}=K\ast \hat{\mu }$. Equivalently, use the renormalized interaction potentialThe bounded Hessian matrix and $\nabla W(0)=0$ implyThus $V_{\mathrm{ren}}$ is finite, is twice continuously differentiable in space, and has $\nabla V_{\mathrm{ren}}=\nabla W\ast \mu$, by dominated differentiation under the integral sign. Its rotated negative gradient is exactly $b_{\mu }$. Whenever $W\ast \mu$ is finite, the two potentials differ only by an $x$-independent constant and give the same transport equation.

We check the hypotheses for characteristic representation of a measure-valued continuity equation. For every $x,y$,For any coupling $\gamma \in \Gamma ({\mu }_t,{\hat{\mu }}_t)$, the Lipschitz condition on $K$ also givesTaking the infimum over couplings proves the uniform boundApplying the same estimate at two times of one curve proves time continuity of $b_{\mu }$, uniformly in $x$. Also $|m_1({\mu }_t)-m_1({\mu }_s)|\le d_1({\mu }_t,{\mu }_s)$, so $m_1({\mu }_t)$ is bounded on compact time intervals. Spatial partial derivatives of $b_{\mu }$ are continuous and bounded by $L$, using dominated convergence in space and weak convergence of probability measures in time for the bounded continuous kernel $DK$. All corresponding facts hold for $\hat{\mu }$.

The characteristic representation of a measure-valued continuity equation says that a continuous velocity field, continuously differentiable and globally Lipschitz in space and with locally uniform linear growth, has a global characteristic flow map $X_{\mu }(t;s,a)$ solvingFor each $f\in {\mathcal{P}}_1$, its pushforward measure is the unique weak solution in $C([0,\infty ),{\mathcal{P}}_1)$ of the associated continuity equation. The hypotheses have all been verified above, and the fields have zero divergence, so these are also the two required transport equations. Explicitly,For completeness, the Gronwall inequality givesso these pushforward measures have finite first absolute moments. Integrating $|X_{\mu }(t;0,a)-X_{\mu }(s;0,a)|$ against $f$ proves continuity in the Wasserstein distance. The chain rule proves the weak identity. For uniqueness at a fixed terminal time $t$, use the backward test function $\phi (s,x)=\psi (X_{\mu }(t;s,x))$, where $\psi$ is continuously differentiable with compact support. It satisfies ${\partial }_s\phi +b_{\mu }\cdot \nabla \phi =0$ and has compact spatial support uniformly for $0\le s\le t$, by the backward linear-growth bound. The weak identity with temporal cutoffs therefore gives $\int \psi d{\rho }_t=\int \psi (X_{\mu }(t;0,a))df(a)$, identifying every weak solution with the displayed pushforward measure.

Finally compare the two characteristic curves with the same initial point $a$. Put ${\Delta }_t=X_{\mu }(t;0,a)-X_{\hat{\mu }}(t;0,a)$. The spatial Lipschitz condition and the boxed velocity estimate givefor almost every time; the integral form gives the same conclusion at zeros of $\Delta$. The Gronwall inequality impliesThe pushforward measure $(X_{\mu }(t;0,\cdot ),X_{\hat{\mu }}(t;0,\cdot ){)}_{\#}f$ is a coupling of ${\rho }_t,{\hat{\rho }}_t$. Integrating the last bound against the probability measure $f$ provesThe same constant $L$ depends only on the uniform bound for the Hessian matrix of $W$, and is independent of the prescribed curves and their common initial data.

For a candidate curve $\rho$, define the velocity field by the convolutionIt is well defined with a finite first absolute moment, because $|K(x-z)|\le L(|x|+|z|)$. Equality of mixed partial derivatives givesThe Hessian matrix bound justifies moving a spatial derivative through this convolution. For smooth densities, the transport equation consequently becomes the continuity equationThis form defines the equation for singular probability measures as well. With initial probability measure ${\rho }_0$, a weak solution is a curve in $C([0,\infty ),{\mathcal{P}}_1)$ such that every $\phi \in C_c^1([0,\infty )\times {\mathbb{R}}^2)$ satisfiesUsing smooth test functions gives the same definition by approximation on compact sets. Continuity in the Wasserstein distance bounds first absolute moments on compact time intervals, so the displayed integrals exist.

For the empirical measure, the chain rule and the particle equations giveIntegrating in time, with zero terminal contribution because $\phi$ has compact support, gives precisely the weak identity and the correct initial empirical measure. Thus ${\mu }^N$ is a global weak solution. The self-interaction term vanishes since $K(0)=0$.

SetSymmetry here means $W(-z)=W(z)$, so $\nabla W(0)=0$ and $K(0)=0$. The bounded Hessian matrix and the fact that $J$ is an orthogonal matrix giveThus the particle system is ${\dot{X}}^i=N^{-1}{\sum }_{j}K(X^i-X^j)$. On the configuration space with norm $\Vert X{\Vert }_{\max }={\max }_i|X^i|$, its vector field has Lipschitz constant at most $2L$:The Picard-Lindelöf theorem gives local existence and uniqueness. Linear growth and the Gronwall inequality give $\Vert X(t){\Vert }_{\max }\le e^{2Lt}\Vert X(0){\Vert }_{\max }$, which rules out escape to infinity in finite time and extends the solution to every $t\ge 0$.

The associated empirical measure isHere each ${\delta }_{X^i(t)}$ is a Dirac measure. The finite first absolute moment follows from $\int |x|d{\mu }_t^N=N^{-1}{\sum }_i|X^i(t)|<\infty$. Pairing equal particle labels defines a coupling, soConsequently

Choose a uniform lower bound $\kappa \in \mathbb{R}$ for the Hessian matrix of the confinement potential, so $D^{2}V(x)\ge \kappa I$ for every $x$. A sufficient condition isIndeed, convexity of $V(x)-\kappa |x{|}^2/2$ gives the confinement energy inequality from part (b), now with $\kappa$ possibly negative. Adding it to the equal-mean interaction energy inequality from part (d) givesThis proves positive displacement convexity on every class with fixed barycenter. In particular, if $D^{2}V\ge -KI$ with $K\ge 0$, the sufficient condition is $\lambda >K$ and one may take $\tilde{\lambda }=\lambda -K$. Wherever classical second derivatives exist, the equivalent differential calculation is ${\mathcal{E}}^{\prime \prime }[{\mu }_t]\ge (\kappa +\lambda )D^2$; the integrated proof also covers the printed growth assumptions.

Define the barycenter of a measure by $m_{\mu }=\int xd\mu (x)$. Under $\Pi$, the mean displacement is $\bar{q}=m_{\nu }-m_{\mu }$, and optimality gives $\int |q{|}^{2}d\Pi =D^2$. Expanding the square under the product measure yields the variance identity for independent copies:In the classical regime of part (c), the lower bound on the Hessian matrix of the interaction potential therefore givesFor equal barycenters, this becomes

For the full stated class of probability measures, prove the displacement convexity inequality directly. Pointwise strong convexity of $W$ givesIntegrating, including the $1/2$ in the interaction energy, and using the displayed variance identity for independent copies givesAll terms are finite by quadratic growth and finite second absolute moments. Equal barycenters give the claimed $\lambda$-displacement convexity. Also $m_{{\mu }_t}=(1-t)m_{\mu }+t{m}_{\nu }$, so this metric geodesic remains in the prescribed fixed-mean class. Applying the same argument to subintervals proves the second derivative bound in the sense of distributions even when a classical derivative has not been justified. The mean restriction is natural: translating all particles together leaves their pairwise differences and hence the interaction energy unchanged.

Use an independent copy $(x^{\prime },y^{\prime })$ of $(x,y)$ under the product measure $\Pi \otimes \Pi$. Write $q=y-x$, $q^{\prime }=y^{\prime }-x^{\prime }$, andSince the pushforward measure of $\Pi \otimes \Pi$ under $(z_t,z_t^{\prime })$ is ${\mu }_t\otimes {\mu }_t$, the interaction energy isTwo applications of the chain rule giveThe factor $1/2$ is retained. This classical identity requires differentiation under the integral sign to be justified, just as in part (b). Bounded Hessian matrix of $W$ is sufficient, since $|q-q^{\prime }{|}^2\le 2|q{|}^2+2|q^{\prime }{|}^2$ is integrable; compactly supported endpoints are another sufficient case. The printed quadratic-growth condition alone does not provide this domination.

The failure can occur for the interaction energy too. Take the even interaction potential $W(x)=1-\cos (2\pi x^3)$ and replace the endpoint probability measures in part (b) by $\frac{1}{2}{\delta }_0+\frac{1}{2}\mu$ and $\frac{1}{2}{\delta }_0+\frac{1}{2}\nu$. Keep the origin fixed and translate every other atom by one. This coupling is increasing on the line, hence is optimal: its assigned values extend to a nondecreasing transport map, which is the gradient of a convex function. Differences between translated atoms remain integers, so their mutual interaction vanishes. Only interactions with the origin contribute, giving $\mathcal{W}[{\mu }_t]=F(t)/4$, with $F$ from part (b). It therefore also lacks a finite classical second derivative at $t=1/2$.

Set $q=y-x$ and $z_t=x+tq$. The definition of pushforward measure gives the confinement energy $\mathcal{V}[{\mu }_t]=\int V(z_t)d\Pi$. The chain rule and differentiation under the integral sign, whenever justified, giveFor example, bounded Hessian matrix is sufficient: it gives $|\nabla V(z)|\le C(1+|z|)$, and the first two differentiated integrands are bounded by $C^{\prime }(1+|x{|}^2+|y{|}^2)$. The dominated convergence theorem applies because $\Pi$ has finite second absolute moments. Compactly supported endpoints also suffice because all interpolating points lie in one compact set.

The printed growth assumption alone does not ensure a classical second derivative. Here is a counterexample within the stated assumptions. On the line take the bounded nonnegative smooth functionand the probability measures $\mu ={\sum }_n{p}_n{\delta }_{n-1/2}$, $\nu ={\sum }_n{p}_n{\delta }_{n+1/2}$. Both have finite second absolute moments. Their translation transport plan is optimal: its cost is one, while every coupling has cost at least the square of its mean displacement, also one. At $t_0=1/2$, $z_{t_0}=n$, so $F(t)=\mathcal{V}[{\mu }_t]$ satisfies $F(t_0)=0$. Each summand is nonnegative, and the Fatou lemma givesThus the requested classical identity requires an additional integrability assumption on the Hessian matrix; quadratic growth controls the energy but not its second derivative.

For a confinement potential $V$ that is a $\lambda$-strongly convex function, the derivative formula, where valid, yieldsThe underlying displacement convexity conclusion is valid under the printed assumptions without that extra differentiation hypothesis. Apply convexity of $V(x)-\lambda |x{|}^2/2$ pointwise and integrate:The same argument on every subinterval makes $t\mapsto \mathcal{V}[{\mu }_t]-\lambda D^2{t}^2/2$ convex, so the second derivative lower bound also holds in the sense of distributions.

Put $D=d_2(\mu ,\nu )$ and $z_t(x,y)=(1-t)x+ty$. The marginal distributions of the optimal transport plan $\Pi$ give ${\mu }_0=\mu$ and ${\mu }_1=\nu$. Alsoso ${\mu }_t$ has a finite second absolute moment. For $0\le s<t\le 1$, the pushforward measure $(z_s,z_t{)}_{\#}\Pi$ is a coupling of ${\mu }_s,{\mu }_t$. ThereforeApply the triangle inequality for the second Wasserstein distance along ${\mu }_0,{\mu }_s,{\mu }_t,{\mu }_1$:All inequalities are equalities, including when $D=0$. Thus this displacement interpolation is a constant speed metric geodesic:

Choose the bounded, nonnegative nondecreasing function $\tau$ from part (d), and defineThe function $h$ is convex and nondecreasing. For $0\le a\le 1$, the triangle inequality, monotonicity, and convexity giveHence $U$ is a convex function. By the gradient of a radial function formula and the fundamental theorem of calculus,for $x\ne 0$ whenever $h^{\prime }(|x|)=\tau (|x|)$. A monotone function has at most countably many discontinuities, so part (d) makes the exceptional radii $\tilde{\mu }$-null. The origin is also $\mu$-null. Define $\mathcal{T}(0)=0$; thus $\mathcal{T}=\nabla U$ $\mu$-almost everywhere.

For every $Q$ in the orthogonal group, $\mathcal{T}(Qx)=Q\mathcal{T}(x)$, including at zero. Consequently ${\mathcal{T}}_{\#}\mu$ is invariant under the orthogonal group. Moreover $|\mathcal{T}(x)|=\tau (|x|)$ away from the null origin, and composition of pushforward measures givesPart (c) therefore gives ${\mathcal{T}}_{\#}\mu =\nu$. The Knott–Smith optimality criterion makes a transport map given by a convex function's gradient optimal for the quadratic transport cost. Uniqueness from Brenier's theorem yieldsSince directions agree, this also identifies the optimal value:

Write $d\mu =f(x)dx$, with $f\ge 0$. Applying polar coordinates and Fubini's theorem gives, for bounded nonnegative measurable $h$,Also $\tilde{\mu }(\{0\})=\mu (\{0\})=0$ by absolute continuity of measures. Extending $g$ by zero on the negative half-line proves

Both radial pushforward measures have compact support of a measure, so Brenier's theorem on the line supplies a unique optimal transport plan and a transport map $\tau$, unique $\tilde{\mu }$-almost everywhere, withIn one dimension, the gradient of a convex function is a nondecreasing function. Nonnegativity holds $\tilde{\mu }$-almost everywhere because ${\tau }_{\#}\tilde{\mu }=\tilde{\nu }$ is carried by $[0,\infty )$. To choose a nonnegative, nondecreasing representative everywhere, let $F,G$ be the radial cumulative distribution functions and use the monotone rearrangementAt $F(r)=0$ set $\tau (r)=0$, and at $F(r)=1$ use the largest point of the support of a measure $\tilde{\nu }$. These choices preserve monotonicity and boundedness. Since $F$ is continuous, $F(R)$ has the uniform distribution on $(0,1)$ when $R$ has law $\tilde{\mu }$, and the quantile function $G^{-1}$ sends this uniform distribution to $\tilde{\nu }$. Thus this representative has the required pushforward measure, even if the target has atoms.