J.-B Doc

C Vergez

P Guillemain

J Kergomard

Sound production on a "coaxial saxophone"

Sound production on a "coaxial saxophone" is investigated experimentally. The coaxial saxophone is a variant of the cylindrical saxophone made up of two tubes mounted in parallel, which can be seen as a low-frequency analogy of a truncated conical resonator with a mouthpiece. Initially developed for the purposes of theoretical analysis, an experimental verification of the analogy between conical and cylindrical saxophones has never been reported. The present paper explains why the volume of the cylindrical saxophone mouthpiece limits the achievement of a good playability. To limit the mouthpiece volume, a coaxial alignment of pipes is proposed and a prototype of coaxial saxophone is built. An impedance model of coaxial resonator is proposed and validated by comparison with experimental data. Sound production is also studied through experiments with a blowing machine. The playability of the prototype is then assessed and proven for several values of the blowing pressure, of the embouchure parameter, and of the instrument's geometrical parameters.

Introduction

In the family of the single-reed instruments, the main difference between the clarinet and the saxophone is the shape of the resonator of the instrument. The resonance frequencies of these instruments exhibit different behaviors: cylindrical resonators produce mainly odd harmonics while conical resonators produce even and odd harmonics (when a mouthpiece with an adequate volume is used). In the literature [START_REF] Ollivier | Idealized Models of Reed Woodwinds. Part I: Analogy with the Bowed String[END_REF][START_REF] Ollivier | Idealized Models of Reed Woodwinds. Part II: On the Stability of "Two-Step" Oscillations[END_REF][START_REF] Dalmont | Reed instruments, from small to large amplitude periodic oscillations and the helmholtz motion analogy[END_REF], an analogy has been made and reveals that it is possible to produce even harmonics with resonators constructed with cylindrical tubes. This analogy was first suggested by Benade [START_REF] Benade | Equivalent circuits for conical waveguides[END_REF]. Based on a low frequency approximation, this analogy consists in representing a conical resonator by two cylindrical pipes with equal cross section areas mounted in parallel. A first tube is equivalent to a truncated cone (the resonator part), and the other tube represents the missing part of the truncated cone (the volume of which is usually equal to that of the mouthpiece). Note that this analogy corresponds also to a particular case of a series of stepped cones [START_REF] Dalmont | New lattices of sound tubes with harmonically related eigenfrequencies[END_REF]. Initially, this analogy was developed for the purpose of theoretical analysis, taking advantage of the fact that in the time domain the reflection functions are simpler for cylinders than for cones. However, in this analogy, the volume of the mouthpiece is considered to be null. This is why in [START_REF] Ollivier | Idealized Models of Reed Woodwinds. Part I: Analogy with the Bowed String[END_REF] the authors make the following remark: "...cylindrical saxophones cannot be built easily for experimental observations (because of the finite volume of a real mouthpiece)...". This would explain why, to our knowledge, no playable example of cylindrical saxophone has emerged. The aim of the present paper is to show how it is yet possible to produce sounds experimentally with a modified cylindrical saxophone -called coaxial saxophone in this paper. The first section recalls the analogy between conical and cylindrical saxophones and explains how the volume of the mouthpiece is harmful for the playability of the instrument with this geometry. The coaxial saxophone geometry is then introduced in Sec- tion 3: the coaxial alignment of the two cylindrical pipes makes it possible to minimize the damaging effect of the mouthpiece volume. Simulations and measurements on a prototype are studied in order to understand the modal behavior of a coaxial saxophone. Finally, the prototype is played with an artificial mouth and the sound produced is analyzed. Particular attention is paid to the nature of the oscillation regimes -periodic or not -which are produced by this instrument according to the control parameters imposed by the musician.

Problem statement

This section recalls the analogy between conical and cylindrical saxophones in order to highlight the main limitation of this analogy for the sound production. In [START_REF] Ollivier | Idealized Models of Reed Woodwinds. Part I: Analogy with the Bowed String[END_REF], it is shown that, at low frequencies, a conical resonator can be analogous to two cylindrical tubes mounted in parallel. For a truncated cone with a cylindrical mouthpiece whose volume is the same as the missing volume of the cone (see Fig. 1(a)), the input impedance is:

Z tc = jZ c 1 kL m - kL m 3 + cot kL c -1 , (1)
where Z c = ρc/S. S is the cross section area of the small end of the truncated cone, ρ is the air density, and c is the speed of sound. L m is the length of the mouthpiece, L c is the length of the truncated cone and k is the wavenumber. For cylindrical resonators mounted in parallel (see Fig. 1(b)), the input impedance is:

Z ts = jZ c (cot kL a + cot kL b ) -1 , (2)
where L a and L b are the lengths of the two cylinders.

Within the low frequency approximation, Equation ( 1) is an expansion of Eq. ( 2) at the third order provided that L b = L c and L a = L m . But the analogy between these two equations has no practical application since the mouthpiece is not taken into account in Eq. ( 2). From Eq. ( 2) it can be deduced that the resonance frequencies of two cylindrical resonators mounted in parallel are perfectly harmonic. Adding a mouthpiece to this cylindrical saxophone (sketched in Fig. 1(c)) results in an alteration of the harmonicity of the impedance peaks of the instrument.

The impedance curves plotted in Fig. 2 are obtained through simulations for the three resonator geometries presented in Fig. 1. The parameters used for these simulations are detailed as follows. The conical resonator has an input radius r c = 7.5 • 10 -3 m, the apex angle is θ = 0.035rad, the length of the conical tube is L c = 0.72m and the length of the mouthpiece is L m = 0.08m.

The cylindrical saxophone has a radius r = 7.5 • 10 -3 m, the lengths of the two mounted cylinders are L b = 0.75m and L a = 0.185m, respectively. The mouthpiece has a radius r = 7.5 • 10 -3 m, and its length is determined by the value of the inner volume, V m = 1.5 • 10 -5 m 3 (standard values for tenor saxophone mouthpieces). The mouthpiece is treated as a cylindrical tube plugged in series with the resonator. These input impedances illustrate that at low frequencies the analogy between a conical and a cylindrical saxophone is basically valid in the absence of a mouthpiece. The low frequency limit is represented by the anti-resonance localized near 900 Hz (depending on the geometrical dimensions of the cylindrical saxophone [START_REF] Ollivier | Idealized Models of Reed Woodwinds. Part I: Analogy with the Bowed String[END_REF]). Below this limit the values of resonance frequencies are similar for the first three peaks. Differences between peak amplitudes are explained by larger visco-thermal losses in the cylindrical saxophone compared with a conical saxophone.

The addition of the mouthpiece strongly modifies the input impedance of the cylindrical saxophone. Indeed, the addition of a mouthpiece results in two defects. The first one is a significant alteration of the harmonicity of the resonance frequencies. For instance, focusing on the two lowest resonance frequencies f 1 and f 2 , the ratio f 2 /f 1 = 2 without mouthpiece and f 2 /f 1 = 1.9 when the mouthpiece is added. As studied in previous work [START_REF] Doc | Oscillation regimes produced by an alto saxophone: Influence of the control parameters and the bore inharmonicity[END_REF], inharmonicity favors the bifurcation towards non-conventional oscillation regimes, such as multiphonic sounds and squeaks. The second effect of the mouthpiece is to generate an additional resonance, around 950 Hz. This resonance is due to the discontinuity between the mouthpiece cross-section and the connection of the two cylindrical tubes (the effective cross-section is doubled at the connection). Note that the frequency of this additional resonance is related to the length of the mouthpiece (quarter wave resonance). Furthermore, it can be observed that the amplitude of this resonance is greater than that the other resonance amplitudes. This hinders the emergence of self-sustained oscillations corresponding to the two lower registers. These two modifications of the input impedance caused by the addition of a mouthpiece suggest some trouble with the instrument playability. To ensure the ease of playing, the effect of the mouthpiece needs to be minimized, and a suitable geometry for the cylindrical saxophone has to be sought.

