Learning from unordered tuples? EDIT: I reduced my problem to a more specific question:
https://math.stackexchange.com/questions/26573/
But I am still interested in other ideas.
Let's say our data is generated by
$$Y_i = f(X_i) + \epsilon_i$$
where $X_i$ are observed vectors, and $f$ is an unknown function.  We know that $f$ is invariant with respect to permutation of the elements of $X$.  For example, if $X_i=[x_{i1},x_{i2},x_{i3}]$, then we have
$$
f([x_{i1},x_{i2},x_{i3}]) = f([x_{i1},x_{i3},x_{i2}]) = f([x_{i2},x_{i1},x_{i3}])=\cdots 
$$
Are there modified versions of linear regression, support vector machines, forests, etc. which can be used to estimate $f$?  I'm specifically interested in the case when $X_i$ are eigenvalues of matrices (so they have complex-valued entries).
EDIT: A desperation move would be to make replicates of each data point with all permutations of each $X_i$ vectors and then apply standard methods, but this is clearly computationally impractical.
 A: For regression models, one way would be to generate derived variables that are invariant to permutation of the labelling of the $x_i$s.
E.g. in your three-variable example, considering only polynomials of total order up to 3, such combinations would be:


*

*$w_1 = x_1 + x_2 + x_3$

*$w_2 = x_1x_2 + x_1x_3 + x_2x_3$

*$w_3 = x_1^2 + x_2^2 + x_3^2$

*$w_4 = x_1x_2x_3$

*$w_5 = x_1^2x_2 + x_1^2x_3 + x_2^2x_1 + x_2^2x_3 + x_3^2x_1 + x_3^2x_2$

*$w_6 = x_1^3 + x_2^3 + x_3^3$


You could then use any any form of regression that includes some function $f(a_1w_1 + a_2w_2 + \cdots + a_8w_8)$ and find values for the $a_i$s by non-linear least squares, generalized linear modelling or other methods. The combination $a_1w_1 + a_2w_2 + \cdots + a_8w_8$ fits a response surface that's a polynomial of order 3 that is symmetric in permutation of $x_1, x_2, x_3$.
Clearly there would be many more possibilities if you wished to allow functions other than polynomials such as logs, fractional powers...
(EDIT I finished this post before I saw your edit to the answer with the link to the more specific question on mathoverflow. I was started to think there must be some mathematical framework for listing all such polynomials of a given total order, but it sounds you already know more than me about the relevant area of maths!)
A: To add to onestop's response, it was confirmed on math.SE that the polynomials
$$w_1 = x_1 + \cdots + x_n$$
$$w_2 = x_1^2 + \cdots + x_n^2$$
$$\cdots$$
$$w_n = x_1^n + \cdots + x_n ^n$$
give you all the information needed to determine the original $X=(x_1, \cdots, x_n)$.
This is a neat result because it also applies to moments of a discrete distribution with uniform probabilities.
A: Deep Sets and PointNet provide two (fairly recent) examples of permutation-invariant deep learning architectures. Both these methods provided state-of-the-art results at their time of introduction and are continuous (in senses described in their papers) with respect to perturbations of the underlying sets.
The permutation-invariant Deep Sets neural architecture can be written as:
$$ F_{DS}(A) = \rho\left( \sum_{a\in A} \phi(a) \right) $$
and a (simplified) PointNet architecture can be written as:
$$ F_{PN}(A) = \rho\left( \max_{a\in A} \phi(a) \right) $$
where $\phi:\mathbb{R}^n\to\mathbb{R}^m$ creates features for each point in the set $A$ and $\rho:\mathbb{R}^m\to\mathbb{R}$ combines these features into a single real-valued output (here the $\max$ of a vector is taken to be the component-wise maximum and $\rho$ and $\phi$ are continuous). Since taking sums and max are permutation-invariant, so is the whole network. 
Ideally we would choose $\rho$ and $\phi$ to be the functions that together minimize the error among all such continuous functions, but that is monstrously intractable. Instead we model $\rho$ and $\phi$ as neural networks whose joint set of parameters $\Theta$ are chosen to minimize the regression error. 

With respect to your context and notation for $|X_i|=3$, these models look like:
$$ F_{DS}(X_i) = \rho\Big(\phi(x_{i1}) + \phi(x_{i2}) + \phi(x_{i3})\Big) $$
$$ F_{PN}(X_i) = \rho\Big( \max\big\{\phi(x_{i1}),\phi(x_{i2}),\phi(x_{i3})\big\} \Big) $$

Bonus: Deep Sets actually also describes a permutation-equivariant architecture as well.
