Eitan Levin

Eitan Levin, Mateo Díaz

Traditional supervised learning aims to learn an unknown mapping by fitting a function to a set of input-output pairs with a fixed dimension. The fitted function is then defined on inputs of the same dimension. However, in many settings, the unknown mapping takes inputs in any dimension; examples include graph parameters defined on graphs of any size and physics quantities defined on an arbitrary number of particles. We leverage a newly-discovered phenomenon in algebraic topology, called representation stability, to define equivariant neural networks that can be trained with data in a fixed dimension and then extended to accept inputs in any dimension. Our approach is user-friendly, requiring only the network architecture and the groups for equivariance, and can be combined with any training procedure. We provide a simple open-source implementation of our methods and offer preliminary numerical experiments.

Shengtai Yao, Eitan Levin, Mateo Díaz

Several machine learning models are defined for inputs of any size, such as graphs with different numbers of nodes and point clouds containing varying numbers of points. The universality properties of such any-dimensional models remain poorly understood, as universality is traditionally studied for models accepting inputs of a fixed size, defined on a compact subset of their domain. In sharp contrast, any-dimensional models can be viewed as sequences of functions defined on growing-sized inputs, and it is not clear in which sense they can be universal. We develop a systematic approach to establish any-dimensional universality, by identifying any-dimensional functions with a unique function taking inputs in a suitable infinite-dimensional limit space containing inputs of all finite sizes as well as their limits. Using the symmetries of these inputs and relations between inputs of different sizes, we show that this limit space admits a natural topology with rich families of compact sets on which any-dimensional universality can be established. We illustrate our approach by showing that several existing architectures fail to be universal, and we propose simple modifications that restore universality.

Eitan Levin, Yuxin Ma, Mateo Díaz et al.

Many modern learning tasks require models that can take inputs of varying sizes. Consequently, dimension-independent architectures have been proposed for domains where the inputs are graphs, sets, and point clouds. Recent work on graph neural networks has explored whether a model trained on low-dimensional data can transfer its performance to higher-dimensional inputs. We extend this body of work by introducing a general framework for transferability across dimensions. We show that transferability corresponds precisely to continuity in a limit space formed by identifying small problem instances with equivalent large ones. This identification is driven by the data and the learning task. We instantiate our framework on existing architectures, and implement the necessary changes to ensure their transferability. Finally, we provide design principles for designing new transferable models. Numerical experiments support our findings.

Eitan Levin, Alexander Y. Meltzer

Accurate determination of the regularization parameter in inverse problems still represents an analytical challenge, owing mainly to the considerable difficulty to separate the unknown noise from the signal. We present a new approach for determining the parameter for the general-form Tikhonov regularization of linear ill-posed problems. In our approach the parameter is found by approximate minimization of the distance between the unknown noiseless data and the data reconstructed from the regularized solution. We approximate this distance by employing the Picard parameter to separate the noise from the data in the coordinate system of the generalized SVD. A simple and reliable algorithm for the estimation of the Picard parameter enables accurate implementation of the above procedure. We demonstrate the effectiveness of our method on several numerical examples. A MATLAB-based implementation of the proposed algorithms can be found at https://www.weizmann.ac.il/condmat/superc/software/

Eitan Levin, Alexander Y. Meltzer

We propose a new stopping criterion for Krylov subspace iterative regularization of large-scale ill-posed inverse problems. Our stopping criterion accurately filters the data using a generalization of the Picard parameter that was originally introduced for direct regularization of small-scale problems. In the one dimension we filter the data in the discrete Fourier transform (DFT) basis using the Picard parameter, which separates noise-dominated Fourier coefficients from the signal-dominated ones. For two-dimensional problems we propose a novel vectorization scheme of the Fourier coefficients of the data based on the Kronecker product structure of the two-dimensional DFT matrix, which effectively reduces the problem to one dimension. At each iteration we compute the distance between the data reconstructed from the iterated solution and the filtered data, terminating the iterations once this distance begins to increase or to level off. The accuracy and robustness of the proposed method is demonstrated by several numerical examples and a MATLAB-based implementation is provided.