# What Motivated Mitigation Policies? A Network-Based Longitudinal Analysis of
State-Level Mitigation Strategies

William Fries
GIDP in Applied Math
University of Arizona

(December 2022)

###### Abstract

Understanding which factors informed pandemic response can help create a more
nuanced perspective on how each state of the United States handled the crisis.
To this end, we create various networks linking states together based on their
similarity in mitigation policies, politics, geographic proximity and COVID-19
case data. We use these networks to analyze the correlation between pandemic
policies and politics, location and case-load from January 2020 through March
2022. We show that the best predictors of a state’s response is an aggregate
political affiliation rather than solely governor affiliation as others have
shown [1, 2]. Further, we illustrate that political affiliation is heavily
correlated with policy intensity from June 2020 through June 2021, but has
little impact on policy after June 2021. In contrast, geographic proximity and
daily incidence are not consistently correlated with state’s having similar
mitigation policies.

##  1 Introduction

Throughout the COVID-19 pandemic, many in the United States turned to their
state leaders for guidance and to instate policies that best served their
needs. In the midst of a global crisis, we should expect that pandemic
intensity dictates the policies that political leaders implement to protect
their citizens, whether medically, economically or otherwise. However,
throughout the course of the pandemic, it became evident that politics played
a much more important role than the severity of the crisis itself. Many have
performed statistical analyses that illustrate the strong correlation between
political affiliation, the policies instated during the pandemic [1, 2, 3],
and the subsequent outcomes [4, 5, 6]. Others have examined how the citizens
have reacted to these policies [7, 8, 9, 10] or vaccine uptake rates based on
a number of factors, including political affiliation [11, 12, 13, 14]

However, few of these studies analyzed to what extent the relationships
between political actors plays a role. [1] and [2] perform longitudinal
studies that analyze the impact of governor policy through November and
December 2020 respectively. This analysis does not span the whole pandemic and
these results only consider the governor’s political affiliation. While this
intuitively makes sense, as governors implemented executive orders, states
such as Maryland and Massachusetts, which are more liberal, are classified as
Republican states. This is recognized as a limitation of the study and we hope
to quantify how much of a limitation this could be and offer a remedy.

We hope to further expand on [1] and [2] by considering when the political
influence is statistically significant and under what conditions politics
plays a strong role. Studies have shown that both homophily and proximity can
be important factors in political networks and their resulting outcomes [15,
16]. We analyze to what extent homophily could play a role in the mitigation
policy process. That is, do Republican and Democrat states tend to cluster
together in their approach to handling the pandemic or is there still
variation. In contrast, we consider to what effect geographic proximity and
current pandemic intensity can be used to explain each state’s mitigation
response. As both of these factors, specifically the latter, would be expected
to have a strong impact on mitigation policy strength, we might expect to see
a high correlation. As states with large amounts of new cases would likely
intensify mitigation policies; similarly, as the pandemic begins to weaken, so
might the policies. This acts as our expectation in the analysis below.

Through analyzing the pandemic responses through a network-based lens, we seek
to understand how the political similarity, geographic proximity and pandemic
intensity between states might correlate to the overall mitigation policies
throughout the pandemic and when they played a significant role.

##  2 Methods

To best analyze how these factors impacted the mitigation strategies
implemented by each state we first quantify each states general mitigation
policy strength. To quantify the mitigation policy strength, we use separate
mitigation strategies as defined in [17, 18] for dates ranging from Jan. 22,
2020 to March 28, 2022. We consider the following mitigation strategies in our
analysis: school closing, workplace closing, cancelling of public events,
restrictions on gatherings, public transport closing, stay at home
requirements, restrictions on internal movement, debt relief, and facial
coverings.

Each of these measures is rated on a scale to indicate the severity. Table 1
describes each strategy and details can be found in [17]. For consistency we
normalize the value in column 2 to range from 0 to 1 where 0 indicates no
measure and 1 indicates the highest possible intensity. These measures will be
used for both standard statistical analysis as well as in constructing
networks to potentially uncover more nuanced perspectives.

To quantify political affiliation, we use four separate measures: governor
affiliation, state senate majority, state legislative majority and 2020
electoral college. We will use these to analyze which political markers best
predict mitigation policy intensity and construct a Political Adjacency
Network.

Name | Range | Description
---|---|---
school closing | [0-3] | Level to which schools are closed
workplace closing | [0-3] | Level to which workplaces are closed
cancel public events | [0-3] | Amount of restriction on public events
restrictions on gatherings | [0-3] | Restricted gatherings of non-household members
public transport closing | [0-3] | Amount of public transportation that is closed
stay at home requirements | [0-3] | Who self-quarantine at home is mandated for
restrictions on internal movement | [0-3] | Amount of travel restriction within country
debt relief | [0-3] | Amount of debt/contract relief for households
facial coverings | [0-4] | Policies on facial coverings outside the home
Table 1: Descriptions of mitigation policies used in the quantifying the
mitigation strength of each state. Detailed explanations for each measurement
criteria can be found at [18]. The data was downloaded from the Google open-
source COVID-19 data repository at [17].

###  2.1 Network Construction

Network analysis offers a method to analyze the underlying relationships that
might motivate individual agents to act [19]. To best analyze which factors
might impact mitigation policies on a relational level, we will consider how
graphs representing these ideas are correlated with each other. As we seek to
uncover potential correlations with mitigation strategy, we consider three
separate variables: political affiliation, geographic proximity, and COVID-19
incidence rates.

To generate the political network, we can define $P(s)$ to be the political
strength of each state. For state $s_{i}$,

$P(s_{i})=p_{gov}(s_{i})+p_{sen}(s_{i})+p_{leg}(s_{i})+p_{elec}(s_{i})$ (1)
$p_{j}(s_{i})=\begin{cases}1&\text{if Democrat}\\\ -1&\text{if Republican}\\\
2k-1&\text{else}\end{cases}$ (2)

where $k$ is the proportion of the political strength that is Democrat and
where $p_{j}$ refers to the political body measured (eg. governor
affiliation). For example, if a state has a Republican governor, Republican
dominated legislature, a 50/50 split senate and voted Republican in the 2020
election then

$P(s_{i})=-1+0-1-1.$ (3)

We then connect states $s_{i}$ and $s_{j}$ if $\|P(s_{i})-P(s_{j})\|\leq 2$.

To illustrate when connections are made, Missouri is a fully Republican state,
then $P(\text{MO})=-4$. North Carolina is Republican dominated but has a
Democrat governor, thus $P(\text{NC})=-2$. Finally, Pennsylvania is split with
a Republican congress but a Democrat governor and electoral college. Thus
$P(\text{PA})=0$. So, North Carolina will be connected to Missouri and
Pennsylvania; however, Missouri will not be connected to Pennsylvania.

We can define an incidence network to illustrate states which have comparable
increase in COVID-19 cases. We define $\mathcal{I}_{s}(t)$ to be the per-
capita incidence of state $s$ at time $t$. We then draw an edge between state
$s_{i}$ and $s_{j}$ if

$\|\mathcal{I}_{s_{i}}(t)-\mathcal{I}_{s_{j}}(t)\|<\frac{0.05}{50}\sum_{k=0}^{49}\mathcal{I}_{s_{k}}(t)=0.001\sum_{k=0}^{49}\mathcal{I}_{s_{k}}(t)$
(4)

We consider a new network for every time step for both the mitigation
similarity network and the incidence similarity network.

Finally, we create a geographic network of the 50 states. In this network
states are connected if they share a border. This generates a time-independent
network with three components (the contiguous United States, Alaska, and
Hawaii).

To collectively analyze the mitigation strategies for each state, we consider
a generalized mitigation policy strength. Let $m_{s}^{i}(t)$ be the mitigation
strategy $i$ at time $t$ for state $s$. Then the mitigation strength for state
$s$ at time $t$ will be defined as $M_{s}(t):=\|\mathbf{m_{s}(t)}\|_{2}$ where
$\mathbf{m_{s}(t)}=\langle m_{s}^{0}(t),\dots m_{s}^{8}(t)\rangle$ and
$\|\cdot\|_{2}$ denotes the Euclidean norm. Finally, we define
$\boldsymbol{\mu}(t)$ to be the mean mitigation policy strength at time $t$
across all 50 states. Thus, the $i$th component of $\boldsymbol{\mu}(t)$ is

$\mu_{t}^{i}=\frac{1}{50}\sum_{s=0}^{49}m_{s}^{i}(t).$ (5)

Using $\boldsymbol{\mu}(t)$, we define a network of states in which an edge
represents comparable strength of mitigation policy. An edge exists between
states $s_{i}$ and $s_{j}$ if

$\|\mathbf{m_{s_{i}}(t)}-\mathbf{m_{s_{j}}(t)}\|_{2}<0.05\|\boldsymbol{\mu}(t)\|_{2}.$
(6)

In our network-based analysis, we will use these two static networks
(geographic and political) and dynamic network (incidence similarity) to
investigate the correlation with the mitigation similarity networks. An
example of each of the networks can be found in Figure 1 where, for the two
dynamic networks, we take the network from May 1, 2020.

(a) Geographic Adjacency Network

(b) Political Adjacency Network

(c) Incidence Similarity Network

(d) Mitigation Similarity Network

Figure 1: Examples of the four networks used in the analysis. Both the
Incidence Similarity and Mitigation Similarity networks are taken on May 1,
2020. Visualizations were created using Gephi [20].

###  2.2 Statistical Methods

We then consider multiple methods to quantify the correlation between these
factors and overall COVID mitigation policy. As done in [1, 2], we consider
the correlation between political alignment and mitigation strength. At every
time step, we compute this Pearson correlation coefficient with respect to
each of the four individual political measures and the aggregate political
measure. This allows us to analyze how the political influence might have
evolved over the course of the pandemic. The results to this analysis can be
found in Section 3.1.

To determine potential underlying relationships between similar mitigation
policies and the three explanatory variables, we considered a graphical model
and quadratic assignment procedure (QAP) [21, 22, 23, 24]. This method extends
standard graph correlation by controlling for graph structure. Standard graph
correlation examines the correlation between the edges of two networks.
However, QAP analysis allows us to consider only graphs with the same
structure, making the result dependent on the specific relationships rather
than the underlying structure. In cases where one of the two graphs might be
significantly sparser than the other, correlating the edges will likely not
yield high values as the number of edges is significantly different.

QAP remedies this problem. For every mitigation similarity network, we compute
the correlation of the edges with those of the political, geographic and
incidence similarity networks. We then permute the node (ie. state) labels,
compute the new correlation, and repeat this for all possible permutations of
node labels. This results in a distribution of correlations. This distribution
represents the correlations between two networks for all isomorphic graphs of
this structure. We can then ask the correlation of the original graph labels
compares to those of isomorphic graphs. Using the corresponding p-value, we
judge the significance of the correlation of the original graph. We use this
method to compare the political similarity, geographic proximity, and
incidence similarity networks with the mitigation similarity networks.

##  3 Results

We explore the correlation between political affiliation and mitigation policy
intensity and the correlation between the various networks described in
Section 2.1. We split each of these analyses into separate sections and
discuss their combined implications in Section 4.

###  3.1 Pearson Correlation Coefficient

For each day of data, we track the correlation between mitigation policy
strength and the four political measures and the aggregate measure as defined
in Equation 1. The results are shown in Figure 2.

Figure 2: Correlation of Mitigation policy strength and political affiliation
measured by governor affiliation, senate and legislative majority, and 2020
electoral college and when there is statistically significant difference in
mitigation policy intensity between majority Democratic and Republican states.

Through the course of the pandemic, we see there is a general positive
correlation between mitigation strength and all measures of state-level
political affiliation. We report the average values of this correlation over
two separate time periods in Table 2. Interestingly, throughout most of the
first year of the pandemic, governor affiliation has the lowest correlation
amongst all political measures, with an average correlation of 0.44 and a
maximum of 0.58. As governors signed executive orders, we might expect this
correlation to be the highest but the analysis illustrates otherwise. This
contradicts the idea that governors affiliation would be the best predictor.
However, as mitigation strategies relaxed in mid-2021, governor affiliation
become the best predictor of mitigation strength.

Further, the best predictor over the first year of the pandemic is either the
overall party strength or the senate majority. On average, from January 2020
through March 2022, the overall political affiliation of the state was the
best predictor of mitigation policy strength. We will discuss potential
reasons for this in Section 4.

