Bounding point-wise maximum of the absolute difference of two convex functions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:00:07Z http://mathoverflow.net/feeds/question/52190 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52190/bounding-point-wise-maximum-of-the-absolute-difference-of-two-convex-functions Bounding point-wise maximum of the absolute difference of two convex functions Rajhans 2011-01-15T22:14:54Z 2011-01-16T22:11:56Z <p>Let $\Delta: R \times R \rightarrow R_{+}$ be a positive and convex function (convex in, say, both the arguments) called the loss function.</p> <p>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$.</p> <p>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.</p> <p>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.</p> <p>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$. </p> <p>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)$.</p> <p>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)$.</p> <p>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.)</p>