The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a σ-finite measure, and not necessarily a probability measure. Under this assumption, which leads to a generalization of the ERM-RER problem allowing a larger degree of flexibility for incorporating prior knowledge, numerous relevant properties are stated. Among these properties, the solution to this problem, if it exists, is shown to be a unique probability measure, mutually absolutely continuous with the reference measure. Such a solution exhibits a probably-approximately-correct guarantee for the ERM problem independently of whether the latter possesses a solution. For a fixed dataset and under a specific condition, the empirical risk is shown to be a sub-Gaussian random variable when the models are sampled from the solution to the ERM-RER problem. The generalization capabilities of the solution to the ERM-RER problem (the Gibbs algorithm) are studied via the sensitivity of the expected empirical risk to deviations from such a solution towards alternative probability measures. Finally, an interesting connection between sensitivity, generalization error, and lautum information is established.

The dependence on training data of the Gibbs algorithm (GA) is analytically characterized. By adopting the expected empirical risk as the performance metric, the sensitivity of the GA is obtained in closed form. In this case, sensitivity is the performance difference with respect to an arbitrary alternative algorithm. This description enables the development of explicit expressions involving the training errors and test errors of GAs trained with different datasets. Using these tools, dataset aggregation is studied and different figures of merit to evaluate the generalization capabilities of GAs are introduced. For particular sizes of such datasets and parameters of the GAs, a connection between Jeffrey’s divergence, training and test errors is established.

The optimality and sensitivity of the empirical risk minimization problem with relative entropy regularization (ERM-RER) are investigated for the case in which the reference is a σ-finite measure instead of a probability measure. This generalization allows for a larger degree of flexibility in the incorporation of prior knowledge over the set of models. In this setting, the interplay of the regularization parameter, the reference measure, the risk function, and the empirical risk induced by the solution of the ERM-RER problem is characterized. This characterization yields necessary and sufficient conditions for the existence of regularization parameters that achieve arbitrarily small empirical risk with arbitrarily high probability. Additionally, the sensitivity of the expected empirical risk to deviations from the solution of the ERM-RER problem is studied. Dataset-dependent and dataset-independent upper bounds on the absolute value of the sensitivity are presented. In a special case, it is shown that the expectation (with respect to the datasets) of the absolute value of the sensitivity is upper bounded, up to a constant factor, by the square root of the lautum information between the models and the datasets.

A permutation rational function $f\in\mathbb{F}\/_q(x)$ is a rational function that induces a bijection on $\mathbb{F}\/_q$, that is, for all $y\in\mathbb{F}\/_q$ there exists exactly one $x\in\mathbb{F}\/_q$ such that $f(x)=y$. Permutation rational functions are intimately related to exceptional rational functions, and, more generally, exceptional covers of the projective line, of which they form the first important example. In this paper, we show how to efficiently generate many permutation rational functions over large finite fields using isogenies of elliptic curves, and discuss some cryptographic applications. Our algorithm is based on Fried's modular interpretation of certain dihedral exceptional covers of the projective line [ Finite Fields: Theory, Applications, and Algorithms, Contemp. Math. 168, 1994, pp. 69--100].

We describe a space-efficient algorithm for solving a generalization of the subset sum problem in a finite group G, using a Pollard-ρ approach. Given an element z and a sequence of elements S, our algorithm attempts to find a subsequence of S whose product in G is equal to z. For a random sequence S of length d log2 n, where n = #G and d ≥ 2 is a constant, we find that its expected running time is $${O(\sqrt{n}\,{\rm log}\,n)}$$ group operations (we give a rigorous proof for d > 4), and it only needs to store O(1) group elements. We consider applications to class groups of imaginary quadratic fields, and to finding isogenies between elliptic curves over a finite field.