Affiliation |  | Max
---
Correlation
| Mean Correlation
---
June 2020 - June 2021
| Mean Correlation
---
July 2021 - March 2022
Aggregate | 0.76 | 0.57 | 0.24
Governor | 0.58 | 0.44 | 0.25
Legislature | 0.72 | 0.51 | 0.19
Senate | 0.77 | 0.56 | 0.22
| Electoral
---
College
0.61 | 0.45 | 0.13
Table 2: Correlation statistics for political affiliation and mitigation
policy strength.

We perform a 2-sample t-test on the mean mitigation policy strength for both
majority Republican and Democrat states. They are statistically significantly
different during two different periods: May 22nd, 2020 through July 23rd, 2020
and from August 26th, 2020 through July 11th, 2021. This acts as an indicator
that there is a meaningful relationship between political similarity and
similar mitigation policies. We will discuss how this relates to the timing of
significance of the network analysis in Section 4.

###  3.2 Network Correlation

When considering the graph correlation through the QAP analysis, we look for a
positive and significant correlation between the graphs. A positive and
significant correlation would imply that the graph structures mirror each
other and that one graph can be used to predict the structure of the other. As
the number of edges between the graphs could vary greatly, we do not expect
high correlation values. For example, the Political Adjacency Network contains
1152 edges whereas the average number of edges for the mitigation networks
between June 2020 and June 2021 is 406 edges. In spite of differing numbers of
edges, QAP allows us to consider when the correlation is significant, and
thus, the network structures are significantly related. We set an
$\alpha$-level of 0.001 and illustrate the results in Figure 3.

Figure 3: Correlation and regions of significance for QAP analysis for network
representations of political similarity, geographic proximity and incidence
similarity.

Table 3 shows the data found in Figure 3. We report the average correlation
and number of days of significance between June 2020 and June 2021. We note
that the period of significance for these networks extends beyond June 2021;
however for consistency with Table 2, we report data between June 2020 and
June 2021. We notice that the only graph that has significant correlation with
the Mitigation Similarity Networks over a long period of time is the Political
Adjacency Network. The Political Adjacency Network not only has the highest
correlation between June 2020 and June 2021, but also the proportion of days
which the political similarity aligns with the mitigation strength of a state.
Interestingly, the Geographic Adjacency Network appears to correlate with the
Mitigation Similarity Networks more consistently than the Incidence Similarity
Networks. Visually, this can be seen by the lack of regions of significance in
at the bottom of Figure 3. Concretely, the Geographic Adjacency Network was
significantly correlated with the Mitigation Similarity Network for only 25%
of the days between June 2020 and June 2021. More striking, the Incidence
Similarity Network is only significantly correlated with the Mitigation
Similarity Network 10% of the days during the same time period. This implies
that neither geographic relationship nor the relative epidemic-severity of can
be used to explain why states had comparably strong mitigation policies.

Network | Mean Correlation |  | Proportion of Days
---
Significant Correlation
Political Adjacency | 0.10 | 0.87
Geographic Adjacency | 0.03 | 0.24
Incidence Similarity | 0.01 | 0.10
Table 3: Graph correlation statistics between June 2020 and June 2021. We
report the average graph correlation between the each of the explanatory
graphs and the Mitigation Strength Adjacency Network during this time period
and the number of days which this correlation is significant.

##  4 Discussion

There are two interesting points of discussion from the analyses above: the
distinctions between the methods and the implications of the results. The two
methods have yielded the same results of many other analysis prior to this
one: there is a significant relationship between a state’s politics and how
they responded to the COVID-19 pandemic. However, now, we know when this
relationship was significant. Both methods reported that the relationship was
significant between May of 2020 and July of 2021. However, each method offered
slightly different results.

The strategy of analyzing Pearson Correlation of mitigation policy strength
with political affiliation highlights a potential method for analyzing state-
level politics more accurately. As the governor’s affiliation showed the
lowest correlation with general mitigation policy strength, it is important to
have a more holistic view of a states politics. For instance, classifying
states by governor during the pandemic would classify Maryland and
Massachusetts as Republican states when every other aspect of their politics
is decisively Democrat.

When considering the timing of the significance of the two-sample t-test, we
see that the difference in responses between Republican and Democrat states
became significant at the beginning of June. While we cannot say for certain
what caused this shift, there are a few possibilities. Many states were ending
their lock-downs and stay-at-home requirements. Political pressure from other
politicians or constituents could have also caused this divergence of the
political parties.

However, when considering the end of the period of significance in 2021, we
can potentially attribute this to the general drop in mitigation policy
strength. As the mean mitigation policy strength (purple in Figure 3) shifts
from 2 to near 1 over a 6 month period. This supports the hypothesis that
higher restrictions and strong policies are more politically divisive.

When comparing the two-sample t-test results to those of the political
similarity network and mitigation similarity networks, we see that the network
analysis gives a slightly broader region of significance. This is likely
because it accounts for the relationships between states and their similar
behaviors rather than looking at each state in isolation. This, in turn,
emphasizes the importance of political relationships in the Mitigation
Similarity Networks structures.

In contrast, the Geographic Adjacency Network and Incidence Similarity Network
show little correlation to the Mitigation Similarity Networks. We notice that
the Geographic Adjacency Network shows small regions of sustained
significance, this is likely because of the political landscape of the United
States: Democrat states tend to be on the coasts and Republican states cluster
in more central states.

Interestingly, the Incidence Similarity Networks correlations are significant
at the beginning of the pandemic, when no other network shows significant
correlation. This is likely because all states were responding to the pandemic
rather than their political counterparts. However, the significant
correlations end at the end of April as many lockdown measures were beginning
to be lifted.

###  4.1 Limitations

This study and its conclusions are limited by several factors. Primarily, the
method for network construction can be modified to the researcher’s
preference. Specifically, the threshold used to connected states within the
Political Adjacency, Mitigation Similarity and Incidence Similarity networks
were chosen in an attempt to capture the significant relationships. However, a
more dense network can be created by lowering the threshold and and sparser
network can be created by raising it. While we do not expect this to
drastically impact the results of this paper, it nevertheless will likely
cause the results to deviate slightly.

Further, other networks might be created, such as complete networks for the
Political Adjacency, Mitigation Similarity, and Incidence Similarity with
weighted edges. This would have the effect of capturing the “distance” between
two states rather than making their relationships binary. We expect similar
results to those presented in the paper; however, in our view, this would not
highlight the importance of the underlying graph structure as much as the
analysis presented above.

Finally, a county-level model could be considered instead of the state-level
one. As many counties and municipalities enforced their own restrictions and
have political affiliations that do not necessarily align with their states, a
county-level analysis might uncover a more nuanced relationship between the
political parties and how urban and rural counties approached mitigation
differently.

###  4.2 Conclusions and Future Work

This study illustrates the strong relationship between political similarity
and mitigation policy similarity. This can be seen through both the analysis
of the Pearson Correlation between state-level politics and their time-
dependent mitigation policies and through the network-based analysis. The
former highlights the general relationship between politics and COVID-19
mitigation while the later emphasizes the underlying relationships between the
states. Further, the network-based analysis allows us to consider both
geographic relationships and incidence similarity and compare how these
influence the mitigation policy when compared to the political relationships.
We see that both similar disease-intensity and geographic distance between
states state showed little to no correlation with similar mitigation policies
after May of 2020 highlighting how politics became the driving factor behind
controlling COVID-19 rather than the severity of the disease.

As discussed above, further work should consider other types of network
constructions. These should be on both the county-level and using different
criteria for connecting states together. Qualitative analysis would also offer
a more nuanced perspective to the analysis. Consideration of interactions
between state-level government officials could present explanations as to why
politics were significantly tied to mitigation policy between June 2020 and
June 2021.

Further work should also consider how social events, such as holidays, and
other collective behavioral phenomena could influence the adjustment of
policy. Finally, with a method to quantify each state’s response to the
pandemic over time, it can be important to understand to what extent the
changes in policy changes diffuse through the networks and what factors drive
said diffusion. Ultimately, we see that political similarity, not geographic
proximity or pandemic intensity, played the most important role in predicting
similar mitigation policies between states at the height of the pandemic.

## References

  * [1] O. Shvetsova, A. Zhirnov, F. R. Giannelli, M. A. Catalano, and O. Catalano, “Governor’s party, policies, and covid-19 outcomes: Further evidence of an effect,” American Journal of Preventive Medicine, vol. 62, no. 3, pp. 433–437, 2022.
  * [2] B. Neelon, F. Mutiso, N. T. Mueller, J. L. Pearce, and S. E. Benjamin-Neelon, “Associations between governor political affiliation and covid-19 cases, deaths, and testing in the u.s.,” American Journal of Preventive Medicine, vol. 61, no. 1, pp. 115–119, 2021.
  * [3] A. B. Adeel, M. Catalano, O. Catalano, G. Gibson, E. Muftuoglu, T. Riggs, M. H. Sezgin, O. Shvetsova, N. Tahir, J. VanDusky-Allen, et al., “Covid-19 policy response and the rise of the sub-national governments,” Canadian Public Policy, vol. 46, no. 4, pp. 565–584, 2020.
  * [4] J. Kerr, C. Panagopoulos, and S. van der Linden, “Political polarization on covid-19 pandemic response in the united states,” Personality and Individual Differences, vol. 179, p. 110892, 2021.
  * [5] S. Hsiang, D. Allen, S. Annan-Phan, K. Bell, I. Bolliger, T. Chong, H. Druckenmiller, L. Y. Huang, A. Hultgren, E. Krasovich, et al., “The effect of large-scale anti-contagion policies on the covid-19 pandemic,” Nature, vol. 584, no. 7820, pp. 262–267, 2020.
  * [6] S. Flaxman, S. Mishra, A. Gandy, H. J. T. Unwin, T. A. Mellan, H. Coupland, C. Whittaker, H. Zhu, T. Berah, J. W. Eaton, et al., “Estimating the effects of non-pharmaceutical interventions on covid-19 in europe,” Nature, vol. 584, no. 7820, pp. 257–261, 2020.
  * [7] B. Franz and L. Y. Dhanani, “Beyond political affiliation: an examination of the relationships between social factors and perceptions of and responses to covid-19,” Journal of Behavioral Medicine, vol. 44, pp. 641–652, Oct 2021\.
  * [8] D. DeFranza, M. Lindow, K. Harrison, A. Mishra, and H. Mishra, “Religion and reactance to covid-19 mitigation guidelines.,” American Psychologist, vol. 76, no. 5, p. 744–754, 2021.
  * [9] S. K. Gadarian, S. W. Goodman, and T. B. Pepinsky, “Partisanship, health behavior, and policy attitudes in the early stages of the covid-19 pandemic,” PLOS ONE, vol. 16, no. 4, 2021.
  * [10] M. Painter and T. Qiu, “Political beliefs affect compliance with covid-19 social distancing orders,” Covid Economics, vol. 4, pp. 103–123, 2020\.
  * [11] J. N. Druckman, K. Ognyanova, M. A. Baum, D. Lazer, R. H. Perlis, J. D. Volpe, M. Santillana, H. Chwe, A. Quintana, and M. Simonson, “The role of race, religion, and partisanship in misperceptions about covid-19,” Group Processes & Intergroup Relations, vol. 24, no. 4, pp. 638–657, 2021.
  * [12] J. Levin, E. L. Idler, and T. J. VanderWeele, “Faith-based organizations and sars-cov-2 vaccination: challenges and recommendations,” Public Health Reports, vol. 137, no. 1, pp. 11–16, 2022.
  * [13] J. Levin and M. Bradshaw, “Determinants of covid-19 skepticism and sars-cov-2 vaccine hesitancy: findings from a national population survey of us adults,” BMC Public Health, vol. 22, no. 1, pp. 1–8, 2022.
  * [14] T. Bolsen and R. Palm, “Politicization and covid-19 vaccine resistance in the us,” Progress in molecular biology and translational science, vol. 188, no. 1, pp. 81–100, 2022.
  * [15] E. R. Gerber, A. D. Henry, and M. Lubell, “Political homophily and collaboration in regional planning networks,” American Journal of Political Science, vol. 57, no. 3, p. 598–610, 2013.
  * [16] M. T. PIETRYKA and D. A. DEBATS, “It’s not just what you have, but who you know: Networks, social proximity to elites, and voting in state and local elections,” American Political Science Review, vol. 111, no. 2, p. 360–378, 2017.
  * [17] O. Wahltinez et al., “Covid-19 open-data: curating a fine-grained, global-scale data repository for sars-cov-2,” GitHub, 2020.  Work in progress.
  * [18] T. Hale, N. Angrist, R. Goldszmidt, B. Kira, A. Petherick, T. Phillips, S. Webster, E. Cameron-Blake, L. Hallas, S. Majumdar, and H. Tatlow, “A global panel database of pandemic policies (oxford covid-19 government response tracker),” Nature Human Behaviour, vol. 5, pp. 529–538, Apr 2021\.
  * [19] M. E. J. Newman, Networks: an introduction.  Oxford; New York: Oxford University Press, 2010.
  * [20] M. Bastian, S. Heymann, and M. Jacomy, “Gephi: an open source software for exploring and manipulating networks,” in Third international AAAI conference on weblogs and social media, 2009.
  * [21] L. Hubert and J. Schultz, “Quadratic assignment as a general data analysis strategy,” British journal of mathematical and statistical psychology, vol. 29, no. 2, pp. 190–241, 1976.
  * [22] D. Krackardt, “Qap partialling as a test of spuriousness,” Social networks, vol. 9, no. 2, pp. 171–186, 1987.
  * [23] D. Krackhardt, “Predicting with networks: Nonparametric multiple regression analysis of dyadic data,” Social networks, vol. 10, no. 4, pp. 359–381, 1988.
  * [24] Lisette-Espin, “Mrqap implementation in python3,” GitHub, 2020.


