Jean-Christophe Blancon

Dr Wanyi Nie

Dr Amanda J Neukirch

Dr Gautam Gupta

Dr Sergei Tretiak

Dr Laurent Cognet

Dr Aditya D Mohite

Dr Jared J Crochet
email: jcrochet@lanl.gov

Dr J.-C Blancon

The effects of electronic impurities and electron-hole recombination dynamics on largegrain organic-inorganic perovskite photovoltaic efficiencies

Keywords: carrier dynamics, electronic impurities, organic-inorganic perovskite, photovoltaic

Organometallic perovskites have attracted considerable attention after promising developments in energy harvesting and other optoelectronic applications. However, further optimization will require a deeper understanding of the intrinsic photo-physics of materials with relevant structural characteristics. Here we investigate the dynamics of photogenerated charge carriers in large-area grain organometallic perovskite thin films via confocal time-resolved photoluminescence spectroscopy. It is found that the bimolecular recombination of free charges is the dominant decay mechanism at excitation densities relevant for photovoltaic applications. Bimolecular coefficients are found to be on the order of 10 -9 cm 3 /s, comparable to typical direct-gap semiconductors, yet significantly smaller than theoretically expected. We also demonstrate that there is no degradation in carrier transport in these thin films due to electronic impurities. Suppressed electron-hole recombination and transport that is not limited by deep level defects provide a microscopic model for the superior performance of large-area grain hybrid perovskites for photovoltaic applications.

Introduction

Direct band gap semiconductors with low defect densities, such as single crystalline GaAs, are the epitome of high efficiency optoelectronic devices. However these materials are obtained using expensive high temperature crystal growth techniques such as molecular beam epitaxy. Consequently, there has been a constant search over the last two decades for new materials that can be obtained using scalable solution based strategies. However most solutionprocessed materials are plagued with polydispersity, lack of crystallinity, and unacceptable levels of electronic defects. Over the past few years, solution-process organometallic perovskite semiconducting materials (mainly CH 3 NH 3 PbI 3 and CH 3 NH 3 PbI 3-x Cl x ), which promise low-cost solution processing together with favourable intrinsic properties for optoelectronic applications, have attracted a significant research effort after initial demonstrations of promising performances in photovoltaics [1,2] , light emitting diodes [1,3] , lasing [4][5][6] . However, several challenges remain towards further improvements of performance, reproducibility, and reliability of these devices under continuous operating conditions [1] . Addressing those matters, inevitably, requires a fundamental understanding of the intrinsic photo-physical properties of bulk perovskites at conditions relevant for application.

Up to date, the details of charges carrier dynamics in organometallic perovskites are still under debate. More precisely, there is a lack of understanding of local intrinsic kinetics of photoexcited carriers in perovskite thin films, serving as active layers in solar cells, at device operating conditions. This knowledge requires replicating solar illumination excitation densities under broadband spectral excitation. Indeed, most investigations of light emission have been conducted at narrow spectral bandwidth, which may not capture the larger picture relevant for practical solar cell devices. Furthermore, due to sample inhomogeneities, local spatial probing of optical properties is the best approach to relate structural characteristics to charge carrier dynamics. In particular, for future improvements of device performance, it is important to decipher the dynamics of charge carriers in organometallic perovskites at photo-excitation densities close to operating conditions at the microscale.

