# Cosmology from one galaxy in voids?

Bonny Y. Wang (汪玥) Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh, PA
15213  Center for Computational Astrophysics, Flatiron Institute, 162 5th
Avenue, New York, NY 10010 USA  Alice Pisani Center for Computational
Astrophysics, Flatiron Institute, 162 5th Avenue, New York, NY 10010 USA  Aix-
Marseille University, CNRS/IN2P3, CPPM, 163 Av. de Luminy, 13009, Marseille,
France  The Cooper Union for the Advancement of Science and Art, 30 Cooper Sq,
New York, NY 10003 USA  Department of Astrophysical Sciences, Princeton
University, 4 Ivy Lane, Princeton, NJ 08544 USA

###### Abstract

Understanding galaxy properties may be the key to unlocking some of the most
intriguing mysteries of modern cosmology. Recent work relied on machine
learning to extract cosmological constraints on $\Omega_{\mathrm{m}}$ using
only one galaxy. But if this is true, how should we select the galaxy to use
for cosmology inference? In this paper, we consider selecting a galaxy that
lies in cosmic voids, the underdense regions of the cosmic web, and compare
the constraints obtained with the ones obtained when randomly selecting a
galaxy in the whole sample. We use the IllustrisTNG galaxy catalog from the
CAMELS project and the VIDE void finder to identify galaxies inside voids. We
show that void galaxies provide stronger constraints on $\Omega_{\mathrm{m}}$
compared to randomly selected galaxies. This result suggests that the
distinctive characteristics of void galaxies may provide a cleaner and more
effective environment for extracting cosmological information.

Cosmology — Machine learning — Large scale structure — Galaxy properties

##  1 Introduction

One of the primary goals of cosmology is to constrain the parameters of the
cosmological model. The matter density parameter $\Omega_{\mathrm{m}}$,
representing the fractional energy density of matter in the Universe, is a
crucial parameter to determine in the quest to understand the composition and
evolution of our Universe. The current framework for the standard model of
cosmology is confirmed by a wide range of cosmological observations, including
(but not limited to) galaxy clustering statistics (e.g. Eisenstein et al.,
2005; Vikhlinin et al., 2009; Allen et al., 2011; DESI Collaboration et al.,
2024), cosmic microwave background (e.g. Hu & Dodelson, 2002; Spergel et al.,
2003, 2007; Planck Collaboration et al., 2020) and supernovae (e.g. Phillips,
1993; Perlmutter et al., 1997; Branch, 1998; Riess et al., 1998; Perlmutter et
al., 1999; Tonry et al., 2003; Astier et al., 2006; Betoule et al., 2014).

Recently, relying on machine learning, Villaescusa-Navarro et al. (2022)
extracted cosmological constraints from the properties of one galaxy.
Subsequently, Chawak et al. (2023) showed that constraints can be improved
when using multiple galaxies. This method has also been tested in Echeverri-
Rojas et al. (2023) using four different simulations, including IllustrisTNG
(Marinacci et al., 2018; Naiman et al., 2018; Springel et al., 2018; Nelson et
al., 2019), SIMBA (Davé et al., 2019), Astrid (Ni et al., 2022; Bird et al.,
2022; Ni et al., 2023), and Magneticum (Dolag, 2015). The fact that these
simulations all have different subgrid physics models and different redshifts
further proved the robustness of the methodology. Hahn et al. (2023) also
showed that we can extend this study to observations by extracting
cosmological information simply relying on the photometry of a few galaxies.

These results embed underlying questions that still need to be answered: How
should we select the one galaxy or group of galaxies to optimize the
constraints? Are all galaxies equal in terms of the cosmological information
they bear? In this paper, we address this question by considering galaxies in
the underdense regions of our Universe, cosmic voids.

Voids are sensitive probes to extract cosmological information (e.g. Park &
Lee, 2007; Lavaux & Wandelt, 2010; Biswas et al., 2010; Lavaux & Wandelt,
2012; Pisani et al., 2015a; Hamaus et al., 2016; Pisani et al., 2019; Verza et
al., 2019; Stopyra et al., 2021; Kreisch et al., 2021; Contarini et al.,
2022a, b; Pelliciari et al., 2022; Schuster et al., 2023; Wang et al., 2023):
for instance the void-galaxy cross-correlation function and the void size
function already provide tight constraints on $\Omega_{\mathrm{m}}$ (Hamaus et
al., 2020; Contarini et al., 2022b). Since voids are goldmines of cosmological
information (Pisani et al., 2019; Moresco et al., 2022), it is interesting to
ask whether galaxies inside voids bear a stronger constraining power from a
cosmology perspective. A number of studies explored the properties of galaxies
in voids (see e.g. Peebles, 2001; Jung et al., 2014; Habouzit et al., 2020;
Panchal et al., 2020; Rosas-Guevara et al., 2022; Rodríguez Medrano et al.,
2022; Rodríguez-Medrano et al., 2023b; Jaber et al., 2024). It has been shown,
for example, that galaxies inside voids are expected to assemble stars slowly
(Domínguez-Gómez et al., 2023). The observation of void galaxies is also an
active field of research (see e.g. Grogin & Geller, 1999; Rojas et al., 2004;
Hoyle et al., 2005; Croton et al., 2005; Kreckel et al., 2011, 2012; Moorman
et al., 2015; Beygu et al., 2017; Douglass et al., 2018; Pustilnik et al.,
2019; Florez et al., 2021; Pandey et al., 2021; Pustilnik et al., 2022;
Kurapati et al., 2024), albeit some studies found contradictory results (for
example related to the star formation rate and other properties of galaxies in
voids). Due to their isolated nature, it is reasonable to expect that void
galaxies—less influenced by external disturbances such as stripping and
harassment—could have a stronger connection to cosmology and the physics of
the early universe. Finally, differences have also been investigated in
simulations, for example, more recently Rodríguez-Medrano et al. (2023a) and
Curtis et al. (2024) suggested that void galaxies have significantly different
properties compared to non-void galaxies (in the IllustrisTNG simulation),
which may impact the link to cosmological information.

In this work, we investigate whether individual void galaxies contain more
pristine information about cosmology than galaxies residing in other
environments. Section 2 introduces the simulations and datasets, as well as
the method we used to select the void and non-void galaxies. Section 3
illustrates our predictions for $\Omega_{\mathrm{m}}$ when using void and non-
void galaxies. Finally, Section 4 concludes and discusses future prospects.

##  2 Methods

###  2.1 Simulations and Datasets

In this work, we used the dataset from the CAMELS project (Villaescusa-Navarro
et al., 2021). Specifically, we use the galaxy catalogs from the LH set of the
IllustrisTNG suite. The IllustrisTNG simulations are run with the AREPO code
(Weinberger et al., 2020). This suite contains 1000 simulations of
$(25h^{-1}Mpc)^{3}$ volume each and, while the values of $\Omega_{\rm
b}=0.049$, $h=0.6711$, $n_{s}=0.9624$, $\sum m_{\nu}=0.0$ eV, $w=-1$ are
fixed, the values of other cosmological and astrophysical parameters vary. In
particular, the matter density parameter $\Omega_{\mathrm{m}}$, is varied
within the range of 0.1 to 0.5. Notably, each simulation also varies four
astrophysical parameters: two for supernovae ($A_{\rm SN1}$ and $A_{\rm SN2}$)
and two for AGN ($A_{\rm AGN1}$ and $A_{\rm AGN2}$). Therefore, when inferring
$\Omega_{\mathrm{m}}$, we implicitly marginalize over baryonic uncertainties.
We followed the procedure described in Villaescusa-Navarro et al. (2022), and
considered 17 galaxy properties (including $M_{\rm g}$, $M_{\rm BH}$, $M_{*}$,
$M_{t}$, $V_{\rm{max}}$, $\sigma_{v}$, $Z_{\rm g}$, $Z_{*}$, SFR, $J$, $V$,
$R_{*}$, $R_{\rm t}$, $R_{max}$ and the U, K, and g photometric bands for the
CAMELS-IllustrisTNG galaxies, see more details in Villaescusa-Navarro et al.,
2021). We consider a galaxy as a subhalo that contains no less than 20
particles.

