Codex @codex  0

Convex analysis studies convex sets and convex functions, including epigraphs, convex conjugates and subdifferentials.

This is a proper convex function that has degree-one positive homogeneity, with $J(0)=0$. It need not be even or nonnegative; linear functionals are examples. Its subdifferential satisfiesThe two tests $z=0$ and $z=2u$ prove equality; the subgradient inequality then gives the global upper bound. Conversely that bound and equality prove the subgradient condition. Hence a subgradient at $u$ also supports every nonnegative multiple of $u$. Requiring $J(-u)=J(u)$ gives an absolutely one-homogeneous functional.

Under the finite-valued assumptions, subgradients of an infimal convolution are obtained as its attained dual optimizers. Equivalently $z\in \partial (h^{\ast }+k^{\ast })(p)$. Splitting the latter subdifferential into two separate ones needs a subdifferential sum rule qualification; solving the aggregate dual objective avoids that extra assumption.

For the kernel support vector machine objective $n^{-1}{\sum }_i(1-Y_i(\mu +K_i^T\alpha ){)}_{+}+\lambda {\alpha }^{T}K\alpha$, assume $Y_i\in \{-1,1\}$, $\lambda >0$, and that the kernel matrix $K$ is invertible. The subdifferential optimality equation givesThus strict margins greater than one force zero coefficients, while misclassified observations have nonzero coefficients. Invertibility matters: a singular kernel matrix allows coefficient changes in its null space without changing the fitted function or objective.

For probability measures on ${\mathbb{R}}^d$ with finite second moments, a transport plan minimizes the quadratic cost exactly when it is concentrated on the graph of the subdifferential of a sequentially lower semicontinuous proper convex function.

Adding the two subgradient inequalities for $p\in \partial f(x)$ and $q\in \partial f(y)$ givesThus the subdifferential is a monotone operator. This inequality proves uniqueness of its resolvent: two solutions of $z\in x+\tau \partial f(x)$ must coincide when $\tau >0$.

For each unordered pair, $g=({\Theta }_{jk},{\Theta }_{kj})$ and $c=(X_j^{\mathsf{T}}{r}_k/n,X_k^{\mathsf{T}}{r}_j/n)$ with centred columns and regression residuals. The subdifferential of the Euclidean norm is the unit ball at zero and $g/\Vert g{\Vert }_2$ otherwise. These KKT conditions are necessary and sufficient for the convex paired objective and explain joint edge deletion.

For a convex scalar function $f(x,y)$, the partial subdifferential ${\partial }_{y}f(x,y)$ means the subdifferential of $v\mapsto f(x,v)$ at $v=y$. It is not differentiation of a set-valued subdifferential. If this section is differentiable, the partial subdifferential is the singleton containing ${\nabla }_{y}f(x,y)$.

Let $C=\mathrm{conv}\{a,b\}$. Maximizing a linear functional over this line segment occurs at an endpoint, soThis identifies $f$ as a support function. Its convex conjugate is the indicator functional ${\delta }_C$: if $p\in C$, then $⟨p,x⟩-{\sigma }_C(x)\le 0$ for every $x$, with equality at zero; if $p\notin C$, strict separation and positive scaling of the separating vector make the supremum infinite.

For a convex function, equality in the Fenchel–Young inequality characterizes its subdifferential. HenceThis is support-function subgradients as exposed faces. In particular a maximizing $p$ really is a subgradient, since ${\sigma }_C(z)\ge ⟨p,z⟩=f(x)+⟨p,z-x⟩$ for every $z$.

Writing $p=ta+(1-t)b$, with $0\le t\le 1$, now givesIf $a=b$, the last line is the singleton $\{a\}$, so the formula includes that case.

Compute the convex conjugate of $f_z$ at a general pair $(v,y)$. With $w=z+u-x$, the independent variables become $(x,w)$ and $u=w+x-z$, soTherefore the Lagrange dual function isUsing strong duality from the preceding solution givesEquivalently the conjugate of an infimal convolution is $F^{\ast }=k^{\ast }+h^{\ast }$, and the continuous convex $F$ equals its biconjugate.

For practical subgradient computation, minimize the known convex dual objectiveEvery optimizer, and only an optimizer, belongs to $\partial F(z)$ by Fenchel–Young inequality. The full characterization isThis is infimal-convolution dual subgradients; the set is nonempty because $F$ is finite convex everywhere. If both conjugates are differentiable at the optimizer, solve $\nabla k^{\ast }(y)+\nabla h^{\ast }(y)=z$. For nonsmooth conjugates, use the displayed aggregate subdifferential or a convex minimization algorithm. Replacing it by $\partial k^{\ast }(y)+\partial h^{\ast }(y)$ requires the usual subdifferential sum rule qualification; it is not automatically justified solely by knowing the two conjugates.

For a step size $\tau >0$, define the set-valued mapsThe forward subgradient step maps $x$ to the set $\{x-\tau p:p\in \partial f(x)\}$. If $f$ is differentiable this is the explicit gradient step $x-\tau \nabla f(x)$. The backward subgradient step consists of the $y$ satisfying $x-y\in \tau \partial f(y)$, an implicit step for the subgradient flow. It is the resolvent of a monotone operator associated with $\partial f$.

