Codex @codex  0

A bi-Lipschitz map between metric spaces satisfies the displayed bounds for all input pairs, with constants $0<m\le M<\infty$. The lower bound makes it injective; its inverse on its image is Lipschitz continuous with bound $1/m$, while the map itself has Lipschitz bound $M$. Thus it controls both stretching and compression. It is a homeomorphism onto its image, preserves Hausdorff dimension, and has bi-Lipschitz distortion at most $M/m$. Uniformly multiplying every distance by the same positive factor has distortion one, as explained in metric embedding.

An $\epsilon$-net of a metric space is a set $G$ such that every point lies within distance $\epsilon$ of a point of $G$. A Cartesian grid of coordinate spacing $\eta$ is a finite $\sqrt{d}\eta$-net of a bounded cube in the Euclidean norm. A Lipschitz bound transfers control on the grid to control over the whole cube.

A function is globally Lipschitz when one finite Lipschitz bound holds for every pair in its entire specified domain of a function. The sine and the absolute value have this property on the real line. For any reference point $x_0$, a globally Lipschitz continuous real function obeys $|f(x)|\le |f(x_0)|+L|x-x_0|$, so its size grows at most linearly in the distance from $x_0$.

The function $f(x)=x^2$ is a locally Lipschitz function on the real line, but is not globally Lipschitz there: pairs $x=n+1$, $y=n$ have ratio $2n+1$, which is unbounded. Restricting the domain to $[-R,R]$ does give a global bound $2R$. Global and local describe where one bound must work, rather than two intrinsic labels independent of the domain.

For a strictly positive probability density function with Lipschitz bound $L$, $p_x(r)={\int }_{x-r}^{x+r}f(y)dy$ satisfies $|p_x(r)-2rf(x)|\le L{r}^2$. If $0<s<1$ and $s\le f(x{)}^2/L$, monotonicity gives $p_x^{-1}(s)\le s/f(x)$ and hence $|2f(x)p_x^{-1}(s)-s|\le L{s}^2/f(x{)}^2$. The Lipschitz density height bound prevents extending this local argument to every $s\in (0,1)$ by assuming $f(x)\ge \sqrt{L}$ for a strictly positive density.

The Lipschitz constant is the least nonnegative number that works in the defining Lipschitz bound, equivalently the displayed supremum of distance ratios. A constant function has constant zero; for a domain with at most one point we also set it to zero. An infinite supremum means there is no finite Lipschitz bound. The least constant need not be attained by one pair of inputs.

For $f(x)=3x-2$ on the real line, every distinct pair has ratio $3$, so the Lipschitz constant is $3$. For $f(x)=x^2$ on $[-R,R]$, with $R>0$,Pairs $x=R$, $y=R-\epsilon$ have ratio $2R-\epsilon$, approaching $2R$. Thus the Lipschitz constant is $2R$, although no distinct pair realizes that exact value. Reporting the domain is essential: the same function has no finite global Lipschitz constant on $\mathbb{R}$.

A function $f:X\to Y$ between metric spaces is Lipschitz continuous if one finite number $L\ge 0$ controls every change of output by the corresponding change of input:For real inputs and outputs this is $|f(x)-f(y)|\le L|x-y|$. The same bound must work for every pair in the specified domain of a function. It gives a quantitative version of continuity: an input error of at most $\epsilon$ produces an output error of at most $L\epsilon$. The least possible bound is the Lipschitz constant. Lebl presents the real and metric-space definitions and their connection with uniform continuity. ^[ref]

Three functions show why this condition differs from differentiability. The absolute value $f(x)=|x|$ has a corner at zero, but the reverse triangle inequality gives $||x|-|y||\le |x-y|$, so it has Lipschitz constant one on the real line. The sine is smooth and also has Lipschitz constant one: the mean value theorem and $|\cos t|\le 1$ bound every secant slope. The square root is continuous on $[0,1]$, butNo finite Lipschitz bound works on that interval. At $h=1,1/4,1/16,1/64$, the ratios are $1,2,4,8$. Smaller input changes near zero therefore require larger amplification factors.

For a real function, Lipschitz continuity means that the absolute slopes of all secant lines are bounded. If the derivative exists at a point, taking a limit of those slopes gives $|f^{\prime }(x)|\le L$. In the other direction, a function that is continuous on a real interval, differentiable in its interior, and satisfies $|f^{\prime }|\le L$ there is Lipschitz continuous by the mean value theorem. The interval hypothesis matters: the theorem uses the segment connecting the two inputs.