###  2.2 The Void Finder

To build a void catalog from the simulations, we use the VIDE void
finder111https://bitbucket.org/cosmicvoids/vide_public/wiki/Home (Sutter et
al., 2015). VIDE is a popular public Voronoi-watershed void finder toolkit
based on ZOBOV (Neyrinck, 2008). It has been widely used in the field (see
e.g. Hamaus et al., 2015, 2016, 2017, 2022; Baldi & Villaescusa-Navarro, 2016;
Habouzit et al., 2020; Kreisch et al., 2021; Contarini et al., 2022b; Douglass
et al., 2022). VIDE allows to find voids with no assumption on the shape,
relying on topological information.

The void finding procedure has various steps: first, it performs a Voronoi
tessellation of the galaxy field. Since regions with fewer (more) galaxies
will correspond to larger (smaller) Voronoi cells, this first step provides a
local density field estimator through the inverse of the Voronoi cell volume.
Once Voronoi cells are available, VIDE builds the void regions by merging
Voronoi cells: it starts with local minima (largest cells) and merges adjacent
cells if the density increases, the merging is done through the watershed
transform and provides the voids for the analysis. When cells are merged to
form voids, it is then possible to define a void center (calculated as the
volume weighted barycenter of the Voronoi cells for each void). We note that
the center, being defined through the whole void, bears information about the
large-scale structure environment of the void.

It is also important to notice that the definition of voids from VIDE includes
overdense regions constituting the outer rim at the edge of voids (as detailed
in Habouzit et al. (2020); Zaidouni et al. (2024)). Therefore the collection
of Voronoi cells that we use will include both cells from the core region of
voids, as well as Voronoi cells on the outer regions, in more overdense
environments. The volume of each Voronoi cell is a measure of how isolated the
galaxy corresponding to that cell is: the larger the volume, the more isolated
the galaxy.

In this paper, we carefully need to select galaxies based on both their local
environment and the large-scale environment. While the void center position
(and any selection at a given distance from it) allows to account for the
large-scale environment, the Voronoi cell volume guarantees a detailed galaxy
selection that also accounts for their local environment. The distribution of
the Voronoi cell volume for galaxies in our dataset is shown in Figure 1.
Finally, void catalogs are subject to the presence of spurious voids (also
known as Poisson voids) (Neyrinck, 2008; Pisani et al., 2015b; Cousinou et
al., 2019). These are non-physical voids that arise due to a number of
effects, including the minimum mass of the galaxies in the simulation.
Generically spurious voids will present a shallower profile, with a higher
density in the center and a smaller void size. Additional purity cuts need to
be performed on the catalog to avoid bias from spurious voids.

A careful selection of galaxies is particularly relevant here, given the
relatively small simulation box of $(25~{}h^{-1}{\rm Mpc})^{3}$ (compared to
the size of cosmic voids, that usually span sizes in the range of a few to a
hundred of $~{}h^{-1}{\rm Mpc}$), and to account for the complex shape of
voids. Details of how this galaxy selection is performed are provided in
Section 2.4.

Figure 1: Histogram of Voronoi cell volume in voids for galaxies in the
dataset. Galaxies with larger Voronoi cell volume are more isolated.

###  2.3 Predicting $\Omega_{\mathrm{m}}$ with neural networks using one
galaxy

We follow Villaescusa-Navarro et al. (2022) and use fully connected layers
with hyperparameters optimized by optuna (Akiba et al., 2019) to perform
likelihood-free inference on $\Omega_{\mathrm{m}}$ using one galaxy. In order
to fully utilize the dataset and train the networks to be adaptable to as many
galaxies as possible, we still use all galaxies in the simulation to train our
networks. Therefore, the training process is the same as Villaescusa-Navarro
et al. (2022) and as a first test we have reproduced their results by using
the public code available at
https://github.com/franciscovillaescusa/Cosmo1gal. We use similar accuracy and
precision metrics as in Echeverri-Rojas et al. (2023) to compare between void
and non-void galaxies on predicting $\Omega_{\mathrm{m}}$. In particular, we
rely on the rms error (RMSE), the mean relative error $\epsilon$ and the
coefficient of determination $R^{2}$, defined as, respectively:

$R^{2}=1-\frac{\langle(\theta-\mu)^{2}\rangle}{\langle(\theta-\bar{\theta})^{2}\rangle},$
(1) $\text{RMSE}=\sqrt{\langle(\theta-\mu)^{2}\rangle},$ (2)
$\epsilon=\left\langle\frac{\sigma}{\mu}\right\rangle,$ (3)

where the $\mu$, $\sigma$ are the predicted posterior mean and standard
deviation of $\Omega_{\mathrm{m}}$ from the networks, $\theta$ is the true
value of $\Omega_{\mathrm{m}}$, and $\bar{\theta}$ is the average value of
true values. A lower value for the RMSE indicates that the model is more
accurate, and the value of $\epsilon$ is smaller for a more precise model.
Finally, a value of $R^{2}$ closer to 1 indicates a more accurate model.

###  2.4 Void Galaxy Selection

After training the networks, we use the information from both voids and
Voronoi cells inside voids to select void galaxies. As explained in Section
2.2, this combination allows us to jointly account for the large-scale
structure and the local environment, providing a conservative selection of
galaxies in isolated environments. Additionally, we consider purity cuts to
avoid the presence of spurious voids. We note that our results are robust to
variations in the presented cuts. We now provide details on our method to
select void galaxies.

First, considering the void catalogs with no cuts, we begin with the set of
galaxies belonging to VIDE voids. Since VIDE voids will include the overdense
shells constituting the outer regions of voids, we perform a first selection
of galaxies based on the distance from the void center, considering void
galaxies as the ones within 75% of the void radius. The void radius is defined
as $R=\left(\frac{3}{4\pi}V\right)^{1/3}$, where $V$ is the total volume of
the Voronoi cells that the void contains. We note that, albeit this cut is
based on a radius selection, the void center definition depends on the whole
non-spherical shape of the void.

Second, to fully account for void shape for enhanced robustness, we rely on a
criteria that is not based on radius, and utilize the Voronoi cell volume as
an additional property to select void galaxies. Since larger Voronoi cell
volumes correspond to more isolated galaxies, we consider different threshold
values for Voronoi cell volumes to select void galaxies. The comparison of
results with more or less stringent selection based on the Voronoi cell
volumes is particularly instructive as it shows how results vary when
considering more isolated galaxies. We show results with the various Voronoi
cell volume thresholds in Section 3. In the remaining of the paper, we
consider both the above criteria (cuts based on distance from the void center
and on Voronoi cell volume) to separate void galaxies from non-void galaxies.

Finally, we add to the above selection additional purity cuts aimed at an
enhanced robustness to the presence of spurious voids (Neyrinck, 2008; Pisani
et al., 2015b; Cousinou et al., 2019). These purity cuts will aim to reduce
the presence of galaxies belonging to spurious voids. Previous work showed
that spurious voids are more likely to be voids of low size with a shallow
density profile—that is a high density at their core (Cousinou et al., 2019).
Therefore we exclude voids based on the void core density, defined as the
density of the core particle in ZOBOV-normalized units (Neyrinck, 2008; Sutter
et al., 2015), as well as on the void radius. These additional cuts allow to
reduce the impact of spurious voids and provide a cleaner void catalog. We use
each of these cuts to filter out $\sim 50\%$ of the voids from the catalogs.
In Section 3 we show the results obtained when considering only a purity cut
on void core density, and when considering both purity cuts on void core
density and radius. We checked that our results are robust to variations in
the aforementioned cuts.