3 Coaxial resonator

Description of the coaxial geometry

In order to minimize the effect of the mouthpiece volume, a coaxial geometry is chosen, replacing the original alignment of the pipes. The geometry proposed is sketched in Fig. 3. The construction of the coaxial geometry ensures that the cross-section area at the end of the mouthpiece is equal to the sum of the cross-section areas of the two cylinders: no discontinuity occurs and thus the emergence of any additional resonance is avoided.

A prototype is constructed according to the geometrical dimensions presented in Table 1. For the design of this prototype, simulations of input impedances have been carried out, as detailed in Section 3.2.1. The prototype outer and inner tubes are made of plexiglass and copper, respectively. The inner tube is centered inside the outer tube by means of two rows of support needles (see Fig. 3). Several lengths of copper tubes are used to test different playing frequencies. In order to ensure the analogy with a conical resonator, the diameter and the thickness of the inner tube are chosen so that its cross-section area is equal to that of the annular gap between the two cylinders. A standard tenor saxophone mouthpiece is used (Yamaha 4C model). The bore of this mouthpiece is cylindrical. In order to minimize the effective mouthpiece volume, the cylindrical part of the mouthpiece is associated with the outer tube. To achieve this, the inner cylinder is inserted inside the mouthpiece up to x = 0 (see Fig. 3).

Input impedance of a coaxial resonator

The coaxial saxophone can be viewed as a particular case of the cylindrical saxophone. Therefore, it is necessary to verify how a classical model of cylindrical saxophone can be modified to correctly represent the coaxial alignment of the tubes. An experimental and numerical study of the input impedance of the coaxial resonator is then carried out in order to highlight the effect of the geometrical parameters.

Computation of input impedances

Input impedances of coaxial saxophones are computed in the same way as those of cylindrical saxophones (see Section 2). The visco-thermal losses at the walls are greater in the annular region than in a simple cylindrical pipe. A crude approximation is made: visco-thermal losses are assumed to be proportional to the wall area of the annular region (on the interval x = [0, L a ]). For further discussion about this assumption, see [START_REF] Backus | Acoustic impedance of an annular capillary[END_REF][START_REF] Kergomard | Measurement of acoustic impedance using a capillary: An attempt to achieve optimization[END_REF]. Therefore, the ratio µ between the surfaces of the inner and outer walls of the annular guide is defined:

µ = 2πL a (r a + r b ) 2πL a r b . (3)
To ensure the analogy with the cylindrical saxophone, the cross-sectional area of the annular gap must be equal to that of the inner tube (S a = S b ), thus r a = √ 2r b leads to µ = 1 + √ 2. Notice that if the coefficient µ was ignored, the height of the impedance peaks would be overestimated, but the overall shape of the input impedances would be preserved. The input impedance of the coaxial saxophone is given by:

Z cs = jZ c (cot k a L a + cot k b L b ) -1 , (4)
where the wavenumbers k b and k a are expressed [START_REF] Chaigne | Acoustics of musical instruments[END_REF] with the ratio µ as:

k b = k 0 1 + 1.044 √ -2j r v b (5)
and

k a = k 0 1 + µ 1.044 √ -2j r v a . (6)
The Stokes numbers for the inner and the outer tubes are expressed as

r v a = r a k 0 /l v and r v b = r b k 0 /l v ,
where k 0 = ω/c and l v is the viscous characteristic length. It remains to use an approximation for the radiation of the outer tube. Despite to the annular bore between the outer and the inner tubes, it is assumed to radiate like a cylindrical tube. Therefore, the radiation impedance for both tubes is that of a tube without flange Z c j0.61kr b + 1 4 (kr b ) 2 . At low frequencies, this approximation is rigorous concerning the real part of the impedance (because of the energy conservation) whereas is it crude for the imaginary part of the radiation impedance.

Validation of the impedance model

To validate the impedance model of coaxial saxophone, experiments are carried out for various values of length L a and L b . First, simulated and measured input impedances for different lengths L b are compared in Fig. 4. The apparatus developed in [START_REF] Dalmont | A new impedance sensor for wind instruments[END_REF] is used for the measurement of the input impedances. No mouthpiece is considered for the impedance measurement, the impedance sensor is plugged at position x = 0 (see the Fig. 3). A qualitative agreement is observed between measurements and simulations (see Fig. 4). The multiplicative coefficient µ models correctly the viscothermal losses in the annular region, since the heights of the resonance peaks are well estimated. Thus, the model of coaxial saxophone presented previously can be used for the design of more advanced prototypes.

Influence of the mouthpiece volume

The influence of the mouthpiece volume is now studied experimentally, focussing on the inharmonicity of the two lowest resonance frequencies. In order to modify experimentally the mouthpiece volume on the prototype, the inner tube is pulled from x = 0 to x = x * > 0 (see Fig. 3). The reduction of the outer tube length (from L a to L ax * ) allows easy change of the mouthpiece volume to an arbitrary value. Inharmonicity arising from this modification of L a is much lower than that brought by the addition of an equivalent mouthpiece volume (this fact was verified according to simulations). For the inharmonicity estimation, resonance frequencies are obtained from the zero crossing of the input impedance phase. The inharmonicity between the first two resonance frequencies is defined as η = f 2 /(2f 1 ) -1. Fig. 5 shows that the larger the mouthpiece volume, the greater the inharmonicity. The most relevant piece of information is that a high range of inharmonicity is obtained with standard values of mouthpiece volume.

For most resonator lengths L b , the inharmonicity is greater than 2.5%, which may limit the stability of the first periodic oscillation regimes [START_REF] Doc | A Minimal Model of a Single-Reed Instrument Producing Quasi-Periodic Sounds[END_REF] (ideally the inharmonicity should be zero). This result highlights why a mouthpiece with a short chamber should be preferred for playing a saxophone with coaxial geometry. Indeed, the volume of the mouthpiece mostly brings a negative inharmonicity and thus the global inharmonicity of the coaxial resonator is deteriorated -which does not happen with a troncated cone.

Influence of the length of the outer tube

Other experiments are carried out to study the influence of the outer tube on the input impedance of the coaxial saxophone. Fig. 6 presents the amplitude ratio A 2 /A 1 between the two first resonance peaks as a function of the length L a of the outer tube. The equivalent mouthpiece volume is modified when L a is shifted, but this has a negligible influence on the amplitude ratio compared to the influence of the increase in L b . This has been confirmed by simulations.

Results reveal that the shorter the outer length L a , the higher the amplitude ratio A 2 /A 1 . This is consistent with what is happening with a conical saxophone. For the shorter outer tubes tested, the amplitude of the second resonance becomes larger than twice the first one. Furthermore, Fig. 6 shows that the overall evolution of the relative amplitude of the two first resonance frequencies can be different from one resonator length L b to another. In particular, it can be observed than for a short resonator tube (L b = 29.4cm) the amplitude of the first impedance peak is almost always higher than that of the second peak, even for a short outer tube (L a = 12.3cm). Similar effects are observed with conical saxophones when the resonator conicity increases. Indeed, in the context of the analogy with the conical saxophone, modifying L a can be seen as a way to adjust the conicity of the instrument [START_REF] Kergomard | Idealized digital models for conical reed instruments, with focus on the internal pressure waveform[END_REF]. In practice, a simple change in the length of the external cylinder is expected to modify the tone color regardless of the fingering played. This is exemplified in the next section.

Sound production on a coaxial saxophone

In order to study the sound production, an artificial mouth is used to play the prototype of coaxial saxophone in controlled conditions.