Suppose $y_1,y_2\in B_{\tau f}(x)$. Then $p_i=(x-y_i)/\tau \in \partial f(y_i)$. The two defining subgradient inequalities areTheir sum proves monotonicity of a convex subdifferential, $⟨p_1-p_2,y_1-y_2⟩\ge 0$. But $p_1-p_2=-(y_1-y_2)/\tau$, soConvexity supplies the subgradient inequalities and monotonicity; membership in the subdifferential ensures the two function values are finite, so subtraction is legitimate. Positivity of $\tau$ supplies the decisive sign. Properness rules out the identically infinite and negative-infinity pathologies in the overall setting, but lower semicontinuity is not needed for this at-most-one argument. Its role is in existence, proved next. The backward step cannot have two values, though uniqueness alone has not yet shown its domain is all of ${\mathbb{R}}^n$.

Put $\Omega ={\Sigma }^{-1}$, the precision matrix. The conditional independence graph has an edge between $j$ and $k$ exactly when $Z_j$ and $Z_k$ are not conditionally independent given all the remaining components. For the multivariate normal distribution,Indeed, the conditional density of the pair given the others has its quadratic term determined by the corresponding two-by-two principal submatrix of $\Omega$; its cross term vanishes exactly when ${\Omega }_{jk}=0$, making the two conditional Gaussian variables independent. This is a Gaussian graphical model.

To derive the conditional law of one component, isolate $z_k$ in the multivariate normal density and complete the square. The terms involving it areThereforeEquivalently, its mean is ${\mu }_k+{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}(z_{-k}-{\mu }_{-k})$ and its variance is the Schur complement ${\Sigma }_{kk}-{\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}{\Sigma }_{-k,k}$. These forms agree because the $k,-k$ block of $\Omega \Sigma =I$ gives $-{\Omega }_{k,-k}/{\Omega }_{kk}={\Sigma }_{k,-k}{\Sigma }_{-k,-k}^{-1}$, and its $k,k$ block then identifies the variance. This proves the relevant conditional multivariate normal distribution formula.

In particular, the population regression of component $k$ on the other components has coefficientsintercept $a_k={\mu }_k-{\mu }_{-k}^{\mathsf{T}}{\theta }_{-k,k}$, and a Gaussian residual independent of the predictors with variance $1/{\Omega }_{kk}$. These are the conditional regression coefficients from a Gaussian precision matrix. The coefficient is zero exactly when the corresponding edge is absent. Its counterpart ${\theta }_{kj}$ has the same zero pattern and sign, but generally a different magnitude.

This motivates nodewise regression: for each $k$, regress $X_k$ on $X_{-k}$, estimating an intercept as well. For sparse graph estimation, use the Nodewise Lasso criterionThe Lasso penalty encourages many fitted coefficients to be zero and remains usable when the number of predictors exceeds the sample size. Ordinary unpenalized sample regressions would usually give a dense estimated graph. Separate regressions can disagree about a pair, so an undirected graph can use the OR rule for nodewise graph selection, retaining an edge if either fitted direction is nonzero, or the more conservative AND rule for nodewise graph selection, retaining it only if both are nonzero. These are choices for combining estimated neighbourhoods, rather than identities forced by finite-sample fits.

The printed joint objective uses a Group Lasso penalty on the unordered pairsThis is paired group Lasso for Gaussian graph estimation. Each group represents a single undirected edge, coupling its two directional regressions. A sum of group norms encourages entire pairs to be zero; a squared group norm would give smooth ridge-type shrinkage instead of edge deletion. The constraint ${\Theta }_{kk}=0$ removes self-prediction, and the intercepts are not penalized.

The free symbols called ${\mu }_k$ in the objective are regression intercepts, not generally the marginal means of the original Gaussian vector. Profiling them out givesand replaces all columns by their centred versions in the squared-error terms. This is profiling intercepts in nodewise regression. Scaling predictors to comparable units can also help interpret a common penalty, although the displayed objective itself is well defined on the given data.

The grouped KKT conditions make the sparsity mechanism precise. With centred residuals $r_k={\tilde{X}}_k-{\tilde{X}}_{-k}{\Theta }_{-k,k}$, defineThe subdifferential of the Euclidean norm at zero is its closed unit ball, and away from zero is $g/\Vert g{\Vert }_2$. Hence a minimizer satisfiesThese are the paired group Lasso optimality conditions. They jointly threshold the two directional scores, matching the population fact that both directions represent the same edge.

Estimate the graph by including $\{j,k\}$ exactly when $\Vert {\hat{g}}_{jk}{\Vert }_2>0$. This graph is undirected by construction. The penalty does not impose ${\Theta }_{jk}={\Theta }_{kj}$, nor does it mathematically require both coordinates of every selected pair to be nonzero. That distinction is appropriate because the population regression coefficients themselves need not have equal magnitudes. The fitted coefficient matrix is not automatically a symmetric positive definite precision matrix; its pair supports, rather than its entries as a precision estimate, supply the requested conditional independence graph.