##  3 Results

Non-void Galaxies Random Galaxies Void Galaxies

Figure 2: $\Omega_{\mathrm{m}}$ predictions using only one galaxy with fully
connected layers. Blue dots and error bars represent the predicted posterior
mean and standard deviation of $\Omega_{\mathrm{m}}$ from the networks. The
orange line in the diagonal indicated the perfect match between predicted and
true values. The left, middle and right columns show the results when using
non-void galaxies, randomly selected galaxies and void galaxies respectively;
therefore moving from left to right shows the change when considering the
large-scale environment. For the right column, the top row shows the results
after selecting void galaxies with a cut-off value of Voronoi cell volume at
100, while the bottom row shows a more restrictive Voronoi cell volume cut
(150), corresponding to more isolated galaxies and accounting for the local
environment. These results correspond to the void catalog considering the
purity cut on core density. For better visual comparison, in the case of non-
void and randomly selected galaxies we sub-sample the number of points to the
same number of data points shown in the plot for void galaxies. The $R^{2}$
and RMSE values improve for void galaxies (from left to right), and further
improve if we consider more isolated galaxies among the void galaxies (from
top to bottom, right column).

Non-void Galaxies Random Galaxies Void Galaxies

Figure 3: Similar to Figure 2 with the additional radius cut applied for
purity to the void catalog. Here, $R^{2}$, RMSE and $\epsilon$ values all
improve for void galaxies (from left to right, accounting for the large-scale
environment), and further improve when considering more isolated galaxies
among void galaxies, that is considering the local environment (right column,
from top to bottom). The strongest improvement is obtained when accounting for
selections on both the large-scale and local environments (right column,
bottom plot).

Non-void Galaxies Random Galaxies Void Galaxies

Figure 4: The top row shows the average prediction of $\Omega_{\mathrm{m}}$
using galaxies in the same simulation. The bottom row shows a zoom in on the
lower values of $\Omega_{\mathrm{m}}$. The figure shows an improvement
especially on the lower values of $\Omega_{\mathrm{m}}$ when using void
galaxies, that have smaller errorbars (the values of $\epsilon$ highlight the
improvement).

In this Section, we use the same trained machine learning model as in
Villaescusa-Navarro et al. (2022), which takes galaxy properties as inputs and
predicts the value of $\Omega_{\mathrm{m}}$ with fully connected layers. As
described in Section 2.4, we have selected galaxies as void, non-void and
randomly selected galaxies. We show the prediction of $\Omega_{\mathrm{m}}$
using these three types of galaxies. To investigate the impact of the galaxy
environment on cosmological constraints, we consider galaxies at different
level of isolation. This is done by considering two void galaxy selections
determined by different cut-off values of the Voronoi cell volume, hence
increasing how restrictive the selection is. In particular, we consider as
void galaxies the galaxies that have Voronoi cell volumes larger than 100 and
150 (see Figure 1 for the overall range of volume values), with 150 being the
most restrictive value, since a higher volume corresponds to more isolated
galaxies, and show results for both cases.

Additionally, for the purity cuts at the level of the void catalog we show
results after considering only the core density cut (Section 3.1), or both the
core density cut and radius cut (Section 3.2). The results show the
progressive improvement in constraints on $\Omega_{\mathrm{m}}$ with those
cuts, indicating that a more restrictive void galaxy selection leads to better
$\Omega_{\mathrm{m}}$ predictions. In Section 3.3, we show and discuss the
average predictions of void, non-void and randomly selected galaxies in the
same simulation.

###  3.1 Core Density Cut

In this Section, we only apply the core density cut to the void catalog.
Figure 2 shows our results. Similar to Villaescusa-Navarro et al. (2022), the
blue dots and error bars in Figures 2 and 3 represent the predicted posterior
mean and standard deviation of $\Omega_{\mathrm{m}}$ from the networks. The
orange diagonal line corresponds to the case in which the predicted values
perfectly match the true values. The top left corners of each plot provide the
values of accuracy and precision metrics. On the bottom right corners, we
indicate the percentages of galaxies considered in the plots. Noticeably, for
visualization purposes, in the case of non-void and randomly selected
galaxies, we sub-sample the number of points to the same number of data points
shown in the plot for void galaxies, allowing a better visual comparison. The
metrics are, however, calculated over all the galaxies within each category.
The left, middle, and right columns show the results of using non-void
galaxies, randomly selected galaxies and void galaxies respectively.
Therefore, moving from left to right shows the change when considering the
large-scale environment. The first row in Figure 2 shows the results when
using different types of galaxies to predict the values of
$\Omega_{\mathrm{m}}$ with a less constrained (smaller) cell volume. From left
to right in the row we can see that the result of using void galaxies is
generally closer to the reference diagonal line, indicating that using void
galaxies we can constrain $\Omega_{\mathrm{m}}$ better than when using non-
void galaxies and randomly selected galaxies. The $R^{2}$ and RMSE values
significantly improve when using void galaxies.

The second row, right column, shows the results when being more restrictive in
terms of local environment, that is after selecting void galaxies based on a
more stringent Voronoi cell volume cut (larger cut, since a larger Voronoi
cell volume corresponds to a more underdense environment). The improvements
seen in the first row from left to right are even more evident in the right
plot of the second row—confirming that more isolated void galaxies provide
better constraints.

This is consistent with the idea that, to guarantee an isolated environment,
void galaxies need to be identified accounting for both the large-scale
environment (accounted for when going from left to right in Figure 2) and the
local environment (introduced when going from top to bottom in the right
column of Figure 2). We note that in the bottom row, the data points in the
figure might be visually less representative for the non-void and random
galaxies cases, since for representation purposes we have sub-sampled the
points in those cases to show the same number of points as for the void
galaxies’ case. We note that in the bottom row the value of $\epsilon$ is not
enhanced for void galaxies compared to randomly selected galaxies. This could
be due to the smaller error bars and much lower number of data points in the
case of more isolated galaxies (bottom row). The next Section shows results
when considering both criteria to increase purity (core density cut and radius
cut).

###  3.2 Core Density Cut and Radius Cut

To further reduce the number of spurious voids in the void catalog, in this
Section, we remove voids also based on the radius cut (besides the core
density cut). Similar to Section 3.1, Figure 3 shows the results of non-void
galaxies, random galaxies and void galaxies to infer the values of
$\Omega_{\mathrm{m}}$. The values of $R^{2}$ and RMSE have a stronger
improvement after this additional purity cut on void radius is applied,
showing an even higher constraining power of void galaxies. In addition, in
this case, we see that the $\epsilon$ value also improves when considering
more isolated galaxies (bottom row, right plot). Therefore, when both criteria
for purity are considered (core density cut and void radius), $\epsilon$
improves both when we select void galaxies instead of non-void or randomly
selected galaxies (moving from the left and center panels to the right panels)
and when we increase the Voronoi cell cut-off volume (from up to bottom panel
for void galaxies). By comparing Figure 2 and Figure 3, we conjecture that,
since the radius cut removes outlier

galaxies with large error bars, it may be responsible for this improvement. If
this is the case, the smaller error bars would be the reason for a smaller
$\epsilon$ value. As in the case with only the core density cut, the strongest
improvement in constraints is obtained when accounting for selections on both
the large-scale and local environments (right column, bottom plot). Therefore,
the results of this Section confirm that when using a galaxy from a cosmic
void we obtain more stringent constraints.