Experimental setup

A photo of the experimental device is shown in Fig. 7.

The coaxial saxophone is connected to the artificial mouth at the level of the mouthpiece (played with a Hemke premium reed with force 4). Inside the artificial mouth, an artificial lip is pressed against the reed and brings the required damping to avoid squeaks when playing the instrument [START_REF] Silva | Interaction of reed and acoustic resonator in clarinetlike systems[END_REF]. The artificial lip is made with a latex tube filled with water through a syringe.

The bearing force of the lip on the reed is controlled by the water pressure imposed by the syringe. The artificial lip is placed around 1cm downstream from the tip of the reed. The experimental device used in this study has been used for a previous study [START_REF] Doc | Oscillation regimes produced by an alto saxophone: Influence of the control parameters and the bore inharmonicity[END_REF] where details concerning its functioning are given.

In order to measure the acoustic signal produced by the instrument, an Endevco pressure microphone (8507C-5 model) is inserted into the mouthpiece. Another similar sensor is used to measure the static pressure in the artificial mouth to control in real-time the servo-valve regulating the supply pressure through a closed-loop system (technical details are available in [START_REF] Ferrand | High-precision regulation of a pressure controlled artificial mouth: The case of recorder-like musical instruments[END_REF]). In addition, a Burkert flowmeter (8701 model) is used to measure the volume flow entering the instrument. A National Instrument acquisition module (NI9215) uses a sampling frequency of 44kHz to digitize the experimental signals, which are then recorded on a computer.

The control parameters imposed by the artificial mouth are estimated by recording the air flow entering the instrument and the static pressure [START_REF] Doc | Oscillation regimes produced by an alto saxophone: Influence of the control parameters and the bore inharmonicity[END_REF]. The embouchure parameter ζ and the blowing pressure γ are considered to be independent. These dimensionless parameters are estimated experimentally from the measurement of the so-called nonlinear characteristics of the exciter [START_REF] Dalmont | Nonlinear characteristics of single-reed instruments: Quasistatic volume flow and reed opening measurements[END_REF] (noted NLC hereafter).

After each modification of the bearing force of the artificial lip on the reed (by acting on the syringe), the NLC is measured. By fitting the measurement with the NLC model [START_REF] Dalmont | Nonlinear characteristics of single-reed instruments: Quasistatic volume flow and reed opening measurements[END_REF], the maximum airflow U max and the corresponding pressure difference P max are estimated.

The embouchure parameter ζ is then obtained through the following relation [START_REF] Dalmont | Nonlinear characteristics of single-reed instruments: Quasistatic volume flow and reed opening measurements[END_REF]:

ζ = √ 3 2
U max P max Z c . (7)
Likewise, the dimensionless blowing pressure is estimated from the following relationship:

γ = P m 3P max , (8)
with P m the static supply pressure. More details about the estimation of the control parameters γ and ζ can be found in [START_REF] Doc | Oscillation regimes produced by an alto saxophone: Influence of the control parameters and the bore inharmonicity[END_REF].

Note that the control parameters γ and ζ are dimensionless. The minimum pressure required for the complete closure of the reed channel corresponds to γ = 1. When the bearing force of the lip on the reed is large enough to completely close the reed channel, the parameter ζ vanishes.

Mouthpiece pressure waveform

One way to describe sound production on a coaxial saxophone consists in studying the mouthpiece pressure waveform.

Figs. 8(a) shows the mouthpiece pressure signal. It is similar to the classical Helmholtz motion obtained for conical reed instruments [START_REF] Dalmont | Reed instruments, from small to large amplitude periodic oscillations and the helmholtz motion analogy[END_REF][START_REF] Kergomard | Idealized digital models for conical reed instruments, with focus on the internal pressure waveform[END_REF], with a v-shaped episode followed by a quasi-plateau. Furthermore, Fig. 8(b) shows that the sound contains both even and odd harmonics. Therefore the analogy between conical and coaxial saxophones is verified experimentally. In Figs. 8, it can also be observed that the length L a of the outer tube, which corresponds to the truncated part of the cone, modifies the internal waveform. The length of the outer tube can be viewed as the parameter that determines an equivalent conicity (apex angle of the cone) [START_REF] Kergomard | Idealized digital models for conical reed instruments, with focus on the internal pressure waveform[END_REF]. The spectral content of sounds produced by the coaxial saxophone may be modified by the adjustment of the length L a . As shown in Fig. 8(b), the shorter the outer tube, the greater the second and third harmonic (compared to the first one). Therefore, the tone color of a coaxial saxophone can be easily modified just by adjusting (or changing) the length of outer tube. Likewise, Fig. 8(b) shows that the playing frequency also depends on the length of the outer tube. This is particularly useful in practice for the tuning of the instrument.

Maps of the oscillation regimes in the control parameter space

A general overview of the sound production can be obtained by deriving maps of oscillation regimes with respect to the control parameters γ and ζ. For this purpose, the methodology detailed in a previous work [START_REF] Doc | Oscillation regimes produced by an alto saxophone: Influence of the control parameters and the bore inharmonicity[END_REF] is applied to the prototype of coaxial saxophone. For a linearly increasing ramp of the blowing pressure, the parameters space is spanned by horizontal lines corresponding to the constant embouchure setting ζ. For each value of ζ, a spectrogram of the mouthpiece pressure signal is computed. This is relevant because the pressure ramps used during the experiments are very slow (about one minute from the minimum to maximum pressure value).

The same qualitative results are obtained with upward and downward ramps. For each value of ζ obtained experimentally, instantaneous frequencies and amplitudes are estimated on the spectrogram by the Matlab function findpeaks. An algorithm is used to classify these data into different oscillation regimes. Three types of regimes are identified: a static regime (no sound), a quasi-periodic regime (multiphonic sound, noted QP in Fig. 9) and a periodic regime. Different playing frequencies of periodic regimes are possible and are represented by a register index. In Fig. 9, R1 and R2 correspond to the first and second registers, respectively. Fig. 9 shows maps for four different lengths of the resonator L b , which can be seen as different fingerings, while the length of the outer tube is kept constant. Each regime is symbolized by a particular color.

The main periodic regimes of self-sustained oscillations produced by the coaxial saxophone are associated with the two first resonance frequencies of the instrument. This result was expected since, as shown in Fig. 4, the amplitudes of these two resonance peaks are higher than those of the other resonances peaks. Consequently, the bifurcation to these registers is favored. Overall, the range of control parameters available to play the different registers of the instrument is rather wide. Although quantitative, these results indicate the good playability of the instrument, since registers can be stable even for large variations of γ. Furthermore, quasi-periodic oscillations also appear on the maps in Fig. 9. This is related, at least partly, to the inharmonicity due to the mouthpiece (as detailed in Sections 2 and 3). For the two following resonator lengths, L b = 29.4cm and L b = 35.8cm (see Figs. 9(a) and 9(b)), quasi-periodicity is very rare and appears only as a transition between the two periodic registers. Thus, quasi-periodicity does not appear here as a defect that could alter the playability of the instrument. However for the resonator lengths L b = 41.5cm and L b = 50cm, quasi-periodicity is more present. Indeed, as shown in Figs. 5 and6, the inharmonicity and the relative amplitude of the second resonance are greater for longer resonators. This feature of the coaxial resonator is an aggravating factor that favors the production of quasi-periodic regimes [START_REF] Doc | A Minimal Model of a Single-Reed Instrument Producing Quasi-Periodic Sounds[END_REF]. This explains why periodic regimes are less widespread for Figs. 9(c) and 9(d).