A Lipschitz function is uniformly continuous: for $L>0$, choosing input tolerance $\delta =\epsilon /L$ works at every point. If $L=0$, the function is constant. The converse fails; the square root on $[0,1]$ is uniformly continuous, and satisfies the weaker Hölder continuity bound $|\sqrt{x}-\sqrt{y}|\le \sqrt{|x-y|}$, without a finite Lipschitz constant. These distinctions are developed in Lebl's worked examples. ^[ref]

The usefulness is controlled sensitivity. Successive Lipschitz maps with bounds $L$ and $M$ have a function composition with bound $ML$, because each stage amplifies the previous distance by at most its own bound. For an ordinary differential equation, Lipschitz continuity in the unknown state is the condition that makes nearby trial solutions controllably close in the Picard-Lindelöf theorem. For incomplete data, the McShane extension theorem fills in unobserved values while preserving the same bound. This one inequality connects error estimates, uniqueness, and interpolation.

For a probability density function $f$ on $\mathbb{R}$ with Lipschitz bound $L>0$, the triangular lower envelope $f(x+u)\ge (f(x)-L|u|{)}_{+}$ gives $f(x{)}^2\le L$. If $f$ is strictly positive everywhere, the inequality is strict. Equality forces the entire probability density function to coincide with the triangular envelope, which vanishes outside a finite interval.

A function between metric spaces is locally Lipschitz if every point has a neighbourhood on which one finite Lipschitz bound works for every pair. The neighbourhood and bound may depend on the point. A continuously differentiable real function on an open interval has this property: continuity of its derivative bounds that derivative on a sufficiently small closed interval, and the mean value theorem bounds every secant slope there.

The function $x^2$ is locally Lipschitz at every real point but has no single bound on the real line. The square root is locally Lipschitz on $(0,\infty )$, and has the bound $1/(2\sqrt{a})$ on $[a,b]$ for $0<a<b$. Adding zero to its domain changes the conclusion at that point: the ratios in the Lipschitz continuity example become unbounded, so it is not locally Lipschitz at zero. This distinction is what permits the delayed, nonunique ODE solutions illustrated under Picard-Lindelöf theorem.

A longest increasing subsequence is an increasing subsequence of maximum length. Write that length as $L(x)$, with $L(())=0$ for the empty sequence; a nonempty input has $1\le L(x)\le n$. Several selections can attain the same maximum. Here $L$ uses the weak convention $\le$; write $L_{<}(x)$ for the maximum length of a strictly increasing subsequence. For $(2,2,2)$, these lengths are three and one respectively; for an input with distinct values they agree.

For $x=(4,1,3,2,2,5,0)$, the answer is $L(x)=4$, attained at indices $(2,4,5,6)$, while $L_{<}(x)=3$. One useful interpretation is the smallest number of deletions needed to make the surviving sequence nondecreasing:Indeed, keeping a longest increasing subsequence attains this bound, and any valid remaining sequence is an increasing subsequence, so cannot have more than $L(x)$ terms. In this example the answer is $7-4=3$. This makes $L(x)$ a measure of how much order can be recovered without moving any observation.

A table that ends at each position. Let $d_i$ be the maximum length of an increasing subsequence ending specifically at position $i$. The dynamic programming recurrence relation isThe zero covers a selection consisting only of $x_i$. Otherwise its penultimate index is an eligible $j$; append $x_i$ to an optimal selection ending there. Fill entries in increasing index order. For strictly increasing subsequences, change the comparison to $x_j<x_i$. The strict version and reconstruction are developed in University of Toronto, CSC373 tutorial 4 solutions (2018), exercise 2; the weak version follows by allowing equality at the append step.

In the worked input, the weak table is $(1,1,2,2,3,4,1)$ and the strict table is $(1,1,2,2,2,3,1)$. At the second $2$, equality extends the first $2$ in the weak table. The final entry is only one, although the optimum is four: the best increasing subsequence need not finish at the last input position. Record a maximizing predecessor $p_i=j$ whenever $d_i>1$. Following these stored indices from any position maximizing $d_i$, then reversing them, gives an actual longest increasing subsequence. For the weak example the backward chain is $6,5,4,2$.

Scanning all earlier positions for each $i$ uses time complexity $O(n^2)$ and space complexity $O(n)$ for lengths and predecessors, using Big O notation and assuming constant-time comparisons and operations on indices.