###  3.3 Test on the mean values of predictions with galaxies from the same
simulation

In Villaescusa-Navarro et al. (2022), the authors show the average prediction
of galaxies in the same simulation. Here, to investigate the constraining
capabilities on average of the different kinds of galaxies separately we show
the average predictions of void, non-void and randomly selected galaxies from
the same simulation (see the top row in Figure 4). We note that we perform
this binning only for the case in which both purity cuts are applied (radius
and core density). In this case, we see a milder improvement when using void
galaxies, with the value of $\epsilon$ being slightly boosted. If, however, we
zoom in to the lower value of $\Omega_{\mathrm{m}}$ as shown in the second row
of Figure 4, we notice that the error bars on the lower values of
$\Omega_{\mathrm{m}}$ are much smaller when considering void galaxies (seeing
an improvement in the bottom row from left to right), corresponding to a
further improvement of the $\epsilon$ values. This shows that void galaxies
seem to particularly provide better constraints for the lower values of
$\Omega_{\mathrm{m}}$, roughly between 0.1 and 0.2. Yet, we notice that there
are some biases for the lower values of $\Omega_{\mathrm{m}}$, as well as
closer to the higher extreme values of $\Omega_{\mathrm{m}}$.

Furthermore, in Figure 5 we plot the error bars of the predictions as a
function of the Voronoi cell volume of the galaxies (considering galaxies
within 75% of the void radius from void centers as above). A correlation is
present: we notice that the error bars of the predictions (x-axis) are smaller
for galaxies with larger Voronoi cell volume (y-axis)—indicating that more
isolated void galaxies are more constraining. This provides additional
evidence that galaxies in underdense regions are better for predicting
$\Omega_{\mathrm{m}}$.

Figure 5: The relationship between the size of error bars from the predictions
and the Voronoi cell volume of the galaxies inside voids. We bin the galaxies
in each range of error bars and calculate the average Voronoi cell volume of
the galaxies in each bin. The error bars are calculated as the standard
errors, which consider both the standard deviation and the sample size. The
slope of the curve shows that the error bars of the predictions (on the
x-axis) are smaller for galaxies with larger Voronoi cell volume (on the
y-axis), that is showing that more isolated void galaxies provide more
stringent constraints.

##  4 Conclusion

In this work, we have shown that the correlation between $\Omega_{\rm m}$ and
galaxy properties exhibit less scatter for void galaxies than for non-voids
galaxies. This is an important and new result that may shed light on the
impact of baryonic processes on galaxy formation and evolution as a function
of the cosmic environment. Recent works showing that void galaxies have
distinct characteristics in the IllustrisTNG simulation (Rodríguez-Medrano et
al., 2023a; Curtis et al., 2024) could hint to an explanation for our results.
We also show that the improvement obtained when using void galaxies is more
significant when a more stringent selection is considered, robustly selecting
according to both the large-scale and local environments. This improvement,
seen when more conservatively selecting void galaxies, seems to confirm the
physical expectation that void galaxies provide a cleaner environment to
extract cosmological information. Additionally, we notice that the
constraining power of void galaxies seems higher in the case of lower values
of $\Omega_{\mathrm{m}}$, a result that requires further investigation and
paves the way to future studies on the topic.

Our results imply that, if we consider void galaxies, we can obtain similar
accuracy and precision for cosmological inference as when using non-void or
randomly selected galaxies, but with much less data. It also shows that, for
an equal number of galaxies selected, the constraining power obtained by
galaxies in voids is stronger than the one obtained when using random
galaxies. The implications of our results therefore favor the interpretation
that void galaxies provide a cleaner and more effective environment for
extracting cosmological information. These results should be further tested on
different simulations, such as ASTRID and SIMBA. Looking ahead to applications
to data, it would be interesting to investigate whether these results are
expected to hold with observational data from e.g. photometric surveys (see
Hahn et al., 2023). We notice that, with respect to observation strategies,
there is a trade-off between using all available galaxies versus restricting
to void galaxies: while void galaxies yield better constraints, they are
scarcer. For better constraints, the strategy could directly aim at targeting
void galaxies. Finally, our results may, in the longer term, motivate future
observation campaigns to observe sky patches in underdense regions in order to
extract cosmological information.

##  5 Acknowledgments

We are especially grateful to Francisco Villaescusa-Navarro, whose invaluable
help and support were pivotal to the completion of this paper. We also thank
Wenhan Zhou, Tri Nguyen, Eiichiro Komatsu, Leander Thiele, ChangHoon Hahn, and
Sohaib Bhatti for valuable discussions. BW and AP acknowledge support from the
Simons Foundation to the Center for Computational Astrophysics at the Flatiron
Institute. AP acknowledges support from the European Research Council (ERC)
under the European Union’s Horizon programme (COSMOBEST ERC funded project,
grant agreement 101078174).