In summary, the maps in Fig. 9 show the variability of oscillation regimes playable with a coaxial saxophone. Extensive ranges of periodic regimes are playable, which illustrates the good playability of the coaxial saxophone. However, in the design of a more complete instrument, some properties concerning resonances of the instrument (such as inharmonicity) are to be avoided in order to provide a good stability in periodic sound production. Moreover, this is important to avoid strong adjustments in control parameters that the musician may have to impose between two fingerings.

Conclusion

The results presented above show that a coaxial geometry makes it possible to experimentally verify the cylindrical saxophone analogy. The prototype of coaxial saxophone presented in this paper can produce periodic oscillation with a waveform very similar to that of conical resonators. The measurement of maps in the control parameter space illustrates the playability of the first two registers of the instrument. The use of an impedance model proves that the mouthpiece volume must be minimized to favor the playability of the instrument. Similarly, it is shown that the coaxial alignment of the two tubes prevents a parasitic resonance limiting the stability of periodic regimes.

As shown by the patent recently published about original pipe structures for wind instruments [START_REF] Masuda | Wind instrument and pipe structure thereof and a method of operating the wind instrument[END_REF][START_REF] Masuda | Wind instrument and pipe structure thereof and a method of operating the wind instrument[END_REF], there is an industrial interest for radically new types of acoustic resonators. With an aim towards realistic musical instruments, current research could be applied to the coaxial saxophone. Numerical optimization could be applied to help the instrument maker to design a complete instrument [START_REF] Noreland | The Logical Clarinet: Numerical Optimization of the Geometry of Woodwind Instruments[END_REF] (resonator geometry, position of the side holes, etc). Finally, the study of bifurcation mechanisms, associated with the analysis of musicians' playing strategies, would make it possible to anticipate the playability and the stability of a complete instrument.

Fig. 1 :

 1 Fig. 1: Schematics of: (a) a conical resonator with mouthpiece, (b) a cylindrical saxophone without mouthpiece and (c) a cylindrical saxophone with mouthpiece.

2 Fig. 2 :

 22 Fig. 2: Simulated input impedance for: a conical resonator with mouthpiece, a cylindrical saxophone (dashed line) and a cylindrical saxophone with mouthpiece. The input radius and the length of the conical resonator are rc = 7.5 • 10 -3 m and Lc = 0.72m respectively. The cylindrical saxophone has a radius r = 7.5 • 10 -3 m, the lengths of the two mounted cylinders are L b = 0.75m and La = 0.185m respectively. The mouthpiece volume is Vm = 1.5 • 10 -5 m 3 .

Fig. 3 :

 3 Fig. 3: Schematic of the coaxial geometry. No discontinuity is present at the connection between the mouthpiece and the resonator. The cylindrical part of the mouthpiece is extended by the outer tube inserted therein. r b e L b (max) Inner tube 5.5mm 0.975mm 0.5m r a L a (max) Outer tube 8.5mm 0.163m

Fig. 4 :

 4 Fig. 4: Comparison between the measured input impedance for the coaxial prototype and the simulated impedance for a cylindrical saxophone without mouthpiece (see Section 3.2.1), = 16.3cm and L b is varying.

Fig. 5 :

 5 Fig. 5: Measured inharmonicity between the two first impedance peaks as a function of the equivalent volume of the mouthpiece.

1 |Fig. 6 :

 16 Fig.6: Measured amplitude ratio between the two first resonance peaks as a function of the length of the outer tube.

Fig. 7 :

 7 Fig. 7: Picture of the experimental device and the prototype of coaxial saxophone.

Fig. 8 :

 8 Fig. 8: (a) Mouthpiece pressure signal and (b) its spectrum amplitude measured for different lengths of the outer tube La. The resonator length is constant L b = 35.8cm. The control parameters are γ = 0.31 and ζ = 0.44.

Fig. 9 :

 9 Fig. 9: Mapping of the oscillation regimes for different lengths of the internal tube L b in the space of the control parameters (γ, ζ). The length of the outer tube is set at La = 16.3cm. R1 and R2 correspond to the first and second registers, respectively, while QP means quasi-periodicity.

Table 1 :

 1 Dimensions of the prototype of coaxial resonator. ra and La are the radius and the length of the outer tube, r b and L b those of the inner tube. e is the wall thickness of the inner tube.

Acknowledgements

This work was done in the frameworks of Labex MEC (ANR-10-LABX-0092) and of the A*MIDEX project (ANR-11-IDEX-0001-02), funded by the French National Research Agency (ANR). It was also supported by the CAGIMA project financed by the French National Research Agency (project ANR-11-BS09-022).


Aurélien Bellet
email: aurelien.bellet@telecom-paristech.fr.

Yingyu Liang
email: yingyul@cs.princeton.edu

Alireza Bagheri Garakani

Maria-Florina Balcan

§ Fei

A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning

Learning sparse combinations is a frequent theme in machine learning. In this paper, we study its associated optimization problem in the distributed setting where the elements to be combined are not centrally located but spread over a network. We address the key challenges of balancing communication costs and optimization errors. To this end, we propose a distributed Frank-Wolfe (dFW) algorithm. We obtain theoretical guarantees on the optimization error and communication cost that do not depend on the total number of combining elements. We further show that the communication cost of dFW is optimal by deriving a lowerbound on the communication cost required to construct an -approximate solution. We validate our theoretical analysis with empirical studies on synthetic and real-world data, which demonstrate that dFW outperforms both baselines and competing methods. We also study the performance of dFW when the conditions of our analysis are relaxed, and show that dFW is fairly robust.

Introduction

Most machine learning algorithms are designed to be executed on a single computer that has access to the full training set. However, in recent years, large-scale data has become increasingly distributed across several machines (nodes) connected through a network, for storage purposes or because it is collected at different physical locations (as in cloud computing, mobile devices or wireless sensor networks [START_REF] Lewis | Wireless sensor networks. Smart environments: technologies, protocols, and applications[END_REF][START_REF] Armbrust | A view of cloud computing[END_REF]). In these situations, communication between machines is often the main bottleneck and the naive approach of sending the entire dataset to a coordinator node is impractical. This distributed setting triggers many interesting research questions. From a fundamental perspective, studying the tradeoff between communication complexity [START_REF] Yao | Some complexity questions related to distributive computing[END_REF][START_REF] Abelson | Lower bounds on information transfer in distributed computations[END_REF] and learning/optimization error has recently attracted some interest [START_REF] Balcan | Distributed Learning, Communication Complexity and Privacy[END_REF][START_REF] Daumé | Protocols for learning classifiers on distributed data[END_REF][START_REF] Shamir | Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation[END_REF]. From a more practical view, a lot of research has gone into developing scalable algorithms with small communication and synchronization overhead (see for instance [START_REF] Lazarevic | Boosting Algorithms for Parallel and Distributed Learning[END_REF][START_REF] Forero | Consensus-Based Distributed Support Vector Machines[END_REF][START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF][START_REF] Duchi | Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling[END_REF][START_REF] Dekel | Optimal Distributed Online Prediction Using Mini-Batches[END_REF][START_REF] Balcan | Distributed k-means and k-median clustering on general communication topologies[END_REF][START_REF] Yang | Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent[END_REF] and references therein).

In this paper, we present both theoretical and practical results for the problem of learning a sparse combination of elements (atoms) that are spread over a network. This has numerous applications in machine learning, such as LASSO regression [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], support vector machines [START_REF] Cortes | Support-Vector Networks[END_REF], multiple kernel learning [START_REF] Bach | Multiple kernel learning, conic duality, and the SMO algorithm[END_REF], 1 -Adaboost [START_REF] Shen | On the Dual Formulation of Boosting Algorithms[END_REF] and sparse coding [START_REF] Lee | Efficient sparse coding algorithms[END_REF]. Formally, let A = [a 1 . . . a n ] ∈ R d×n be a finite set of n d-dimensional atoms (one per column). Here, atoms broadly refer to data points, features, dictionary elements, basis functions, etc, depending on the application. We wish to find a weight vector α ∈ R n (α i giving the weight assigned to atom i) that minimizes some cost function f (α) = g(Aα) under a sparsity constraint: 1(1.1) min