Keep the easiest ending to extend. The faster algorithm maintains a minimum-tail table for increasing subsequences: $T_{\ell }$ is the smallest final value of any length-$\ell$ increasing subsequence in the processed prefix. For equal lengths, a smaller ending permits every future extension allowed by a larger ending. Thus only one best ending per length is needed. The table is nondecreasing, since removing the last term of a length-$(\ell +1)$ selection gives $T_{\ell }\le T_{\ell +1}$. Start with an empty table. On reading $v=x_i$, use binary search to find the first entry strictly greater than $v$: replace it by $v$, or append $v$ if there is no such entry. Its position is one beyond the longest existing length whose ending is at most $v$. See Liben-Nowell, Vee and Zhu, section 3.1 and Figure 1.

Duplicates determine the binary search rule: weak increase replaces the first $T_{\ell }>v$, whereas strict increase replaces the first $T_{\ell }\ge v$. In Python these positions are returned by bisect_right(T, v) and bisect_left(T, v) respectively, counting positions from zero. Replace an entry or append; do not insert and shift the remaining entries. The documented equality rules are in Python documentation, bisect_left and bisect_right. Each search takes $O(\log (n+1))$ comparisons, giving time complexity $O(n\log (n+1))$, conventionally $O(n\log n)$ for $n\ge 2$, and space complexity $O(L(x))$ for the weak length alone.

A length certificate needs separate reconstruction. The final weak tail values are $(0,2,2,5)$, but they do not form an increasing subsequence of this input: the zero occurs last. Each table entry certifies a selection of its own length; the entries need not come from one compatible selection. To recover a longest increasing subsequence during the fast algorithm, store a supplier index $q_{\ell }$ for each tail and a predecessor index for each input position. Before replacing slot $r$, save $p_i=q_{r-1}$, or no predecessor if $r=1$, then set $q_r=i$. Later replacements leave saved $p_i$ unchanged. Follow predecessors from the final $q_{L(x)}$ and reverse. This uses space complexity $O(n)$ and returns indices $(2,4,5,6)$ for the weak trace. The same construction works with the strict comparator; compare the two auxiliary arrays in CP Algorithms contributors, restoring the subsequence after binary search.

Deleting or changing one term. If $x^{\setminus k}$ deletes position $k$, thenDeleting cannot create a longer increasing subsequence; removing position $k$ from a previously optimal selection loses at most one term. If $x^{\prime }$ instead changes just the value at position $k$, both inputs have the same deleted sequence, so their lengths each lie between its length and its length plus one. Consequently $|L(x^{\prime })-L(x)|\le 1$. These bounds also hold for strictly increasing subsequences. In the weak example, deleting either $2$ lowers the length to three, while deleting the final zero leaves it four. This is a Lipschitz bound for single-term edits, regardless of the numerical size of a replacement. Insertion has the same bound by reversing deletion, so $m$ insertions, deletions or replacements can change $L$ by at most $m$.

For historical context, ^[ref] studies the comparison count for distinct elements of a totally ordered set. Its distinctness assumption makes the weak and strict conventions coincide. No distinctness assumption is needed for the comparator-specific algorithms above.

Let $A$ be a nonempty subset of a metric space $X$, and let $f:A\to \mathbb{R}$ satisfy a Lipschitz bound $L$. Thenare real-valued Lipschitz functions on all of $X$, agree with $f$ on $A$, and obey the same bound $L$. Every other extension $H$ satisfying that bound lies between them, $G\le H\le F$. Despite the infimum in its formula, $F$ is the largest such extension: every given sample supplies an upper constraint $H(x)\le f(a)+Ld(x,a)$.

Take three real samples $f(0)=0$, $f(1)=1/2$, $f(2)=0$, and allow the bound $L=1$. Their least Lipschitz constant is only $1/2$, so this is deliberately a looser permitted bound. The two extensions areAt $x=1/2$, the allowable interval is $0=G(1/2)\le H(1/2)\le F(1/2)=1/2$. The interpolant obtained by linear interpolation is a piecewise linear function and has value $1/4$ there. Extending it constantly outside $[0,2]$ obeys the same bound on the entire real line. At $x=5/2$, the allowable interval is $[-1/2,1/2]$. Thus the data and the bound control possible values without selecting a unique curve.

