sets of simulations as 1 sim, 6 sims, 6 sims + $10^{10}M_{\odot}$ and 18 sims
hereafter. Note that for the 18 sims set, although we divide subhalos
according to their formation time, the formation time is not used as the
starting time of these validation simulations, unlike the pre-evolution part
of our hierarchical framework described in Sec. II.2 and II.3. In the
validation simulations for this appendix, these four sets of simulations are
all started at $t=4$ Gyr, initialized with NFW profiles (parameters determined
by Galacticus merger tree), and ended at $t=9$ Gyr, such that all subhalos to
be matched and compared among these four setups have the same amount of
evolution time. The SIDM model for these simulations is a constant cross
section $\sigma_{m}=6\ \rm cm^{2}/g$, for which the evaporation effect among
subhalos is strong and can highlight any potential subhalo-subhalo
interaction. We expect subhalo-subhalo SIDM interactions to be weaker for the
other models we consider in this paper, since their cross sections at subhalo-
subhalo pairwise velocities (comparable to subhalos’ orbital velocities) are
smaller.

At the beginning of the simulation, 1092 subhalos are initialized in each of
the four sets of simulations. At the end of the simulation, there are around
1060 subhalos left that can be matched among these four. We conduct a subhalo-
by-subhalo comparison, in terms of each subhalo’s virial mass and radial
distance from the host center, as shown in subplot a) and b) of Fig. 12. We
find that there are only a few outliers when comparing the split 6 sims, 6
sims + $10^{10}M_{\odot}$ and 18 sims against 1 sim. Overall we find that
$\sim$94% of subhalos have a mass discrepancy of $<10\%$ and $\sim$96% of
subhalos have a radial distance discrepancy $<10\%$, for all the three
hierarchical sets against 1 sim. The two fractions are $\sim 96\%$ and $\sim
98\%$ for the subhalo mass and radial distribution, respectively, for error
tolerances of 20%. We show the subhalo mass function and radial distribution
in subplot c) and d) of Fig. 12, where again we can see that the overall
distribution of subhalos is not affected by the missing subhalo-subhalo
interaction. Only a few subhalos at the very low mass end, which are very
heavily stripped, show visible scatter among these simulations.

Furthermore, as a comparison between the two split sets, 6 sims and 18 sims,
we can see that their subhalo mass function and radial distribution are nearly
identical, and the subhalo-by-subhalo trackers also show no sign of any
systematic difference. This further hints that the missing subhalo-subhalo
interaction is indeed a minimal effect, since splitting the whole population
of subhalos into 6 or 18 simulations does not seem to matter at all. Any
difference between the 1 sim and 6 sims or 18 sims are more likely to be
caused by resolution and realization difference than the missing subhalo-
subhalo interaction (recall that 6 sims and 18 sims have the same infall-mass
binning so the subhalos are identical at the beginning of the simulation, but
1 sim have different mass resolution and hence also different realization of
subhalos), which is also consistent with the Poisson error shown in Fig. 12.

##  Appendix C Linking a halo’s characteristic velocity for self-interaction
to velocity dispersion

Figure 13: The analytically calculated SIDM heat conductivity of the ‘window
function’ models, as a function of halo’s 1-d velocity dispersion
$\sigma_{v}$. Results are normalized against the heat conductivity of a
constant SIDM cross section $\sigma/m=$200 cm2/g, which corresponds to the
cross section inside the velocity window of the window function models. The
$\sigma_{v}$ range for subhalos’ infall mass from $10^{8}$ to
$10^{10}M_{\odot}$ is shaded with gray color. The $\sigma_{v}$ range
corresponding to velocity window range divided by $C=3.8$ is shown in regions
with forward slash.

We have shown in Sec. IV.3 that from simulation we estimate $3.0<C<4.2$, for
the factor $C$ that characterizes the relation between a (sub)halo’s typical
velocity relevant for self-interaction and maximal 1-d velocity dispersion of
a halo’s CDM initial condition $\langle v_{\rm rel}\rangle=C\sigma_{v}$. In
this appendix we approach the same question analytically with the gravothermal
method.

If we consider the characteristic velocity for heat transfer inside a
(sub)halo as the mean value of the particle-particle relative velocity, a
simple averaging over the Maxwell-Boltzmann distribution gives

$\begin{split}\langle v_{\rm
rel}\rangle&=\int\sqrt{v^{2}_{1}+v^{2}_{2}-v_{1}v_{2}\cos{\theta}}f_{\rm
MB}(v_{1})f_{\rm MB}(v_{2})d^{3}v_{1}d^{3}v_{2}\\\
&=2.26\sigma_{v},\end{split}$ (3)

where $v_{1}$ and $v_{2}$ are the velocities of any two scattering particles,
and the Boltzmann distribution $f_{\rm MB}(v)=(\frac{m}{2\pi
k_{B}T})^{3/2}\exp{(-\frac{mv^{2}}{2k_{B}T})}$ has the temperature $T$
determined by $\sigma_{v}=\sqrt{k_{B}T/m}$. This factor 2.26 from simple
averaging does not agree with the result $3.0<C<4.2$ from simulation. However,
[84] argued that the averaged heat conductivity in the long-mean-free-path
regime

$\langle\kappa_{\rm lmfp}\rangle\propto\frac{\langle
v_{1}v_{2}v^{3}_{12}\sigma(v_{12})\rangle}{\langle
v_{1}v_{2}v^{3}_{12}\rangle},$ (4)

where $v_{12}$ is the relative velocity between particle 1 and 2, would better
characterize the heat transfer for a velocity-dependent SIDM model
$\sigma(v_{12})$. In Fig. 13, we show this numerically integrated
$\langle\kappa_{\rm lmfp}\rangle$ of window2 and window3 models (window1 not
used because it has a less sharp drop in cross section outside the velocity
window, see Fig. 7(a)), normalized by the $\langle\kappa_{\rm lmfp}\rangle$ of
constant $\sigma/m=200$ cm2/g, as a function of the 1-d velocity dispersion
$\sigma_{v}$. Note that the window functions, or in general any functions with
step-like features in $\sigma(v_{12})$ cannot be easily integrated
numerically, since the integral variables are $v_{1}$ and $v_{2}$ instead of
$v_{12}$. Thus we use $[\tanh{(v_{12}-v_{\rm low})}\times\tanh{(v_{\rm
high}-v_{12})}+1]/2$) to represent window functions for this integral, where
$v_{\rm low}$ and $v_{\rm high}$ are the bounds of the velocity window. From
Fig. 13, we find that this calculation of $\langle\kappa_{\rm lmfp}\rangle$
does successfully predict the corresponding subhalo mass/$\sigma_{v}$ bins
that has strong core-collapse, where a window-model that has normalized heat
conductivity $\gtrsim 0.4$ would have noticeable fraction of core-collapse in
that infall-mass bin.

Choosing an intermediate value $C=3.8$ from simulation constrained range
$3.0<C<4.2$, we plot the range of $\sigma_{v}=[v_{\rm low},v_{\rm high}]/C$
corresponding to each window model in Fig. 13. We can see that the estimated
$C=3.8$ from simulation correctly picks out the region of relatively high heat
conductivity $\gtrsim 0.4$. Thus we conclude that both the analytical
gravothermal approach and the estimated range $3.0<C<4.2$ or $C\approx 3.8$
have correct predictions on the core-collapse mass-filtering effect by the
window-type models.

We comment that our finding echoes the conclusion of [83] and [84], that it is
the heat conductivity averaged over the whole (sub)halo that determines the
speed of SIDM evolution, instead of the cross section at the average relative
velocity.

##  Appendix D Animated time evolution of subhalos’ inner mass and virial mass

We compile the time-animated version from $t=4$ Gyr to $t=9$ Gyr of the
$M_{\rm inner}-M_{\rm vir}$ plot in Fig. 3, in this link, and another version
where each subhalo’s inner mass $M_{\rm inner}$ is not defined by a fixed
aperture 200 pc but a fraction 2% of its virial radius at any given time. The
latter with the inner aperture scaling with subhalo mass may better describe
low-mass subhalos that experience dramatic mass loss.

##  Appendix E Supplementary figures

We include variations of some figures in the main text in this section, which
may be more relevant to other use cases:

  * •

Fig. 14 shows the cross section of various SIDM models used, but in the format
of $v_{\rm rel}\times\sigma/m$ instead of the cross section $\sigma/m$ alone.
Since the particle scattering rate/probability is proportional to $v_{\rm
rel}\times\sigma/m$, this version gives more intuitive understanding of the
strength of self-interaction at different velocity scales.

  * •

Fig. 15 shows the validation of our rewinding algorithm, that the calculated
initial position and velocity of randomly selected subhalos are correct, since
their orbits in the simulation can match the input information of infall radii
and velocities.

  * •

Fig. 16 is similar to the 1-point function of substructure lensing in Fig.
9(a), but the y-axis has an additional weight of $\kappa_{\rm sub}^{2}$ that
highlights the large $\kappa_{\rm sub}$ bins, to which substructure lensing is
most sensitive. For example, the strong core-collapse in the
$\\{\sigma_{0}=200,\omega=200\\}$ model (purple line) is featured by a sharp
increase at high $\kappa_{\rm sub}$ bins, which is not visible in Fig. 9(a)
but does show up in Fig. 16 with the additional weight.

  * •

Fig. 17 is similar to Fig. 10(a), but showing the time difference for core-
collapse in field halos and subhalos as an acceleration (positive) or
deceleration (negative) factor to the core-collapse time of field halos.

  * •

Fig. 18 shows the 1-d velocity dispersion profiles of each CDM subhalo at
$t=4$ Gyr. Panel a) shows the velocity dispersion near its maximum value for
each subhalo, and panel b) shows the velocity dispersion in center of the
subhalo.

(a)

(b)

Figure 14: The velocity dependent SIDM models we use in this work, but the
y-axis shown in terms of $v_{\rm rel}\times\frac{\sigma}{m}$ instead of just
the cross section that we show in the main text. Since the pairwise scattering
probability is proportional to $v_{\rm rel}\times\frac{\sigma}{m}$, adding a
weight of $v_{\rm rel}$ to cross section better reflects the actual strength
of self-interaction.  Figure 15:  The orbital distance (top panel) and orbital
velocity (bottom panel) of five randomly selected subhalos. The lines are
results from simulation, and the big dots mark their infall radii and
velocities generated by Galacticus which serve as the input information to
infer subhalos’ motion. The dots lie almost exactly on the simulation lines,
showing that our rewinding calculation of each subhalo’s position and velocity
at an earlier time is accurate — when simulated forward in time, its position
and velocity at the infall time both agree with the input from Galacticus.
Figure 16: The PDF of the substructure lensing $\kappa_{\rm sub}$, which
corresponds to Fig. 9(a) but with additional weight $\kappa_{\rm sub}^{2}$, so
as to highlight the high density end.  Figure 17: The time difference for
core-collapse in field halos and subhalos, shown in the form as a deceleration
(negative) or acceleration (positive) factor by the host field.

(a)

(b)

Figure 18: The typical velocity dispersion of CDM subhalos in each infall-mass
group, at $t=4$ Gyr, before host effects kick in. a) shows the $\sigma_{v}$
near its maximum value for each subhalo. b) shows the $\sigma_{v}$ near the
center of each subhalo. The colored vertical bars mark the $\pm 1\sigma$
scatter of $\sigma_{v}$ in each panel, and those of panel a) are the range of
$\sigma_{v}$ we use in Table 3.