α∈R n f (α) s.t. α 1 ≤ β,
where the cost function f (α) is convex and continuously differentiable and β > 0.

We propose a distributed Frank-Wolfe (dFW) algorithm, a novel approach to solve such distributed sparse learning problems based on an adaptation of its centralized counterpart [START_REF] Frank | An algorithm for quadratic programming[END_REF][START_REF] Clarkson | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF]. Intuitively, dFW is able to determine, in a communication-efficient way, which atoms are needed to reach an -approximate solution, and only those are broadcasted through the network. We also introduce an approximate variant of dFW that can be used to balance the amount of computation across the distributed machines to reduce synchronization costs. In terms of theoretical guarantees, we show that the total amount of communication required by dFW is upper-bounded by a quantity that does not depend on n but only on , d and the topology of the network. We further establish that this dependency on and d is worst-case optimal for the family of problems of interest by proving a matching lower-bound of Ω(d/ ) communication for any deterministic algorithm to construct an -approximation. Simple to implement, scalable and parameter-free, dFW can be applied to many distributed learning problems. We illustrate its practical performance on two learning tasks: LASSO regression with distributed features and Kernel SVM with distributed examples. Our main experimental findings are as follows: (i) dFW outperforms baseline strategies that select atoms using a local criterion, (ii) when the data and/or the solution is sparse, dFW requires less communication than ADMM, a popular competing method, and (iii) in a real-world distributed architecture, dFW achieves significant speedups over the centralized version, and is robust to random communication drops and asynchrony in the updates.

Outline Section 2 reviews the Frank-Wolfe algorithm in the centralized setting. In Section 3, we introduce our proposed dFW algorithm and an approximate variant of practical interest, as well as examples of applications. The theoretical analysis of dFW, including our matching communication lower bound, is presented in Section 4. Section 5 reviews some related work, and experimental results are presented in Section 6. Finally, we conclude in Section 7.

The Frank-Wolfe Algorithm

The Frank-Wolfe (FW) algorithm [START_REF] Frank | An algorithm for quadratic programming[END_REF][START_REF] Clarkson | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF], also known as Conditional Gradient, is a procedure to solve convex constrained optimization problems of the form min α∈D f (α) where f is convex and continuously differentiable, and D is a compact convex subset of any vector space (say R n ). The basic FW algorithm is shown in Algorithm 1. At each iteration, it moves towards a feasible point s that minimizes a linearization of f at the current iterate. The stopping criterion uses a surrogate optimality gap that can be easily computed as a by-product of the algorithm. Let α * be an optimal solution. Theorem 2.1 shows that FW finds anapproximate solution in O(1/ ) iterations.

Theorem 2.1. ( [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF]) Let C f be the curvature constant of f . 2 Algorithm 1 terminates after at most 6.75C f / iterations and outputs a feasible point α which satisfies f ( α) -f (α * ) ≤ . 2 The assumption of bounded C f is closely related to that of L-Lipschitz continuity of ∇f with respect to an arbitrary chosen norm • . In particular, we have

C f ≤ L diam • (D) 2 [22].
Algorithm 1 FW algorithm on general domain D (k) , where γ = 2 k+2 or obtained via line-search. 5: end for 6: stopping criterion:

1: Let α (0) ∈ D 2: for k = 0, 1, 2, . . . do 3: s (k) = arg min s∈D s, ∇f (α (k) ) 4: α (k+1) = (1 -γ)α (k) + γs
α (k) -s (k) , ∇f (α (k) ) ≤ Algorithm 2 Compute s (k) for 1 / simplex 1: if 1 constraint 2: j (k) = arg max j∈[n] ∇f (α (k) ) j 3: s (k) = sgn -∇f (α (k) ) j (k) βe j (k) 4: else if simplex constraint 5: j (k) = arg min j∈[n] ∇f (α (k) ) j 6: s (k) = e j (k)
Solving the subproblems The key step in FW is to solve a linear minimization subproblem on D (step 3 in Algorithm 1). When the extreme points of D have a special structure (e.g., when they are sparse), it can be exploited to solve this subproblem efficiently. In particular, when D is an 1 norm constraint as in problem (1.1), a single coordinate (corresponding to the largest entry in the magnitude of the current gradient) is greedily added to the solution found so far (Algorithm 2). Taking α (0) = 0, we get α 0 ≤ 6.75C f / . Combining this observation with Theorem 2.1 shows that Algorithm 1 always finds an -approximate solution to problem (1.1) with O(1/ ) nonzero entries, which is sometimes called an -coreset of size O(1/ ) [START_REF] Shalev-Shwartz | Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints[END_REF][START_REF] Jaggi | Sparse Convex Optimization Methods for Machine Learning[END_REF]. It turns out that this is worst-case optimal (up to constant terms) for the family of problems (1.1), as evidenced by the derivation of a matching lower bound of Ω(1/ ) for the sparsity of an -approximate solution [START_REF] Jaggi | Sparse Convex Optimization Methods for Machine Learning[END_REF]. 3Another domain D of interest is the unit simplex ∆ n = {α ∈ R n : α ≥ 0, i α i = 1}. The solution to the linear subproblem, shown in Algorithm 2, also ensures the sparsity of the iterates and thus leads to an -approximation with O(1/ ) nonzero entries, which is again worst-case optimal [START_REF] Clarkson | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF].

For both domains, the number of nonzero entries depends only on , and not on n, which is particularly useful for tackling large-scale problems. These results constitute the basis for our design of a distributed algorithm with small communication overhead.

Algorithm 3 Distributed Frank-Wolfe (dFW) algorithm for problem (1.1)

1: on all nodes: α (0) = 0 2: for k = 0, 1, 2, . . . do 3:

on each node v i ∈ V : • j (k) i = arg max j∈Ai ∇f (α (k) ) j
// find largest entry of the local gradient in absolute value

• S (k) i = j∈Ai α (k) j ∇f (α (k) ) j
// compute partial sum for stopping criterion

• broadcast g (k) i = ∇f (α (k) ) j (k) i and S (k) i 4:
on each node v i ∈ V :

• i (k) = arg max i∈[N ] g (k) i
// compute index of node with largest overall gradient on all nodes: k) , where γ = 2 k+2 or line-search 6: end for 7: stopping criterion:

