arXiv research

We extend a recently proposed 1-nearest-neighbor based multiclass learning algorithm and prove that our modification is universally strongly Bayes-consistent in all metric spaces admitting any such learner, making it an "optimistically universal" Bayes-consistent learner. This is the first learning algorithm known to e…

Proves DCNNs with expansive convolution are strongly universally consistent.

New rule universally consistent for online learning with non-ergodic data.

New algorithm achieves consistent learning from context in bandit problems.

Solves open problem on universally consistent online learning with unbounded losses.

Study shows $k$-NN classifier is not universally consistent on $(0,1)$ but consistent on discrete and specific measure spaces.

Modified relative universality for unbiasedness and consistency in dimension reduction.

New findings on universal learning in contextual bandits with adversarial rewards.

Prototype rules simplify multiclass classification in metric spaces, achieving consistency and reduced complexity.

Reduces bounded loss learning to binary classification.

This appendix proves CORN's universal consistency. One of Bin's PhD thesis examiner (Special thanks to Vladimir Vovk from Royal Holloway, University of London) suggested that CORN is universal and provided sketch proof of Lemma 1.6, which is the key of this proof. Based on the proof in Gyprfi et al. [2006], we thus pro…

Learning rule consistency tied to non-existence of real-valued measurable cardinals.

New algorithms for regression with adversarial responses on various metric spaces.

Consistency of k-NN rule proven in sigma-finite dimensional metric spaces.

A new learning rule consistently reduces error over data samples.

Estimates means in metric spaces using quantization.

The K-sample testing problem involves determining whether K groups of data points are each drawn from the same distribution. Analysis of variance is arguably the most classical method to test mean differences, along with several recent methods to test distributional differences. In this paper, we demonstrate the existe…

Novel approach to universal online learning for bounded losses, closing open problems.

This work initiates a general study of learning and generalization without the i.i.d. assumption, starting from first principles. While the traditional approach to statistical learning theory typically relies on standard assumptions from probability theory (e.g., i.i.d. or stationary ergodic), in this work we are inter…

In this work we show that, using the eigen-decomposition of the adjacency matrix, we can consistently estimate feature maps for latent position graphs with positive definite link function $κ$, provided that the latent positions are i.i.d. from some distribution F. We then consider the exploitation task of vertex classi…

Implementing $k$-NN classification using Gromov--Wasserstein distances

In this paper we modify the coordinate construction in our previous paper on the universal moduli space of pair consisting of a Riemann Surfaces and a stable holomorphic bundles on the Riemann Surface, so as to produce a new set of coordinates, which are in fact K\" ahler coordinates on this universal moduli space. Fur…

We prove the statistical consistency of kernel Partial Least Squares Regression applied to a bounded regression learning problem on a reproducing kernel Hilbert space. Partial Least Squares stands out of well-known classical approaches as e.g. Ridge Regression or Principal Components Regression, as it is not defined as…

For graphs generated from stochastic blockmodels, adjacency spectral embedding is asymptotically consistent. Further, adjacency spectral embedding composed with universally consistent classifiers is universally consistent to achieve the Bayes error. However when the graph contains private or sensitive information, trea…

The problem of universal outlying sequence detection is studied, where the goal is to detect outlying sequences among $M$ sequences of samples. A sequence is considered as outlying if the observations therein are generated by a distribution different from those generating the observations in the majority of the sequenc…

Paper develops a privacy-preserving nonparametric regression method.

New theorem for generalized group sparsity improves consistency and convergence rates.

A universal LSTM model outperforms asset-specific models in forecasting stock volatilities.

The paper proves neural networks' consistency and optimal convergence rates for various function classes.

We consider stationary autoregressive processes with coefficients restricted to an ellipsoid, which includes autoregressive processes with absolutely summable coefficients. We provide consistency results under different norms for the estimation of such processes using constrained and penalized estimators. As an applica…

Differentially-private Bayes consistency rule for binary classification and density estimation.

Paper establishes a universal growth rate for smooth surrogate losses in classification.

Constructs universal local deformations for curves and differential forms.

The massive amount of available data potentially used to discover patters in machine learning is a challenge for kernel based algorithms with respect to runtime and storage capacities. Local approaches might help to relieve these issues. From a statistical point of view local approaches allow additionally to deal with …

Deep neural networks without regularization can achieve consistent estimates with good convergence rates.

We investigate iterated compositions of weighted sums of Gaussian kernels and provide an interpretation of the construction that shows some similarities with the architectures of deep neural networks. On the theoretical side, we show that these kernels are universal and that SVMs using these kernels are universally con…

PLN-Nets with two linear layers and parallel LN achieve universal approximation.

We construct a variant $\mathcal{K}_n$ of the Hopf algebra $\mathcal{H}_n$, which acts directly on the noncommutative model for the generic space of leaves rather than on its frame bundle. We prove that the Hopf cyclic cohomology of $\mathcal{K}_n$ is isomorphic to that of the pair $(\mathcal{H}_n, {\mathop{\rm GL}_n})…

The $k$-nearest neighbour ($k$-NN) classifier is one of the oldest and most important supervised learning algorithms for classifying datasets. Traditionally the Euclidean norm is used as the distance for the $k$-NN classifier. In this thesis we investigate the use of alternative distances for the $k$-NN classifier. We …

We study in this paper the consequences of using the Mean Absolute Percentage Error (MAPE) as a measure of quality for regression models. We show that finding the best model under the MAPE is equivalent to doing weighted Mean Absolute Error (MAE) regression. We also show that, under some asumptions, universal consisten…

Universal model for soft tissue mechanics under shock waves.

PanRep learns universal node embeddings for heterogeneous graphs.

We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is universally optimal in the sense that it achieves the optimal rate both in the deterministic and stochastic case and operates without knowledge …

Constraining linear layers in neural networks to respect symmetry transformations from a group $G$ is a common design principle for invariant networks that has found many applications in machine learning. In this paper, we consider a fundamental question that has received little attention to date: Can these networks ap…

New variational formula for Rényi divergences improves neural network estimation in high dimensions.

We propose and analyze a regularization approach for structured prediction problems. We characterize a large class of loss functions that allows to naturally embed structured outputs in a linear space. We exploit this fact to design learning algorithms using a surrogate loss approach and regularization techniques. We p…

This article introduces a universal moduli space for the set whose archetypal element is a pair that consists of a metric and second fundamental form from a compact, oriented, positive genus minimal surface in some hyperbolic 3-manifold. This moduli space is a smooth, finite dimensional manifold with canonical maps to …

Deep learning models converge to Gaussian dynamics with mixed structured inputs.