## References

  * Spergel and Steinhardt [2000] D. N. Spergel and P. J. Steinhardt, Observational Evidence for Self-Interacting Cold Dark Matter, Phys. Rev. Lett. 84, 3760 (2000).
  * Battaglieri  _et al._ [2017] M. Battaglieri, A. Belloni, _et al._ , US Cosmic Visions: New Ideas in Dark Matter 2017: Community Report, arXiv e-prints , arXiv:1707.04591 (2017), arXiv:1707.04591 [hep-ph] .
  * Tulin and Yu [2018] S. Tulin and H.-B. Yu, Dark matter self-interactions and small scale structure, Phys. Rept. 730, 1 (2018).
  * Buckley and Peter [2018] M. R. Buckley and A. H. G. Peter, Gravitational probes of dark matter physics, Phys. Rept. 761, 1 (2018), arXiv:1712.06615 [astro-ph.CO] .
  * Adhikari  _et al._ [2022] S. Adhikari, A. Banerjee, K. K. Boddy, F.-Y. Cyr-Racine, H. Desmond, C. Dvorkin, B. Jain, F. Kahlhoefer, M. Kaplinghat, A. Nierenberg, A. H. G. Peter, A. Robertson, J. Sakstein, and J. Zavala, Astrophysical Tests of Dark Matter Self-Interactions, arXiv e-prints , arXiv:2207.10638 (2022), arXiv:2207.10638 [astro-ph.CO] .
  * Kaplinghat  _et al._ [2016] M. Kaplinghat, S. Tulin, and H.-B. Yu, Dark Matter Halos as Particle Colliders: Unified Solution to Small-Scale Structure Puzzles from Dwarfs to Clusters, Phys. Rev. Lett. 116, 041302 (2016).
  * Kamada  _et al._ [2017] A. Kamada, M. Kaplinghat, A. B. Pace, and H.-B. Yu, Self-Interacting Dark Matter Can Explain Diverse Galactic Rotation Curves, Phys. Rev. Lett. 119, 111102 (2017), arXiv:1611.02716 [astro-ph.GA] .
  * Sameie  _et al._ [2020] O. Sameie, H.-B. Yu, L. V. Sales, M. Vogelsberger, and J. Zavala, Self-Interacting Dark Matter Subhalos in the Milky Way’s Tides, Phys. Rev. Lett. 124, 141102 (2020), arXiv:1904.07872 [astro-ph.GA] .
  * Kaplinghat  _et al._ [2020] M. Kaplinghat, T. Ren, and H.-B. Yu, Dark matter cores and cusps in spiral galaxies and their explanations, JCAP 2020 (6), 027, arXiv:1911.00544 [astro-ph.GA] .
  * Correa [2021] C. A. Correa, Constraining velocity-dependent self-interacting dark matter with the Milky Way’s dwarf spheroidal galaxies, Mon. Not. Roy. Astron. Soc. 503, 920 (2021), arXiv:2007.02958 [astro-ph.GA] .
  * Zeng  _et al._ [2022] Z. C. Zeng, A. H. G. Peter, X. Du, A. Benson, S. Kim, F. Jiang, F.-Y. Cyr-Racine, and M. Vogelsberger, Core-collapse, evaporation, and tidal effects: the life story of a self-interacting dark matter subhalo, Mon. Not. Roy. Astron. Soc. 513, 4845 (2022), arXiv:2110.00259 [astro-ph.CO] .
  * Correa  _et al._ [2022] C. A. Correa, M. Schaller, S. Ploeckinger, N. Anau Montel, C. Weniger, and S. Ando, TangoSIDM: tantalizing models of self-interacting dark matter, Mon. Not. Roy. Astron. Soc. 517, 3045 (2022), arXiv:2206.11298 [astro-ph.GA] .
  * Bhattacharyya  _et al._ [2022] S. Bhattacharyya, S. Adhikari, A. Banerjee, S. More, A. Kumar, E. O. Nadler, and S. Chatterjee, The Signatures of Self-interacting Dark Matter and Subhalo Disruption on Cluster Substructure, Astrophys. J. 932, 30 (2022).
  * Nadler  _et al._ [2023a] E. O. Nadler, D. Yang, and H.-B. Yu, An SIDM Solution to the Extreme Diversity of Low-mass Halo Properties, arXiv e-prints , arXiv:2306.01830 (2023a), arXiv:2306.01830 [astro-ph.GA] .
  * Silverman  _et al._ [2023] M. Silverman, J. S. Bullock, M. Kaplinghat, V. H. Robles, and M. Valli, Motivations for a large self-interacting dark matter cross-section from Milky Way satellites, Mon. Not. Roy. Astron. Soc. 518, 2418 (2023).
  * Yang  _et al._ [2023a] D. Yang, E. O. Nadler, and H.-B. Yu, Strong Dark Matter Self-interactions Diversify Halo Populations within and surrounding the Milky Way, Astrophys. J. 949, 67 (2023a), arXiv:2211.13768 [astro-ph.GA] .
  * Kuzio de Naray and McGaugh [2014] R. Kuzio de Naray and S. S. McGaugh, The Inner Dynamical Mass across Galaxy Morphology: A Weak Scaling with Total Stellar Mass, Astrophys. J. Lett. 782, L12 (2014), arXiv:1401.3002 [astro-ph.GA] .
  * Oman  _et al._ [2015] K. A. Oman, J. F. Navarro, A. Fattahi, C. S. Frenk, T. Sawala, S. D. M. White, R. Bower, R. A. Crain, M. Furlong, M. Schaller, J. Schaye, and T. Theuns, The unexpected diversity of dwarf galaxy rotation curves, Mon. Not. Roy. Astron. Soc. 452, 3650 (2015), arXiv:1504.01437 [astro-ph.GA] .
  * Errani  _et al._ [2018] R. Errani, J. Peñarrubia, and M. G. Walker, Systematics in virial mass estimators for pressure-supported systems, Mon. Not. Roy. Astron. Soc. 481, 5073 (2018), arXiv:1805.00484 [astro-ph.GA] .
  * Read  _et al._ [2019] J. I. Read, M. G. Walker, and P. Steger, Dark matter heats up in dwarf galaxies, Mon. Not. Roy. Astron. Soc. 484, 1401 (2019), arXiv:1808.06634 [astro-ph.GA] .
  * Relatores  _et al._ [2019] N. C. Relatores, A. B. Newman, J. D. Simon, R. S. Ellis, P. Truong, L. Blitz, A. Bolatto, C. Martin, M. Matuszewski, P. Morrissey, and J. D. Neill, The Dark Matter Distributions in Low-mass Disk Galaxies. II. The Inner Density Profiles, Astrophys. J. 887, 94 (2019), arXiv:1911.05836 [astro-ph.GA] .
  * Santos-Santos  _et al._ [2020] I. M. E. Santos-Santos, J. F. Navarro, A. Robertson, A. Benítez-Llambay, K. A. Oman, M. R. Lovell, C. S. Frenk, A. D. Ludlow, A. Fattahi, and A. Ritz, Baryonic clues to the puzzling diversity of dwarf galaxy rotation curves, Mon. Not. Roy. Astron. Soc. 495, 58 (2020), arXiv:1911.09116 [astro-ph.GA] .
  * Hayashi  _et al._ [2020] K. Hayashi, M. Chiba, and T. Ishiyama, Diversity of Dark Matter Density Profiles in the Galactic Dwarf Spheroidal Satellites, Astrophys. J. 904, 45 (2020), arXiv:2007.13780 [astro-ph.GA] .
  * Li  _et al._ [2020] P. Li, F. Lelli, S. McGaugh, and J. Schombert, A Comprehensive Catalog of Dark Matter Halo Models for SPARC Galaxies, The Astrophysical Journal Supplement Series 247, 31 (2020), arXiv:2001.10538 [astro-ph.GA] .
  * Kochanek and White [2000] C. S. Kochanek and M. White, A Quantitative Study of Interacting Dark Matter in Halos, Astrophys. J. 543, 514 (2000), arXiv:astro-ph/0003483 [astro-ph] .
  * Davé  _et al._ [2001] R. Davé, D. N. Spergel, P. J. Steinhardt, and B. D. Wandelt, Halo Properties in Cosmological Simulations of Self-interacting Cold Dark Matter, Astrophys. J. 547, 574 (2001), arXiv:astro-ph/0006218 [astro-ph] .
  * Colín  _et al._ [2002] P. Colín, V. Avila-Reese, O. Valenzuela, and C. Firmani, Structure and Subhalo Population of Halos in a Self-interacting Dark Matter Cosmology, Astrophys. J. 581, 777 (2002), arXiv:astro-ph/0205322 [astro-ph] .
  * Balberg  _et al._ [2002] S. Balberg, S. L. Shapiro, and S. Inagaki, Self-Interacting Dark Matter Halos and the Gravothermal Catastrophe, Astrophys. J. 568, 475 (2002), arXiv:astro-ph/0110561 [astro-ph] .
  * Balberg and Shapiro [2002] S. Balberg and S. L. Shapiro, Gravothermal Collapse of Self-Interacting Dark Matter Halos and the Origin of Massive Black Holes, Phys. Rev. Lett. 88, 101301 (2002), arXiv:astro-ph/0111176 [astro-ph] .
  * Pollack  _et al._ [2015] J. Pollack, D. N. Spergel, and P. J. Steinhardt, Supermassive Black Holes from Ultra-strongly Self-interacting Dark Matter, Astrophys. J. 804, 131 (2015), arXiv:1501.00017 [astro-ph.CO] .
  * Shapiro [2018] S. L. Shapiro, Star clusters, self-interacting dark matter halos, and black hole cusps: The fluid conduction model and its extension to general relativity, Phys. Rev. D 98, 023021 (2018), arXiv:1809.02618 [astro-ph.HE] .
  * Feng  _et al._ [2021] W.-X. Feng, H.-B. Yu, and Y.-M. Zhong, Seeding Supermassive Black Holes with Self-interacting Dark Matter: A Unified Scenario with Baryons, Astrophys. J. Lett. 914, L26 (2021), arXiv:2010.15132 [astro-ph.CO] .
  * Meshveliani  _et al._ [2023] T. Meshveliani, J. Zavala, and M. R. Lovell, Gravothermal collapse of self-interacting dark matter halos as the origin of intermediate mass black holes in Milky Way satellites, Phys. Rev. D 107, 083010 (2023).
  * Rocha  _et al._ [2013] M. Rocha, A. H. G. Peter, J. S. Bullock, M. Kaplinghat, S. Garrison-Kimmel, J. Oñorbe, and L. A. Moustakas, Cosmological simulations with self-interacting dark matter - I. Constant-density cores and substructure, Mon. Not. Roy. Astron. Soc. 430, 81 (2013), arXiv:1208.3025 [astro-ph.CO] .
  * Elbert  _et al._ [2018] O. D. Elbert, J. S. Bullock, M. Kaplinghat, S. Garrison-Kimmel, A. S. Graus, and M. Rocha, A Testable Conspiracy: Simulating Baryonic Effects on Self-interacting Dark Matter Halos, Astrophys. J. 853, 109 (2018).
  * Andrade  _et al._ [2022] K. E. Andrade, J. Fuson, S. Gad-Nasr, D. Kong, Q. Minor, M. G. Roberts, and M. Kaplinghat, A stringent upper limit on dark matter self-interaction cross-section from cluster strong lensing, Mon. Not. Roy. Astron. Soc. 510, 54 (2022).
  * Peter  _et al._ [2013] A. H. G. Peter, M. Rocha, J. S. Bullock, and M. Kaplinghat, Cosmological simulations with self-interacting dark matter - II. Halo shapes versus observations, Mon. Not. Roy. Astron. Soc. 430, 105 (2013), arXiv:1208.3026 [astro-ph.CO] .
  * Robertson  _et al._ [2019] A. Robertson, D. Harvey, R. Massey, V. Eke, I. G. McCarthy, M. Jauzac, B. Li, and J. Schaye, Observable tests of self-interacting dark matter in galaxy clusters: cosmological simulations with SIDM and baryons, Mon. Not. Roy. Astron. Soc. 488, 3646 (2019).
  * McDaniel  _et al._ [2021] A. McDaniel, T. Jeltema, and S. Profumo, X-ray shapes of elliptical galaxies and implications for self-interacting dark matter, JCAP 2021 (5), 020.
  * Shen  _et al._ [2022] X. Shen, T. Brinckmann, D. Rapetti, M. Vogelsberger, A. Mantz, J. Zavala, and S. W. Allen, X-ray morphology of cluster-mass haloes in self-interacting dark matter, Mon. Not. Roy. Astron. Soc. 516, 1302 (2022).
  * Despali  _et al._ [2022a] G. Despali, L. G. Walls, S. Vegetti, M. Sparre, M. Vogelsberger, and J. Zavala, Constraining SIDM with halo shapes: Revisited predictions from realistic simulations of early-type galaxies, Mon. Not. Roy. Astron. Soc. 516, 4543 (2022a).
  * Robertson  _et al._ [2023] A. Robertson, E. Huff, and K. Markovič, Why weak lensing cluster shapes are insensitive to self-interacting dark matter, Mon. Not. Roy. Astron. Soc. 521, 3172 (2023).
  * Randall  _et al._ [2008] S. W. Randall, M. Markevitch, D. Clowe, A. H. Gonzalez, and M. Bradač, Constraints on the Self-Interaction Cross Section of Dark Matter from Numerical Simulations of the Merging Galaxy Cluster 1E 0657-56, Astrophys. J. 679, 1173 (2008), arXiv:0704.0261 [astro-ph] .
  * Kim  _et al._ [2017] S. Y. Kim, A. H. G. Peter, and D. Wittman, In the wake of dark giants: new signatures of dark matter self-interactions in equal-mass mergers of galaxy clusters, Mon. Not. Roy. Astron. Soc. 469, 1414 (2017), arXiv:1608.08630 [astro-ph.CO] .
  * Robertson  _et al._ [2017] A. Robertson, R. Massey, and V. Eke, What does the Bullet Cluster tell us about self-interacting dark matter?, Mon. Not. Roy. Astron. Soc. 465, 569 (2017).
  * Cross  _et al._ [2023] D. Cross, G. Thoron, T. Jeltema, A. Swart, D. Hollowood, S. Adhikari, S. Bocquet, O. Eiger, S. Everett, and J. Jobel, Examining the Self-Interaction of Dark Matter through Central Cluster Galaxy Offsets, arXiv e-prints , arXiv:2304.10128 (2023), arXiv:2304.10128 [astro-ph.CO] .
  * Fischer  _et al._ [2023] M. S. Fischer, N.-H. Durke, K. Hollingshausen, C. Hammer, M. Brüggen, and K. Dolag, The role of baryons in self-interacting dark matter mergers, Mon. Not. Roy. Astron. Soc. 10.1093/mnras/stad1786 (2023).
  * Koda and Shapiro [2011] J. Koda and P. R. Shapiro, Gravothermal collapse of isolated self-interacting dark matter haloes: N-body simulation versus the fluid model, Mon. Not. Roy. Astron. Soc. 415, 1125 (2011), arXiv:1101.3097 [astro-ph.CO] .
  * Essig  _et al._ [2019] R. Essig, S. D. McDermott, H.-B. Yu, and Y.-M. Zhong, Constraining Dissipative Dark Matter Self-Interactions, Phys. Rev. Lett. 123, 121102 (2019), arXiv:1809.01144 [hep-ph] .
  * Valli and Yu [2018] M. Valli and H.-B. Yu, Dark matter self-interactions from the internal dynamics of dwarf spheroidals, Nature Astronomy 2, 907 (2018), arXiv:1711.03502 [astro-ph.GA] .
  * Kaplinghat  _et al._ [2019] M. Kaplinghat, M. Valli, and H.-B. Yu, Too big to fail in light of Gaia, Mon. Not. Roy. Astron. Soc. 490, 231 (2019), arXiv:1904.04939 [astro-ph.GA] .
  * Vogelsberger  _et al._ [2012] M. Vogelsberger, J. Zavala, and A. Loeb, Subhaloes in self-interacting galactic dark matter haloes, Mon. Not. Roy. Astron. Soc. 423, 3740 (2012), arXiv:1201.5892 [astro-ph.CO] .
  * Banerjee  _et al._ [2020] A. Banerjee, S. Adhikari, N. Dalal, S. More, and A. Kravtsov, Signatures of self-interacting dark matter on cluster density profile and subhalo distributions, JCAP 2020 (2), 024, arXiv:1906.12026 [astro-ph.CO] .
  * Colquhoun  _et al._ [2021] B. Colquhoun, S. Heeba, F. Kahlhoefer, L. Sagunski, and S. Tulin, Semiclassical regime for dark matter self-interactions, Phys. Rev. D 103, 035006 (2021), arXiv:2011.04679 [hep-ph] .
  * Turner  _et al._ [2021] H. C. Turner, M. R. Lovell, J. Zavala, and M. Vogelsberger, The onset of gravothermal core collapse in velocity-dependent self-interacting dark matter subhaloes, Mon. Not. Roy. Astron. Soc. 505, 5327 (2021).
  * Shah and Adhikari [2023] N. Shah and S. Adhikari, The abundance of core–collapsed subhalos in SIDM: insights from structure formation in $\Lambda$CDM, arXiv e-prints , arXiv:2308.16342 (2023), arXiv:2308.16342 [astro-ph.CO] .
  * Dalal and Kochanek [2002] N. Dalal and C. S. Kochanek, Direct Detection of Cold Dark Matter Substructure, Astrophys. J. 572, 25 (2002), arXiv:astro-ph/0111456 [astro-ph] .
  * Metcalf [2005a] R. B. Metcalf, The Importance of Intergalactic Structure to Gravitationally Lensed Quasars, Astrophys. J. 629, 673 (2005a), arXiv:astro-ph/0412538 [astro-ph] .
  * Metcalf [2005b] R. B. Metcalf, Testing $\Lambda$CDM with Gravitational Lensing Constraints on Small-Scale Structure, Astrophys. J. 622, 72 (2005b), arXiv:astro-ph/0407298 [astro-ph] .
  * Xu  _et al._ [2009] D. D. Xu, S. Mao, J. Wang, V. Springel, L. Gao, S. D. M. White, C. S. Frenk, A. Jenkins, G. Li, and J. F. Navarro, Effects of dark matter substructures on gravitational lensing: results from the Aquarius simulations, Mon. Not. Roy. Astron. Soc. 398, 1235 (2009), arXiv:0903.4559 [astro-ph.CO] .
  * Birrer  _et al._ [2017] S. Birrer, A. Amara, and A. Refregier, Lensing substructure quantification in RXJ1131-1231: a 2 keV lower bound on dark matter thermal relic mass, JCAP 2017 (5), 037, arXiv:1702.00009 [astro-ph.CO] .
  * Gilman  _et al._ [2018] D. Gilman, S. Birrer, T. Treu, C. R. Keeton, and A. Nierenberg, Probing the nature of dark matter by forward modelling flux ratios in strong gravitational lenses, Mon. Not. Roy. Astron. Soc. 481, 819 (2018), arXiv:1712.04945 [astro-ph.CO] .
  * Gilman  _et al._ [2020] D. Gilman, S. Birrer, A. Nierenberg, T. Treu, X. Du, and A. Benson, Warm dark matter chills out: constraints on the halo mass function and the free-streaming length of dark matter with eight quadruple-image strong gravitational lenses, Mon. Not. Roy. Astron. Soc. 491, 6077 (2020), arXiv:1908.06983 [astro-ph.CO] .
  * Hsueh  _et al._ [2020] J. W. Hsueh, W. Enzi, S. Vegetti, M. W. Auger, C. D. Fassnacht, G. Despali, L. V. E. Koopmans, and J. P. McKean, SHARP - VII. New constraints on the dark matter free-streaming properties and substructure abundance from gravitationally lensed quasars, Mon. Not. Roy. Astron. Soc. 492, 3047 (2020), arXiv:1905.04182 [astro-ph.CO] .
  * Nierenberg  _et al._ [2023] A. M. Nierenberg, R. E. Keeley, D. Sluse, D. Gilman, S. Birrer, T. Treu, K. N. Abazajian, T. Anguita, A. J. Benson, V. N. Bennert, S. G. Djorgovski, X. Du, C. D. Fassnacht, S. F. Hoenig, A. Kusenko, C. Lemon, M. Malkan, V. Motta, L. A. Moustakas, D. Stern, and R. H. Wechsler, JWST lensed quasar dark matter survey I: Description and First Results, arXiv e-prints , arXiv:2309.10101 (2023), arXiv:2309.10101 [astro-ph.CO] .
  * Koopmans [2005] L. V. E. Koopmans, Gravitational imaging of cold dark matter substructures, Mon. Not. Roy. Astron. Soc. 363, 1136 (2005), arXiv:astro-ph/0501324 [astro-ph] .
  * Vegetti  _et al._ [2010] S. Vegetti, L. V. E. Koopmans, A. Bolton, T. Treu, and R. Gavazzi, Detection of a dark substructure through gravitational imaging, Mon. Not. Roy. Astron. Soc. 408, 1969 (2010), arXiv:0910.0760 [astro-ph.CO] .
  * Meneghetti  _et al._ [2020] M. Meneghetti, G. Davoli, P. Bergamini, P. Rosati, P. Natarajan, C. Giocoli, G. B. Caminha, R. B. Metcalf, E. Rasia, S. Borgani, F. Calura, C. Grillo, A. Mercurio, and E. Vanzella, An excess of small-scale gravitational lenses observed in galaxy clusters, Science 369, 1347 (2020), arXiv:2009.04471 [astro-ph.GA] .
  * Minor  _et al._ [2021a] Q. Minor, M. Kaplinghat, T. H. Chan, and E. Simon, Inferring the concentration of dark matter subhaloes perturbing strongly lensed images, Mon. Not. Roy. Astron. Soc. 507, 1202 (2021a), arXiv:2011.10629 [astro-ph.CO] .
  * Minor  _et al._ [2021b] Q. Minor, S. Gad-Nasr, M. Kaplinghat, and S. Vegetti, An unexpected high concentration for the dark substructure in the gravitational lens SDSSJ0946+1006, Mon. Not. Roy. Astron. Soc. 507, 1662 (2021b), arXiv:2011.10627 [astro-ph.GA] .
  * Despali  _et al._ [2022b] G. Despali, S. Vegetti, S. D. M. White, D. M. Powell, H. R. Stacey, C. D. Fassnacht, F. Rizzo, and W. Enzi, Detecting low-mass haloes with strong gravitational lensing I: the effect of data quality and lensing configuration, Mon. Not. Roy. Astron. Soc. 510, 2480 (2022b), arXiv:2111.08718 [astro-ph.GA] .
  * Ballard  _et al._ [2023] D. J. Ballard, W. J. R. Enzi, T. E. Collett, H. C. Turner, and R. J. Smith, Gravitational imaging through a triple source plane lens: revisiting the $\Lambda$CDM-defying dark subhalo in SDSSJ0946+1006, arXiv e-prints , arXiv:2309.04535 (2023), arXiv:2309.04535 [astro-ph.CO] .
  * Yang and Yu [2021] D. Yang and H.-B. Yu, Self-interacting dark matter and small-scale gravitational lenses in galaxy clusters, Phys. Rev. D 104, 103031 (2021), arXiv:2102.02375 [astro-ph.GA] .
  * Gilman  _et al._ [2021] D. Gilman, J. Bovy, T. Treu, A. Nierenberg, S. Birrer, A. Benson, and O. Sameie, Strong lensing signatures of self-interacting dark matter in low-mass haloes, Mon. Not. Roy. Astron. Soc. 507, 2432 (2021), arXiv:2105.05259 [astro-ph.CO] .
  * Gilman  _et al._ [2022] D. Gilman, Y.-M. Zhong, and J. Bovy, Constraining resonant dark matter self-interactions with strong gravitational lenses, arXiv e-prints , arXiv:2207.13111 (2022), arXiv:2207.13111 [astro-ph.CO] .
  * Dhanasingham  _et al._ [2023a] B. Dhanasingham, F.-Y. Cyr-Racine, C. Mace, A. H. G. Peter, and A. Benson, Anisotropic strong lensing as a probe of dark matter self-interactions, arXiv e-prints , arXiv:2306.10109 (2023a), arXiv:2306.10109 [astro-ph.CO] .
  * Peñarrubia  _et al._ [2010] J. Peñarrubia, A. J. Benson, M. G. Walker, G. Gilmore, A. W. McConnachie, and L. Mayer, The impact of dark matter cusps and cores on the satellite galaxy population around spiral galaxies, Mon. Not. Roy. Astron. Soc. 406, 1290 (2010), arXiv:1002.3376 [astro-ph.GA] .
  * Errani  _et al._ [2023] R. Errani, J. F. Navarro, J. Peñarrubia, B. Famaey, and R. Ibata, Dark matter halo cores and the tidal survival of Milky Way satellites, Mon. Not. Roy. Astron. Soc. 519, 384 (2023), arXiv:2210.01131 [astro-ph.GA] .
  * Kummer  _et al._ [2018] J. Kummer, F. Kahlhoefer, and K. Schmidt-Hoberg, Effective description of dark matter self-interactions in small dark matter haloes, Mon. Not. Roy. Astron. Soc. 474, 388 (2018), arXiv:1706.04794 [astro-ph.CO] .
  * Vogelsberger  _et al._ [2019] M. Vogelsberger, J. Zavala, K. Schutz, and T. R. Slatyer, Evaporating the Milky Way halo and its satellites with inelastic self-interacting dark matter, Mon. Not. Roy. Astron. Soc. 484, 5437 (2019), arXiv:1805.03203 [astro-ph.GA] .
  * Slone  _et al._ [2023] O. Slone, F. Jiang, M. Lisanti, and M. Kaplinghat, Orbital evolution of satellite galaxies in self-interacting dark matter models, Phys. Rev. D 107, 043014 (2023), arXiv:2108.03243 [astro-ph.CO] .
  * Nadler  _et al._ [2020a] E. O. Nadler, A. Banerjee, S. Adhikari, Y.-Y. Mao, and R. H. Wechsler, Signatures of Velocity-dependent Dark Matter Self-interactions in Milky Way-mass Halos, Astrophys. J. 896, 112 (2020a), arXiv:2001.08754 [astro-ph.CO] .
  * Outmezguine  _et al._ [2022] N. J. Outmezguine, K. K. Boddy, S. Gad-Nasr, M. Kaplinghat, and L. Sagunski, Universal gravothermal evolution of isolated self-interacting dark matter halos for velocity-dependent cross sections, arXiv e-prints , arXiv:2204.06568 (2022), arXiv:2204.06568 [astro-ph.GA] .
  * Yang  _et al._ [2023b] S. Yang, X. Du, Z. C. Zeng, A. Benson, F. Jiang, E. O. Nadler, and A. H. G. Peter, Gravothermal Solutions of SIDM Halos: Mapping from Constant to Velocity-dependent Cross Section, Astrophys. J. 946, 47 (2023b), arXiv:2205.02957 [astro-ph.CO] .
  * Robertson  _et al._ [2021] A. Robertson, R. Massey, V. Eke, J. Schaye, and T. Theuns, The surprising accuracy of isothermal Jeans modelling of self-interacting dark matter density profiles, Mon. Not. Roy. Astron. Soc. 501, 4610 (2021), arXiv:2009.07844 [astro-ph.CO] .
  * Jiang  _et al._ [2022] F. Jiang, A. Benson, P. F. Hopkins, O. Slone, M. Lisanti, M. Kaplinghat, A. H. G. Peter, Z. Carton Zeng, X. Du, S. Yang, and X. Shen, A semi-analytic study of self-interacting dark-matter haloes with baryons, arXiv e-prints , arXiv:2206.12425 (2022), arXiv:2206.12425 [astro-ph.CO] .
  * Shirasaki  _et al._ [2022] M. Shirasaki, T. Okamoto, and S. Ando, Modelling self-interacting dark matter substructures - I. Calibration with N-body simulations of a Milky-Way-sized halo and its satellite, Mon. Not. Roy. Astron. Soc. 516, 4594 (2022), arXiv:2205.09920 [astro-ph.CO] .
  * Robles  _et al._ [2019] V. H. Robles, T. Kelley, J. S. Bullock, and M. Kaplinghat, The Milky Way’s halo and subhaloes in self-interacting dark matter, Mon. Not. Roy. Astron. Soc. 490, 2117 (2019), arXiv:1903.01469 [astro-ph.GA] .
  * Vegetti  _et al._ [2023] S. Vegetti, S. Birrer, G. Despali, C. D. Fassnacht, D. Gilman, Y. Hezaveh, L. Perreault Levasseur, J. P. McKean, D. M. Powell, C. M. O’Riordan, and G. Vernardos, Strong gravitational lensing as a probe of dark matter, arXiv e-prints , arXiv:2306.11781 (2023), arXiv:2306.11781 [astro-ph.CO] .
  * van den Bosch and Ogiya [2018] F. C. van den Bosch and G. Ogiya, Dark matter substructure in numerical simulations: a tale of discreteness noise, runaway instabilities, and artificial disruption, Mon. Not. Roy. Astron. Soc. 475, 4066 (2018), arXiv:1801.05427 [astro-ph.GA] .
  * Nadler  _et al._ [2023b] E. O. Nadler, P. Mansfield, Y. Wang, X. Du, S. Adhikari, A. Banerjee, A. Benson, E. Darragh-Ford, Y.-Y. Mao, S. Wagner-Carena, R. H. Wechsler, and H.-Y. Wu, Symphony: Cosmological Zoom-in Simulation Suites over Four Decades of Host Halo Mass, Astrophys. J. 945, 159 (2023b), arXiv:2209.02675 [astro-ph.CO] .
  * Springel [2010] V. Springel, E pur si muove:galilean-invariant cosmological hydrodynamical simulations on a moving mesh, Monthly Notices of the Royal Astronomical Society 401, 791–851 (2010).
  * Vogelsberger  _et al._ [2014] M. Vogelsberger, J. Zavala, C. Simpson, and A. Jenkins, Dwarf galaxies in cdm and sidm with baryons: observational probes of the nature of dark matter, Monthly Notices of the Royal Astronomical Society 444, 3684–3698 (2014).
  * Benson [2012] A. J. Benson, Galacticus: A Semi-Analytic Model of Galaxy Formation, New Astron. 17, 175 (2012), arXiv:1008.1786 [astro-ph.CO] .
  * Parkinson  _et al._ [2008] H. Parkinson, S. Cole, and J. Helly, Generating Dark Matter Halo Merger Trees, Mon. Not. Roy. Astron. Soc. 383, 557 (2008), arXiv:0708.1382 [astro-ph] .
  * Robertson  _et al._ [2020] A. Robertson, G. P. Smith, R. Massey, V. Eke, M. Jauzac, M. Bianconi, and D. Ryczanowski, What does strong gravitational lensing? The mass and redshift distribution of high-magnification lenses, Mon. Not. Roy. Astron. Soc. 495, 3727 (2020), arXiv:2002.01479 [astro-ph.CO] .
  * Navarro  _et al._ [1996] J. F. Navarro, C. S. Frenk, and S. D. M. White, The Structure of cold dark matter halos, Astrophys. J. 462, 563 (1996), arXiv:astro-ph/9508025 .
  * Percival [2005] W. J. Percival, Cosmological structure formation in a homogeneous dark energy background, Astron.Astrophys. 443, 819 (2005), arXiv:astro-ph/0508156 [astro-ph] .
  * Ludlow  _et al._ [2016] A. D. Ludlow, S. Bose, R. E. Angulo, L. Wang, W. A. Hellwing, J. F. Navarro, S. Cole, and C. S. Frenk, The Mass-Concentration-Redshift Relation of Cold and Warm Dark Matter Halos, Mon. Not. Roy. Astron. Soc. 460, 1214 (2016), arXiv:1601.02624 [astro-ph.CO] .
  * Benson  _et al._ [2019] A. J. Benson, A. Ludlow, and S. Cole, Halo concentrations from extended Press-Schechter merger histories, Mon. Not. Roy. Astron. Soc. 485, 5010 (2019), arXiv:1812.06026 [astro-ph.GA] .
  * Jiang  _et al._ [2015] L. Jiang, S. Cole, T. Sawala, and C. S. Frenk, Orbital parameters of infalling satellite haloes in the hierarchical $\Lambda$CDM model, Mon. Not. Roy. Astron. Soc. 448, 1674 (2015), arXiv:1409.1179 [astro-ph.CO] .
  * Akrami  _et al._ [2020] Y. Akrami _et al._ (Planck), Planck 2018 results. X. Constraints on inflation, Astron. Astrophys. 641, A10 (2020), arXiv:1807.06211 [astro-ph.CO] .
  * Eisenstein and Hu [1999] D. J. Eisenstein and W. Hu, Power spectra for cold dark matter and its variants, Astrophys. J. 511, 5 (1999), arXiv:astro-ph/9710252 [astro-ph] .
  * Diemer and Kravtsov [2014] B. Diemer and A. V. Kravtsov, Dependence of the outer density profiles of halos on their mass accretion rate, Astrophys. J. 789, 1 (2014), arXiv:1401.1216 [astro-ph.CO] .
  * More  _et al._ [2015] S. More, B. Diemer, and A. Kravtsov, The splashback radius as a physical halo boundary and the growth of halo mass, Astrophys. J. 810, 36 (2015), arXiv:1504.05591 [astro-ph.CO] .
  * Yang  _et al._ [2023c] S. Yang, F. Jiang, A. Benson, Y.-M. Zhong, C. Mace, X. Du, Z. Carton Zeng, and A. H. G. Peter, Constraining SIDM cross section models with a joint analysis of galaxies and clusters, arXiv e-prints , arXiv:2305.05067 (2023c), arXiv:2305.05067 [astro-ph.CO] .
  * Zhong  _et al._ [2023] Y.-M. Zhong, D. Yang, and H.-B. Yu, The impact of baryonic potentials on the gravothermal evolution of self-interacting dark matter haloes, arXiv e-prints , arXiv:2306.08028 (2023), arXiv:2306.08028 [astro-ph.CO] .
  * Han  _et al._ [2023] C. Han, K.-P. Xie, J. M. Yang, and M. Zhang, Self-interacting dark matter implied by nano-Hertz gravitational waves, arXiv e-prints , arXiv:2306.16966 (2023), arXiv:2306.16966 [hep-ph] .
  * Knollmann and Knebe [2009] S. R. Knollmann and A. Knebe, AHF: Amiga’s Halo Finder, The Astrophysical Journal Supplement Series 182, 608 (2009), arXiv:0904.3662 [astro-ph.CO] .
  * Metcalf and Petkova [2014] R. B. Metcalf and M. Petkova, GLAMER - I. A code for gravitational lensing simulations with adaptive mesh refinement, Mon. Not. Roy. Astron. Soc. 445, 1942 (2014), arXiv:1312.1128 [astro-ph.CO] .
  * Petkova  _et al._ [2014] M. Petkova, R. B. Metcalf, and C. Giocoli, GLAMER - II. Multiple-plane gravitational lensing, Mon. Not. Roy. Astron. Soc. 445, 1954 (2014), arXiv:1312.1536 [astro-ph.CO] .
  * Nishikawa  _et al._ [2020] H. Nishikawa, K. K. Boddy, and M. Kaplinghat, Accelerated core collapse in tidally stripped self-interacting dark matter halos, Phys. Rev. D 101, 063009 (2020), arXiv:1901.00499 [astro-ph.GA] .
  * Şengül and Dvorkin [2022] A. c. Şengül and C. Dvorkin, Probing dark matter with strong gravitational lensing through an effective density slope, Mon. Not. Roy. Astron. Soc. 516, 336 (2022), arXiv:2206.10635 [astro-ph.CO] .
  * Minor  _et al._ [2017] Q. E. Minor, M. Kaplinghat, and N. Li, A Robust Mass Estimator for Dark Matter Subhalo Perturbations in Strong Gravitational Lenses, Astrophys. J. 845, 118 (2017), arXiv:1612.05250 [astro-ph.GA] .
  * Zhang  _et al._ [2022] G. Zhang, S. Mishra-Sharma, and C. Dvorkin, Inferring subhalo effective density slopes from strong lensing observations with neural likelihood-ratio estimation, Mon. Not. Roy. Astron. Soc. 517, 4317 (2022), arXiv:2208.13796 [astro-ph.CO] .
  * Green and van den Bosch [2019] S. B. Green and F. C. van den Bosch, The tidal evolution of dark matter substructure - I. subhalo density profiles, Mon. Not. Roy. Astron. Soc. 490, 2091 (2019), arXiv:1908.08537 [astro-ph.GA] .
  * Benson and Du [2022] A. J. Benson and X. Du, Tidal tracks and artificial disruption of cold dark matter haloes, Mon. Not. Roy. Astron. Soc. 517, 1398 (2022), arXiv:2206.01842 [astro-ph.GA] .
  * Zhang  _et al._ [2023] G. Zhang, A. Çağan Şengül, and C. Dvorkin, Subhalo effective density slope measurements from HST strong lensing data with neural likelihood-ratio estimation, arXiv e-prints , arXiv:2308.09739 (2023), arXiv:2308.09739 [astro-ph.CO] .
  * Pullen  _et al._ [2014] A. R. Pullen, A. J. Benson, and L. A. Moustakas, Nonlinear Evolution of Dark Matter Subhalos and Applications to Warm Dark Matter, Astrophys. J. 792, 24 (2014), arXiv:1407.8189 [astro-ph.CO] .
  * Yang  _et al._ [2020] S. Yang, X. Du, A. J. Benson, A. R. Pullen, and A. H. G. Peter, A new calibration method of sub-halo orbital evolution for semi-analytic models, Mon. Not. Roy. Astron. Soc. 498, 3902 (2020), arXiv:2003.10646 [astro-ph.CO] .
  * Yang and Yu [2022] D. Yang and H.-B. Yu, Gravothermal evolution of dark matter halos with differential elastic scattering, JCAP 2022 (9), 077, arXiv:2205.03392 [astro-ph.CO] .
  * Despali  _et al._ [2020] G. Despali, M. Lovell, S. Vegetti, R. A. Crain, and B. D. Oppenheimer, The lensing properties of subhaloes in massive elliptical galaxies in sterile neutrino cosmologies, Mon. Not. Roy. Astron. Soc. 491, 1295 (2020), arXiv:1907.06649 [astro-ph.CO] .
  * Brennan  _et al._ [2019] S. Brennan, A. J. Benson, F.-Y. Cyr-Racine, C. R. Keeton, L. A. Moustakas, and A. R. Pullen, Quantifying the power spectrum of small-scale structure in semi-analytic galaxies, Mon. Not. Roy. Astron. Soc. 488, 5085 (2019), arXiv:1808.03501 [astro-ph.GA] .
  * Verdugo  _et al._ [2014] T. Verdugo, V. Motta, G. Foëx, J. E. Forero-Romero, R. P. Muñoz, R. Pello, M. Limousin, A. More, R. Cabanac, G. Soucail, J. P. Blakeslee, A. J. Mejía-Narváez, G. Magris, and J. G. Fernández-Trincado, Characterizing SL2S galaxy groups using the Einstein radius, Astron. Astrophys. 571, A65 (2014), arXiv:1409.2900 [astro-ph.CO] .
  * Remolina González  _et al._ [2020] J. D. Remolina González, K. Sharon, B. Reed, N. Li, G. Mahler, L. E. Bleem, M. Gladders, A. Niemiec, A. Acebron, and H. Child, Efficient Mass Estimate at the Core of Strong Lensing Galaxy Clusters Using the Einstein Radius, Astrophys. J. 902, 44 (2020), arXiv:2008.10676 [astro-ph.CO] .
  * Meneghetti  _et al._ [2023] M. Meneghetti, W. Cui, E. Rasia, G. Yepes, A. Acebron, G. Angora, P. Bergamini, S. Borgani, F. Calura, G. Despali, C. Giocoli, G. Granata, C. Grillo, A. Knebe, A. Macciò, A. Mercurio, L. Moscardini, P. Natarajan, A. Ragagnin, P. Rosati, and E. Vanzella, A persistent excess of galaxy-galaxy strong lensing observed in galaxy clusters, arXiv e-prints , arXiv:2309.05799 (2023), arXiv:2309.05799 [astro-ph.CO] .
  * Xu  _et al._ [2012] D. D. Xu, S. Mao, A. P. Cooper, L. Gao, C. S. Frenk, R. E. Angulo, and J. Helly, On the effects of line-of-sight structures on lensing flux-ratio anomalies in a $\Lambda$CDM universe, Mon. Not. Roy. Astron. Soc. 421, 2553 (2012), arXiv:1110.1185 [astro-ph.CO] .
  * Despali  _et al._ [2018] G. Despali, S. Vegetti, S. D. M. White, C. Giocoli, and F. C. van den Bosch, Modelling the line-of-sight contribution in substructure lensing, Mon. Not. Roy. Astron. Soc. 475, 5424 (2018), arXiv:1710.05029 [astro-ph.CO] .
  * Gilman  _et al._ [2019] D. Gilman, S. Birrer, T. Treu, A. Nierenberg, and A. Benson, Probing dark matter structure down to 107 solar masses: flux ratio statistics in gravitational lenses with line-of-sight haloes, Mon. Not. Roy. Astron. Soc. 487, 5721 (2019), arXiv:1901.11031 [astro-ph.CO] .
  * Dhanasingham  _et al._ [2023b] B. Dhanasingham, F.-Y. Cyr-Racine, A. H. G. Peter, A. Benson, and D. Gilman, Interlopers speak out: studying the dark universe using small-scale lensing anisotropies, Mon. Not. Roy. Astron. Soc. 518, 5843 (2023b), arXiv:2203.13775 [astro-ph.CO] .
  * Lazar  _et al._ [2023] A. Lazar, J. S. Bullock, M. Boylan-Kolchin, L. Moustakas, and A. Nierenberg, An analytic surface density profile for $\Lambda$CDM halos and gravitational lensing studies, arXiv e-prints , arXiv:2304.11177 (2023), arXiv:2304.11177 [astro-ph.CO] .
  * Díaz Rivero  _et al._ [2018] A. Díaz Rivero, F.-Y. Cyr-Racine, and C. Dvorkin, Power spectrum of dark matter substructure in strong gravitational lenses, Phys. Rev. D 97, 023001 (2018), arXiv:1707.04590 [astro-ph.CO] .
  * Hezaveh  _et al._ [2016] Y. Hezaveh, N. Dalal, G. Holder, T. Kisner, M. Kuhlen, and L. Perreault Levasseur, Measuring the power spectrum of dark matter substructure using strong gravitational lensing, JCAP 1611 (11), 048, arXiv:1403.2720 [astro-ph.CO] .
  * Cyr-Racine  _et al._ [2019] F.-Y. Cyr-Racine, C. R. Keeton, and L. A. Moustakas, Beyond subhalos: Probing the collective effect of the Universe’s small-scale structure with gravitational lensing, Phys. Rev. D 100, 023013 (2019), arXiv:1806.07897 [astro-ph.CO] .
  * Feng  _et al._ [2009] J. L. Feng, M. Kaplinghat, H. Tu, and H.-B. Yu, Hidden charged dark matter, JCAP 2009 (7), 004, arXiv:0905.3039 [hep-ph] .
  * Tulin  _et al._ [2013] S. Tulin, H.-B. Yu, and K. M. Zurek, Beyond collisionless dark matter: Particle physics dynamics for dark matter halo structure, Phys. Rev. D 87, 115007 (2013), arXiv:1302.3898 [hep-ph] .
  * Nadler  _et al._ [2020b] E. O. Nadler, R. H. Wechsler, _et al._ , Milky Way Satellite Census. II. Galaxy-Halo Connection Constraints Including the Impact of the Large Magellanic Cloud, Astrophys. J. 893, 48 (2020b), arXiv:1912.03303 [astro-ph.GA] .
  * Garavito-Camargo  _et al._ [2021] N. Garavito-Camargo, G. Besla, C. F. P. Laporte, A. M. Price-Whelan, E. C. Cunningham, K. V. Johnston, M. Weinberg, and F. A. Gómez, Quantifying the Impact of the Large Magellanic Cloud on the Structure of the Milky Way’s Dark Matter Halo Using Basis Function Expansions, Astrophys. J. 919, 109 (2021), arXiv:2010.00816 [astro-ph.GA] .
  * Behroozi  _et al._ [2014] P. S. Behroozi, R. H. Wechsler, Y. Lu, O. Hahn, M. T. Busha, A. Klypin, and J. R. Primack, Mergers and Mass Accretion for Infalling Halos Both End Well Outside Cluster Virial Radii, Astrophys. J. 787, 156 (2014), arXiv:1310.2239 [astro-ph.CO] .
  * Feng  _et al._ [2022] W.-X. Feng, H.-B. Yu, and Y.-M. Zhong, Dynamical instability of collapsed dark matter halos, JCAP 2022 (5), 036, arXiv:2108.11967 [astro-ph.CO] .
  * Center [1987] O. S. Center, Ohio supercomputer center (1987).
  * Diemand  _et al._ [2004] J. Diemand, B. Moore, J. Stadel, and S. Kazantzidis, Two body relaxation in CDM simulations, Mon. Not. Roy. Astron. Soc. 348, 977 (2004), arXiv:astro-ph/0304549 [astro-ph] .