• if i = i (k) then broadcast j (k) = j (k) i and a j (k) end if //
α (k+1) = (1 -γ)α (k) + γ sgn -g (k) i (k) βe j (
N i=1 S (k) i + β g (k) i (k) ≤ 3 Distributed Frank-Wolfe (dFW) Algorithm
We now focus on the problem of solving (1.1) in the distributed setting. We consider a set of N local nodes V = {v i } N i=1 which communicate according to an undirected connected graph G = (V, E) where E is a set of M edges. An edge (v i , v j ) ∈ E indicates that v i and v j can communicate with each other. To simplify the analysis, we assume no latency in the network and synchronous updates -our experiments in Section 6 nonetheless suggest that these simplifying assumptions could be relaxed.

The atom matrix A ∈ R d×n is partitioned columnwise across V . Formally, for i ∈ [N ], let the local data of v i , denoted by A i ⊆ [n], be the set of column indices associated with node v i , where i A i = [n] and A i A j = ∅ for i = j. The local gradient of v i is the gradient of f restricted to indices in A i . We measure the communication cost in number of real values transmitted.

Basic Algorithm

Our communication-efficient procedure to solve (1.1) in the distributed setting is shown in Algorithm 3. 4 The algorithm is parameterfree and each iteration goes as follows: (i) each node first identifies the largest component of its local gradient (in absolute value) and broadcasts it to the other nodes (step 3), (ii) the node with the overall largest value broadcasts the corresponding atom, which will be needed by other nodes to compute their local gradients in subsequent iterations (step 4), and (iii) all nodes perform a FW update (step 5). We have the following result. Proof. We prove this by showing that dFW performs Frank-Wolfe updates and that the nodes have enough information to execute the algorithm. The key observation is that the local gradient only depends on local data and atoms received so far. Details can be found in the extended version of this paper [START_REF] Bellet | A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning[END_REF]. Theorem 3.1 shows that dFW allows a trade-off between communication and optimization error without dependence on the total number of atoms, which makes the algorithm very appealing for large-scale problems. The communication cost depends only linearly on 1/ , d and the network topology.

An Approximate Variant

Besides its strong theoretical guarantees on optimization error and communication cost, dFW is very scalable, as the local computational cost of an iteration typically scales linearly in the number of atoms on the node. However, if these local costs are misaligned, the algorithm can suffer from significant wait time overhead due to the synchronized updates.

To address this issue, we propose an approximate variant of dFW which can be used to balance or reduce the effective number of atoms on each node. The algorithm is as follows. First, each node v i clusters its local dataset A i into m i groups using the classic greedy m-center algorithm in [START_REF] Teofilo | Clustering to minimize the maximum intercluster distance[END_REF], which repeatedly C = C ∪ {a j }, where j = arg max j∈A d(a j , C) with d(a j , C) = min l∈C a j -a l 1 Algorithm 5 Approximate dFW algorithm

1: on each node v i ∈ V : α (0) = 0; C i = GreedySelection(∅, m (0) i ) 2: for k = 0, 1, 2, . . . do 3:
perform the same steps as in Algorithm 3, except that j

(k) i is selected from C i 4: on each node v i ∈ V : C i = GreedySelection(A i , C i , m (k+1) i -m (k) i ) 5: end for
adds a new center that is farthest from the current set of centers (Algorithm 4). Then, dFW is simply run on the resulting centers. Intuitively, each original atom has a nearby center, thus selecting only from the set of centers is optimal up to small additive error that only leads to small error in the final solution. Optionally, we can also gradually add more centers so that the additive error scales as O(1/k), in which case the error essentially does not affect the quality of the final solution. The details are given in Algorithm 5, and we have the following result (the proof is in the extended version [START_REF] Bellet | A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning[END_REF]). Lemma 3.1. Let r opt (A, m) denote the optimal 1radius of partitioning the local data indexed by A into m clusters, and let r opt (m) := max i r opt (A i , m i ). Let G := max α ∇g(Aα) ∞ . Then, Algorithm 5 computes a feasible solution with optimality gap at most +O(Gr opt (m 0 )) after O(1/ ) iterations. Furthermore, if r opt (m (k) ) = O(1/Gk), then the optimality gap is at most . Proof. By the analysis in [START_REF] Teofilo | Clustering to minimize the maximum intercluster distance[END_REF], the maximum cluster radius on node v i is at most 2r opt (A i , m (k) i ) at time k, hence the maximum 1 -radius over all clusters is at most 2r opt (m (k) ). For any j ∈ [n], there exists j ∈ ∪ i S i such that

|∇f (α) j -∇f (α) j | = |a T j ∇g(Aα) -a T j ∇g(Aα)| ≤ 2r opt (m (k) )G.
Thus the selected atom is optimal up to a 2r opt (m (k) )G additive error. Then the first claim follows from the analysis in [START_REF] Freund | New Analysis and Results for the Conditional Gradient Method[END_REF]. Similarly, when r opt (m (k) ) = O(1/Gk), the additive error is O(1/k). The second claim then follows from the analysis in [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF].

Algorithm 5 has the potential to improve runtime over exact dFW in various practical situations. For instance, when dealing with heterogenous local nodes, v i can pick m i to be proportional to its computational power so as to reduce the overall waiting time. Another situation where this variant can be useful is when the distribution of atoms across nodes is highly unbalanced. We illustrate the practical benefits of this approximate variant on large-scale Kernel SVM in Section 6.

Illustrative Examples

We give three examples of interesting problems that dFW can solve efficiently: LASSO regression, Kernel SVM and 1 -Adaboost.

LASSO with distributed features The LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] is a linear regression method which aims at approximating a target vector y ∈ R d by a sparse combination of features:

(3.2) min α∈R n y -Aα 2 2 s.t. α 1 ≤ β,
where y i and a ij are the target value and j th feature for training point i, respectively. Our dFW algorithm applies to problem (3.2) in the context of distributed features (each local node holds a subset of the features for all training points), as common in distributed sensor networks. It applies in a similar manner to sparse logistic regression [START_REF] Shevade | A simple and efficient algorithm for gene selection using sparse logistic regression[END_REF] and, perhaps more interestingly, to Group-LASSO [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF]. For the latter, suppose each group of features is located on the same node, for instance when combining features coming from the same source in multi-view learning or when using dummy variables that encode categorical features. In this case, each atom is a group of features and dFW selects a single group at each iteration (see [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF] for the Frank-Wolfe update in this case).

SVM with distributed examples

Let {z i = (x i , y i )} n i=1 be a training sample with x i ∈ R d and y i ∈ {±1}. Let k(x, x ) = ϕ(x), ϕ(x ) be a PSD kernel. The dual problem of L2-loss SVM with kernel k is as follows [START_REF] Tsang | Core Vector Machines: Fast SVM Training on Very Large Data Sets[END_REF][START_REF] Ouyang | Fast Stochastic Frank-Wolfe Algorithms for Nonlinear SVMs[END_REF]:

(3.3) min α∈∆n α T Kα, with K = [ k(z i , z j )] n i,j=1
where k(z i , z j ) = y i y j k(x i , x j ) + y i y j + δij C is the "augmented kernel".

It is easy to see that k(z

i , z j ) = φ(z i ), φ(z j ) with φ(z i ) = [y i ϕ(x i ); y i ; 1 √ C e i ]. Thus K = ΦT Φ where Φ = [ φ(z 1 ), . . . , φ(z n )] T is the atom matrix.
Notice however that atoms may be of very high (or even infinite) dimension since they lie in kernel space. Fortunately, the gradient only depends on K ∈ R n×n , thus we can broadcast the training point z i instead of φ(z i ) (assuming all nodes know the kernel function k). Note that dFW can be seen as a distributed version of Core Vector Machines [START_REF] Tsang | Core Vector Machines: Fast SVM Training on Very Large Data Sets[END_REF], a large-scale SVM algorithm based on Frank-Wolfe, and that it applies in a similar manner to a direct multi-class L2-SVM [START_REF] Asharaf | Multiclass core vector machine[END_REF] and to Structural SVM (see the recent work of [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF]).

Boosting with distributed base classifiers Let H = {h j (•) : X → R, j = 1, . . . , n} be a class of base classifiers to be combined. Given a training sample {(x i , y i )} d i=1 , let A ∈ R d×n where a ij = y i h j (x i ). We consider the following 1 -Adaboost formulation [START_REF] Shen | On the Dual Formulation of Boosting Algorithms[END_REF]:

(3.4) min α∈∆n log 1 d d i=1 exp - (Aα) i T ,
where T > 0 is a tuning parameter. Our algorithm thus applies to the case where the base classifiers are distributed across nodes. Note that the gradient of (3.4) is as follows:

∇f (x) = -w T A, with w = exp(-Aα/T ) d i=1 exp (-(Aα) i /T )
.

