Take a Lipshitz function on a compact subset of $R^N$ where we want to scale up $N$. If we know that (1) the functions are invariant to permutations (2) that there is a bound that is independent of the number of arguments; and (3) there are some sorts of bounds on the curvature (not sure the exact condition). Can we make any claims on how the Lipshitz coefficient scales with the number of arguments?
To try to formalize this (which might be the wrong direction):
Take a sequence of function $f_N : [0,1]^N \to R$. Denote an element as $X \in [0,1]^N$. The key structure is:
- The function $f_N$ is invariant to permutations. That is, for any permutation matrix $P_N \in R^{N \times N}$, $f_N(P_N X) = f_N(X)$.
- Some sort of bound on the curvature that is independent of $N$. Maybe on the hessian?
- The function $f_N$ is Lipshitz. Denote its Lipshitz norm as $\|f_N\|_{Lip}$
- There is a bound on the function independent of $N$. That is $\max_{X \in [0,1]^N} f_N(X) \leq K$ for all $N$, for some $K < \infty$.
Given this structure (i.e. invariant to permutations and bounded independent of $N$), can we make any claims on the maximum dependence of the Lipshitz norm? In particular, I would like to claim that there exists a constant $C$ such that $$\|f_N\|_{Lip} \leq \frac{C}{\sqrt{N}}$$
Or something like that. If this is true, how can it be proved? What is the precise condition bounding the curvature that we would need to add to eliminate counterfactuals (such as the one below)?
To have some examples in your mind:
A good example of a function fulfilling the criteria is the mean function defined on any compact set. $$ f_N(X) = \frac{1}{N}\sum_{n=1}^N x_n $$ In that case, we know that the $\|f_N\|_{Lip} = \frac{1}{\sqrt{N}}$. This is clearly symmetric and fulfills the boundedness criteria since for any N, $\max_{X \in [0,1]^N} f_N(X) = 1$.
Alternatively, while something like $f_N(X) = \sum_{n=1}^N x_n$ is Lipshitz and symmetric, $\max_{X \in [0,1]^N} f_N(X) = N$ which is symmetric but not bounded independent of $N$, and hence wouldn't fulfill the criteria I am looking for.
Similarly, while $f_N(X) = x_1$ is Lipshitz and bounded independently of $N$, it is not invariant to permutations. So I think symmetry is required here.
The example $f_N(X) = \sum_{n=1}^N x_n^N$ is Lipshitz and symmetric, $\max_{X \in [0,1]^N} f_N(X) = 1$ (since it is on the boundary). And yet the Lipshitz constant blows up. However, note that this function has curvature that explodes as $N$ increases.
This is useful for bounding the concentration of measure for high-dimensional probability with symmetric functions---which will themselves come out of neural network approximations.