Let $H(q,p)$ be a Hamiltonian on $T^*T^n$. We show that the sequence $H_{k}(q,p)=H(kq,p)$ converges for the $gamma$ topology defined by the author, to $bar{H}(p)$. This is extended to the case where only some of the variables are homogenized, that is
the sequence $H(kx,y,q,p)$ where the limit is of the type ${bar H}(y,q,p)$ and thus yields an effective Hamiltonian. We give here the proof of the convergence, and the first properties of the homogenization operator, and give some immediate consequences for solutions of Hamilton-Jacobi equations, construction of quasi-states, etc. We also prove that the function $bar H$ coincides with Mathers $alpha$ function which gives a new proof of its symplectic invariance proved by P. Bernard. A previous version of this paper relied on the former On the capacity of Lagrangians in $T^*T^n$ which has been withdrawn. The present version of Symplectic Homogenization does not rely on it anymore.
Distributed computing offers a high degree of flexibility to accommodate modern learning constraints and the ever increasing size of datasets involved in massive data issues. Drawing inspiration from the theory of distributed computation models devel
oped in the context of gradient-type optimization algorithms, we present a consensus-based asynchronous distributed approach for nonparametric online regression and analyze some of its asymptotic properties. Substantial numerical evidence involving up to 28 parallel processors is provided on synthetic datasets to assess the excellent performance of our method, both in terms of computation time and prediction accuracy.
Let $bX=(X_1, hdots, X_d)$ be a $mathbb R^d$-valued random vector with i.i.d. components, and let $VertbXVert_p= (sum_{j=1}^d|X_j|^p)^{1/p}$ be its $p$-norm, for $p>0$. The impact of letting $d$ go to infinity on $VertbXVert_p$ has surprising consequ
ences, which may dramatically affect high-dimensional data processing. This effect is usually referred to as the {it distance concentration phenomenon} in the computational learning literature. Despite a growing interest in this important question, previous work has essentially characterized the problem in terms of numerical experiments and incomplete mathematical statements. In the present paper, we solidify some of the arguments which previously appeared in the literature and offer new insights into the phenomenon.
We consider the nonlinear Klein-Gordon equation in $R^d$. We call multi-solitary waves a solution behaving at large time as a sum of boosted standing waves. Our main result is the existence of such multi-solitary waves, provided the composing boosted
standing waves are stable. It is obtained by solving the equation backward in time around a sequence of approximate multi-solitary waves and showing convergence to a solution with the desired property. The main ingredients of the proof are finite speed of propagation, variational characterizations of the profiles, modulation theory and energy estimates.
We consider the setting of sequential prediction of arbitrary sequences based on specialized experts. We first provide a review of the relevant literature and present two theoretical contributions: a general analysis of the specialist aggregation rul
e of Freund et al. (1997) and an adaptation of fixed-share rules of Herbster and Warmuth (1998) in this setting. We then apply these rules to the sequential short-term (one-day-ahead) forecasting of electricity consumption; to do so, we consider two data sets, a Slovakian one and a French one, respectively concerned with hourly and half-hourly predictions. We follow a general methodology to perform the stated empirical studies and detail in particular tuning issues of the learning parameters. The introduced aggregation rules demonstrate an improved accuracy on the data sets at hand; the improvements lie in a reduced mean squared error but also in a more robust behavior with respect to large occasional errors.
We consider a Kullback-Leibler-based algorithm for the stochastic multi-armed bandit problem in the case of distributions with finite supports (not necessarily known beforehand), whose asymptotic regret matches the lower bound of cite{Burnetas96}. Ou
r contribution is to provide a finite-time analysis of this algorithm; we get bounds whose main terms are smaller than the ones of previously known algorithms with finite-time analyses (like UCB-type algorithms).
We consider the framework of stochastic multi-armed bandit problems and study the possibilities and limitations of forecasters that perform an on-line exploration of the arms. These forecasters are assessed in terms of their simple regret, a regret n
otion that captures the fact that exploration is only constrained by the number of available rounds (not necessarily known in advance), in contrast to the case when the cumulative regret is considered and when exploitation needs to be performed at the same time. We believe that this performance criterion is suited to situations when the cost of pulling an arm is expressed in terms of resources rather than rewards. We discuss the links between the simple and the cumulative regret. One of the main results in the case of a finite number of arms is a general lower bound on the simple regret of a forecaster in terms of its cumulative regret: the smaller the latter, the larger the former. Keeping this result in mind, we then exhibit upper bounds on the simple regret of some forecasters. The paper ends with a study devoted to continuous-armed bandit problems; we show that the simple regret can be minimized with respect to a family of probability distributions if and only if the cumulative regret can be minimized for it. Based on this equivalence, we are able to prove that the separable metric spaces are exactly the metric spaces on which these regrets can be minimized with respect to the family of all probability distributions with continuous mean-payoff functions.
We consider a generalization of stochastic bandits where the set of arms, $cX$, is allowed to be a generic measurable space and the mean-payoff function is locally Lipschitz with respect to a dissimilarity function that is known to the decision maker
. Under this condition we construct an arm selection policy, called HOO (hierarchical optimistic optimization), with improved regret bounds compared to previous results for a large class of problems. In particular, our results imply that if $cX$ is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally continuous with a known smoothness degree, then the expected regret of HOO is bounded up to a logarithmic factor by $sqrt{n}$, i.e., the rate of growth of the regret is independent of the dimension of the space. We also prove the minimax optimality of our algorithm when the dissimilarity is a metric. Our basic strategy has quadratic computational complexity as a function of the number of time steps and does not rely on the doubling trick. We also introduce a modified strategy, which relies on the doubling trick but runs in linearithmic time. Both results are improvements with respect to previous approaches.
We consider a (sub) critical Galton-Watson process with neutral mutations (infinite alleles model), and decompose the entire population into clusters of individuals carrying the same allele. We specify the law of this allelic partition in terms of th
e distribution of the number of clone-children and the number of mutant-children of a typical individual. The approach combines an extension of Harris representation of Galton-Watson processes and a version of the ballot theorem. Some limit theorems related to the distribution of the allelic partition are also given.
We consider a system of particles with arms that are activated randomly to grab other particles as a toy model for polymerization. We assume that the following two rules are fulfilled: Once a particle has been grabbed then it cannot be grabbed again,
and an arm cannot grab a particle that belongs to its own cluster. We are interested in the shape of a typical polymer in the situation when the initial number of monomers is large and the numbers of arms of monomers are given by i.i.d. random variables. Our main result is a limit theorem for the empirical distribution of polymers, where limit is expressed in terms of a Galton-Watson tree.