The FW update thus corresponds to adding the base classifier that performs best on the training sample weighted by w, where w defines a distribution that favors points that are currently misclassified. This can be done efficiently even for a large (potentially infinite) family of classifiers when a weak learner for H is available. 5 In particular, when H is the class of decision stumps and the features are distributed, each node can call the weak learner on its local features to determine its best local base classifier.

Communication Complexity Analysis

In this section, we focus on communication complexity. We first give the communication cost of dFW depending on the network topology (Section 4.1). Then, we show that this communication complexity is worst-case optimal by proving a communication lower bound for the family of problems of interest (Section 4.2).

Communication Cost of dFW

We explicitly derive the communication cost of dFW for various types of network graphs (depicted in Figure 1). General connected graph If the nodes can agree on a spanning tree, then this reduces to the previous case. We further consider the case when nodes operate without using any information beyond that in their local neighborhood and cannot agree on a spanning tree (this is known as the fully distributed setting [START_REF] Mosk-Aoyama | Fully distributed algorithms for convex optimization problems[END_REF]). In this case, broadcasting can be done through a message-passing procedure similar to [START_REF] Balcan | Distributed k-means and k-median clustering on general communication topologies[END_REF]. The cost of broadcasting a number is B = O(M ), and thus the total communication cost is O (M (N + d)/ ).

v 0 v 1 v 2 v 4 v 3 Star graph v 3 v 4 v 1 v 2 v 5 v 6 v 7 Rooted tree v 1 v 2 v 3 v 4 v 6 v 5

General connected graph

Lower Bound on Communication Cost

In this section, we derive a lower bound on the communication required by any deterministic algorithm to construct an -approximation to problem (1.1) for either the 1 -ball or the simplex constraint. We assume that at the end of the algorithm, at least one of the nodes has all the selected atoms. This is not a restrictive assumption since in many applications, knowledge of the selected atoms is required in order to use the learned model (for instance in kernel SVM).

Our proof is based on designing an optimization problem that meets the desired minimum amount of communication. First, we consider a problem for which any -approximation solution must have O(1/ ) selected atoms. We split the data across two nodes v 1 and v 2 so that these atoms must be almost evenly split across the two nodes. Then, we show that for any fix dataset on one node, there are T different instances of the dataset on the other node, so that in any two such instances, the sets of selected atoms are different. Therefore, for any node to figure out the atom set, it needs O(log T ) bits. The proof is completed by showing log T = Ω(d/ ).

Setup Consider the problem of minimizing f (α) := Aα 2 2 over the unit simplex ∆ d , where A is a d × d orthonormal matrix (i.e., A T A = I). Suppose the first d/2 columns of A (denoted as A 1 ) are on the node v 1 and the other half (denoted as A 2 ) are on the node v 2 . Restrict A to be block diagonal as follows: vectors in A 1 only have non-zeros entries in coordinates {1, . . . , d/2} and vectors in A 2 only have non-zeros entries in coordinates {d/2 + 1, . . . , d}.

For any deterministic algorithm A, let A(A 1 , A 2 ) denote the set of atoms selected given input A 1 and A 2 , and let f A (A 1 , A 2 ) denote the minimum value of f (α) when α ∈ ∆ d and α has only non-zero entries on A(A 1 , A 2 ). We only consider deterministic algorithms that lead to provably good approximations: A satisfies f A (A 1 , A 2 ) < + OPT for any A 1 , A 2 . Furthermore, at the end of the algorithm, at least one of the nodes has all the selected atoms.

In practice, bounded precision representations are used for real values. Study of communication in such case requires algebraic assumptions [START_REF] Abelson | Lower bounds on information transfer in distributed computations[END_REF][START_REF] Tsitsiklis | Communication complexity of convex optimization[END_REF]. For our problem, we allow the columns in A to be orthogonal and of unit length only approximately. More precisely, we say that two vectors v 1 and v 2 are near-orthogonal if |v 1 v 2 | ≤ 4d 2 , and a vector v has near-unit length if |v v -1| ≤ 4d 2 . The notion of subspace is then defined based on near-orthogonality and near-unit length. We make the following assumption about the representation precision of vectors in subspaces. Assumption 4.1. There exists a constant κ > 1 s.t. for any t-dimensional subspace, t ≤ d, the number of different d-dimensional near-unit vectors in the subspace is Θ(κ t-1 ).

Analysis Let ∈ (0, 1/6) and d = 1 6 (for simplicity, suppose d/4 is an integer). We first show that the atoms in any good approximation solution must be almost evenly split across the two nodes. Next, we show that for any fix dataset on one node, there are many different instances of the dataset on the other node, so that any two different instances lead to different selected atoms. Claim 4.2. For any instance of A 1 , there exist T = κ Ω(d/ ) /(d/e) O(d) different instances of A 2 (denoted as {A i 2 } T i=1 ) such that the set of atoms selected from A i 2 are different for all i, i.e., for any 0

≤ i = j ≤ T , A(A 1 , A i 2 ) ∩ A i 2 = A(A 1 , A j 2 ) ∩ A j 2 .
Due to lack of space, the proofs of Claim 4.1 and 4.2 can be found in the extended version of the paper [START_REF] Bellet | A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning[END_REF]. Distinguishing between the T instances requires communication, resulting in our lower bound.

Theorem 4.1. Suppose a deterministic algorithm A satisfies f A (A 1 , A 2 ) < + OPT for any A 1 , A 2 . Under Assumption 4.1, the communication cost of A is lower- bounded by Ω( d log κ -d log d) bits.
Proof. Suppose the algorithm uses less than log T bits. At the end of the algorithm, if node v 1 has the selected atoms, then v 1 must have determined these atoms based on A 1 and less than log T bits. By Claim 4.2, there are

T different instances of A 2 with different A(A 1 , A 2 ) ∩ A 2 .
For at least two of these instances, v 1 will output the same set of atoms, which is contradictory. A similar argument holds if node v 2 has the selected atoms. Therefore, the algorithm uses at least log T bits.

Remarks The same lower bound holds for 1constrained problems by reduction to the simplex case. The analysis also extends to networks with more than two nodes, in which case the diameter of the network is a multiplicative factor in the bound. Details can be found in the extended version of the paper [START_REF] Bellet | A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning[END_REF].

The upper bound given by dFW in Theorem 3.1 matches the lower bound of Theorem 4.1 in its dependency on and d. This leads to the important result that the communication cost of dFW is worst-case optimal in these two quantities.

Related Work

In this section, we review some related work in distributed optimization.

Distributed examples An important body of work considers the distributed minimization of a function f (α) = N i=1 f i (α) where f i is convex and only known to node i. This typically corresponds to the risk minimization setting with distributed training examples, where f i gives the loss for the data points located on node i. These methods are based on subgradient descent (SGD) ( [START_REF] Duchi | Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling[END_REF][START_REF] Dekel | Optimal Distributed Online Prediction Using Mini-Batches[END_REF] and references therein), the Alternating Direction Methods of Multipliers (ADMM) [START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF][START_REF] Wei | Distributed Alternating Direction Method of Multipliers[END_REF] and Stochastic Dual Coordinate Ascent (SDCA) [START_REF] Yang | Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent[END_REF]. Their rate of convergence (and thus their communication cost) for general convex functions is in O(1/ ) or O(1/ 2 ), sometimes with a dependency on n (the total number of data points), which is undesirable for large-scale problems. The above algorithms focus on theoretical guarantees for the optimization error and pay less attention to minimizing the communication overhead. Overall, it is unclear whether any of them is optimal in the communication complexity sense.

Note that for Kernel SVM (Section 3.3), none of the above methods can be applied efficiently, either because they rely on the primal (GD, ADMM) or because they require broadcasting at each iteration a number of data points that is at least the number of nodes in the network (SDCA). In contrast, dFW only needs to broadcast a single point per iteration and still converges in O(1/ ), with no dependency on n. We illustrate its performance on this task in the experiments.