Despite several attempts to correlate the optical properties and photo-excited carrier dynamics within a given material morphology [2,[7][8][9] , only a few reports have explored optical properties at the micro-scale or at the single grain size in thin films for practical applications [2,9] . Two of the major hindrances to such studies have been low crystalline quality and small grain sizes. On the other hand, there have been several attempts to investigate the optical properties and dynamics of carriers in bulk perovskite thin films, which consists of ensembles of grains.

Typically this is performed at room temperature, using light emission [2,[10][11][12][13][14][15][16][17][18] and absorption [11,14,[19][20][21][22][23] characteristics to develop photophysical models. The first set of studies, hypothesizing a mixed response of excitonic and free-carrier photo-excitations, suggested extraordinary charge carrier diffusion lengths derived from nearly mono-exponential photoluminescence decays [10,11] . Others have observed mixed monomolecular and bimolecular mechanisms which were attributed to the competition of trap assisted and free carrier recombination [12,14,15,18,20] . These results are in sharp contrast to what is expected in conventional semiconducting direct band-gap materials with high crystallinity, which at room temperature should display a pure bimolecular recombination of free charges carriers [24,25] and have never been observed. Monomolecular decay of photoluminescence is only observed when electronic defects or excitonic effects dominate.

The growth of organometallic perovskite crystals has recently reached a milestone with the synthesis by solution processing of thin films with large crystalline grain structures [2] . Moreover, these large grains have been reported to be free of deep level electronic impurities resulting in near intrinsic transport properties as well as stable and reliable solar cell performances. For these reasons, they offer a new opportunity to access the local intrinsic photophysical properties of organic-inorganic perovskite.

In this investigation, we unify the micro-scale dynamics of photo-carriers and macroscale solar cell performance of large grain methylammonium halide perovskite thin films. Most importantly, we demonstrate a pure bimolecular recombination through confocal time-resolved photoluminescence spectroscopy in large crystalline grains over a broad spectral range at excitation densities relevant for photovoltaic applications. This is a textbook signature of defectfree bulk direct band gap semiconducting materials, where the bimolecular recombination of photo-generated electrons and holes via radiative [24,25] and non-radiative [26] decay are prevailing relaxation processes. By comparing bimolecular coefficients computed within the Langevin model and derived from photoluminescence decays, we infer that recombining photogenerated carriers do not lead to major losses in photovoltaic devices because of efficient charge extraction.

Additionally, measurements of an operating solar cell device under open circuit conditions (where carriers are not extracted from the cell) demonstrate that bimolecular recombination remains the sole decay channel of photo-generated charges and any defects formed during device fabrication are minor. These results demonstrate that solution cast large-area organic-inorganic perovskites have a technological potential in optoelectronics comparable to conventional semiconducting systems, and superb photovoltaic performance can be attributed to suppressed electron-hole recombination and negligible deep level electronic impurities.

Results and Discussion

Unambiguous bimolecular recombination in large grain perovskites

Thin films of crystalline grains of mixed halide perovskite CH 3 NH 3 PbI 3-x Cl x synthesized via a hot-casting method were used in this study [2] . The optical properties and carrier dynamics were investigated by micro-scale confocal spectroscopy and time-resolved photoluminescence (PL) which probes local regions in thin films used for solar cell applications (Note S1). The microscale approach locally interrogated, with micrometer resolution (~ 1 𝜇m 2 ), the optical response of a single large-area grains (> 100 µm in diameter) residing in a ~300 nm thick perovskite thin film deposited on a glass substrate (Figure 1a, inset). The inner region of the large-area grain is relevant for photovoltaic applications as grain-boundaries in these large grains have a minor impact on the overall device performance [2] . Figure 1a shows the absolute absorption coefficient and normalized photoluminescence spectrum measured confocally within a single large-area grain. This was obtained by correcting for multiple reflections occurring at the air/film and film/substrate interfaces and we deduced an absorption coefficient (α) of ∼ 2.5×10 ) cm -1 at the band-edge in the near infrared that displays an increase of an order of magnitude over the visible spectral range. From these results we also extracted the real and imaginary parts of refractive index (Figure S1 and Note S2) demonstrating an acceptable agreement with our DFT calculations (Figure S2 and Note S3) and other recent studies [21][22][23]27] . The emission and absorption band-edge, observed at 1.626±0.002 eV (763 nm) and 1.62±0.01 eV (765 nm) respectively, display a relatively small Stokes shift at ambient conditions (Figure 1a). We emphasize the importance of determining the absolute absorption coefficient for correctly interpreting the dynamics of carriers and the quantum efficiency of solar cell devices through accurate estimates of the carrier excitation density (Figure S1). Accurate determinations of α also allow for comparing the photo-excited carrier density (𝑁 + ) achievable in our time-resolved photoluminescence (TRPL) experiment to 𝑁 + obtained in a planar solar cell under standard AM1.5 global illumination. With our TRPL system, featuring a wavelength-tunable 6-ps-pulsedmonochromatic laser excitation at 1 MHz, one solar irradiance translates into a lower limit of 𝑁 + = 6.5×10 /0 cm -3 , and further reaching values above 8×10 /0 cm -3 when considering the device structure geometry.

For quantitative understanding and measurements, time-resolved photoluminescence was then performed on the same grain as the absorption and photoluminescence measurements using time-correlated single-photon counting (see details in Note S1). Figure 1b shows the timedependent photoluminescence intensity at the band-edge after excitation at 690 nm (1.80 eV) generating an equivalent excitation density of less than 4 suns of irradiance (𝑁 + = 2.8×10 /2 cm - 3 ). The decay kinetics was modelled with a numerical solution to the first order rate equation describing the recombination of valence and conduction band carriers coupled to a least squares optimization of the rate constant. Briefly, a focused laser pulse of photon energy ℏ𝜔, described by the charge density generation rate 𝐺 = 6 7ℏ8 𝐴𝛼 (where 𝑃 is the laser power, 𝑆 is the spot size, A the thin film absorbance), creates a non-equilibrium distribution carriers in the valence and conduction bands (see also Figure 4). These carriers quickly relax to the band-edge on a picosecond-time scale [11,20] , which is unresolved in our experiments. Subsequently, the recombination of carriers is modelled by a pure band-to-band or bimolecular recombination, 𝑁 = 𝐺 -𝛾 ? 𝑁 @ , of the non-equilibrium carrier density 𝑁(𝑡) (assuming equivalent photo-excited carrier density in the valence and conduction bands) and described by a single bimolecular coefficient 𝛾 ? that includes both radiative and non-radiative processes [24][25][26] . Here the intensity of light emission is given as: 𝐼 EF ∝ 𝑁 @ , as will be demonstrated later. An example of the accuracy of this model is shown in Figure 1b where an excellent fit is displayed for the only free parameter 𝛾 ? = 5.3x10 -9 cm 3 /s. Interestingly, this bimolecular recombination coefficient is order(s) of magnitude larger than previous reports on smaller-grain-structured organometallic samples [6,9,12,14,15,18,20] , and comparable to that of typical direct-gap semiconductors [28,29] . Again, this result attests both the crystalline quality of our samples and that the photo-excitation of free charge carriers is the dominating kinetic process. However, 𝛾 ? is most likely influenced by photon recycling because of a small photoluminescence Stokes shift and a large absorption coefficient [25,30,31] . We therefore expect this value to be a lower bound of the recombination rate and further enhancements may be made in planar perovskite devices by limiting the angle of photon emission [32,33] . The determined recombination rate at this excitation energy (~1.8 eV) corresponds to an approximate 7 ns effective electron-hole recombination lifetime, and this result unambiguously demonstrates that free carriers, are the main photo-excitation in these materials. This is in agreement with recent reports of very small exciton binding energies (a few meV) at room temperature [21,34] , and possible ultra-fast exciton dissociations due to strong screening the electron-hole interaction by optical phonons and collective rotational motions of the organic cations (CH 3 NH 3 ) [35,36] .

Density dependent emission intensity and dynamics

Investigating the dependence of the recombination dynamics on the photoexcitation density is necessary to fully understand the relaxation processes of excess free charge carriers. In general, the photoluminescence intensity for electron-hole pair recombination is expressed as 𝐼 EF ~𝑁I 𝑁 J .

Photoluminescence can also arise from recombination of an electron or hole with a charged shallow defect such that the charge densities should be re-defined as 𝑁 I (𝑡) = 𝑁(𝑡) + 𝑁 L in the case of n-doping and 𝑁 J 𝑡 = 𝑁 𝑡 + 𝑁 L in the case of p-doping. The equilibrium free carrier density 𝑁 L , encompassing n-type or p-type unintentional doping, is related to intrinsic defects.

Theoretical investigations have associated this type unintentional doping to mainly Frenkel-type point defects, including vacancies, interstitials, and substitutions, and demonstrated that defects with small formation energies are all shallow trap states due the ionic nature of the material [37,38] .

In particular, donors and acceptors act as both a source of doping and recombination centres (non-radiative) for excess carriers. A donor (acceptor) is a shallow level impurity which has an energy level just below (above) the conduction (valence) bands and can easily transfer an electron (hole) to the band, such that 𝐷 + ⇄ 𝐷 O + 𝑒 Q (𝐴 + ⇄ 𝐴 O + ℎ O ). On the other hand, deep level impurities are trap states and are composed of defects with large formation energies, however are much lower in density. Moreover, Schottky-type, neutral vacancy pair defects of PbI 2 and CH 3 NH 3 I, are presumably abundant in solution-cast growth and are neutral de-localized states within the bands that do not contribute to doping. These defects are not expected to be major (non-radiative) recombination centres for carriers [37] . Our preliminary measurements of field-effect transistor responses, that will be reported elsewhere, suggests a slight n-type doping in thin films grown by the method above. Thus, in the case of defects in the conduction band, the time-dependent photoluminescence intensity becomes 𝐼 EF t ~𝑁@ + 𝑁𝑁 L , and in the steady state limit 𝐼 EF ~𝑁+ @ + 𝑁 + 𝑁 L . These two regimes of light emission in the steady state, free carrier and unpassivated defect assisted emission, were clearly identified by performing an excitation intensity dependent integrated photoluminescence study, Figure 2. This allowed for an estimate of an equilibrium density associated with unintentional doping due to intrinsic defects of 𝑁 L ∼ 2.5×10 /0 cm -3 . This is equivalent to ~0.3 sun irradiance. For an excitation density of 𝑁 + > 𝑁 L , the regime in which solar cells operate, the photoluminescence intensity scales as 𝐼 EF ~𝑁@ where excess free carriers mostly undergo bimolecular recombination after having passivated the equilibrium background charge.

Following these steady state measurements, the dynamics of photo-excited carriers were investigated via TRPL over a relatively broad range of excitation densities at photon energy 1.8

eV (Figure 3). A general model of the carrier dynamics considering defect levels (trap states)

probed by TRPL is given by the first-order rate equations:

𝑁 = 𝐺 -𝛾 ? [𝑥𝑁 @ + 1 -𝑥 𝑁𝑁 L ] -𝛾 ↓ 𝑁 + 𝛾 ↑ 𝑁 Z 𝑁 Z = 𝛾 ↓ 𝑁 -𝛾 ↑ 𝑁 Z -𝛾 [ 𝑁 Z (1)
where all quantities are defined in the schematics and captions of Figure 4, and 𝑥 (between 0 and 1) is determined from the static PL results (see previous paragraph and Figure 2). ), where 𝑘 i is the Boltzmann constant and T the sample temperature (295 K). The TRPL kinetics were fit independently using a numerical solution to equations (1) (see results in Figure S3), yielding excellent fits with coefficients of determination R 2 exceeding 0.95, with the exception of the kinetics associated with 𝑁 + = 0.4×10 /0 cm -3 for which R 2 = 0.64 due to low signal-to-noise ratio at low photon collection yields in these experiments. For an excitation density of 𝑁 + < 5×10 /0 cm -3 , the photoluminescence decays tend toward a more mono-exponential response mixed with the bimolecular process of recombination in agreement with previous reports [10,12,14] ; we label this as the "mixed regime". On the other hand, at higher excitation density, 𝑁 + > 5×10 /0 cm -3 , the kinetics yield a pure bimolecular recombination behaviour ("bimolecular regime"). Figure 3b,c present the photo-excitation density dependence of the trap-state energy level (Δ𝐸 Z ), the maximum occupation of both the band-edge (𝑁 lmn ) and trap state (𝑁 Z lmn ), and the ratio 𝜏 ↓ /𝜏 ? deduced from the global fitting procedure. Moreover, following the high quality fits with equations (1), we hypothesize that Auger recombination is negligible in the range of excitation density explored here, 𝑁 + < 10 /p cm -3 , which is in agreement with the literature [12,18] .

All parameters directly related to the nature of the trap state 𝑁 Z (Δ𝐸 Z , 𝑁 Z lmn , τ ↓ /𝜏 s ) present a clear change in behaviour at the threshold value 𝑁 tu ∼ 5.5 ± 1.0×10 /0 cm -3 . This is identified as the photo-excitation density for which shallow trap states (Δ𝐸 Z < 25 meV) are filled thus becoming transparent to carriers. The effective defect density in our large-area grains is somewhat lower than previous report in bulk perovskite materials [14,15] and comparable with a recent report on locally enhanced photo-emission in a micro-structured or Cl-enriched materials [9,39] . Also, 𝑁 tu is slightly larger than the unintentional doping density 𝑁 L measured in the static regime, which suggests that either non-doping neutral defects act as non-radiative recombination centres or n-and p-type intrinsic defect states partially compensate the static PL signal while TRPL only probes defects related to the minority carriers [37,38] . Concomitant to the switching of the trap-assisted decay path from shallow trap states (Δ𝐸 Z < 25 meV) to deep trap states (Δ𝐸 Z > 100 meV), we observe a strong reduction of the maximum occupation of the defect level 𝑁 Z lmn as well as an increase of the time constant ratio 𝜏 ↓ /𝜏 ? above unity. The latter implies that the excess carriers preferentially decay through the bimolecular recombination pathway for 𝜏 ↓ /𝜏 ? > 1, where 𝜏 ? becomes the smallest effective lifetime. The former is explained by the lack of carrier exchange between the band-edge and trap state per the Boltzmann distribution, where deep trap states should be unoccupied at room temperature (Figure S4). From this we describe a physical picture where for Δ𝐸 Z < 25 meV, a carrier occupying 𝑁 Z decays non-radiatively at a rate 𝛾 t but has also a chance to repopulate the bandedge with a rate 𝛾 ↑ , whereas, for Δ𝐸 Z > 100 meV, a carrier has a negligible probability to transit from the trap-state to the bandedge (𝛾 ↑ ~ 0) and 𝛾 ↓ is the rate dominating the trap-assisted decay pathway (see also Figure S3c,d).

To summarize these results, in the mixed regime (N + < N tu ) the photo-excited carriers decay by undergoing both trap-assisted non-radiative recombination (dominant mechanism) and bimolecular recombination, whereas in the bimolecular regime (N + > N tu ) the former decay pathway is either strongly damped (weak decay to deep trap states) or totally prohibited (Figure 3d). The latter observation is in agreement with the low density of deep trap states in this material, since they require much higher energy to be formed [37,38] . From the defect density we infer that large-area-grain structured solar cells operate in the bimolecular regime (at least in the spectral range around 1.8 eV) as reported in Figure 1b. This behaviour is different than previous studies reporting solar cell operation in the mixed regime involving trap-assisted recombination and bimolecular recombination to dark carriers due to doping [15,39] and the pure bimolecular regime being reached at tens of solar irradiance [15] .

Photo-physics over broadband light excitation

In order to gain a more complete understanding of the photo-physics in solar cells, we also examined the photoluminescence kinetics over a broad spectral range of excitation energies, 1.8 and 2.7 eV (Figure 5a-c), while keeping the excess carrier density close to 1 solar irradiance.

First, the material was investigated in the bimolecular regime (Figure 5a, see also Figure 1b) and a pure bimolecular recombination process was observed with negligible trap-assisted decay to deep trap states (Figure 5c, black square symbols). The quality of the fits were characterized by R 2 ≥ 0.8 and were mainly impaired by the inevitable noise in the data at such low photon flux densities (Figure S5). The bimolecular coefficients were found to range from ≈ 5.3×10 Qz to less than 0.5×10 Qz cm 3 /s (Figure 5b, see also Figure S5). The error in the determination of these values is mainly related to the maximum 5% error on the absorption measurements. As shown in Figure 5b the bimolecular recombination coefficient depends strongly on the magnitude of the absorption coefficient and shows an anti-correlated behavior with the absorption coefficient.

Next, we investigated the time-resolved photoluminescence response in the mixed regime and fit the data with equations (1). In contrast to the bimolecular coefficient showing a strong spectral dependence, the trapping rate shows little spectral dependence (Figure 5c, blue round symbols), with a mean value of ∼ 4×10 { s -1 . This suggests that the trap states probed over the whole spectral range of photo-excitation are of similar nature.

Finally, the photoluminescence of several large-area grains under monochromatic excitation was measured over a broad spectral range. Within a single large grain, a standard photoluminescence excitation (PLE) map and the corresponding integrated PL normalized to the absorption coefficient (equivalent to probing the relative change of the quantum yield) are displayed in Figure 5d. Fluctuations in intensity are in the maximum 5% error related to measurements of the absorption coefficient. The emission spectrum for each excitation energy was acquired by keeping the photo-excited density of carriers at approximately 1 sun of irradiance in order to reflect the conditions of illumination in photovoltaics. Over the entire range, no significant shift or broadening of the emission peak was observed, whereas a strong reduction of the PL intensity occurs towards the blue spectral region following a similar anti-correlated behaviour in comparison to the absorption profile as observed for the bimolecular coefficient.

The spectral profiles of the quantum yield and kinetic parameters are possibly explained by an increased amount of trapping events, that lead to an overall reduction in 𝛾 ? due to a dominating but slower non-radiaZtive bimolecular decay, taking place at high energy during intra-band relaxation of carriers (Figure 6, middle-right panel). This hypothesis was drawn from both the similar nature of trap states across the visible spectrum and the broadband absorption mechanisms as described by Even et al. [35,40,41] (also sketched in Figure 6, left panel).

Qualitatively, we describe the intra-band relaxation in reciprocal space via the differential equation: 𝑛(𝑘) = -𝑃 } 𝑛(𝑘), with 𝑛(𝑘) the carrier density at wave vector k and P i the probability of trapping carriers in k-space (assumed to be constant). Using the band dispersion relation 𝐸 = ℏe @• * along the R-M direction in k-space, where the 𝑚 * is the effective mass [42,43] , the carrier density at the R-point following excitation at E(k) is proportional to exp [-𝑃 } 2𝑚 * 𝐸/ℏ], which yields a reasonable qualitative fit to the integrated PL (Figure 5d, dashed line). From above spectral dependent TRPL results, we estimated an upper limit of the trap saturation threshold density N th over a broad spectral range (Figure S6), demonstrating that passivation of shallow trap states was observed at values below solar excitation density for photons energies below ~ 2 eV, however at slightly higher values above 2 eV. This observation corroborates the higher probability for carriers generated with blue-light excitation to undergo trap-assisted recombination as they are exposed to a higher density of trap states, both shallow and deep, distributed along the bands in k-space while undergoing intra-band relaxation (schematic in Figure 6). In addition to this effect, we can expect surface trap states, self-trapped charges or self-trapped excitons, originating from electron-phonon coupling at the thin film surface [44] , to be prevalent under blue-light excitation which probes a more shallow layer of the thin film (see also Figure S7).

Solar cell performance

To confirm that trap-assisted recombination is not an influential process in a high qualityoperating device, we investigated the performance of a planar solar cell (see inset in Figure 7b)

with the same material active region as above over a wide range of illumination irradiance. We also probed the recombination of photo-generated carriers by measuring 𝑉 ƒ" as a function of light intensity, Figure 7a. In this measurement, all of the carriers recombine in the active layer because there is no net current flow. Here the slope of 𝑉 …I vs irradiance on a linear-log scale determines the so-called ideality factor 𝑛. More precisely, 𝑛𝑘 i 𝑇/𝑞 is the slope of the linear curve where 𝑞 the elementary charge. When 𝑛=1 the measurement suggests that bimolecular recombination is the dominating decay mechanism in the active layer [45] . Larger values up to 𝑛=2 indicate trap-assisted recombination is prevalent and the material has a relatively large density of deep level electronic impurities that mask bimolecular recombination. For this device and material we found n ∼1.1 where the small deviation from an ideality of 1 is expected to result from the presence of a few grain boundaries under the contact and illumination area [2] .

