Coordinate Sensitivities in McDiarmid Bounds

Why Coordinate Sensitivity Matters

For a function of independent inputs, concentration depends not only on how many inputs there are but also on how much each input can affect the function. A change to one coordinate might have a large effect, a small effect, or no effect at all. Recording these effects separately can produce a useful weighted bound, rather than treating every coordinate as equally influential.

The central task is to find a valid worst-case bound for each one-coordinate change. The bounds need not be the smallest possible, but they must hold uniformly over the permitted input values. Once they are established, the bounded-differences inequality combines them through the sum of their squares.

Coordinatewise Oscillation Bounds

Definition: Let $X_1,\ldots,X_n$ be independent random variables taking values in measurable spaces $\mathcal X_1,\ldots,\mathcal X_n$, and let $f:\prod_{i=1}^n\mathcal X_i\to\mathbb R$ be measurable. A coordinatewise change bound for coordinate $i$ is a number $c_i\geq 0$ such that $$ |f(x_1,\ldots,x_i,\ldots,x_n)-f(x_1,\ldots,x_i',\ldots,x_n)|\leq c_i $$ for every fixed choice of the other coordinates and every permitted pair $x_i,x_i'$. The smallest such bound is the coordinatewise oscillation of $f$ in coordinate $i$. It is enough to impose the condition on the product of the supports of the inputs, provided that the resulting bounded-differences theorem applies almost surely.

The word permitted matters: the bound concerns possible values of a coordinate, not just values likely to occur in a typical sample. In calculations, a convenient $c_i$ that is easy to verify is often preferable to the exact smallest oscillation.

Theorem (McDiarmid’s bounded-differences inequality): Suppose $X_1,\ldots,X_n$ are independent, $f(X_1,\ldots,X_n)$ is integrable, and finite constants $c_1,\ldots,c_n$ satisfy the coordinatewise change condition almost surely on the product of the input supports. Then, for every $t>0$, $$ P\bigl(f(X)-E[f(X)]\geq t\bigr)\leq \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). $$ The same bound holds for $P(E[f(X)]-f(X)\geq t)$; consequently, $$ P\bigl(|f(X)-E[f(X)]|\geq t\bigr)\leq 2\exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). $$ If every $c_i=0$, then $f(X)$ is almost surely constant and the deviation probabilities are zero for $t>0$.

The role of coordinate sensitivity is direct: a larger $c_i$ contributes more to $\sum_i c_i^2$, weakening the bound. A coordinate with $c_i=0$ contributes nothing. The inequality itself follows from the bounded-differences result and its Doob martingale proof; here the practical work is identifying valid $c_i$ values for the function at hand.

Building Bounds From Local Contributions

Many functions are sums of terms, each involving only a subset of the coordinates. A coordinate can change only the terms in which it appears, so adding the bounds for those terms gives a bound for the full function.

Proposition: Suppose $f(x)=\sum_{r=1}^m h_r(x_{S_r})$, where $S_r\subseteq\{1,\ldots,n\}$ and $x_{S_r}$ denotes the coordinates indexed by $S_r$. If changing coordinate $i$ changes $h_r$ by at most $d_{ri}$ whenever $i\in S_r$, then a valid coordinate bound for $f$ is $$ c_i=\sum_{r:\,i\in S_r}d_{ri}. $$

Proof. Fix all coordinates other than $i$, and compare two permitted values of coordinate $i$. If $i\notin S_r$, the term $h_r(x_{S_r})$ is unchanged. For each term with $i\in S_r$, its change in absolute value is at most $d_{ri}$. By the triangle inequality, the absolute change in the sum is no greater than the sum of the absolute changes of its terms. Therefore it is at most $\sum_{r:\,i\in S_r}d_{ri}$, as claimed. $\square$

This bound is valid even when changes in different terms partially cancel. It may then be conservative, but it does not rely on cancellation that might disappear for another input configuration.

Worked Example: Changes to Adjacent-Pair Matches

Let $X_1,\ldots,X_6$ be independent Bernoulli random variables with $P(X_i=1)=0.4$. Define $H$ to be the number of adjacent pairs with equal values: $$ H=\sum_{i=1}^{5}\mathbf{1}\{X_i=X_{i+1}\}. $$ Find coordinate bounds and a one-sided deviation bound for $H$.

Each summand depends on two neighboring coordinates. Changing an interior coordinate $X_i$, for $2\leq i\leq 5$, can change only the two indicators for pairs $(i-1,i)$ and $(i,i+1)$. Each indicator changes by at most 1, so $c_i=2$ is valid. This value is attained, for example, when both neighbors are 0 and $X_i$ changes from 0 to 1. An endpoint affects only one indicator, so $c_1=c_6=1$.

For any adjacent pair, independence gives $P(X_i=X_{i+1})=0.4^2+0.6^2=0.16+0.36=0.52$. By linearity of expectation, $E[H]=5(0.52)=2.6$. The squared-bound sum is $$ \sum_{i=1}^{6}c_i^2=1^2+4(2^2)+1^2=18. $$ Thus, for $t>0$, $$ P(H-2.6\geq t)\leq \exp\left(-\frac{2t^2}{18}\right). $$ In particular, at $t=1$ the upper bound is $\exp(-1/9)$, approximately $0.895$. It is a valid bound, although it is not especially sharp for this small example.

Metric Changes and Range Bounds

Sometimes an input is not naturally described by a finite list of possible values. A metric can express how far two values of one coordinate are from each other. A coordinatewise Lipschitz condition then converts directly into a sensitivity bound.