# Lower-bounds on the Bayesian Risk in Estimation Procedures via
$f$–Divergences

Adrien Vandenbroucque, Amedeo Roberto Esposito, Michael Gastpar  School of
Computer and Communication Sciences
EPFL, Lausanne, Switzerland
<EMAIL_ADDRESS>{amedeo.esposito,
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of parameter estimation in a Bayesian setting and
propose a general lower-bound that includes part of the family of
$f$-Divergences. The results are then applied to specific settings of interest
and compared to other notable results in the literature. In particular, we
show that the known bounds using Mutual Information can be improved by using,
for example, Maximal Leakage, Hellinger divergence, or generalizations of the
Hockey-Stick divergence.

###### Index Terms:

Bayesian Risk, Parameter Estimation, Information Measures, $f-$Divergences,
Mutual Information, Hockey-Stick Divergence

##  I Introduction

In this work we consider the problem of parameter estimation in a Bayesian
setting. The connection between said problem and information measures has been
established multiple times over the years [1, 2, 3]. Here we further develop
the perspective undertaken in [2] and in [4]. Similarly to [2] and [4] we will
look at the problem through an information-theoretic lens and we will thus
treat the parameter to be estimated as a message sent through a channel. The
family of bounds one can derive in this framework generally give rise to two
objects:

  * •

a measure of information (Shannon’s Mutual Information was employed in [2],
Sibson’s $\alpha$-Mutual Information in [4], Hockey-Stick Divergence in [3],
etc.);

  * •

a small-ball probability;

The main advantage of this is that both terms can be rendered independent of
the specific choice of the estimator, which in turns renders these lower-
bounds quite general. Our main focus will not be on asymptotic results but
rather on finite sample lower-bounds. In particular, we will expand upon [4],
utilizing the same approach but focusing on $f-$Divergences rather than on
Sibson’s Mutual Information.

##  II Background and definitions

######  Definition 1.

Given a function $f:\mathcal{X}\to\mathcal{Y}$, the Legendre-Fenchel transform
of $f$ is defined as

$f^{\star}(x^{\star})=\sup_{x\in\mathcal{X}}\langle x^{\star},x\rangle-f(x),$
(1)

where $\langle x^{\star},x\rangle$ denotes the natural pairing between a space
$\mathcal{X}$ and its topological dual $\mathcal{X}^{\star}$, i.e., $\langle
x^{\star},x\rangle=x^{\star}(x).$ Given a function $f$, $f^{\star}$ is
guaranteed to be lower semi-continuous and convex. If $f$ is convex and lower
semi-continuous then $f=f^{\star\star}|_{\mathcal{X}}$ (the restriction of
$f^{\star\star}$ on $\mathcal{X}$ agrees with $f$).

###  II-A $f-$Divergences

A straightforward generalization of the KL-Divergence can be obtained by
considering a generic convex function $f:\mathbb{R}\to\mathbb{R}$, usually
with the simple constraint that $f(1)=0$.

######  Definition 2.

Let $(\Omega,\mathcal{F},\mathcal{P}),(\Omega,\mathcal{F},\mathcal{Q})$ be two
probability spaces. Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function such
that $f(1)=0$. Consider a measure $\mu$ such that $\mathcal{P}\ll\mu$ and
$\mathcal{Q}\ll\mu$ (i.e., $\mathcal{P}$ and $\mathcal{Q}$ are absolutely
continuous with respect to $\mu$). Denoting with $p,q$ the densities of the
measures with respect to $\mu$, the $f-$Divergence of $\mathcal{P}$ from
$\mathcal{Q}$ is defined as follows:

$\displaystyle D_{f}(\mathcal{P}\|\mathcal{Q})=\int
qf\left(\frac{p}{q}\right)d\mu.$ (2)

Note that $f-$divergences are independent from the choice of the dominating
measure $\mu$ [5]. When absolute continuity between $\mathcal{P},\mathcal{Q}$
holds, denoted with $\mathcal{P}\ll\mathcal{Q}$ one retrieves the following
[5]:

$D_{f}(\mathcal{P}\|\mathcal{Q})=\int
f\left(\frac{d\mathcal{P}}{d\mathcal{Q}}\right)d\mathcal{Q}.$ (3)

This generalization includes the KL divergence (by simply setting
$f(t)=t\log(t)$), but it also includes:

  * •

Total Variation distance, with $f(t)=\frac{1}{2}|t-1|$;

  * •

Hellinger distance, with $f(t)=(\sqrt{t}-1)^{2}$;

  * •

Pearson $\chi^{2}$-divergence, with $f(t)=(t-1)^{2}$.

In particular, in this paper, we will be interested in two families of
divergences. The first family, also known as Hellinger Divergences, is
typically characterized by a parameter $p>0$. More precisely, we are referring
to the $f$–Divergences that stem from $f_{p}(t)=\frac{t^{p}-1}{p-1}$ and that
will be denoted as follows:

$\mathcal{H}_{p}(\mathcal{P}\|\mathcal{Q})=D_{f_{p}}(\mathcal{P}\|\mathcal{Q}).$
(4)

The second family we consider is characterized by two parameters, namely
$\beta>0$ and $\gamma\geq\beta$, and arise from the parametric family of
functions $f_{\beta,\gamma}(t)=\max\\{0,\beta t-\gamma\\}$. We denote it as:

$E_{\beta,\gamma}(\mathcal{P}\|\mathcal{Q})=D_{f_{\beta,\gamma}}(\mathcal{P}\|\mathcal{Q}).$
(5)

For the case $\beta=1$, one retrieves the family of so-called
$E_{\gamma}$–Divergences [6, Eq. (47)].

Much like $f$–Divergences, a generalization of Shannon’s Mutual Information,
denoted in the literature as $f$–Mutual Information, can be defined starting
from $f$–Divergences as follows:

######  Definition 3.

Let $X$ and $Y$ be two random variables jointly distributed according to
$\mathcal{P}_{XY}$ over a measurable space
$(\mathcal{X}\times\mathcal{Y},\mathcal{F}_{XY})$. Let
$(\mathcal{X},\mathcal{F}_{X},\mathcal{P}_{X}),(\mathcal{Y},\mathcal{F}_{Y},\mathcal{P}_{Y})$
be the corresponding probability spaces induced by the marginals. Let
$f:\mathbb{R}\to\mathbb{R}$ be a convex function such that $f(1)=0$. The
$f$–Mutual Information between $X$ and $Y$ is defined as:

$I_{f}(X,Y)=D_{f}(\mathcal{P}_{XY}\|\mathcal{P}_{X}\mathcal{P}_{Y}).$ (6)

If $f$ is strictly convex at $1$ and satisfies $f(1)=0$, then $I_{f}(X,Y)=0$
if and only if $X$ and $Y$ are independent [5, Theorem 5]. Choosing
$f(t)=t\log t$, one recovers the Mutual Information. With a slight abuse of
notation, we will denote $f$–Mutual Informations with the same symbols used to
characterize the corresponding divergences, e.g.,
$\mathcal{H}_{p}(X,Y)=\mathcal{H}_{p}(\mathcal{P}_{XY}\|\mathcal{P}_{X}\mathcal{P}_{Y})$
will represent the $f_{p}$–Mutual Information, while
$E_{\beta,\gamma}(X,Y)=E_{\beta,\gamma}(\mathcal{P}_{XY}\|\mathcal{P}_{X}\mathcal{P}_{Y})$
will represent the $f_{\beta,\gamma}$–Mutual Information.

###  II-B Problem Setting - the Bayesian framework

Let $\mathcal{W}$ denote the parameter space and assume that we have access to
a prior distribution over this space $\mathcal{P}_{W}$. Suppose then that we
observe $W$ through the family of distributions
$\mathcal{P}=\\{\mathcal{P}_{X|W=w}:w\in\mathcal{W}\\}.$ Given a function
$\phi:\mathcal{X}\to\mathcal{W}$ one can then estimate $W$ from
$X\sim\mathcal{P}_{X|W}$ via $\phi(X)=\hat{W}$. Let us denote with
$\ell:\mathcal{W}\times\mathcal{W}\to\mathbb{R}^{+}$ a loss function, the
Bayesian risk is defined as:

$R=\inf_{\phi}\mathbb{E}[\ell(W,\phi(X)]=\inf_{\phi}\mathbb{E}[\ell(W,\hat{W})].$
(7)

Our purpose will be to lower-bound $R$ using the tools described in the
previous section. To this end, we will be using a simple Markov’s inequality
approach: i.e., for every estimator $\phi$ and $\rho\geq 0$, one can do the
following

$\mathbb{E}[\ell(W,\hat{W})]\geq\rho\left(P_{W\hat{W}}(\ell(W,\hat{W})\geq\rho)\right).$
(8)

With further manipulations we can actually relate
$\mathbb{P}(\ell(W,\hat{W})\geq\rho)$ to the information-measures described
before and some function $\psi$ of $P_{W}P_{\hat{W}}(\ell(W,\hat{W})\geq\rho)$
(the measure of $\\{\ell(W,\hat{W})\geq\rho\\}$ under the product of the
marginals $P_{W}P_{\hat{W}}$). Let us denote
$P_{W}P_{\hat{W}}(\ell(W,\hat{W})\leq\rho)=L_{W}(\hat{W},\rho)$. In some
cases, this $\psi$ will lead us to considering the so-called small-ball
probability

$L_{W}(\rho)=\sup_{\hat{w}\in\mathcal{\hat{W}}}L_{W}(\hat{w},\rho)=\sup_{\hat{w}\in\mathcal{\hat{W}}}\mathbb{P}(\ell(W,\hat{w})\leq\rho).$
(9)

The purpose is to render both of these quantities independent of $\phi$,
granting us the tools to provide general lower-bounds on the risk $R$.

###  II-C Related Works

A survey of early works in this area, mainly focusing on asymptotic settings,
can be found in [7]. More recent but important advances are instead due to [1,
8]. Closely connected to this work is [2]. The approach is quite similar, with
the main difference that we employ a family of bounds involving a variety of
divergences while [2] relies solely on Mutual Information and the Kullback-
Leibler Divergence. [4] focuses on Sibson’s $\alpha$-Mutual Information, and
[3] uses the $E_{\gamma}$-Divergence. A similar approach was also undertaken
in [9]. The authors focused on the notion of $f-$informativity (cf. [10]) and
leveraged the data processing inequality similarly to [11, Theorem 3]. In
particular, $f-$informativities are more general than the $f-$Mutual
Informations considered in this work (cf. Definition 3) and they can
potentially lead to tighter results. The technique used to provide lower-
bounds on the Bayesian risk for general non-negative losses (cf. [9, Section
4]) is, however, different. It is unclear whether the results provided in this
work are equivalent (or weaker) with respect to those obtained in [9].

##  III The lower bounds

Let us start with our main result and then show how it is connected to the
Bayesian Risk.

######  Theorem 1.

Consider the Bayesian framework described in Sec. II-B. Let
$f:[0,+\infty)\to\mathbb{R}$ be an increasing convex function such that
$f(1)=0$ and suppose that the generalized inverse, defined as
$f^{-1}(y)=\inf\\{t\geq 0:f(t)>y\\}$, exists. Then the following must hold for
every $\rho>0$ and every estimator $\hat{W}$:

$\mathbb{E}[\ell(W,\hat{W})]\geq\rho\Bigg{(}1-L_{W}(\hat{W},\rho)\cdot\\\
f^{-1}\left(\frac{I_{f}(W,\hat{W})+(1-L_{W}(\hat{W},\rho))f^{\star}(0)}{L_{W}(\hat{W},\rho)}\right)\Bigg{)}.$
(10)

Moreover, if $f^{\star}(0)\leq 0$, the bound simplifies to

$\displaystyle\mathbb{E}[\ell(W,\hat{W})]\geq\rho\left(1-L_{W}(\hat{W},\rho)\cdot
f^{-1}\left(\frac{I_{f}(W,\hat{W})}{L_{W}(\hat{W},\rho)}\right)\right).$ (11)

###### Proof.

To prove the statement we use [11, Theorem 3]. In our notation, it states that
for every function $f$ with the desired properties, we have

$\displaystyle P_{W\hat{W}}(\ell(W,\hat{W})$ $\displaystyle\leq\rho)\leq
L_{W}(\hat{W},\rho)\cdot$ (12) $\displaystyle
f^{-1}\left(\frac{I_{f}(W,\hat{W})+(1-L_{W}(\hat{W},\rho))f^{\star}(0)}{L_{W}(\hat{W},\rho)}\right).$
(13)

In particular when $f^{\star}(0)\leq 0$, the bound reduces to

$\displaystyle P_{W\hat{W}}(\ell(W,\hat{W})\leq\rho)\leq
L_{W}(\hat{W},\rho)\cdot
f^{-1}\left(\frac{I_{f}(W,\hat{W})}{L_{W}(\hat{W},\rho)}\right).$ (14)

Rewriting $P_{W\hat{W}}(\ell(W,\hat{W})\geq\rho)$ as
$1-P_{W\hat{W}}(\ell(W,\hat{W})\leq\rho)$ and combining this with Equations
(8) and (13) concludes the proof. ∎

In order to provide a lower-bound on the Bayesian Risk, one needs to render
the right-hand side of Equations (10) (or (11)) independent of
$\hat{W}=\phi(X)$ and, in order to do that, one needs to render independent of
$\hat{W}$:

  1. 1.

The information-measure, e.g., through the data-processing inequality
$I_{f}(W,\hat{W})\leq I_{f}(W,X)$;

  2. 2.

The quantity $L_{W}(\hat{W},\rho)$, that can be easily upper-bounded in the
following way:
$L_{W}(\hat{W},\rho)\leq\sup_{\hat{w}}L_{W}(\hat{w},\rho)=L_{W}(\rho)$.

For simplicity, consider Equation (11) and introduce the following object

$G_{f}(I_{f},L_{W}):=L_{W}(\hat{W},\rho)\cdot
f^{-1}\left(\frac{I_{f}(W,\hat{W})}{L_{W}(\hat{W},\rho)}\right).$ (15)

To use the two inequalities just stated above in items 1) and 2), one thus
needs that for a given choice of $f$, $G_{f}(I_{f},L_{W})$ is increasing in
$I_{f}$ for a given value of $L_{W}$ and vice-versa. This allows us to further
lower-bound (11) and render the quantity independent of the specific choice of
$\phi$. Hence, starting from (7) one can provide a lower-bound on the risk $R$
that is independent of $\phi$. Let us now look at some specific choices of $f$
such that $G_{f}$ satisfies the desired properties and for which a bound on
the Bayesian risk can indeed be retrieved.