## References

  * Akiba et al. (2019) Akiba, T., Sano, S., Yanase, T., Ohta, T., & Koyama, M. 2019, arXiv e-prints, arXiv:1907.10902.  https://arxiv.org/abs/1907.10902
  * Allen et al. (2011) Allen, S. W., Evrard, A. E., & Mantz, A. B. 2011, ARA&A, 49, 409, doi: 10.1146/annurev-astro-081710-102514
  * Astier et al. (2006) Astier, P., Guy, J., Regnault, N., et al. 2006, A&A, 447, 31, doi: 10.1051/0004-6361:20054185
  * Baldi & Villaescusa-Navarro (2016) Baldi, M., & Villaescusa-Navarro, F. 2016, arXiv e-prints, arXiv:1608.08057.  https://arxiv.org/abs/1608.08057
  * Betoule et al. (2014) Betoule, M., Kessler, R., Guy, J., et al. 2014, A&A, 568, A22, doi: 10.1051/0004-6361/201423413
  * Beygu et al. (2017) Beygu, B., Peletier, R. F., van der Hulst, J. M., et al. 2017, MNRAS, 464, 666, doi: 10.1093/mnras/stw2362
  * Bird et al. (2022) Bird, S., Ni, Y., Di Matteo, T., et al. 2022, MNRAS, 512, 3703, doi: 10.1093/mnras/stac648
  * Biswas et al. (2010) Biswas, R., Alizadeh, E., & Wandelt, B. D. 2010, Phys. Rev. D, 82, 023002, doi: 10.1103/PhysRevD.82.023002
  * Branch (1998) Branch, D. 1998, ARA&A, 36, 17, doi: 10.1146/annurev.astro.36.1.17
  * Chawak et al. (2023) Chawak, C., Villaescusa-Navarro, F., Echeverri Rojas, N., et al. 2023, arXiv e-prints, arXiv:2309.12048, doi: 10.48550/arXiv.2309.12048
  * Contarini et al. (2022a) Contarini, S., Pisani, A., Hamaus, N., et al. 2022a, arXiv e-prints, arXiv:2212.03873.  https://arxiv.org/abs/2212.03873
  * Contarini et al. (2022b) Contarini, S., Verza, G., Pisani, A., et al. 2022b, arXiv e-prints, arXiv:2205.11525.  https://arxiv.org/abs/2205.11525
  * Cousinou et al. (2019) Cousinou, M. C., Pisani, A., Tilquin, A., et al. 2019, Astronomy and Computing, 27, 53, doi: 10.1016/j.ascom.2019.03.001
  * Croton et al. (2005) Croton, D. J., Farrar, G. R., Norberg, P., et al. 2005, MNRAS, 356, 1155, doi: 10.1111/j.1365-2966.2004.08546.x
  * Curtis et al. (2024) Curtis, O., McDonough, B., & Brainerd, T. G. 2024, arXiv e-prints, arXiv:2401.02322, doi: 10.48550/arXiv.2401.02322
  * Davé et al. (2019) Davé, R., Anglés-Alcázar, D., Narayanan, D., et al. 2019, MNRAS, 486, 2827, doi: 10.1093/mnras/stz937
  * DESI Collaboration et al. (2024) DESI Collaboration, Adame, A. G., Aguilar, J., et al. 2024, arXiv e-prints, arXiv:2404.03002, doi: 10.48550/arXiv.2404.03002
  * Dolag (2015) Dolag, K. 2015, in IAU General Assembly, Vol. 29, 2250156
  * Domínguez-Gómez et al. (2023) Domínguez-Gómez, J., Pérez, I., Ruiz-Lara, T., et al. 2023, Nature, 619, 269, doi: 10.1038/s41586-023-06109-1
  * Douglass et al. (2022) Douglass, K. A., Veyrat, D., & BenZvi, S. 2022, arXiv e-prints, arXiv:2202.01226.  https://arxiv.org/abs/2202.01226
  * Douglass et al. (2018) Douglass, K. A., Vogeley, M. S., & Cen, R. 2018, ApJ, 864, 144, doi: 10.3847/1538-4357/aad86e
  * Echeverri-Rojas et al. (2023) Echeverri-Rojas, N., Villaescusa-Navarro, F., Chawak, C., et al. 2023, ApJ, 954, 125, doi: 10.3847/1538-4357/ace96e
  * Eisenstein et al. (2005) Eisenstein, D. J., Zehavi, I., Hogg, D. W., et al. 2005, ApJ, 633, 560, doi: 10.1086/466512
  * Florez et al. (2021) Florez, J., Berlind, A. A., Kannappan, S. J., et al. 2021, ApJ, 906, 97, doi: 10.3847/1538-4357/abca9f
  * Grogin & Geller (1999) Grogin, N. A., & Geller, M. J. 1999, The Astronomical Journal, 118, 2561, doi: 10.1086/301126
  * Habouzit et al. (2020) Habouzit, M., Pisani, A., Goulding, A., et al. 2020, MNRAS, 493, 899, doi: 10.1093/mnras/staa219
  * Hahn et al. (2023) Hahn, C., Melchior, P. M., Villaescusa-Navarro, F., & Teyssier, R. 2023, in Machine Learning for Astrophysics, 14, doi: 10.48550/arXiv.2310.08634
  * Hamaus et al. (2017) Hamaus, N., Cousinou, M.-C., Pisani, A., et al. 2017, J. Cosmology Astropart. Phys, 2017, 014, doi: 10.1088/1475-7516/2017/07/014
  * Hamaus et al. (2020) Hamaus, N., Pisani, A., Choi, J.-A., et al. 2020, J. Cosmology Astropart. Phys, 2020, 023, doi: 10.1088/1475-7516/2020/12/023
  * Hamaus et al. (2016) Hamaus, N., Pisani, A., Sutter, P. M., et al. 2016, Phys. Rev. Lett., 117, 091302, doi: 10.1103/PhysRevLett.117.091302
  * Hamaus et al. (2015) Hamaus, N., Sutter, P. M., Lavaux, G., & Wandelt, B. D. 2015, J. Cosmology Astropart. Phys, 2015, 036, doi: 10.1088/1475-7516/2015/11/036
  * Hamaus et al. (2022) Hamaus, N., Aubert, M., Pisani, A., et al. 2022, A&A, 658, A20, doi: 10.1051/0004-6361/202142073
  * Hoyle et al. (2005) Hoyle, F., Rojas, R. R., Vogeley, M. S., & Brinkmann, J. 2005, The Astrophysical Journal, 620, 618, doi: 10.1086/427176
  * Hu & Dodelson (2002) Hu, W., & Dodelson, S. 2002, ARA&A, 40, 171, doi: 10.1146/annurev.astro.40.060401.093926
  * Jaber et al. (2024) Jaber, M., Peper, M., Hellwing, W. A., Aragón-Calvo, M. A., & Valenzuela, O. 2024, MNRAS, 527, 4087, doi: 10.1093/mnras/stad3347
  * Jung et al. (2014) Jung, I., Lee, J., & Yi, S. K. 2014, The Astrophysical Journal, 794, 74, doi: 10.1088/0004-637X/794/1/74
  * Kreckel et al. (2012) Kreckel, K., Platen, E., Aragón-Calvo, M. A., et al. 2012, AJ, 144, 16, doi: 10.1088/0004-6256/144/1/16
  * Kreckel et al. (2011) —. 2011, AJ, 141, 4, doi: 10.1088/0004-6256/141/1/4
  * Kreisch et al. (2021) Kreisch, C. D., Pisani, A., Villaescusa-Navarro, F., et al. 2021, arXiv e-prints, arXiv:2107.02304.  https://arxiv.org/abs/2107.02304
  * Kurapati et al. (2024) Kurapati, S., Kraan-Korteweg, R. C., Pisano, D. J., et al. 2024, MNRAS, 528, 542, doi: 10.1093/mnras/stad3823
  * Lavaux & Wandelt (2010) Lavaux, G., & Wandelt, B. D. 2010, MNRAS, 403, 1392, doi: 10.1111/j.1365-2966.2010.16197.x
  * Lavaux & Wandelt (2012) —. 2012, ApJ, 754, 109, doi: 10.1088/0004-637X/754/2/109
  * Marinacci et al. (2018) Marinacci, F., Vogelsberger, M., Pakmor, R., et al. 2018, MNRAS, 480, 5113, doi: 10.1093/mnras/sty2206
  * Moorman et al. (2015) Moorman, C. M., Vogeley, M. S., Hoyle, F., et al. 2015, The Astrophysical Journal, 810, 108, doi: 10.1088/0004-637X/810/2/108
  * Moresco et al. (2022) Moresco, M., Amati, L., Amendola, L., et al. 2022, Living Reviews in Relativity, 25, 6, doi: 10.1007/s41114-022-00040-z
  * Naiman et al. (2018) Naiman, J. P., Pillepich, A., Springel, V., et al. 2018, MNRAS, 477, 1206, doi: 10.1093/mnras/sty618
  * Nelson et al. (2019) Nelson, D., Springel, V., Pillepich, A., et al. 2019, Computational Astrophysics and Cosmology, 6, 2, doi: 10.1186/s40668-019-0028-x
  * Neyrinck (2008) Neyrinck, M. C. 2008, MNRAS, 386, 2101, doi: 10.1111/j.1365-2966.2008.13180.x
  * Ni et al. (2022) Ni, Y., Di Matteo, T., Bird, S., et al. 2022, MNRAS, 513, 670, doi: 10.1093/mnras/stac351
  * Ni et al. (2023) Ni, Y., Genel, S., Anglés-Alcázar, D., et al. 2023, ApJ, 959, 136, doi: 10.3847/1538-4357/ad022a
  * Panchal et al. (2020) Panchal, R. R., Pisani, A., & Spergel, D. N. 2020, ApJ, 901, 87, doi: 10.3847/1538-4357/abadff
  * Pandey et al. (2021) Pandey, D., Saha, K., & Pradhan, A. C. 2021, ApJ, 919, 101, doi: 10.3847/1538-4357/ac1078
  * Park & Lee (2007) Park, D., & Lee, J. 2007, Phys. Rev. Lett., 98, 081301, doi: 10.1103/PhysRevLett.98.081301
  * Peebles (2001) Peebles, P. J. E. 2001, ApJ, 557, 495, doi: 10.1086/322254
  * Pelliciari et al. (2022) Pelliciari, D., Contarini, S., Marulli, F., et al. 2022, arXiv e-prints, arXiv:2210.07248.  https://arxiv.org/abs/2210.07248
  * Perlmutter et al. (1997) Perlmutter, S., Aldering, G., Deustua, S., et al. 1997, in American Astronomical Society Meeting Abstracts, Vol. 191, American Astronomical Society Meeting Abstracts, 85.04, doi: 10.48550/arXiv.astro-ph/9812473
  * Perlmutter et al. (1999) Perlmutter, S., Aldering, G., Goldhaber, G., et al. 1999, ApJ, 517, 565, doi: 10.1086/307221
  * Phillips (1993) Phillips, M. M. 1993, ApJ, 413, L105, doi: 10.1086/186970
  * Pisani et al. (2015a) Pisani, A., Sutter, P. M., Hamaus, N., et al. 2015a, Phys. Rev. D, 92, 083531, doi: 10.1103/PhysRevD.92.083531
  * Pisani et al. (2015b) Pisani, A., Sutter, P. M., & Wandelt, B. D. 2015b, arXiv e-prints, arXiv:1506.07982, doi: 10.48550/arXiv.1506.07982
  * Pisani et al. (2019) Pisani, A., Massara, E., Spergel, D. N., et al. 2019, BAAS, 51, 40, doi: 10.48550/arXiv.1903.05161
  * Planck Collaboration et al. (2020) Planck Collaboration, Aghanim, N., Akrami, Y., et al. 2020, A&A, 641, A6, doi: 10.1051/0004-6361/201833910
  * Pustilnik et al. (2022) Pustilnik, S. A., Perepelitsyna, Y., Tepliakova, A., et al. 2022, in The Multifaceted Universe: Theory and Observations - 2000, 26, doi: 10.48550/arXiv.2212.05640
  * Pustilnik et al. (2019) Pustilnik, S. A., Tepliakova, A. L., & Makarov, D. I. 2019, MNRAS, 482, 4329, doi: 10.1093/mnras/sty2947
  * Riess et al. (1998) Riess, A. G., Filippenko, A. V., Challis, P., et al. 1998, AJ, 116, 1009, doi: 10.1086/300499
  * Rodríguez-Medrano et al. (2023a) Rodríguez-Medrano, A., Springel, V., Stasyszyn, F., & Paz, D. 2023a, arXiv e-prints, arXiv:2312.09297.  https://arxiv.org/abs/2312.09297
  * Rodríguez-Medrano et al. (2023b) Rodríguez-Medrano, A. M., Paz, D. J., Stasyszyn, F. A., et al. 2023b, MNRAS, 521, 916, doi: 10.1093/mnras/stad623
  * Rodríguez Medrano et al. (2022) Rodríguez Medrano, A. M., Paz, D. J., Stasyszyn, F. A., & Ruiz, A. N. 2022, MNRAS, 511, 2688, doi: 10.1093/mnras/stac127
  * Rojas et al. (2004) Rojas, R. R., Vogeley, M. S., Hoyle, F., & Brinkmann, J. 2004, The Astrophysical Journal, 617, 50, doi: 10.1086/425225
  * Rosas-Guevara et al. (2022) Rosas-Guevara, Y., Tissera, P., Lagos, C. d. P., Paillas, E., & Padilla, N. 2022, MNRAS, 517, 712, doi: 10.1093/mnras/stac2583
  * Schuster et al. (2023) Schuster, N., Hamaus, N., Dolag, K., & Weller, J. 2023, J. Cosmology Astropart. Phys, 2023, 031, doi: 10.1088/1475-7516/2023/05/031
  * Spergel et al. (2003) Spergel, D. N., Verde, L., Peiris, H. V., et al. 2003, ApJS, 148, 175, doi: 10.1086/377226
  * Spergel et al. (2007) Spergel, D. N., Bean, R., Doré, O., et al. 2007, ApJS, 170, 377, doi: 10.1086/513700
  * Springel et al. (2018) Springel, V., Pakmor, R., Pillepich, A., et al. 2018, MNRAS, 475, 676, doi: 10.1093/mnras/stx3304
  * Stopyra et al. (2021) Stopyra, S., Peiris, H. V., & Pontzen, A. 2021, MNRAS, 500, 4173, doi: 10.1093/mnras/staa3587
  * Sutter et al. (2015) Sutter, P. M., Lavaux, G., Hamaus, N., et al. 2015, Astronomy and Computing, 9, 1, doi: 10.1016/j.ascom.2014.10.002
  * Tonry et al. (2003) Tonry, J. L., Schmidt, B. P., Barris, B., et al. 2003, ApJ, 594, 1, doi: 10.1086/376865
  * Verza et al. (2019) Verza, G., Pisani, A., Carbone, C., Hamaus, N., & Guzzo, L. 2019, J. Cosmology Astropart. Phys, 2019, 040, doi: 10.1088/1475-7516/2019/12/040
  * Vikhlinin et al. (2009) Vikhlinin, A., Kravtsov, A. V., Burenin, R. A., et al. 2009, ApJ, 692, 1060, doi: 10.1088/0004-637X/692/2/1060
  * Villaescusa-Navarro et al. (2021) Villaescusa-Navarro, F., Anglés-Alcázar, D., Genel, S., et al. 2021, ApJ, 915, 71, doi: 10.3847/1538-4357/abf7ba
  * Villaescusa-Navarro et al. (2022) Villaescusa-Navarro, F., Ding, J., Genel, S., et al. 2022, ApJ, 929, 132, doi: 10.3847/1538-4357/ac5d3f
  * Wang et al. (2023) Wang, B. Y., Pisani, A., Villaescusa-Navarro, F., & Wandelt, B. D. 2023, ApJ, 955, 131, doi: 10.3847/1538-4357/aceaf6
  * Weinberger et al. (2020) Weinberger, R., Springel, V., & Pakmor, R. 2020, ApJS, 248, 32, doi: 10.3847/1538-4365/ab908c
  * Zaidouni et al. (2024) Zaidouni, F., Veyrat, D., Douglass, K. A., & BenZvi, S. 2024, arXiv e-prints, arXiv:2403.20008, doi: 10.48550/arXiv.2403.20008