# Boosting Share Routing for Multi-task Learning

Xiaokai Chen  Tencent PCGChina<EMAIL_ADDRESS>,  Xiaoguang Gu
Tencent PCGChina<EMAIL_ADDRESS>and  Libo Fu  Tencent PCGChina
<EMAIL_ADDRESS>
(2021)

###### Abstract.

Multi-task learning (MTL) aims to make full use of the knowledge contained in
multi-task supervision signals to improve the overall performance. How to make
the knowledge of multiple tasks shared appropriately is an open problem for
MTL. Most existing deep MTL models are based on parameter sharing. However,
suitable sharing mechanism is hard to design as the relationship among tasks
is complicated. In this paper, we propose a general framework called Multi-
Task Neural Architecture Search (MTNAS) to efficiently find a suitable sharing
route for a given MTL problem. MTNAS modularizes the sharing part into
multiple layers of sub-networks. It allows sparse connection among these sub-
networks and soft sharing based on gating is enabled for a certain route.
Benefiting from such setting, each candidate architecture in our search space
defines a dynamic sparse sharing route which is more flexible compared with
full-sharing in previous approaches. We show that existing typical sharing
approaches are sub-graphs in our search space. Extensive experiments on three
real-world recommendation datasets demonstrate MTANS achieves consistent
improvement compared with single-task models and typical multi-task methods
while maintaining high computation efficiency. Furthermore, in-depth
experiments demonstrates that MTNAS can learn suitable sparse route to
mitigate negative transfer.