######  Corollary 1.

Consider the Bayesian framework described in Sec. II-B. The following must
hold for every $p>1$ and $\rho>0$:

$R\geq\rho\left(1-L_{W}(\rho)^{\frac{p-1}{p}}\cdot\left((p-1)\mathcal{H}_{p}(W,X)+1\right)^{\frac{1}{p}}\right).$
(16)

###### Proof.

Since $f(x)=\frac{x^{p}-1}{p-1}$, we have that $f^{\star}(0)=\sup_{x\geq
0}(-f(x))=\frac{1}{p-1}$ and $f^{-1}(t)=((p-1)t+1)^{\frac{1}{p}}$.

For every estimator $\hat{W}$,

$\displaystyle L_{W}(\hat{W},\rho)\cdot
f^{-1}\left(\frac{I_{f}(W,\hat{W})+(1-L_{W}(\hat{W},\rho))f^{\star}(0)}{L_{W}(\hat{W},\rho)}\right)$
(17)
$\displaystyle=L_{W}(\hat{W},\rho)\left(\frac{(p-1)\mathcal{H}_{p}(W,\hat{W})+1}{L_{W}(\hat{W},\rho)}\right)^{\frac{1}{p}}$
(18)
$\displaystyle=L_{W}(\hat{W},\rho)^{\frac{p-1}{p}}\left((p-1)\mathcal{H}_{p}(W,\hat{W})+1\right)^{\frac{1}{p}}$
(19) $\displaystyle\leq
L_{W}(\rho)^{\frac{p-1}{p}}\left((p-1)\mathcal{H}_{p}(W,X)+1\right)^{\frac{1}{p}},$
(20)

where in (20) we used the data-processing inequality for $f$–divergences.
Using (20) with Theorem 1, we retrieve that for every estimator $\hat{W}$

$\mathbb{E}[\ell(W,\hat{W})]\geq\rho\\!\left(1-L_{W}(\rho)^{\frac{p-1}{p}}\left((p-1)\mathcal{H}_{p}(W,X)+1\right)^{\frac{1}{p}}\right).$
(21)

Since the right-hand side of (21) is independent of $\hat{W}=\phi(X)$ one can
use it to lower-bound the risk $R$. ∎

Restricting the choice of $f$ to this family of polynomials we can thus state
the following lower-bound on the risk:

$R\geq\sup_{\rho>0}\sup_{p>1}\rho\\!\left(\\!1-L_{W}(\rho)^{\frac{p-1}{p}}\\!\\!\cdot\left((p-1)\mathcal{H}_{p}(W,\hat{W})+1\right)\\!^{\frac{1}{p}}\\!\right).$
(22)

######  Remark 1.

Using the one-to-one mapping connecting Hellinger divergences and Rényi’s
$\alpha-$Divergence [6, Eq. (30)], the bound above can be re-written as
follows:

$\displaystyle R\geq\sup_{\rho>0}\sup_{\alpha>1}\rho$
$\displaystyle\bigg{(}1-L_{W}(\rho)^{\frac{\alpha-1}{\alpha}}\cdot$
$\displaystyle\exp\left(\frac{\alpha-1}{\alpha}D_{\alpha}(P_{W\hat{W}}\|P_{W}P_{\hat{W}})\right)\bigg{)}.$
(23)

In addition, given the generality of Theorem 1 we can also recover other
notable results present in the literature (cf. [3, Remark 1]) through the
following:

######  Corollary 2.

Consider the Bayesian framework described in Sec. II-B. The following must
hold for every $\beta>0$, $\gamma\geq\beta$, and $\rho>0$:

$R\geq\rho\left(1-\frac{E_{\beta,\gamma}(W,\hat{W})+\gamma
L_{W}(\rho)}{\beta}\right).$ (24)

###### Proof.

We take the same approach as in Corollary 1. Let $f(x)=\max\\{0,\beta
x-\gamma\\}$, consequently one has that $f^{\star}(0)=\sup_{x\geq 0}(-f(x))=0$
and that the generalized inverse corresponds to
$f^{-1}(t)=\frac{t+\gamma}{\beta}$. Using Theorem 1, along with the fact that
$f^{\star}(0)\leq 0$ we have that for every estimator $\hat{W}$,

$\displaystyle\mathbb{E}[\ell(W,\hat{W})]$
$\displaystyle\geq\rho\left(1-\frac{E_{\beta,\gamma}(W,\hat{W})+\gamma
L_{W}(\hat{W},\rho)}{\beta}\right)$ (25)
$\displaystyle\geq\rho\left(1-\frac{E_{\beta,\gamma}(W,X)+\gamma
L_{W}(\rho)}{\beta}\right).$ (26)

Since (26) is independent of $\hat{W}=\phi(X)$ one can use it to lower-bound
the risk $R$. ∎

We thus retrieve the following lower-bound on the risk:

$R\geq\sup_{\rho>0}\sup_{\beta>0,\gamma\geq\beta}\rho\left(1-\frac{E_{\beta,\gamma}(W,\hat{W})+\gamma
L_{W}(\rho)}{\beta}\right).$ (27)

######  Remark 2.

Note that setting $\beta=1$ (24) recovers the result in [3, Remark 1]. In
fact, by introducing an additional degree of freedom through the $\beta$
parameter in Equation (27), the resulting lower-bound can only be tighter than
[3, Remark 1].

##  IV Examples

In this section we apply Corollaries 1 and 2 to two classical estimation
settings. The resulting lower-bounds are then compared with those obtained in
[4] involving Sibson’s $\alpha$-Mutual Information and Maximal Leakage and
with those in [2] involving Shannon’s Mutual Information and Maximal Leakage.

Ultimately, for each example, we would like to compare the tightest versions
of our bounds, which are given by Equation (22) for the
$\mathcal{H}_{p}$–Divergence and (27) for the $E_{\beta,\gamma}$–Divergence.
However, since their computations involve a maximization problem over some
parameters ($p$ or $\beta,\gamma$) that we cannot analytically solve, we
compute these lower-bounds only for specific values of the parameters. The
choice of parameters we use might seem arbitrary but it correctly captures the
behavior of the bounds. Indeed, experiments show that when solving the
maximization over $p$ or $\beta,\gamma$ (e.g., through the
scipy.optimize.minimize function from the Python library SciPy) the same
behaviors are observed, like Figure 1 shows in the context of Example 1.

Figure 1: Setting: Example 1. Comparison between the largest lower-bounds one
can retrieve for different information measures in Example 1: that is between
(27), (28), [4, Eq. (16)] and [2, Corollary 2, Eq. (19)]. The quantities are
analytically maximized over $\rho$ (cf. Appendix -C) and numerically optimized
over, respectively, $p>1$, $\beta>0$, and $\gamma\geq\beta$.

###  IV-A Example 1: Bernoulli Bias Estimation

######  Example 1.

Suppose that $W\sim U[0,1]$ and that for each $i\in[n]$,
$X_{i}|\\{W\\!=\\!w\\}\sim\text{Ber}(w)$. Also, assume that
$\ell(w,\hat{w})=|w-\hat{w}|$.

We first provide a closed-form expression of the lower-bound resulting from
Corollary 1 for a specific choice of $p$ which enables to match the upper-
bound up to a constant factor. In fact in general, the tightest bound in this
family comes from Equation (22) and can, in this example, be stated as
follows:

$R\geq\sup_{\rho>0}\sup_{p>1}\rho\\!\left(\\!1-(2\rho)^{\frac{p-1}{p}}\\!\\!\cdot\left((p-1)\mathcal{H}_{p}(W,X^{n})+1\right)\\!^{\frac{1}{p}}\\!\right).$
(28)

The value of $\mathcal{H}_{p}(W,X^{n})$ for this setting is expressed in the
following Lemma.

######  Lemma 1.

Consider the setting described in Example 1. Then for every $p>1$,

$\displaystyle(p-1)($ $\displaystyle\mathcal{H}_{p}(W,X^{n})+1)$
$\displaystyle=(n+1)^{p-1}\sum_{k=0}^{n}\binom{n}{k}^{p}\frac{\Gamma(kp+1)\Gamma((n-k)p+1)}{\Gamma(np+2)}.$
(29)

In particular with $p=2$, one recovers:

