# Bounding point-wise maximum of the absolute difference of two convex functions

Let $\Delta: R \times R \rightarrow R_{+}$ be a positive and convex function (convex in, say, both the arguments) called the loss function.

Let $x \in R^d$. Moreover, let $H_1,...,H_r$ be sets of linear functions defined on $x$ i.e. for $h_i \in H_i$, $h_i(x)$ is a linear function of $x$.

Let $D_S$ and $D_T$ be two distributions over $x$ on $R^d$ and for $h_i,h'_i \in H_i$, define $\Delta^S(h_i,h_i') = E_{x \sim D_S} [ \Delta (h_i(x),h'_i(x)]$ to be the expected value of $\Delta(h_i(x),h'_i(x))$ under distribution $D_S$; same for $\Delta^T$. That is $\Delta^S$ is some kind of an expected loss between two functions $h_i$ and $h'_i$. Obviously $\Delta^S$ is convex.

Let's define discrepancy, $Disc(h;D_S,D_T)$ for a given set of linear functions $H$ as $Disc(H; D_S,D_T) = \max_{h,h' \in H} | \Delta^S(h,h') - \Delta^T(h,h')|$ as a discrepancy between distributions $D_S$ and $D_T$ given a hypothesis class $H$. This is similar to several statistical distance measures in vogue.

Phew..the final thing now. Given a set of positive parameters: $\{\lambda_1,...,\lambda_r\}$ with $\sum_i \lambda_i =1$, consider $\overline{H} = (\sum_i \lambda_i h_i | h_i \in H_i)$ as the set of all possible convex combinations of hypotheses in $H_1,...,H_r$.

Finally, the question is that can I bound $Disc(\overline{H};D_S,D_T)$ in terms of $\lambda_1,...,\lambda_r$ and $Disc(H_1;D_S,D_T),...,Disc(H_r;D_S,D_T)$.

Bounding it as a convex combination as $\sum_i \lambda_i Disc(H_i;D_S,D_T)$ seems hard. I would be happy if I can bound it even by $\max_i Disc(H_i;D_S,D_T)$.

It is easy to see that the above is essentially a question of bounding a maximum over the absolute difference of two convex functions (or a linear combination of two convex functions with coefficients summing to zero.)

-
There is a large literature on maximizing differences of two convex functions, as you can see by googling: "maximizing difference of two convex functions" Much of this literature addresses bounds of the sort you are interested in. –  Igor Rivin Jan 15 '11 at 22:24