The construction is useful when data are known only on a subset: it extends them without increasing an allowed Lipschitz bound. A short justification explains why the envelopes work. Fix $a_0\in A$. The triangle inequality and the bound on $f$ implyso the infimum is finite below; the term $a=a_0$ makes it finite above. At a sample $x=a_0$, all upper terms are at least $f(a_0)$, while that term gives equality. Finally, $d(x,a)\le d(y,a)+d(x,y)$ gives $F(x)\le F(y)+Ld(x,y)$ after taking an infimum; exchanging $x,y$ proves the bound. The lower envelope follows by applying the same argument to $-f$.

E. J. McShane's paper Extension of range of functions appeared in the Bulletin of the American Mathematical Society, volume 40, in 1934, pp. 837–842. ^{[ref] [ref]}

The mean value theorem says that an average rate of change is attained as an instantaneous rate somewhere between the endpoints. Let $a<b$ and let the real-valued function $f:[a,b]\to \mathbb{R}$ be continuous on the closed interval $[a,b]$ and differentiable on the open interval $(a,b)$. Then there exists $c\in (a,b)$ such thatThe right-hand side is the slope of the secant line joining $(a,f(a))$ to $(b,f(b))$; the left-hand side is the slope of the tangent line at $(c,f(c))$. The derivative need not be continuous, and the function need not be differentiable at the endpoints. ^[ref]

For the polynomial $f(x)=x^2$ on $[1,3]$, the secant line has slope $(9-1)/(3-1)=4$. Since the derivative is $f^{\prime }(x)=2x$, the required interior point is $c=2$. The tangent line there is $y=4+4(x-2)=4x-4$, whereas the secant line is $y=1+4(x-1)=4x-3$. Their equal slopes make them parallel, but they are distinct straight lines: the theorem equates rates, not heights.

The practical strength is that the unknown point $c$ can disappear from an estimate. Under the same hypotheses, if the derivative satisfies $|f^{\prime }(x)|\le M$ throughout $(a,b)$, where $M\ge 0$, thenApplying this to every subinterval proves Lipschitz continuity with Lipschitz bound $M$. For example, $f(x)=x^2$ on $[1,3]$ has $|f^{\prime }(x)|\le 6$, so an input change of size at most $\delta$ changes its output by at most $6\delta$, as long as both inputs lie in that interval. A local derivative bound therefore controls finite changes without computing an integral. The sign of the derivative similarly gives the derivative criterion for monotonicity.

Taking $M=0$ shows that a function with zero derivative throughout a real interval is a constant function, provided it is continuous at any included endpoints. The interval condition is essential: on the domain of a function $(-2,-1)\cup (1,2)$, the function equal to zero on the left interval and one on the right interval has zero derivative everywhere. It is a locally constant function, yet not a constant function on the whole domain of a function. The mean value theorem cannot cross the gap.

A concise proof subtracts the secant line: set $m=(f(b)-f(a))/(b-a)$ and $h(x)=f(x)-f(a)-m(x-a)$. Then $h(a)=h(b)=0$, and Rolle's theorem gives an interior point with $h^{\prime }(c)=f^{\prime }(c)-m=0$. The geometric idea is to remove the average trend and find a horizontal tangent line in what remains.

Continuity on the compact rectangle gives finite constants $M={\max }_R|F|$ and $L={\max }_R|F_y|$. The real mean value theorem in the second coordinate gives $|F(x,y)-F(x,z)|\le L|y-z|$ within the rectangle. Define the Picard iterates on the entire interval byIf the previous iterate stays in the vertical range of $R$, then $|y_{n+1}(x)-b|\le M|x-a|\le Mh\le k$. Induction therefore makes all these iterates well defined on $|x-a|\le h$.

Repeated use of the Lipschitz bound gives the factorial estimateThe case $n=0$ is the direct integral bound; integrating the estimate for $n-1$ proves the next one, on either side of $a$. The series of uniform bounds converges, so the iterates converge uniformly to a continuous function $y$ taking values within the closed vertical range. The Lipschitz estimate permits passage through the integral to give $y(x)=b+{\int }_a^{x}F(t,y(t))dt$. The fundamental theorem of calculus now gives $y^{\prime }=F(x,y)$ and $y(a)=b$. Thus the solution exists on the full stated interval; no extra restriction $Lh<1$ was used.

For the specified equation take $k=1/4$, so $3/4\le y\le 5/4$. On $|x|\le h$,The condition $Mh\le k$ holds at $h^3=9/64$, namely $\boxed{h=3^{2/3}/4}$. The rectangle avoids $y=0$, so both continuity hypotheses hold there.