$\chi^{2}(W,X^{n})+1=\frac{n+1}{2n+1}\cdot\frac{4^{n}}{\binom{2n}{n}}\leq\frac{16\sqrt{\pi
n}}{21}.$ (30)

###### Proof.

See Appendix -D. ∎

######  Corollary 3.

Consider the setting described in Example 1. The Bayesian risk is lower-
bounded by

$R\geq\frac{7}{72\sqrt{\pi n}}.$ (31)

###### Proof.

Let $p=2$ in Corollary 1 along with $L_{W}(\rho)\leq 2\rho$, one has that

$R\geq\sup_{\rho>0}\rho\left(1-\sqrt{2\rho(\chi^{2}(W,X^{n})+1)}\right).$ (32)

Solving the maximization over $\rho$ (cf. Appendix -C) ) and using (30) we
conclude that

$\displaystyle R$
$\displaystyle\geq\frac{2}{27}\cdot\frac{1}{\chi^{2}(W,X^{n})+1}\geq\frac{7}{72\sqrt{\pi
n}}.$ (33)

∎

Notice that (31) matches the upper-bound up to a constant, and tightens the
result in [2, Corollary 2] while not requiring that $n\to\infty$.

######  Remark 3.

As mentioned in previous proof, Stirling’s approximation yields
$(\chi^{2}(W,X^{n})+1)\sim\frac{\sqrt{\pi n}}{2}$ when $n$ is large. This
implies that for $n$ large one can show that $R\gtrsim\frac{4}{27\sqrt{\pi
n}}$, thus leading to a slight improvement over (31).

Similarly, one can do the same steps used to retrieve Corollary 3, but this
time using the $E_{\beta,\gamma}$–Divergence instead of the
$\mathcal{H}_{p}$–Divergence. In particular, for the case $\beta=0.75$ and
$\gamma=2.2$, Eq. (24) in this example can be expressed as

$\displaystyle R$
$\displaystyle\geq\sup_{\rho>0}\rho\left(1-\frac{4}{3}\left(E_{0.75,2.2}(W,X^{n})+4.4\rho\right)\right)$
(34) $\displaystyle=\frac{5(0.75-E_{0.75,2.2}(W,X^{n}))^{2}}{66}.$ (35)

A direct comparison between the bounds we provide and those already present in
the literature can be seen in Figure 2. The lower-bounds are computed as a
function of the number of samples $n$, which we consider to be in the range
$\\{1,\dots,50\\}$. The figure shows that all the divergences we considered in
this work provide a larger (and thus, better) lower-bound on the Bayesian risk
when compared with results that stem from using Shannon’s Mutual Information
(cf. [2, Corollary 2]). In particular, the lower-bound involving the
$E_{\beta,\gamma}$–Mutual Information represents the largest among the ones we
consider. Given the lack of a closed-form expression for $E_{\beta,\gamma}$ in
this example the quantities (35) along with ([2, Corollary 2, Eq. (19)] and
[4, Eq. (16)]) and (31) are computed numerically.

Figure 2: Setting: Example 1. The picture shows the behaviour of (31), (35),
[4, Eq. (16)], and[2, Corollary 2, Eq. (19)] as a function of $n$. The values
of $E_{0.75,2.2}(W,X^{n})$ for each $n$ are computed numerically. Here, unlike
in Figure 1 where parameters are optimized, the values are fixed to
$\gamma=2.2,\beta=0.75$ and $p=2$.

###  IV-B Gaussian prior with Gaussian noise in $d$ dimensions

######  Example 2.

Assume that $W\sim N(0,\sigma^{2}_{W})$ and that for $i\in[n]$,
$X_{i}=W+Z_{i}$ where $Z_{i}\sim N(0,\sigma^{2})$. Assume also that the loss
is s.t. $\ell(w,\hat{w})=|w-\hat{w}|$.

Using the estimator $\hat{W}=\mathbb{E}[W|\bar{X}]$ with
$\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}\sim\mathcal{N}(0,\frac{\sigma^{2}}{n})$,
one has that
$R\leq\sqrt{\sigma_{W}^{2}/\left(1+n\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)}$.
Moreover, the small-ball probability can be upper-bounded as follows

$\displaystyle L_{W}(\rho)$
$\displaystyle\leq\left(\sup_{w\in\mathbb{R}}P_{W}(w)\right)\left(\int_{-\rho}^{\rho}1du\right)=\frac{2\rho}{\sqrt{2\pi\sigma_{W}^{2}}}.$
(36)

Once again the largest lower bound on the risk, in the family of bounds
provided by Corollary 1, can be expressed as follows

$R\\!\geq\\!\sup_{\rho>0}\sup_{p>1}\rho\\!\left(\\!\\!1-\left(\\!\\!\frac{2\rho}{\sqrt{2\pi\sigma_{W}^{2}}}\\!\\!\right)^{\frac{p-1}{p}}\\!\\!\\!\\!\left(\\!(p-1)\mathcal{H}_{p}(W,X^{n})\\!+\\!1\\!\right)\\!^{\frac{1}{p}}\\!\\!\right).$
(37)

To compute the Hellinger information, we make use of the following lemma:

######  Lemma 2.

Let $W\sim\mathcal{N}(0,\sigma_{W}^{2}I_{d})$ and
$Z\sim\mathcal{N}(0,\sigma^{2}I_{d})$ be two Gaussian random variables, where
$I_{d}$ denotes the $d\times d$ identity matrix. Moreover, let $X=W+Z$ and
$p>1$. Then

$(p-1)(\mathcal{H}_{p}(W,X)+1)=\left(\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{p}}{1+(2-p)p\frac{\sigma_{W}^{2}}{\sigma^{2}}}\right)^{\frac{d}{2}}.$
(38)

In particular, with $p=3/2$ and $d=1$, one recovers:

$\frac{1}{2}(\mathcal{H}_{3/2}(W,X)+1)=\sqrt{\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{3}{2}}}{1+\frac{3\sigma_{W}^{2}}{4\sigma^{2}}}}.$
(39)

###### Proof.

See Appendix -E. ∎

Setting $p=3/2$ in (37) leads to the following result:

######  Corollary 4.

Consider the setting described in Example 2. The Bayesian risk is lower-
bounded by

$R\geq\frac{81\sqrt{2\pi}}{2048}\sqrt{\frac{\sigma_{W}^{2}}{1+n\frac{\sigma_{W}^{2}}{\sigma^{2}}}}.$
(40)

###### Proof.

Given that $\bar{X}$ is a sufficient statistic we have that
$\mathcal{H}_{p}(W,X^{n})=\mathcal{H}_{p}(W,\bar{X})$. Plugging this choice of
$\bar{X}$ in (39), substituting in (37), and then optimizing over $\rho$ (cf.
Eq. (45) ), yields the statement after some algebraic manipulations. ∎

Note that (40) matches the upper-bound up to a constant factor, and provides a
strengthening of the bounds obtained in [2, Corollary 1]. One can, as in
Example 1, repeat the analysis with the $f_{\beta,\gamma}$–Divergence instead
of the $f_{p}$–Divergence. In particular for the case $\beta=0.75$ and
$\gamma=2.2$, Equation (24) in this example can be expressed as

$\displaystyle R$
$\displaystyle\geq\sup_{\rho>0}\rho\left(1-\frac{4}{3}\left(E_{0.75,2.2}(W,X^{n})+\frac{4.4\rho}{\sqrt{2\pi\sigma_{W}^{2}}}\right)\right)$
(41)
$\displaystyle=\frac{5\sqrt{2\pi\sigma_{W}^{2}}(0.75-E_{0.75,2.2}(W,X^{n}))^{2}}{66},$
(42)

where the optimization over $\rho$ stems from Appendix A.

Figure 3: Setting: Example 2 with $\sigma_{W}^{2}=1$ and $\sigma^{2}=2$. The
picture shows the behaviour of (40), (42), [4, Eq. (21)], and [2, Corollary 1,
Eq. (16)] as a function of $n$. The values of $E_{0.75,2.2}(W,X^{n})$ for each
$n$ are computed numerically. Here, the values of the parameters are fixed to
$\gamma=2.2,\beta=0.75,\alpha=2$ and $p=1.5$.

Similarly to Example 1, we numerically evaluate (42) and compare it with [2,
Corollary 1, Eq. (16)], [4, Eq. (21)] (with $\alpha=2$), and (40). Figure 3
shows the resulting lower-bounds as a function of the number of samples $n$.
One can observe similar behaviors when comparing with the results from
previous example: the bounds retrieved through the $\mathcal{H}_{p}$– and
$E_{\beta,\gamma}$–Divergences are able to both improve on the lower-bound
relying on Shannon’s Mutual Information. Once again, Equation (27) gives the
largest lower-bound in this example, while Sibson’s $\alpha$-Mutual
Information is still able to provide a stronger result than (22).

###  -C Maximization over $\rho$

In the two examples considered, one can notice that the lower-bounds resulting
from Corollaries 1 and 2 have the following form

$\sup_{\rho>0}\rho(1-c\rho^{t}-b),$ (43)

for some $c,t,b\geq 0$. Letting $h(\rho):=\rho(1-c\rho^{t}-b)$, the optimal
value is found by setting $h^{\prime}(\rho_{\star})=0$, which yields

$1-(t+1)c\rho_{\star}^{t}-b=0\iff\rho_{\star}=\left(\frac{1-b}{(t+1)c}\right)^{\frac{1}{t}}.$
(44)

Since $h^{\prime\prime}(\rho_{\star})=-t(t+1)c\rho_{\star}^{t-1}\leq 0$, this
ensures $\rho_{\star}$ is a maximum. Substituting $\rho^{\star}$ back in (43),
we find

$\sup_{\rho>0}\rho(1-c\rho^{t}-b)=\frac{t}{c^{\frac{1}{t}}}\left(\frac{1-b}{t+1}\right)^{1+\frac{1}{t}}.$
(45)

###  -D Proof of Lemma 1

In order to prove Lemma 1, let us introduce a technical lemma which will be
useful in subsequent computations.

######  Lemma 3 ([12, Eq. (5.39), p.187]).

Let $n\geq 0$ be a positive integer. Then

$\sum_{k=0}^{n}\binom{2k}{k}\binom{2(n-k)}{n-k}=4^{n}.$ (46)

We can now move on and prove Lemma 1 which we restate here for reference.

######  Lemma.

Consider the setting described in Example 1 i.e., $W\sim U[0,1]$ and
$X_{i}|\\{W\\!=\\!w\\}\sim\text{Ber}(w)$ for each $i\in[n]$. Then for every
$p>1$,

$\displaystyle(p-1)($ $\displaystyle\mathcal{H}_{p}(W,X^{n})+1)$
$\displaystyle=(n+1)^{p-1}\sum_{k=0}^{n}\binom{n}{k}^{p}\frac{\Gamma(kp+1)\Gamma((n-k)p+1)}{\Gamma(np+2)}.$

###### Proof.

In this specific setting, one has that
$P_{X^{n}|W=w}(x^{n})=w^{k}(1-w)^{(n-k)}$ where $k=\sum_{i=1}^{n}x_{i}$, i.e.,
the hamming weight of $x^{n}$. As per assumption $P_{W}(w)=\mathds{1}\\{0\leq
w\leq 1\\}$ and consequently one has that
$P_{W|X^{n}=x^{n}}(w)=(n+1)\binom{n}{k}(1-w)^{n-k}w^{k}$. Thus we can compute

$\displaystyle(p-1)\mathcal{H}_{p}(W,X^{n})+1$ $\displaystyle=$ (47)
$\displaystyle\sum_{x^{n}\in\\{0,1\\}^{n}}P_{X^{n}}(x^{n})\int_{0}^{1}P_{W}(w)\left(\frac{P_{W|X^{n}=x^{n}}(w)}{P_{W}(w)}\right)^{p}dw$
$\displaystyle=$ (48)
$\displaystyle\sum_{k=0}^{n}\frac{1}{n+1}\int_{0}^{1}\left((n+1)\binom{n}{k}w^{k}(1-w)^{(n-k)}\right)^{p}dw$
$\displaystyle=$ (49)
$\displaystyle(n+1)^{p-1}\sum_{k=0}^{n}\binom{n}{k}^{p}\frac{\Gamma(kp+1)\Gamma((n-k)p+1)}{\Gamma(np+2)},$
(50)

