The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated under the assumption that the reference measure is a $\sigma $ -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.

Generalizing a method of Sutherland and the author for elliptic cur ves we design a subexponential algorithm for computing the endomorphism rings of ordinary abelian varieties of dimension two over finite fields. Although its correctness and complexity analysis rest on several assumptions, we report on practical computations showing that it performs very well and can easily handle previously intractable cases. Note . Some results of this paper previously appeared in the author’s thesis, [ Endomorphism Rings in Cryptography , Ph.D. Thesis. Eindhoven University of Technology and Institut National Polytechnique de Lorraine, 2011. ISBN: 90-386-2519-7].

International Press of Boston - publishers of scholarly mathematical and scientific journals and books

In this paper, closed-form expressions for the variation of the expectation of a given function due to changes in the probability measure (probability distribution drifts) are presented. These expressions unveil interesting connections with Gibbs probability measures, information projections, Pythagorean identities for relative entropy, mutual information, and lautum information.

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 sigma-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 a regularization parameter that achieves an arbitrarily small empirical risk with arbitrarily high probability. The sensitivity of the expected empirical risk to deviations from the solution of the ERM-RER problem is studied. The sensitivity is then used to provide upper and lower bounds on the expected empirical risk. Moreover, it is shown that the expectation 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.

La cryptographie est indispensable aux réseaux de communication modernes afin de garantir la sécurité et l'intégrité des données y transitant. Récemment, des cryptosystèmes efficaces, sûr et riches ont été construits à partir de variétés abéliennes définies sur des corps finis. Cette thèse contribue à plusieurs aspects algorithmiques de ces variétés touchant à leurs anneaux d'endomorphismes. Cette structure joue un rôle capital pour construire des variétés abéliennesmunies de bonnes propriétés, comme des couplages, et nous montrons qu'un plus grand nombre de telles variétés peut être construit qu'on ne pourrait croire. Nous considérons aussi le problème inverse qu'est celui du calcul de l'anneau d'endomorphismes d'une variété abélienne donnée. Les meilleures méthodes connues ne pouvaient précédemment résoudre ce problème qu'en temps exponentiel ; ici, nous concevons plusieurs algorithmes de complexité sous-exponentielle le résolvant dans le cas ordinaire. Pour les courbes elliptiques, nous bornons rigoureusement la complexité de nos algorithmes sous l'hypothèse de Riemann étendue et démontrons qu'ils sont extrêmement efficaces en pratique. Comme sous-routine, nous développons notamment un algorithme sans mémoire pour résoudre une généralisation du problème du sac à dos. Nous généralisons aussi notre méthode aux variétés abélienne de dimension supérieure. Concrètement, nous développons une bibliothèque qui permet d'évaluer des isogénies entre variétés abéliennes ; cet outil nous permet d'appliquer une généralisation de notre méthode à des exemples jusqu'alors incalculables.