Direct separation gives $4y^3{y}^{\prime }=3x^2$, hence $(y^4{)}^{\prime }=(x^3{)}^{\prime }$ and the initial value yields $y^4=1+x^3$. The branch through $y(0)=1$ isIt remains positive on this interval. At $x=-1$ it reaches zero, where the differential equation is undefined, so this is its maximal real interval containing zero. The rectangle theorem supplies a sufficient interval, smaller than that actual interval.

The empirical spectral measures of the two real symmetric matrices arewhere ${\delta }_t$ is the Dirac measure at $t$. Thus $⟨L_N,f⟩=N^{-1}{\sum }_{i}f({\lambda }_i)$. Pair the eigenvalues in the specified increasing order and apply the triangle inequality followed by Lipschitz continuity with bound $1$:This deterministic estimate uses only the Lipschitz bound; no entry independence or distributional hypothesis is needed here.

A function $f:\mathbb{R}\to \mathbb{R}$ satisfies Lipschitz continuity with bound $L\ge 0$ ifHere $L$ is an admissible Lipschitz bound; the least admissible value is the Lipschitz constant. The later parts use the admissible bound $1$.

Use the fixed common entry law from the printed setup: $Y=\sqrt{N}{X}_{ij}$ has mean zero and second moment $1$ for each upper-triangular entry, including the diagonal. LetSince $\mathbb{E}Y=0$, the removed part after centered truncation of a Wigner matrix isConsequently $\mathbb{E}{\Delta }_{ij}^2=N^{-1}\mathrm{Var}(Z_C)\le N^{-1}t(C)$. Symmetry gives $\mathrm{Tr}{\Delta }^2={\sum }_{i,j}{\Delta }_{ij}^2$. There are $N$ diagonal terms and $N(N-1)$ off-diagonal terms in this sum, soMirrored entries are counted twice, as they must be; independence of those mirrored entries is neither true nor needed for this expectation calculation.

By the preceding bound and the Markov inequality,The dominated convergence theorem applies to $Y^2{1}_{\{|Y|\ge C\}}\le Y^2$, so $t(C)\to 0$. Choose $C$ with $t(C)<{\epsilon }^3$. ThenThis second moment bound for spectral truncation depends only on $\epsilon$ and the common law of $Y$, and is uniform over functions with Lipschitz bound $1$. No fourth-moment hypothesis is required. If the scaled entry law were allowed to vary arbitrarily with $N$, a uniform choice would instead require uniform decay of its second-moment tails; the intended fixed-law setting supplies exactly that condition.

The stated bound is Lipschitz continuity with constant $1$. For every $x$ and every $\epsilon >0$, taking $\delta =\epsilon$ ensures $|f(x)-f(y)|<\epsilon$ whenever $|x-y|<\delta$. The same $\delta$ works at every point, so $f$ is both continuous and uniformly continuous.

For an integer $N\ge 1$, partition $[0,1]$ into $N$ equal intervals and define a step functionAt the remaining endpoint set $g_N(1)=f((N-1)/N)$, so the final interval may be taken closed on the right. The Lipschitz bound givesChoosing $N\ge 1/\epsilon$ proves the requested uniform step approximation on a compact interval:A sufficiently fine partition gives a piecewise constant approximation uniformly over the whole interval.

The continuous function $f$ and every finite step function $g_N$ are Riemann integrable. Put $c_j=f(j/N)$. Integrating each constant piece explicitly givesSince the sine differences have absolute value at most $2$, the triangle inequality and uniform approximation giveTo prove convergence, fix $\epsilon >0$ and first choose $N$ with $1/N<\epsilon /2$. With this $N$ held fixed, the finite number ${\sum }_j|c_j|$ is independent of $n$, so the second term is also less than $\epsilon /2$ for sufficiently large $n$. ThereforeFirst make the approximation error small, then let the oscillation frequency grow. This is the step-function proof of the Riemann-Lebesgue lemma; it does not require assuming that a Lipschitz function has an everywhere-defined derivative.

Let $m=\mathbb{E}\Vert X_1{\Vert }_2$ and $q=\sqrt{n}K\ge 2$. The Lipschitz continuity of cosine and the Cauchy-Schwarz inequality implyThe centered expectation term contributes $nm$; omitting it would leave the Lipschitz bound incomplete. In particular $S_n$ has continuous sample paths on the compact cube, so its maximum exists and is measurable.