This confirms that bimolecular recombination is the dominating dynamics for carriers in this material at macroscopic scale, as well as that decay of carriers to deep electronic defects is minor and does not alter the overall transport properties of devices. Moreover, both the micro-and macro-scale carrier dynamics results are reflected in the external quantum efficiency under one sun illumination that yields values larger than 80% above the band-gap, Figure 7b. This clearly suggests few losses after absorption and nearly 100% internal quantum efficiency for single crystals, in agreement with recent studies [21,46,47] .

Microscopic origins of photovoltaic efficiency

Knowledge of the underlying physics of shallow trap passivation, bimolecular recombination, and spectral variations of the photoluminescence kinetics and intensity are important for understanding the transport properties of large grain perovskite semiconductors. Using Langevin theory describing the recombination of free carriers in diffusion limited semiconductors, the spectral and excitation density dependence of the effective diffusion constant of carriers can be derived as 𝐷 = ˆ‰ )Š‹ OE (Figure S5), using the Onsager radius

𝑟 Ž = e • • '' e f g
, where k C is the Coulomb constant, 𝜀 + the vacuum permittivity, and 𝜀 " = 35 the static dielectric constant [48] (see details in Note S4). Values of D are in the range ~0.1-2.5×10 -3 cm 2 /s depending on excitation energy, with similar spectral dependence as 𝛾 ? . From the values of diffusion constant, at room temperature, we expect minority carrier mobility in the range ~10 -1 -10 -2 cm 2 /V.s, with a similar spectral profile as the diffusion constant and 𝛾 ? . These values are of same magnitude as those reported for bulk NH 3 CH 3 PbI 3 (see refs. [49,50] and literature therein), however much smaller than what is expected theoretically [49,51] . Using derived mobilities from the bi-molecular coefficients, the Nernst-Townsend-Einstein relation would yield un-physical sub-fs elastic scattering mean free times, assuming effective masses reported in the literature [42,43] . Thus, we infer in these systems there may be an effective mass enhancement due to electron-phonon coupling linked to polaronic states [52][53][54] , or carrier localization effects [36] , mostly caused by an orientational disorder of organic cation. In fact, it is understood that the orientational disorder of the organic cation (methylammonium ions) in the lattice is altered by polarized light, which can give rise to local structural distortions that cause changes in the electronic and vibrational landscapes of perovskites [52,[55][56][57][58][59] . For example, this may be reflected in the recent observation of giant photoinduced dielectric constants [60] and Glass coefficients [55] , that increase linearly with broadband excitation intensity. Since these effects increase with increasing excitation energy the overall screening of charge carriers may become more effective reducing the probability of recombination, which is reflected by reductions in 𝛾 ? and D.

Further, lower-limit values of mobility predicted from first principle (140 cm 2 /V.s for holes and 466 cm 2 /V.s) [49] yield a Langevin bimolecular coefficient [61] of 𝛾 • = 3.1×10 Q0 cm 3 /s.