Distributed features In the case of distributed features, ADMM is often the method of choice due to its wide applicability and good practical performance [START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF]. 6Given N nodes, the parameter vector α is partitioned as

α = [α 1 , . . . , α N ] with α i ∈ R ni , where N i=1 n i = n. The matrix A is partitioned likewise as A = [A 1 . . . A N ]
and the optimization problem has the form

min α∈R n g N i=1 A i α i -y + λR(α),
where the loss g is convex, the regularizer R is separable across nodes and convex, and λ > 0. Each node v i iteratively solves a local subproblem and sends its local prediction A i α i to a coordinator node, which then broadcasts the current global prediction N i=1 A i α i . ADMM can be slow to converge to high accuracy, but typically converges to modest accuracy within a few tens of iterations [START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF].

Both ADMM and dFW can deal with LASSO regression with distributed features. When features are dense, dFW and ADMM have a similar iteration cost but dFW is typically slower to converge as it only adds one feature to the solution at each iteration. On the other hand, the case of sparse features creates an interesting tradeoff between the number of iterations and the communication cost per iteration. Indeed, an iteration of dFW becomes much cheaper in communication than an iteration of ADMM since local/global predictions are typically dense. This tradeoff is studied in the experiments.

Experiments

We have shown that dFW enjoys strong theoretical guarantees on the communication cost. In this section, we validate our analysis with a series of experiments on two tasks: LASSO regression with distributed features, and Kernel SVM with distributed examples.

Summary of Main Results

Our main results are as follows:

1. dFW decreases the objective better than two baselines that select atoms locally.

2. When data and/or the solution are sparse, dFW requires less communication than distributed ADMM [START_REF] Boyd | Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[END_REF], a popular competing method for distributed optimization.

3. dFW and its approximate variant perform well in a real-world distributed architecture.

4. dFW is fairly robust to random communication drops and asynchronous updates.

Due to the lack of space, detailed experiments for 1-2 on both synthetic and real data can be found in the extended version of the paper [START_REF] Bellet | A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning[END_REF]. In the following, we describe our results for 3-4.

Large-scale Distributed Experiments

In this section, we apply dFW to kernel SVM (see Section 3.3) in real-world distributed conditions. Note that dFW is computationally very efficient if implemented carefully. In particular, the local gradient of a node v i can be recursively updated using only the kernel values between its n i points and the point received at the previous iteration. Thus the algorithm only needs O(n i ) memory and the computational cost of an iteration is O(n i ). We implemented dFW (without line-search) in C++ with openMPI. Our code is freely available under GNU/GPL license. 7 We experiment with a fully connected network with N ∈ {1, 5, 10, 25, 50} nodes which communicate over a 56.6-gigabit infrastructure. Each node is a single 2.4GHz CPU core of a separate host. We use a speech dataset of 8.7M examples with 120 features and 42 class labels (the task is majority class versus rest). 8 In all experiments, we use the RBF kernel and set its bandwidth based on the averaged distance among examples. The parameter C of SVM is set to 100. Exact dFW We first investigate how dFW scales with the number of nodes. For this experiment, training points are assigned to nodes uniformly at random. Figure 2(a) shows the runtime results for different values of N . We obtain near-linear speedup, showing that synchronization costs are not a significant issue when the local computation is well-balanced across nodes.

Approximate variant When the local costs are misaligned, the exact dFW will suffer from large wait time. As we have seen in Section 3.2, we can use the approximate variant of dFW to balance these costs. To illustrate this, we set N = 10 and assign about 50% of the data to a single node while other nodes share the rest uniformly at random. We use the greedy clustering algorithm on the large node to generate a number of centers approximately equal to the number of atoms on the other nodes, thus balancing local computation. 9 Asynchronous updates Another way to reduce waiting times and synchronization costs is to use asynchronous updates. To simulate this, we randomly drop the communication messages with some probability p > 0. This means that at any given iteration: (i) the selected atom may be suboptimal, and (ii) some nodes may not update their iterate. As a result, the iterates across nodes are not synchronized anymore. Figure 2(c) shows the objective value averaged over all the nodes at each iteration. We can see that dFW is robust to this asynchronous setting and converges properly (albeit a bit slower), even with 40% random communica- 9 For kernel SVM with RBF kernel, the difference between gradient entries of f can be directly bounded by performing clustering in the augmented kernel space, because |∇f (α) i -∇f (α

) j | ≤ 2 maxz k | k(z i , z k ) -k(z j , z k )| ≤ φ(z i ) -φ(z j ) 2 .
tion drops. This suggests that an asynchronous version of dFW could lead to significant speedups in practice. A theoretical analysis of the algorithm in this challenging setting is an exciting direction for future work.

Conclusion

We studied the problem of finding sparse combinations of distributed elements, focusing on minimizing the communication overhead. To this end, we proposed a distributed Frank-Wolfe algorithm with favorable properties. We established a lower-bound to the communication cost for the family of problems we consider, which shows that dFW is optimal in its dependency on the approximation quality . Experiments confirmed the practical utility of the approach.

Theorem 3 . 1 .

 31 Algorithm 3 terminates after O(1/ ) rounds and O ((Bd + N B)/ ) total communication, where B is an upper bound on the cost of broadcasting a real number to all nodes in the network G. At termination, all nodes hold the same α with optimality gap at most and the O(1/ ) atoms corresponding to its nonzero entries.

Algorithm 4

 4 GreedySelection(A, C, ∆k) // add ∆k centers from A to C 1: repeat ∆k times 2:

Figure 1 :

 1 Figure 1: Illustration of network topologies.

Claim 4 . 1 .

 41 Any α with f ( α) < + OPT has more than 3d/4 non-zero entries. Consequently, |A(A p , A q )∩ A p | > d/4 for {p, q} = {1, 2}.

Figure 2 :

 2 Figure 2: Empirical evaluation of our theoretical analysis on distributed Kernel SVM (best seen in color).

Figure 2 (

 2 b) shows that the approximate dFW reduces the runtime dramatically over exact dFW on the unbalanced distribution. As often the case in large-scale datasets, training examples cluster well, so the additive error suffered is negligible in this case.

  send atom and index to other nodes

	5:

Our results also hold for sparsity constraints other than the 1 norm, such as simplex constraints.

Note that the dependency on can be improved to O(n log(1/ )) for strongly convex functions by using away-steps (see e.g.[START_REF] Lacoste-Julien | An Affine Invariant Linear Convergence Analysis for Frank-Wolfe Algorithms[END_REF]). However, when n is large, this improvement might not be desirable since it introduces a dependency on n.

Note that it can be straightforwardly adapted to deal with a simplex constraint based on Algorithm 2.

A weak learner for H returns the base classifier in H that performs best on the sample weighted by w.

Note that to the best of our knowledge, no convergence rate is known for ADMM with distributed features.

https://mloss.org/software/view/593/

The data is from IARPA Babel Program, Cantonese language collection release IARPA-babel101b-v0.4c limited data pack.

Acknowledgments Computation for the work described in this paper was supported by the University of Southern California's Center for High-Performance Computing (http://hpcc.usc.edu). This research is partially supported by NSF grants CCF-0953192 and CCF-1101215, AFOSR grant FA9550-09-1-0538, ONR grant N00014-09-1-0751, a Google Research Award, a Microsoft Research Faculty Fellowship, the Intelligence Advanced Research Projects Activity (IARPA) via Department of Defense U.S. Army Research Laboratory (DoD / ARL) contract number W911NF-12-C-0012, a NSF IIS-1065243, an Alfred. P. Sloan Research Fellowship, DARPA award D11AP00278, and an ARO YIP Award (W911NF-12-1-0241). The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoD/ARL, or the U.S. Government.