multi-task learning, neural architecture search, parameter sharing

††copyright: iw3c2w3††journalyear: 2021††doi:
10.1145/XXXXXXX.XXXXXXX††conference: Companion Proceedings of the Web
Conference 2021; April 19–23, 2021; Ljubljana, Slovenia††booktitle: Companion
Proceedings of the Web Conference 2021 (WWW ’21 Companion), April 19–23, 2021,
Ljubljana, Slovenia††doi: 10.1145/3442442.3452323††isbn:
978-1-4503-8313-4/21/04††ccs: Computing methodologies Neural networks

##  1\. Introduction

Multi-task learning (MTL) aims to make full use of the knowledge contained in
multi-task labels to improve the overall performance(Caruana, 1997). It has
been extensively used in many real-world applications, such as recommendation
systems(Bansal et al., 2016; Covington et al., 2016; Zhao et al., 2019), e.g.
predicting whether a user will click on a video and the engagement time the
user will spend simultaneously. Compared with learning tasks separately MTL
benefits a lot. It not only reduces maintenance cost of online systems but
also could achieve better performance. MTL can be viewed as a form of
inductive transfer, from this perspective, it generalizes better by
introducing inductive biases contained in tasks(Ruder, 2017). However, the
inductive biases may conflict with each other, sharing information with a less
related task in this case might actually hurt performance which is known as
negative transfer(Ma et al., 2018). Therefore, a crucial problem in MTL is how
to appropriately balance the sharing route of parameters for each task.