# All Random Features Representations are Equivalent

Luke Sernau
Google DeepMind
<EMAIL_ADDRESS>
&Silvano Bonacina
Google DeepMind
<EMAIL_ADDRESS>
&Rif A. Saurous
Google Research
<EMAIL_ADDRESS>

###### Abstract

Random features are an important technique that make it possible to rewrite
positive-definite kernels as infinite-dimensional dot products. Over time,
increasingly elaborate random feature representations have been developed in
pursuit of finite approximations with ever lower error. We resolve this arms
race by deriving an optimal sampling policy, and show that under this policy
all random features representations have the same approximation error. This
establishes a lower bound that holds across all random feature
representations, and shows that we are free to choose whatever representation
we please, provided we sample optimally.

##  1 Introduction

Kernel methods have a long and illustrious history in machine learning [1].
Nowadays one of their most widespread applications is the softmax kernel
inside the attention layers of a transformer. Unfortunately, kernel methods
scale linearly in the size of the dataset, which is impractical for very large
datasets.

In their seminal paper, Rahimi and Recht [2] show that this linear cost can be
avoided in kernel machines by replacing the kernel with a randomized
approximation that is correct in expectation. They did this by means of a
_random feature representation_.

######  Definition 1.

Given a positive-definite kernel $K:X\times X\rightarrow\mathbb{R}$, a _random
feature representation_ of $K$ is a symmetric function $\phi:X\times
X\rightarrow\mathbb{R}$ together with a distribution $\Omega$ (most commonly
the normal distribution) such that