where (48) follows from the definition of Hellinger divergence and (50) uses
the identity relating the Beta function with the Gamma function:

$\mathrm{Beta}(x,y)=\int_{0}^{1}t^{x-1}(1-t)^{y-1}dt=\frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}.$
(51)

If $p=2$ one has that:

$\displaystyle\chi^{2}(W,X^{n})+1$
$\displaystyle=(n+1)\sum_{k=0}^{n}\binom{n}{k}^{2}\frac{(2k)!(2(n-k))!}{(2n+1)!}$
(52)
$\displaystyle=\frac{n+1}{(2n+1)}\sum_{k=0}^{n}\frac{(n!)^{2}(2k)!(2(n-k))!}{(k!)^{2}((n-k)!)^{2}(2n)!}$
(53)
$\displaystyle=\frac{n+1}{(2n+1)\binom{2n}{n}}\sum_{k=0}^{n}\binom{2k}{k}\binom{2(n-k)}{n-k}$
(54) $\displaystyle=\frac{n+1}{2n+1}\cdot\frac{4^{n}}{\binom{2n}{n}}$ (55)
$\displaystyle\leq\frac{2}{3}\cdot\frac{8\sqrt{\pi n}}{7}$ (56)
$\displaystyle=\frac{16\sqrt{\pi n}}{21},$ (57)

where (55) follows from Lemma 3. To obtain (56), we use
$\frac{n+1}{2n+1}\leq\frac{2}{3}$ for $n\geq 1$ and Stirling’s approximation
to get $\binom{2n}{n}\sim\frac{4^{n}}{\sqrt{\pi n}}$ and retrieve
$\binom{2n}{n}\geq\frac{8}{7}\cdot\frac{4^{n}}{\sqrt{\pi n}}$ for $n\geq 1$. ∎

###  -E Proof of Lemma 2

Let us re-state the result for ease of reference.

######  Lemma.

Let $W\sim\mathcal{N}(0,\sigma_{W}^{2}I_{d})$ and
$Z\sim\mathcal{N}(0,\sigma^{2}I_{d})$ be two Gaussian random variables, where
$I_{d}$ denotes the $d\times d$ identity matrix. Moreover, let $X=W+Z$ and
$p>1$. Then

$(p-1)(\mathcal{H}_{p}(W,X)+1)=\left(\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{p}}{1+(2-p)p\frac{\sigma_{W}^{2}}{\sigma^{2}}}\right)^{\frac{d}{2}}.$

In particular, with $p=3/2$ and $d=1$, one recovers:

$\frac{1}{2}(\mathcal{H}_{3/2}(W,X)+1)=\sqrt{\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{3}{2}}}{1+\frac{3\sigma_{W}^{2}}{4\sigma^{2}}}}.$

###### Proof.

First, note that $X|\\{W=w\\}\sim\mathcal{N}(w,\sigma^{2}I_{d})$. Since the
Hellinger information of order $p$ is defined as
$\mathcal{H}_{p}(W,X)=\mathbb{E}_{P_{W}P_{X}}\left[f\left(\frac{dP_{WX}}{dP_{W}P_{X}}\right)\right]$
with $f(t)=\frac{t^{p}-1}{p-1}$, we have that

$\displaystyle(p-1)\mathcal{H}_{p}$ $\displaystyle(W,X)+1$
$\displaystyle=\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}P_{W}(w)P_{X}(x)\left(\frac{P_{X|W=w}(x)}{P_{X}(x)}\right)^{p}dwdx$
(58)
$\displaystyle=\int_{\mathbb{R}^{d}}P_{X}(x)^{1-p}\int_{\mathbb{R}^{d}}P_{W}(w)P_{X|W=w}(x)^{p}dwdx.$
(59)

Let us denote the inner-most integral in (59) as $G_{p}(x)$. One has that:

$\displaystyle G_{p}(x):$
$\displaystyle=\int_{\mathbb{R}^{d}}P_{{W}}({w})P_{{X}|{W}={w}}({x})^{p}d{w}$
(60)
$\displaystyle=\left(\frac{(2\pi\sigma^{2})^{-p}}{2\pi\sigma_{W}^{2}}\right)^{\frac{d}{2}}\int_{\mathbb{R}^{d}}e^{-\frac{\|{w}\|_{2}^{2}}{2\sigma_{W}^{2}}-\frac{p\|{w}-{x}\|_{2}^{2}}{2\sigma^{2}}}d{w}.$
(61)

Let
$I_{p}(x):=\int_{\mathbb{R}^{d}}e^{-\frac{\|{w}\|_{2}^{2}}{2\sigma_{W}^{2}}-\frac{p\|{w}-{x}\|_{2}^{2}}{2\sigma^{2}}}d{w}$
(and thus,
$G_{p}(x)=\left(\frac{(2\pi\sigma^{2})^{-p}}{2\pi\sigma_{W}^{2}}\right)^{\frac{d}{2}}I_{p}(x)$)
one has

$\displaystyle I_{p}(x)$
$\displaystyle=\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\sigma^{2}}\left(p\|{x}\|_{2}^{2}-2p{x}^{\top}{w}+\left(\frac{\sigma^{2}}{\sigma_{W}^{2}}+p\right)\|{w}\|_{2}^{2}\right)}d{w}$
(62)
$\displaystyle=e^{\frac{-p\cdot\|{x}\|_{2}^{2}}{2\sigma^{2}}}\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\sigma^{2}}\left(-2p{x}^{\top}{w}+\left(\frac{\sigma^{2}}{\sigma_{W}^{2}}+p\right)\|{w}\|_{2}^{2}\right)}d{w}$
(63)

Let us now add and subtract $c\|x\|_{2}^{2}$ with
$c=-p\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{-1}$ in the exponent
in Equation (63):

$\displaystyle I_{p}(x)$
$\displaystyle=e^{{\frac{c\|{x}\|_{2}^{2}}{2\sigma^{2}}}}\int_{\mathbb{R}^{d}}e^{-\frac{\frac{\sigma^{2}}{\sigma_{W}^{2}}+p}{2\sigma^{2}}\left(\left\|{w}-\sqrt{\frac{p+c}{\frac{\sigma^{2}}{\sigma_{W}^{2}}+p}}{x}\right\|_{2}^{2}\right)}d{w}$
(64)
$\displaystyle=\exp\left(-{\frac{p\cdot\|{x}\|_{2}^{2}}{2\sigma^{2}\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)}}\right)\left(2\pi\frac{\sigma^{2}}{\frac{\sigma^{2}}{\sigma_{W}^{2}}+p}\right)^{\frac{d}{2}}.$
(65)

Substituting (65) in (61) gives

$G_{p}(x)=\frac{1}{(2\pi\sigma^{2})^{\frac{dp}{2}}}e^{-\frac{p\|{x}\|_{2}^{2}}{2\left(\sigma^{2}+p\sigma_{W}^{2}\right)}}\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{-\frac{d}{2}}.$
(66)

Finally, if we plug in (66) in (59), we retrieve that:

$\displaystyle(p-1)\mathcal{H}_{p}(W,X)+1$
$\displaystyle=\int_{\mathbb{R}^{d}}P_{{X}}({x})^{1-p}\frac{1}{(2\pi\sigma^{2})^{\frac{dp}{2}}}e^{-\frac{p\|{x}\|_{2}^{2}}{2\left(\sigma^{2}+p\sigma_{W}^{2}\right)}}\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{-\frac{d}{2}}d{x}$
(67)
$\displaystyle=\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d(p-1)}{2}}}{(2\pi\sigma^{2})^{\frac{d}{2}}\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}e^{\frac{(p-1)\|{x}\|_{2}^{2}}{2\left(\sigma^{2}+\sigma_{W}^{2}\right)}-\frac{p\|{x}\|_{2}^{2}}{2\left(\sigma^{2}+p\sigma_{W}^{2}\right)}}d{x}$
(68)
$\displaystyle=\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d(p-1)}{2}}}{(2\pi\sigma^{2})^{\frac{d}{2}}\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}e^{-\frac{\|{x}\|_{2}^{2}}{2}\left(\frac{1-p}{\sigma^{2}+\sigma_{W}^{2}}+\frac{p}{\sigma^{2}+p\sigma_{W}^{2}}\right)}d{x}$
(69)
$\displaystyle=\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d(p-1)}{2}}}{(2\pi\sigma^{2})^{\frac{d}{2}}\left(1+p\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d}{2}}}\left(\frac{2\pi}{\frac{1-p}{\sigma^{2}+\sigma_{W}^{2}}+\frac{p}{\sigma^{2}+p\sigma_{W}^{2}}}\right)^{\frac{d}{2}}$
(70)
$\displaystyle=\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{\frac{d(p-1)}{2}}}{\left(\sigma^{2}+p\sigma_{W}^{2}\right)^{\frac{d}{2}}}\left(\frac{1}{\frac{1-p}{\sigma^{2}+\sigma_{W}^{2}}+\frac{p}{\sigma^{2}+p\sigma_{W}^{2}}}\right)^{\frac{d}{2}}$
(71)
$\displaystyle=\left(\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{p-1}}{\frac{(1-p)\left(\sigma^{2}+p\sigma_{W}^{2}\right)}{\sigma^{2}+\sigma_{W}^{2}}+p}\right)^{\frac{d}{2}}$
(72)
$\displaystyle=\left(\frac{\left(1+\frac{\sigma_{W}^{2}}{\sigma^{2}}\right)^{p}}{1+(2-p)p\frac{\sigma_{W}^{2}}{\sigma^{2}}}\right)^{\frac{d}{2}},$
(73)

which concludes the proof. ∎

## References

  * [1] Y. Zhang, J. Duchi, M. I. Jordan, and M. J. Wainwright, “Information-theoretic lower bounds for distributed statistical estimation with communication constraints,” in _Advances in Neural Information Processing Systems_ , C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, Eds., vol. 26. Curran Associates, Inc., 2013, pp. 2328–2336.
  * [2] A. Xu and M. Raginsky, “Information-theoretic lower bounds on bayes risk in decentralized estimation,” _IEEE Transactions on Information Theory_ , vol. 63, no. 3, pp. 1580–1600, 2017.
  * [3] S. Asoodeh, M. Aliakbarpour, and F. P. Calmon, “Local differential privacy is equivalent to contraction of an $f$-divergence,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 545–550.
  * [4] A. R. Esposito and M. Gastpar, “Lower-bounds on the bayesian risk in estimation procedures via Sibson’s $\alpha$-mutual information,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 748–753.
  * [5] F. Liese and I. Vajda, “On divergences and informations in statistics and information theory,” _IEEE Trans. Inf. Theor._ , vol. 52, no. 10, pp. 4394–4412, 2006. [Online]. Available: http://dx.doi.org/10.1109/TIT.2006.881731
  * [6] I. Sason, “On f-divergences: Integral representations, local behavior, and inequalities,” _Entropy_ , vol. 20, no. 5, 2018. [Online]. Available: https://www.mdpi.com/1099-4300/20/5/383
  * [7] Te Sun Han and S. Amari, “Statistical inference under multiterminal data compression,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2300–2324, 1998.
  * [8] O. Shamir, “Fundamental limits of online and distributed algorithms for statistical learning and estimation,” in _Advances in Neural Information Processing Systems_ , Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, Eds., vol. 27. Curran Associates, Inc., 2014, pp. 163–171.
  * [9] X. Chen, A. Guntuboyina, and Y. Zhang, “On bayes risk lower bounds,” _J. Mach. Learn. Res._ , vol. 17, no. 1, p. 7687–7744, jan 2016.
  * [10] I. Csiszár, “A class of measures of informativity of observation channels,” _Periodica Mathematica Hungarica_ , vol. 2, pp. 191–213, 1972\.
  * [11] A. R. Esposito, M. Gastpar, and I. Issa, “Generalization error bounds via Rényi-, $f$-divergences and Maximal Leakage,” _IEEE Transactions on Information Theory_ , vol. 67, no. 8, pp. 4986–5004, 2021.
  * [12] R. L. Graham, D. E. Knuth, and O. Patashnik, _Concrete Mathematics: A Foundation for Computer Science_. Reading: Addison-Wesley, 1989.


González Flores, Guilmer et al