Most existing neural-based approaches achieves MTL via parameter
sharing(Caruana, 1997; Ruder, 2017; Duong et al., 2015; Misra et al., 2016;
Yang and Hospedales, 2016). As shown in Fig1(a,b), there exist two typical
architectures of parameter sharing, hard and soft sharing. A classical
approach for hard sharing is called Share-Bottom(Caruana, 1993). It shares the
bottom hidden layers across all task layers. Although it reduces the risk of
overfitting, it suffers from significant degeneration in performance when the
tasks are less related. This is due to its sharing strategy forces the input
of all task-specific layers be the same, which harms model performance. Recent
work MMoE(Ma et al., 2018) is a representative soft sharing approach, it
divides the shared bottom hidden layers into several parallel sub-networks and
then aggregates the results of all sub-networks by gates. Compared with Share-
Bottom, MMoE achieves more flexible parameter sharing.

Figure 1. (a)Share-Bottom. (b) MMoE. (c) A variant of MMoE. (d)Average gate
scores in MMoE trained on BookCrossing(Ziegler et al., 2005). (e) Comparison
of the variant and MMoE on BookCrossing with two tasks, for each model, we
have 20 runs with independent random initialization and the hyper-parameters
are kept the same.

Interestingly, in practice we find that a variant architecture consistently
outperforms MMoE on a real-world recommendation dataset BookCrossing(Ziegler
et al., 2005), the comparison is shown in Fig1(e). The variant is similar to
MMoE, except for some connections between sub-networks and task layers are cut
off, as shown in Fig1(c). Note that the variant is a special case in MMoE when
the corresponding weight scores given by gates are constantly zero. This
motivates us to ask: why the variant is superior and why the gating mechanism
is not enough to establish a better architecture at least similar to the
variant? On the one hand, we find that MMoE is inherently a full-sharing (in
terms of topology) approach while the variant is a sparse version. We argue
that the full-sharing style of MMoE forces all experts to contribute to all
tasks, which limits the flexibility of the sharing route. On the other hand,
gating, as an idea to achieve dynamic feature aggregation, can hardly help
learning a sparse connection although theoretically possible, as shown in
Fig1(d) some gate scores are very low, but they don’t equal zero.