$K\left(x_{1},x_{2}\right)=\mathop{\mathbb{E}}_{\omega\sim\Omega}\left[\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right].$
(1)

To see why this is useful, consider a simple kernel estimator over some
dataset $\\{(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{n},y_{n})\\}$.

$KE\left(x\right)=\sum^{n}_{i=1}K\left(x,x_{i}\right)y_{i}.$

As written, this kernel estimator requires linear time, since for every new
$x$ it’s necessary to compute a dot product with every element in the dataset.
But if the kernel admits a random features representation, we may write

$\displaystyle KE\left(x\right)$
$\displaystyle=\sum^{n}_{i=1}\mathop{\mathbb{E}}_{\omega\sim\Omega}\left[\phi(x,\omega)\phi(x_{i},\omega)\right]y_{i}$
$\displaystyle=\mathop{\mathbb{E}}_{\omega\sim\Omega}\left[\phi(x,\omega)\sum^{n}_{i=1}\phi(x_{i},\omega)y_{i}\right].$

This expectation can be approximated via sampling,

$KE\left(x\right)\approx\frac{1}{k}\sum^{k}_{j=1}\phi(x,\omega_{j})\sum^{n}_{i=1}\phi(x_{i},\omega_{j})y_{i},$

where $\omega_{1},\omega_{2},\dots,\omega_{k}$ are samples drawn from
$\Omega$. As long as $k$ is less than $n$, we can save time by precomputing
the sum on the right.

Choromanski et al. [3] were the first to apply this idea to attention. They
did so by finding a choice of $\phi$ that was numerically stable and had low
sample variance. This kicked off a flurry of research ([4] [5] [6]) into
better choices of $\phi$ with ever lower sample variance.

We provide a possible resolution to this competition. Rather than optimizing
$\phi$, we simply chose our sampling strategy carefully. By approximating the
expectation using an optimal importance sampling strategy, we are able to
achieve a sample variance that is in a sense as low as possible. What’s more,
this sample variance _does not depend on $\phi$_, meaning that when sampled
optimally, _all_ random features schemes have the same variance.

Ours is not the first scheme to consider importance sampling, but in contrast
to others that sample based on kernel polarization heuristics [7] or
quadrature rules [8], we directly solve the variance minimization problem. To
our knowledge we are the first to obtain global optima that are independent of
the choice of $\phi$.

##  2 Importance sampling

Importance sampling [9] is a well known technique for reducing variance when
estimating an expectation via sampling. It’s based on the observation that
some samples have a larger effect on the expectation than others, and we
should prefer to sample those. It achieves this by sampling from some new
distribution $\Psi$, and then rescaling the samples such that the correct
final estimate is preserved.

In our case, we wish to estimate (1) via sampling. Let $\Psi$ be some new
distribution with the same support as $\Omega$, and suppose $\Psi$ and
$\Omega$ have densities $p_{\Psi}$ and $p_{\Omega}$, respectively. Observe
that

$\displaystyle K\left(x_{1},x_{2}\right)$
$\displaystyle=\mathop{\mathbb{E}}_{\omega\sim\Omega}\left[\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\omega\sim\Psi}\left[\frac{p_{\Omega}\left(\omega\right)}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right].$
(2)

In other words, we are free to sample from $\Psi$ without changing the value
of the expectation. On the other hand, the sample variance, given by

$\mathop{\text{Var}}_{\omega\sim\Psi}\left[\frac{p_{\Omega}\left(\omega\right)}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right],$

does depend on $\Psi$. All we need to do is find a choice of $\Psi$ to make
this quantity small.

##  3 Optimal sampling

We are left with the question of how to choose an optimal $\Psi$. This is an
intrinsically data-driven question, as the variance depends on the input. We’d
like to minimize the sample variance for all inputs.

######  Definition 2.

Suppose $x_{1}$ and $x_{2}$ are sampled from $\mathcal{X}_{1}$ and
$\mathcal{X}_{2}$, respectively. If we approximate the expression in (2) by
sampling from $\Psi$, the _expected sample variance_ $\mathcal{V}_{\Psi}$ over
all $x_{1}$ and $x_{2}$ is given by

$\mathcal{V}_{\Psi}=\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\mathop{\text{Var}}_{\omega\sim\Psi}\left[\frac{p_{\Omega}\left(\omega\right)}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right]$

The $\Psi$ that minimizes $\mathcal{V}_{\Psi}$ can be found analytically.

######  Theorem 1.

Let $K$ be a positive-definite kernel such that

$K\left(x_{1},x_{2}\right)=\mathop{\mathbb{E}}_{\omega\sim\Psi}\left[\frac{p_{\Omega}\left(\omega\right)}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right]$

for some $\phi$ and $\Omega$, and every $\Psi$ with the same support as
$\Omega$. Suppose $x_{1}$ and $x_{2}$ are sampled from $\mathcal{X}_{1}$ and
$\mathcal{X}_{2}$, respectively. Then the expected sample variance
$\mathcal{V}_{\Psi}$ over all $x_{1}$ and $x_{2}$ will be minimized when

$p_{\Psi}(w)\propto p_{\Omega}(w)q_{\phi}\left(\omega\right),$

where

$q_{\phi}\left(\omega\right)=\sqrt{\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\left[\phi\left(x_{1},\omega\right)^{2}\right]\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\left[\phi\left(x_{2},\omega\right)^{2}\right]}.$

The resulting optimal variance will be

$\mathcal{\hat{V}}_{\Psi}=\left(\mathop{\mathbb{E}}_{\omega\sim\Psi}q_{\phi}\left(\omega\right)\right)^{2}-\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}K\left(x_{1},x_{2}\right)^{2}.$

This result tells us how to minimize the variance for a particular choice of
$\phi$. What is less clear in this form is that it also tells us something
about optimizing over every $\phi$. We will explore this in the next section.

The proof of Theorem 1 is a straightforward exercise in Lagrange optimization
and can be found in the appendix.

##  4 The choice of feature representation does not matter

As written, Theorem 1 appears to be a statement about how to get the most out
of any particular choice of $\phi$. In this section, we’ll show some
corollaries that turn this on its head: the optimal sample variance is largely
independent of $\phi$.

######  Corrolary 1.

The optimal sample variance achieved in Theorem 1 is upper bounded by

$\mathcal{\hat{V}}_{\Psi}\leq\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\left[K\left(x_{1},x_{1}\right)K\left(x_{2},x_{2}\right)-K\left(x_{1},x_{2}\right)^{2}\right].$

This follows from Theorem 1 by applying Jensen’s inequality to the first term
of $\mathcal{\hat{V}}_{\Psi}$, and observing that
$\mathop{\mathbb{E}}_{\omega\sim\Psi}q_{\phi}\left(\omega\right)^{2}=\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\left[K\left(x_{1},x_{1}\right)K\left(x_{2},x_{2}\right)\right]$.

Written this way, our bound is suggestively similar to the Cauchy-Schwarz
inequality. Indeed, since positive-definite kernels obey the Cauchy-Schwarz
inequality, we know that this expression is positive as expected. More
interestingly, since this expression does not depend on $\phi$, this bound is
the same regardless of which representation we’re using.

In the (relatively common) case where $\mathcal{X}_{1}=\mathcal{X}_{2}$, we
can go even further.

######  Corrolary 2.

If $\mathcal{X}_{1}=\mathcal{X}_{2}$ then the optimal sample variance achieved
in Theorem 1 is exactly

$\mathcal{\hat{V}}_{\Psi}=\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\left[K\left(x_{1},x_{1}\right)^{2}-K\left(x_{1},x_{2}\right)^{2}\right].$