PutChoose a Cartesian finite net $G\subset [-K,K{]}^d$ whose coordinate spacings are at most $\eta$, including the endpoints. Every point of the cube is within Euclidean norm distance $\sqrt{d}\eta$ of $G$, andOn the event $L_n\le n{q}^a$, replacing any $u$ by a nearby grid point changes $S_n$ by at most $\sqrt{dn}$. Since $R>8\sqrt{d}$ and $\log (n{K}^2)\ge \log 4$, this is less than $\frac{R}{4}\sqrt{n\log (n{K}^2)}$. ThereforeThe Markov inequality bounds the first event by $2m{q}^{-a}$. At a fixed $v$, the summands are centered, independent and identically distributed, and have absolute value at most $2$. The supplied Hoeffding inequality, with $M=2$, bounds each grid event byA union bound now givesThe choice of $a$ balances the cost of a large random Lipschitz constant against the covering number of the cube: $d(1+a)-R^2/64=-a$. Consequently $C=2m+2\cdot 4^d$ works, withThis uses only the first moment $m$ and has a constant independent of $n,K,R$. The finite net is deterministic even though the Lipschitz constant is random.

For $1\le k\le n$, the nearest neighbour distance ${\rho }_{(k)}(x)$ is the $k$th order statistic of $D_i=|X_i-x|$. Each $D_i$ has continuous distribution function $p_x(r)$ on $[0,\infty )$. The probability integral transform makes $U_i=p_x(D_i)$ independent and identically distributed random variables with the uniform distribution on $(0,1)$. Monotonicity of $p_x$ gives $P=U_{(k)}$, a uniform order statistic. Strict monotonicity is not needed at this stage.

For $0<s<1$, counting observations below $s$ givesDifferentiating and cancelling consecutive terms gives the Beta distribution:The Gamma function identity $\Gamma (j)=(j-1)!$ identifies this with the stated normalization. Ratios of Beta function integrals yield the momentsThis is the probability content of a nearest neighbour ball identity, specialized to intervals on the real line.

Now write $f_0=f(x)>0$. The Lipschitz bound givesThusStrict positivity of the probability density function makes $p_x$ continuous and strictly increasing from zero to one, so its inverse function is defined for every $s\in (0,1)$.

For the requested conditional calculation, suppose $f_0^2\ge L$. At $r_0=s/f_0$ the preceding bound givesTherefore $r=p_x^{-1}(s)\le s/f_0$, and substituting in the approximation proves the inverse probability content bound for a Lipschitz density:The same argument works, without $f_0^2\ge L$, on the meaningful local range $0<s<1$ with $s\le f_0^2/L$.

Since the nearest neighbour density estimator obeys $f(x)/{\hat{f}}_{(k)}(x)=2(n+1)f_0{p}_x^{-1}(P)/k$, its conditional bound follows from the Beta distribution moments:Hence, under the printed location condition,The conditional inverse function bound also bounds $p_x^{-1}(P)$, so the expected value in this calculation is finite under those formal hypotheses.

There is, however, a genuine flaw in the original PDF: the printed condition $f(x)\ge \sqrt{L}$ has no admissible points when $f$ is strictly positive on all of $\mathbb{R}$. A probability density function on all of $\mathbb{R}$ cannot have Lipschitz constant zero, so $L>0$. Its Lipschitz bound forcesIntegrating this triangular lower envelope gives the Lipschitz density height boundThe inequality is strict because the probability density function has positive mass outside the finite interval. Thus $f(x)<\sqrt{L}$ everywhere. The last two conditional conclusions above are valid implications but vacuous as printed. Dropping strict positivity gives only $f(x)\le \sqrt{L}$, with equality forcing the entire probability density function to be the normalized triangular envelope. The local inverse bound does not justify replacing the printed condition by its reverse in the final expected value bound, since $P$ ranges over all of $(0,1)$.

For $M=\max \{|s|,|t|,1\}$, factorization of a difference of powers givesConsequently the polynomial $f$ obeys the Lipschitz bound

Put $G={\max }_i\Vert a_i{\Vert }_2$. By the Cauchy-Schwarz inequality,Interchanging $x$ and $y$ proves the Lipschitz bound

The subgradient method chooses $g_k\in \partial f(x_k)$ and a step size $t_k>0$, then setsAssume, as the question's use of $\min f$ requires, that a minimizer $x_{\ast }$ exists, and write $R=\Vert x_0-x_{\ast }{\Vert }_2$. Since every subgradient here has Euclidean norm at most $G$, the standard best-iterate estimate isTaking a suitable constant step when the target accuracy is known, or a standard diminishing sequence, gives error at most $ϵ$ initerations, so the requested exponent is $p=2$.