In the paper Dissimilarity in Graph-Based Semi-Supervised Classification, there are few things I could not understand. Given that $x_1, x_2,..., x_n$ are the vector representation of $n$ items, $f : X \rightarrow \mathbb{R}$ is the discriminant function, and $w_{ij}$ are all non-negative,

why is $ \frac{1}{2} \sum_{i, j = 1}^n w_{ij} (f(x_i)- f(x_j))^2$ convex w.r.t to $f$?
Also, why does changing any $w_{ij}$ to negative value make it non-convex?

I read on wikipedia that

"A twice-differentiable function of a single variable is convex if and only if its second derivative is nonnegative on its entire domain"

But I don't understand derivative should be take w.r.t to what?

  • 1
    $\begingroup$ I guess the first question is, convex with respect to what? What is the variable? $\endgroup$
    – Nik Weaver
    Aug 17, 2021 at 3:24
  • $\begingroup$ @NikWeaver Judging from some other passages in the paper, with respect to $f$. Not sure I understand much of their jargon: apparently it is just some internal technical report. The mathematics (when I can decipher what is written and translate it into plain English) seems fairly simple though. $\endgroup$
    – fedja
    Aug 17, 2021 at 4:25
  • $\begingroup$ I'm not sure that the second derivative is a good way to approach convexity here. If it's not a typo to say that the expression is convex in $f$, then they seem to be treating it as an operation on an infinite-dimensional function space, since that's what $f$ belongs to. I'll call this operation $\mathcal W$, so that $\mathcal W(f):=\frac12\sum_{i,j=1}^nw_{ij}\big(f(x_i)-f(x_j)\big)^2$. Then to say that $\mathcal W$ is convex is to say that if $f_1$ and $f_2$ are two functions (from $X$ to $\mathbb R$) and $t\in[0,1]$, then $\mathcal W(tf_1+(1-t)f_2)\le t\mathcal W(f_1)+(1-t)\mathcal W(f_2)$. $\endgroup$ Aug 17, 2021 at 5:16
  • $\begingroup$ @TobyBartels It does not seem to typo. On the second page, bottom left side, just above Proposition 1, they mention "It handles both similarity and dissimilarity, and is clearly convex in f ." $\endgroup$ Aug 17, 2021 at 5:55

1 Answer 1


Call the sum $S(f)$. Let $0<b<1$, and let $f$ and $g$ be two functions mapping $X$ to $\Bbb R$. Then $$ S(bf+(1-b)g)=b^2S(f)+(1-b)^2S(g)+b(1-b)\sum_{i,j}w_{i,j} [f(x_i)-f(x_j)]\cdot[g(x_i-g(x_j)]. $$ By Cauchy-Schwarz, $$ \sum_{i,j}w_{i,j} [f(x_i)-f(x_j)]\cdot[g(x_i-g(x_j)]\le 2\sqrt{S(f)S(g)}. $$ (The non-negativity of $w_{i,j}$ is used here: $w_{i,j} = \sqrt{w_{i,j}}\cdot \sqrt{w_{i,j}}$.) Therefore $$ \eqalign{ S(bf+(1-b)g) &\le b^2S(f)+(1-b)^2S(g)+2b(1-b)\sqrt{S(f)S(g)}\cr &= \left[b\sqrt{S(f)}+(1-b)\sqrt{S(g)}\right]^2\cr &\le bS(f)+(1-b)S(g), } $$ the final inequality because the square function is convex. This shows that $f\mapsto S(f)$ is convex. (Intuitively, $f\mapsto [f(x_i)-f(x_j)]^2$ is convex because the square is convex; and then $S$ is convex becasue it's a positive-linear combination of such functions of $f$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.