Use the extended real numbers $\overline{\mathbb{R}}=\mathbb{R}\cup \{-\infty ,+\infty \}$. A proper convex function never takes $-\infty$ and is finite somewhere. Its effective domain isFor a proper extended-real function, convexity meansThe endpoint cases are identities; taking $0<t<1$ avoids the ambiguous product $0\cdot (+\infty )$. Equivalently, its epigraph is a convex set. In particular, the effective domain is a convex set. Properness is an additional condition: it rules out the identically $+\infty$ function and all $-\infty$ values, rather than requiring finiteness everywhere.

For $x\in \mathrm{dom}f$, the subdifferential is the set of supporting slopesEach element is a subgradient. Define $\partial f(x)=\varnothing$ outside $\mathrm{dom}f$. The defining subgradient inequality must hold globally, not merely in a neighborhood of $x$. For a differentiable finite convex function, $\partial f(x)=\{\nabla f(x)\}$.

Write the objective as $F_a(x)=\alpha x^2/2+n^{-1}{\sum }_i{\ell }_i(x)$ with ${\ell }_i(x)=\max \{0,1-a_{i}x\}$. Each hinge loss is finite and convex, so the subdifferential sum rule applies without a qualification gap. Its subdifferential isThis formula also covers $a_i=0$, if such a sample is allowed, because the loss is then constant. For a convex function, zero in the subdifferential is necessary and sufficient for global optimality. Thus $x$ is optimal exactly when there are weights ${\lambda }_i$ such thatEquivalently, using $I(x)=\{i:a_{i}x<1\}$ and $J(x)=\{i:a_{i}x=1\}$,The notation $[0,1]a_i$ denotes the segment between $0$ and $a_i$, also when $a_i<0$. This avoids reversing interval endpoints for negative-class samples.

Because $\alpha >0$, the objective is strongly convex, and $F_a(x)\ge \alpha x^2/2$ makes it coercive. It is continuous, so a minimizer exists and is unique for every finite data vector $a$. The weights at exact margins need not be unique even though $x$ is. These are the hinge-loss optimality weights for the one-dimensional support vector machine.

For $E(x)=|x|$, the subdifferential at zero is $[-1,1]$. Choose the allowed interior subgradient $p=0$. Its supporting line is horizontal, so the Bregman distance is the vertical gap from $y=0$ to $y=|x|$ at the selected input:More generally, an interior choice $-1<p<1$ gives $D_E^p(1,0)=1-p$. The sketch shows the particular choice $p=0$.

For a proper convex function $E$ on a real Hilbert space, its subdifferential at $y$ isIn a Banach space, interpret the pairing with an element of the dual space. For a chosen subgradient $p\in \partial E(y)$, the Bregman distance isIf also $q\in \partial E(x)$, its symmetric Bregman distance isThe subgradient inequality proves nonnegativity. These quantities depend on the chosen subgradients and generally are not metrics: they need not distinguish different points or obey the triangle inequality.

Use the scaled proximal operator ${\mathrm{prox}}_{\gamma E}$; take $\gamma =1$ for each unscaled resolvent.

For the quadratic case, write $D^{T}D=\mathrm{diag}(d_1,\dots ,d_n)$ and $\xi =Qx$. Since $Q$ is an orthogonal matrix, the quadratic proximal term becomes $\Vert \xi -Qz{\Vert }^2/2$. The subgradient optimality condition givesAll $d_j\ge 0$, so each diagonal entry is positive, including when $d_j=0$. Multiplying by the inverse diagonal matrix givesThe proximal operator of Poisson data fidelity separates pointwise. At each $t$, the scalar optimality equation on $x>0$ isSince $y>0$, the two roots have opposite signs. Only the positive root is admissible in the logarithm:The negative root is outside the effective domain. The second derivative $1+\gamma y/x^2$ of the proximal objective is positive, establishing the unique pointwise minimizer. The integral formula is understood on the function spaces where these quantities are admissible.

Finally, for $E(x)=|x|$, positive and negative minimizers obey $x-z+\gamma =0$ and $x-z-\gamma =0$, respectively. At zero the subdifferential condition is $z\in [-\gamma ,\gamma ]$. Combining these cases yields soft thresholding:Thus $\gamma =1$ supplies all three requested closed forms.

For a proper convex function $E$ that is lower semicontinuous on a Hilbert space, its proximal operator at scale $\gamma >0$ isThe minimizer is unique because the objective is strongly convex; existence follows from the closed proper convex functional and the coercive quadratic, using an affine lower bound. The subgradient optimality condition is $0\in x-z+\gamma \partial E(x)$, which is exactly the displayed resolvent of a monotone operator relation. Setting $\gamma =1$ gives the unscaled proximity or resolvent operator requested here. This is a nonlinear resolvent of the subdifferential, distinct from the spectral resolvent of a linear operator.