The above analysis implies that there exist various sparse sharing routes
which are beyond the capability of gates to establish. Therefore, we are
concerned with two questions:(i) compared with full-sharing, is sparse
connection generally helpful for MTL (e.g., mitigates negative transfer)? (ii)
if so, how to find the best sparse sharing route automatically?

Present work. To answer these two questions, we propose a general framework,
called MTNAS(Multi-Task Neural Architecture Search) to efficiently find a
suitable sharing route for a target MTL problem. Both sparse and full-sharing
routes are considered in our search space. MTNAS modularizes the sharing part
into multiple layers of sub-networks. In contrast to full-sharing in existing
typical approaches, sparse connections among sub-networks are allowed, while
soft sharing based on gating is enabled for a certain route. Besides, in order
to make full use of soft sharing, the choice of query for a gate is also
considered in the search space. Benefiting from this setting, each candidate
architecture in our search space defines a certain dynamic sharing route,
which is more general compared with previous work. Following ProxylessNAS(Cai
et al., 2019), a practical NAS approach, we directly learn the architecture
parameters and weights for large-scale target MTL data, while the
computational cost is in the same level of training a regular model. By
comparing the learned sharing route with existing full-sharing approaches, the
questions we concerned can be answered.

Search space is important, however, in MTL context, there exist no off-the-
shelf operations (e.g., convolution, pooling) that widely used in visual
domain(Zoph and Le, 2016). In order to balance sharing route, we first design
a search space that is composed of multiple search blocks, each block
enumerates all possible combinations of features from sub-networks in previous
layer as well as all possible choices of the query for a gate. Based on
ProxylessNAS, each candidate architecture is sampled from an over-
parameterized network with multinomial distributions, then REINFORCE(Williams,
1992) is applied to optimize architecture parameters since it generalizes to
non-differentiable evaluation metrics, while weights are tuned via standard
gradient back propagation. At inference time, the sharing route and its
weights are derived by picking up the local route with the maximum probability
in each block. Extensive experiments on three real-world recommendation
datasets demonstrate MTNAS achieves consistent improvement compared with
single-task models and typical multi-task methods while maintaining high
computation efficiency. Furthermore, in-depth experiments show that MTNAS is
able to find a sparse route that can effectively alleviate negative transfer
when tasks are less related.

##  2\. Related work

Parameter sharing in Multi-task learning. There are a number of deep models
that improve MTL via parameter sharing. Share-Bottom(Caruana, 1993) is a
classical approach which shares bottom hidden layers across all task layers,
although it reduces the risk of overfitting, it suffers from negative transfer
when tasks are less related, as it forces all tasks to share the same set of
parameters in bottom layers. Recent work focus on designing flexible parameter
sharing methods to mitigate negative transfer. L.Duong et al. (Duong et al.,
2015) adds L2 constraint between two single-sized model parameters, however it
requires prior knowledge of task relatedness which is still an open
problem(Baxter, 2000; Ben-David and Schuller, 2003; Ben-David et al., 2002).
I.Misra et al. (Misra et al., 2016) proposed a cross-stitch module that learns
to fuse the features extracted from different single-task models. Compared
with Share-Bottom, these models improve performance with more task-specific
parameters. For efficiently serving, J.Ma et al. proposed MMoE(Ma et al.,
2018), which splits the shared bottom layers into sub-networks and utilizes
gates to aggregate all features of sub-networks for each task. However, the
shared parts are all fully connected (in terms of topology) to task layers in
these previous works. Our approach allows sparse connections among shared sub-
networks, that is, parameters of different tasks are partially overlapped,
thus our approach can find more flexible sharing routes while maintaining high
computation efficiency.

Neural architecture search(NAS). NAS has become an increasing popular method
to design architectures automatically. Reinforcement learning based
methods(Zoph and Le, 2016; Baker et al., 2016) are usually computational
intensive, an alternative to RL-based methods is the evolutionary approach(Liu
et al., 2017), which optimizes the neural architecture by evolutionary
algorithms. Some recent work(Brock et al., 2017; Liu et al., 2018; Cai et al.,
2019) are proposed to accelerate NAS by one-shot setting, where the network is
sampled by a hyper graph, and weight sharing is adopt to accelerate the search
process. For instance, DARTS(Liu et al., 2018) optimizes the weights with a
continuous relaxation, so that the architecture parameters can be updated via
standard gradient descend. ProxylessNAS(Cai et al., 2019) further addresses
the issue of large GPU memory consumption with path binarization. However,
these previous work attempt to find a good architecture for a given task, the
focus of this work is to find a suitable sharing route for an MTL problem, and
consequently our search space is relatively small. Our approach is closely
related to the SNR(Ma et al., 2019), which learns connections among sub-
networks. Nevertheless, the sharing route found by SNR is static, and it
requires L0 regularization to achieve sparsity. In contrast, each specific
sharing route in our search space is dynamic. What’s more, sparsity is
naturally considered in our search space, hence there is no need to tune
hyper-parameters to control the sparsity in our MTNAS.

Figure 2. The illustration of our approach MTNAS. (a) A block defines a sub-
space, where different local sharing routes exist, intuitively each route
represents a certain combination of inputs (totally 3 values in this example)
that come from previous sub-networks. The choice of query for a gate in each
route is also contribute to the sub-space. (b) The over-parameterized network
defines our search space; it is composed of multiple search blocks (3 layers
in this example). The query of a block is omitted for convenience. (c) An
illustration of searching process. Each candidate sharing route is sampled
from multinomial distributions determined by architecture parameters. The
architecture parameters $\alpha$ and its weights $w_{u}$ are optimized
alternately.

##  3\. Proposed method: MTNAS

In this section, we introduce MTNAS in details. The key idea is to allow
sparse connections among shared sub-networks, that is, parameters can be
partially shared across different tasks, while soft sharing is enabled for a
specific route. By utilizing NAS to search a promising sharing route for an
MTL problem, we can confirm whether sparsity in sharing route is generally
beneficial for MTL. We first describe the search space (Section3.1), where
each candidate architecture defines a certain sharing route. Then we describe
how the architecture and its weights can be learned via gradient-based method
(Section3.2). Finally, we describe the searching process and how to derive the
learned route after searching (Section3.3).

###  3.1. Architecture search space: describing sparse and full-sharing routes
in a unified form

The design philosophy behind our search space is to include both sparse and
full-sharing routes so that the search space is general enough to solve MTL
problems. MTNAS modularizes the sharing part into multiple layers of sub-
networks. Without loss of generality, for a target MTL problem with $T$ tasks,
we assume there exist $L$ sub-networks layers in the space, with each layer
has $H$ sub-networks.

Following the typical block-wise NAS paradigm, our whole search space is
composed of multiple search blocks. Each block defines a sub-space that
contains different local sharing routes (e.g., connections among sub-networks)
with each route defines a sub-path. Unlike most search blocks designed in
visual domain(Liu et al., 2018; Cai et al., 2019), where each sub-path has its
own weights, a sub-path in our search space contains hardly any weights except
for a lightweight gate used to achieve dynamic aggregation, as shown in
Fig2(a). The intuition behind this setting is that our search space is
generated by enumerating all local sharing routes and the sub-networks are
shared during searching (Fig2(b)). Note that we allow all blocks to be
searched simultaneously. Next, we introduce the configuration of a block.

The configuration of a block. As shown in Fig2(a), a block defines a sub-
space, where different local sharing routes are contained, intuitively each
route represents a certain combination of inputs that come from previous sub-
networks. Besides, in order to achieve soft sharing for a certain route, we
assign a gate to each route in the block. What’s more, considering a query
comes from different layers has different abstract levels, we set the source
of a query can also be searched, so the choice of queries are also contribute
to the sub-space. Formally, the sub-space can be represented as the Cartesian
product $\mathcal{R}=\mathcal{V}\times\mathcal{Q}$, where $\mathcal{V}$
represents all possible combinations of values and $\mathcal{Q}$ represents
all choices of a query. To be specific, $\mathcal{V}$ is a set that contains
all possible combinations of outputs given by $H$ sub-networks in a previous
layer $l$. The cardinality of set $\mathcal{V}$ is
$|\mathcal{V}|=C_{1}^{H}+C_{2}^{H}+...+C_{H}^{H}=2^{H}-1$, where $C_{i}^{H}$
indicates the number of i-combinations from a set of $H$ values. A query
$q\in\mathcal{Q}$ can come from the output of any sub-network in previous
layer. There exist $|\mathcal{R}|$ different sharing routes within a block.
For a certain route (e.g., $k^{th}$ route, $k=1,2,...,|\mathcal{R}|$), the
inputs of a block are $\hat{V}$ and $\hat{q}$, where
$\hat{V}\in\mathbb{R}^{s*d_{v}}$ indicates $s$ values with each has dimension
$d_{v}$, and $\hat{q}\in\mathbb{R}^{d_{q}}$ indicates the query with dimension
$d_{q}$, the output $y_{k}$ is the weighted sum of values:

(1) $\displaystyle
y_{k}=g^{k}({\hat{q}},\hat{V})=\sum_{i=1}^{s}m_{i}v_{i}\quad\text{with}$
$\displaystyle
m_{i}=\frac{exp(e_{i})}{\sum_{i=1}^{s}exp(e_{i})},e=w^{k}\hat{q}$

where $g^{k}$ indicates the gate for k-th route, $m_{i}$ is the gate score for
i-th value $v_{i}$, $w^{k}$ is the parameter in the gate to be learned.

The over-parameterized network. As shown in Fig2(b), a block is located either
between two consequence sub-network layers or between the last sub-network
layer and task-layers. Consequently, the total number of blocks is
$B=(L-1)*H+T$. Based on the above setting, the whole search space
$\mathcal{A}$ can be represented as the Cartesian product of sub-spaces in
blocks, $\mathcal{A}=\prod_{i=1}^{B}\mathcal{R}_{i}$, which is an over-
parameterized network. This over-parameterized network is able to describe
various sharing routes, since existing typical parameter sharing approaches
(e.g., Share-Bottom and MMoE) are sub-graphs in the space.

###  3.2. Search the sharing route with multinomial distribution learning

With the search space defined above, in this section, we introduce how to find
a promising sharing route for a given MTL problem from the perspective of NAS.

Following ProxylessNAS(Cai et al., 2019), we start from an over-parameterized
network (supernet) from which a candidate sharing route can be sampled. The
goal is to find a good candidate route in the supernet to perform MTL. Note
that our search space is composed of $B$ blocks with each has
$|\mathcal{R}_{i}|$ local routes, therefore, by selecting a local route in
each block, a candidate sharing route can be established. Specifically, a
candidate sharing route is denoted as $\mathcal{N}(u,w_{u})$, where
$u\in\mathbb{R}^{B}$ indicates the selecting actions for $B$ blocks and
$w_{u}$ indicates its weights.

Architecture parameter optimization. We set each action $u_{i}$ is sampled
from a multinomial distribution determined by architecture parameters
$\alpha_{i}\in\mathbb{R}^{|\mathcal{R}_{i}|}$:

(2) $u_{i}\sim multinomial({p_{i}})$ (3) ${p_{i}}=softmax({\alpha_{i}})$

Therefore a sharing route can be established by sampling from $B$ multinomial
distributions. In order to optimize on non-differentiable evaluation metrics,
we utilize REINFORCE(Williams, 1992) to optimize architecture parameters by
maximizing the expected reward got from sampled architectures. The intuition
behind the optimization is that the candidate sharing route with good
performance should have a higher probability to be sampled. Therefore, the
object function for optimizing architecture parameters are formalized as:

(4) $J({\alpha})=E_{{u}\sim{p(\alpha)}}R_{val}(\mathcal{N}(u,w_{u}))$

where ${p(\alpha)}$ indicates the multinomial distributions determined by
architecture parameters ${\alpha}$, $R_{val}$ indicates the reward(e.g., AUC,
accuracy, -loss) of the sampled architecture on validation set. According to
REINFORCE(Williams, 1992), the gradient of architecture parameters is obtained
as follows:

(5)
$\nabla_{{\alpha}}J({\alpha})=(R_{val}(\mathcal{N}(u,w_{u}))-b)\nabla_{{\alpha}}\log
p_{{\alpha}}$

where b is the baseline to reduce the variance of reward, here we simply
compute the moving average of rewards experienced so far as baseline.

###  3.3. Details in training and testing

In this section, we describe the training of architecture parameters and its
weights (Fig2(c)), and introduce the deriving of learned route after searching
(Algorithm1).

An instinctive understanding of Algorithm1 is that at each iteration, a
sharing route is sampled from multinomial distributions that determined by
architecture parameters, then the architecture parameters as well as the
weights of this sampled route are optimized in turn, and as this process
iterates, the sampling probabilities of routes with good performance gradually
increase. After searching, we pick up the local sharing route with the maximum
probability in each block to derive the final architecture.

Algorithm 1 Architecture searching and deriving

0: train set and valid set, supernet with $B$ blocks.

0: Optimized architecture parameters $\alpha$ and weights $w$.

Initialize $\alpha$ and $w$.

while not converged do

for each $\text{block}_{i}$ in supernet do

Calculate the sample probability for different local sharing routes via Eq3;

Sample a local sharing route $u_{i}$ via Eq2;

end for

Get a candidate sharing route $\mathcal{N}(u,w_{u}),\ \text{with}\
u=\\{u_{i}\\}_{i=1}^{B}$;

Update weights $w$ by descending gradient computed via
$\nabla_{w}\mathcal{L}_{train}(\mathcal{N}(u,w_{u}))$;

Update architecture parameters $\alpha$ by ascending gradient computed via
Eq5;

end while

return Derive the final architecture based on $\alpha$ and $w$.

##  4\. Experiments

We design our experiments with the goals of (i) verifying the improvement of
MTNAS over typical sharing approaches and (ii) answering whether sparsity in
sharing route is generally helpful to mitigate negative transfer. We first
conduct experiments on three real-world recommendation datasets, considering
there naturally exist multiple tasks in recommendation systems. We then
conduct experiments on synthetic data to further confirm the effectiveness of
MTNAS.

Table 1. Statistics of the datasets. Dataset | #Train | #Valid | #Test | Fields | Features(Sparse) | Task number
---|---|---|---|---|---|---
Bookcrossing | 800,000 | 200,000 | 149,780 | 15 | 1,000,000 | 2
Tiktok | 15,697,872 | 1,962,234 | 1,962,234 | 9 | 4,000,000 | 2
Goodreads | 1,822,664 | 455,666 | 456,020 | 14 | 500,000 | 3
Table 2. Results on BookCrossing and Tiktok (higher AUC is better). The performance degradation compared with single-task model is in gray. Method | BookCrossing | Tiktok
---|---|---
AUC0 | AUC1 | MTL-Loss | AUC0 | AUC1 | MTL Loss
Single | 0.7842 | - | - | 0.7485 | - | -
- | 0.7984 | - | - | 0.9428 | -
Share-Bottom | 0.7834 | 0.8014 | 0.7322 | 0.7478 | 0.9415 | 0.6020
MMoE | 0.7885 | 0.8022 | 0.7302 | 0.7488 | 0.9425 | 0.6006
ML-MMoE | 0.7884 | 0.8051 | 0.7299 | 0.7487 | 0.9421 | 0.6011
AutoMTL(Ours) | 0.7907 | 0.8086 | 0.7247 | 0.7507 | 0.9467 | 0.5930

###  4.1. Experimental setup

Datasets. We evaluate our method on three public real-world recommendation
datasets: Bookcrossing(Ziegler et al., 2005), Goodreads(Wan and McAuley, 2018)
and Tiktok(Bytedance, 2019), datasets are randomly split into training,
validation and testing sets, the statistics are listed in Table1. We hash each
feature into a hexadecimal number, and calculate the remainder to get the
feature id. Bookcrossing contains 278,858 users providing 1,149,780 ratings
about 271,379 books. We construct a MTL problem with two tasks: predicting
whether a user rates a book (denoted task0) and whether a user is satisfied
with a book(task1). Goodreads is collected from a book review website. Due to
the complete dataset is extreame large, we use a medium-size subset by setting
genre as poetry following the official advise. It contains 2,734,350
interactions collected from 377,799 users’ public bookshelves and covers 36514
books. An MTL problem with three tasks is constructed by predicting whether a
user reads a book(task0), whether a user is satisfied(task1) and whether a
user leaves a review text(task2). Tiktok is a dataset provided by Bytedance in
the 2019 Short Video Understanding Challenge. There are two tasks in the
challenge, predicting whether a user finishes watching a video(task0) and
whether a user likes a video(task1).

Evaluation metrics. Since each single task is a binary classification problem,
the cross-entropy loss is used for each task. Therefore, the total loss
(denoted MTL-Loss) for MTL of each dataset is a sum of loss for each single
task. We use AUC (area under ROC curve) scores as evaluation metric. It is
noticeable that a slightly higher AUC at 0.001-level is regarded significant
for CTR-prediction like tasks, which has also been pointed out in existing
works(Cheng et al., 2016; Guo et al., 2017; Wang et al., 2017).

###  4.2. Implementation Details

Input feature means the root shared feature. All the raw features including
user-side and item-side are first discretized, then an embedding layer is used
to map these one-hot features to distributed representations, then
representations of different fields are concatenated to form the input
feature. Embedding dimension is empirically set 10 for all datasets.

Methods. We compare MTNAS with three widely used approaches: Share-
Bottom(Caruana, 1993), MMoE(Ma et al., 2018) and ML-MMoE. There are two fully-
connected layers in Share-Bottom. As for MMoE, we set one fully-connected
layer followed by four sub-networks, each of which being a one-layer fully-
connected layer. ML-MMoE is an extension of MMoE, which has multiple sub-
network layers. As for MTNAS, we set one fully-connected layer followed by two
subsequent sub-network layers($L=2$) with each layer having four sub-
networks($H=4$), each of which being a one-layer fully-connected layer. In
MTNAS, the hidden size of all fully-connected layers is set 64 and $R_{val}$
is set as the sum of AUC scores of each task. To make the comparison fair, we
set the number of parameters approximately the same as MTNAS for other
methods. Task layer in these models are all a fully connected layer. ReLU(Nair
and Hinton, 2010) activation function is used wherever needed. As for single-
task model, its architecture is the same as Share-Bottom except for only one
task layer in it.

Hyper-parameters. With regard to MTNAS, for the three datasets, adam(Kingma
and Ba, 2014) optimizer with an initial learning rate of 0.01 is used to
update architecture parameters, the mini-batch size is 1024. For the
optimization of weights, another adam optimizer with an initial learning rate
of 0.001 is adopted, and weight decay is set 0.0005, the mini-batch size is
512. As for the compared methods, we apply grid search for optimal training
hype-parameters. In order to provide a fair comparison, the loss function is
kept the same for all methods. The Adam optimizer is also adopted to update
parameters for all these methods.

Table 3. Results on GoodRead (higher AUC is better). Method | AUC0 | AUC1 | AUC2 | MTL Loss
---|---|---|---|---
Single | 0.8104 | - | - | -
- | 0.7752 | - | -
- | - | 0.8209 | -
Share-Bottom | 0.8250 | 0.7748 | 0.8415 | 1.0726
MMOE | 0.8255 | 0.7761 | 0.8441 | 1.0716
ML-MMOE | 0.8244 | 0.7743 | 0.8443 | 1.0720
AutoMTL(ours) | 0.8281 | 0.7771 | 0.8460 | 1.0656
Figure 3. The learned sharing routes on three datasets.

###  4.3. Main results

Performance. We compare our approach MTNAS with single task model as well as
typical multi-task approaches, Share-Bottom, MMOE and ML-MMOE. The results on
three datasets are listed in Table2 and Table3. It can be observed that MTNAS
consistently outperforms compared methods on three datasets, MTNAS achieves
the highest AUC score on all tasks for three MTL problems, this demonstrates
the effectiveness of MTNAS. We notice that negative transfer happens for
compared multi-task methods (colored in gray), where the performance is worse
than single-task model. For the ease of understanding, we compute Pearson
correlation coefficient (PCC) to estimate the correlation of tasks, results
are illustrated in Table4. It is observed that the PCC of two tasks in Tiktok
is only 0.030, which is very close to zero, means that linear correlation of
these two tasks is quite weak. Therefore, negative transfer is leaning to
happen if the sharing route is not appropriate. However, MTNAS escapes from
negative transfer, this indicates that it’s able to find a suitable sharing
route to make full use of knowledge of tasks. To further understand MTNAS, we
discuss in Section5.

