Introduction and Main Results
Total variation denoising (TVD) is a classical nonparametric regression and denoising method that has been extensively studied in statistics, applied mathematics, and signal processing. It was introduced in the seminal work of Rudin et al. [21 ] , which proposed total variation regularization for two-dimensional image denoising. In one dimension, given observations y 1 , … , y n y_1,\ldots,y_n y 1 , … , y n , the TVD estimator, for λ ≥ 0 \lambda\ge0 λ ≥ 0 , is
θ ^ ( λ ) = arg min θ ∈ R n { 1 2 ∑ i = 1 n ( y i − θ i ) 2 + λ ∑ i = 1 n − 1 ∣ θ i + 1 − θ i ∣ } (1) \widehat{\theta}^{(\lambda)} = \underset{\theta\in\mathbb{R}^n}{\arg\min}\left\{\frac{1}{2}\sum_{i=1}^{n}(y_i-\theta_i)^2+\lambda\sum_{i=1}^{n-1}|\theta_{i+1}-\theta_i|\right\} \tag*{(1)} θ ( λ ) = θ ∈ R n arg min { 2 1 i = 1 ∑ n ( y i − θ i ) 2 + λ i = 1 ∑ n − 1 ∣ θ i + 1 − θ i ∣ } (1)
The total variation (TV) penalty promotes sparsity in the first-order differences of the fitted signal, and consequently the estimator θ ^ ( λ ) \widehat{\theta}^{(\lambda)} θ ( λ ) is piecewise constant. This estimator is also known as the fused lasso ([23 ] ) and is closely related to locally adaptive regression splines ([12 ] ).
In the setting of image denoising, the corresponding TV penalty sums absolute differences across horizontally and vertically adjacent pixels. If G = ( V , E ) G=(V,E) G = ( V , E ) is the 2 D 2D 2 D grid graph, this penalty is
TV G ( θ ) = ∑ { u , v } ∈ E ∣ θ u − θ v ∣ . (2) \operatorname{TV}_G(\theta)=\sum_{\{u,v\}\in E}|\theta_u-\theta_v|. \tag*{(2)} TV G ( θ ) = { u , v } ∈ E ∑ ∣ θ u − θ v ∣. (2)
This is the so-called anisotropic form of the total variation penalty. The definition in (2) extends naturally to any finite undirected graph, yielding graph TVD, also known as the graph fused lasso. This estimator encourages piecewise constant signals on connected regions of the graph; see Tibshirani and Taylor [24 ] for its formulation within generalized lasso, and [27 , 7 , 11 ] for statistical and computational developments.
The nondifferentiable TV penalty couples neighboring coordinates, making the fitted values of θ ^ ( λ ) \widehat{\theta}^{(\lambda)} θ ( λ ) difficult to characterize explicitly. Despite the long history of TVD, an exact pointwise representation was established only recently in the univariate setting by Chatterjee [3 ] . This representation is explicit and expresses each fitted value as a min–max, or equivalently a max–min, of simple functions of local averages over nested intervals containing the target point. It also provides a direct route to pointwise statistical analysis, which is difficult to carry out using the global optimization formulation alone.
In subsequent work, Ghoshal and Chatterjee [6 ] established a corresponding representation for quantile TVD, replacing the averages by suitable local order statistics. Quantile loss is neither differentiable nor strictly convex, and the fitted TVD solution need not be unique. Their formulae characterize the endpoints of the interval of possible fitted values at each coordinate.
These two results raise three natural questions, which we answer in this paper.
Does a similar representation hold for two-dimensional TVD? The results of Chatterjee [3 ] and Ghoshal and Chatterjee [6 ] only hold for the one-dimensional case.
The main contribution of this article is to show that an exact representation holds on every finite graph, including the 2 D 2D 2 D lattice/grid graph. In one dimension, the representation takes a min–max over nested intervals of local averages with correction terms determined by the position of the inner interval within the outer interval. Our graph representation gives a remarkably clean and natural generalization: intervals become connected vertex sets, and the correction is determined by a count of edges leaving the inner set I I I , with opposite signs according to whether they remain inside or leave the outer set J J J .
How is this representation related to the classical isotonic minmax formula? The classical min–max formulas for isotonic regression are a cornerstone of shape-restricted inference: they express a globally constrained estimator through local averages and provide a direct route to its pointwise statistical analysis Robertson et al. [19 ] ; Zhang [28 ] ; Chatterjee et al. [4 ] . We show that these formulas are instances of a more general pointwise representation for graph TVD. In particular, the classical formula over intersections of upper and lower sets on a DAG emerges from our formula over nested connected sets. The bridge is asymmetric TVD, which includes nearly isotonic regression Tibshirani et al. [25 ] , which further agrees exactly with isotonic regression once the penalty exceeds a finite threshold. This places order-constrained estimation and total variation regularization within a common min–max framework.
Does the representation extend to a general convex loss? The quantile result suggests that such minmax representations can hold for TVD with other (possibly nondifferentiable) losses beyond just the squared loss. In this article, we establish a min-max/maxmin representation for arbitrary finite, separable convex losses. This general formula recovers both the squared-loss formula of Chatterjee [3 ] and the quantile formula of Ghoshal and Chatterjee [6 ] .
Taken together, these results establish a unified pointwise min–max characterization of graph TVD, quantile TVD, nearly-isotonic regression, and isotonic regression. In the next section, we give a precise statement of our pointwise min-max representation for graph TVD.
Squared-loss TVD on a general graph
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a finite undirected graph with V ≠ ∅ V\ne\varnothing V = ∅ . Given y ∈ R V y\in\mathbb{R}^{V} y ∈ R V , define the total variation denoising estimator (for the graph G G G ) as follows:
θ ^ ( λ ) = arg min θ ∈ R V { 1 2 ∑ u ∈ V ( y u − θ u ) 2 + λ TV G ( θ ) } (3) \widehat{\theta}^{(\lambda)}=\underset{\theta\in\mathbb{R}^{V}}{\arg\min}\left\{\frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2+\lambda\operatorname{TV}_{G}(\theta)\right\} \tag*{(3)} θ ( λ ) = θ ∈ R V arg min { 2 1 u ∈ V ∑ ( y u − θ u ) 2 + λ TV G ( θ ) } (3)
where
TV G ( θ ) = ∑ { u , v } ∈ E ∣ θ u − θ v ∣ . (4) \operatorname{TV}_{G}(\theta)=\sum_{\{u,v\}\in E}\lvert\theta_u-\theta_v\rvert. \tag*{(4)} TV G ( θ ) = { u , v } ∈ E ∑ ∣ θ u − θ v ∣ . (4)
The objective is strictly convex and coercive, so the minimizer exists and is unique. Write C \mathcal{C} C for the collection of nonempty vertex sets whose induced subgraphs are connected, and let C i = { J ∈ C : i ∈ J } \mathcal{C}_i=\{J\in\mathcal{C}:i\in J\} C i = { J ∈ C : i ∈ J } . For a nonempty set I I I , write y ˉ I = ∣ I ∣ − 1 ∑ u ∈ I y u \bar{y}_I=\lvert I\rvert^{-1}\sum_{u\in I}y_u y ˉ I = ∣ I ∣ − 1 ∑ u ∈ I y u . For disjoint sets A , B ⊆ V A, B \subseteq V A , B ⊆ V , let ∣ E ( A , B ) ∣ |E(A,B)| ∣ E ( A , B ) ∣ denote the number of edges with one endpoint in A A A and the other in B B B .
For any pair of nested subsets ∅ ≠ I ⊆ J ⊆ V \varnothing\ne I \subseteq J \subseteq V ∅ = I ⊆ J ⊆ V , let us define
C I , J = ∣ E ( I , J ∖ I ) ∣ − ∣ E ( I , J c ) ∣ (5) C_{I,J}=|E(I,J\setminus I)|-|E(I,J^{c})| \tag*{(5)} C I , J = ∣ E ( I , J ∖ I ) ∣ − ∣ E ( I , J c ) ∣ (5)
where J c = V ∖ J J^{c}=V\setminus J J c = V ∖ J . Every edge leaving I I I contributes either + 1 +1 + 1 , if it remains inside J J J , or − 1 -1 − 1 , if it leaves J J J as well. Thus C I , J C_{I,J} C I , J is a signed count of the boundary of I I I (number of edges leaving I I I ) with respect to the outer set J J J . We are now ready to state the main result of this paper.
Theorem 1.1 (Pointwise representation for graph TVD). For every finite undirected graph G = ( V , E ) G=(V,E) G = ( V , E ) , every y ∈ R V y\in\mathbb{R}^{V} y ∈ R V , every λ ≥ 0 \lambda\ge0 λ ≥ 0 , and every i ∈ V i\in V i ∈ V ,
θ ^ i ( λ ) = max J ∈ C i min I ∈ C i I ⊆ J { y ˉ I + λ C I , J ∣ I ∣ } (6) \widehat{\theta}^{(\lambda)}_i=\max_{J\in\mathcal{C}_i}\min_{\substack{I\in\mathcal{C}_i\\ I\subseteq J}}\left\{\bar{y}_I+\frac{\lambda C_{I,J}}{|I|}\right\} \tag*{(6)} θ i ( λ ) = J ∈ C i max I ∈ C i I ⊆ J min { y ˉ I + ∣ I ∣ λ C I , J } (6) = min J ∈ C i max I ∈ C i I ⊆ J { y ˉ I − λ C I , J ∣ I ∣ } . (7) =\min_{J\in\mathcal{C}_i}\max_{\substack{I\in\mathcal{C}_i\\ I\subseteq J}}\left\{\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. \tag*{(7)} = J ∈ C i min I ∈ C i I ⊆ J max { y ˉ I − ∣ I ∣ λ C I , J } . (7)
Remark 1. In the above result, the connectedness restrictions on I I I and J J J can be dropped. Both identities remain valid when I I I and J J J range over arbitrary vertex sets satisfying i ∈ I ⊆ J i\in I\subseteq J i ∈ I ⊆ J .
How to read the min–max representation
Fix a vertex i i i . Choose an outer connected set J J J containing i i i , and then an inner connected set I I I such that i ∈ I ⊆ J i\in I\subseteq J i ∈ I ⊆ J . The pair ( I , J ) (I,J) ( I , J ) gives a corrected local average: the ordinary average y ˉ I \bar{y}_I y ˉ I , adjusted by λ C I , J / ∣ I ∣ \lambda C_{I,J}/|I| λ C I , J /∣ I ∣ . In the max–min formula this correction is added; in the min–max formula it is subtracted. The inner optimization compares these corrected averages for a fixed J J J , and the outer optimization then selects among the possible choices of J J J .
Let us consider the toy case when n = 2 n=2 n = 2 , where the graph has two vertices and one edge, and see what the minmax representation gives us. Write y ˉ = ( y 1 + y 2 ) / 2 \bar{y}=(y_1+y_2)/2 y ˉ = ( y 1 + y 2 ) /2 . To find the fitted value at vertex 1, there are two choices of outer set. If J = { 1 } J=\{1\} J = { 1 } , necessarily I = { 1 } I=\{1\} I = { 1 } , and C I , J = − 1 C_{I,J}=-1 C I , J = − 1 . If J = { 1 , 2 } J=\{1,2\} J = { 1 , 2 } , the two choices are I = { 1 } I=\{1\} I = { 1 } , for which C I , J = 1 C_{I,J}=1 C I , J = 1 , and I = { 1 , 2 } I=\{1,2\} I = { 1 , 2 } , for which C I , J = 0 C_{I,J}=0 C I , J = 0 . Thus the min–max identity reads
θ ^ 1 ( λ ) = min { y 1 + λ , max { y 1 − λ , y ˉ } } = proj [ y 1 − λ , y 1 + λ ] ( y ˉ ) . \begin{aligned}
\widehat{\theta}^{(\lambda)}_1=\min\{y_1+\lambda,\max\{y_1-\lambda,\bar{y}\}\} \\
&=\operatorname{proj}_{[y_1-\lambda,y_1+\lambda]}(\bar{y}).
\end{aligned} θ 1 ( λ ) = min { y 1 + λ , max { y 1 − λ , y ˉ }} = proj [ y 1 − λ , y 1 + λ ] ( y ˉ ) .
By symmetry, the corresponding expression for vertex 2 projects y ˉ \bar{y} y ˉ onto [ y 2 − λ , y 2 + λ ] [y_2-\lambda,y_2+\lambda] [ y 2 − λ , y 2 + λ ] . Writing d = y 2 − y 1 d=y_2-y_1 d = y 2 − y 1 and evaluating these projections gives
( θ ^ 1 ( λ ) , θ ^ 2 ( λ ) ) = { ( y ˉ , y ˉ ) , ∣ d ∣ ≤ 2 λ , ( y 1 + λ , y 2 − λ ) , d > 2 λ , ( y 1 − λ , y 2 + λ ) , d < − 2 λ . \begin{pmatrix}\widehat{\theta}^{(\lambda)}_1,\widehat{\theta}^{(\lambda)}_2\end{pmatrix}
=
\begin{cases}
(\bar{y},\bar{y}), & |d|\le2\lambda,\\
(y_1+\lambda,y_2-\lambda), & d>2\lambda,\\
(y_1-\lambda,y_2+\lambda), & d<-2\lambda.
\end{cases} ( θ 1 ( λ ) , θ 2 ( λ ) ) = ⎩ ⎨ ⎧ ( y ˉ , y ˉ ) , ( y 1 + λ , y 2 − λ ) , ( y 1 − λ , y 2 + λ ) , ∣ d ∣ ≤ 2 λ , d > 2 λ , d < − 2 λ .
Hence observations separated by at most 2 λ 2\lambda 2 λ are fused at their average. Otherwise, the two fitted values remain distinct, with each observation shifted toward the other by λ \lambda λ .
Comparison with the 1D Result
On a one-dimensional chain graph, connected vertex sets are intervals. An interval has at most two boundary edges, and (5) recovers the correction factors in Chatterjee [3 ] . For example, when J J J avoids the endpoints { 1 , n } \{1,n\} { 1 , n } , C I , J = 2 C_{I,J}=2 C I , J = 2 if I I I lies strictly inside J J J , C I , J = − 2 C_{I,J}=-2 C I , J = − 2 if I = J I=J I = J , and C I , J = 0 C_{I,J}=0 C I , J = 0 if I I I shares exactly one endpoint with J J J .
In Chatterjee [3 ] , these correction factors were specified case by case, without a unifying formula. Equation (5) reveals their underlying structure: C I , J C_{I,J} C I , J is a signed count of the boundary edges of I I I , with each edge connecting I I I to J ∖ I J\setminus I J ∖ I contributing 1 1 1 , and each edge connecting I I I to J c J^{c} J c contributing − 1 -1 − 1 . This interpretation is purely graph theoretic and makes no reference to the linear ordering of the 1D chain graph. A central contribution of this paper is to identify this graph-theoretic structure and establish that the same signed boundary count yields an exact pointwise min–max representation on every finite graph.
Implications for two-dimensional TVD
On a two-dimensional grid, the representation involves arbitrary connected vertex sets containing the vertex of interest. Unlike connected sets on the 1D chain, these sets need not have a simple geometric form: they can have irregular boundaries and are not restricted to rectangles. Thus the local averages appearing in the formula range over a much richer collection of regions than in one dimension.
The representation does not by itself provide a practical method for computing the estimator. On a two-dimensional grid, the number of admissible pairs I ⊆ J I\subseteq J I ⊆ J can be prohibitively large, making direct enumeration infeasible. Even in one dimension, computation is better handled by specialized algorithms, such as the O ( n ) O(n) O ( n ) dynamic programming algorithm of Johnson [8 ] or the fast direct algorithm of Condat [5 ] , without evaluating the min–max formula.
We anticipate that the representation will instead be useful for studying the pointwise statistical properties of two-dimensional TVD. It expresses each fitted value through maxima and minima of explicit local averages with boundary corrections, making the roles of the observations and the geometry of the graph directly visible. In particular, fixing an outer set J J J in the two representations gives upper and lower bounds on the fitted value. Such bounds offer a starting point for analyzing pointwise estimation error in terms of local signal variation, noise averages, and local geometry of the graph.
A preview of the proof
Why does the representation involve an outer set J J J , an inner set I ⊆ J I\subseteq J I ⊆ J , and a min–max over these choices? An instructive starting point is the following elementary identity, valid for every vector v ∈ R V v\in\mathbb{R}^{V} v ∈ R V :
v i = min J ⊆ V i ∈ J max I ⊆ J i ∈ I v ‾ I , v ‾ I = 1 ∣ I ∣ ∑ u ∈ I v u . (8) v_i=\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}\overline{v}_I,\qquad\overline{v}_I=\frac{1}{\lvert I\rvert}\sum_{u\in I}v_u. \tag*{(8)} v i = J ⊆ V i ∈ J min I ⊆ J i ∈ I max v I , v I = ∣ I ∣ 1 u ∈ I ∑ v u . (8)
To see this, for any J J J containing i i i , choose
I = J ∩ { u ∈ V : v u ≥ v i } . I = J \cap\{u \in V : v_u \ge v_i\}. I = J ∩ { u ∈ V : v u ≥ v i } .
Then v ˉ I ≥ v i \bar{v}_I \ge v_i v ˉ I ≥ v i , so the inner maximum is at least v i v_i v i for every J J J . Conversely, choose
J = { u ∈ V : v u ≤ v i } . J = \{u \in V : v_u \le v_i\}. J = { u ∈ V : v u ≤ v i } .
For this particular J J J , every I ⊆ J I \subseteq J I ⊆ J containing i i i satisfies v ˉ I ≤ v i \bar{v}_I \le v_i v ˉ I ≤ v i , proving the reverse inequality.
The exact same choices of level sets also prove the TVD representation. Write θ ^ = θ ^ ( λ ) \hat{\theta} = \hat{\theta}^{(\lambda)} θ ^ = θ ^ ( λ ) . For every nonempty I ⊆ V I \subseteq V I ⊆ V , the optimality conditions give
θ ^ I = y ˉ I + F ( I , I c ) ∣ I ∣ . \hat{\theta}_I = \bar{y}_I + \frac{\mathcal{F}(I,I^c)}{|I|}. θ ^ I = y ˉ I + ∣ I ∣ F ( I , I c ) .
where F ( I , I c ) \mathcal{F}(I,I^c) F ( I , I c ) can be interpreted as a signed flow across the boundary of I I I , going from I I I to I c I^c I c . Apply the preceding level-set choices with v = θ ^ v = \hat{\theta} v = θ ^ . For the upper bound, the same inner set I I I inside any J J J turns out to satisfy F ( I , I c ) ≤ − λ C I , J \mathcal{F}(I,I^c) \le-\lambda C_{I,J} F ( I , I c ) ≤ − λ C I , J . For the lower bound, the same outer set J J J gives the opposite inequality, F ( I , I c ) ≥ − λ C I , J \mathcal{F}(I,I^c) \ge-\lambda C_{I,J} F ( I , I c ) ≥ − λ C I , J , for every I ⊆ J I \subseteq J I ⊆ J containing i i i . These flow bounds allow the fitted averages in the elementary argument to be replaced by the corrected data averages y ˉ I − λ C I , J / ∣ I ∣ \bar{y}_I - \lambda C_{I,J}/|I| y ˉ I − λ C I , J /∣ I ∣ , with both inequalities going in the required directions.
We feel that this level-set viewpoint makes the mechanics of the proof more transparent than in the earlier one-dimensional arguments of Chatterjee [3 ] and Ghoshal and Chatterjee [6 ] . The full proof is given in § 2 .
Isotonic Regression is a Special Case of TVD
It is well known that isotonic regression admits pointwise minmax/maxmin representations. We first recall the classical formula. Let D = ( V , A ) D = (V,A) D = ( V , A ) be a finite directed acyclic graph (DAG), and write u ⪯ v u \preceq v u ⪯ v if u = v u = v u = v or there is a directed path from u u u to v v v . The isotonic cone is
K D = { θ ∈ R V : θ u ≤ θ v for all ( u , v ) ∈ A } . (9) K_D = \{\theta\in\mathbb{R}^{V} : \theta_u \le\theta_v \text{ for all } (u,v) \in A\}. \tag*{(9)} K D = { θ ∈ R V : θ u ≤ θ v for all ( u , v ) ∈ A } . (9)
A lower set contains every predecessor of each of its vertices; an upper set contains every successor. Equivalently, no directed edge enters a lower set from outside, and no directed edge leaves an upper set. Let L i \mathcal{L}_i L i and U i \mathcal{U}_i U i denote the lower and upper sets containing i i i . The least-squares isotonic regression estimator is defined by
θ ^ i s o = argmin θ ∈ R V : θ u ≤ θ v for all ( u , v ) ∈ A 1 2 ∑ u ∈ V ( y u − θ u ) 2 . \hat{\theta}^{\mathrm{iso}} = \underset{\theta\in\mathbb{R}^{V}:\,\theta_u \le\theta_v\ \text{for all }(u,v)\in A}{\operatorname{argmin}}\ \frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2. θ ^ iso = θ ∈ R V : θ u ≤ θ v for all ( u , v ) ∈ A argmin 2 1 u ∈ V ∑ ( y u − θ u ) 2 .
Its classical pointwise representation is
max U ∈ U i min L ∈ L i y ˉ L ∩ U = θ ^ i i s o = min L ∈ L i max U ∈ U i y ˉ L ∩ U . (10) \max_{U\in\mathcal{U}_i}\min_{L\in\mathcal{L}_i}\bar{y}_{L\cap U}
= \hat{\theta}^{\mathrm{iso}}_i
= \min_{L\in\mathcal{L}_i}\max_{U\in\mathcal{U}_i}\bar{y}_{L\cap U}. \tag*{(10)} U ∈ U i max L ∈ L i min y ˉ L ∩ U = θ ^ i iso = L ∈ L i min U ∈ U i max y ˉ L ∩ U . (10)
This formula plays a major role in the classical theory of order-restricted inference; see Brunk [2 ] , Barlow et al. [1 ] , and Robertson et al. [19 ] .
The resemblance to our TVD representation is immediate, but the connection is less apparent. In one dimension, the isotonic formula optimizes over the two endpoints of a single interval, whereas the TVD formula optimizes over two nested intervals. Moreover, the isotonic formula involves only local averages, without any penalty correction. On a general graph, the distinction is between intersections of upper and lower sets for isotonic regression and pairs of arbitrary nested connected sets for TVD. In these respects, the isotonic formula appears simpler. Nevertheless, as we will argue, it is a special case of our TVD representation.
Write ISO ( y , D ) = θ ^ i s o \operatorname{ISO}(y,D)=\widehat{\theta}^{\mathrm{iso}} ISO ( y , D ) = θ iso for the isotonic estimator and TVD ( y , G , λ ) \operatorname{TVD}(y,\mathcal{G},\lambda) TVD ( y , G , λ ) for symmetric TVD. The following proposition makes their connection explicit.
Proposition 1.2 (Isotonic regression as TVD). Let D = ( V , A ) D=(V,A) D = ( V , A ) be a finite DAG with n = ∣ V ∣ ≥ 1 n=|V|\ge1 n = ∣ V ∣ ≥ 1 , and let G ~ \widetilde{G} G be its underlying undirected graph. Define
d u = deg D + ( u ) − deg D − ( u ) , y ~ u ( λ ) = y u − λ 2 d u , d_u=\deg_D^{+}(u)-\deg_D^{-}(u),\qquad\widetilde{y}^{(\lambda)}_u=y_u-\frac{\lambda}{2}d_u, d u = deg D + ( u ) − deg D − ( u ) , y u ( λ ) = y u − 2 λ d u , where deg D + ( u ) \deg_D^{+}(u) deg D + ( u ) and deg D − ( u ) \deg_D^{-}(u) deg D − ( u ) denote the out-degree and in-degree of u u u . Then, for every
λ > λ 0 : = n ( max u ∈ V y u − min u ∈ V y u ) , \lambda>\lambda_0:=n\left(\max_{u\in V}y_u-\min_{u\in V}y_u\right), λ > λ 0 := n ( u ∈ V max y u − u ∈ V min y u ) , we have
ISO ( y , D ) = TVD ( y ~ ( λ ) , G ~ , λ 2 ) . (11) \operatorname{ISO}(y,D)=\operatorname{TVD}\left(\widetilde{y}^{(\lambda)},\widetilde{G},\frac{\lambda}{2}\right). \tag*{(11)} ISO ( y , D ) = TVD ( y ( λ ) , G , 2 λ ) . (11)
As we will show in this article, applying our TVD formula to these transformed observations recovers the classical isotonic representation (10) . In this sense, our pointwise min–max representation for graph TVD is a strict and seemingly far-reaching generalization of Brunk’s classical formula for isotonic regression. We now present our general strategy for showing the reduction from isotonic regression to TVD as in Proposition 1.2. It involves going through two intermediate classes of estimators, namely asymmetric TVD and nearly isotonic regression.
Asymmetric TVD
Let D = ( V , A ) D=(V,A) D = ( V , A ) be a finite DAG. For λ + , λ − ≥ 0 \lambda_{+},\lambda_{-}\geq0 λ + , λ − ≥ 0 , define the asymmetric TVD estimator by
\begin{aligned}
\widehat{\theta}^{(\lambda_{+},\lambda_{-})}
&=\mathop{\arg\min}_{\theta\in\mathbb{R}^{V}}\left\{
\frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2
+\lambda_{+}\sum_{(u,v)\in A}(\theta_v-\theta_u)_{+}\\
&\qquad\qquad\qquad\qquad
+\lambda_{-}\sum_{(u,v)\in A}(\theta_v-\theta_u)_{-}
\right\}. \tag*{(12)}
\end{aligned}
where x + = max { x , 0 } x_{+}=\max\{x,0\} x + = max { x , 0 } and x − = max { − x , 0 } x_{-}=\max\{-x,0\} x − = max { − x , 0 } . Thus, increases and decreases along a directed edge receive penalties λ + \lambda_{+} λ + and λ − \lambda_{-} λ − , respectively.
The elementary identity
λ + x + + λ − x − = a ∣ x ∣ + b x , a = λ + + λ − 2 , b = λ + − λ − 2 , \lambda_{+}x_{+}+\lambda_{-}x_{-}=a|x|+bx,
\qquad
a=\frac{\lambda_{+}+\lambda_{-}}{2},
\qquad
b=\frac{\lambda_{+}-\lambda_{-}}{2}, λ + x + + λ − x − = a ∣ x ∣ + b x , a = 2 λ + + λ − , b = 2 λ + − λ − ,
allows us to express the asymmetric penalty as a symmetric TV penalty plus a linear function of θ \theta θ . Indeed, let
d u = deg D + ( u ) − deg D − ( u ) d_u=\deg^{+}_{D}(u)-\deg^{-}_{D}(u) d u = deg D + ( u ) − deg D − ( u )
denote the out-degree minus the in-degree of vertex u u u . Applying the identity to each edge and using
∑ ( u , v ) ∈ A ( θ v − θ u ) = − ∑ u ∈ V d u θ u , \sum_{(u,v)\in A}(\theta_v-\theta_u)=-\sum_{u\in V}d_u\theta_u, ( u , v ) ∈ A ∑ ( θ v − θ u ) = − u ∈ V ∑ d u θ u ,
we obtain
λ + ∑ ( u , v ) ∈ A ( θ v − θ u ) + + λ − ∑ ( u , v ) ∈ A ( θ v − θ u ) − = a ∑ ( u , v ) ∈ A ∣ θ v − θ u ∣ − b ∑ u ∈ V d u θ u . (13) \begin{aligned}
\lambda_{+}\sum_{(u,v)\in A}(\theta_v-\theta_u)_{+}
+\lambda_{-}\sum_{(u,v)\in A}(\theta_v-\theta_u)_{-}
&=a\sum_{(u,v)\in A}|\theta_v-\theta_u|
-b\sum_{u\in V}d_u\theta_u. \tag*{(13)}
\end{aligned} λ + ( u , v ) ∈ A ∑ ( θ v − θ u ) + + λ − ( u , v ) ∈ A ∑ ( θ v − θ u ) − = a ( u , v ) ∈ A ∑ ∣ θ v − θ u ∣ − b u ∈ V ∑ d u θ u . (13)
Absorbing the linear term into the squared loss by completing the square gives the following reduction.
Lemma 1.3 (Asymmetric TVD as symmetric TVD). Let G ~ \widetilde{G} G be the underlying undirected graph of D D D . With a , b , d a,b,d a , b , d as above, define the shifted data vector
y ~ u = y u + b d u , u ∈ V . \widetilde{y}_u=y_u+bd_u,\qquad u\in V. y u = y u + b d u , u ∈ V . Then
θ ^ ( λ + , λ − ) = TVD ( y ~ , G ~ , a ) . (14) \widehat{\theta}^{(\lambda_{+},\lambda_{-})}
=\operatorname{TVD}(\widetilde{y},\widetilde{G},a). \tag*{(14)} θ ( λ + , λ − ) = TVD ( y , G , a ) . (14) Thus, asymmetric TVD is symmetric TVD applied to suitably transformed observations.
Nearly Isotonic Regression
Taking λ + = 0 \lambda_{+}=0 λ + = 0 and λ − = λ \lambda_{-}=\lambda λ − = λ in (12) gives the nearly isotonic estimator
NearIso ( y , D , λ ) = arg min θ ∈ R V { 1 2 ∑ u ∈ V ( y u − θ u ) 2 + λ ∑ ( u , v ) ∈ A ( θ v − θ u ) − } . (15) \operatorname{NearIso}(y,D,\lambda)=\mathop{\arg\min}_{\theta\in\mathbb{R}^{V}}\left\{\frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2+\lambda\sum_{(u,v)\in A}(\theta_v-\theta_u)_{-}\right\}. \tag*{(15)} NearIso ( y , D , λ ) = arg min θ ∈ R V ⎩ ⎨ ⎧ 2 1 u ∈ V ∑ ( y u − θ u ) 2 + λ ( u , v ) ∈ A ∑ ( θ v − θ u ) − ⎭ ⎬ ⎫ . (15)
The penalty consists of only violations of the isotonic inequalities θ u ≤ θ v \theta_u\le\theta_v θ u ≤ θ v , with larger values of λ \lambda λ imposing a greater cost on such violations.
Nearly isotonic regression in the univariate setting was introduced by Tibshirani et al. [25 ] , who developed an algorithm for its entire solution path. Extensions to directed graphs have been studied by Minami [13 ] ; Pastukhov [15 , 16 ] .
For this choice of penalty,
a = λ 2 , b = − λ 2 . a=\frac{\lambda}{2},\qquad b=-\frac{\lambda}{2}. a = 2 λ , b = − 2 λ .
Lemma 1.3 therefore gives the following reduction.
Corollary 1.4 (Nearly isotonic regression as TVD). Let G ~ \widetilde{G} G be the underlying undirected graph of D D D , and let d u = deg D + ( u ) − deg D − ( u ) d_u=\deg_D^{+}(u)-\deg_D^{-}(u) d u = deg D + ( u ) − deg D − ( u ) . Then, for every λ ≥ 0 \lambda\ge0 λ ≥ 0 ,
NearIso ( y , D , λ ) = TVD ( y − λ 2 d , G ~ , λ 2 ) . (16) \operatorname{NearIso}(y,D,\lambda)=\operatorname{TVD}\left(y-\frac{\lambda}{2}d,\widetilde{G},\frac{\lambda}{2}\right). \tag*{(16)} NearIso ( y , D , λ ) = TVD ( y − 2 λ d , G , 2 λ ) . (16)
The next lemma shows that nearly isotonic regression agrees exactly with isotonic regression once the penalty exceeds an explicit finite threshold.
Lemma 1.5 (Exact agreement with isotonic regression). Let D = ( V , A ) D=(V,A) D = ( V , A ) be a finite DAG with n = ∣ V ∣ ≥ 1 n=|V|\ge1 n = ∣ V ∣ ≥ 1 , and set
λ 0 = n ( max u ∈ V y u − min u ∈ V y u ) . \lambda_0=n\left(\max_{u\in V}y_u-\min_{u\in V}y_u\right). λ 0 = n ( u ∈ V max y u − u ∈ V min y u ) . For every λ > λ 0 \lambda>\lambda_0 λ > λ 0 ,
NearIso ( y , D , λ ) = ISO ( y , D ) . (17) \operatorname{NearIso}(y,D,\lambda)=\operatorname{ISO}(y,D). \tag*{(17)} NearIso ( y , D , λ ) = ISO ( y , D ) . (17)
Remark 3. As λ → ∞ \lambda\to\infty λ → ∞ , violations of the order constraints become increasingly costly, suggesting convergence to isotonic regression. Lemma 1.5 strengthens this limiting statement to exact agreement at a finite penalty.
Remark 4. The threshold λ 0 \lambda_0 λ 0 is only a sufficient bound: exact agreement may occur for smaller values of λ \lambda λ , and we do not claim that λ 0 \lambda_0 λ 0 is the smallest threshold for a given y y y .
Combining Corollary 1.4 with Lemma 1.5 proves Proposition 1.2.
From Nested Sets to Upper and Lower Sets
We have thus traced a chain of special cases: isotonic regression is a special case of nearly isotonic regression, which is a special case of asymmetric TVD, which in turn reduces to symmetric TVD after a shift of the observations. A single TVD minmax formula therefore unifies all four estimators.
Our TVD minmax representation can be shown to recover the classical isotonic formula. The mechanism behind this is worth highlighting here. After substituting the transformed observations and the penalty parameter into the min–max representation, the correction terms involving C I , J C_{I,J} C I , J , combined with the data shift, simplify considerably. Since the penalty is sufficiently large, any outer set J J J with an incoming edge is ruled out: the inner choice I = J I=J I = J produces a large positive correction, making the inner maximum too large to attain the outer minimum over J J J . Thus only lower sets J = L J=L J = L remain. For such an L L L , any inner set I I I with an edge directed from I I I to L ∖ I L\setminus I L ∖ I receives a large negative correction and is excluded by the inner maximization. The surviving inner sets are therefore upper sets relative to L L L , precisely the intersections I = L ∩ U I=L\cap U I = L ∩ U with U U U an upper set. On these pairs the combined correction from the data shift and TV penalty vanishes, leaving only the local averages y ˉ L ∩ U \bar{y}_{L\cap U} y ˉ L ∩ U as in the classical formula. The max–min representation follows by reversing the roles of upper and lower sets. The full proof is given in § 3 .
General convex losses and nonunique solutions
Our interest in extending the pointwise representation beyond squared loss began with quantile regression. Given the importance of quantile regression [10 ] in statistics, it is natural to ask for an analogous description of TVD for quantile regression. For 0 < τ < 1 0<\tau<1 0 < τ < 1 , let ρ τ ( r ) = τ r + + ( 1 − τ ) r − \rho_\tau(r)=\tau r_{+}+(1-\tau)r_{-} ρ τ ( r ) = τ r + + ( 1 − τ ) r − . In the univariate setting, the quantile TVD problem is defined as
S λ τ = arg min θ ∈ R n { ∑ i = 1 n ρ τ ( y i − θ i ) + λ ∑ i = 1 n − 1 ∣ θ i + 1 − θ i ∣ } . (18) \mathcal{S}_{\lambda}^{\tau}=\underset{\theta\in\mathbb{R}^{n}}{\arg\min}\left\{\sum_{i=1}^{n}\rho_{\tau}(y_i-\theta_i)+\lambda\sum_{i=1}^{n-1}\lvert\theta_{i+1}-\theta_i\rvert\right\}. \tag*{(18)} S λ τ = θ ∈ R n arg min { i = 1 ∑ n ρ τ ( y i − θ i ) + λ i = 1 ∑ n − 1 ∣ θ i + 1 − θ i ∣ } . (18)
Unlike squared loss, quantile loss is not strictly convex, so the minimizer need not be unique. Recall that a function f : C → R f:C\to\mathbb{R} f : C → R on a convex set C ⊆ R d C\subseteq\mathbb{R}^{d} C ⊆ R d is strictly convex if
f ( ( 1 − t ) x + t y ) < ( 1 − t ) f ( x ) + t f ( y ) f\left((1-t)x+ty\right)<(1-t)f(x)+tf(y) f ( ( 1 − t ) x + t y ) < ( 1 − t ) f ( x ) + t f ( y )
for every distinct x , y ∈ C x,y\in C x , y ∈ C and every t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) . Strict convexity guarantees uniqueness of a minimizer whenever one exists.
This raises a basic question: in the absence of a unique fitted value, what could a pointwise minmax representation characterize?
In the one dimensional case, Ghoshal and Chatterjee [6 ] answer this question by characterizing the set of possible fitted values at each coordinate. To state their result in our notation, let I i \mathcal{I}_i I i be the intervals containing i i i , and compute C I , J C_{I,J} C I , J for the 1D chain graph as in (5) . For any nonempty set I I I , write y I , ( k ) y_{I,(k)} y I , ( k ) for its k k k th order statistic, with the conventions
y I , ( k ) = − ∞ ( k ≤ 0 ) , y I , ( k ) = + ∞ ( k > ∣ I ∣ ) . y_{I,(k)}=-\infty\quad(k\le0),\qquad y_{I,(k)}=+\infty\quad(k>|I|). y I , ( k ) = − ∞ ( k ≤ 0 ) , y I , ( k ) = + ∞ ( k > ∣ I ∣ ) .
Then,
{ θ i : θ ∈ S λ τ } = [ θ ^ i τ , θ ‾ i τ ] , (19) \{\theta_i:\theta\in S_\lambda^\tau\}=[\widehat{\theta}_i^\tau,\overline{\theta}_i^\tau], \tag*{(19)} { θ i : θ ∈ S λ τ } = [ θ i τ , θ i τ ] , (19)
where
θ ^ i τ = max J ∈ I i min I ∈ I i I ⊆ J y I , ( ⌈ τ ∣ I ∣ + λ C I , J ⌉ ) , (20) \widehat{\theta}_i^\tau=\max_{J\in\mathcal{I}_i}\min_{\substack{I\in\mathcal{I}_i\\I\subseteq J}}y_{I,(\lceil\tau|I|+\lambda C_{I,J}\rceil)}, \tag*{(20)} θ i τ = J ∈ I i max I ∈ I i I ⊆ J min y I , (⌈ τ ∣ I ∣ + λ C I , J ⌉) , (20)
θ ‾ i τ = min J ∈ I i max I ∈ I i I ⊇ J y I , ( ⌊ τ ∣ I ∣ − λ C I , J ⌋ + 1 ) . (21) \overline{\theta}_i^\tau=\min_{J\in\mathcal{I}_i}\max_{\substack{I\in\mathcal{I}_i\\I\supseteq J}}y_{I,(\lfloor\tau|I|-\lambda C_{I,J}\rfloor+1)}. \tag*{(21)} θ i τ = J ∈ I i min I ∈ I i I ⊇ J max y I , (⌊ τ ∣ I ∣ − λ C I , J ⌋ + 1 ) . (21)
Thus, the possible fitted values at coordinate i i i form an interval whose left and right endpoints are, respectively, a maxmin and a minmax of corrected local τ \tau τ -quantiles over the inner interval I I I . The quantile ranks are adjusted by the same boundary correction C I , J C_{I,J} C I , J that appears in the squared-loss representation of Chatterjee [3 ] and its graph extension above.
Moreover, both endpoint vectors θ ^ τ = ( θ ^ i τ ) i = 1 n \widehat{\theta}^\tau=(\widehat{\theta}_i^\tau)_{i=1}^{n} θ τ = ( θ i τ ) i = 1 n and θ ‾ τ = ( θ ‾ i τ ) i = 1 n \overline{\theta}^\tau=(\overline{\theta}_i^\tau)_{i=1}^{n} θ τ = ( θ i τ ) i = 1 n belong to S λ τ S_\lambda^\tau S λ τ . Thus, the endpoints are attained simultaneously at every coordinate by the componentwise smallest and largest solutions, respectively.
This result suggests three further questions. Does the interval description persist for an arbitrary convex loss? Can its endpoints be expressed by a common minmax/maxmin formula that includes both squared loss and quantile loss? And can such a characterization hold on any finite graph? The answer to all these questions is yes. The interval property follows from convexity and compactness; the substantive issue is to identify its endpoints explicitly and show that they are attained simultaneously by two extremal solutions.
Let G = ( V , E ) G=(V,E) G = ( V , E ) be a finite undirected graph, and let ℓ u : R → R \ell_u:\mathbb{R}\to\mathbb{R} ℓ u : R → R , u ∈ V u\in V u ∈ V , be finite convex functions, with dependence on y u y_u y u left implicit. For λ ≥ 0 \lambda\ge0 λ ≥ 0 , define the generalized graph TVD problem
F λ ( θ ) = ∑ u ∈ V ℓ u ( θ u ) + λ TV G ( θ ) , S λ = arg min θ ∈ R V F λ ( θ ) . (22) F_\lambda(\theta)=\sum_{u\in V}\ell_u(\theta_u)+\lambda\operatorname{TV}_G(\theta),\qquad S_\lambda=\underset{\theta\in\mathbb{R}^{V}}{\arg\min}\ F_\lambda(\theta). \tag*{(22)} F λ ( θ ) = u ∈ V ∑ ℓ u ( θ u ) + λ TV G ( θ ) , S λ = θ ∈ R V arg min F λ ( θ ) . (22)
We assume that F λ F_\lambda F λ is coercive, meaning that F λ ( θ ) → + ∞ F_\lambda(\theta)\to+\infty F λ ( θ ) → + ∞ as ∥ θ ∥ → ∞ \lVert\theta\rVert\to\infty ∥ θ ∥ → ∞ . This ensures that the solution set S λ S_\lambda S λ is nonempty and compact. A simple sufficient condition is that each ℓ u \ell_u ℓ u is coercive, that is, ℓ u ( x ) → + ∞ \ell_u(x)\to+\infty ℓ u ( x ) → + ∞ as ∣ x ∣ → ∞ |x|\to\infty ∣ x ∣ → ∞ : since TV G ≥ 0 \operatorname{TV}_G\ge0 TV G ≥ 0 , we then have
F λ ( θ ) ≥ ∑ u ∈ V ℓ u ( θ u ) → + ∞ as ∥ θ ∥ → ∞ . F_\lambda(\theta)\ge\sum_{u\in V}\ell_u(\theta_u)\to+\infty\qquad\text{as }\lVert\theta\rVert\to\infty. F λ ( θ ) ≥ u ∈ V ∑ ℓ u ( θ u ) → + ∞ as ∥ θ ∥ → ∞.
Individual coercivity is not necessary, however; see Remark 9. We emphasize that, beyond finiteness and convexity of the losses, our only requirement is coercivity of the full objective. This is a mild regularity condition, satisfied by squared, quantile, and Huber losses, and by logistic TVD under the conditions in Remark 9. In particular, neither differentiability nor strict convexity is required.
To define the local quantities in our representation, we first recall some facts from univariate convex analysis. Let h : R → R h:\mathbb{R}\to\mathbb{R} h : R → R be a finite convex function. Then, h h h is continuous, and its left and right derivatives, denoted by h − ′ h'_{-} h − ′ and h + ′ h'_{+} h + ′ , exist and are finite everywhere. Both derivatives are nondecreasing and satisfy h − ′ ( t ) ≤ h + ′ ( t ) h'_{-}(t) \le h'_{+}(t) h − ′ ( t ) ≤ h + ′ ( t ) for every t ∈ R t \in\mathbb{R} t ∈ R ; see Rockafellar [20 ] . Define
r − ( h ) = inf { t : h + ′ ( t ) ≥ 0 } , r_{-}(h)=\inf\{t:h'_{+}(t)\ge0\}, r − ( h ) = inf { t : h + ′ ( t ) ≥ 0 } ,
r + ( h ) = sup { t : h − ′ ( t ) ≤ 0 } , (23) r_{+}(h)=\sup\{t:h'_{-}(t)\le0\}, \tag*{(23)} r + ( h ) = sup { t : h − ′ ( t ) ≤ 0 } , (23)
with inf ∅ = + ∞ \inf\varnothing=+\infty inf ∅ = + ∞ and sup ∅ = − ∞ \sup\varnothing=-\infty sup ∅ = − ∞ .
Remark 5. By convexity and continuity, the set of minimizers of h h h , when nonempty, is a closed interval, possibly unbounded or a singleton. If this interval is bounded, its left and right endpoints are r − ( h ) r_{-}(h) r − ( h ) and r + ( h ) r_{+}(h) r + ( h ) , respectively. See § 6.1 for a proof.
Remark 6. The same endpoint interpretation holds when the minimizing interval is unbounded, with endpoints understood in the extended real line. For example, if h ( t ) = t + h(t)=t_{+} h ( t ) = t + , then arg min h = ( − ∞ , 0 ] \arg\min h=(-\infty,0] arg min h = ( − ∞ , 0 ] , so r − ( h ) = − ∞ r_{-}(h)=-\infty r − ( h ) = − ∞ and r + ( h ) = 0 r_{+}(h)=0 r + ( h ) = 0 . The quantities r − ( h ) r_{-}(h) r − ( h ) and r + ( h ) r_{+}(h) r + ( h ) remain well defined even when the infimum is not attained. For instance, if h ( t ) = e t h(t)=e^{t} h ( t ) = e t , there is no minimizer, but r − ( h ) = r + ( h ) = − ∞ r_{-}(h)=r_{+}(h)=-\infty r − ( h ) = r + ( h ) = − ∞ , reflecting that the infimum is approached as t → − ∞ t\to-\infty t → − ∞ . Similarly, h ( t ) = e − t h(t)=e^{-t} h ( t ) = e − t gives r − ( h ) = r + ( h ) = + ∞ r_{-}(h)=r_{+}(h)=+\infty r − ( h ) = r + ( h ) = + ∞ .
For nonempty nested sets I ⊆ J I\subseteq J I ⊆ J , set
q I , J − = r − ( t ↦ ∑ u ∈ I ℓ u ( t ) − λ C I , J t ) (24) q^{-}_{I,J}=r_{-}\left(t\mapsto\sum_{u\in I}\ell_u(t)-\lambda C_{I,J}t\right) \tag*{(24)} q I , J − = r − ( t ↦ u ∈ I ∑ ℓ u ( t ) − λ C I , J t ) (24)
q I , J + = r + ( t ↦ ∑ u ∈ I ℓ u ( t ) + λ C I , J t ) . (25) q^{+}_{I,J}=r_{+}\left(t\mapsto\sum_{u\in I}\ell_u(t)+\lambda C_{I,J}t\right). \tag*{(25)} q I , J + = r + ( t ↦ u ∈ I ∑ ℓ u ( t ) + λ C I , J t ) . (25)
The quantities q I , J − q^{-}_{I,J} q I , J − and q I , J + q^{+}_{I,J} q I , J + describe local fits (on I I I ), the fitting objective ∑ u ∈ I ℓ u ( t ) \sum_{u\in I}\ell_u(t) ∑ u ∈ I ℓ u ( t ) is modified by a linear function with slope − λ C I , J -\lambda C_{I,J} − λ C I , J or + λ C I , J +\lambda C_{I,J} + λ C I , J , where C I , J C_{I,J} C I , J is the correction factor defined in (1.5).
More precisely, q I , J − q^{-}_{I,J} q I , J − is the smallest minimizer of ∑ u ∈ I ℓ u ( t ) − λ C I , J t \sum_{u\in I}\ell_u(t)-\lambda C_{I,J}t ∑ u ∈ I ℓ u ( t ) − λ C I , J t , while q I , J + q^{+}_{I,J} q I , J + is the largest minimizer of ∑ u ∈ I ℓ u ( t ) + λ C I , J t \sum_{u\in I}\ell_u(t)+\lambda C_{I,J}t ∑ u ∈ I ℓ u ( t ) + λ C I , J t . If either extreme minimizer does not exist, the corresponding quantity is interpreted using the extended-real definitions of r − r_{-} r − and r + r_{+} r + above.
For example, under squared loss ℓ u ( t ) = 1 2 ( y u − t ) 2 \ell_u(t)=\frac{1}{2}(y_u-t)^2 ℓ u ( t ) = 2 1 ( y u − t ) 2 , these quantities reduce to
q I , J − = y ˉ I + λ C I , J ∣ I ∣ , q I , J + = y ˉ I − λ C I , J ∣ I ∣ . q^{-}_{I,J}=\bar{y}_I+\frac{\lambda C_{I,J}}{|I|},\qquad q^{+}_{I,J}=\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}. q I , J − = y ˉ I + ∣ I ∣ λ C I , J , q I , J + = y ˉ I − ∣ I ∣ λ C I , J .
Thus, they generalize the corrected local averages appearing in the squared-loss representation.
Similarly, under quantile loss ℓ u ( t ) = ρ τ ( y u − t ) \ell_u(t)=\rho_{\tau}(y_u-t) ℓ u ( t ) = ρ τ ( y u − t ) , it can be checked that
q I , J − = y I , ( ⌈ τ ∣ I ∣ + λ C I , J ⌉ ) , q I , J + = y I , ( ⌊ τ ∣ I ∣ − λ C I , J ⌋ + 1 ) , q^{-}_{I,J}=y_{I,(\lceil\tau|I|+\lambda C_{I,J}\rceil)},\qquad q^{+}_{I,J}=y_{I,(\lfloor\tau|I|-\lambda C_{I,J}\rfloor+1)}, q I , J − = y I , (⌈ τ ∣ I ∣ + λ C I , J ⌉) , q I , J + = y I , (⌊ τ ∣ I ∣ − λ C I , J ⌋ + 1 ) ,
with the order-statistic conventions given above. Thus, the same construction yields corrected local averages for squared loss and corrected local quantiles for quantile loss. We now state our main result.
Theorem 1.6 (Pointwise representation under convex loss). Let G = ( V , E ) G=(V,E) G = ( V , E ) be a finite undirected graph with V ≠ ∅ V\ne\varnothing V = ∅ , let ℓ u : R → R \ell_u:\mathbb{R}\to\mathbb{R} ℓ u : R → R , u ∈ V u\in V u ∈ V , be finite convex functions, and let λ ≥ 0 \lambda\ge0 λ ≥ 0 . Suppose that F λ F_\lambda F λ in (22) is coercive. Then, the following statements hold.
(i) For every i ∈ V i\in V i ∈ V , the set of possible fitted values at coordinate i i i is a nonempty compact interval:
{ θ i : θ ∈ S λ } = [ θ ^ i , θ ‾ i ] . (26) \{\theta_i:\theta\in S_\lambda\}=[\widehat{\theta}_i,\overline{\theta}_i]. \tag*{(26)} { θ i : θ ∈ S λ } = [ θ i , θ i ] . (26) (ii) The endpoints are given by
θ ^ i = max J ∈ C i I ∈ C i I ⊆ J q I , J − , (27) \widehat{\theta}_i=\max_{\substack{J\in\mathcal{C}_i\\ I\in\mathcal{C}_i\\ I\subseteq J}}q_{I,J}^{-}, \tag*{(27)} θ i = J ∈ C i I ∈ C i I ⊆ J max q I , J − , (27) θ ‾ i = min J ∈ C i I ∈ C i I ⊆ J q I , J + . (28) \overline{\theta}_i=\min_{\substack{J\in\mathcal{C}_i\\ I\in\mathcal{C}_i\\ I\subseteq J}}q_{I,J}^{+}. \tag*{(28)} θ i = J ∈ C i I ∈ C i I ⊆ J min q I , J + . (28) Both formulas remain valid when I I I and J J J range over all vertex sets satisfying i ∈ I ⊆ J i\in I\subseteq J i ∈ I ⊆ J , without connectedness restrictions. The final minmax/maxmin values are finite, although individual q I , J − q_{I,J}^{-} q I , J − and q I , J + q_{I,J}^{+} q I , J + may be infinite.
(iii) The solution set S λ S_\lambda S λ is a lattice under pointwise minimum and maximum, i.e., if θ , η ∈ S λ \theta,\eta\in S_\lambda θ , η ∈ S λ , then θ ∧ η \theta\wedge\eta θ ∧ η and θ ∨ η \theta\vee\eta θ ∨ η also belong to S λ S_\lambda S λ , where the two operations are taken coordinatewise. Together with compactness, this implies that S λ S_\lambda S λ has a coordinatewise smallest solution θ ^ = ( θ ^ i ) i ∈ V \widehat{\theta}=(\widehat{\theta}_i)_{i\in V} θ = ( θ i ) i ∈ V and a coordinatewise largest solution θ ‾ = ( θ ‾ i ) i ∈ V \overline{\theta}=(\overline{\theta}_i)_{i\in V} θ = ( θ i ) i ∈ V . These solutions attain the lower and upper endpoints, respectively, simultaneously at every coordinate, and every θ ∈ S λ \theta\in S_\lambda θ ∈ S λ satisfies
θ ^ i ≤ θ i ≤ θ ‾ i for all i ∈ V . \widehat{\theta}_i\le\theta_i\le\overline{\theta}_i\qquad\text{for all }i\in V. θ i ≤ θ i ≤ θ i for all i ∈ V . (iv) If F λ F_\lambda F λ is strictly convex, in particular if every ℓ u \ell_u ℓ u is strictly convex, then θ ^ = θ ‾ \widehat{\theta}=\overline{\theta} θ = θ , and S λ S_\lambda S λ consists of a unique solution.
Remark 7. Although every value in [ θ ^ i , θ ‾ i ] [\widehat{\theta}_i,\overline{\theta}_i] [ θ i , θ i ] is attained at coordinate i i i by some solution, arbitrary choices from these intervals need not combine to form a solution. In particular, S λ S_\lambda S λ need not equal the Cartesian product ∏ i ∈ V [ θ ^ i , θ ‾ i ] \prod_{i\in V}[\widehat{\theta}_i,\overline{\theta}_i] ∏ i ∈ V [ θ i , θ i ] . The theorem nevertheless guarantees that the vectors θ ^ \widehat{\theta} θ and θ ‾ \overline{\theta} θ are both solutions.
The above theorem gives a complete characterization of each coordinate projection of the solution set of the generalized TVD problem on graphs.
For squared loss, part (iv) applies, and Theorem 1.6 recovers Theorem 1.1 as a special case. The generality of the result lies in its applicability to arbitrary finite, separable convex losses: neither strict convexity nor differentiability is required, only the mild additional assumption that the full objective is coercive.
Intuition behind the general representation
We briefly explain the reasoning that led us to Theorem 1.6 . Our starting point was the case of differentiable, strictly convex losses, where the minimizer is unique and the loss terms enter the optimality conditions through their ordinary derivatives. Arguments similar to those for squared loss suggest retaining the same max–min and min–max structure, with the corrected local averages replaced by solutions of the scalar equations
∑ u ∈ I ℓ u ′ ( t ) = λ C I , J and ∑ u ∈ I ℓ u ′ ( t ) = − λ C I , J , \sum_{u\in I}\ell'_u(t)=\lambda C_{I,J}
\qquad\text{and}\qquad
\sum_{u\in I}\ell'_u(t)=-\lambda C_{I,J}, u ∈ I ∑ ℓ u ′ ( t ) = λ C I , J and u ∈ I ∑ ℓ u ′ ( t ) = − λ C I , J ,
respectively. When these solutions exist for every admissible pair I , J I,J I , J , the fitted value is the max–min of the solutions to the first equation, or equivalently the min–max of those to the second. For squared loss, these solutions are precisely the corrected averages in Theorem 1.1 . For losses of the form ℓ u ( t ) = b ( t ) − y u t \ell_u(t)=b(t)-y_ut ℓ u ( t ) = b ( t ) − y u t , with b b b differentiable and strictly convex, as arising in exponential families, the equations reduce to
b ′ ( t ) = y ˉ I ± λ C I , J ∣ I ∣ . b'(t)=\bar{y}_I\pm\frac{\lambda C_{I,J}}{\lvert I\rvert}. b ′ ( t ) = y ˉ I ± ∣ I ∣ λ C I , J .
Since b ′ b' b ′ is strictly increasing, this yields the same max–min and min–max formulas as in the squared-loss case for the transformed fitted values b ′ ( θ ^ i ) b'(\hat{\theta}_i) b ′ ( θ ^ i ) ; see Remark 8.
For general convex losses, the minimizer need no longer be unique. Under our assumptions, however, the solution set S λ S_\lambda S λ is convex and compact, so the possible fitted values at each coordinate form a nonempty compact interval. We therefore sought representations of the smallest and largest possible fitted values.
A key step was to recognize the scalar equations above as the optimality conditions for minimizing
f I , J ( t ) = ∑ u ∈ I ℓ u ( t ) − λ C I , J t , f ~ I , J ( t ) = ∑ u ∈ I ℓ u ( t ) + λ C I , J t . f_{I,J}(t)=\sum_{u\in I}\ell_u(t)-\lambda C_{I,J}t,\qquad
\tilde{f}_{I,J}(t)=\sum_{u\in I}\ell_u(t)+\lambda C_{I,J}t. f I , J ( t ) = u ∈ I ∑ ℓ u ( t ) − λ C I , J t , f ~ I , J ( t ) = u ∈ I ∑ ℓ u ( t ) + λ C I , J t .
These local optimization problems remain meaningful without differentiability or strict convexity. Their minimizers may be nonunique, but whenever they exist, they form an interval.
To see how this suggests a representation of the extremal fitted values, fix a vertex i i i and consider the min–max operator
T i ( a ) = min J ∈ C i I ∈ C i I ⊆ J a I , J . T_i(a)=\min_{\substack{J\in\mathcal{C}_i\\ I\in\mathcal{C}_i\\ I\subseteq J}}a_{I,J}. T i ( a ) = J ∈ C i I ∈ C i I ⊆ J min a I , J .
This operator is nondecreasing in each input: if a I , J ≤ b I , J a_{I,J}\le b_{I,J} a I , J ≤ b I , J for every admissible pair ( I , J ) (I,J) ( I , J ) , then T i ( a ) ≤ T i ( b ) T_i(a)\le T_i(b) T i ( a ) ≤ T i ( b ) . The corresponding max–min operator has the same monotonicity property. Thus, when each input ranges over a compact interval, choosing all their lower endpoints gives the smallest output, while choosing all their upper endpoints gives the largest.
This suggested that the smallest possible fitted value should be the max–min of the smallest minimizers of f I , J f_{I,J} f I , J , while the largest possible fitted value should be the min–max of the largest minimizers of f ~ I , J \tilde{f}_{I,J} f ~ I , J . This was the intuition behind the definitions of q I , J q_{I,J} q I , J and q I , J + q^+_{I,J} q I , J + . Formulating these quantities carefully also accommodates local problems with unbounded solution sets or no minimizer. Theorem 1.6 confirms this intuition, extending the familiar formulas for a unique solution to characterize the smallest and largest possible fitted values.
We next apply this result to quantile TVD on graphs.
Quantile TVD on graphs
For 0 < τ < 1 0 < \tau< 1 0 < τ < 1 , consider quantile TVD on a finite undirected graph G = ( V , E ) G = (V, E) G = ( V , E ) :
S λ τ = arg min θ ∈ R V { ∑ u ∈ V ρ τ ( y u − θ u ) + λ TV G ( θ ) } . (29) S_{\lambda}^{\tau} = \mathop{\arg\min}_{\theta\in\mathbb{R}^{V}} \left\{ \sum_{u \in V} \rho_{\tau}(y_u - \theta_u) + \lambda\operatorname{TV}_{G}(\theta) \right\}. \tag*{(29)} S λ τ = arg min θ ∈ R V { u ∈ V ∑ ρ τ ( y u − θ u ) + λ TV G ( θ ) } . (29)
The quantile losses are finite and convex, and the objective is coercive. Applying Theorem 1.6 therefore gives the following result.
Proposition 1.7 (Pointwise representation for graph quantile TVD). Let G = ( V , E ) G = (V, E) G = ( V , E ) be a finite undirected graph with V ≠ ∅ V \ne\varnothing V = ∅ . For every y ∈ R V y \in\mathbb{R}^{V} y ∈ R V , 0 < τ < 1 0 < \tau< 1 0 < τ < 1 , and λ ≥ 0 \lambda\ge0 λ ≥ 0 , the following statements hold.
(i) For every i ∈ V i \in V i ∈ V , the set of possible fitted values at coordinate i i i is a nonempty compact interval:
{ θ i : θ ∈ S λ τ } = [ θ ^ i τ , θ ^ ‾ i τ ] . \{\theta_i : \theta\in S_{\lambda}^{\tau}\} = [\widehat{\theta}^{\tau}_i, \overline{\widehat{\theta}}^{\tau}_i]. { θ i : θ ∈ S λ τ } = [ θ i τ , θ i τ ] . (ii) The endpoints are given by
θ ^ i τ = max J ∈ C i min I ∈ C i I ⊆ J y I , ( ⌈ τ ∣ I ∣ + λ C I , J ⌉ ) . (30) \widehat{\theta}^{\tau}_i =
\max_{J \in\mathcal{C}_i}
\min_{\substack{I \in\mathcal{C}_i \\ I \subseteq J}}
y_{I,(\lceil\tau|I| + \lambda C_{I,J} \rceil)}. \tag*{(30)} θ i τ = J ∈ C i max I ∈ C i I ⊆ J min y I , (⌈ τ ∣ I ∣ + λ C I , J ⌉) . (30) θ ^ ‾ i τ = min J ∈ C i max I ∈ C i I ⊆ J y I , ( ⌊ τ ∣ I ∣ − λ C I , J ⌋ + 1 ) . (31) \overline{\widehat{\theta}}^{\tau}_i =
\min_{J \in\mathcal{C}_i}
\max_{\substack{I \in\mathcal{C}_i \\ I \subseteq J}}
y_{I,(\lfloor\tau|I| - \lambda C_{I,J} \rfloor+ 1)}. \tag*{(31)} θ i τ = J ∈ C i min I ∈ C i I ⊆ J max y I , (⌊ τ ∣ I ∣ − λ C I , J ⌋ + 1 ) . (31) Both formulas remain valid when I I I and J J J range over all vertex sets satisfying i ∈ I ⊆ J i \in I \subseteq J i ∈ I ⊆ J , without connectedness restrictions. The values are finite, although individual order statistics in the formulas may be infinite under the conventions below.
(iii) The endpoint vectors θ ^ τ = ( θ ^ i τ ) i ∈ V \widehat{\theta}^{\tau} = (\widehat{\theta}^{\tau}_i)_{i \in V} θ τ = ( θ i τ ) i ∈ V and θ ^ ‾ τ = ( θ ^ ‾ i τ ) i ∈ V \overline{\widehat{\theta}}^{\tau} = (\overline{\widehat{\theta}}^{\tau}_i)_{i \in V} θ τ = ( θ i τ ) i ∈ V belong to S λ τ S_{\lambda}^{\tau} S λ τ . They are its coordinatewise smallest and largest solutions, respectively, and satisfy
θ ^ i τ ≤ θ i ≤ θ ^ ‾ i τ for every θ ∈ S λ τ and every i ∈ V . \widehat{\theta}^{\tau}_i \le\theta_i \le\overline{\widehat{\theta}}^{\tau}_i
\qquad\text{for every } \theta\in S_{\lambda}^{\tau} \text{ and every } i \in V. θ i τ ≤ θ i ≤ θ i τ for every θ ∈ S λ τ and every i ∈ V . Thus, the lower and upper endpoints are attained simultaneously at every coordinate by θ ^ τ \widehat{\theta}^{\tau} θ τ and θ ^ ‾ τ \overline{\widehat{\theta}}^{\tau} θ τ , respectively.
This proposition generalizes the result of Ghoshal and Chatterjee [6 ] from the one-dimensional chain graph to arbitrary finite graphs. Intervals on the chain graph are replaced by connected vertex sets, while the corrected ranks retain the same form. Recall here that y I , ( k ) y_{I,(k)} y I , ( k ) denotes the k k k th order statistic of { y u : u ∈ I } \{y_u : u \in I\} { y u : u ∈ I } for 1 ≤ k ≤ ∣ I ∣ 1 \le k \le|I| 1 ≤ k ≤ ∣ I ∣ , with the conventions
y I , ( k ) = − ∞ ( k ≤ 0 ) , y I , ( k ) = + ∞ ( k > ∣ I ∣ ) . y_{I,(k)} = -\infty\quad(k \le0), \qquad y_{I,(k)} = +\infty\quad(k > |I|). y I , ( k ) = − ∞ ( k ≤ 0 ) , y I , ( k ) = + ∞ ( k > ∣ I ∣ ) .
where b : R → R b:\mathbb{R}\to\mathbb{R} b : R → R is differentiable and strictly convex, provided the objective F λ F_\lambda F λ is coercive. Writing g = ( b ′ ) − 1 g=(b')^{-1} g = ( b ′ ) − 1 , the local quantities become
q I , J − = g ( y ˉ I + λ C I , J ∣ I ∣ ) , q_{I,J}^{-}=g\left(\bar{y}_{I}+\frac{\lambda C_{I,J}}{|I|}\right), q I , J − = g ( y ˉ I + ∣ I ∣ λ C I , J ) ,
q I , J + = g ( y ˉ I − λ C I , J ∣ I ∣ ) . q_{I,J}^{+}=g\left(\bar{y}_{I}-\frac{\lambda C_{I,J}}{|I|}\right). q I , J + = g ( y ˉ I − ∣ I ∣ λ C I , J ) .
with extended-real interpretations inherited from the scalar endpoint definitions in (23) . Since g g g is increasing, it commutes with the maxima and minima in the representation. Consequently,
b ′ ( θ ^ ) = TVD ( y , G , λ ) , b'(\hat{\theta})=\operatorname{TVD}(y,G,\lambda), b ′ ( θ ^ ) = TVD ( y , G , λ ) ,
where b ′ b' b ′ acts coordinatewise and the right-hand side denotes squared-loss graph TVD with the same penalty parameter. This recovers the equivalence between TVD under exponential-family loss and TVD under squared loss on arbitrary graphs established by Sadhanala et al. [22 ] , and yields explicit pointwise representations for the corresponding natural-parameter estimates. Examples include logistic TVD, with b ( t ) = log ( 1 + e t ) b(t)=\log(1+e^t) b ( t ) = log ( 1 + e t ) , and Poisson TVD, with b ( t ) = e t b(t)=e^t b ( t ) = e t ; see also van de Geer [26 ] for theoretical properties of logistic TVD.
Beyond exponential-family likelihoods, the theorem can be applied to Huber-loss TVD, considered computationally by Polson and Scott [17 ] , who do not provide a pointwise characterization of the fitted values. Since Huber loss is not strictly convex, the solution need not be unique. Theorem 1.6 gives exact pointwise minmax/maxmin representations for the coordinatewise smallest and largest solutions on arbitrary graphs, with the local quantities obtained by substituting the Huber loss into (24) and (25) .
Remark 9 (Coercivity for logistic TVD). Individual coercivity of the losses is not necessary for Theorem 1.6 to hold. Let G G G be connected, let y u ∈ { 0 , 1 } y_u\in\{0,1\} y u ∈ { 0 , 1 } , and consider
F λ ( θ ) = ∑ u ∈ V { log ( 1 + e θ u ) − y u θ u } + λ TV G ( θ ) , λ > 0. F_\lambda(\theta)=\sum_{u\in V}\{\log(1+e^{\theta_u})-y_u\theta_u\}+\lambda\operatorname{TV}_G(\theta),\qquad\lambda>0. F λ ( θ ) = u ∈ V ∑ { log ( 1 + e θ u ) − y u θ u } + λ TV G ( θ ) , λ > 0.
Although none of the individual logistic losses is coercive, F λ F_\lambda F λ is coercive as long as the observations include both a zero and a one. Hence Theorem 1.6 applies. Moreover, F λ F_\lambda F λ is strictly convex, so the solution is unique. A proof is given in § 6.2 .
Isotonic regression under convex loss
The connection to isotonic regression also extends to general convex losses. For the isotonic result below, we assume that each individual loss is coercive. Let D = ( V , A ) D=(V,A) D = ( V , A ) be a finite DAG with V ≠ ∅ V\ne\varnothing V = ∅ , and use the isotonic cone K D K_D K D and the lower and upper sets from § 1.2 . Consider the generalized isotonic regression problem
S i s o = a r g m i n θ ∈ K D ∑ u ∈ V ℓ u ( θ u ) . (32) S_{\mathrm{iso}}=\mathop{\rm arg\,min}_{\theta\in K_D}\sum_{u\in V}\ell_u(\theta_u). \tag*{(32)} S iso = arg min θ ∈ K D u ∈ V ∑ ℓ u ( θ u ) . (32)
where the losses ℓ u \ell_u ℓ u are finite convex functions that are coercive on R \mathbb{R} R . For nonempty B ⊆ V B\subseteq V B ⊆ V , define
q B − = r − ( t ↦ ∑ u ∈ B ℓ u ( t ) ) , q B + = r + ( t ↦ ∑ u ∈ B ℓ u ( t ) ) . (33) q_B^{-}=r_-\left(t\mapsto\sum_{u\in B}\ell_u(t)\right),\qquad q_B^{+}=r_+\left(t\mapsto\sum_{u\in B}\ell_u(t)\right). \tag*{(33)} q B − = r − ( t ↦ u ∈ B ∑ ℓ u ( t ) ) , q B + = r + ( t ↦ u ∈ B ∑ ℓ u ( t ) ) . (33)
These quantities give the smallest and largest optimal constant fits (w.r.t the losses) on B B B .
Theorem 1.8 (Convex-loss isotonic representation). Under the assumptions above, the following statements hold.
(i) For every i ∈ V i \in V i ∈ V , the set of possible fitted values at coordinate i i i is a nonempty compact interval:
{ θ i : θ ∈ S i s o } = [ θ ^ i i s o , θ ‾ i i s o ] . \{\theta_i:\theta\in S_{\mathrm{iso}}\} = [\widehat{\theta}^{\mathrm{iso}}_i,\overline{\theta}^{\mathrm{iso}}_i]. { θ i : θ ∈ S iso } = [ θ i iso , θ i iso ] . (ii) The endpoints are given by
θ ^ i i s o = max U ∈ U i min L ∈ L i q L ∩ U − , (34) \widehat{\theta}^{\mathrm{iso}}_i = \max_{U\in\mathcal{U}_i}\min_{L\in\mathcal{L}_i}q^-_{L\cap U}, \tag*{(34)} θ i iso = U ∈ U i max L ∈ L i min q L ∩ U − , (34) θ ‾ i i s o = min L ∈ L i max U ∈ U i q L ∩ U + . (35) \overline{\theta}^{\mathrm{iso}}_i = \min_{L\in\mathcal{L}_i}\max_{U\in\mathcal{U}_i}q^+_{L\cap U}. \tag*{(35)} θ i iso = L ∈ L i min U ∈ U i max q L ∩ U + . (35) (iii) The solution set S i s o S_{\mathrm{iso}} S iso is a lattice under pointwise minimum and maximum: if θ , η ∈ S i s o \theta,\eta\in S_{\mathrm{iso}} θ , η ∈ S iso , then θ ∧ η \theta\wedge\eta θ ∧ η and θ ∨ η \theta\vee\eta θ ∨ η also belong to S i s o S_{\mathrm{iso}} S iso . Together with compactness, this implies that S i s o S_{\mathrm{iso}} S iso has a coordinatewise smallest solution θ ^ i s o = ( θ ^ i i s o ) i ∈ V \widehat{\theta}^{\mathrm{iso}}=(\widehat{\theta}^{\mathrm{iso}}_i)_{i\in V} θ iso = ( θ i iso ) i ∈ V and a coordinatewise largest solution θ ‾ i s o = ( θ ‾ i i s o ) i ∈ V \overline{\theta}^{\mathrm{iso}}=(\overline{\theta}^{\mathrm{iso}}_i)_{i\in V} θ iso = ( θ i iso ) i ∈ V . These solutions attain the lower and upper endpoints, respectively, simultaneously at every coordinate, and every θ ∈ S i s o \theta\in S_{\mathrm{iso}} θ ∈ S iso satisfies
θ ^ i i s o ≤ θ i ≤ θ ‾ i i s o for all i ∈ V . \widehat{\theta}^{\mathrm{iso}}_i \le\theta_i \le\overline{\theta}^{\mathrm{iso}}_i \qquad\text{for all } i \in V. θ i iso ≤ θ i ≤ θ i iso for all i ∈ V . (iv) If θ ↦ ∑ u ∈ V ℓ u ( θ u ) \theta\mapsto\sum_{u\in V}\ell_u(\theta_u) θ ↦ ∑ u ∈ V ℓ u ( θ u ) is strictly convex on K D \mathcal{K}_D K D , in particular if every ℓ u \ell_u ℓ u is strictly convex, then θ ^ i s o = θ ‾ i s o \widehat{\theta}^{\mathrm{iso}}=\overline{\theta}^{\mathrm{iso}} θ iso = θ iso , and S i s o S_{\mathrm{iso}} S iso consists of a unique solution.
For squared loss, q B − = q B + = y ˉ B q^-_B=q^+_B=\bar{y}_B q B − = q B + = y ˉ B , recovering (10) . For quantile loss,
q B − = y B , ( ⌈ τ ∣ B ∣ ⌉ ) , q B + = y B , ( ⌊ τ ∣ B ∣ ⌋ + 1 ) , q^-_B=y_{B,(\lceil\tau|B|\rceil)}, \qquad q^+_B=y_{B,(\lfloor\tau|B|\rfloor+1)}, q B − = y B , (⌈ τ ∣ B ∣ ⌉) , q B + = y B , (⌊ τ ∣ B ∣ ⌋ + 1 ) ,
so the theorem gives the extremal isotonic quantile fits.
The proof follows the same sequence of ideas as in the proof of the square loss case as described in § 3 . Basically the result follows by reducing graph isotonic regression to graph TVD through asymmetric TVD and nearly isotonic regression, and then applying Theorem 1.6 .
Minmax representations for isotonic mean and quantile regression are classical. Extensions to more general losses also have substantial precedents. Robertson and Wright [18 ] obtain such representations on partial orders under a Cauchy mean-value condition; Mösching and Dümbgen [14 ] give extremal-solution formulas for coercive losses on a chain graph, including quantile loss; and Jordan et al. [9 ] develop minmax characterizations for set-valued identifiable functionals on arbitrary partial orders. Theorem 1.8 provides a general formulation of the isotonic minmax representation on arbitrary finite DAGs: it allows arbitrary finite, convex, coercive losses at the vertices and characterizes both extremal solutions without assuming differentiability or strict convexity. This formulation may be of independent interest in shape-restricted inference. The key point is that our graph TVD representation strictly generalizes the isotonic minmax framework: the representation for isotonic regression under general convex losses follows as a special case.
Proof of Theorem 1.1
Write θ ^ = θ ^ ( λ ) \widehat{\theta}=\widehat{\theta}^{(\lambda)} θ = θ ( λ ) . We will first prove (1.6)–(1.7) over arbitrary sets J , I J,I J , I containing i i i and then justify why the connected set restriction holds.
Step 1: Optimality Conditions
Define the TVD objective function
f ( θ ) : = 1 2 ∑ u ∈ V ( y u − θ u ) 2 + λ ∑ { u , v } ∈ E ∣ θ u − θ v ∣ . f(\theta):=\frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2+\lambda\sum_{\{u,v\}\in E}|\theta_u-\theta_v|. f ( θ ) := 2 1 u ∈ V ∑ ( y u − θ u ) 2 + λ { u , v } ∈ E ∑ ∣ θ u − θ v ∣.
Since f f f is convex, KKT conditions imply that θ ^ \widehat{\theta} θ is a minimizer of f f f if and only if 0 ∈ ∂ ( f ) ( θ ^ ) 0\in\partial(f)(\widehat{\theta}) 0 ∈ ∂ ( f ) ( θ ) , where ∂ ( f ) ( θ ^ ) \partial(f)(\widehat{\theta}) ∂ ( f ) ( θ ) is the set of subgradients of f f f at θ ^ \widehat{\theta} θ . Now, let us express f f f as
f ( θ ) = 1 2 ∑ u ∈ V ( y u − θ u ) 2 + λ ∑ { u , v } ∈ E h u v ( θ ) . f(\theta)=\frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2+\lambda\sum_{\{u,v\}\in E}h_{uv}(\theta). f ( θ ) = 2 1 u ∈ V ∑ ( y u − θ u ) 2 + λ { u , v } ∈ E ∑ h uv ( θ ) .
Here h u v ( θ ) = ∣ θ u − θ v ∣ h_{uv}(\theta)=|\theta_u-\theta_v| h uv ( θ ) = ∣ θ u − θ v ∣ . Since both the loss function and h u v h_{uv} h uv are convex and finite, one can apply the sum rule for subdifferentials. To this end, let us calculate the subgradient of the TVD objective function with respect to the coordinate θ u \theta_u θ u . For the squared-error term,
∂ ∂ θ u { 1 2 ∑ v ∈ V ( θ v − y v ) 2 } = θ u − y u . \frac{\partial}{\partial\theta_u}\left\{\frac{1}{2}\sum_{v\in V}(\theta_v-y_v)^2\right\}=\theta_u-y_u. ∂ θ u ∂ { 2 1 v ∈ V ∑ ( θ v − y v ) 2 } = θ u − y u .
For every edge { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E , consider quantities satisfying
s u v ∈ { { λ } , θ ^ v > θ ^ u , [ − λ , λ ] , θ ^ v = θ ^ u , { − λ } , θ ^ v < θ ^ u . s_{uv}\in
\begin{cases}
\{\lambda\}, & \widehat{\theta}_v>\widehat{\theta}_u,\\
[-\lambda,\lambda], & \widehat{\theta}_v=\widehat{\theta}_u,\\
\{-\lambda\}, & \widehat{\theta}_v<\widehat{\theta}_u.
\end{cases} s uv ∈ ⎩ ⎨ ⎧ { λ } , [ − λ , λ ] , { − λ } , θ v > θ u , θ v = θ u , θ v < θ u .
Here the ordering of the pair ( u , v ) (u,v) ( u , v ) is important: s u v s_{uv} s uv denotes the quantity associated with the edge { u , v } \{u,v\} { u , v } when viewed from u u u toward v v v . For the reverse ordering, we set s v u = − s u v s_{vu}=-s_{uv} s v u = − s uv . Then, the contribution of the total variation penalty to the subgradient of f f f with respect to θ u \theta_u θ u is precisely − ∑ v : { u , v } ∈ E s u v -\sum_{v:\{u,v\}\in E}s_{uv} − ∑ v : { u , v } ∈ E s uv .
Consequently, θ ^ \widehat{\theta} θ is a minimizer if and only if there exist such edge variables satisfying
θ ^ u − y u = ∑ v : { u , v } ∈ E s u v , u ∈ V . (36) \widehat{\theta}_u-y_u=\sum_{v:\{u,v\}\in E}s_{uv},\qquad u\in V. \tag*{(36)} θ u − y u = v : { u , v } ∈ E ∑ s uv , u ∈ V . (36)
Step 2: A Set Version of the Optimality Conditions.
Fix any nonempty set I ⊆ V I\subseteq V I ⊆ V . Summing the optimality conditions (36) over all vertices in I I I , we obtain
∑ u ∈ I ( θ ^ u − y u ) = ∑ u ∈ I ∑ v ∈ V { u , v } ∈ E s u v = ∑ u ∈ I ∑ v ∈ I { u , v } ∈ E s u v + ∑ u ∈ I ∑ v ∈ I c { u , v } ∈ E s u v = ∑ u ∈ I ∑ v ∈ I c { u , v } ∈ E s u v . \sum_{u\in I}(\widehat{\theta}_u-y_u)
= \sum_{u\in I}\sum_{\substack{v\in V\\ \{u,v\}\in E}}s_{uv}
= \sum_{u\in I}\sum_{\substack{v\in I\\ \{u,v\}\in E}}s_{uv}
+ \sum_{u\in I}\sum_{\substack{v\in I^c\\ \{u,v\}\in E}}s_{uv}
= \sum_{u\in I}\sum_{\substack{v\in I^c\\ \{u,v\}\in E}}s_{uv}. u ∈ I ∑ ( θ u − y u ) = u ∈ I ∑ v ∈ V { u , v } ∈ E ∑ s uv = u ∈ I ∑ v ∈ I { u , v } ∈ E ∑ s uv + u ∈ I ∑ v ∈ I c { u , v } ∈ E ∑ s uv = u ∈ I ∑ v ∈ I c { u , v } ∈ E ∑ s uv .
The last equality follows because, if { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E with u , v ∈ I u,v\in I u , v ∈ I , then the edge appears once as s u v s_{uv} s uv and once as s v u s_{vu} s v u , and by definition, s v u = − s u v s_{vu}=-s_{uv} s v u = − s uv .
Now let us introduce the following notation. For two disjoint sets A , B ⊆ V A,B\subseteq V A , B ⊆ V , define
F ( A , B ) = ∑ u ∈ A , v ∈ B { u , v } ∈ E s u v . \mathcal{F}(A,B)=\sum_{\substack{u\in A,v\in B\\ \{u,v\}\in E}}s_{uv}. F ( A , B ) = u ∈ A , v ∈ B { u , v } ∈ E ∑ s uv .
With this notation,
∑ u ∈ I ( θ ^ u − y u ) = F ( I , I c ) . \sum_{u\in I}(\widehat{\theta}_u-y_u)=\mathcal{F}(I,I^c). u ∈ I ∑ ( θ u − y u ) = F ( I , I c ) .
Defining θ ^ I = ∣ I ∣ − 1 ∑ u ∈ I θ ^ u \widehat{\theta}_I=|I|^{-1}\sum_{u\in I}\widehat{\theta}_u θ I = ∣ I ∣ − 1 ∑ u ∈ I θ u and dividing by ∣ I ∣ |I| ∣ I ∣ gives
θ ^ I = y ‾ I + F ( I , I c ) ∣ I ∣ . (37) \widehat{\theta}_I=\overline{y}_I+\frac{\mathcal{F}(I,I^c)}{|I|}. \tag*{(37)} θ I = y I + ∣ I ∣ F ( I , I c ) . (37)
The above set identity for all sets I I I also characterizes the optimal solution θ ^ \widehat{\theta} θ and is the set version of the optimality conditions (36) .
Step 3: The Upper Bound.
We will first prove the following minmax upper bound for a fixed vertex i ∈ V i\in V i ∈ V .
θ ^ i ( λ ) ≤ min J ⊆ V i ∈ J max I ⊆ J i ∈ I { y ‾ I − λ C I , J ∣ I ∣ } . (38) \widehat{\theta}^{(\lambda)}_i
\leq
\min_{\substack{J\subseteq V\\ i\in J}}
\max_{\substack{I\subseteq J\\ i\in I}}
\left\{
\overline{y}_I-\frac{\lambda C_{I,J}}{|I|}
\right\}. \tag*{(38)} θ i ( λ ) ≤ J ⊆ V i ∈ J min I ⊆ J i ∈ I max { y I − ∣ I ∣ λ C I , J } . (38)
Note that there is no restriction above for J , I J,I J , I to be connected sets.
Let J ⊆ V J\subseteq V J ⊆ V be any set containing i i i . Define
I = { u ∈ J : θ ^ u ≥ θ ^ i } . I=\{u\in J:\widehat{\theta}_u\geq\widehat{\theta}_i\}. I = { u ∈ J : θ u ≥ θ i } .
Clearly, i ∈ I i\in I i ∈ I .
Since θ ^ u ≥ θ ^ i \widehat{\theta}_u\geq\widehat{\theta}_i θ u ≥ θ i for every u ∈ I u\in I u ∈ I , we have by (37) ,
θ ^ i ≤ θ ^ I = y ‾ I + F ( I , I c ) ∣ I ∣ . \widehat{\theta}_i\leq\widehat{\theta}_I
=\overline{y}_I+\frac{\mathcal{F}(I,I^c)}{|I|}. θ i ≤ θ I = y I + ∣ I ∣ F ( I , I c ) .
In view of the preceding display, to upper bound θ ^ i \widehat{\theta}_i θ i it remains to upper bound F ( I , I c ) \mathcal{F}(I,I^c) F ( I , I c ) , which is the sum of the quantities s u v s_{uv} s uv over all edges from I I I to I c I^c I c . Since each s u v ≤ λ s_{uv}\leq\lambda s uv ≤ λ , a trivial upper bound would be obtained by replacing every such term by + λ +\lambda + λ . However, we can do better. The key observation is that, for certain boundary edges, the definition of s u v s_{uv} s uv forces s u v = − λ s_{uv}=-\lambda s uv = − λ . Using the value − λ -\lambda − λ on these edges gives an upper bound that is at least as sharp. Thus the main question is: for which edges { u , v } \{u,v\} { u , v } with u ∈ I u\in I u ∈ I and v ∈ I c v\in I^{c} v ∈ I c can we determine that s u v = − λ s_{uv}=-\lambda s uv = − λ ?
For edges with u ∈ I u\in I u ∈ I , v ∈ J ∖ I v\in J\setminus I v ∈ J ∖ I , and { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E , the definition of I I I gives
θ ^ u ≥ θ ^ i > θ ^ v . \widehat{\theta}_u\ge\widehat{\theta}_i>\widehat{\theta}_v. θ u ≥ θ i > θ v .
Hence
s u v = − λ , s_{uv}=-\lambda, s uv = − λ ,
and therefore
F ( I , J ∖ I ) = − λ ∣ E ( I , J ∖ I ) ∣ . \mathcal{F}(I,J\setminus I)=-\lambda|E(I,J\setminus I)|. F ( I , J ∖ I ) = − λ ∣ E ( I , J ∖ I ) ∣.
On the other hand, for edges { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E with u ∈ I u\in I u ∈ I and v ∈ J c v\in J^{c} v ∈ J c , we have no ordering information between θ ^ u \widehat{\theta}_u θ u and θ ^ v \widehat{\theta}_v θ v . We therefore use the trivial bound s u v ≤ λ s_{uv}\le\lambda s uv ≤ λ , which yields
F ( I , J c ) ≤ λ ∣ E ( I , J c ) ∣ . \mathcal{F}(I,J^{c})\le\lambda|E(I,J^{c})|. F ( I , J c ) ≤ λ ∣ E ( I , J c ) ∣.
Combining the two bounds gives
F ( I , I c ) = F ( I , J ∖ I ) + F ( I , J c ) ≤ − λ ∣ E ( I , J ∖ I ) ∣ + λ ∣ E ( I , J c ) ∣ = − λ C I , J . \begin{aligned}
\mathcal{F}(I,I^{c})&=\mathcal{F}(I,J\setminus I)+\mathcal{F}(I,J^{c})\\
&\le-\lambda|E(I,J\setminus I)|+\lambda|E(I,J^{c})|\\
&=-\lambda C_{I,J}.
\end{aligned} F ( I , I c ) = F ( I , J ∖ I ) + F ( I , J c ) ≤ − λ ∣ E ( I , J ∖ I ) ∣ + λ ∣ E ( I , J c ) ∣ = − λ C I , J .
It follows that
θ ^ i ≤ θ ^ I = y ˉ I + F ( I , I c ) ∣ I ∣ ≤ y ˉ I − λ C I , J ∣ I ∣ . \widehat{\theta}_i\le\widehat{\theta}_I=\bar{y}_I+\frac{\mathcal{F}(I,I^{c})}{|I|}\le\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}. θ i ≤ θ I = y ˉ I + ∣ I ∣ F ( I , I c ) ≤ y ˉ I − ∣ I ∣ λ C I , J .
Since the preceding argument holds for every set J ∋ i J\ni i J ∋ i , for each such J J J there exists a set I ⊆ J I\subseteq J I ⊆ J with i ∈ I i\in I i ∈ I for which
θ ^ i ≤ y ˉ I − λ C I , J ∣ I ∣ . \widehat{\theta}_i\le\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}. θ i ≤ y ˉ I − ∣ I ∣ λ C I , J .
Therefore,
θ ^ i ≤ max I ⊆ J i ∈ I { y ˉ I − λ C I , J ∣ I ∣ } \widehat{\theta}_i\le\max_{\substack{I\subseteq J\\i\in I}}\left\{\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\} θ i ≤ I ⊆ J i ∈ I max { y ˉ I − ∣ I ∣ λ C I , J }
for every J ∋ i J\ni i J ∋ i . Taking the minimum over all such J J J proves (38) .
Step 4: The Lower Bound. We will now prove a matching lower bound for a fixed vertex i ∈ V i\in V i ∈ V :
θ ^ i ( λ ) ≥ min J ⊇ i i ∈ J max I ⊆ J i ∈ I { y ˉ I − λ C I , J ∣ I ∣ } . (39) \widehat{\theta}_i^{(\lambda)}\ge\min_{\substack{J\supseteq i\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}\left\{\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. \tag*{(39)} θ i ( λ ) ≥ J ⊇ i i ∈ J min I ⊆ J i ∈ I max { y ˉ I − ∣ I ∣ λ C I , J } . (39)
Again, there is no restriction above for J , I J,I J , I to be connected sets. Define
J = { u ∈ V : θ ^ u ≤ θ ^ i } . J = \{u \in V : \widehat{\theta}_u \le\widehat{\theta}_i\}. J = { u ∈ V : θ u ≤ θ i } .
Clearly, i ∈ J i \in J i ∈ J .
Now let I ⊆ J I \subseteq J I ⊆ J be any set containing i i i . Since θ ^ u ≤ θ ^ i \widehat{\theta}_u \le\widehat{\theta}_i θ u ≤ θ i for every u ∈ I u \in I u ∈ I , we have by (37) ,
θ ^ i ≥ θ ^ I = y ‾ I + F ( I , I c ) ∣ I ∣ . \widehat{\theta}_i \ge\widehat{\theta}_I = \overline{y}_I + \frac{\mathcal{F}(I,I^c)}{|I|}. θ i ≥ θ I = y I + ∣ I ∣ F ( I , I c ) .
In view of the preceding display, to lower bound θ ^ i \widehat{\theta}_i θ i it remains to now lower bound F ( I , I c ) \mathcal{F}(I,I^c) F ( I , I c ) . Since each s u v ≥ − λ s_{uv} \ge-\lambda s uv ≥ − λ , a trivial lower bound would be obtained by replacing every such term by − λ -\lambda − λ .
The key observation again is that, for certain edges, the definition of s u v s_{uv} s uv forces s u v = + λ s_{uv}=+\lambda s uv = + λ . Using the value + λ +\lambda + λ on these edges gives a lower bound that is at least as sharp.
We observe that for edges with u ∈ I u \in I u ∈ I , v ∈ J c v \in J^c v ∈ J c , and { u , v } ∈ E \{u,v\} \in E { u , v } ∈ E , the definition of J J J gives
θ ^ u ≤ θ ^ i < θ ^ v . \widehat{\theta}_u \le\widehat{\theta}_i < \widehat{\theta}_v. θ u ≤ θ i < θ v .
Hence
s u v = + λ , s_{uv}=+\lambda, s uv = + λ ,
and therefore
F ( I , J c ) = λ ∣ E ( I , J c ) ∣ . \mathcal{F}(I,J^c)=\lambda|E(I,J^c)|. F ( I , J c ) = λ ∣ E ( I , J c ) ∣.
On the other hand, for edges { u , v } ∈ E \{u,v\} \in E { u , v } ∈ E with u ∈ I u \in I u ∈ I and v ∈ J ∖ I v \in J \setminus I v ∈ J ∖ I , we have no ordering information between θ ^ u \widehat{\theta}_u θ u and θ ^ v \widehat{\theta}_v θ v . We therefore use the trivial bound s u v ≥ − λ s_{uv} \ge-\lambda s uv ≥ − λ , which yields
F ( I , J ∖ I ) ≥ − λ ∣ E ( I , J ∖ I ) ∣ . \mathcal{F}(I,J\setminus I)\ge-\lambda|E(I,J\setminus I)|. F ( I , J ∖ I ) ≥ − λ ∣ E ( I , J ∖ I ) ∣.
Combining the two bounds gives
F ( I , I c ) = F ( I , J ∖ I ) + F ( I , J c ) ≥ − λ ∣ E ( I , J ∖ I ) ∣ + λ ∣ E ( I , J c ) ∣ = − λ C I , J . \begin{aligned}
\mathcal{F}(I,I^c) &= \mathcal{F}(I,J\setminus I)+\mathcal{F}(I,J^c) \\
&\ge-\lambda|E(I,J\setminus I)|+\lambda|E(I,J^c)| \\
&= -\lambda C_{I,J}.
\end{aligned} F ( I , I c ) = F ( I , J ∖ I ) + F ( I , J c ) ≥ − λ ∣ E ( I , J ∖ I ) ∣ + λ ∣ E ( I , J c ) ∣ = − λ C I , J .
It follows that
θ ^ i ≥ θ ^ I = y ‾ I + F ( I , I c ) ∣ I ∣ ≥ y ‾ I − λ C I , J ∣ I ∣ . \widehat{\theta}_i \ge\widehat{\theta}_I = \overline{y}_I+\frac{\mathcal{F}(I,I^c)}{|I|} \ge\overline{y}_I-\frac{\lambda C_{I,J}}{|I|}. θ i ≥ θ I = y I + ∣ I ∣ F ( I , I c ) ≥ y I − ∣ I ∣ λ C I , J .
Since the preceding argument holds for every set I ⊆ J I \subseteq J I ⊆ J with i ∈ I i \in I i ∈ I , we obtain
θ ^ i ≥ max I ⊆ J i ∈ I { y ‾ I − λ C I , J ∣ I ∣ } . \widehat{\theta}_i \ge\max_{\substack{I\subseteq J\\ i\in I}}\left\{\overline{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. θ i ≥ I ⊆ J i ∈ I max { y I − ∣ I ∣ λ C I , J } .
Since the particular set J = { u ∈ V : θ ^ u ≤ θ ^ i } J=\{u\in V:\widehat{\theta}_u\le\widehat{\theta}_i\} J = { u ∈ V : θ u ≤ θ i } is feasible in the sense that it contains i i i , it follows that
θ ^ i ≥ min J ⊆ V i ∈ J max I ⊆ J i ∈ I { y ‾ I − λ C I , J ∣ I ∣ } . \widehat{\theta}_i \ge\min_{\substack{J\subseteq V\\ i\in J}}\max_{\substack{I\subseteq J\\ i\in I}}\left\{\overline{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. θ i ≥ J ⊆ V i ∈ J min I ⊆ J i ∈ I max { y I − ∣ I ∣ λ C I , J } .
Step 5: The Connected Set Restriction.
The previous two steps have shown that the same quantity is both an upper and a lower bound for the fitted value θ ^ i \hat{\theta}_i θ ^ i . Therefore, we have established
θ ^ i ( λ ) = min J ⊆ V i ∈ J max I ⊆ J i ∈ I { y ˉ I − λ C I , J ∣ I ∣ } . (40) \hat{\theta}_i^{(\lambda)}=\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}\left\{\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. \tag*{(40)} θ ^ i ( λ ) = J ⊆ V i ∈ J min I ⊆ J i ∈ I max { y ˉ I − ∣ I ∣ λ C I , J } . (40)
This is a minmax representation over arbitrary subsets I ⊆ J I\subseteq J I ⊆ J containing i i i . However, it turns out that both I I I and J J J can be restricted to connected sets.
We first revisit the upper-bound argument in Step 3. Let J ∋ i J\ni i J ∋ i be any connected set and define
I ~ = J ∩ { u ∈ V : θ ^ u ≥ θ ^ i } . \widetilde{I}=J\cap\{u\in V:\hat{\theta}_u\geq\hat{\theta}_i\}. I = J ∩ { u ∈ V : θ ^ u ≥ θ ^ i } .
Now consider the subgraph induced by I ~ \widetilde{I} I , and let I I I be the (uniquely defined) connected component of this subgraph containing i i i . Then I I I is connected, i ∈ I i\in I i ∈ I , and I ⊆ J I\subseteq J I ⊆ J .
We claim that for every edge { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E with u ∈ I u\in I u ∈ I and v ∈ J ∖ I v\in J\setminus I v ∈ J ∖ I , we have
θ ^ u ≥ θ ^ i > θ ^ v . \hat{\theta}_u\geq\hat{\theta}_i>\hat{\theta}_v. θ ^ u ≥ θ ^ i > θ ^ v .
Indeed, if v ∈ I ~ v\in\widetilde{I} v ∈ I , then the edge { u , v } \{u,v\} { u , v } would imply that v v v belongs to the same connected component of the subgraph induced by I ~ \widetilde{I} I as u u u , and hence v ∈ I v\in I v ∈ I , a contradiction. Therefore v ∉ I ~ v\notin\widetilde{I} v ∈ / I , and so
θ ^ v < θ ^ i . \hat{\theta}_v<\hat{\theta}_i. θ ^ v < θ ^ i .
Thus
s u v = − λ s_{uv}=-\lambda s uv = − λ
for every edge from I I I to J ∖ I J\setminus I J ∖ I , and the remainder of the upper-bound argument proceeds exactly as before. Consequently,
θ ^ i ≤ min J ⊆ V i ∈ J max I ⊆ J i ∈ I { y ˉ I − λ C I , J ∣ I ∣ } . \hat{\theta}_i\leq\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}\left\{\bar{y}_I-\frac{\lambda C_{I,J}}{|I|}\right\}. θ ^ i ≤ J ⊆ V i ∈ J min I ⊆ J i ∈ I max { y ˉ I − ∣ I ∣ λ C I , J } .
For the reverse inequality, start as in the lower bound argument in Step 4 with
J ~ = { u ∈ V : θ ^ u ≤ θ ^ i } , \widetilde{J}=\{u\in V:\hat{\theta}_u\leq\hat{\theta}_i\}, J = { u ∈ V : θ ^ u ≤ θ ^ i } ,
and let J J J be the connected component of the subgraph induced by J ~ \widetilde{J} J containing i i i . In particular, J J J is connected and i ∈ J i\in J i ∈ J .
Now let I ⊆ J I\subseteq J I ⊆ J be any connected set containing i i i . Consider an edge { u , v } ∈ E \{u,v\}\in E { u , v } ∈ E with u ∈ I u\in I u ∈ I and v ∈ J c v\in J^c v ∈ J c . We must have v ∉ J ~ v\notin\widetilde{J} v ∈ / J . Indeed, if v ∈ J ~ v\in\widetilde{J} v ∈ J , then the edge { u , v } \{u,v\} { u , v } would connect v v v to the connected component J J J of J ~ \widetilde{J} J , implying v ∈ J v\in J v ∈ J , a contradiction. Hence
θ ^ v > θ ^ i ≥ θ ^ u , \hat{\theta}_v>\hat{\theta}_i\geq\hat{\theta}_u, θ ^ v > θ ^ i ≥ θ ^ u ,
and therefore
s u v = + λ . (41) s_{uv}=+\lambda. \tag*{(41)} s uv = + λ . (41)
The remainder of the lower-bound argument proceeds exactly as before and yields
θ ^ i ≥ y ‾ I − λ C I , J ∣ I ∣ \widehat{\theta}_i \ge\overline{y}_I - \frac{\lambda C_{I,J}}{|I|} θ i ≥ y I − ∣ I ∣ λ C I , J
for every connected I ⊆ J I \subseteq J I ⊆ J containing i i i . Therefore,
θ ^ i ≥ min J ∈ C i ∈ J max I ⊆ J , i ∈ I I ∈ C { y ‾ I − λ C I , J ∣ I ∣ } . \widehat{\theta}_i \ge\min_{\substack{J \in\mathcal{C}\\ i \in J}} \max_{\substack{I \subseteq J,\ i \in I\\ I \in\mathcal{C}}} \left\{ \overline{y}_I - \frac{\lambda C_{I,J}}{|I|} \right\}. θ i ≥ J ∈ C i ∈ J min I ⊆ J , i ∈ I I ∈ C max { y I − ∣ I ∣ λ C I , J } .
Combining the two inequalities proves
θ ^ i ( λ ) = min J ∈ C i ∈ J max I ⊆ J , i ∈ I I ∈ C { y ‾ I − λ C I , J ∣ I ∣ } . \widehat{\theta}_i^{(\lambda)} = \min_{\substack{J \in\mathcal{C}\\ i \in J}} \max_{\substack{I \subseteq J,\ i \in I\\ I \in\mathcal{C}}} \left\{ \overline{y}_I - \frac{\lambda C_{I,J}}{|I|} \right\}. θ i ( λ ) = J ∈ C i ∈ J min I ⊆ J , i ∈ I I ∈ C max { y I − ∣ I ∣ λ C I , J } .
Step 6: The Maxmin Identity. The objective in (3) is invariant under the transformation ( y , θ ) ↦ ( − y , − θ ) (y,\theta) \mapsto(-y,-\theta) ( y , θ ) ↦ ( − y , − θ ) . Since the minimizer is unique, it follows that θ ^ ( λ ) ( − y ) = − θ ^ ( λ ) ( y ) \widehat{\theta}^{(\lambda)}(-y)=-\widehat{\theta}^{(\lambda)}(y) θ ( λ ) ( − y ) = − θ ( λ ) ( y ) . Applying the arbitrary-set and connected-set minmax identities just proved to the data vector − y -y − y and then negating both sides exchanges the minimum and maximum, yielding the maxmin representation. □
Proof of Proposition 1.2
The goal in this section is to illustrate how the classical isotonic regression minmax representations fall out from our TVD minmax representation. To this end, we prove Lemma 1.3, Corollary 1.4, and Lemma 1.5 in order. The only nontrivial part here is Lemma 1.5.
Proof of Lemma 1.3. By (13) , the asymmetric TVD objective equals
1 2 ∑ u ∈ V ( y u − θ u ) 2 + a TV G ~ ( θ ) − b ∑ u ∈ V d u θ u = 1 2 ∑ u ∈ V ( y u + b d u − θ u ) 2 + a TV G ~ ( θ ) + c , \frac{1}{2}\sum_{u\in V}(y_u-\theta_u)^2+a\operatorname{TV}_{\widetilde{G}}(\theta)-b\sum_{u\in V}d_u\theta_u
=
\frac{1}{2}\sum_{u\in V}(y_u+bd_u-\theta_u)^2+a\operatorname{TV}_{\widetilde{G}}(\theta)+c, 2 1 u ∈ V ∑ ( y u − θ u ) 2 + a TV G ( θ ) − b u ∈ V ∑ d u θ u = 2 1 u ∈ V ∑ ( y u + b d u − θ u ) 2 + a TV G ( θ ) + c ,
where c = − ∑ u ∈ V ( b d u y u + b 2 d u 2 / 2 ) c=-\sum_{u\in V}(bd_uy_u+b^2d_u^2/2) c = − ∑ u ∈ V ( b d u y u + b 2 d u 2 /2 ) is independent of θ \theta θ . Thus the two objectives have the same unique minimizer, proving the lemma. □
Proof of Corollary 1.4. Set λ + = 0 \lambda_+=0 λ + = 0 and λ − = λ \lambda_-=\lambda λ − = λ in Lemma 1.3. Then a = λ / 2 a=\lambda/2 a = λ /2 , b = − λ / 2 b=-\lambda/2 b = − λ /2 , and y ~ = y − λ d / 2 \widetilde{y}=y-\lambda d/2 y = y − λ d /2 , giving (16) . □
Proof of Lemma 1.5. Write θ ^ [ λ ] = NearIso ( y , D , λ ) \widehat{\theta}^{[\lambda]}=\operatorname{NearIso}(y,D,\lambda) θ [ λ ] = NearIso ( y , D , λ ) and let
y min = min u ∈ V y u , y max = max u ∈ V y u . y_{\min}=\min_{u\in V}y_u,\qquad y_{\max}=\max_{u\in V}y_u. y m i n = u ∈ V min y u , y m a x = u ∈ V max y u .
Fix λ > λ 0 = n ( y max − y min ) \lambda>\lambda_0=n(y_{\max}-y_{\min}) λ > λ 0 = n ( y m a x − y m i n ) and i ∈ V i\in V i ∈ V . For disjoint sets S , T ⊆ V S, T \subseteq V S , T ⊆ V , let A ( S , T ) A(S,T) A ( S , T ) denote the directed edges from S S S to T T T . Internal edges cancel when we sum the (out minus in) degrees over I I I , so
∑ u ∈ I d u = ∣ A ( I , I c ) ∣ − ∣ A ( I c , I ) ∣ . \sum_{u\in I} d_u = |A(I,I^c)| - |A(I^c,I)|. u ∈ I ∑ d u = ∣ A ( I , I c ) ∣ − ∣ A ( I c , I ) ∣.
Combining this with the definition of C I , J C_{I,J} C I , J on the underlying undirected graph gives
C I , J + ∑ u ∈ I d u = 2 { ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } . (42) C_{I,J}+\sum_{u\in I}d_u
=2\{|A(I,J\setminus I)|-|A(J^c,I)|\}. \tag*{(42)} C I , J + u ∈ I ∑ d u = 2 { ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } . (42)
Indeed, edges from I I I to J ∖ I J\setminus I J ∖ I contribute 2, edges from J c J^c J c to I I I contribute − 2 -2 − 2 , and the other boundary edges contribute zero.
Apply the arbitrary-set TVD formula (40) to the shifted observations y − λ d / 2 y-\lambda d/2 y − λ d /2 with tuning parameter λ / 2 \lambda/2 λ /2 . Corollary 1.4 and (42) yield
θ ^ i [ λ ] = min J ⊆ V i ∈ J max I ⊆ J i ∈ I { y ‾ I − λ ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ ∣ I ∣ } . (43) \widehat{\theta}^{[\lambda]}_i
=\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}
\left\{
\overline{y}_I-\lambda\frac{|A(I,J\setminus I)|-|A(J^c,I)|}{|I|}
\right\}. \tag*{(43)} θ i [ λ ] = J ⊆ V i ∈ J min I ⊆ J i ∈ I max { y I − λ ∣ I ∣ ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } . (43)
We now simplify this expression using y min ≤ y ‾ I ≤ y max y_{\min}\leq\overline{y}_I\leq y_{\max} y m i n ≤ y I ≤ y m a x for every nonempty I I I .
Step 1: Restricting the outer minimum to lower sets. If J ∋ i J\ni i J ∋ i is not lower, then ∣ A ( J c , J ) ∣ ≥ 1 |A(J^c,J)|\geq1 ∣ A ( J c , J ) ∣ ≥ 1 . The inner choice I = J I=J I = J gives
y ‾ J + λ ∣ A ( J c , J ) ∣ ∣ J ∣ ≥ y min + λ n > y max . \overline{y}_J+\lambda\frac{|A(J^c,J)|}{|J|}
\geq y_{\min}+\frac{\lambda}{n}>y_{\max}. y J + λ ∣ J ∣ ∣ A ( J c , J ) ∣ ≥ y m i n + n λ > y m a x .
In contrast, for J = V J=V J = V , every term in the inner maximum is at most y ‾ I ≤ y max \overline{y}_I\leq y_{\max} y I ≤ y m a x . Thus no non-lower set can attain the outer minimum.
We may therefore restrict J J J to L ∈ L i L\in\mathcal{L}_i L ∈ L i . Since no edge enters L L L from outside, A ( L c , I ) = ∅ A(L^c,I)=\varnothing A ( L c , I ) = ∅ for every I ⊆ L I\subseteq L I ⊆ L , and hence
θ ^ i [ λ ] = min L ∈ L i max I ⊆ L i ∈ I { y ‾ I − λ ∣ A ( I , L ∖ I ) ∣ ∣ I ∣ } . (44) \widehat{\theta}^{[\lambda]}_i
=\min_{L\in\mathcal{L}_i}\max_{\substack{I\subseteq L\\i\in I}}
\left\{\overline{y}_I-\lambda\frac{|A(I,L\setminus I)|}{|I|}\right\}. \tag*{(44)} θ i [ λ ] = L ∈ L i min I ⊆ L i ∈ I max { y I − λ ∣ I ∣ ∣ A ( I , L ∖ I ) ∣ } . (44)
Step 2: Expressing the inner maximum using upper sets. Fix L ∈ L i L\in\mathcal{L}_i L ∈ L i . If A ( I , L ∖ I ) ≠ ∅ A(I,L\setminus I)\neq\varnothing A ( I , L ∖ I ) = ∅ , then
y ‾ I − λ ∣ A ( I , L ∖ I ) ∣ ∣ I ∣ ≤ y max − λ n < y min . \overline{y}_I-\lambda\frac{|A(I,L\setminus I)|}{|I|}
\leq y_{\max}-\frac{\lambda}{n}<y_{\min}. y I − λ ∣ I ∣ ∣ A ( I , L ∖ I ) ∣ ≤ y m a x − n λ < y m i n .
Such an I I I cannot attain the inner maximum, since I = L I=L I = L gives y ‾ L ≥ y min \overline{y}_L\geq y_{\min} y L ≥ y m i n . Only sets with A ( I , L ∖ I ) = ∅ A(I,L\setminus I)=\varnothing A ( I , L ∖ I ) = ∅ remain, and their correction vanishes. We claim that these sets are precisely I = L ∩ U I = L \cap U I = L ∩ U , with U ∈ U i U \in\mathcal{U}_i U ∈ U i . Indeed, no edge can go from L ∩ U L \cap U L ∩ U to L ∖ U L \setminus U L ∖ U , since it would leave the upper set U U U . Conversely, if i ∈ I ⊆ L i \in I \subseteq L i ∈ I ⊆ L and A ( I , L ∖ I ) = ∅ A(I, L \setminus I) = \varnothing A ( I , L ∖ I ) = ∅ , set U = I ∪ L c U = I \cup L^c U = I ∪ L c . Then L ∩ U = I L \cap U = I L ∩ U = I . An edge from U U U to U c = L ∖ I U^c = L \setminus I U c = L ∖ I could start neither in I I I , by assumption, nor in L c L^c L c , since L L L is lower. Thus U U U is upper and contains i i i .
Substituting this characterization into (44) gives
θ ^ i [ λ ] = min L ∈ L i max U ∈ U i y ‾ L ∩ U , λ > λ 0 . (45) \widehat{\theta}^{[\lambda]}_i = \min_{L \in\mathcal{L}_i} \max_{U \in\mathcal{U}_i} \overline{y}_{L \cap U}, \qquad\lambda> \lambda_0. \tag*{(45)} θ i [ λ ] = L ∈ L i min U ∈ U i max y L ∩ U , λ > λ 0 . (45)
Step 3: The maxmin identity.
Let D r e v D^{\mathrm{rev}} D rev be obtained by reversing every edge of D D D . The transformation ( y , θ , D ) ↦ ( − y , − θ , D r e v ) (y, \theta, D) \mapsto(-y, -\theta, D^{\mathrm{rev}}) ( y , θ , D ) ↦ ( − y , − θ , D rev ) preserves the nearly isotonic objective. By uniqueness,
NearIso ( − y , D r e v , λ ) = − NearIso ( y , D , λ ) . \operatorname{NearIso}(-y, D^{\mathrm{rev}}, \lambda) = -\operatorname{NearIso}(y, D, \lambda). NearIso ( − y , D rev , λ ) = − NearIso ( y , D , λ ) .
Reversal interchanges lower and upper sets, while negation leaves the data range unchanged. Applying (45) to − y -y − y on D r e v D^{\mathrm{rev}} D rev and negating both sides therefore gives
θ ^ i [ λ ] = max U ∈ U i min L ∈ L i y ‾ L ∩ U . \widehat{\theta}^{[\lambda]}_i = \max_{U \in\mathcal{U}_i} \min_{L \in\mathcal{L}_i} \overline{y}_{L \cap U}. θ i [ λ ] = U ∈ U i max L ∈ L i min y L ∩ U .
Step 4: Exact agreement with isotonic regression.
The right-hand side of (45) does not depend on λ \lambda λ . Thus there is a fixed vector m m m such that θ ^ [ λ ] = m \widehat{\theta}^{[\lambda]} = m θ [ λ ] = m for every λ > λ 0 \lambda> \lambda_0 λ > λ 0 . Write
f ( θ ) = 1 2 ∑ u ∈ V ( y u − θ u ) 2 , f(\theta) = \frac{1}{2}\sum_{u \in V}(y_u-\theta_u)^2, f ( θ ) = 2 1 u ∈ V ∑ ( y u − θ u ) 2 ,
P ( θ ) = ∑ ( u , v ) ∈ A ( θ v − θ u ) − . P(\theta) = \sum_{(u,v)\in A}(\theta_v-\theta_u)_-. P ( θ ) = ( u , v ) ∈ A ∑ ( θ v − θ u ) − .
Since m m m minimizes f + λ P f+\lambda P f + λ P for every such λ \lambda λ , comparison with the zero vector gives
f ( m ) + λ P ( m ) ≤ f ( 0 ) , λ > λ 0 . f(m) + \lambda P(m) \leq f(0), \qquad\lambda> \lambda_0. f ( m ) + λ P ( m ) ≤ f ( 0 ) , λ > λ 0 .
Letting λ → ∞ \lambda\to\infty λ → ∞ shows that P ( m ) = 0 P(m) = 0 P ( m ) = 0 , so m m m is isotonic. For any isotonic vector θ \theta θ , we also have P ( θ ) = 0 P(\theta) = 0 P ( θ ) = 0 , and optimality gives f ( m ) ≤ f ( θ ) f(m) \leq f(\theta) f ( m ) ≤ f ( θ ) . Hence m m m is the unique isotonic least-squares estimator. This proves the lemma and, together with Steps 2 and 3, recovers the classical representation (10) .
Combining Lemma 1.5 with Corollary 1.4 proves Proposition 1.2 .
Proofs for general convex losses
We prove Theorem 1.6 , Proposition 1.7, and Theorem 1.8 in order.
Proof of Theorem 1.6
Write F = F λ F=F_{\lambda} F = F λ and S = S λ \mathcal{S}=\mathcal{S}_{\lambda} S = S λ . We use the scalar endpoints r + r_{+} r + from (23) . Let us first state the following elementary facts about convex maps that will be very useful in our proofs.
Lemma 4.1 (Scalar facts for finite convex functions). Let h : R → R h:\mathbb{R}\to\mathbb{R} h : R → R be a finite convex function and let t ∈ R t\in\mathbb{R} t ∈ R .
If h − ′ ( t ) ≤ 0 h'_{-}(t)\le0 h − ′ ( t ) ≤ 0 , then t ≤ r + ( h ) t\le r_{+}(h) t ≤ r + ( h ) .
If r + ( h ) > t r_{+}(h)>t r + ( h ) > t , then h ( t + ε ) ≤ h ( t ) h(t+\varepsilon)\le h(t) h ( t + ε ) ≤ h ( t ) for all sufficiently small ε > 0 \varepsilon>0 ε > 0 .
For each ε > 0 \varepsilon>0 ε > 0 , the function x ↦ h ( x + ε ) − h ( x ) x\mapsto h(x+\varepsilon)-h(x) x ↦ h ( x + ε ) − h ( x ) is nondecreasing.
If h + ′ ( t ) < 0 h'_{+}(t)<0 h + ′ ( t ) < 0 , then r + ( h ) > t r_{+}(h)>t r + ( h ) > t .
If h − ′ ( t ) > 0 h'_{-}(t)>0 h − ′ ( t ) > 0 , then r + ( h ) < t r_{+}(h)<t r + ( h ) < t .
If h ~ ( x ) = h ( − x ) \widetilde{h}(x)=h(-x) h ( x ) = h ( − x ) for x ∈ R x\in\mathbb{R} x ∈ R , then r + ( h ~ ) = − r − ( h ) r_{+}(\widetilde{h})=-r_{-}(h) r + ( h ) = − r − ( h ) .
All relations involving r + ( h ) r_{+}(h) r + ( h ) and r − ( h ) r_{-}(h) r − ( h ) hold in the extended real line: r + ( h ) = + ∞ r_{+}(h)=+\infty r + ( h ) = + ∞ is allowed in the first, second, and fourth assertions, and r + ( h ) = − ∞ r_{+}(h)=-\infty r + ( h ) = − ∞ in the fifth.
The proof of Lemma 4.1 is given in § 6 . Let us now get into the proof of Theorem 1.6. For the ease of presentation, for any nonempty I ⊆ J I\subseteq J I ⊆ J , let us define
Φ I , J ( t ) : = ∑ u ∈ I ℓ u ( t ) + λ C I , J t . (46) \Phi_{I,J}(t):=\sum_{u\in I}\ell_u(t)+\lambda C_{I,J}t. \tag*{(46)} Φ I , J ( t ) := u ∈ I ∑ ℓ u ( t ) + λ C I , J t . (46)
and let
Φ − I , J ( t ) : = ∑ u ∈ I ℓ u ( t ) − λ C I , J t . (47) \Phi_{-I,J}(t):=\sum_{u\in I}\ell_u(t)-\lambda C_{I,J}t. \tag*{(47)} Φ − I , J ( t ) := u ∈ I ∑ ℓ u ( t ) − λ C I , J t . (47)
Thus, q I , J + = r + ( Φ I , J ) q^{+}_{I,J}=r_{+}(\Phi_{I,J}) q I , J + = r + ( Φ I , J ) and q I , J − = r − ( Φ − I , J ) q^{-}_{I,J}=r_{-}(\Phi_{-I,J}) q I , J − = r − ( Φ − I , J ) .
We first prove the interval assertion, then identify its endpoints. We next show that the endpoint vectors are themselves solutions, and finally establish uniqueness under strict convexity.
Step 1: Coordinate Intervals. Each finite convex loss ℓ u \ell_u ℓ u is continuous on R \mathbb{R} R , so F F F is continuous on R V \mathbb{R}^{V} R V . Coercivity of F F F therefore makes the nonempty sublevel set
K = { θ ∈ R V : F ( θ ) ≤ F ( 0 ) } K=\{\theta\in\mathbb{R}^{V}:F(\theta)\le F(0)\} K = { θ ∈ R V : F ( θ ) ≤ F ( 0 )}
compact. The minimum of F F F on K K K is attained and is also its global minimum. Hence, S \mathcal{S} S is nonempty and compact. Being the set of minimizers of a convex map, S \mathcal{S} S is convex.
For each i ∈ V i\in V i ∈ V , the coordinate projection of S \mathcal{S} S is consequently a nonempty compact convex subset of R \mathbb{R} R , and thus a closed bounded interval. Define
θ ^ i = min θ ∈ S θ i , θ ‾ i = max θ ∈ S θ i . \widehat{\theta}_i=\min_{\theta\in\mathcal{S}}\theta_i,\qquad\overline{\theta}_i=\max_{\theta\in\mathcal{S}}\theta_i. θ i = θ ∈ S min θ i , θ i = θ ∈ S max θ i .
This proves (26) and part (i). Next, we characterize these endpoints in terms of min–max and max–min formulae.
Step 2: Optimality Conditions. By the KKT conditions, a vector θ ^ \hat{\theta} θ ^ minimizes F F F if and only if there exist subgradients
g u ∈ ∂ ℓ u ( θ ^ u ) g_u \in\partial\ell_u(\hat{\theta}_u) g u ∈ ∂ ℓ u ( θ ^ u )
and edge variables s u v = − s v u s_{uv}=-s_{vu} s uv = − s v u such that
g u = ∑ v : { u , v } ∈ E s u v , s u v ∈ { { λ } , θ ^ v > θ ^ u , [ − λ , λ ] , θ ^ v = θ ^ u , { − λ } , θ ^ v < θ ^ u . (48) g_u = \sum_{v:\{u,v\}\in E} s_{uv}, \qquad
s_{uv} \in
\begin{cases}
\{\lambda\}, & \hat{\theta}_v > \hat{\theta}_u,\\
[-\lambda,\lambda], & \hat{\theta}_v = \hat{\theta}_u,\\
\{-\lambda\}, & \hat{\theta}_v < \hat{\theta}_u.
\end{cases} \tag*{(48)} g u = v : { u , v } ∈ E ∑ s uv , s uv ∈ ⎩ ⎨ ⎧ { λ } , [ − λ , λ ] , { − λ } , θ ^ v > θ ^ u , θ ^ v = θ ^ u , θ ^ v < θ ^ u . (48)
Note that the dual variables s u v s_{uv} s uv have the exact same definition as the duals in the squared loss case as they solely depend on the TV penalty. The difference from the squared loss case is that the sub-differential ∂ ℓ u ( θ ^ u ) \partial\ell_u(\hat{\theta}_u) ∂ ℓ u ( θ ^ u ) might not be singleton. Indeed, since the losses are convex and continuous, the following interval characterization for the subgradient of ℓ u \ell_u ℓ u holds (see proof of Theorem 24.1 of Rockafellar [20 ] ):
∂ ℓ u ( θ ^ u ) = [ ℓ u , − ′ ( θ ^ u ) , ℓ u , + ′ ( θ ^ u ) ] . (49) \partial\ell_u(\hat{\theta}_u) = [\ell'_{u,-}(\hat{\theta}_u),\ell'_{u,+}(\hat{\theta}_u)]. \tag*{(49)} ∂ ℓ u ( θ ^ u ) = [ ℓ u , − ′ ( θ ^ u ) , ℓ u , + ′ ( θ ^ u )] . (49)
For the squared loss case, both left and right derivative coincide and hence the sub-differential becomes a singleton.
For any nonempty I ⊆ V I \subseteq V I ⊆ V , summing these conditions over u ∈ I u \in I u ∈ I gives
∑ u ∈ I g u = ∑ u ∈ I ∑ v : { u , v } ∈ E s u v = ∑ u ∈ I ∑ v ∈ I { u , v } ∈ E s u v + ∑ u ∈ I ∑ v ∈ I c { u , v } ∈ E s u v = ∑ u ∈ I ∑ v ∈ I c { u , v } ∈ E s u v . \begin{aligned}
\sum_{u\in I} g_u
&= \sum_{u\in I}\sum_{v:\{u,v\}\in E} s_{uv}\\
&= \sum_{u\in I}\sum_{\substack{v\in I\\\{u,v\}\in E}}s_{uv}
+ \sum_{u\in I}\sum_{\substack{v\in I^c\\\{u,v\}\in E}}s_{uv}\\
&= \sum_{u\in I}\sum_{\substack{v\in I^c\\\{u,v\}\in E}}s_{uv}.
\end{aligned} u ∈ I ∑ g u = u ∈ I ∑ v : { u , v } ∈ E ∑ s uv = u ∈ I ∑ v ∈ I { u , v } ∈ E ∑ s uv + u ∈ I ∑ v ∈ I c { u , v } ∈ E ∑ s uv = u ∈ I ∑ v ∈ I c { u , v } ∈ E ∑ s uv .
The internal edges cancel because s u v = − s v u s_{uv}=-s_{vu} s uv = − s v u . Thus, with the boundary-flow notation from § 2 ,
∑ u ∈ I g u = F ( I , I c ) . (50) \sum_{u\in I}g_u = \mathcal{F}(I,I^c). \tag*{(50)} u ∈ I ∑ g u = F ( I , I c ) . (50)
Step 3: The Upper Bound. Let θ ^ \hat{\theta} θ ^ be any solution and fix i ∈ V i\in V i ∈ V . For any J ⊆ V J\subseteq V J ⊆ V containing i i i , take
I = J ∩ { u ∈ V : θ ^ u ≥ θ ^ i } . I = J \cap\{u\in V:\hat{\theta}_u\geq\hat{\theta}_i\}. I = J ∩ { u ∈ V : θ ^ u ≥ θ ^ i } .
For every u ∈ I u\in I u ∈ I , it follows from the interval characterization of subdifferential in (49) and the monotonicity of the left derivative of a finite convex function that
g u ≥ ℓ u , − ′ ( θ ^ u ) ≥ ℓ u , − ′ ( θ ^ i ) , g_u \geq\ell'_{u,-}(\hat{\theta}_u)\geq\ell'_{u,-}(\hat{\theta}_i), g u ≥ ℓ u , − ′ ( θ ^ u ) ≥ ℓ u , − ′ ( θ ^ i ) ,
Consequently,
∑ u ∈ I ℓ u , − ′ ( θ ^ i ) ≤ ∑ u ∈ I g u = F ( I , I c ) . \sum_{u\in I}\ell'_{u,-}(\hat{\theta}_i) \le\sum_{u\in I}g_u = \mathcal{F}(I,I^c). u ∈ I ∑ ℓ u , − ′ ( θ ^ i ) ≤ u ∈ I ∑ g u = F ( I , I c ) .
As in the squared-loss proof, every edge from I I I to J ∖ I J \setminus I J ∖ I leads to a strictly smaller fitted value by definition of I I I . Thus, its edge variable is − λ -\lambda − λ . On edges from I I I to J c J^c J c , we use the trivial bound s u v ≤ λ s_{uv} \le\lambda s uv ≤ λ . Therefore, it follows that
F ( I , I c ) ≤ − λ ∣ E ( I , J ∖ I ) ∣ + λ ∣ E ( I , J c ) ∣ = − λ C I , J . \mathcal{F}(I,I^c) \le-\lambda|E(I,J\setminus I)|+\lambda|E(I,J^c)|=-\lambda C_{I,J}. F ( I , I c ) ≤ − λ ∣ E ( I , J ∖ I ) ∣ + λ ∣ E ( I , J c ) ∣ = − λ C I , J .
Therefore,
∑ u ∈ I ℓ u , − ′ ( θ ^ i ) + λ C I , J ≤ 0 , \sum_{u\in I}\ell'_{u,-}(\hat{\theta}_i)+\lambda C_{I,J}\le0, u ∈ I ∑ ℓ u , − ′ ( θ ^ i ) + λ C I , J ≤ 0 ,
or equivalently,
Φ I , J , − ′ ( θ ^ i ) ≤ 0. \Phi'_{I,J,-}(\hat{\theta}_i)\le0. Φ I , J , − ′ ( θ ^ i ) ≤ 0.
By the definition of r + r_+ r + ,
θ ^ i ≤ r + ( Φ I , J ) ≤ max i ∈ I r + ( Φ I , J ) . \hat{\theta}_i\le r_+(\Phi_{I,J})\le\max_{i\in I}r_+(\Phi_{I,J}). θ ^ i ≤ r + ( Φ I , J ) ≤ i ∈ I max r + ( Φ I , J ) .
For every outer set J ∋ i J\ni i J ∋ i , we have found an inner set I ⊆ J I\subseteq J I ⊆ J containing i i i such that the above inequality holds. Hence, taking minimum over the outer set J J J , we obtain
θ ^ i ≤ min J ⊆ V i ∈ J max I ⊆ J i ∈ I r + ( Φ I , J ) . (51) \hat{\theta}_i\le\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}r_+(\Phi_{I,J}). \tag*{(51)} θ ^ i ≤ J ⊆ V i ∈ J min I ⊆ J i ∈ I max r + ( Φ I , J ) . (51)
Step 4: A Matching Bound for the Upper Endpoint
The preceding upper bound applies to every solution. To obtain a matching bound for the upper endpoint, we now use its maximality through a one-sided perturbation.
By compactness, choose a solution θ ^ ∈ S \hat{\theta}\in\mathcal{S} θ ^ ∈ S such that θ ^ i = θ ˉ i \hat{\theta}_i=\bar{\theta}_i θ ^ i = θ ˉ i , and define
J = { u ∈ V : θ ^ u ≤ θ ^ i } . J=\{u\in V:\hat{\theta}_u\le\hat{\theta}_i\}. J = { u ∈ V : θ ^ u ≤ θ ^ i } .
Take any I ⊆ J I\subseteq J I ⊆ J containing i i i . We will show that
θ ^ i ≥ r + ( Φ I , J ) . \hat{\theta}_i\ge r_+(\Phi_{I,J}). θ ^ i ≥ r + ( Φ I , J ) .
For ε > 0 \varepsilon>0 ε > 0 , define the local perturbation
θ ~ u = { θ ^ u + ε , u ∈ I , θ ^ u , u ∉ I . \widetilde{\theta}_u=
\begin{cases}
\hat{\theta}_u+\varepsilon, & u\in I,\\
\hat{\theta}_u, & u\notin I.
\end{cases} θ u = { θ ^ u + ε , θ ^ u , u ∈ I , u ∈ / I .
Since θ ~ i = θ ˉ i + ε > θ ˉ i \widetilde{\theta}_i=\bar{\theta}_i+\varepsilon>\bar{\theta}_i θ i = θ ˉ i + ε > θ ˉ i , by definition of θ ˉ i \bar{\theta}_i θ ˉ i the perturbed vector cannot belong to S \mathcal{S} S . Therefore, the perturbed vector should produce strictly larger objective, i.e.,
0 < F ( θ ~ ) − F ( θ ^ ) . (52) 0<\mathcal{F}(\widetilde{\theta})-\mathcal{F}(\hat{\theta}). \tag*{(52)} 0 < F ( θ ) − F ( θ ^ ) . (52)
We now bound this change in the objective from above. For the loss term,
∑ u ∈ V { ℓ u ( θ ~ u ) − ℓ u ( θ ^ u ) } = ∑ u ∈ I { ℓ u ( θ ^ u + ε ) − ℓ u ( θ ^ u ) } ≤ ∑ u ∈ I { ℓ u ( θ ^ i + ε ) − ℓ u ( θ ^ i ) } . \sum_{u\in V}\{\ell_u(\widetilde{\theta}_u)-\ell_u(\widehat{\theta}_u)\}
= \sum_{u\in I}\{\ell_u(\widehat{\theta}_u+\varepsilon)-\ell_u(\widehat{\theta}_u)\}
\le\sum_{u\in I}\{\ell_u(\widehat{\theta}_i+\varepsilon)-\ell_u(\widehat{\theta}_i)\}. u ∈ V ∑ { ℓ u ( θ u ) − ℓ u ( θ u )} = u ∈ I ∑ { ℓ u ( θ u + ε ) − ℓ u ( θ u )} ≤ u ∈ I ∑ { ℓ u ( θ i + ε ) − ℓ u ( θ i )} .
The last inequality uses θ ^ u ≤ θ ^ i \widehat{\theta}_u\le\widehat{\theta}_i θ u ≤ θ i on I I I and the monotonicity of the discrete derivative from Lemma 4.1 .
Let us now track the amount of change in the penalty term after perturbation. Write
TV ( θ ) = ∑ { u , v } ∈ E ∣ θ u − θ v ∣ . \operatorname{TV}(\theta)=\sum_{\{u,v\}\in E}|\theta_u-\theta_v|. TV ( θ ) = { u , v } ∈ E ∑ ∣ θ u − θ v ∣.
Edges internal to I I I or to I c I^c I c contribute no change. Each edge from I I I to J ∖ I J\setminus I J ∖ I contributes at most ε \varepsilon ε . Now, by definition of J J J , for an edge from u ∈ I u\in I u ∈ I to v ∈ J c v\in J^c v ∈ J c , we have
θ ^ u ≤ θ ^ i < θ ^ v . \widehat{\theta}_u\le\widehat{\theta}_i<\widehat{\theta}_v. θ u ≤ θ i < θ v .
Thus, for all sufficiently small ε > 0 \varepsilon>0 ε > 0 , the contribution of this edge towards the change in the penalty is exactly − ε -\varepsilon − ε . Consequently,
TV ( θ ~ ) − TV ( θ ^ ) ≤ − ε ∣ E ( I , J c ) ∣ + ε ∣ E ( I , J ∖ I ) ∣ = ε C I , J . \operatorname{TV}(\widetilde{\theta})-\operatorname{TV}(\widehat{\theta})
\le-\varepsilon|E(I,J^c)|+\varepsilon|E(I,J\setminus I)|
= \varepsilon C_{I,J}. TV ( θ ) − TV ( θ ) ≤ − ε ∣ E ( I , J c ) ∣ + ε ∣ E ( I , J ∖ I ) ∣ = ε C I , J .
Combining these bounds gives the key inequality
F ( θ ~ ) − F ( θ ^ ) ≤ ∑ u ∈ I { ℓ u ( θ ^ i + ε ) − ℓ u ( θ ^ i ) } + λ ε C I , J = Φ I , J ( θ ^ i + ε ) − Φ I , J ( θ ^ i ) . (53) F(\widetilde{\theta})-F(\widehat{\theta})
\le\sum_{u\in I}\{\ell_u(\widehat{\theta}_i+\varepsilon)-\ell_u(\widehat{\theta}_i)\}+\lambda\varepsilon C_{I,J}
= \Phi_{I,J}(\widehat{\theta}_i+\varepsilon)-\Phi_{I,J}(\widehat{\theta}_i). \tag*{(53)} F ( θ ) − F ( θ ) ≤ u ∈ I ∑ { ℓ u ( θ i + ε ) − ℓ u ( θ i )} + λ ε C I , J = Φ I , J ( θ i + ε ) − Φ I , J ( θ i ) . (53)
Together with (52) , this yields
0 < Φ I , J ( θ ^ i + ε ) − Φ I , J ( θ ^ i ) 0<\Phi_{I,J}(\widehat{\theta}_i+\varepsilon)-\Phi_{I,J}(\widehat{\theta}_i) 0 < Φ I , J ( θ i + ε ) − Φ I , J ( θ i )
for every sufficiently small ε > 0 \varepsilon>0 ε > 0 . By the contrapositive statement of the second assertion of Lemma 4.1 , this implies
r + ( Φ I , J ) ≤ θ ^ i . r_+(\Phi_{I,J})\le\widehat{\theta}_i. r + ( Φ I , J ) ≤ θ i .
Since this holds for every I ⊆ J I\subseteq J I ⊆ J containing i i i , we conclude that
max I ⊆ J i ∈ I r + ( Φ I , J ) ≤ θ ^ i . \max_{\substack{I\subseteq J\\i\in I}}r_+(\Phi_{I,J})\le\widehat{\theta}_i. I ⊆ J i ∈ I max r + ( Φ I , J ) ≤ θ i .
Using this particular J J J in the outer minimum gives
min J ⊆ V i ∈ J max I ⊆ J i ∈ I r + ( Φ I , J ) ≤ θ ^ i . \min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}r_+(\Phi_{I,J})\le\widehat{\theta}_i. J ⊆ V i ∈ J min I ⊆ J i ∈ I max r + ( Φ I , J ) ≤ θ i .
Combining this with the upper bound proves
θ ^ i = min J ⊆ V i ∈ J max I ⊆ J i ∈ I r + ( Φ I , J ) . \widehat{\theta}_i=\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}r_+(\Phi_{I,J}). θ i = J ⊆ V i ∈ J min I ⊆ J i ∈ I max r + ( Φ I , J ) .
Step 5: The Connected Set Restriction.
The connected set restriction follows as in § 2 . For the upper bound, let J J J be connected and replace
J ∩ { u : θ ^ u ≥ θ ^ i } J\cap\{u:\widehat{\theta}_u\ge\widehat{\theta}_i\} J ∩ { u : θ u ≥ θ i }
by its connected component containing i i i . Every edge from this component to J ∖ I J\setminus I J ∖ I still leads to a fitted value strictly below θ ^ i \widehat{\theta}_i θ i . The upper-bound argument therefore remains valid. For the lower bound, take J J J to be the connected component containing i i i of
{ u : θ ^ u ≤ θ ^ i } . \{u:\widehat{\theta}_u\le\widehat{\theta}_i\}. { u : θ u ≤ θ i } .
Every neighbor of J J J outside J J J has fitted value strictly above θ ^ i \widehat{\theta}_i θ i ; otherwise it would belong to the same component. The perturbation argument therefore applies to every connected I ⊆ J I\subseteq J I ⊆ J containing i i i . This proves (28) .
Step 6: The Maxmin Representation.
Apply the minmax representation to the reflected losses
ℓ ~ u ( x ) = ℓ u ( − x ) . \widetilde{\ell}_u(x)=\ell_u(-x). ℓ u ( x ) = ℓ u ( − x ) .
The reflected objective is F ~ ( θ ) = F ( − θ ) \widetilde{F}(\theta)=F(-\theta) F ( θ ) = F ( − θ ) , which is again convex and coercive. Its solution set is − S -S − S , so its upper endpoint at coordinate i i i is
max η ∈ − S η i = − min θ ∈ S θ i = − θ ^ i . \max_{\eta\in-S}\eta_i=-\min_{\theta\in S}\theta_i=-\widehat{\theta}_i. η ∈ − S max η i = − θ ∈ S min θ i = − θ i .
Moreover, its corresponding scalar function satisfies
Φ ~ I , J ( x ) = ∑ u ∈ I ℓ u ( − x ) + λ C I , J x = Φ I , J ( − x ) . \widetilde{\Phi}_{I,J}(x)=\sum_{u\in I}\ell_u(-x)+\lambda C_{I,J}x=\Phi_{I,J}(-x). Φ I , J ( x ) = u ∈ I ∑ ℓ u ( − x ) + λ C I , J x = Φ I , J ( − x ) .
Since
r + ( f ( − ⋅ ) ) = − r − ( f ) , r_+\bigl(f(-\cdot)\bigr)=-r_-(f), r + ( f ( − ⋅ ) ) = − r − ( f ) ,
negating the reflected minmax identity exchanges minimum and maximum and gives (27) . The same argument applies with or without the connected set restrictions. This completes the proof of part (ii).
Step 7: Lattice Structure and Simultaneous Attainment.
We first show that S S S is a lattice under pointwise minimum and maximum. For θ , η ∈ R V \theta,\eta\in\mathbb{R}^{V} θ , η ∈ R V , write
( θ ∧ η ) u = min { θ u , η u } , ( θ ∨ η ) u = max { θ u , η u } . (\theta\wedge\eta)_u=\min\{\theta_u,\eta_u\},\qquad(\theta\vee\eta)_u=\max\{\theta_u,\eta_u\}. ( θ ∧ η ) u = min { θ u , η u } , ( θ ∨ η ) u = max { θ u , η u } .
We use the elementary inequality
∣ min ( a , c ) − min ( b , d ) ∣ + ∣ max ( a , c ) − max ( b , d ) ∣ ≤ ∣ a − b ∣ + ∣ c − d ∣ . \left\lvert\min(a,c)-\min(b,d)\right\rvert+\left\lvert\max(a,c)-\max(b,d)\right\rvert
\le\left\lvert a-b\right\rvert+\left\lvert c-d\right\rvert. ∣ min ( a , c ) − min ( b , d ) ∣ + ∣ max ( a , c ) − max ( b , d ) ∣ ≤ ∣ a − b ∣ + ∣ c − d ∣ .
To see this, note that if a ≤ c a\le c a ≤ c and b ≤ d b\le d b ≤ d , or a ≥ c a\ge c a ≥ c and b ≥ d b\ge d b ≥ d , the left-hand side equals ∣ a − b ∣ + ∣ c − d ∣ \left\lvert a-b\right\rvert+\left\lvert c-d\right\rvert ∣ a − b ∣ + ∣ c − d ∣ . Otherwise, say a ≤ c a\le c a ≤ c and b > d b>d b > d ; then the left-hand side is ∣ a − d ∣ + ∣ c − b ∣ \left\lvert a-d\right\rvert+\left\lvert c-b\right\rvert ∣ a − d ∣ + ∣ c − b ∣ , and the claim follows since a − d a-d a − d and c − b c-b c − b both lie between a − b a-b a − b and c − d c-d c − d . Applying this inequality to each edge and using separability of the losses gives
F ( θ ∧ η ) + F ( θ ∨ η ) ≤ F ( θ ) + F ( η ) . F(\theta\wedge\eta)+F(\theta\vee\eta)\le F(\theta)+F(\eta). F ( θ ∧ η ) + F ( θ ∨ η ) ≤ F ( θ ) + F ( η ) .
If θ , η ∈ S \theta,\eta\in\mathcal{S} θ , η ∈ S , both terms on the left are at least the minimum of F F F , so both θ ∧ η \theta\wedge\eta θ ∧ η and θ ∨ η \theta\vee\eta θ ∨ η also belong to S \mathcal{S} S . This proves the lattice assertion.
By compactness, for each i ∈ V i\in V i ∈ V we can choose solutions θ i , − \theta^{i,-} θ i , − and θ i , + \theta^{i,+} θ i , + satisfying θ i i , − = θ ^ i \theta^{i,-}_i=\widehat{\theta}_i θ i i , − = θ i and θ i i , + = θ ‾ i \theta^{i,+}_i=\overline{\theta}_i θ i i , + = θ i . Since V V V is finite, closure under coordinatewise minimum and maximum implies that
⋀ i ∈ V θ i , − ∈ S , ⋁ i ∈ V θ i , + ∈ S . \bigwedge_{i\in V}\theta^{i,-}\in\mathcal{S},\qquad\bigvee_{i\in V}\theta^{i,+}\in\mathcal{S}. i ∈ V ⋀ θ i , − ∈ S , i ∈ V ⋁ θ i , + ∈ S .
At every coordinate u u u , all solutions have values in [ θ ^ u , θ ‾ u ] [\widehat{\theta}_u,\overline{\theta}_u] [ θ u , θ u ] , while θ u , − \theta^{u,-} θ u , − and θ u , + \theta^{u,+} θ u , + attain the respective endpoints in S \mathcal{S} S . Thus, these two vectors are exactly θ ^ \widehat{\theta} θ and θ ‾ \overline{\theta} θ . This proves part (iii).
Step 8: Uniqueness under Strict Convexity. If F F F is strictly convex, two distinct minimizers cannot exist, as the midpoint of these two points would have objective value strictly below the minimum. Since a minimizer exists, it is unique, and hence it follows that θ ^ = θ ‾ \widehat{\theta}=\overline{\theta} θ = θ . Finally, if every ℓ u \ell_u ℓ u is strictly convex, then θ ↦ ∑ u ∈ V ℓ u ( θ u ) \theta\mapsto\sum_{u\in V}\ell_u(\theta_u) θ ↦ ∑ u ∈ V ℓ u ( θ u ) is strictly convex. Adding the convex TV penalty preserves strict convexity, which proves part (iv). □
Proof of Proposition 1.7
For ℓ u ( t ) = ρ τ ( y u − t ) \ell_u(t)=\rho_\tau(y_u-t) ℓ u ( t ) = ρ τ ( y u − t ) , the one-sided derivatives are
ℓ u , − ′ ( t ) = 1 { y u < t } − τ , ℓ u , + ′ ( t ) = 1 { y u ≤ t } − τ . \ell'_{u,-}(t)=1\{y_u<t\}-\tau,\qquad\ell'_{u,+}(t)=1\{y_u\le t\}-\tau. ℓ u , − ′ ( t ) = 1 { y u < t } − τ , ℓ u , + ′ ( t ) = 1 { y u ≤ t } − τ .
Consequently, with m = ∣ I ∣ m=\lvert I\rvert m = ∣ I ∣ ,
q ‾ I , J = inf { t : # { u ∈ I : y u ≤ t } ≥ m τ + λ C I , J } = y I , ( ⌈ m τ + λ C I , J ⌉ ) , \overline{q}_{I,J}=\inf\{t:\#\{u\in I:y_u\le t\}\ge m\tau+\lambda C_{I,J}\}
=y_{I,(\lceil m\tau+\lambda C_{I,J}\rceil)}, q I , J = inf { t : # { u ∈ I : y u ≤ t } ≥ m τ + λ C I , J } = y I , (⌈ m τ + λ C I , J ⌉) ,
q ‾ I , J = sup { t : # { u ∈ I : y u < t } ≤ m τ − λ C I , J } = y I , ( ⌊ m τ − λ C I , J ⌋ + 1 ) . \underline{q}_{I,J}=\sup\{t:\#\{u\in I:y_u<t\}\le m\tau-\lambda C_{I,J}\}
=y_{I,(\lfloor m\tau-\lambda C_{I,J}\rfloor+1)}. q I , J = sup { t : # { u ∈ I : y u < t } ≤ m τ − λ C I , J } = y I , (⌊ m τ − λ C I , J ⌋ + 1 ) .
These identities include ties and ranks outside 1 , … , m 1,\ldots,m 1 , … , m under the stated infinite-rank conventions. The ceiling and floor-plus-one arise from the weak and strict inequalities, respectively. Substitution into Theorem 1.6 proves all assertions of the proposition. □
Proof of Theorem 1.8
Throughout this subsection, for θ ∈ R V \theta\in\mathbb{R}^{V} θ ∈ R V we write
f ( θ ) = ∑ u ∈ V ℓ u ( θ u ) , f(\theta)=\sum_{u\in V}\ell_u(\theta_u), f ( θ ) = u ∈ V ∑ ℓ u ( θ u ) ,
P ( θ ) = ∑ ( u , v ) ∈ A ( θ v − θ u ) − , P(\theta)=\sum_{(u,v)\in A}(\theta_v-\theta_u)_{-}, P ( θ ) = ( u , v ) ∈ A ∑ ( θ v − θ u ) − ,
as in Step 4 of the proof of Lemma 1.5, with the squared loss replaced by a general separable convex loss. Every summand of P P P is nonnegative, and the summand of an edge ( u , v ) ∈ A (u,v)\in A ( u , v ) ∈ A vanishes if and only if θ u ≤ θ v \theta_u\leq\theta_v θ u ≤ θ v . Hence
P ≥ 0 on R V , P ( θ ) = 0 ⟺ θ ∈ K D . (54) P\geq0\text{ on }\mathbb{R}^{V},\qquad P(\theta)=0\iff\theta\in\mathcal{K}_{D}. \tag*{(54)} P ≥ 0 on R V , P ( θ ) = 0 ⟺ θ ∈ K D . (54)
The standing assumptions of Theorem 1.8 imply that every ℓ u \ell_u ℓ u is finite, convex, and coercive, and hence,
f ( θ ( k ) ) → + ∞ whenever ∥ θ ( k ) ∥ → ∞ , θ ( k ) ∈ R V . (55) f(\theta^{(k)})\to+\infty\quad\text{whenever }\lVert\theta^{(k)}\rVert\to\infty,\quad\theta^{(k)}\in\mathbb{R}^{V}. \tag*{(55)} f ( θ ( k ) ) → + ∞ whenever ∥ θ ( k ) ∥ → ∞ , θ ( k ) ∈ R V . (55)
For λ ≥ 0 \lambda\geq0 λ ≥ 0 , the nearly isotonic objective under the losses ℓ u \ell_u ℓ u is
H λ ( θ ) = f ( θ ) + λ P ( θ ) , θ ∈ R V , (56) H_{\lambda}(\theta)=f(\theta)+\lambda P(\theta),\qquad\theta\in\mathbb{R}^{V}, \tag*{(56)} H λ ( θ ) = f ( θ ) + λ P ( θ ) , θ ∈ R V , (56)
which reduces to the objective in (15) when ℓ u ( x ) = 1 2 ( y u − x ) 2 \ell_u(x)=\frac{1}{2}(y_u-x)^2 ℓ u ( x ) = 2 1 ( y u − x ) 2 .
The proof follows the squared-loss argument of § 3 . There, isotonic regression was reduced to TVD in three stages: Lemma 1.3 and Corollary 1.4 expressed nearly isotonic regression as TVD, Lemma 1.5 identified nearly isotonic regression with isotonic regression at a large finite penalty, and the proof of Lemma 1.5 reduced the nested-set formula to lower and upper sets. Lemma 4.2 below is the counterpart of the first stage, Lemma 4.3 is the counterpart of the second, and Steps 1–3 in the proof of Theorem 1.8 are the counterparts of Steps 1–3 in the proof of Lemma 1.5.
The next lemma is the convex-loss counterpart of Lemma 1.3 and Corollary 1.4. Under squared loss, the linear term produced by the asymmetric penalty was absorbed into the data by completing the square; for a general loss it is absorbed into the loss itself.
Lemma 4.2 (Nearly isotonic regression as generalized TVD). Let G ~ \widetilde{G} G be the underlying undirected graph of D D D , let d u = deg D + ( u ) − deg D − ( u ) d_u=\deg_D^{+}(u)-\deg_D^{-}(u) d u = deg D + ( u ) − deg D − ( u ) , and for λ ≥ 0 \lambda\geq0 λ ≥ 0 define
ℓ u ( λ ) ( x ) = ℓ u ( x ) + λ 2 d u x , u ∈ V , x ∈ R . (57) \ell_u^{(\lambda)}(x)=\ell_u(x)+\frac{\lambda}{2}d_u x,\qquad u\in V,\ x\in\mathbb{R}. \tag*{(57)} ℓ u ( λ ) ( x ) = ℓ u ( x ) + 2 λ d u x , u ∈ V , x ∈ R . (57) Then each ℓ u ( λ ) \ell_u^{(\lambda)} ℓ u ( λ ) is finite and convex, and for every θ ∈ R V \theta\in\mathbb{R}^{V} θ ∈ R V ,
H λ ( θ ) = ∑ u ∈ V ℓ u ( λ ) ( θ u ) + λ 2 TV G ~ ( θ ) . (58) H_{\lambda}(\theta)=\sum_{u\in V}\ell_u^{(\lambda)}(\theta_u)+\frac{\lambda}{2}\operatorname{TV}_{\widetilde{G}}(\theta). \tag*{(58)} H λ ( θ ) = u ∈ V ∑ ℓ u ( λ ) ( θ u ) + 2 λ TV G ( θ ) . (58) In other words, H λ H_{\lambda} H λ is the generalized graph TVD objective (22) on the graph G ~ \widetilde{G} G , with losses ℓ u ( λ ) \ell_u^{(\lambda)} ℓ u ( λ ) and penalty parameter λ / 2 \lambda/2 λ /2 .
Proof. Each ℓ u ( λ ) \ell_u^{(\lambda)} ℓ u ( λ ) is the sum of a finite convex function and a linear function, so it is finite and convex. Apply (13) with λ + = 0 \lambda_+ = 0 λ + = 0 and λ − = λ \lambda_- = \lambda λ − = λ , so that a = λ / 2 a = \lambda/2 a = λ /2 and b = − λ / 2 b = -\lambda/2 b = − λ /2 :
λ P ( θ ) = λ 2 ∑ ( u , v ) ∈ A ∣ θ v − θ u ∣ + λ 2 ∑ u ∈ V d u θ u . \lambda P(\theta) = \frac{\lambda}{2} \sum_{(u,v)\in A} \lvert\theta_v-\theta_u\rvert+ \frac{\lambda}{2}\sum_{u\in V}d_u\theta_u. λ P ( θ ) = 2 λ ( u , v ) ∈ A ∑ ∣ θ v − θ u ∣ + 2 λ u ∈ V ∑ d u θ u .
Since D D D is acyclic, no two vertices are joined by directed edges in both directions. The directed edges of D D D therefore correspond one-to-one to the edges of G ~ \widetilde{G} G , and the first sum equals TV G ~ ( θ ) \operatorname{TV}_{\widetilde{G}}(\theta) TV G ( θ ) . Adding f ( θ ) f(\theta) f ( θ ) to both sides and grouping the linear term with the losses gives (58) .
The next lemma is the convex-loss counterpart of Lemma 1.5.
Lemma 4.3 (Exact agreement with isotonic regression). Under the assumptions of Theorem 1.8 , the following statements hold.
(a) The set S i s o S_{\mathrm{iso}} S iso is nonempty, compact, and convex. We write f ∗ = min θ ∈ K D f ( θ ) f^*=\min_{\theta\in K_D} f(\theta) f ∗ = min θ ∈ K D f ( θ ) .
(b) There is a finite constant γ ∗ ≥ 0 \gamma_* \ge0 γ ∗ ≥ 0 such that, for every θ ∈ R V \theta\in\mathbb{R}^V θ ∈ R V and every λ ≥ 0 \lambda\ge0 λ ≥ 0 ,
H λ ( θ ) − f ∗ ≥ ( λ − γ ∗ ) P ( θ ) . (59) H_\lambda(\theta)-f^* \ge(\lambda-\gamma_*)P(\theta). \tag*{(59)} H λ ( θ ) − f ∗ ≥ ( λ − γ ∗ ) P ( θ ) . (59) (c) For every λ > γ ∗ \lambda>\gamma_* λ > γ ∗ ,
arg min θ ∈ R V H λ ( θ ) = S i s o . (60) \underset{\theta\in\mathbb{R}^V}{\operatorname{arg\,min}}\ H_\lambda(\theta)=S_{\mathrm{iso}}. \tag*{(60)} θ ∈ R V arg min H λ ( θ ) = S iso . (60)
Proof. Part (a). Each ℓ u \ell_u ℓ u is finite and convex, hence continuous, so f f f is continuous and convex on R V \mathbb{R}^V R V . The cone K D K_D K D is closed and convex and contains 0 0 0 . Consider
K = { θ ∈ K D : f ( θ ) ≤ f ( 0 ) } . K=\{\theta\in K_D:f(\theta)\le f(0)\}. K = { θ ∈ K D : f ( θ ) ≤ f ( 0 )} .
This set is nonempty and closed. It is also bounded: otherwise it would contain a sequence θ ( k ) \theta^{(k)} θ ( k ) with ∥ θ ( k ) ∥ → ∞ \lVert\theta^{(k)}\rVert\to\infty ∥ θ ( k ) ∥ → ∞ and f ( θ ( k ) ) ≤ f ( 0 ) f(\theta^{(k)})\le f(0) f ( θ ( k ) ) ≤ f ( 0 ) , contradicting (55) . Thus K K K is compact, and f f f attains its minimum over K K K . This minimum is the minimum f ∗ f^* f ∗ of f f f over K D K_D K D , because f > f ( 0 ) ≥ f ∗ f>f(0)\ge f^* f > f ( 0 ) ≥ f ∗ on K D ∖ K K_D\setminus K K D ∖ K . Hence,
S i s o = { θ ∈ K D : f ( θ ) = f ∗ } . S_{\mathrm{iso}}=\{\theta\in K_D:f(\theta)=f^*\}. S iso = { θ ∈ K D : f ( θ ) = f ∗ } .
is nonempty. It is a closed subset of K K K due to continuity of f f f , hence it is compact, and it is convex because both K D K_D K D and f f f are convex.
Part (b). Fix θ ∗ ∈ S i s o \theta^*\in S_{\mathrm{iso}} θ ∗ ∈ S iso . By definition, θ ∗ \theta^* θ ∗ minimizes the finite convex function f f f subject to the affine inequality constraints
c u v ( θ ) : = θ u − θ v ≤ 0 , ( u , v ) ∈ A . c_{uv}(\theta):=\theta_u-\theta_v\le0,\qquad(u,v)\in A. c uv ( θ ) := θ u − θ v ≤ 0 , ( u , v ) ∈ A .
These constraints are strictly feasible. Indeed, since D D D is acyclic, it admits a topological ordering, that is, a bijection π : V → { 1 , … , n } \pi:V\to\{1,\ldots,n\} π : V → { 1 , … , n } with π ( u ) < π ( v ) \pi(u)<\pi(v) π ( u ) < π ( v ) for every ( u , v ) ∈ A (u,v)\in A ( u , v ) ∈ A , and the vector θ 0 = ( π ( u ) ) u ∈ V \theta^0=(\pi(u))_{u\in V} θ 0 = ( π ( u ) ) u ∈ V satisfies c u v ( θ 0 ) < 0 c_{uv}(\theta^0)<0 c uv ( θ 0 ) < 0 for every ( u , v ) ∈ A (u,v)\in A ( u , v ) ∈ A . The optimal value f ∗ f^* f ∗ is finite. The Kuhn–Tucker theorem [20 Theorems 28.2 and 28.3] therefore provides multipliers γ u v ≥ 0 \gamma_{uv} \ge0 γ uv ≥ 0 , ( u , v ) ∈ A (u,v) \in A ( u , v ) ∈ A , such that
0 ∈ ∂ f ( θ ∗ ) + ∑ ( u , v ) ∈ A γ u v ∇ c u v , 0 \in\partial f(\theta^*) + \sum_{(u,v)\in A} \gamma_{uv} \nabla c_{uv}, 0 ∈ ∂ f ( θ ∗ ) + ( u , v ) ∈ A ∑ γ uv ∇ c uv ,
γ u v c u v ( θ ∗ ) = 0 , ( u , v ) ∈ A . \gamma_{uv}c_{uv}(\theta^*) = 0,\quad(u,v) \in A. γ uv c uv ( θ ∗ ) = 0 , ( u , v ) ∈ A .
Here ∇ c u v = e u − e v \nabla c_{uv} = e_u - e_v ∇ c uv = e u − e v , where e u e_u e u is the u u u -th standard basis vector of R V \mathbb{R}^V R V . Moreover, since f f f is separable, a vector g g g belongs to ∂ f ( θ ∗ ) \partial f(\theta^*) ∂ f ( θ ∗ ) if and only if g u ∈ ∂ ℓ u ( θ u ∗ ) g_u \in\partial\ell_u(\theta_u^*) g u ∈ ∂ ℓ u ( θ u ∗ ) for every u ∈ V u \in V u ∈ V . Reading the first condition coordinate by coordinate, we obtain for each u ∈ V u \in V u ∈ V , there exists g u ∈ ∂ ℓ u ( θ u ∗ ) g_u \in\partial\ell_u(\theta_u^*) g u ∈ ∂ ℓ u ( θ u ∗ ) , such that
g u + ∑ v : ( u , v ) ∈ A γ u v − ∑ v : ( v , u ) ∈ A γ v u = 0 , u ∈ V , γ u v ( θ u ∗ − θ v ∗ ) = 0 , ( u , v ) ∈ A . (61) \begin{aligned}
g_u + \sum_{v:(u,v)\in A} \gamma_{uv} - \sum_{v:(v,u)\in A} \gamma_{vu} &= 0,\quad u \in V,\\
\gamma_{uv}(\theta_u^*-\theta_v^*) &= 0,\quad(u,v) \in A. \tag*{(61)}
\end{aligned} g u + v : ( u , v ) ∈ A ∑ γ uv − v : ( v , u ) ∈ A ∑ γ v u γ uv ( θ u ∗ − θ v ∗ ) = 0 , u ∈ V , = 0 , ( u , v ) ∈ A . (61)
If A = ∅ A = \varnothing A = ∅ , there are no constraints and (61) reads g u = 0 g_u = 0 g u = 0 for all u u u . Define
γ ∗ = max ( u , v ) ∈ A γ u v , \gamma_* = \max_{(u,v)\in A} \gamma_{uv}, γ ∗ = ( u , v ) ∈ A max γ uv ,
with γ ∗ = 0 \gamma_* = 0 γ ∗ = 0 if A = ∅ A = \varnothing A = ∅ .
Now fix θ ∈ R V \theta\in\mathbb{R}^V θ ∈ R V and write δ = θ − θ ∗ \delta= \theta-\theta^* δ = θ − θ ∗ . The definition of subgradient gives ℓ u ( θ u ) − ℓ u ( θ u ∗ ) ≥ g u δ u \ell_u(\theta_u)-\ell_u(\theta_u^*) \ge g_u\delta_u ℓ u ( θ u ) − ℓ u ( θ u ∗ ) ≥ g u δ u . Summing this inequality over u ∈ V u \in V u ∈ V , and using the first line of (61) give
f ( θ ) − f ∗ ≥ ∑ u ∈ V g u δ u = ∑ u ∈ V δ u { ∑ v : ( v , u ) ∈ A γ v u − ∑ v : ( u , v ) ∈ A γ u v } = ∑ ( u , v ) ∈ A γ u v ( δ v − δ u ) . \begin{aligned}
f(\theta)-f^* &\ge\sum_{u\in V}g_u\delta_u\\
&= \sum_{u\in V}\delta_u\left\{\sum_{v:(v,u)\in A}\gamma_{vu}-\sum_{v:(u,v)\in A}\gamma_{uv}\right\}\\
&= \sum_{(u,v)\in A}\gamma_{uv}(\delta_v-\delta_u).
\end{aligned} f ( θ ) − f ∗ ≥ u ∈ V ∑ g u δ u = u ∈ V ∑ δ u ⎩ ⎨ ⎧ v : ( v , u ) ∈ A ∑ γ v u − v : ( u , v ) ∈ A ∑ γ uv ⎭ ⎬ ⎫ = ( u , v ) ∈ A ∑ γ uv ( δ v − δ u ) .
The last equality holds because each edge ( u , v ) ∈ A (u,v) \in A ( u , v ) ∈ A appears exactly twice in the double sum: once with coefficient + γ u v δ v +\gamma_{uv}\delta_v + γ uv δ v , at its head v v v , and once with coefficient − γ u v δ u -\gamma_{uv}\delta_u − γ uv δ u , at its tail u u u . By the second line of (61) ,
γ u v ( δ v − δ u ) = γ u v ( θ v − θ u ) − γ u v ( θ v ∗ − θ u ∗ ) = γ u v ( θ v − θ u ) . \begin{aligned}
\gamma_{uv}(\delta_v-\delta_u) &= \gamma_{uv}(\theta_v-\theta_u)-\gamma_{uv}(\theta_v^*-\theta_u^*)\\
&= \gamma_{uv}(\theta_v-\theta_u).
\end{aligned} γ uv ( δ v − δ u ) = γ uv ( θ v − θ u ) − γ uv ( θ v ∗ − θ u ∗ ) = γ uv ( θ v − θ u ) .
Finally, x ≥ − x − x \ge-x_- x ≥ − x − for every x ∈ R x \in\mathbb{R} x ∈ R , and 0 ≤ γ u v ≤ γ ∗ 0 \le\gamma_{uv} \le\gamma_* 0 ≤ γ uv ≤ γ ∗ , so
γ u v ( θ v − θ u ) ≥ − γ u v ( θ v − θ u ) − ≥ − γ ∗ ( θ v − θ u ) − . \gamma_{uv}(\theta_v-\theta_u) \ge-\gamma_{uv}(\theta_v-\theta_u)_- \ge-\gamma_*(\theta_v-\theta_u)_-. γ uv ( θ v − θ u ) ≥ − γ uv ( θ v − θ u ) − ≥ − γ ∗ ( θ v − θ u ) − .
Summing over ( u , v ) ∈ A (u,v) \in A ( u , v ) ∈ A yields
f ( θ ) − f ∗ ≥ − γ ∗ P ( θ ) , f(\theta)-f^* \ge-\gamma_*P(\theta), f ( θ ) − f ∗ ≥ − γ ∗ P ( θ ) ,
and adding λ P ( θ ) \lambda P(\theta) λ P ( θ ) to both sides gives (59) .
Part (c). Let λ > γ ∗ \lambda> \gamma_* λ > γ ∗ . By (59) and P ≥ 0 P \ge0 P ≥ 0 , we have H λ ( θ ) ≥ f ∗ H_\lambda(\theta) \ge f^* H λ ( θ ) ≥ f ∗ for every θ ∈ R V \theta\in\mathbb{R}^V θ ∈ R V . If θ ∈ S i s o \theta\in S_{\mathrm{iso}} θ ∈ S iso , then P ( θ ) = 0 P(\theta) = 0 P ( θ ) = 0 by (54) and f ( θ ) = f ∗ f(\theta) = f^* f ( θ ) = f ∗ , so H λ ( θ ) = f ∗ H_\lambda(\theta) = f^* H λ ( θ ) = f ∗ . Thus min R V H λ = f ∗ \min_{\mathbb{R}^V} H_\lambda= f^* min R V H λ = f ∗ , and every element of S i s o S_{\mathrm{iso}} S iso minimizes H λ H_\lambda H λ . Conversely, let θ \theta θ minimize H λ H_\lambda H λ , so that H λ ( θ ) = f ∗ H_\lambda(\theta) = f^* H λ ( θ ) = f ∗ . Then (59) gives ( λ − γ ∗ ) P ( θ ) ≤ 0 (\lambda-\gamma_*)P(\theta) \le0 ( λ − γ ∗ ) P ( θ ) ≤ 0 , and hence P ( θ ) = 0 P(\theta) = 0 P ( θ ) = 0 . By (54) , θ ∈ K D \theta\in K_D θ ∈ K D , and f ( θ ) = H λ ( θ ) = f ∗ f(\theta) = H_\lambda(\theta) = f^* f ( θ ) = H λ ( θ ) = f ∗ . Therefore, θ ∈ S i s o \theta\in S_{\mathrm{iso}} θ ∈ S iso .
Proof of Theorem 1.8 . We prove the four parts in order. The proof of part (ii) is organized as the proof of Lemma 1.5.
Part (i): Coordinate intervals. By Lemma 4.3 (a), S i s o S_{\mathrm{iso}} S iso is nonempty, compact, and convex. For each i ∈ V i \in V i ∈ V , the set { θ i : θ ∈ S i s o } \{\theta_i:\theta\in S_{\mathrm{iso}}\} { θ i : θ ∈ S iso } is the image of S i s o S_{\mathrm{iso}} S iso under the continuous linear map θ ↦ θ i \theta\mapsto\theta_i θ ↦ θ i . It is therefore a nonempty compact convex subset of R \mathbb{R} R , that is, a closed bounded interval. Its endpoints are
θ ^ i i s o = min θ ∈ S i s o θ i , θ ‾ i i s o = max θ ∈ S i s o θ i , \widehat{\theta}^{\mathrm{iso}}_i = \min_{\theta\in S_{\mathrm{iso}}} \theta_i,\qquad\overline{\theta}^{\mathrm{iso}}_i = \max_{\theta\in S_{\mathrm{iso}}} \theta_i, θ i iso = θ ∈ S iso min θ i , θ i iso = θ ∈ S iso max θ i ,
both of which are finite. This proves part (i).
Part (ii): The nested-set formula. Fix i ∈ V i \in V i ∈ V and put
t = θ ‾ i i s o ∈ R . t = \overline{\theta}^{\mathrm{iso}}_i \in\mathbb{R}. t = θ i iso ∈ R .
The one-sided derivatives of the finite convex functions ℓ u \ell_u ℓ u are finite at t t t , so
M : = max u ∈ V max { ∣ ℓ u , − ′ ( t ) ∣ , ∣ ℓ u , + ′ ( t ) ∣ } < ∞ . M := \max_{u \in V} \max\{|\ell'_{u,-}(t)|,|\ell'_{u,+}(t)|\} < \infty. M := u ∈ V max max { ∣ ℓ u , − ′ ( t ) ∣ , ∣ ℓ u , + ′ ( t ) ∣ } < ∞.
With γ ∗ \gamma_* γ ∗ as in Lemma 4.3 , fix
λ > λ 0 : = max { γ ∗ , ∣ V ∣ M } . (62) \lambda> \lambda_0 := \max\{\gamma_*, |V|M\}. \tag*{(62)} λ > λ 0 := max { γ ∗ , ∣ V ∣ M } . (62)
This threshold plays the role of λ 0 = n ( y max − y min ) \lambda_0 = n(y_{\max} - y_{\min}) λ 0 = n ( y m a x − y m i n ) in the proof of Lemma 1.5. It may depend on i i i through t t t . This is harmless: λ \lambda λ is an auxiliary parameter, which does not appear in (34) or (35) .
By Lemma 4.2 , H λ H_\lambda H λ is the generalized graph TVD objective on G ~ \widetilde{G} G with finite convex losses ℓ u ( λ ) \ell_u^{(\lambda)} ℓ u ( λ ) and penalty parameter λ / 2 \lambda/2 λ /2 . The tilted losses ℓ u ( λ ) \ell_u^{(\lambda)} ℓ u ( λ ) need not be coercive. However, P ≥ 0 P \ge0 P ≥ 0 by (54) , so H λ ≥ f H_\lambda\ge f H λ ≥ f , and f f f is coercive on R V \mathbb{R}^V R V by (55) . Hence H λ H_\lambda H λ is coercive, and Theorem 1.6 applies to it. By Lemma 4.3 (c), the solution set of this TVD problem is S i s o S_{\mathrm{iso}} S iso , so its upper endpoint at coordinate i i i is t t t . Therefore, it follows from (28) that
t = min J ⊆ V i ∈ J max I ⊆ V i ∈ I r + ( Φ I , J ( λ ) ) , (63) t = \min_{J \subseteq V \atop i \in J} \max_{I \subseteq V \atop i \in I} r_+\left(\Phi^{(\lambda)}_{I,J}\right), \tag*{(63)} t = i ∈ J J ⊆ V min i ∈ I I ⊆ V max r + ( Φ I , J ( λ ) ) , (63)
where
Φ I , J ( λ ) ( x ) = ∑ u ∈ I ℓ u ( λ ) ( x ) + λ 2 C I , J x , \Phi^{(\lambda)}_{I,J}(x) = \sum_{u \in I} \ell_u^{(\lambda)}(x) + \frac{\lambda}{2} C_{I,J}x, Φ I , J ( λ ) ( x ) = u ∈ I ∑ ℓ u ( λ ) ( x ) + 2 λ C I , J x ,
and C I , J C_{I,J} C I , J is computed in G ~ \widetilde{G} G . As in § 3 , for disjoint S , T ⊆ V S,T \subseteq V S , T ⊆ V let A ( S , T ) A(S,T) A ( S , T ) denote the set of directed edges of D D D from S S S to T T T . By the definition (57) of ℓ u ( λ ) \ell_u^{(\lambda)} ℓ u ( λ ) and the boundary identity (42) ,
Φ I , J ( λ ) ( x ) = ∑ u ∈ I ℓ u ( x ) + λ 2 { C I , J + ∑ u ∈ I d u } x = ∑ u ∈ I ℓ u ( x ) + λ { ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } x . \begin{aligned}
\Phi_{I,J}^{(\lambda)}(x)
&=\sum_{u\in I}\ell_u(x)+\frac{\lambda}{2}\left\{C_{I,J}+\sum_{u\in I}d_u\right\}x\\
&=\sum_{u\in I}\ell_u(x)\\
&\quad+\lambda\left\{\lvert A(I,J\setminus I)\rvert-\lvert A(J^c,I)\rvert\right\}x.
\end{aligned} Φ I , J ( λ ) ( x ) = u ∈ I ∑ ℓ u ( x ) + 2 λ { C I , J + u ∈ I ∑ d u } x = u ∈ I ∑ ℓ u ( x ) + λ { ∣ A ( I , J ∖ I )∣ − ∣ A ( J c , I )∣ } x .
Accordingly, for i ∈ I ⊆ J ⊆ V i\in I\subseteq J\subseteq V i ∈ I ⊆ J ⊆ V , define
Ψ I , J ( x ) = ∑ u ∈ I ℓ u ( x ) + λ { ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } x , Q I , J = r + ( Ψ I , J ) ∈ [ − ∞ , + ∞ ] , μ J = max I ⊆ J i ∈ I Q I , J . (64) \begin{aligned}
\Psi_{I,J}(x)
&=\sum_{u\in I}\ell_u(x)\\
&\quad+\lambda\left\{\lvert A(I,J\setminus I)\rvert-\lvert A(J^c,I)\rvert\right\}x,\\
Q_{I,J}&=r_+(\Psi_{I,J})\in[-\infty,+\infty],\\
\mu_J&=\max_{\substack{I\subseteq J\\i\in I}}Q_{I,J}. \tag*{(64)}
\end{aligned} Ψ I , J ( x ) Q I , J μ J = u ∈ I ∑ ℓ u ( x ) + λ { ∣ A ( I , J ∖ I )∣ − ∣ A ( J c , I )∣ } x , = r + ( Ψ I , J ) ∈ [ − ∞ , + ∞ ] , = I ⊆ J i ∈ I max Q I , J . (64)
With this notation, (63) becomes
t = min J ⊆ V i ∈ J μ J = min J ⊆ V i ∈ J max I ⊆ J i ∈ I Q I , J . (65) t=\min_{\substack{J\subseteq V\\i\in J}}\mu_J
=\min_{\substack{J\subseteq V\\i\in J}}\max_{\substack{I\subseteq J\\i\in I}}Q_{I,J}. \tag*{(65)} t = J ⊆ V i ∈ J min μ J = J ⊆ V i ∈ J min I ⊆ J i ∈ I max Q I , J . (65)
This is the counterpart of (43) : under squared loss, Q I , J = y ˉ I − λ { ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } / ∣ I ∣ Q_{I,J}=\bar y_I-\lambda\{\lvert A(I,J\setminus I)\rvert-\lvert A(J^c,I)\rvert\}/\lvert I\rvert Q I , J = y ˉ I − λ {∣ A ( I , J ∖ I )∣ − ∣ A ( J c , I )∣} / ∣ I ∣ . The minima and maxima in (65) are taken over finite collections of extended real numbers, so they are attained. Individual values Q I , J Q_{I,J} Q I , J may be infinite, but the left-hand side t t t is finite.
In the squared-loss proof, (43) was simplified by comparing its terms with y max y_{\max} y m a x and y min y_{\min} y m i n . Here we compare the terms Q I , J Q_{I,J} Q I , J with the value t t t itself, through the sign of a one-sided derivative of Ψ I , J \Psi_{I,J} Ψ I , J at t t t and Lemma 4.1 . Since one-sided derivatives are additive, for every i ∈ I ⊆ J i\in I\subseteq J i ∈ I ⊆ J ,
Ψ I , J , ± ′ ( t ) = ∑ u ∈ I ℓ u , ± ′ ( t ) + λ { ∣ A ( I , J ∖ I ) ∣ − ∣ A ( J c , I ) ∣ } . (66) \Psi'_{I,J,\pm}(t)=\sum_{u\in I}\ell'_{u,\pm}(t)
+\lambda\left\{\lvert A(I,J\setminus I)\rvert-\lvert A(J^c,I)\rvert\right\}. \tag*{(66)} Ψ I , J , ± ′ ( t ) = u ∈ I ∑ ℓ u , ± ′ ( t ) + λ { ∣ A ( I , J ∖ I )∣ − ∣ A ( J c , I )∣ } . (66)
and, by the definition of M M M ,
∣ ∑ u ∈ I ℓ u , ± ′ ( t ) ∣ ≤ ∣ I ∣ M ≤ ∣ V ∣ M < λ . (67) \left\lvert\sum_{u\in I}\ell'_{u,\pm}(t)\right\rvert\leq\lvert I\rvert M\leq\lvert V\rvert M<\lambda. \tag*{(67)} u ∈ I ∑ ℓ u , ± ′ ( t ) ≤ ∣ I ∣ M ≤ ∣ V ∣ M < λ . (67)
Step 1: Restricting the outer minimum to lower sets.
Let J ∋ i J\ni i J ∋ i be a set that is not lower. Then some edge of D D D enters J J J from outside, so
k : = ∣ A ( J c , J ) ∣ ≥ 1. k:=\lvert A(J^c,J)\rvert\geq1. k := ∣ A ( J c , J )∣ ≥ 1.
The choice I = J I=J I = J is admissible in the inner maximum, and A ( J , J ∖ J ) = ∅ A(J,J\setminus J)=\varnothing A ( J , J ∖ J ) = ∅ . By (66) and (67) ,
Ψ J , J , + ′ ( t ) = ∑ u ∈ J ℓ u , + ′ ( t ) − λ k ≤ ∣ V ∣ M − λ < 0. \Psi'_{J,J,+}(t)=\sum_{u\in J}\ell'_{u,+}(t)-\lambda k\leq\lvert V\rvert M-\lambda<0. Ψ J , J , + ′ ( t ) = u ∈ J ∑ ℓ u , + ′ ( t ) − λk ≤ ∣ V ∣ M − λ < 0.
The fourth assertion of Lemma 4.1 gives Q J , J > t Q_{J,J}>t Q J , J > t . Consequently,
μ J ≥ Q J , J > t for every non-lower J ⊇ i . (68) \mu_J \ge Q_{J,J}>t \quad\text{for every non-lower } J\supseteq i. \tag*{(68)} μ J ≥ Q J , J > t for every non-lower J ⊇ i . (68)
By (65) , t t t is the smallest of the values μ J \mu_J μ J , and this minimum is attained. By (68) , it is not attained at any non-lower set. Since V ∈ L i V\in\mathcal{L}_i V ∈ L i , the collection L i \mathcal{L}_i L i is nonempty, and therefore
t = min L ∈ L i μ L . t=\min_{L\in\mathcal{L}_i}\mu_L. t = L ∈ L i min μ L .
Now let L ∈ L i L\in\mathcal{L}_i L ∈ L i and i ∈ I ⊆ L i\in I\subseteq L i ∈ I ⊆ L . No edge of D D D enters L L L from L c L^c L c , so A ( L c , I ) = ∅ A(L^c,I)=\varnothing A ( L c , I ) = ∅ and
Ψ I , L ( x ) = ∑ u ∈ I ℓ u ( x ) + λ ∣ A ( I , L ∖ I ) ∣ x . \Psi_{I,L}(x)=\sum_{u\in I}\ell_u(x)+\lambda|A(I,L\setminus I)|x. Ψ I , L ( x ) = u ∈ I ∑ ℓ u ( x ) + λ ∣ A ( I , L ∖ I ) ∣ x .
We have thus shown that
t = min L ∈ L i max i ∈ I ⊆ L Q I , L , t=\min_{L\in\mathcal{L}_i}\max_{i\in I\subseteq L}Q_{I,L}, t = L ∈ L i min i ∈ I ⊆ L max Q I , L ,
Q I , L = r + ( x ↦ ∑ u ∈ I ℓ u ( x ) + λ ∣ A ( I , L ∖ I ) ∣ x ) . (69) Q_{I,L}=r_+\left(x\mapsto\sum_{u\in I}\ell_u(x)+\lambda|A(I,L\setminus I)|x\right). \tag*{(69)} Q I , L = r + ( x ↦ u ∈ I ∑ ℓ u ( x ) + λ ∣ A ( I , L ∖ I ) ∣ x ) . (69)
which is the counterpart of (44) .
Step 2: Expressing the inner maximum using upper sets.
Fix L ∈ L i L\in\mathcal{L}_i L ∈ L i . By (69) ,
μ L ≥ t . (70) \mu_L\ge t. \tag*{(70)} μ L ≥ t . (70)
Let i ∈ I ⊆ L i\in I\subseteq L i ∈ I ⊆ L be a set with
k : = ∣ A ( I , L ∖ I ) ∣ ≥ 1. k:=|A(I,L\setminus I)|\ge1. k := ∣ A ( I , L ∖ I ) ∣ ≥ 1.
By (66) with A ( L c , I ) = ∅ A(L^c,I)=\varnothing A ( L c , I ) = ∅ , and by (67) ,
Ψ I , L , − ′ ( t ) = ∑ u ∈ I ℓ u , − ′ ( t ) + λ k ≥ − ∣ V ∣ M + λ > 0. \Psi'_{I,L,-}(t)=\sum_{u\in I}\ell'_{u,-}(t)+\lambda k\ge-|V|M+\lambda>0. Ψ I , L , − ′ ( t ) = u ∈ I ∑ ℓ u , − ′ ( t ) + λk ≥ − ∣ V ∣ M + λ > 0.
The fifth assertion of Lemma 4.1 and (70) give
Q I , L < t ≤ μ L . Q_{I,L}<t\le\mu_L. Q I , L < t ≤ μ L .
Hence no set I I I with A ( I , L ∖ I ) ≠ ∅ A(I,L\setminus I)\ne\varnothing A ( I , L ∖ I ) = ∅ attains the inner maximum μ L \mu_L μ L . The set I = L I=L I = L satisfies A ( L , L ∖ L ) = ∅ A(L,L\setminus L)=\varnothing A ( L , L ∖ L ) = ∅ , so the remaining collection is nonempty, and
μ L = max { Q I , L : i ∈ I ⊆ L , A ( I , L ∖ I ) = ∅ } . \mu_L=\max\{Q_{I,L}:i\in I\subseteq L,\ A(I,L\setminus I)=\varnothing\}. μ L = max { Q I , L : i ∈ I ⊆ L , A ( I , L ∖ I ) = ∅ } .
For every such I I I , the linear term of Ψ I , L \Psi_{I,L} Ψ I , L vanishes, so that, by (33) ,
Q I , L = r + ( x ↦ ∑ u ∈ I ℓ u ( x ) ) = q I + . Q_{I,L}=r_+\left(x\mapsto\sum_{u\in I}\ell_u(x)\right)=q_I^+. Q I , L = r + ( x ↦ u ∈ I ∑ ℓ u ( x ) ) = q I + .
It remains to identify the surviving sets. This is a statement about the DAG D D D alone, and it was established in Step 2 of the proof of Lemma Lemma 1.5:
{ I : i ∈ I ⊆ L , A ( I , L ∖ I ) = ∅ } = { L ∩ U : U ∈ U i } . \left\{ I : i \in I \subseteq L,\ A(I,L\setminus I)=\varnothing\right\}
= \left\{ L\cap U : U\in\mathcal{U}_i \right\}. { I : i ∈ I ⊆ L , A ( I , L ∖ I ) = ∅ } = { L ∩ U : U ∈ U i } .
Therefore
μ L = max U ∈ U i q L ∩ U + for every L ∈ L i , \mu_L=\max_{U\in\mathcal{U}_i}q^+_{L\cap U}
\qquad\text{for every }L\in\mathcal{L}_i, μ L = U ∈ U i max q L ∩ U + for every L ∈ L i ,
and substituting this into t = min L ∈ L i μ L t=\min_{L\in\mathcal{L}_i}\mu_L t = min L ∈ L i μ L gives
θ ^ i i s o = min L ∈ L i max U ∈ U i q L ∩ U + . (71) \widehat{\theta}^{\mathrm{iso}}_i
=\min_{L\in\mathcal{L}_i}\max_{U\in\mathcal{U}_i}q^+_{L\cap U}. \tag*{(71)} θ i iso = L ∈ L i min U ∈ U i max q L ∩ U + . (71)
This is (35) , and the counterpart of (45) . The right-hand side is finite, since the left-hand side is.
Step 3: The maxmin identity. The preceding argument used only the standing assumptions. Hence (71) holds for every vertex of every finite DAG and every family of finite, convex, coercive losses. We apply it to a reflected problem, as in Step 3 of the proof of Lemma Lemma 1.5.
Let D r e v = ( V , A r e v ) D^{\mathrm{rev}}=(V,A^{\mathrm{rev}}) D rev = ( V , A rev ) , with A r e v = { ( v , u ) : ( u , v ) ∈ A } A^{\mathrm{rev}}=\{(v,u):(u,v)\in A\} A rev = {( v , u ) : ( u , v ) ∈ A } , be obtained by reversing every edge of D D D , and let
ℓ ~ u ( x ) = ℓ u ( − x ) , f ~ ( θ ) = ∑ u ∈ V ℓ ~ u ( θ u ) = f ( − θ ) . \widetilde{\ell}_u(x)=\ell_u(-x),\qquad
\widetilde{f}(\theta)=\sum_{u\in V}\widetilde{\ell}_u(\theta_u)=f(-\theta). ℓ u ( x ) = ℓ u ( − x ) , f ( θ ) = u ∈ V ∑ ℓ u ( θ u ) = f ( − θ ) .
The reflected losses remain finite, convex, and coercive. Since K D r e v = − K D \mathcal{K}_{D^{\mathrm{rev}}}=-\mathcal{K}_D K D rev = − K D , the reflected solution set is − S i s o -\mathcal{S}_{\mathrm{iso}} − S iso , with upper endpoint − θ ^ i i s o -\widehat{\theta}^{\mathrm{iso}}_i − θ i iso at coordinate i i i . Reversing the edges interchanges lower and upper sets. Moreover, for nonempty B ⊆ V B\subseteq V B ⊆ V , the sixth assertion of Lemma Lemma 4.1 gives
r + ( x ↦ ∑ u ∈ B ℓ ~ u ( x ) ) = − r − ( ∑ u ∈ B ℓ u ) = − q B − . r_+\left(x\mapsto\sum_{u\in B}\widetilde{\ell}_u(x)\right)
=-r_-\left(\sum_{u\in B}\ell_u\right)
=-q^-_B. r + ( x ↦ u ∈ B ∑ ℓ u ( x ) ) = − r − ( u ∈ B ∑ ℓ u ) = − q B − .
Applying (71) to the reflected problem therefore gives
− θ ^ i i s o = min U ∈ U i max L ∈ L i ( − q L ∩ U − ) . -\widehat{\theta}^{\mathrm{iso}}_i
=\min_{U\in\mathcal{U}_i}\max_{L\in\mathcal{L}_i}(-q^-_{L\cap U}). − θ i iso = U ∈ U i min L ∈ L i max ( − q L ∩ U − ) .
Negating both sides exchanges minimum and maximum:
θ ^ i i s o = max U ∈ U i min L ∈ L i q L ∩ U − . \widehat{\theta}^{\mathrm{iso}}_i
=\max_{U\in\mathcal{U}_i}\min_{L\in\mathcal{L}_i}q^-_{L\cap U}. θ i iso = U ∈ U i max L ∈ L i min q L ∩ U − .
This is (34) , which completes the proof of part (ii).
Part (iii): Lattice structure and simultaneous attainment. Let θ , η ∈ S i s o \theta,\eta\in\mathcal{S}_{\mathrm{iso}} θ , η ∈ S iso . We first show that θ ∧ η \theta\wedge\eta θ ∧ η and θ ∨ η \theta\vee\eta θ ∨ η belong to K D \mathcal{K}_D K D . For every ( u , v ) ∈ A (u,v)\in A ( u , v ) ∈ A , we have θ u ≤ θ v \theta_u\leq\theta_v θ u ≤ θ v and η u ≤ η v \eta_u\leq\eta_v η u ≤ η v , and therefore
min { θ u , η u } ≤ min { θ v , η v } , \min\{\theta_u,\eta_u\}\leq\min\{\theta_v,\eta_v\}, min { θ u , η u } ≤ min { θ v , η v } ,
max { θ u , η u } ≤ max { θ v , η v } . \max\{\theta_u,\eta_u\}\leq\max\{\theta_v,\eta_v\}. max { θ u , η u } ≤ max { θ v , η v } .
Next, for every u ∈ V u \in V u ∈ V , the pair ( min { θ u , η u } , max { θ u , η u } ) (\min\{\theta_u,\eta_u\},\max\{\theta_u,\eta_u\}) ( min { θ u , η u } , max { θ u , η u }) is a rearrangement of ( θ u , η u ) (\theta_u,\eta_u) ( θ u , η u ) . Summing ℓ u \ell_u ℓ u over both entries and then over u ∈ V u \in V u ∈ V gives
f ( θ ∧ η ) + f ( θ ∨ η ) = f ( θ ) + f ( η ) = 2 f ∗ . f(\theta\wedge\eta) + f(\theta\vee\eta) = f(\theta) + f(\eta) = 2f^{*}. f ( θ ∧ η ) + f ( θ ∨ η ) = f ( θ ) + f ( η ) = 2 f ∗ .
Since both θ ∧ η \theta\wedge\eta θ ∧ η and θ ∨ η \theta\vee\eta θ ∨ η lie in K D \mathcal{K}_D K D , each term on the left is at least f ∗ f^{*} f ∗ . Hence both terms equal f ∗ f^{*} f ∗ , that is, θ ∧ η , θ ∨ η ∈ S i s o \theta\wedge\eta,\theta\vee\eta\in S_{\mathrm{iso}} θ ∧ η , θ ∨ η ∈ S iso . This proves that S i s o S_{\mathrm{iso}} S iso is a lattice.
By part (i), for each j ∈ V j \in V j ∈ V we can choose θ j , − , θ j , + ∈ S i s o \theta^{j,-},\theta^{j,+} \in S_{\mathrm{iso}} θ j , − , θ j , + ∈ S iso with
θ j j , − = θ ^ j i s o , θ j j , + = θ ‾ j i s o . \theta_j^{j,-} = \widehat{\theta}^{\mathrm{iso}}_j,\qquad\theta_j^{j,+} = \overline{\theta}^{\mathrm{iso}}_j. θ j j , − = θ j iso , θ j j , + = θ j iso .
Since V V V is finite, applying the lattice property finitely many times gives
θ − : = ⋀ j ∈ V θ j , − ∈ S i s o , θ + : = ⋁ j ∈ V θ j , + ∈ S i s o . \theta^{-} := \bigwedge_{j \in V} \theta^{j,-} \in S_{\mathrm{iso}},\qquad\theta^{+} := \bigvee_{j \in V} \theta^{j,+} \in S_{\mathrm{iso}}. θ − := j ∈ V ⋀ θ j , − ∈ S iso , θ + := j ∈ V ⋁ θ j , + ∈ S iso .
Fix u ∈ V u \in V u ∈ V . On the one hand, θ u − ≤ θ u u , − = θ ^ u i s o \theta_u^{-} \le\theta_u^{u,-} = \widehat{\theta}^{\mathrm{iso}}_u θ u − ≤ θ u u , − = θ u iso . On the other hand, θ − ∈ S i s o \theta^{-} \in S_{\mathrm{iso}} θ − ∈ S iso , so θ u − ≥ θ ^ u i s o \theta_u^{-} \ge\widehat{\theta}^{\mathrm{iso}}_u θ u − ≥ θ u iso by the definition of θ ^ u i s o \widehat{\theta}^{\mathrm{iso}}_u θ u iso . Thus θ − = θ ^ i s o \theta^{-} = \widehat{\theta}^{\mathrm{iso}} θ − = θ iso , and in the same way θ + = θ ‾ i s o \theta^{+} = \overline{\theta}^{\mathrm{iso}} θ + = θ iso . Consequently, θ ^ i s o \widehat{\theta}^{\mathrm{iso}} θ iso and θ ‾ i s o \overline{\theta}^{\mathrm{iso}} θ iso belong to S i s o S_{\mathrm{iso}} S iso , and by the definition of the coordinate endpoints every θ ∈ S i s o \theta\in S_{\mathrm{iso}} θ ∈ S iso satisfies θ ^ u i s o ≤ θ u ≤ θ ‾ u i s o \widehat{\theta}^{\mathrm{iso}}_u \le\theta_u \le\overline{\theta}^{\mathrm{iso}}_u θ u iso ≤ θ u ≤ θ u iso for all u ∈ V u \in V u ∈ V . They are therefore the coordinatewise smallest and largest solutions, which proves part (iii).
Part (iv): Uniqueness under strict convexity. Suppose that f f f is strictly convex on K D \mathcal{K}_D K D , and let θ ≠ η \theta\ne\eta θ = η be two elements of S i s o S_{\mathrm{iso}} S iso . Their midpoint ( θ + η ) / 2 (\theta+\eta)/2 ( θ + η ) /2 belongs to the convex set K D \mathcal{K}_D K D , and strict convexity gives
f ( θ + η 2 ) < f ( θ ) + f ( η ) 2 = f ∗ . f\left(\frac{\theta+\eta}{2}\right) < \frac{f(\theta)+f(\eta)}{2} = f^{*}. f ( 2 θ + η ) < 2 f ( θ ) + f ( η ) = f ∗ .
contradicting the definition of f ∗ f^{*} f ∗ . Hence S i s o S_{\mathrm{iso}} S iso , which is nonempty by part (i), consists of a single vector, and θ ^ i s o = θ ‾ i s o \widehat{\theta}^{\mathrm{iso}} = \overline{\theta}^{\mathrm{iso}} θ iso = θ iso by part (iii). Finally, if every ℓ u \ell_u ℓ u is strictly convex, then f f f is strictly convex on R V \mathbb{R}^{V} R V : for θ ≠ η \theta\ne\eta θ = η , the strict inequality holds in at least one coordinate and the weak inequality in all others. In particular, f f f is strictly convex on K D \mathcal{K}_D K D . This proves part (iv).
Proofs of Auxiliary Facts
Proof of Remark 5
Suppose the set of minimizers of h h h is non-empty. Due to convexity, the set of minimizers of h h h has to be a convex set in R \mathbb{R} R . To see this, note that for any minimizers x 1 ≤ x 2 x_1 \le x_2 x 1 ≤ x 2 and any α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] , convexity gives
h ( α x 1 + ( 1 − α ) x 2 ) ≤ α h ( x 1 ) + ( 1 − α ) h ( x 2 ) = min x ∈ R h ( x ) . h\left(\alpha x_1 + (1-\alpha)x_2\right) \le\alpha h(x_1) + (1-\alpha)h(x_2) = \min_{x \in\mathbb{R}} h(x). h ( α x 1 + ( 1 − α ) x 2 ) ≤ α h ( x 1 ) + ( 1 − α ) h ( x 2 ) = x ∈ R min h ( x ) .
Now, any convex set in R \mathbb{R} R is an interval, possibly unbounded or a singleton. Moreover, the set of minimizers is closed due to continuity of h h h . This proves first part of the remark.
Now, suppose the set of minimizers of h h h is bounded. The minimizer set is also closed, so it is compact. Let us denote this interval as [ m , M ] [m,M] [ m , M ] . Now, it holds that x ∈ R x \in\mathbb{R} x ∈ R minimizes the convex map h h h , if and only if
h − ′ ( x ) ≤ 0 ≤ h + ′ ( x ) . h'_{-}(x) \le0 \le h'_{+}(x). h − ′ ( x ) ≤ 0 ≤ h + ′ ( x ) .
This follows easily from the subdifferential characterization in (49) and the associated optimality conditions. Therefore h − ′ ( m ) ≤ 0 ≤ h + ′ ( m ) h'_{-}(m) \le0 \le h'_{+}(m) h − ′ ( m ) ≤ 0 ≤ h + ′ ( m ) , and for any ϵ > 0 \epsilon> 0 ϵ > 0 , due to monotonicity of one-sided derivative of convex map h h h , we have
h − ′ ( m − ϵ ) ≤ h − ′ ( m ) ≤ 0. h'_{-}(m-\epsilon) \le h'_{-}(m) \le0. h − ′ ( m − ϵ ) ≤ h − ′ ( m ) ≤ 0.
If h + ′ ( m − ϵ ) ≥ 0 h'_{+}(m-\epsilon) \ge0 h + ′ ( m − ϵ ) ≥ 0 , then it would imply that m − ϵ m-\epsilon m − ϵ also minimizes h h h , which contradicts the definition of m m m . Therefore in this case,
m = min { t : h + ′ ( t ) ≥ 0 } = r − ( h ) . m = \min\{t : h'_{+}(t) \ge0\} = r_{-}(h). m = min { t : h + ′ ( t ) ≥ 0 } = r − ( h ) .
It can be similarly proved that M = max { t : h − ′ ( t ) ≤ 0 } = r + ( h ) M = \max\{t : h'_{-}(t) \le0\} = r_{+}(h) M = max { t : h − ′ ( t ) ≤ 0 } = r + ( h ) . □ \square □
Proof of Remark 9
Suppose F λ ( θ ) ≤ M F_{\lambda}(\theta) \le M F λ ( θ ) ≤ M , where M ≥ 0 M \ge0 M ≥ 0 . Since all loss terms and the TV penalty are nonnegative, each loss is at most M M M , and TV G ( θ ) ≤ M / λ \operatorname{TV}_{G}(\theta) \le M/\lambda TV G ( θ ) ≤ M / λ . For any vertices u , v u,v u , v , connectedness provides a simple path from u u u to v v v . Applying the triangle inequality along this path gives
∣ θ u − θ v ∣ ≤ TV G ( θ ) ≤ M / λ . |\theta_u-\theta_v| \le\operatorname{TV}_{G}(\theta) \le M/\lambda. ∣ θ u − θ v ∣ ≤ TV G ( θ ) ≤ M / λ .
Thus the TV penalty bounds the difference between any two coordinates.
Choose vertices a , b a,b a , b with y a = 0 y_a=0 y a = 0 and y b = 1 y_b=1 y b = 1 . The loss at a a a satisfies
M ≥ ℓ a ( θ a ) = log ( 1 + e θ a ) ≥ θ a , M \ge\ell_a(\theta_a) = \log(1+e^{\theta_a}) \ge\theta_a, M ≥ ℓ a ( θ a ) = log ( 1 + e θ a ) ≥ θ a ,
so θ a ≤ M \theta_a \le M θ a ≤ M . Consequently, for every u ∈ V u \in V u ∈ V ,
θ u ≤ θ a + ∣ θ u − θ a ∣ ≤ M + M / λ . \theta_u \le\theta_a + |\theta_u-\theta_a| \le M+M/\lambda. θ u ≤ θ a + ∣ θ u − θ a ∣ ≤ M + M / λ .
Similarly, the loss at b b b satisfies
M ≥ ℓ b ( θ b ) = log ( 1 + e − θ b ) ≥ − θ b , M \ge\ell_b(\theta_b) = \log(1+e^{-\theta_b}) \ge-\theta_b, M ≥ ℓ b ( θ b ) = log ( 1 + e − θ b ) ≥ − θ b ,
so θ b ≥ − M \theta_b \ge-M θ b ≥ − M , and hence
θ u ≥ θ b − ∣ θ u − θ b ∣ ≥ − M − M / λ . \theta_u \ge\theta_b-|\theta_u-\theta_b| \ge-M-M/\lambda. θ u ≥ θ b − ∣ θ u − θ b ∣ ≥ − M − M / λ .
Therefore every sublevel set of F λ F_{\lambda} F λ is bounded, proving coercivity. The losses are finite and convex, so Theorem 1.6 applies.
Finally, each logistic loss is strictly convex, since
ℓ u ′ ′ ( t ) = e t ( 1 + e t ) 2 > 0 for every t ∈ R . \ell''_{u}(t)=\frac{e^t}{(1+e^t)^2}>0 \qquad\text{for every } t\in\mathbb{R}. ℓ u ′′ ( t ) = ( 1 + e t ) 2 e t > 0 for every t ∈ R .
Their separable sum is therefore strictly convex on R V \mathbb{R}^{V} R V . Adding the convex TV penalty preserves strict convexity, so F λ F_{\lambda} F λ has a unique minimizer. □ \square □
Proof of Lemma 4.1
Recall from (23) that
r + ( h ) = sup { x : h − ′ ( x ) ≤ 0 } , r − ( h ) = inf { x : h + ′ ( x ) ≥ 0 } . r_{+}(h)=\sup\{x:h'_{-}(x)\le0\},\qquad
r_{-}(h)=\inf\{x:h'_{+}(x)\ge0\}. r + ( h ) = sup { x : h − ′ ( x ) ≤ 0 } , r − ( h ) = inf { x : h + ′ ( x ) ≥ 0 } .
By Rockafellar [20 ] , h − ′ h'_{-} h − ′ and h + ′ h'_{+} h + ′ are finite and nondecreasing on R \mathbb{R} R , and
lim z ↓ t h − ′ ( z ) = h + ′ ( t ) , lim z ↑ t h + ′ ( z ) = h − ′ ( t ) . (72) \lim_{z\downarrow t}h'_{-}(z)=h'_{+}(t),\qquad
\lim_{z\uparrow t}h'_{+}(z)=h'_{-}(t). \tag*{(72)} z ↓ t lim h − ′ ( z ) = h + ′ ( t ) , z ↑ t lim h + ′ ( z ) = h − ′ ( t ) . (72)
If h − ′ ( t ) ≤ 0 h'_{-}(t)\le0 h − ′ ( t ) ≤ 0 , then t t t belongs to the set { x : h − ′ ( x ) ≤ 0 } \{x:h'_{-}(x)\le0\} { x : h − ′ ( x ) ≤ 0 } , whose supremum is r + ( h ) r_{+}(h) r + ( h ) .
If r + ( h ) > t r_{+}(h)>t r + ( h ) > t , the definition of the supremum gives a point s > t s>t s > t with h − ′ ( s ) ≤ 0 h'_{-}(s)\le0 h − ′ ( s ) ≤ 0 . Fix any 0 < ε < s − t 0<\varepsilon<s-t 0 < ε < s − t . We will use the secant inequality for real-valued convex maps: for a < b < c a<b<c a < b < c ,
h ( b ) − h ( a ) b − a ≤ h ( c ) − h ( a ) c − a ≤ h ( c ) − h ( b ) c − b . \frac{h(b)-h(a)}{b-a}\le\frac{h(c)-h(a)}{c-a}\le\frac{h(c)-h(b)}{c-b}. b − a h ( b ) − h ( a ) ≤ c − a h ( c ) − h ( a ) ≤ c − b h ( c ) − h ( b ) .
It follows from the secant-inequality that for any 0 < δ < ε 0<\delta<\varepsilon 0 < δ < ε ,
h ( t + ε ) − h ( t ) ε ≤ h ( t + ε ) − h ( t + δ ) ε − δ . \frac{h(t+\varepsilon)-h(t)}{\varepsilon}\le\frac{h(t+\varepsilon)-h(t+\delta)}{\varepsilon-\delta}. ε h ( t + ε ) − h ( t ) ≤ ε − δ h ( t + ε ) − h ( t + δ ) .
Taking δ ↑ ε \delta\uparrow\varepsilon δ ↑ ε , the RHS converges to h − ′ ( t + ε ) h'_{-}(t+\varepsilon) h − ′ ( t + ε ) . Therefore, using the monotonicity of h − ′ h'_{-} h − ′ , we get
h ( t + ε ) − h ( t ) ε ≤ h − ′ ( t + ε ) ≤ h − ′ ( s ) ≤ 0. \frac{h(t+\varepsilon)-h(t)}{\varepsilon}\le h'_{-}(t+\varepsilon)\le h'_{-}(s)\le0. ε h ( t + ε ) − h ( t ) ≤ h − ′ ( t + ε ) ≤ h − ′ ( s ) ≤ 0.
Fix ε > 0 \varepsilon>0 ε > 0 . We need to show that h ( x + ε ) − h ( x ) ≤ h ( y + ε ) − h ( y ) h(x+\varepsilon)-h(x)\le h(y+\varepsilon)-h(y) h ( x + ε ) − h ( x ) ≤ h ( y + ε ) − h ( y ) whenever x ≤ y x\le y x ≤ y , the case x = y x=y x = y being trivial. First, consider the case x < y < x + ε x<y<x+\varepsilon x < y < x + ε . Applying the secant inequality to x < y < x + ε x<y<x+\varepsilon x < y < x + ε , and then to y < x + ε < y + ε y<x+\varepsilon<y+\varepsilon y < x + ε < y + ε , gives
h ( x + ε ) − h ( x ) ε ≤ h ( x + ε ) − h ( y ) x + ε − y ≤ h ( y + ε ) − h ( y ) ε . \frac{h(x+\varepsilon)-h(x)}{\varepsilon}\le\frac{h(x+\varepsilon)-h(y)}{x+\varepsilon-y}\le\frac{h(y+\varepsilon)-h(y)}{\varepsilon}. ε h ( x + ε ) − h ( x ) ≤ x + ε − y h ( x + ε ) − h ( y ) ≤ ε h ( y + ε ) − h ( y ) .
Next, consider the case x + ε < y x+\varepsilon<y x + ε < y . Applying the secant inequality to x < x + ε < y x<x+\varepsilon<y x < x + ε < y , and then to x + ε < y < y + ε x+\varepsilon<y<y+\varepsilon x + ε < y < y + ε , gives
h ( x + ε ) − h ( x ) ε ≤ h ( y ) − h ( x + ε ) y − x − ε ≤ h ( y + ε ) − h ( y ) ε . \frac{h(x+\varepsilon)-h(x)}{\varepsilon}\le\frac{h(y)-h(x+\varepsilon)}{y-x-\varepsilon}\le\frac{h(y+\varepsilon)-h(y)}{\varepsilon}. ε h ( x + ε ) − h ( x ) ≤ y − x − ε h ( y ) − h ( x + ε ) ≤ ε h ( y + ε ) − h ( y ) .
Finally, if y = x + ε y=x+\varepsilon y = x + ε , the secant inequality applied to x < x + ε < x + 2 ε x<x+\varepsilon<x+2\varepsilon x < x + ε < x + 2 ε gives the claim directly.
In every case the two extreme terms yield
h ( x + ε ) − h ( x ) ≤ h ( y + ε ) − h ( y ) , h(x+\varepsilon)-h(x)\le h(y+\varepsilon)-h(y), h ( x + ε ) − h ( x ) ≤ h ( y + ε ) − h ( y ) ,
as desired.
If h + ′ ( t ) < 0 h'_{+}(t)<0 h + ′ ( t ) < 0 , the first limit in (72) gives a point s > t s>t s > t with h − ′ ( s ) < 0 h'_{-}(s)<0 h − ′ ( s ) < 0 . Then s ∈ { x : h − ′ ( x ) ≤ 0 } s\in\{x:h'_{-}(x)\le0\} s ∈ { x : h − ′ ( x ) ≤ 0 } , so r + ( h ) ≥ s > t r_{+}(h)\ge s>t r + ( h ) ≥ s > t .
If h − ′ ( t ) > 0 h'_{-}(t) > 0 h − ′ ( t ) > 0 , the second limit in (72) gives a point s < t s < t s < t with h − ′ ( s ) > 0 h'_{-}(s) > 0 h − ′ ( s ) > 0 . Since h − ′ h'_{-} h − ′ is nondecreasing, h − ′ ( x ) > 0 h'_{-}(x) > 0 h − ′ ( x ) > 0 for every x ≥ s x \ge s x ≥ s . Thus { x : h − ′ ( x ) ≤ 0 } ⊆ ( − ∞ , s ) \{x : h'_{-}(x) \le0\} \subseteq(-\infty,s) { x : h − ′ ( x ) ≤ 0 } ⊆ ( − ∞ , s ) , and r + ( h ) ≤ s < t r_{+}(h) \le s < t r + ( h ) ≤ s < t ; if the set is empty, r + ( h ) = − ∞ < t r_{+}(h) = -\infty< t r + ( h ) = − ∞ < t .
For every x ∈ R x \in\mathbb{R} x ∈ R ,
h ~ − ′ ( x ) = lim ε ↓ 0 h ( − x ) − h ( − x + ε ) ε = − h + ′ ( − x ) . \widetilde{h}'_{-}(x) = \lim_{\varepsilon\downarrow0} \frac{h(-x) - h(-x+\varepsilon)}{\varepsilon} = -h'_{+}(-x). h − ′ ( x ) = ε ↓ 0 lim ε h ( − x ) − h ( − x + ε ) = − h + ′ ( − x ) .
Therefore, substituting s = − x s=-x s = − x ,
r + ( h ~ ) = sup { x : h + ′ ( − x ) ≥ 0 } = − inf { s : h + ′ ( s ) ≥ 0 } = − r − ( h ) , r_{+}(\widetilde{h}) = \sup\{x : h'_{+}(-x) \ge0\}
= -\inf\{s : h'_{+}(s) \ge0\} = -r_{-}(h), r + ( h ) = sup { x : h + ′ ( − x ) ≥ 0 } = − inf { s : h + ′ ( s ) ≥ 0 } = − r − ( h ) ,
where the conventions sup ∅ = − ∞ \sup\varnothing= -\infty sup ∅ = − ∞ and inf ∅ = + ∞ \inf\varnothing= +\infty inf ∅ = + ∞ are consistent with each other. □
Acknowledgement
Sabyasachi Chatterjee thanks Ashwin Pananjady for a conversation which initiated this research.