Guilmer González Flores, Laboratorio de Cómputo Científico, Departamento de
Matemáticas, Facultad de Ciencias, Universidad Nacional Autónoma de México,
Ciudad universitaria, 04510 Ciudad de México, México.
and

# New quality measures for quadrilaterals and new discrete functionals for
grid generation

González Flores  Guilmer  Barrera Sánchez  Pablo  Facultad de Ciencias,
Universidad Nacional Autónoma de México, CDMX, México
<EMAIL_ADDRESS><EMAIL_ADDRESS>G. González Flores  P.
Barrera Sánchez

(26 April 2016; 6 June 2016; 6 June 2016)

###### Abstract

[Summary]In this paper, we review some grid quality metrics 1, 2, 3, 4, 5 and
define some new quality measures for quadrilateral elements. Usually, a
maximum value of a quality measure corresponds to the minimum value of the
energy density over the grid 6.

We also define new discrete functionals which are implemented as objective
functions in an optimization-based method for quadrilateral grid generation
and improvement. These functionals are linearly combined with a discrete
functional whose domain has an infinite barrier at the boundary of the set of
unfolded grids like $S_{\omega,\epsilon}(G)$, see 7, in order to preserve
convex grid cells in each step of the optimization process.

, and (2022), New quality measures for quadrilaterals and new discrete
functionals for grid generation, xxxxx., xxxx.

###### keywords:

mesh generation, quality measure, aspect ratio, quality improvement

††articletype: RESEARCH ARTICLE00footnotetext: Abbreviations: ANA, anti-
nuclear antibodies; APC, antigen-presenting cells; IRF, interferon regulatory
factor

##  1 Introduction

There is a relatively large number of papers on numerical grid generation of
unstructued grids. There is also a special interest in studying meshes formed
by triangular elements. Our interest here is to generate structured meshes
with quadrilateral elements, however, all the disscussion can be applied to
unstructured meshes.

The simplest way to generate a structured mesh is by interpolation of the
boundaries, but it is difficult to ensure that the mesh thus obtained is a
convex one. In 7, the authors made a review of some functionals and conditons
that guarantee the existence of optimal meshes which are $\epsilon$-convex
over irregular planar regions. Our interest now is to improve mesh quality via
the control the shape of the elements. The improvement of mesh quality can be
done in two ways:

Clean-up.

Basically it consists in elimination, insertion and reconnection of nodes in
order to eliminate the worst elements. Some authors call that this procedure
as topological optimization in the sense that the connectivity of the nodes is
removed to obtain an optimal configuration.

Smoothing.

It consists on node reposition without changing the connectivity of the
elements.

In both cases, the goal is to obtain a quality mesh with a low number of
distorted elements. To achieve this goal for a quadrilateral it is neccesary
to define an ad hoc quality measure.

######  Definition 1.

We say that a real valued function $\mu(Q)$ over a quadrilateral $Q$ is a
quality measure in the sense of Field-Oddy, if it

  1. 1)

has the ability to detect degenerate elements;

  2. 2)

is bounded and continuous;

  3. 3)

is independent of scale;

  4. 4)

is normalized;

  5. 5)

and it is invariant under rigid transformations;

For practical purposes it is convenient to define an acceptability interval
$[\mu_{0},1]$ for the quality value when a quadrilateral has a suitable shape.
When the quality value lies outside this interval the quadrilateral is
distorsioned.

In this work we are interested in identifying the shape of the cells and
quantifying the distortion of a quadrilateral when it is not a square or a
rectangle. For this purpose, we will review the most used quality measures for
rectangles and then we will propose new quality measures.

##  2 Background

Following the ideas behind the quality measures reported for triangles, it is
straightforward to define some figures that measure the shape of the
quadrilaterals. One of these is the aspect ratio, which is defined by
comparing with the ideal case when the quadrilateral is a rectangle: the ratio
of the largest to the smallest sides. An estimator for this ratio was
discussed in 1987 by Robinson 1. The idea is to associate a rectangle to the
convex quadrilateral: a rectangle passing through the midpoints of the sides
of the quadrilateral, see the figure bellow.

Figure 1: A rectangle associated with a quadrilateral.

This idea is usual in continuum mechanics. Robinson proposes a practical way
of calculating it by means of the bilinear mapping between the unit square and
the quadrilateral

$\displaystyle x$ $\displaystyle=$ $\displaystyle
e_{1}+e_{2}\xi+e_{3}\eta+e_{4}\xi\eta,$ (1) $\displaystyle y$ $\displaystyle=$
$\displaystyle f_{1}+f_{2}\xi+f_{3}\eta+f_{4}\xi\eta,$ (2)

which yields

$\mbox{aspect
ratio}=\max\left\\{\frac{e_{2}}{f_{3}},\frac{f_{3}}{e_{2}}\right\\}.$

The associated rectangle has sides which are parallel to the coordinate axes
and pass through the midpoints of the sides of the quadrilateral. In spite of
its simplicity, this analytic representation is not satisfactory since it
depends on a orthogonal coordinate system. In 2000, Field 3 reviewed this
definition and suggested to calculate the aspect ratio of Robinson
orthogonalizing the main axes and proposes a quality measure to detect
squares.

In 1989, Lo 2 reviewed the quality measure for triangules $T(a,b,c)$ with side
lengths $l_{1}$, $l_{2}$ and $l_{3}$