The learned sharing route of MTNAS is illustrated in Fig3. In general, it can
be observed that all the searched sharing routes are sparse (compared to full-
sharing). As is shown in Fig3(a), task-0 and task-1 share path input-s2-s5,
while other parts are private for each task. We suppose that this architecture
provides a trade-off between the shared and independent parts, making each
task take what it needs adaptively. As for Goodreads (Fig3(c)), it’s worth
noting that task-0 and task-1 share the same combination of sub-networks:
s6&s7. Interestingly, we find that the PCC of task-0 and task-1 is highest,
0.493, among three tasks (Table4). This phenomenon further suggests that our
approach MTNAS can find interpretable sharing route for a given MTL problem.

Table 4. The Pearson correlation (PCC) of tasks. t0 indicates task-0(defined in Sec4.1). Dataset | t0&t1 | t1&t2 | t0&t2
---|---|---|---
BookCrossing | 0.348 | - | -
Tiktok | 0.030 | - | -
GoodReads | 0.493 | 0.124 | 0.245
Table 5. Comparison of variants. We compare testing loss on the three datasets. Variants | BookCrossing | Tiktok | GoodReads
---|---|---|---
Baseline | 0.7286 | 0.5961 | 1.0690
$\text{MTNAS}_{\text{w/o QS}}$ | 0.7260 | 0.5941 | 1.0669
MTNAS | 0.7247 | 0.5930 | 1.0656

Effectiveness of Components. We compare MTNAS with two variants. Baseline
replaces gate with mean pooling, so the learned route is static. MTNAS(w/o QS)
teases apart the query selection and all queries are set as the root feature.
As shown in Table5, our entire method outperforms all the variants. By
comparing MTNAS with Baseline, we confirm the effectiveness of dynamic
aggregation. Compared to MTNAS(w/o QS), MTNAS achieves consistent improvements
which demonstrates that it’s able to find suitable queries and the root input
feature is not always the best choice for query.

##  5\. Analysis

###  5.1. Experiments on synthetic data.

To further make it clear when MTNAS works and how it behaves, we conduct
experiments on synthetic data, where task relatedness $\rho$ can be
controlled. We push it to an extreme case where $\rho=0$, in this case tasks
are unrelated, so we can observe how MTNAS behaves. We generate two regression
tasks; the synthetic data generation is illustrated below.

Synthetic data generation Following (Ma et al., 2018), the synthetic data is
generated through the following four steps.

  1. (1)

Given the input feature dimension $d$, we generate two orthogonal unit vectors
$u_{1},u_{2}\in\mathbb{R}^{d}$. To be specific,

(6) $u_{1}^{T}u_{2}=0,||u_{1}||_{2}=|u_{2}||_{2}=1$

  2. (2)

Given a correlation score $-1\leq\rho\leq 1$, we generate two weight vectors
$w_{1},w2$,

(7) $w_{1}=u_{1},\ w_{2}=\rho u_{1}+\sqrt{1-\rho^{2}}u_{2}$

with this setting, the cosine similarity of the these two weights is exactly
$\rho$, that is, $cos(w_{1},w_{2})=\rho$.

  3. (3)

Generate inputs. Randomly sample an input data point $x\in\mathbb{R}^{d}$,
with each entry from a normal distribution $\mathcal{N}(0,1)$.

  4. (4)

Generate two labels $y_{1},y_{2}$ for two regression tasks as follows,

(8)
$y_{1}=w_{1}^{T}x+\sum_{i=1}^{m}sin(\alpha_{i}w_{1}^{T}x+\beta_{i})+\epsilon_{1}$
(9)
$y_{2}=w_{2}^{T}x+\sum_{i=1}^{m}sin(\alpha_{i}w_{2}^{T}x+\beta_{i})+\epsilon_{2}$

the sum of sine functions here make the mapping from input to label non-
linear. $\epsilon$ is the noise from $\mathcal{N}(0,0.01)$.

Note that, the correlation parameter $\rho$ represents the cosine similarity
of two task labels. Due to the non-linear data generation procedure, it’s not
straightforward to control the Pearson correlation coefficient (PCC). So we
indirectly control PCC through $\rho$. We set $\rho=0$ and repeat these four
steps 10,000 times to generate a dataset with two unrelated tasks. In our
experiment, the PCC of two tasks is -0.0162.

Figure 4. Comparison of Share-Bottom, MMoE and MTNAS on synthetic data with
two unrelated tasks. The plot show total loss over steps. Figure 5. The
learned sharing route with L=1,H=3. Figure 6. Left, the architecture of MMoE.
Right, the distribution of average gate scores.

Results. We compare Share-Bottom, MMoE with architecture searched by MTNAS on
the synthetic data. To make the comparison fair, we set the number of
parameters for each model approximately the same. The results are shown in
Fig4. It can be observed that MTNAS achieves the lowest loss. Note that the
main difference between MMoE and MTNAS is that the sharing route in MMoE is
fully connected (in terms of topology), while MTNAS’s is sparse. Furthermore,
a key feature of the learned sharing route is that no overlap exists between
two sharing route of each task, on the one hand this indicates that MTNAS
behaves reasonable since no knowledge could be shared with two unrelated
tasks, on the other hand we believe this demonstrates that sparsity is
important to alleviate negative transfer when tasks are less related, because
it allows parameters of each task to be partially shared, while although the
average gate scores in MMoE for some shared parts are very low, it is still
not equal to constantly zero.

###  5.2. Parameter sensitivity.

We study the sensitivity to $L$ and $H$(Sec3.1). We find that setting $L=2$
provides good performance on the three datasets, while increasing $L$ beyond 2
gives marginal returns in performance. We also find diminishing returns and
increasing search cost for larger $H$(Fig7).

Figure 7. Performance on GoodReads w.r.t the number of sub-networks in a
layer.

##  6\. Conclusion

We present MTNAS to efficiently find a suitable sparse sharing route to
perform multi-task learning. MTNAS consistently outperforms single-task model
and typical multi-task approaches on three real-world datasets, which
indicates that it can establish a promising sharing route to make full use of
the knowledge of tasks. Visualization of learned routes confirm that sparsity
is beneficial for MTL as it allows parameters to be partially shared across
tasks. Experiments on synthetic data further demonstrates that, by allowing
sparse connection among shared sub-networks, MTNAS is able to find a sparse
route that can effectively alleviate negative transfer when tasks are less
related.

## References

  * (1)
  * Baker et al. (2016) Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. 2016.  Designing neural network architectures using reinforcement learning.  _arXiv preprint arXiv:1611.02167_ (2016).
  * Bansal et al. (2016) Trapit Bansal, David Belanger, and Andrew McCallum. 2016\.  Ask the gru: Multi-task learning for deep text recommendations. In _Proceedings of the 10th ACM Conference on Recommender Systems_. 107–114.
  * Baxter (2000) Jonathan Baxter. 2000\.  A model of inductive bias learning.  _Journal of artificial intelligence research_ 12 (2000), 149–198.
  * Ben-David et al. (2002) Shai Ben-David, Johannes Gehrke, and Reba Schuller. 2002\.  A theoretical framework for learning from a pool of disparate data sources. In _Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining_. 443–449.
  * Ben-David and Schuller (2003) Shai Ben-David and Reba Schuller. 2003.  Exploiting task relatedness for multiple task learning.  In _Learning Theory and Kernel Machines_. Springer, 567–580.
  * Brock et al. (2017) Andrew Brock, Theodore Lim, James M Ritchie, and Nick Weston. 2017.  Smash: one-shot model architecture search through hypernetworks.  _arXiv preprint arXiv:1708.05344_ (2017).
  * Bytedance (2019) Bytedance. 2019\.  _Short Video Understanding Challenge_.  http://ai-lab-challenge.bytedance.com/tce/vc/
  * Cai et al. (2019) Han Cai, Ligeng Zhu, and Song Han. 2019.  ProxylessNAS: Direct Neural Architecture Search on Target Task and Hardware.  (2019).
  * Caruana (1993) Rich Caruana. 1993\.  Multitask Learning: A Knowledge-Based Source of Inductive Bias ICML.  _Google Scholar Google Scholar Digital Library Digital Library_ (1993).
  * Caruana (1997) Rich Caruana. 1997\.  Multitask learning.  _Machine learning_ 28, 1 (1997), 41–75.
  * Cheng et al. (2016) Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. 2016\.  Wide & deep learning for recommender systems. In _Proceedings of the 1st workshop on deep learning for recommender systems_. 7–10.
  * Covington et al. (2016) Paul Covington, Jay Adams, and Emre Sargin. 2016\.  Deep neural networks for youtube recommendations. In _Proceedings of the 10th ACM conference on recommender systems_. 191–198.
  * Duong et al. (2015) Long Duong, Trevor Cohn, Steven Bird, and Paul Cook. 2015\.  Low resource dependency parsing: Cross-lingual parameter sharing in a neural network parser. In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_. 845–850.
  * Guo et al. (2017) Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017.  DeepFM: a factorization-machine based neural network for CTR prediction.  _arXiv preprint arXiv:1703.04247_ (2017).
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ (2014).
  * Liu et al. (2017) Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. 2017\.  Hierarchical representations for efficient architecture search.  _arXiv preprint arXiv:1711.00436_ (2017).
  * Liu et al. (2018) Hanxiao Liu, Karen Simonyan, and Yiming Yang. 2018\.  Darts: Differentiable architecture search.  _arXiv preprint arXiv:1806.09055_ (2018).
  * Ma et al. (2019) Jiaqi Ma, Zhe Zhao, Jilin Chen, Ang Li, Lichan Hong, and Ed H Chi. 2019\.  SNR: Sub-Network Routing for Flexible Parameter Sharing in Multi-task Learning. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 216–223.
  * Ma et al. (2018) Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi. 2018\.  Modeling task relationships in multi-task learning with multi-gate mixture-of-experts. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1930–1939.
  * Misra et al. (2016) Ishan Misra, Abhinav Shrivastava, Abhinav Gupta, and Martial Hebert. 2016.  Cross-stitch networks for multi-task learning. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_. 3994–4003.
  * Nair and Hinton (2010) Vinod Nair and Geoffrey E Hinton. 2010.  Rectified linear units improve restricted boltzmann machines. In _Proceedings of the 27th international conference on machine learning (ICML-10)_. 807–814.
  * Ruder (2017) Sebastian Ruder. 2017\.  An Overview of Multi-Task Learning in Deep Neural Networks.  _arXiv: Learning_ (2017).
  * Wan and McAuley (2018) Mengting Wan and Julian McAuley. 2018.  Item recommendation on monotonic behavior chains. In _Proceedings of the 12th ACM Conference on Recommender Systems_. 86–94.
  * Wang et al. (2017) Ruoxi Wang, Bin Fu, Gang Fu, and Mingliang Wang. 2017\.  Deep & cross network for ad click predictions.  In _Proceedings of the ADKDD’17_. 1–7.
  * Williams (1992) Ronald J Williams. 1992\.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ 8, 3-4 (1992), 229–256.
  * Yang and Hospedales (2016) Yongxin Yang and Timothy Hospedales. 2016.  Deep multi-task representation learning: A tensor factorisation approach.  _arXiv preprint arXiv:1605.06391_ (2016).
  * Zhao et al. (2019) Zhe Zhao, Lichan Hong, Li Wei, Jilin Chen, Aniruddh Nath, Shawn Andrews, Aditee Kumthekar, Maheswaran Sathiamoorthy, Xinyang Yi, and Ed Chi. 2019.  Recommending what video to watch next: a multitask ranking system. In _Proceedings of the 13th ACM Conference on Recommender Systems_. 43–51.
  * Ziegler et al. (2005) Cai-Nicolas Ziegler, Sean M McNee, Joseph A Konstan, and Georg Lausen. 2005.  Improving recommendation lists through topic diversification. In _Proceedings of the 14th international conference on World Wide Web_. 22–32.
  * Zoph and Le (2016) Barret Zoph and Quoc V Le. 2016.  Neural architecture search with reinforcement learning.  _arXiv preprint arXiv:1611.01578_ (2016).