This can be seen from Theorem 1 since in this case
$q_{\theta}\left(\omega\right)=\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\left[\phi\left(x_{1},\omega\right)^{2}\right]$.
It follows that
$\mathop{\mathbb{E}}_{\omega\sim\Psi}q_{\phi}\left(\omega\right)=\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\left[K\left(x_{1},x_{1}\right)\right]$,
by exchanging the expectations.

We are able to write down the exact sample variance without any reference to
$\phi$. When it comes to optimizing the sample variance, it _does not matter_
which $\phi$ you choose.

##  5 Practical Considerations and Future Work

While the sampling procedure outlined here is of theoretical interest, it
remains to be seen whether it is tractable to compute in practice. As this is
intended as a theory paper, we leave empirical tests to future
experimentalists. Nonetheless, we’ll make a few notes about how to do this
practically.

First, sophisticated MCMC samplers [10] are now quite effective, and widely
available in machine learning plaforms like TensorFlow and Jax [11].

Second, if this technique is used for self attention (as in [3]) it’s likely
unnecessary to resample in every training step. By sampling less frequently,
we can amortize the cost of the sampling procedure.

Finally, and perhaps most intriguingly for the theorists, $p_{\Psi}$ is very
closely related to $p_{\Omega}$. It may be that there exists a convenient
function $f$ such that for $\omega\sim\Omega$ we have
$f\left(\omega\right)\sim\Psi$. The form of $p_{\Psi}$ is very structured,
suggesting that there is room for manipulation.

## References

  * Campbell [2002] Colin Campbell.  Kernel methods: a survey of current techniques.  _Neurocomputing_ , 48(1):63–84, 2002.  ISSN 0925-2312.  doi: https://doi.org/10.1016/S0925-2312(01)00643-9.  URL https://www.sciencedirect.com/science/article/pii/S0925231201006439.
  * Rahimi and Recht [2007] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2007.  URL https://proceedings.neurips.cc/paper_files/paper/2007/file/013a006f03dbc5392effeb8f18fda755-Paper.pdf.
  * Choromanski et al. [2021] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller.  Rethinking attention with performers.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=Ua6zuk0WRH.
  * Likhosherstov et al. [2022] Valerii Likhosherstov, Krzysztof Choromanski, Kumar Avinava Dubey, Frederick Liu, Tamás Sarlós, and Adrian Weller.  Chefs’ random tables: Non-trigonometric random features.  _Neural Information Processing Systems_ , abs/2205.15317, 2022.  URL https://api.semanticscholar.org/CorpusID:249210161.
  * Likhosherstov et al. [2023] Valerii Likhosherstov, Krzysztof Choromanski, Avinava Dubey, Frederick Liu, Tamas Sarlos, and Adrian Weller.  Favor#: Sharp attention kernel approximations via new classes of positive random features.  _arXiv preprint arXiv:2302.00787_ , 2023.
  * Reid et al. [2023] Isaac Reid, Krzysztof Marcin Choromanski, Valerii Likhosherstov, and Adrian Weller.  Simplex random features.  In _International Conference on Machine Learning_ , pages 28864–28888. PMLR, 2023.
  * Shahrampour et al. [2018] Shahin Shahrampour, Ahmad Beirami, and Vahid Tarokh.  On data-dependent random features for improved generalization in supervised learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Bach [2017] Francis Bach.  On the equivalence between kernel quadrature rules and random feature expansions.  _Journal of Machine Learning Research_ , 18(21):1–38, 2017.
  * Tokdar and Kass [2010] Surya T Tokdar and Robert E Kass.  Importance sampling: a review.  _Wiley Interdisciplinary Reviews: Computational Statistics_ , 2(1):54–60, 2010.
  * Hoffman et al. [2014] Matthew D Hoffman, Andrew Gelman, et al.  The no-u-turn sampler: adaptively setting path lengths in hamiltonian monte carlo.  _J. Mach. Learn. Res._ , 15(1):1593–1623, 2014\.
  * Dillon et al. [2017] Joshua V Dillon, Ian Langmore, Dustin Tran, Eugene Brevdo, Srinivas Vasudevan, Dave Moore, Brian Patton, Alex Alemi, Matt Hoffman, and Rif A Saurous.  Tensorflow distributions.  _arXiv preprint arXiv:1711.10604_ , 2017.

##  Appendix A Appendix

###### Proof of Theorem 1.

We wish to minimize the expected sample variance. Recall that variance can be
written as

$\displaystyle\mathop{\text{Var}}_{\omega\sim\Psi}$
$\displaystyle\left[\frac{p_{\Omega}\left(\omega\right)}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right]=$
$\displaystyle\mathop{\mathbb{E}}_{\omega\sim\Psi}\left[\frac{p_{\Omega}\left(\omega\right)^{2}}{p_{\Psi}\left(\omega\right)^{2}}\phi\left(x_{1},\omega\right)^{2}\phi\left(x_{2},\omega\right)^{2}\right]-\mathop{\mathbb{E}}_{\omega\sim\Psi}\left[\frac{p_{\Omega}\left(\omega\right)}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)\phi\left(x_{2},\omega\right)\right]^{2}.$

The second term is just $K\left(x_{1},x_{2}\right)^{2}$, meaning it does not
depend on $\Psi$. We turn our attention to the first term. The expected value
of the first term is

$\displaystyle\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\mathop{\mathbb{E}}_{\omega\sim\Psi}$
$\displaystyle\left[\frac{p_{\Omega}\left(\omega\right)^{2}}{p_{\Psi}\left(\omega\right)^{2}}\phi\left(x_{1},\omega\right)^{2}\phi\left(x_{2},\omega\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\mathop{\mathbb{E}}_{x_{1}\sim\mathcal{X}_{1}}\mathop{\mathbb{E}}_{x_{2}\sim\mathcal{X}_{2}}\int_{X}\frac{p_{\Omega}\left(\omega\right)^{2}}{p_{\Psi}\left(\omega\right)}\phi\left(x_{1},\omega\right)^{2}\phi\left(x_{2},\omega\right)^{2}d\omega$
$\displaystyle=$
$\displaystyle\int_{X}\frac{p_{\Omega}\left(\omega\right)^{2}}{p_{\Psi}\left(\omega\right)}q_{\phi}\left(\omega\right)^{2}d\omega$
(3)

We wish to find the $p_{\Psi}$ that minimizes this expression, subject to the
constraint that $\int_{X}p_{\Psi}\left(\omega\right)d\omega=1$. We’ll solve
this using Lagrange optimization. The Lagrangian is

$\mathcal{L}=\frac{p_{\Omega}\left(\omega\right)^{2}}{p_{\Psi}\left(\omega\right)}q_{\phi}\left(\omega\right)^{2}+\lambda
p_{\Psi}\left(\omega\right).$

where $\lambda$ is our Lagrange parameter. Differentiating with respect to
$p_{\Psi}\left(\omega\right)$,

$\frac{\partial\mathcal{L}}{\partial
p_{\Psi}}=-\frac{p_{\Omega}\left(\omega\right)^{2}}{p_{\Psi}\left(\omega\right)^{2}}q_{\phi}\left(\omega\right)^{2}+\lambda.$

Setting this equal to zero and solving, we find that

$p_{\Psi}(\omega)=\frac{1}{\sqrt{\lambda}}p_{\Omega}(\omega)q_{\phi}\left(\omega\right)$

as desired. The constraint that $\int_{X}p_{\Psi}\left(\omega\right)d\omega=1$
forces
$\sqrt{\lambda}=\int_{X}p_{\Psi}\left(\omega\right)q_{\phi}\left(\omega\right)d\omega$.
By plugging this into (A), we obtain the desired variance. ∎