$g_{i}=4\sqrt{3}\frac{\mbox{\'{a}rea}(T_{i})}{l_{1}^{2}+l_{2}^{2}+l_{3}^{2}}$

which attains its optimum value in equilateral triangles and proposed again to
calculate each one of those values over the four $T_{i}$ triangles which are
defined by the sides and diagonals of a quadrilateral, but reordering these
quantitites in such a way that

$g_{1}\leq g_{2}\leq g_{3}\leq g_{4}$

and use

$\mu(Q)=\frac{g_{1}g_{2}}{g_{3}g_{4}}.$

as quality measure. Lo points out that the optimal value of 1 is obtained for
rectangles. This is a quality measure because it is continuous, bounded and
identifies degenerate and even non-convex quadrilaterals. The measure that Lo
uses for triangles is the reciprocal of the number of condition of a linear
mapping $\mu(Q)=1/\kappa_{2}(Q)$, that Knupp 4 used in 2001 to measure the
distortion of the elements. Locally, Lo’s measure may have more critical
points which can be far from representing a rectangle.

Another measure of quality, described by van Rens et al. 8 for quadrilaterals,
is given as follows: compute the inner angles $\theta_{k}$ and define

$\mu(Q)=\prod_{k=1}^{4}\left(1-\left|\frac{\frac{\pi}{2}-\theta_{k}}{\frac{\pi}{2}}\right|\right).$

This function is continuous, dimensionless and $0\leq\mu(Q)\leq 1$. One can
see that $\mu(Q)=0$ if $Q$ is a triangle and $\mu(Q)=1$ only if $Q$ is a
rectangle.

In 2012, Remacle et al. 5 described the Blossom-Quad algorithm to construct a
non-structured mesh with quadrilaterals elements obtained from a previous
triangulation and used a cost-function to produce a quality mesh. They used

$\mu(Q)=\max\left\\{1-\frac{2}{\pi}\max_{k}\left\\{|\frac{\pi}{2}-\theta_{k}|\right\\},0\right\\}$

and observed that the value of this function is 1 the $Q$ is a perfect
quadrilateral and 0 if any of the angles is greater than or equal to $\pi$, id
est when the quadrilateral degenerates into a triangle or is nonconvex. This
function is also a quality measure.

As noted, unlike other measures for rectangles we have discussed up to this
point, the two last ones do not depend neither on the shape of the
quadrilaterals, nor the aspect ratio or proportion of their sides; they only
measure how near or far away is a quadrilateral from being a rectangle using
only the internal angles.

Another function based on inner angles was proposed by Wu 9. This author used
the same idea of Lo: to order the inner angles $\theta_{i}$ so that
$\theta_{1}\leq\theta_{2}\leq\theta_{3}\leq\theta_{4}$ and define

$\mu(Q)=\frac{\theta_{1}\theta_{2}}{\theta_{3}\theta_{4}}.$

Wu observed that this function attains its optimal value of 1 on rectangles.
However, this is not a good measure in the sense of Field-Oddy, since it is
not capable of detecting degenerate quadrilaterals.

##  3 New quality measures

In the previous section, we have reviewed some measures that characterize
rectangles and we have also pointed out some intervals of acceptability to
decide whether that a quadrilateral is close to having the desired shape is
distorted. However, we have not noticed how it is that square or rectangle.

###  3.1 Minrect 2015

A very interesting problem in computational geometry is the following: given a
cloud of points, calculate the rectangle of the minimum area that contains
them. It is known that this problem can be raised directly on the convex hull
of the cloud of points and therefore the problem can be regarded as to
calculate a rectangle of minimum area that contains a polygon convex.

We propose to use the rectangle of minimum area to define a distortion measure
of the quadrilateral in the sense that measures how close or far is a
quadrilateral $Q$ of being a rectangle (see 2(a)).

(a) (b)

Figure 2: (a) The rectangle of minimum area for one quadrilateral. (b)
Comparación entre aspect ratio of Robinson and the aspect ratio of rectangle
of minimum area

On one hand, the cell area $a_{c}$, is less than the rectangle area; that is,
$a_{c}\leq a_{R}$, and is easy to see that

$\frac{2a_{c}-a_{R}}{a_{R}}\leq 1;$

see Lassak 10 for the proof. The quotient thus defined reaches its maximum
value of 1 on rectangles. Therefore, we propose the value

$\mu(Q)=\frac{2a_{c}-a_{R}}{a_{R}}$

as a quality measure to characterize rectangles.

One must note that $\mu(Q)$ is a good quality measure according to Field-Oddy,
and $\mu(Q)=0$ when $Q$ is a triangle.

Another good quality measure in this sense is

$\mu(Q)=\frac{2a_{-}}{a_{R}}$

where

$a_{-}=\min\left\\{a_{1},\,a_{2},\,a_{3},\,a_{4}\right\\}$ (3)

is the minimum area between the four triangles defind by taking the four
vertices of a quadrilateral into groups of three.

###  3.2 New aspect ratio

Using the rectangle of minimum area for $Q$, we propose to use the ratio of
the largest to the smallest side as aspect ratio. This measures is invariant
under rigid and scaling transformations.

This measure is better than the Robinson aspect ratio. It is easy to construct
an example for which the Robinson aspect ratio 1 but very distorted

Example : For the quadrilateral $A(3.53,10.21),B(-10,-4)$, $C(11.81,-1.38)$ y
$D(9.27,11.94)$ the Robinson’s aspect ratio is $1.00$ and using the rectangle
of minimum area our aspect ratio is $1.62$. See the figure 2(b).

###  3.3 Rectangles 2015

As we have discussed, some measures to characterize rectangles are based on
the inner angles. Another way to do this is to ask $Q$ to be a parallelogram
and one of its inner angles to be a right one. This is, we use a measure that
imposes a particular condition of a rectangle instead of one on the form of
$Q$ .

Our interest is to characterize the rectangles geometrically. A well known
result in the literature is as follows:

######  Theorem 1.

Let $Q$ be a quadrilateral of vertices $A,B,C$ and $D$ whose sides are $a,b,c$
and $d$. The quadrilateral $Q$ is a rectangle if and only if the area of the
quadrilateral is written as

$a_{R}=\frac{1}{2}\sqrt{(a^{2}+c^{2})(b^{2}+d^{2})}$

The proof of this result can be found in Josefsson 11. The interesting fact
about this theorem is that it provides of an analytical expression of the area
of a hypothetical rectangle formed by the sum of the square of the opposite
sides of $Q$ and compare the square of the area of $Q$ to identify how far if
is from being a rectangle.

On the other hand, following the proof of the theorem, it is easy to see that
the area $a_{c}$ of any convex quadrilateral satisfies

$2a_{c}\leq\sqrt{(a^{2}+c^{2})(b^{2}+d^{2})}.$

Using this idea we propose the measure

$\mu(Q)=\frac{2a_{-}}{\sqrt{(a^{2}+c^{2})(b^{2}+d^{2})}}$

where $a_{-}$ is defined in equation (3).

This is a good quality measure in the Field-Oddy sense, since it is
continuous, bounded, and capable of indentifying degenerate quadrilaterals (to
triangle) as well as to identify if a quadrilateral is non-convex. This
measure reaches its optimal value of 1 for rectangles.

An acceptability interval to consider that the quadrilateral is rectangle
under this measure is $[.95,\,1]$.

###  3.4 Cuadrados: Harmonic mean 2017

An ideal mesh is one in which its cells are close to being squares. If
$\mu(T)$ is a good quality measure for triangles, the harmoic mean of the four
triangles $T_{i}$

$\mu(Q)=\sigma\frac{4}{\sum_{i=1}^{4}\frac{1}{\mu(T_{i})}}$ (4)

is a good quality measure for quadrilaterals, because it is continuous,
bounded, invariant under rigid and scaling transformations and identifies
degenerate and even non-convex quadrilaterals since it inherits those
properties from $\mu(T)$. Here $\sigma$ is a normalization parameter.

Rewriting (4) we obtain

$\mu(Q)=\frac{4\sigma\mu(T_{1})\mu(T_{2})\mu(T_{3})\mu(T_{4})}{\mu(T_{2})\mu(T_{3})\mu(T_{4})+\mu(T_{1})\mu(T_{3})\mu(T_{4})+\mu(T_{1})\mu(T_{2})\mu(T_{4})+\mu(T_{1})\mu(T_{2})\mu(T_{3})}$
(5)

To characterize squares we require a property $\mu(T)$ as seen from

######  Theorem 2.

If $\mu(T)$ is a good quality measure for triangles according to Field-Oddy in
which for isosceles triangle the highest energy among all right triangles is
achieved, sothe harmoic mean (5), characterize squares at their maximum value.

The proof is simple, and can be reviewed at 12 it is based on the fact that
the four triangles must be congruent to have the same energy.

Some measures $\mu(T)$ for triangles with those properties are

$\mu_{1}(T)=4\sqrt{3}\frac{A}{l_{1}^{2}+l_{2}^{2}+l_{3}^{2}},\quad\mu_{2}(T)=2\frac{r}{R},\quad\mu_{3}(T)=\frac{4\sqrt{3}}{9}\frac{A}{R^{2}},\quad\mu_{4}(T)=\frac{4}{\sqrt{3}}\frac{A}{l_{\max}^{2}}$

whree $\mu_{1}(T)$ is proposed by Joe, 13, $\mu_{2}(T)$ is the radius ratio
measure, $\mu_{3}(T)$ is described by Shewchuk y $\mu_{4}(T)$ is the
Cavendish’s measure, see 14.

(a) (b)

Figure 3: Level curves for (5) using (a) $\mu_{1}(T)$, (b) radius ratio
$\mu_{2}(T)$.

##  4 Grid quality improvement

###  4.1 A distorsion measure

In general, if $\mu(Q)$ is a good quality measure for quadrilaterals, a way of
measuring the distortion of an $\epsilon$-convex quadrilateral $Q$ with
respect to $\mu(Q)$ is using

$f(Q)=\frac{1}{\mu(Q)}$

because if $f(Q)$ is much greater than 1, the cell will be far from the value
for which $\mu(Q)$ characterizes the geometric shape of the cell $Q$ (square,
rectangle, parallelogram, etc.) and we can say that $Q$ is a distorsioned
quadrilateral with respect to that measure.

Under this idea, the distortion of the mesh $G$ can be measured as the average
of the distortions of all the cells

$F(G)=\frac{1}{Ne}\sum_{k=1}^{Ne}\frac{1}{\mu(Q_{k})}$ (6)

where $Ne$ its the number of the cells. We have in consequence the follow
definition

######  Definition 2.

A grid $\hat{G}$ has better quality than the mesh $\bar{G}$ if

$F(\hat{G})<F(\bar{G})$

where $F(G)$ is a distorsion measure.

As an optimization problem, improving the quality of a G-mesh can be
considered as the problem

$G^{*}=\arg\min_{G}F(G)=\frac{1}{Ne}\sum_{k=1}^{Ne}\frac{1}{\mu(Q_{k})}.$

where the inner node of $G$ are the unknowns. The optimization problem is a
large scale one when mesh dimension $m\times n$ is very large. It is important
to notice that the initial mesh $G_{0}$ must be convex and remain so in each
step of the optimization process.

Usually the quality measures for quadrilaterals are non differentiable
functions, in an optimization process is better to build convex function with
similar characteristics as the quality measure.

##  5 New quality discrete functionals

From the proof of theorem 1 it is easy to see that

$2a_{c}\leq\sqrt{(a^{2}+c^{2})(b^{2}+d^{2})}$

for any convex quadrilateral; then

$f(Q)=\frac{(a^{2}+c^{2})(b^{2}+d^{2})}{4a_{c}^{2}}$

its a positive convex function whose critical points are rectangles. With this
function we can define a discrete functional $F_{R}(G)$ over all the grid
cells

$F_{R}(G)=\frac{1}{Ne}\sum_{k=1}^{Ne}f(Q_{k}).$

In Figure 4 the shape of the surface of $F_{R}$ is sketched.

(a) (b)

Figure 4: Level for (a) $f(Q)$ y (b) $f_{r}(Q)$ where $Q$ has 3 fixed vertices
$(0,0),(2,0)$ and $(0,1)$.

We propose to combine this functional with a convex area functional $S_{w}(G)$
(see 7) to guarantee the convexity of the cells and and that their shape is
close to a rectangle:

$F(G)=(1-\sigma)S_{w}(G)+\sigma F_{R}(G)$

where $\sigma>0$. In addition, the function

$f(Q)=\frac{(a^{2}+c^{2})(b^{2}+d^{2})}{4a_{c}^{2}}$

can be interpreted (by cells) as a normalization (with respect to the
jacobian) of Knupp’s area-orthogonility functional 15

$f_{ao}(Q)=(a^{2}+c^{2})(b^{2}+d^{2}).$

As we have discussed, because quality measures are usually non-differentiable
functions it is difficult to use them as objective function; it is advisable
to design convex and differentiable functions $f(Q)$ whose optimal values also
satisfy $\mu(Q)\approx 1$ for a specific quality measure $\mu(Q)$.

As it is known, a rectangle is a parallelogram where its diagonals are equal
and a quadrilateral is a parallelogram if its diagonals intersect at the
midpoints. In Figure 5, you can see those elements.

Figure 5: Diagonals of a quadrilateral and the segment joining the midpoints
between them.

With this ideas, we propose a convex functional of the form

$F_{p}(G)=\sum_{i,j}\|\frac{{\bf p}_{i,j}+{\bf p}_{i+1,j+1}}{2}-\frac{{\bf
p}_{i+1,j}+{\bf p}_{i,j+1}}{2}\|^{2}$

over all elements of the grid $G$. Locally, this functional has as a critical
point in the cells formed by parallelograms (see Khattri 16). In that paper
Kattri, uses a discrete scheme that coincides with the Laplacian-Isoparametric
scheme of Herrmann 17.

Optimizing $F_{p}(G)$ tries to produce parallelograms, now we define a
discrete functional to obtain rectangles. For each cell of $G$ let us measure
the square of the difference of the square of diagonals

$F_{d}(G)=\sum_{i,j}(\|{\bf p}_{i,j}-{\bf p}_{i+1,j+1}\|^{2}-\|{\bf
p}_{i+1,j}-{\bf p}_{i,j+1}\|^{2})^{2};$

combining both functionals we get

$F_{r}(G)=\alpha F_{p}(G)+\beta F_{d}(G).$

If $\alpha\geq 0,\beta\geq 0$ are appropiately chosen, we obtain a positive
and convex functional which has as a critical point in a mesh formed by
rectangles (including squares). We can always do this if we guarantee that in
each optimization step the mesh is convex.

Therefore, we use $S_{w}(G)$ to guarantee and preserve the convexity of the
mesh, and combine with the latter fuctional to obtain a convex mesh and over
irregular regions we will obtain meshes whose cells are close to being
rectangles.

$F(G)=(1-\sigma)S_{\omega}(G)+\sigma F_{r}(G).$

##  6 Examples

For both functionals we can obtain optimal grids whose cells have a very large
aspect ratio, see the Figure 6

Figure 6: A mesh over the Strait of Gibraltar.

To control the aspect ratio we propose use an area (volume) distortion
measures functional

$F_{A}(G)=\sum_{q=1}^{N}\frac{1}{\alpha(\triangle_{q})^{2}}+\delta\alpha(\triangle_{q})^{2}$

over all the $N$ signed areas of all the grid cells triangles. Here $\delta>0$
is an adecuate value. This distortion measures have a barrier on the boundary
of the set of grids consisting of convex quadrilateral cells and its very
similar to one proposed by Garanzha 18, but now we have a better control of
the global distribution of the area.

---
(a)
(b)
Figure 7: Color map of: (a) Rectangles 2015 quality measure (b) Minrect 2015
quality measure.
---
(a)
(b)
Figure 8: Color map of: (a) Rectangles 2015 quality measure (b) Minrect 2015
quality measure.

##  7 Conclusions

In this work we have described new quality measures for quadrilaterals, that
help us to improve mesh and aspect ratio. Also we have proposed new
functionals for grid generation that our computational tests, give us bases
for using as alternative for area-orthogonal grid generation.

## Acknowledgements

We want to thank Posgrado en Ciencias Matemáticas of UNAM for the financial
support for this work.

### ORCID

Guilmer González Flores https://orcid.org/0000-0001-7390-9088

## References

  * 1 Robinson J. Some new distortion measures for quadrilaterals. Finite Elements in Analysis and Design 1987; 3: 183–197.
  * 2 Lo S. Generating quadrilateral elements on plane and over curved surfaces. J. Comp. & Structures 1989; 31(3): 421–426.
  * 3 Field D. Qualitative measures for initial meshes. Int. J. Numer. Meth. Engng. 2000; 47: 887–906.
  * 4 Knupp P. Algebraic mesh quality metrics. SIAM J.. Sci. Comp. 2001; 23: 193–218.
  * 5 Remacle J.-F. LJSBMEJA, C. G. Blossom-Quad: a non-uniform quadrilateral mesh generator using a minimum cost perfect matching algorithm. Int. J. Numer. Meth. Engng 2012; 89(9): 1102–1119.
  * 6 Ivanenko S. Control of cell shapes in the course of grid generation. Comput. Maths. Math. Phys. 2000; 40(11): 1596–1684.
  * 7 Barrera-Sánchez P, González-Flores G. Smoothness and Convex Area Functional–Revisited. SIAM J. Sci. Compu. 2010; 32(4): 1913–1928.
  * 8 Rens vB, Brokken BW, Baaijens F. A Two-Dimensional Paving Mesh Generator for Triangles with Controllable Aspect Ratio and Quadrilaterals with High Quality. Engineering with Computers 1998; 14: 248–259.
  * 9 Wu L. Realization of quadrilateral mesh partition and optimization algorithm based on cloud data. J. Computs. 2011; 6(12): 2519–2525.
  * 10 Lassak M. Approximation of convex bodies by rectangles. Geometriae Dedicata 1993; 47: 111–117.
  * 11 Josefsson M. Five proofs of an area characterization of rectangle. Forum Geometricorum 2013; 13: 17–21.
  * 12 González-Flores G. Generación numérica de mallas estructuradas de calidad y adaptativas en regiones planas irregulares. Tesis doctoral UNAM (en español) 2018: 490.
  * 13 Joe B. Shape measures for quadrilaterals, pyramids, wedges and hexahedra. Tech. Rep. Technical Report ZCS2008-03, Los Alamos National Laboratory FALTA; The address: 2008.
  * 14 Shewchuk J. What is a good linear finite element? Interpolation, conditioning, anisotropy and quality measures. unpublished preprint, december 2002 2002: 1.
  * 15 Knupp P. A Robust Elliptic Grid Generator. J. Comp. Phys. 1992; 100: 409–418.
  * 16 Khattri S. A New Smoothing Algorithm for Quadrilateral and Hexahedral Meshes. Lecture Notes in Computer Science 2006; 3992: 239–246.
  * 17 Herrman L, Asce M. Laplacian-isoparametric grid generation scheme. J. Engnrs. Mech. Div. 1976; 102(5): 749–907.
  * 18 Garanza V. Barrier variational generation of quasi-isometric grids. Comput. Maths. Math. Phys. 2000; 40(11): 1617–1637.