Proposition: Suppose each input space $\mathcal X_i$ has a metric $d_i$, and $$ |f(x)-f(y)|\leq\sum_{i=1}^n L_i d_i(x_i,y_i) $$ for all $x,y$ in the product input space, where $L_i\geq0$. If the diameter $D_i=\sup_{u,v\in\mathcal X_i}d_i(u,v)$ is finite, then $c_i=L_iD_i$ is a valid coordinatewise change bound.

Proof. Take $x$ and $y$ that agree in every coordinate except $i$. For $j\ne i$, $d_j(x_j,y_j)=0$. The assumed inequality therefore reduces to $$ |f(x)-f(y)|\leq L_i d_i(x_i,y_i)\leq L_iD_i. $$ This holds for every permitted pair of values in coordinate $i$, so $c_i=L_iD_i$ is valid. $\square$

Worked Example: The Maximum of Three Inputs

Let $X_1,X_2,X_3$ be independent, with $X_1\in\{0,2\}$, $X_2\in\{0,1\}$, and $X_3\in\{0,3\}$. Suppose their probabilities of taking their nonzero values are $0.5$, $0.25$, and $0.2$, respectively. For $M=\max(X_1,X_2,X_3)$, find coordinate bounds, $E[M]$, and a McDiarmid bound.

Changing $X_i$ cannot change the maximum by more than the difference between its two possible values. The bounds are therefore $c_1=2$, $c_2=1$, and $c_3=3$. They are attained by setting the other inputs to 0 and changing $X_i$ from 0 to its positive value.

To compute the expectation, partition according to which positive value is the maximum. The maximum is 3 with probability $0.2$, contributing $3(0.2)=0.6$. It is 2 when $X_3=0$ and $X_1=2$, an event of probability $0.8(0.5)=0.4$, contributing $2(0.4)=0.8$. It is 1 when $X_3=0$, $X_1=0$, and $X_2=1$, an event of probability $0.8(0.5)(0.25)=0.1$, contributing $0.1$. Otherwise the maximum is 0. Hence $E[M]=0.6+0.8+0.1=1.5$.

Here $\sum_i c_i^2=4+1+9=14$, so for $t>0$, $$ P(M-1.5\geq t)\leq \exp\left(-\frac{2t^2}{14}\right). $$ For $t=1$, this is $\exp(-1/7)$, approximately $0.867$.

Normalized Pair Statistics

Normalization changes coordinate sensitivity. If a statistic averages many local contributions, changing one input may affect several terms, but each affected term also has a smaller weight. Tracking both effects is essential.

Worked Example: The Fraction of Matching Pairs

Let $X_1,\ldots,X_8$ be independent Bernoulli variables with $P(X_i=1)=0.3$. Let $Q$ be the fraction of all unordered pairs whose labels agree: $$ Q=\frac{1}{\binom{8}{2}}\sum_{1\leq i<j\leq 8}\mathbf{1}\{X_i=X_j\}. $$ Find coordinate bounds, $E[Q]$, and a bound for $P(Q-E[Q]\geq0.2)$.

Changing coordinate $X_i$ affects only pairs containing $i$. There are 7 such pairs among $\binom{8}{2}=28$ total pairs. Each indicator changes by at most 1, so $c_i\leq 7/28=1/4$. This bound can be attained: if all the other labels equal the old value of $X_i$, changing $X_i$ makes all 7 affected pairs switch from matching to nonmatching.

For any pair, the probability of agreement is $0.3^2+0.7^2=0.09+0.49=0.58$. Every pair has weight $1/28$, so linearity of expectation gives $E[Q]=0.58$. Also, $\sum_{i=1}^{8}c_i^2=8(1/4)^2=1/2$. Therefore, $$ P(Q-0.58\geq0.2) \leq \exp\left(-\frac{2(0.2)^2}{1/2}\right) =\exp(-0.16). $$ The calculation shows why normalization belongs in the sensitivity calculation: the numerator can change in as many as seven places, but each change contributes only $1/28$ to $Q$.

Common Mistake: Using Typical Changes

A frequent error is to substitute an average or typical coordinate effect for the worst-case bound. For example, an input might usually leave a statistic unchanged, but still be able to change it substantially for a particular configuration of the other inputs. McDiarmid’s inequality requires a bound that holds uniformly over permitted inputs, not merely a small expected change.

The correction is to fix the other coordinates and consider all permitted pairs of values for coordinate $i$. Bound the largest resulting absolute difference, then use that $c_i$ in the squared-bound sum. If a convenient bound is loose, it remains valid; an average sensitivity does not become valid just because it is smaller.

Independence is also a separate requirement of the stated inequality. Correctly computing coordinate oscillations does not make the McDiarmid bound applicable when the inputs are dependent. For independent inputs, the practical sequence is: identify which parts of the function can change, bound each part’s change, combine the bounds, and then apply the weighted inequality.

Key takeaway: The weighted bound is only as reliable as its coordinate sensitivities. Compute each one from the largest possible one-coordinate change, account for normalization and local structure, and combine the results through $\sum_i c_i^2$.

Check Your Understanding

For each question, focus on the largest change possible when one coordinate varies and the others are fixed.

If a function is a sum of local terms, why can a coordinate bound be obtained by summing the bounds for the terms involving that coordinate?
In the adjacent-pair example, why is an interior-coordinate bound larger than an endpoint bound?
For a function that is Lipschitz in coordinate $i$ with constant $L_i$, what additional quantity is needed to turn that condition into a coordinate change bound?
Why is the average effect of changing a coordinate not, in general, an acceptable $c_i$ for McDiarmid’s inequality?
If a statistic counts affected pairs and then divides by the total number of pairs, how should the division enter its coordinate sensitivity?