This provides a lower limit for the perovskites transport figure of merit which reflects a suppression of electron-hole recombination, ˆ‰ ˆ-∼ 1.7×10 Q) . Using typical mobilities in our solar cells [2,62] , ~ 5 cm 2 /V.s or more for 15% power conversion efficiency, we find 𝛾 • = 5.2×10 Q{ cm 3 /s and ˆ‰ ˆ-< 1×10 Q@ . This implies that perovskite solar cells fabricated in this fashion operate in the non-Langevin recombination regime, which is necessary for efficient photovoltaic devices with low charge carrier mobilities in order to prevent significant losses due to recombination competing with the charge extraction processes [61] . In other words, the lifetime of the charge carriers must be longer than their transit time in the intrinsic electric field in order to obtain efficient energy conversion in solar cells. This can be reformulated in terms of a mobility lower limit as 𝜇 > ˜™ˆ‰š J›oe , where 𝑉 s• is the built-in electric field potential (𝑉 s• = 0.78 V in our solar cells [62] ) with thickness d=450 nm. We estimate 𝜇 > 0.01 cm 2 /Vs is necessary for efficient energy conversion. These conditions are in good agreement with our TRPL analysis, and fulfilled in our large-area grain perovskite material. This rational further explains the high performances observed in perovskite-based solar cells beyond having low deep level defect densities.

Conclusions

Our findings of pure bimolecular recombination are in stark contrast with previous reports on bulk organometallic perovskite materials showing nearly exponential mono-molecular processes at equivalent carrier densities or a combination of both bimolecular recombination and trapassisted relaxation [10,12,14,15,39,63] . The origin of this discrepancy may result from small grains where crystal boundaries and defects result in dynamics that deviate from bimolecular recombination because of monomolecular trap assisted recombination [2] , Figure 4b and Figure S8. Notably, the observation of a pure bimolecular decay is unique for semiconducting solutionprocessed materials at this excitation density as trap-assisted or exciton recombination (both mono-molecular kinetics) are usually dominating processes. Most importantly, our findings bridge the gap between the micro-scale optical properties and macro-scale solar cell performance of crystalline methylammonium halide thin films. These results clearly demonstrate that devices based on solution processed thin film semiconductors can be operated in regimes free of impurities that degrade transport and alter optical properties. More broadly this work asserts the rapid progress in organic-inorganic perovskite based optoelectronics where experimentally determined intrinsic properties represent a clear departure from macroscopic ensembles of nanoparticle systems that are plagued by inhomogeneity and defects. Nevertheless, the mobility of charge carriers in perovskites remains significantly lower than conventional semiconductors, reflecting transport may be similar to that in organic systems without large deep level defect densities associated with multiple interfaces. Further understanding of the details of charge carrier localization and mobilities associated with the dynamic perovskite lattice [64] will aid in providing a physical picture of transport in these hybrid systems and pave the way for improved stability and performance in optoelectronic devices. perovskite (from ref. [41] ) during: photoexcitation (left), relaxation in the mixed regime (middle), and relaxation in the bimolecular regime (right). Optical excitations generate free carriers in the valence (E 1/2,g ) and conductions (E 1/2,u ) bands which relax towards the R point where the emission takes place. The effects of electronic impurities and electron-hole recombination dynamics on largegrain organic-inorganic perovskite photovoltaic efficiencies

  After photogeneration (G), the excess of free carriers (N) at the band-edge can: undergo bimolecular recombination (𝛾 ? 𝑁 @ ), exchange densities with trap states (-𝛾 ↓ 𝑁 + 𝛾 ↑ 𝑁 Z ), and relax by undergoing trap-assisted non-radiative recombination (-𝛾 [ 𝑁 Z ); see also the schematic in Figure2d. Here, we define the effective lifetime of free charge recombination 𝜏 ? = 𝛾 ? 𝑁 + Q/ , and characteristic lifetimes for the trap-assisted decay as 𝜏 ↓ = 𝛾 ↓ Q/ and 𝜏 [ = 𝛾 [ Q/ . The exchange rates between the band-edge and trap states are directly related by the Boltzmann distribution defined from their energy splitting (Δ𝐸 Z ): 𝛾 ↑ = 𝛾 ↓ exp (-

Figure 1 .

 1 Figure 1. (a) Absolute value of the absorption coefficient (black) and the PL spectrum (red).

Figure 2 .

 2 Figure 2. Photoluminescence intensity as a function of the photo-excitation density. Dashed

Figure 3 .

 3 Figure 3. (a) Time-correlated single photon counting histogram of the PL (darken colors) and

Figure 4 .

 4 Figure 4. (a) The dynamics of light emission is modelled by an excitation density generation rate

Figure 5 .

 5 Figure 5. (a) Time-correlated single photon counting histogram of the PL (darken colors) and

Figure 6 .

 6 Figure 6. Schematics of the band structure of the high-temperature pseudo-cubic phase of

Figure 7 .

 7 Figure 7. (a) Open circuit voltage as a function of irradiance (filled black circles). The line is a

Acknowledgements

This work was supported the Los Alamos National Laboratory LDRD program. L.C. acknowledges additional support from INCa-Canceropole GSO.

Received: ((will be filled in by the editorial staff))

Revised: ((will be filled in by the editorial staff))

Supporting Information

Supporting Information is available from the Wiley Online Library or from the author.

Competing financial interest

The authors declare no competing financial interests. generated carriers. (b) Spectrally resolved absolute value of the external quantum efficiency measured on a full device. The inset is a schematic of the device geometry.


Claire Daguin

Philippe Borsa
email: borsa@crit.univ-montp2.fr

Genetic characterization of Mytilus galloprovincialis Lmk. in North West Africa using nuclear DNA markers [MYTILUS GALLOPROVINCIALIS IN NW AFRICA]

Keywords: mussel, Mytilus galloprovincialis, Mytilus edulis, northwestern Africa, polymerase chain reaction, intron, size polymorphism, geographic structure

The genetic relationships among Mytilus galloprovincialis populations over their range in the northeastern Atlantic and the western Mediterranean were investigated using polymerase chain reaction (PCR)amplified nuclear DNA markers. We used long-range polyacrylamide gel electrophoresis for characterizing an intron-length polymorphism at the actin gene locus mac-1 in Mytilus. Sharp resolution was obtained with this technique, which revealed a high level of size polymorphism. It also allowed to discriminate between M. galloprovincialis and M. edulis.

Mytilus populations sampled on the northwestern African coasts (Morocco, Western Sahara, and Mauritania) were M. galloprovincialis as formerly suggested on the basis of morphology and geographic location. A sample of the Padstow mussel reported as M. galloprovincialis according to allozyme and morphological data exhibited allele frequencies that were rather intermediate between M. galloprovincialis and M. edulis. Slight heterozygote deficiencies were possibly present within each sample as usually reported in bivalve populations. Additional PCRs using a second pair of primers showed that this could not be explained by the occurrence of null alleles that would have resulted from mis-priming during DNA amplification. Significant differentiation was observed between M. galloprovincialis from northwestern Africa and the reference M. galloprovincialis sample from the Mediterranean Sea, a result that is consistent with previous allozyme-and mitochondrial DNA-based reports of an abrupt genetic change between northeastern Atlantic / Alboran Sea and western Mediterranean M. galloprovincialis populations.

Introduction

The mussel Mytilus galloprovincialis Lmk. is present in the northeastern Atlantic from the shores of the Irish Sea to southern Spain and in the western Mediterranean, the Tyrrenian Sea, the Adriatic Sea, the Aegean Sea and the Black Sea (Lubet et al., 1984;Karakousis and Skibinski, 1992;Seed, 1992). Lubet et al. (1984) have also reported the presence of Mytilus that is morphologically M. galloprovincialis in northern Africa.

The closely related blue mussel, M. edulis L., has a more boreal range.

M. galloprovincialis and M. edulis occur sympatrically from the Irish Sea to the Biscay coast of France or even northern Spain (Lubet et al., 1984;Coustau et al., 1991;Seed, 1992;Gardner, 1994;Sanjuan et al., 1994).

Mytilus populations in this area exhibit a range of patterns of morphological and genetic intergradation (Skibinski and Beardmore, 1979;[START_REF] Beaumont | Electrophoretic and morphometric criteria for the identification of the mussels Mytilus edulis and M. galloprovincialis[END_REF]Coustau et al., 1991;[START_REF] Mcdonald | Allozymes and morphometric characters of three species of Mytilus in the northern and the southern hemispheres[END_REF][START_REF] Mcdonald | Allozymes and morphometric characters of three species of Mytilus in the northern and the southern hemispheres[END_REF]Gardner, 1994) that has been interpreted as the result of extensive hybridization between the two species.

Here we conducted a genetic analysis of Mytilus samples from northwest Africa using the intron-length polymorphism at the actin gene locus mac-1 [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF] as a marker. These samples were compared to reference M. galloprovincialis and M. edulis samples from, respectively, the western Mediterranean and Denmark (Coustau et al., 1991;[START_REF] Mcdonald | Allozymes and morphometric characters of three species of Mytilus in the northern and the southern hemispheres[END_REF]Seed, 1992) and to a sample of the 'Padstow' (M. galloprovincialis-like) mussel from Polzeath Bay in the Irish Sea (Skibinski et al., 1983;[START_REF] Beaumont | Electrophoretic and morphometric criteria for the identification of the mussels Mytilus edulis and M. galloprovincialis[END_REF]Seed, 1992[START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF] in order to assess their genetic relationships to other mussel populations in the area. We report that the northwest African Mytilus populations, which occur as far south as southern Western Sahara and even Mauritania, are M. galloprovincialis, but these also exhibited genetic differences with western Mediterranean M. galloprovincialis.

Materials and methods

Samples of Mytilus spp. were collected in 1995 and 1996 in Denmark, South-West Britain, southern France, Morocco and Western Sahara (details given in Fig. 1). The sample from Denmark is M. edulis according to data from former allozyme studies on samples collected in the area (Coustau et al., 1991;Seed, 1992). Similarly, the sample from southern France has been assigned to species M. galloprovincialis (Coustau et al., 1991). We used these two samples as references for either species in subsequent comparisons with the other samples. After their collection, the mussels were either preserved alive on ice (samples from SW Britain and southern France), or frozen (samples from Morocco and Western Sahara) or in alcohol (sample from Denmark) and sent to Laboratoire Génome et Populations in Sète until they were processed as described in the following. Two additional individuals identified as M. galloprovincialis on the basis of their morphology were collected amidst dense Perna picta Born settlements in Cansado, Mauritania (Fig. 1). These were preserved in 90% ethanol until processed.

For DNA extraction, 1-3 mg adductor muscle tissue was dissected from each individual and digested at 55°C overnight in a microfuge tube containing 6% Chelex (Biorad, Richmond CA, USA) and 12 U proteinase K in 350 µl 0.1 mM Tris / 0.01 mM EDTA, pH 8.0 buffer. The samples were then vortexed, heated at 95°C for 20 min and centrifuged at 3500 g for 5 min.

The supernatant was stored at -20°C until it was used as the DNA extract for polymerase chain reaction (PCR). Specific PCR primers (forward 5'-CGT CTA GCG TAG TAC TTA AAT TG-3' and reverse 5'-CGA AAA TTG TAG TCT AGT TTT GTG-3') were designed from the alignment of 6 partial sequences of Intron-1 of the actin gene mac-1 [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF]M. Ohresser, unpublished). The length-polymorphism reported at mac-1 Intron 1 is due to large (28-65 base pairs (bp)) insertions / deletions and short gaps in the sequences [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF]M. Ohresser, unpublished). We chose the primers that would minimize the length of the PCR product for better electrophoretic resolution while still encompassing most polymorphic sites that were encountered on the 6 sequences. From the information available then we expected that the sizes of the amplified fragments would range from ~250 bp to ~315 bp, a range of sizes that is suitable for separating alleles differing by as little as 1 bp in size when using long-range denaturing polyacrylamide gel electrophoresis.

Prior to PCR the forward primer was radioactively 5' end-labeled using 1 U/µl Phage T4 polynucleotide kinase (Eurogentec, Liège, Belgium) in a reaction mixture comprising the enzyme buffer, 2 µM primer and 1.7 µM [γ-3 P]ATP (Isotopchim, Ganagobie, France) and left at 37°C for 30 min.

PCR was carried out in a Crocodile III thermocycler (Appligène, Strasbourg, France) in 10 µl reaction mixture containing about 0.5 ng/µl template DNA, 20 pM radioactively labeled forward primer, 200 pM reverse primer, 1.5 mM MgCl 2 , 0.7 mM dNTPs and 3 U/ml Taq polymerase (Promega, Madison WI, USA) in its buffer. Amplifications were achieved by running 30 cycles of 1.5 min at 94°C, 1 min at 46°C and 0.5 min at 72°C following a 3 min start at 94°C and terminated by 5 min at 72°C. The PCR products were heated at 95°C for 5 min in 33% formamide solution and electrophoresed in vertical gels of 0.4-mm thick 4% denaturing polyacrylamide / 0.5X TBE buffer for 4-5 hrs at 50 W. After migration, the gels were vacuum-dried at 80°C for 1 hr and autoradiographed against X-Omat film (Eastman Kodak, Rochester NY, U.S.A.). Allele sizes were obtained from sequences [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF]C. Daguin, P. Borsa and M. Ohresser, unpublished) or by log-linear interpolation on the gel autoradiographs. Size-homologies of alleles from different individuals were ascertained by side-by-side electrophoretic runs.

Correlations of alleles within individuals relative to the population, and within populations relative to the total population, were estimated using Weir & Cockerham's (1984) estimators f and θ, respectively. Random permutations on the matrices of individuals x genotypes were used to give the expected distributions of f and θ under the null hypotheses f = 0 and θ = 0, respectively. The probability of occurrence of a parameter value larger or equal to the estimate was estimated as P = (n+1)/(N+1) where n is the number of pseudo-values larger than or equal to the estimate and N is the number of random permutations (Sokal and Rohlf, 1995). The null hypothesis f = 0 was rejected when P < 0.025 (using a two-tailed test). The null hypothesis θ = 0 was rejected when P < 0.05 (using a one-tailed test). For multiple tests we used the sequential Bonferroni adjustment as advocated by [START_REF] Rice | Analyzing tables of statistical tests[END_REF]. The estimations of f and θ and permutation tests were made using Procedure FSTATS in the computer package GENETIX [START_REF] Belkhir | Recherches experimentales sur l'hybridation de Mytilus edulis L. et M. galloprovincialis Lmk (mollusques lamellibranches)[END_REF].

Results

Long-range polyacrylamide gel electrophoresis revealed a high level of size polymorphism in mac-1 Intron 1 (Fig. 2 and Table 1). Size alleles ranged from 250 bp to 315 bp as expected from preliminary data [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF]M. Ohresser, unpublished). Three size classes of alleles were designated by letters a, b and c as in [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF].

Because of sharper resolution we detected size differences within each class leading to the recognition of 18 alleles in the present survey.

Hence we chose to designate them by numbers following the letter formerly assigned to each class (e.g. a1, b3, c4...).

The distributions among samples of the allelic frequencies at locus mac-1 are presented in Table 1. Alleles a1, a4 and a5 were characteristic of M. edulis since they were present in the M. edulis reference sample (GILL) and absent or virtually absent from the M. galloprovincialis reference sample (SETE). Similarly, alleles b1, b2, c1, c2, c5, a2, a6, and a7 were considered as characteristic of M. galloprovincialis. c2, the most frequent allele in the reference M. galloprovincialis sample and which was absent in the reference M. edulis sample, was also the most common allele in the 3 samples from northwestern Africa. a4 and a5, the galloprovincialis) into a synthetic allele "E" (respectively "G"), we obtained the following distribution of genotypes in sample POLZ: EE:10 ; EG:20 ; GG:13 ; E-:6 ; G-:9 ; --:1 where dots refer to alleles that were absent in the reference samples (b3, b4, c3, c4, a15 and a8). This genotype distribution suggests that the POLZ sample was drawn from an hybrid population (at least for mac-1 genes) rather than consisting of a mixture of individuals with M. edulis and M. galloprovincialis mac-1 genotypes.

Weir and Cockerham's (1984) f-estimates for each population ranged from f = 0.034 (TEMA) to f = 0.230 (GILL) (Table 2). None of these values was significantly different from 0 although they were all positive, thereby indicating some tendency towards heterozygote deficiency.

Heterozygote deficiencies have been regularly reported in mussel populations (see Gaffney, 1994;[START_REF] Raymond | Heterozygote deficiency in the mussel Mytilus edulis species complex revisited[END_REF] and so did the homozygotes. No artifact caused by mis-priming was thus detected, leading to the conclusion that this type of null alleles is not the cause of heterozygote deficiency, if this actually occurs in the populations sampled in Polzeath and Sète.

Weir and Cockerham's (1984) θ-estimates, calculated for each pair of populations, are presented in Table 3. Each of the 3 northwestern African populations significantly differed from the reference M. edulis sample (GILL) (with θ ranging from 0.292 to 0.333) whereas no significant genetic heterogeneity was evident between each of the 3 northwestern African samples and the reference M. galloprovincialis sample (SETE) (with θ ranging from 0.009 to 0.026). However, when pooling all northwestern African individuals including those of Sample Cansado, a significant albeit weak difference with the reference M. galloprovincialis was detected (θ = 0.013; P = 0.039). The Padstow mussel sample (POLZ) appeared differentiated from all the other populations (θ ranging from 0.054 to 0.152).

Discussion

Intron-1 length polymorphism at the actin gene locus mac-1 proves useful as a genetic marker for population studies in Mytilus mussels. It is diagnostic between two mussel species, M. edulis L. and M.

galloprovincialis Lmk and exhibits size-polymorphism within each species.

The techniques reported in the present study allowed to discriminate between size-alleles differing from each another by as little as 1 bp leading to the recognition of 18 size-alleles in the total sample. Sequencing analysis [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF]C. Daguin, P. Borsa and M. Ohresser, unpublished) revealed that the large size differences observed between alleles are caused by the occurrence of several indels within the amplified fragments whereas small size differences generally correspond to single-or di-nucleotide gaps. With this and other nuclear DNA markers such as the calmoduline gene intron (Côrte-Real et al., 1994a) and the gene encoding the byssal polyphenolic adhesive protein, Glu (Inoue et al., 1995;[START_REF] Rawson | Evidence for intragenic recombination within a novel genetic marker that distinguishes mussels in the Mytilus edulis species complex[END_REF], an interesting array of population genetic markers is now available in Mytilus. PCR-based assays of genetic markers are also valuable because they are more sensitive than allozymes and can be used in the routine analysis of minute quantities of material, such as mussel larvae or spat (Côrte-Real et al., 1994a,b;[START_REF] Rawson | Evidence for intragenic recombination within a novel genetic marker that distinguishes mussels in the Mytilus edulis species complex[END_REF]Bierne et al., 1998).

The possible occurrence of "null" alleles that would be artifacts caused by mis-priming as reported for oysters (Hare et al., 1996) was here tested on some samples by using two independent PCR-primer pairs. There was no evidence of such an artifact. The trend towards heterozygote deficiency that was apparent from genotype frequency distributions has therefore another cause (see Gaffney, 1994 and[START_REF] Raymond | Heterozygote deficiency in the mussel Mytilus edulis species complex revisited[END_REF] in-depth discussions of this phenomenon). The high proportion in sample POLZ of heterozygotes with both an M. edulis and an M. galloprovincialis mac-1 alleles indicates that the population it was drawn from is hybrid rather than a mixture of mussels from the two species. This result is compatible with the introgressed status of the mussel population at this location, that was reported by [START_REF] Beaumont | Electrophoretic and morphometric criteria for the identification of the mussels Mytilus edulis and M. galloprovincialis[END_REF]. Nevertheless, the slight heterozygote deficiency in this sample, if it is real, may be interpreted as a Wahlund effect as already discussed in [START_REF] Ohresser | Intron-length polymorphism at the actin gene locus mac-1: a genetic marker for population studies in the marine mussels Mytilus galloprovincialis Lmk and M. edulis L[END_REF].

We here showed that on the basis of allele frequencies at locus mac-1 Intron 1, the mussel sampled on the northwestern African coasts are M. galloprovincialis, as formerly supposed on the basis of morphology and geographic location (Lubet et al., 1984). To our knowledge, the occurrence of M. galloprovincialis on the Mauritanian coasts so far constitutes its southernmost reported location in the northeastern Atlantic.

No genetic heterogeneity was detected among the northwestern African samples including Tetouan. Although the latter location is at the eastern side of the Gibraltar strait, this sample did not exhibit genetic differences with the other northwestern African samples. There was an a priori reason for grouping the Tetouan sample with the other northwestern African samples as explained in the following. Tetouan is located in the Alboran Sea; because the Alboran Sea is considered to be a permanent intrusion of Atlantic surface waters in the Mediterranean, the Almeria-Oran oceanographic front which delimits it at the East (Tintore et al., 1996) is thought to constitute the effective boundary between the Atlantic and the western Mediterranean waters. This physical structure is thought to constitute a barrier to larval flow, explaining the abrupt genetic change in allozyme and mitochondrial DNA haplotype frequencies between northeastern Atlantic-Alboran Sea and western Mediterranean M. galloprovincialis (Quesada et al., 1995a,b;[START_REF] Sanjuan | Macrogeographic differentiation by mtDNA restriction site analysis in the S.W. European M. galloprovincialis Lmk[END_REF]. The θvalue at locus mac-1, between the northwestern African populations grouped together and the reference sample for M. galloprovincialis (θ = 0.013) was of the same order as the mean Gst-value reported for allozymes (Gst = 0.029 ± 0.032; Quesada et al., 1995b) between each side of the Almería-Oran front. The genetic differentiation level observed using the two types of nuclear markers is therefore comparable and it contrasts with that reported for mitochondrial DNA (Gst = 0.128, calculated from the haplotype frequency data in [START_REF] Sanjuan | Macrogeographic differentiation by mtDNA restriction site analysis in the S.W. European M. galloprovincialis Lmk[END_REF]. Such an observation is compatible with the hypothesis that the northeastern Inheritance of a nuclear DNA polymorphism assayed in single bivalve larvae. Mar. Biol., Vol. 120, pp.415-420. Coustau, C., F. Renaud, and B. Delay, 1991. Genetic Table 2 Weir and Cockerham's (1984) f-estimates in Mytilus spp. populations from the northeastern Atlantic and the western Mediterranean. Abbreviations for samples as in legend to Fig. 1 ------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------- ------------------------------------------------------------------------------------ns , not significant (1000 pseudo-samples obtained by permutations of alleles within each sample) Table 3 Weir and Cockerham's (1984) θ-estimates between pairs of Mytilus spp. populations from the northeastern Atlantic and the western Mediterranean.

------------------------------------------------------------------------------------P OLZ SET E TETO TE MA DAKH ------------------------------------------------------------------------------------GILL 0. .027 ------------------------------------------------------------------------------------* values significantly different from 0 (1000 pseudo-samples obtained by permutations of genotypes in the total sample) with significance level adjusted using sequential Bonferroni procedure [START_REF] Rice | Analyzing tables of statistical tests[END_REF].

Figures legends

Fig. 1. Sampling localities for Mytilus sp. in northwestern Africa and for reference M. edulis and M. galloprovincialis in Europe. GILL Gilleleje, Denmark, Sep. 1996;POLZ Polzeath, south-west Britain, July 1996;SETE Sète, southern France, May 1996;TEMA Temara, Morocco, Nov. 1995;TETO Tetouan, Morocco, Nov. 1995;DAKH Dakhla, Western Sahara, Nov. 1995;CANS Cansado, Mauritania, Apr. 1996 B,b2c2;C,a7a8;D,b1a4;E,c4c4;F,c3c4;G,c2a2;H,a1b1;I,a3a5;J,negative PCR control;K,a2a8;L,a2a7;M,c4a6;N,a2a5;O,a2a4

  most frequent alleles in Sample GILL, were virtually absent from SETE and from the northwestern African samples. The genotypes of the two mussels from Cansado (sample CANS) were c1a8 and c1c2, therefore showing M. galloprovincialis characteristics. Incidentally, the Padstow mussel (sample POLZ) showed characteristics of both species with Alleles c2 and a5 as the most common. Although the frequencies of the latter were intermediate between those of the reference M. edulis and M. galloprovincialis populations, Allele a4 was virtually absent in sample POLZ. mac-1 allele frequencies in sample POLZ were generally intermediate between those of the reference M. edulis and M. galloprovincialis samples. This may reflect either extensive introgression in the POLZ population, or the admixture of differentiated populations or both. A closer look at genotype data is here necessary. By pooling, for convenience, all alleles characteristic of M. edulis (respectively M.

  for rewiews). Using the PCR amplification of nuclear DNA, one may overlook the occurrence of some alleles because of sequence polymorphism leading to mis-priming under given stringency conditions (see Hare et al., 1996 for such an example of "null" alleles in oysters), hence artifactually increasing the frequency of apparent homozygotes in a sample. Two of the samples analysed in the present survey, POLZ and SETE (127 individuals) were also analysed by Ohresser et al. (1997) using a different pair of primers. Hence we were able to assess the probability of occurrence of null alleles due to priming site sequence polymorphism by comparing the genotypes obtained with our pair of primers (pair 1) with those obtained by Ohresser et al. (1997) (pair 2). All heterozygotes with Pair 1 (N = 58) remained heterozygotes for the same size-class alleles with Pair 2

  Atlantic and the western Mediterranean M. galloprovincialis populations have undergone geographic isolation. Under geographic isolation, mitochondrial DNA clones are indeed expected to evolve faster than nuclear DNA genes because of their smaller effective population size. The present results, though preliminary, warrant further investigations on the evolutionary genetics of Mytilus populations using mac-1 as a marker. Both mac-1 polymorphism studies on Iberian populations and allozyme and mitochondrial DNA studies on northwestern African samples would be helpful for a more complete picture of the phylogeography of M. galloprovincialis in the northeastern Atlantic and the Mediterranean. populations. Version 3.0. Montpellier, France: Université de Montpellier II. Bierne, N., S. Launey, Y. Naciri-Graven and F. Bonhomme, 1998. Early effect of inbreeding as revealed by microsatellite analysis on Ostrea edulis larvae. Genetics (in press) Côrte-Real, H.B.S.M., D.R. Dixon and P.W.H. Holland, 1994a. Introntargeted PCR: a new approach to survey neutral DNA polymorphism in bivalve populations. Mar. Biol., Vol. 120, pp.407-413. Côrte-Real, H.B.S.M., P.W.H. Holland and D.R. Dixon, 1994b.

  characterization of the hybridization between Mytilus edulis and M. galloprovincialis on the Atlantic coast of France. Mar. Biol., Vol. 111, pp. 87-93. Gardner, J.P.A., 1994. The structure and dynamics of naturally occurring hybrid Mytilus edulis Linnaeus, 1758 and Mytilus galloprovincialis Lamarck, 1819 (bivalvia: Mollusca) populations: review and interpretation. Arch. Hydrobiol., Suppl. 99, pp. 37-71. Hare, M.P, S.A. Karl and J.C. Avise, 1996. Anonymous nuclear DNA markers in the American oyster and their implications for the heterozygote deficiency phenomenon in marine bivalves. Mol. Biol. Evol., Vol. 13, pp. 334-345. Inoue, K., J.H. Waite, M. Matsuoka, S. Odo and S. Harayama, 1995. Interspecific variations in adhesive protein sequences of Mytilus edulis, M. galloprovincialis and M. trossulus. Biol. Bull. Vol. 189, pp. 370-375. Karakousis, Y. and D.O.F. Skibinski, 1992. An analysis of allozyme, mitochondrial DNA and morphological variation in mussel (Mytilus galloprovincialis) populations from Greece.Experientia, Vol. 48, pp. 878-881. Koehn, R.K., 1991. The genetics and taxonomy of species in the genus Mytilus.Aquaculture, Vol. 94,

Fig. 2 .

 2 Fig. 2. Length-polymorphism of the PCR products of Intron-1 of the actin gene mac-1 in Mytilus spp. individuals. Allele size-classes are designated by letters a, b, or c followed by a number. The radioactively labeled PCR products of different individuals were loaded into different lanes of a vertical 4% denaturing polyacrylamide gel, electrophoresed and autoradiographed. Individual genotypes were the following : lane A, c1c2;

Acknowledgments: we are grateful to François Bonhomme for advice and support, to him, Patrice David and Michel Raymond for discussion, suggestions and comments on this manuscript, to Marc Ohresser for helpful suggestions, to Galice Hoarau for assistance in the laboratory, to Didier Jollivet, Mariam Naciri, Marc Ohresser and Michel Raymond for participating in the collection of samples and to Ngone Dieng and Didier Jouffre for hospitality in Mauritania. This is a contribution from Laboratoire Génome et Populations.

Seed, R., 1992. Systematics, evolution and distribution of mussels belonging to the genus Mytilus: an overview. Amer. Malacol. Bull., Vol. 9, pp. 123-137. Skibinski, D.O.F. and J.A. Beardmore, 1979. A - ---------------------------------------------------------------------------------------- 16) ------------------------------------------------------------------------------------------


Jean-Yves Audibert

No fast exponential deviation inequalities for the progressive mixture rule

No fast exponential deviation inequalities for the progressive mixture rule

Jean-Yves Audibert CERTIS -Ecole des Ponts 19, rue Alfred Nobel -Cité Descartes 77455 Marne-la-Vallée -France audibert@certis.enpc.fr

Abstract. We consider the learning task consisting in predicting as well as the best function in a finite reference set G up to the smallest possible additive term. If R(g) denotes the generalization error of a prediction function g, under reasonable assumptions on the loss function (typically satisfied by the least square loss when the output is bounded), it is known that the progressive mixture rule ĝ satisfies

ER(ĝ) ≤ ming∈G R(g) + C log |G| n , (1)
where n denotes the size of the training set, E denotes the expectation w.r.t. the training set distribution and C denotes a positive constant. This work mainly shows that for any training set size n, there exist ǫ > 0, a reference set G and a probability distribution generating the data such that with probability at least ǫ R(ĝ) ≥ ming∈G R(g) + c log(|G|ǫ -1 ) n , where c is a positive constant. In other words, surprisingly, for appropriate reference set G, the deviation convergence rate of the progressive mixture rule is only of order 1/ √ n while its expectation convergence rate is of order 1/n. The same conclusion holds for the progressive indirect mixture rule. This work also emphasizes on the suboptimality of algorithms based on penalized empirical risk minimization on G.

Setup and notation

We assume that we observe n pairs of input-output denoted Z 1 = (X 1 , Y 1 ), . . . , Z n = (X n , Y n ) and that each pair has been independently drawn from the same unknown distribution denoted P . The input and output space are denoted respectively X and Y, so that P is a probability distribution on the product space Z X × Y. The quality of a (prediction) function g : X → Y is measured by the risk (or generalization error):

R(g) = E (X,Y )∼P ℓ[Y, g(X)],
where ℓ[Y, g(X)] denotes the loss (possibly infinite) incurred by predicting g(X) when the true output is Y . We work under the following assumptions for the data space and the loss function ℓ : Y × Y → R ∪ {+∞}.

Main assumptions. The input space is assumed to be infinite: |X | = +∞. The output space is a non-trivial (i.e. infinite) interval of R symmetrical w.r.t. some a ∈ R: for any y ∈ Y, we have 2a -y ∈ Y. The loss function is uniformly exp-concave: there exists λ > 0 such that for any y ∈ Y, the set y ′ ∈ R : ℓ(y, y ′ ) < +∞ is an interval containing a on which the function y ′ → e -λℓ(y,y ′ ) is concave.

symmetrical: for any y 1 , y 2 ∈ Y, ℓ(y 1 , y 2 ) = ℓ(2a -y 1 , 2a -y 2 ), -admissible: for any y, y ′ ∈ Y∩]a; +∞[, ℓ(y, 2a -y ′ ) > ℓ(y, y ′ ), -well behaved at center: for any y ∈ Y∩]a; +∞[, the function ℓ y : y ′ → ℓ(y, y ′ ) is twice continuously differentiable on a neighborhood of a and ℓ ′ y (a) < 0.

These assumptions imply that

-Y has necessarily one of the following form: ]

-∞; +∞[, [a -ζ; a + ζ] or ]a -ζ; a + ζ[ for some ζ > 0.
for any y ∈ Y, from the exp-concavity assumption, the function ℓ y : y ′ → ℓ(y, y ′ ) is convex on the interval on which it is finite1 . As a consequence, the risk R is also a convex function (on the convex set of prediction functions for which it is finite).

The assumptions were motivated by the fact that they are satisfied in the following settings:

least square loss with bounded outputs: Y = [y min ; y max ] and ℓ(y 1 , y 2 ) = (y 1y 2 ) 2 . Then we have a = (y min +y max )/2 and may take λ = 1/[2(y max -y min ) 2 ]. -entropy loss: Y = [0; 1] and ℓ(y 1 , y 2 ) = y 1 log y1 y2 + (1 -y 1 ) log 1-y1 1-y2 . Note that ℓ(0, 1) = ℓ(1, 0) = +∞. Then we have a = 1/2 and may take λ = 1.

exponential (or AdaBoost) loss: Y = [-y max ; y max ] and ℓ(y 1 , y 2 ) = e -y1y2 .

Then we have a = 0 and may take λ = e -y 2 max . -logit loss: Y = [-y max ; y max ] and ℓ(y 1 , y 2 ) = log(1 + e -y1y2 ). Then we have a = 0 and may take λ = e -y 2 max .

Progressive indirect mixture rule. Let G be a finite reference set of prediction functions. Under the previous assumptions, the only known algorithms satisfying (1) are the progressive indirect mixture rules defined below.

For any i ∈ {0, . . . , n}, the cumulative loss suffered by the prediction function g on the first i pairs of input-output is

Σ i (g) i j=1 ℓ[Y j , g(X j )],
where by convention we take Σ 0 ≡ 0. Let π denote the uniform distribution on G. We define the probability distribution πi on G as πi ∝ e -λΣi • π equivalently for any g ∈ G, πi (g) = e -λΣi(g) /( g ′ ∈G e -λΣi(g ′ ) ). This distribution concentrates on functions having low cumulative loss up to time i. For any i ∈ {0, . . . , n}, let ĥi be a prediction function such that

∀ (x, y) ∈ Z ℓ[y, ĥi (x)] ≤ -1 λ log E g∼πi e -λℓ[y,g(x)] . (2)
The progressive indirect mixture rule produces the prediction function

ĝpim = 1 n+1 n i=0 ĥi .
From the uniform exp-concavity assumption and Jensen's inequality, ĥi does exist since one may take ĥi = E g∼πi g. This particular choice leads to the progressive mixture rule, for which the predicted output for any x ∈ X is

ĝpm (x) = g∈G 1 n+1 n i=0
e -λΣ i (g) g ′ ∈G e -λΣ i (g ′ ) g(x). Consequently, any result that holds for any progressive indirect mixture rule in particular holds for the progressive mixture rule.

The idea of a progressive mean of estimators has been introduced by Barron ( [START_REF] Barron | Are bayes rules consistent in information?[END_REF]) in the context of density estimation with Kullback-Leibler loss. The form ĝpm is due to Catoni ([7]). It was also independently proposed in [START_REF] Barron | Information-theoretic determination of minimax rates of convergence[END_REF]. The study of this procedure was made in density estimation and least square regression in [START_REF] Catoni | Universal aggregation rules with exact bias bound[END_REF][START_REF] Blanchard | The progressive mixture estimator for regression trees[END_REF][START_REF] Yang | Combining different procedures for adaptive regression[END_REF][START_REF] Bunea | Sequential procedures for aggregating arbitrary estimators of a conditional mean[END_REF]. Results for general losses can be found in [START_REF] Juditsky | Learning by mirror averaging[END_REF][START_REF] Audibert | A randomized online learning algorithm for better variance control[END_REF]. Finally, the progressive indirect mixture rule is inspired by the work of Vovk, Haussler, Kivinen and Warmuth [START_REF] Vovk | Aggregating strategies[END_REF][START_REF] Haussler | Sequential prediction of individual sequences under general loss functions[END_REF][START_REF] Vovk | A game of prediction with expert advice[END_REF] on sequential prediction and was studied in the "batch" setting in [START_REF] Audibert | A randomized online learning algorithm for better variance control[END_REF].

The symbol C will denote some positive constant whose value may differ from line to line. The logarithm in base 2 is denoted by log 2 (i.e. log 2 t = log t/ log 2) and ⌊x⌋ denotes the largest integer k such that k ≤ x.

Expectation convergence rate

First let us define the expectation convergence rate of a learning algorithm. Definition 1. For a given reference set G of prediction functions and a set P of probability distributions on Z = X × Y, a positive sequence (∆ n ) n≥2 is said to be an expectation convergence rate of a learning algorithm producing the prediction function ĝ iff there exist C > c > 0 such that 1. for any distribution P ∈ P and any n ≥ 2, we have

ER(ĝ) -inf g∈G R(g) ≤ C∆ n (3)
2. for large enough n, there exists P ∈ P for which

ER(ĝ) -inf g∈G R(g) ≥ c∆ n .
We say that the rate ∆ n is optimal iff the previous item 2 is also satisfied for any other algorithm, in other words iff there is no algorithm having an expectation convergence rate ∆n satisfying lim n→+∞ ∆n /∆ n = 0.

The following theorem shows that the expectation convergence rate of any progressive indirect mixture rule is at least (log |G|)/n and that for any positive integer d, there exists a set G of d prediction functions such that this rate is optimal whether we take P as the set of all probability distributions on Z or the set of all probability distributions on Z for which the output has almost surely two symmetrical values (e.g. {-1;+1}-classication with exponential or logit losses).

Theorem 1. Any progressive indirect mixture rule satisfies

ER(ĝ pim ) ≤ min g∈G R(g) + log |G| λ(n+1) .
Let y 1 ∈ Y -{a} and d be a positive integer. There exists a set G of d prediction functions such that: for any learning algorithm, there exists a probability distribution generating the data for which the output marginal is supported by 2a-y 1 and y 1 :

P (Y ∈ {2a-y 1 ; y 1 }) = 1, -ER(ĝ) ≥ min g∈G R(g)+ e -1 κ 1 ∧ ⌊log 2 |G|⌋ n+1 , with κ sup y∈Y [ℓ(y 1 , a)-ℓ(y 1 , y)] > 0.
Proof. See Appendix A.

The second part of Theorem 1 has the same (log |G|/n)-rate as the lower bounds obtained in sequential prediction ( [START_REF] Haussler | Sequential prediction of individual sequences under general loss functions[END_REF]). From the link between sequential predictions and our "batch" setting with i.i.d. data (see e.g. [2, Lemma 3]), upper bounds for sequential prediction lead to upper bounds for i.i.d. data, and lower bounds for i.i.d. data leads to lower bounds for sequential prediction. The converse of this last assertion is not true, so that the second part of Theorem 1 is not a consequence of the lower bounds of [START_REF] Haussler | Sequential prediction of individual sequences under general loss functions[END_REF].

The following theorem shows that for appropriate set G:

the empirical risk minimizer has a log |G|/n-expectation convergence rate.

any empirical risk minimizer and any of its penalized variants are really poor algorithms in our learning task since their expectation convergence rate cannot be faster than log |G|/n. This last point explains the interest we have in progressive mixture rules.

Theorem 2. If B sup y,y ′ ,y ′′ ∈Y [ℓ(y, y ′ ) -ℓ(y, y ′′ )]
< +∞, then any empirical risk minimizer, which produces a prediction function ĝerm in argmin g∈G Σ n , satisfies:

ER(ĝ erm ) ≤ min g∈G R(g) + B 2 log |G| n .
Let y 1 , ỹ1 ∈ Y∩]a; +∞[ and d be a positive integer. There exists a set G of d prediction functions such that: for any learning algorithm producing a prediction function in G (e.g. ĝerm ) there exists a probability distribution generating the data for which the output marginal is supported by 2a-y 1 and y 1 :

P (Y ∈ {2a-y 1 ; y 1 }) = 1, -ER(ĝ) ≥ min g∈G R(g)+ δ 8 ⌊log 2 |G|⌋ n ∧2 , with δ ℓ(y 1 , 2a-ỹ1 )-ℓ(y 1 , ỹ1 ) > 0.
Proof. See Appendix B.

Deviation convergence rate

The efficiency of an algorithm ĝ can be summarized by its expected risk E R(ĝ), but this does not precise the fluctuations of R(ĝ). In several application fields of learning algorithms, these fluctuations play a key role: in finance for instance, the bigger the losses can be, the more money the bank needs to freeze in order to alleviate these possible losses. In this case, a "good" algorithm is an algorithm having not only low expected risk but also small deviations.

The deviation convergence rate we define now is concerned with exponential deviation inequalities (such as Hoeffding's inequality or more generally such as standard statistical learning inequalities on the supremum of empirical processes).

Definition 2. Let 0 < γ ≤ 1. For a given reference set G of prediction functions and a set P of probability distributions on Z = X × Y, a positive sequence (∆ ′ n ) n∈N is said to be a deviation convergence rate of order γ of a learning algorithm iff there exist C > c > 0 such that 1. for any distribution P ∈ P, integer n ≥ 2, and ǫ > 0, with probability at least 1 -ǫ w.r.t. the training set distribution, we have

R(ĝ) -inf g∈G R(g) ≤ C log γ (eǫ -1 ) ∆ ′ n , (4)
2. for large enough n, there exist ǫ > 0 and a distribution P ∈ P such that with probability at least ǫ w.r.t. the training set distribution, we have

R(ĝ) -inf g∈G R(g) ≥ c log γ (eǫ -1 ) ∆ ′ n .
The following lemma shows that the expectation convergence rate of a learning algorithm is at least of order of its deviation convergence rate. The expectation convergence rate can also be strictly faster as the comparison between Theorems 1 and 3 shows. Lemma 1. Let ĝ satisfy: for any ǫ > 0, with probability at least 1 -ǫ, (4) holds. Then we have

ER(ĝ) -inf g∈G R(g) ≤ 2 γ C∆ ′ n .
Proof. It suffices to integrate the deviations. Let R * = inf g∈G R(g). By Jensen's inequality, we have

ER(ĝ)-R * C∆ ′ n 1/γ -1 ≤ E R(ĝ)-R * C∆ ′ n 1/γ -1 ≤ E R(ĝ)-R * C∆ ′ n 1/γ -1 ∨ 0 = +∞ 0 P R(ĝ)-R * C∆ ′ n 1/γ -1 > u du = 1 0 P R(ĝ) -R * > C∆ ′ n log γ (eǫ -1 ) dǫ ǫ [setting u = log(ǫ -1 )] ≤ 1.
The following theorem shows that the deviation convergence rate of order 1/2 of any progressive indirect mixture rule is at least 1/ √ n and that there exists G such that the deviation convergence rate of order 1/2 of any progressive indirect mixture rule is 1/ √ n whether we take P as the set of all probability distributions on Z or the set of all probability distributions on Z for which the output has almost surely two symmetrical values (e.g. {-1;+1}-classication with exponential or logit losses). Theorem 3. If B sup y,y ′ ,y ′′ ∈Y [ℓ(y, y ′ )-ℓ(y, y ′′ )] < +∞, then any progressive indirect mixture rule satisfies: for any ǫ > 0, with probability at least 1 -ǫ w.r.t. the training set distribution, we have

R(ĝ pim ) ≤ min g∈G R(g) + B 2 log(ǫ -1 ) n+1 + log |G| λ(n+1)
Let y 1 and ỹ1 in Y∩]a; +∞[ such that ℓ y1 is twice continuously differentiable on [a; ỹ1 ] and ℓ ′ y1 ( ỹ1 ) ≤ 0 and ℓ ′′ y1 ( ỹ1 ) > 0. Consider the prediction functions g 1 ≡ ỹ1 and g 2 ≡ 2a -ỹ1 . For any training set size n large enough, there exist ǫ > 0 and a distribution generating the data such that the output marginal is supported by y 1 and 2a -y 1 -with probability larger than ǫ, we have

R(ĝ pim ) -min g∈{g1,g2} R(g) ≥ c log(eǫ -1 )
n where c is a positive constant depending only on the loss function, the symmetry parameter a and the output values y 1 and ỹ1 .

Proof. See Section 4.

This result is quite surprising since it gives an example of an algorithm which is optimal in terms of expectation convergence rate and for which the deviation convergence rate is (significantly) worse that the expectation convergence rate.

4 Proof of Theorem 3

Proof of the upper bound

We would like to thank an anonymous reviewer for suggesting the following proof, which leads to better constants than the original one based on PAC-Bayesian inequalities.

Let Z n+1 = (X n+1 , Y n+1 ) be an input-output pair independent from the training set Z 1 , . . . , Z n and with the same distribution P . From the convexity of y ′ → ℓ(y, y ′ ), we have

R(ĝ pim ) ≤ 1 n+1 n i=0 R( ĥi ).
(

) 5
Now from [16, Theorem 1] (see also [9, Proposition 1]), for any ǫ > 0, with probability at least 1 -ǫ, we have

1 n+1 n i=0 R( ĥi ) ≤ 1 n+1 n i=0 ℓ Y i+1 , ĥ(X i+1 ) + B log(ǫ -1 ) 2(n+1) (6)
Using [START_REF] Haussler | Sequential prediction of individual sequences under general loss functions[END_REF]Theorem 3.8] and the exp-concavity assumption, we have

n i=0 ℓ Y i+1 , ĥ(X i+1 ) ≤ min g∈G n i=0 ℓ Y i+1 , g(X i+1 ) + log |G| λ (7)
Let g ∈ argmin G R. By Hoeffding's inequality, with probability at least 1 -ǫ, we have

1 n+1 n i=0 ℓ Y i+1 , g(X i+1 ) ≤ R(g) + B log(ǫ -1 ) 2(n+1) (8)
Merging ( 5), ( 6), ( 7) and [START_REF] Catoni | Universal aggregation rules with exact bias bound[END_REF], with probability at least 1 -2ǫ, we get

R(ĝ pim ) ≤ 1 n+1 n i=0 ℓ Y i+1 , g(X i+1 ) + log |G| λ(n+1) + B log(ǫ -1 ) 2(n+1) ≤ R(g) + B 2 log(ǫ -1 ) n+1 + log |G| λ(n+1) .

Proof of the lower bound

We cannot use standard tools like Assouad's argument (see e.g. [10, Theorem 14.6]) because if it were possible, it would mean that the lower bound would hold for any algorithm and this is (non trivially) false.

To prove that any progressive indirect mixture rule have no fast exponential deviation inequalities, we will show that on some event with not too small probability, for most of the i in {0, . . . , n}, π -λΣi concentrates on the wrong function.

The proof is organized as follows. First we define the probability distribution for which we will prove that the progressive indirect mixture rules cannot have fast deviation convergence rates. Then we define the event on which the progressive indirect mixture rules do not perform well. We lower bound the probability of this excursion event. Finally we conclude by lower bounding R(ĝ pim ) on the excursion event.

Before starting the proof, note that from the "well behaved at center" and exp-concavity assumptions, for any y ∈ Y∩]a; +∞[, on a neighborhood of a, we have: ℓ ′′ y ≥ λ(ℓ ′ y ) 2 and since ℓ ′ y (a) < 0, y 1 and ỹ1 exist.

Probability distribution generating the data and first consequences. Let γ ∈]0; 1] be a parameter to be tuned later. We consider a distribution generating the data such that the output distribution satisfies for any x ∈ X

P (Y = y 1 |X = x) = (1 + γ)/2 = 1 -P (Y = y 2 |X = x),
where y 2 = 2a -y 1 . Let ỹ2 = 2a -ỹ1 . From the symmetry and admissibility assumptions, we have ℓ(y 2 , ỹ2 ) = ℓ(y 1 , ỹ1 ) < ℓ(y 1 , ỹ2 ) = ℓ(y 2 , ỹ1 ). Introduce

δ ℓ(y 1 , ỹ2 ) -ℓ(y 1 , ỹ1 ) > 0. ( 9
)
We have

R(g 2 ) -R(g 1 ) = 1+γ 2 [ℓ(y 1 , ỹ2 ) -ℓ(y 1 , ỹ1 )] + 1-γ 2 [ℓ(y 2 , ỹ2 ) -ℓ(y 2 , ỹ1 )] = γδ. (10
) Therefore g 1 is the best prediction function in {g 1 , g 2 } for the distribution we have chosen. Introduce W j 1 Yj =y1 -1 Yj =y2 and S i i j=1 W j . For any i ∈ {1, . . . , n}, we have

Σ i (g 2 ) -Σ i (g 1 ) = i j=1 [ℓ(Y j , ỹ2 ) -ℓ(Y j , ỹ1 )] = i j=1 W j δ = δ S i
The weight given by the Gibbs distribution π -λΣi to the function g 1 is

π -λΣi (g 1 ) = e -λΣ i (g 1 ) e -λΣ i (g 1 ) +e -λΣ i (g 2 ) = 1 1+e λ[Σ i (g 1 )-Σ i (g 2 )] = 1 1+e -λδS i . (11)
An excursion event on which the progressive indirect mixture rules will not perform well. (11) leads us to consider the event:

E τ = ∀i ∈ {τ, . . . , n}, S i ≤ -τ ,
with τ the smallest integer larger than (log n)/(λδ) such that n -τ is even. (We could have just as well chosen n -τ odd; see (17) below.) We have

log n λδ ≤ τ ≤ log n λδ + 2. ( 12
)
The event E τ can be seen as an excursion event of the random walk defined through the random variables W j = 1 Yj =y1 -1 Yj =y2 , j ∈ {1, . . . , n}, which are equal to +1 with probability (1 + γ)/2 and -1 with probability (1 -γ)/2.

From ( 11), on the event E τ , for any i ∈ {τ, . . . , n}, we have

π -λΣi (g 1 ) ≤ 1 n+1 . (13)
This means that π -λΣi concentrates on the wrong function, i.e. the function g 2 having larger risk (see [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]).

Lower bound of the probability of the excursion event. This requires to look at the probability that a slightly shifted random walk in the integer space has a very long excursion above a certain threshold. To lower bound this probability, we will first look at the non-shifted random walk. Then we will see that for small enough shift parameter, probabilities of shifted random walk events are close to the ones associated to the non-shifted random walk.

Let N be a positive integer. Let σ 1 , . . . , σ N be N independent Rademacher variables: P(σ i = +1) = P(σ i = -1) = 1/2. Let s i i j=1 σ i be the sum of the first i Rademacher variables. We start with the following lemma for sums of Rademacher variables.

Lemma 2. Let m and t be positive integers. We have

P max 1≤k≤N s k ≥ t; s N = t; s N -t ≤ m = 2P t < s N ≤ t + m (14)
Proof (of Lemma 2). The result comes from the well known mirror trick used to compute the law of sup s≤t W s , W t where W denotes a Brownian motion. Consider a sequence σ 1 , . . . , σ N which belongs to the event E of the l.h.s. probability.

Let J be the first integer j such that s j = t. Since the sequences σ 1 , . . . , σ N and σ 1 , . . . , σ J , -σ J+1 , . . . , -σ N have the same probabilities, -both sequences belong to E and are different since J < N , -exactly one of the sequences satisfy s N > t, we have

P max 1≤k≤N s k ≥ t; s N = t; s N -t ≤ m = 2P s N > t; s N -t ≤ m ,
which is the desired result.

Let σ ′ 1 , . . . , σ ′ N be N independent shifted Rademacher variables to the extent that P(σ ′ i = +1) = (1 + γ)/2 = 1 -P(σ ′ i = -1). These random variables satisfy the following key lemma Lemma 3. For any set A ⊂ (ǫ 1 , . . . , ǫ N ) ∈ {-1, 1} n : N i=1 ǫ i ≤ M where M is a positive integer, we have

P (σ ′ 1 , . . . , σ ′ N ) ∈ A ≥ 1-γ 1+γ M/2 1 -γ 2 N/2 P (σ 1 , . . . , σ N ) ∈ A (15)
Proof (of Lemma 3). Let s be an integer such that N -s is even and |s| ≤ M Consider a sequence ǫ 1 , . . . , ǫ N such that N i=1 ǫ i = s. Then the numbers of -1 and +1 in the sequence are respectively (N -s)/2 and (N + s)/2. Consequently, we have

P[(σ ′ 1 ,...,σ ′ N )=(ǫ1,...,ǫN )] P[(σ1,...,σN )=(ǫ1,...,ǫN )] = (1 + γ) (N -s)/2 (1 -γ) (N +s)/2 , hence P{(σ ′ 1 , . . . , σ ′ N ) = (ǫ 1 , . . . , ǫ N ) ≥ (1 -γ 2 ) N/2 1-γ 1+γ M/2 P (σ 1 , . . . , σ N ) = (ǫ 1 , . . . , ǫ N ) .
By summing over the sequences ǫ 1 , . . . , ǫ N in A, we obtain the desired result.

We may now lower bound the probability of the excursion event E τ . Let M be an integer larger than τ . We still use W j 1 Yj =y1 -1 Yj =y2 for j ∈ {1, . . . , n}. By using Lemma 3 with N = n -2τ , we obtain

P(E τ ) ≥ P W 1 = -1, . . . , W 2τ = -1; ∀ 2τ < i ≤ n, i j=2τ +1 W j ≤ τ = 1-γ 2 2τ P ∀ i > 2τ i j=2τ +1 W j ≤ τ = 1-γ 2 2τ P ∀ i ∈ {1, . . . , N } i j=1 σ ′ j ≤ τ ≥ 1-γ 2 2τ P N i=1 σ ′ i < M ; ∀ i ∈ {1, . . . , N } i j=1 σ ′ j ≤ τ ≥ 1-γ 2 2τ 1-γ 1+γ M/2 1 -γ 2 N 2 P |s N | ≤ M ; ∀ i ∈ {1, . . . , N } s i ≤ τ (16)
By using Lemma 2, since τ ≤ M , the r.h.s. probability can be lower bounded:

P |s N | ≤ M ; max 1≤i≤N s i ≤ τ = P max 1≤i≤N s i ≤ τ ; s N ≥ -M ≥ P max 1≤i≤N s i < τ ; |s N -τ | ≤ M + τ ; s N = τ = P |s N -τ | ≤ M + τ ; s N = τ -P max 1≤i≤N s i ≥ τ ; |s N -τ | ≤ M + τ ; s N = τ = P |s N -τ | ≤ M + τ ; s N = τ -2P τ < s N ≤ M + 2τ = P -M ≤ s N < τ -P τ < s N ≤ M + 2τ = P -τ < s N ≤ M -P τ < s N ≤ M + 2τ = P -τ < s N ≤ τ -P M < s N ≤ M + 2τ
Let us consider only the integer M > τ such that n -M is even, or equivalently N -M is even. Since N -τ = n -3τ is also even, we have

P |s N | ≤ M ; max 1≤i≤N s i ≤ τ ≥ τ -1 k=0 P(s N = 2 -τ + 2k) -τ k=1 P(s N = M + 2k) ≥ τ [P(s N = τ ) -P(s N = M )], (17)
where the last inequality comes from properties of the binomial coefficients.

Combining ( 16) and (17), we obtain

P(E τ ) ≥ τ 1-γ 2 2τ 1-γ 1+γ M/2 1 -γ 2 N 2 [P(s N = τ ) -P(s N = M )] (18)
where we recall that τ have the order of log n, N = n -2τ has the order of n and that γ > 0 and M ≥ τ have to be appropriately chosen.

To control the probabilities of the r.h.s., we use Stirling's formula

n n e -n √ 2πn e 1/(12n+1) < n! < n n e -n √ 2πn e 1/(12n) , (19)
and get for any s ∈ [0; N ] such that N -s even,

P(s N = s) = 1 2 N N N +s 2 ≥ 1 2 N ( N e ) N √ 2πN e 1 12N +1 ( N +s 2e ) N +s 2 ( N -s 2e ) N -s 2 √ π(N +s) √ π(N -s)e 1 6(N +s) e 1 6(N -s) = 1 (1+ s N ) N +s 2 (1-s N ) N -s 2 2N π(N 2 -s 2 ) e 1 12N +1 - 1 6(N +s) - 1 6(N -s) ≥ 2 πN 1 -s 2 N 2 -N 2 1-s N 1+ s N s 2 e -1 6(N +s) - 1 6(N -s) (20)
and similarly

P(s N = s) ≤ 2 πN 1 -s 2 N 2 -N 2 1-s N 1+ s N s 2 e 1 12N +1 (21)
These computations and (18) leads us to take M as the smallest integer larger than √ n such that n -M is even. Indeed, from ( 12), ( 20) and ( 21), we obtain lim n→+∞ √ n[P(s N = τ ) -P(s N = M )] = c, where c = 2/π 1 -e -1/2 > 0. Therefore for n large enough we have

P(E τ ) ≥ cτ 2 √ n 1-γ 2 2τ 1-γ 1+γ M/2 1 -γ 2 N 2 (22)
The last two terms of the r.h.s. of ( 22) leads us to take γ of order 1/ √ n up to possibly a logarithmic term. We obtain the following lower bound on the excursion probability Lemma 4. If γ = C 0 (log n)/n with C 0 a positive constant, then for any large enough n,

P(E τ ) ≥ 1 n C 0 .
Behavior of the progressive indirect mixture rule on the excursion event. From now on, we work on the event E τ . We have ĝpim = ( n i=0 ĥi )/(n + 1). We still use δ ℓ(y 1 , ỹ2 ) -ℓ(y 1 , ỹ1 ) = ℓ(y 2 , ỹ1 ) -ℓ(y 2 , ỹ2 ). On the event E τ , for any x ∈ X and any i ∈ {τ, . . . , n}, by definition of ĥi , we have

ℓ[y 2 , ĥi (x)] -ℓ(y 2 , ỹ2 ) ≤ -1 λ log E g∼π -λΣ i e -λ{ℓ[y2,g(x)]-ℓ(y2, ỹ2)} = -1 λ log π -λΣi (g 1 )e -λδ + π -λΣi (g 2 ) = -1 λ log e -λδ + (1 -e -λδ )π -λΣi (g 2 ) ≤ -1 λ log 1 -(1 -e -λδ ) 1 n+1
In particular, for any n large enough, we have ℓ[y 2 , ĥi (x)] -ℓ(y 2 , ỹ2 ) ≤ Cn -1 , with C > 0 independent from γ. From the convexity of the function y → ℓ(y 2 , y) and by Jensen's inequality, we obtain

ℓ[y 2 , ĝpim (x)] -ℓ(y 2 , ỹ2 ) = ℓ[y 2 , 1 n+1 n i=0 ĥi (x)] -ℓ(y 2 , ỹ2 ) ≤ 1 n+1 n i=0 ℓ[y 2 , ĥi (x)] -ℓ(y 2 , ỹ2 ) ≤ τ δ n+1 + Cn -1 < C 1 log n n (23)
for some constant C 1 > 0 independent from γ. Let us now prove that for n large enough, we have

ỹ2 ≤ ĝpim (x) ≤ ỹ2 + C log n n ≤ ỹ1 , (24)
with C > 0 independent from γ.

Proof. For any y ∈ Y, let t = 2a-y. We have ℓ(y 2 , y)-ℓ(y 2 , ỹ2 ) = ℓ y1 (t)-ℓ y1 ( ỹ1 ). Since ℓ ′ y1 ( ỹ1 ) ≤ 0, ℓ ′′ y1 ( ỹ1 ) > 0, ℓ ′′ y1 ≥ λ(ℓ ′ y1 ) 2 and ℓ ′′ y1 is continuous on [a; ỹ1 ], there exists m > 0 such that ℓ ′′ y1 > m on [a; ỹ1 ]. For any ỹ2 < y ≤ a, from Taylor's expansion, we have

ℓ(y 2 , y) -ℓ(y 2 , ỹ2 ) > (t -ỹ1 )ℓ ′ y1 ( ỹ1 ) + (t-ỹ1) 2 2 m ≥ (t-ỹ1) 2 2 m = (y-ỹ2) 2 2 m (25) Let y 0 ỹ2 + 2C1 log n mn
where C 1 is the constant appearing in (23). For n large enough, we have y 0 ≤ a and we may apply (25) to y = y 0 . We get

ℓ(y 2 , y 0 ) -ℓ(y 2 , ỹ2 ) > C 1 log n n . ( 26
)
Since ℓ y1 is convex, ℓ ′ y1 ( ỹ1 ) ≤ 0 and ℓ ′′ y1 ( ỹ1 ) > 0, the function ℓ y1 decreases on ] -∞; ỹ1 ] ∩ Y. By symmetry, the function y → ℓ(y 2 , y) is non-decreasing on [ ỹ2 ; +∞[∩ Y. From ( 23) and ( 26), we get ĝpim (x) / ∈ [y 0 ; +∞[, which ends the proof of the upper bound of ĝpim (x).

For the lower bound, for any x ∈ X , by definition of ĥi , we have

ℓ[y 1 , ĥi (x)] -ℓ(y 1 , ỹ1 ) ≤ -1 λ log E g∼π -λΣ i e -λ{ℓ[y1,g(x)]-ℓ(y1, ỹ1)} = -1 λ log π -λΣi (g 1 ) + π -λΣi (g 2 )e -λδ ≤ δ.
By Jensen's inequality, we obtain

ℓ y1 [ĝ pim (x)] -ℓ y1 ( ỹ1 ) = ℓ[y 1 , 1 n+1 n i=0 ĥi (x)] -ℓ(y 1 , ỹ1 ) ≤ 1 n+1 n i=0 ℓ[y 1 , ĥi (x)] -ℓ(y 1 , ỹ1 ) ≤ δ = ℓ y1 ( ỹ2 ) -ℓ y1 ( ỹ1 ).
Since the function ℓ y1 decreases on ] -∞; ỹ2 ] ∩ Y, we get that ĝpim (x) ≥ ỹ2 , which ends the proof of (24). From (24), we obtain

R(ĝ pim ) -R(g 1 ) = 1+γ 2 ℓ(y 1 , ĝpim ) -ℓ(y 1 , ỹ1 ) + 1-γ 2 ℓ(y 2 , ĝpim ) -ℓ(y 2 , ỹ1 ) = 1+γ 2 ℓ y1 (ĝ pim ) -ℓ y1 ( ỹ1 ) + 1-γ 2 ℓ y1 (2a -ĝpim ) -ℓ y1 ( ỹ2 ) = 1+γ 2 δ + ℓ y1 (ĝ pim ) -ℓ y1 ( ỹ2 ) + 1-γ 2 -δ + ℓ y1 (2a -ĝpim ) -ℓ y1 ( ỹ1 ) ≥ γδ -(ĝ pim -ỹ2 )|ℓ ′ y1 ( ỹ2 )| ≥ γδ -C 2 log n n , (27)
with C 2 independent from γ. We may take γ = 2C2 δ (log n)/n and obtain: for n large enough, on the event E τ , we have R(ĝ pim ) -R(g 1 ) ≥ C log n/n. From Lemma 4, this inequality holds with probability at least 1/n C4 for some C 4 > 0. To conclude, for any n large enough, there exists ǫ > 0 s.t. with probability at least ǫ,

R(ĝ pim ) -R(g 1 ) ≥ c log(eǫ -1 ) n .
where c is a positive constant depending only on the loss function, the symmetry parameter a and the output values y 1 and ỹ1 .

Remark 1. Had we consider the progressive mixture rule, this last part of the proof would have been much simpler. Indeed, for n large enough, on the event E τ , from (13), we have

p 1 n+1 n i=0 π -λΣi (g 1 ) ≤ τ n+1 + sup τ ≤i≤n π -λΣi (g 1 ) ≤ C log n n and ĝpm = 1 n+1 n i=0 E g∼π -λΣ i g = pg 1 + (1 -p)g 2 ≡ ỹ2 + p( ỹ1 -ỹ2 ). So we have ỹ2 ≤ ĝpm ≤ ỹ2 + C log n n ≤ ỹ1 ,
which is much stronger than (24) (and much simpler to prove).

A Proof of Theorem 1

The first assertion is a direct consequence of Lemma 3. . We consider a m, 1 n+1 ∧ 1 m , 1 -hypercube of probability distributions with h 1 ≡ argmin y∈Y ℓ y1 (y) and h 2 ≡ argmin y∈Y ℓ y2 (y). We obtain

ER(ĝ) -min g∈G R(g) ≥ ⌊log 2 |G|⌋ n+1 ∧ 1 d I 1 -1 n+1 ∧ 1 ⌊log 2 |G|⌋ n ≥ ⌊log 2 |G|⌋ n+1 ∧ 1 d I e -1 ,
where the last inequality comes from [1 -1/(n + 1)] n ց e -1 . Now the edge discrepancy d I can be computed: where the last equality uses that the function y → ℓ(y1,y)+ℓ(y1,2a-y) 2 is convex. Finally, from the "well behaved at center" assumption, the supremum is positive.

d I = ψ 1,0,y1,y2 (1/2) = inf

B Proof of Theorem 2

Let g ∈ argmin G R and η > 0. Hoeffding's inequality applied to the random variable W = ℓ[Y, g(X)] -ℓ[Y, g(X)] ∈ [-B; B] for a fixed g ∈ G gives

Ee η[W -EW ] ≤ e η 2 B 2 /2 for any η > 0. Since the random variable Z 1 , . . . , Z n are independent, we obtain Ee η[nR(g)-nR(g)+Σn(g)-Σn(g)] ≤ e η 2 nB 2 /2 .

Consequently we have

n ER(ĝ erm ) -R(g) ≤ E nR(ĝ erm ) -nR(g) + Σ n (g) -Σ n (ĝ erm ) ≤ 1 η log Ee η[nR(ĝerm)-nR(g)+Σn(g)-Σn(ĝerm)] ≤ 1

η log E g∈G e η[nR(g)-nR(g)+Σn(g)-Σn(g)]

≤ 1 η log |G|e η 2 nB 2 /2 .
The first assertion follows from the (optimal) choice η = (2 log |G|)/(nB 2 ). The second assertion is based on an Assouad's type lower bound. Let y 2 = 2a -y 1 and m = ⌊log 2 |G|⌋. We use the notation introduced in [1, Section 8.1]. We consider a m, 1 m , dII -hypercube of probability distributions with h 1 ≡ ỹ1 and h 2 ≡ ỹ2 2a -ỹ1 and dII has to be optimized in [0; 1]. In the proof of Theorem 1, we take the set G such that min g∈G R(g) = min g R(g), where the second minimum is w.r.t. all possible prediction functions. Here the trick is to realize that min g∈G R(g) for our learning setting equals to min g R(g) for the learning task in which the output space is only { ỹ1 , ỹ2 }. Therefore we apply ([1, Inequality (8.17

  3 and Corollary 4.1 of [2]. The second assertion is based on an Assouad's type lower bound ([1, Inequality (8.19)]. Let y 2 = 2a -y 1 and m = ⌊log 2 |G|⌋. We use the notation introduced in [1, Section 8.1]

  y 1 , a) -ℓ(y 1 , y)],

2 =

 2 )] with the function φ appearing in the edge discrepancy d I defined as φ y1,y2 (p) = min y∈{ ỹ1, ỹ2} pℓ(y 1 , y) + (1 -p)ℓ(y 2 , y) . We getER(ĝ) ≥ min g∈G R(g) + mwd I 1 -√ nwd II = min g∈G R(g) + d I 1 -n m dII .From the symmetry and admissibility assumptions of the loss function, we have ℓ(y 2 , ỹ2 ) = ℓ(y 1 , ỹ1 ) > ℓ(y 2 , ỹ1 ) = ℓ(y 1 , ỹ2 ), hence δ ℓ(y 1 , ỹ2 ) -ℓ(y 1 , ỹ1 ) > 0. We obtaind I = ψ 1+ φ y1,y2 (1/2) -φ y1,y2The optimization of the lower bound leads us to choose dII = m 4n ∧ 1 and we get the desired result.

Indeed, if ξ denotes the function e -λℓy , from Jensen's inequality, for any probability distribution, Eℓy(Y) = E -1 λ log ξ(Y ) ≥ -1 λ log Eξ(Y ) ≥ -1 λ log ξ(EY ) = ℓy(EY ).