#

V. Diana Rakotonirina  Department of Materials Science and Engineering,
University of Toronto, St. George Campus, Toronto, ON, Canada  Marco Bragato
Faculty of Physics, University of Vienna, Kolingasse 1416, AT1090 Wien,
Austria  Stefan Heinen  Vector Institute for Artificial Intelligence, Toronto,
ON, M5S 1M1, Canada  O. Anatole von Lilienfeld
<EMAIL_ADDRESS>Department of Materials Science and
Engineering, University of Toronto, St. George Campus, Toronto, ON, Canada
Vector Institute for Artificial Intelligence, Toronto, ON, M5S 1M1, Canada
Chemical Physics Theory Group, Department of Chemistry, University of Toronto,
St. George Campus, Toronto, ON, Canada  ML Group, Technische Universität
Berlin and Institute for the Foundations of Learning and Data, 10587 Berlin,
Germany  Berlin Institute for the Foundations of Learning and Data, 10587
Berlin, Germany  Department of Physics, University of Toronto, St. George
Campus, Toronto, ON, Canada  Acceleration Consortium, University of Toronto,
Toronto, ON

# Combination rule for Hammett $\sigma$ constants in computational catalyst
discovery

V. Diana Rakotonirina  Department of Materials Science and Engineering,
University of Toronto, St. George Campus, Toronto, ON, Canada  Marco Bragato
Faculty of Physics, University of Vienna, Kolingasse 1416, AT1090 Wien,
Austria  Stefan Heinen  Vector Institute for Artificial Intelligence, Toronto,
ON, M5S 1M1, Canada  O. Anatole von Lilienfeld
<EMAIL_ADDRESS>Department of Materials Science and
Engineering, University of Toronto, St. George Campus, Toronto, ON, Canada
Vector Institute for Artificial Intelligence, Toronto, ON, M5S 1M1, Canada
Chemical Physics Theory Group, Department of Chemistry, University of Toronto,
St. George Campus, Toronto, ON, Canada  ML Group, Technische Universität
Berlin and Institute for the Foundations of Learning and Data, 10587 Berlin,
Germany  Berlin Institute for the Foundations of Learning and Data, 10587
Berlin, Germany  Department of Physics, University of Toronto, St. George
Campus, Toronto, ON, Canada  Acceleration Consortium, University of Toronto,
Toronto, ON

###### Abstract

The Hammett equation is popular for navigating chemical space by quantifying
the effects of substituents on chemical properties and behavior. We study the
applicability of the Hammett-inspired product (HIP) Ansatz to model relative
substrate binding within homogenous organometallic catalysis, assigning
$\sigma$ and $\rho$ to ligands and metals, respectively. Implementing an
additive combination (c) rule for obtaining $\sigma$ constants for any ligand
pair combination results in a cHIP model that can be leveraged (i) as a
baseline for $\Delta$-machine learning (ML), and (ii) to identify novel
catalyst candidates via volcano plots. After testing the combination rule on
Hammett constants previously published in the literature, we have generated
numerical evidence for the Suzuki-Miyaura (SM) C-C cross-coupling reaction
using two synthetic datasets of metallic catalysts (including (10) and
(11)-metals Ni, Pd, Pt, and Cu, Ag, Au as well as 96 ligands such as
N-heterocyclic carbenes, phosphines, or pyridines). When used as a baseline,
$\Delta$-ML prediction errors of relative binding decrease systematically with
training set size and reach chemical accuracy ($\sim$1 kcal/mol) for 20k
training instances. Employing the individual ligand constants obtained from
cHIP, we report relative substrate binding for a novel dataset consisting of
720 catalysts (not part of training data), of which 145 fall into the most
promising range on the volcano plot accounting for oxidative addition,
transmetalation, and reductive elimination steps. Multiple Ni-based catalysts,
e.g. Aphos-Ni-P($t$-Bu)3, are included among these promising candidates,
potentially offering dramatic cost savings in experimental applications.

##  I Introduction

Fig. 1: Vision of iterative catalyst discovery. a) Catalytic cycle of Suzuki-
Miyaura C-C cross-coupling with organometallic catalyst $L_{i}-M_{m}-L_{j}$
and substrate $R$ (typically [B(OH)_2(O^tBu)]^-) for metals $M$ and exemplary
ligands $L$ indicated below. b) Parameters for combination Hammett Inspired
Product (cHIP) model of relative binding energies $\Delta E^{\mathrm{r}}$ are
fitted for each complex: $\rho$ for the metal, and averaged $\sigma$ for
ligand combinations. c) Volcano plot generated by predicting the relative
binding energies corresponding to all three intermediate steps.

Cross-coupling reactions drive drug discovery and development by enabling the
production of medicinal compounds with the help of organometallic catalysts
Yet (2018); Shen  _et al._ (2019); Ohmiya (2020), the Suzuki-Miyaura (SM)
reaction (Fig. 1a) being a popular example Miyaura  _et al._ (1979); Miyaura
and Suzuki (1995); Suzuki (2011). Pd, despite its high cost, remains the most
prevalent metal among catalysts due to its superior performance. The search
for an alternative, equally high-performing yet more cost-effective metal is
challenging Graedel  _et al._ (2015); Han (2013). However, since the chemical
space of ligands is vast, its comprehensive experimental exploration is
prohibitive, even though it could reveal compounds that enhance the
performance of more affordable transition metals, or reduce the cost of
ligands in Pd complexes. Current tools for catalyst discovery comprise high-
throughput screening, combinatorial chemistry, Collins  _et al._ (2014);
Shimizu  _et al._ (1998); Isbrandt  _et al._ (2019) and machine learning (ML)
Nandy  _et al._ (2021); Kitchin (2018), a combination of which would also
benefit self-driving labs Burger  _et al._ (2020); Huang  _et al._ (2023). In
particular, the promise of ML for freely sampling chemical compound space is
owed mainly to its computational cost being many orders of magnitude lower
than ab initio methods, such as density functional theory (DFT), and as
pointed out in Ref. Strieth-Kalthoff  _et al._ (2020); Rupp  _et al._ (2012).
Established ML methods in the domain of homogeneous catalysis involve models
like random forest Ahneman  _et al._ (2018) and linear regression Reid and
Sigman (2019) to anticipate catalyst reactivity Jorner  _et al._ (2021); dos
Passos Gomes  _et al._ (2021). For the SM reaction specifically, kernel ridge
regression (KRR) Meyer  _et al._ (2018) and feed-forward neural networks
Schilter  _et al._ (2023) successfully learned relative binding energies for
7054 complexes. In addition to models, the exploration of descriptors, or
representations, capturing parameters essential in inferring a system’s
properties has been extensively investigated Rupp  _et al._ (2012); Huang and
von Lilienfeld (2020); Hansen  _et al._ (2015); Khan  _et al._ (2023);
Damewood  _et al._ (2023); Chang  _et al._ (2019). Comprehensive evidence,
such as that mentioned in Ref. von Lilienfeld  _et al._ (2020), suggests that
quantum ML models using such representations can generalize exploration across
diverse chemical spaces. That work also indicates that
$\mathrm{\Delta}$-machine learning ($\mathrm{\Delta}$-ML) Ramakrishnan  _et
al._ (2015), which learns residuals between different levels of theory, can
mitigate excessive data needs. Linear free energy relationships, such as the
Hammett equation Hammett (1935, 1937), might serve as a baseline lower level
of theory for this purpose. Introduced in 1935 Hammett (1935, 1937), it has
been recognized as a simple but accurate tool for separating substituent and
reaction effects on free energy changes. It was first proposed for benzoic
acid derivatives and was subsequently shown to be generalizable. Applications
to heterocyclic compounds Jaffé and Jones (1964) and metal-ligand complexes
Chattopadhyay  _et al._ (1976) have been reported. Moreover, Bragato et al.
Bragato  _et al._ (2020) introduced a Hammett-inspired product model (HIP)
that can fit parameters to diverse chemistries and properties. Some of its
successful applications in this domain include the prediction of adsorption
energies of small carbon molecules Bragato  _et al._ (2023) and the
quantification of substituent effects on the rates of cross-coupling reactions
Dong  _et al._ (2010). The simplicity and accuracy of the Hammett equation are
particularly appealing for the computational discovery of catalysts. The
Hammett equation, discussed in the following section, assigns a $\sigma$
parameter to the substituent on a compound, and another parameter $\rho$ to
another dimension. For organometallic catalysis, access to the $\sigma$ effect
of each ligand, as well as to ligand combinations, is therefore essential.
Early studies on disubstituted and trisubstituted benzene derivatives using
the Hammett equation indicated additive substituent effects under minimal
steric inhibition of resonance Jaffé (1953). Diverse combination rules have
also been employed for estimating thermodynamic properties of mixtures Al-
Matar and Rockstraw (2004); Delhommelle and Millié (2001); Fyta and Netz
(2012). These include using the arithmetic mean for pure component properties
to estimate collision diameters Lorentz (1881) and the geometric mean for
potential well depths Berthelot (1898) in the Lennard-Jones potential. The
harmonic mean is used for second virial coefficients Fender and Halsey Jr
(1962), and the sixth-power mean for rare gas systems Waldman and Hagler
(1993).

In this work, we introduce an approach leveraging the Hammett equation to
predict relative binding energies relevant to catalyzing the SM reaction. We
assess and propose methods for retrieving and combining individual ligand
effects that ensure statistically stable calculations. The combining rule is
integrated into a HIP model Bragato  _et al._ (2020, 2023) (Fig. 1b).
Utilizing a dataset of 25k oxidative addition relative binding energies, we
investigate the performance of this combination rule-enhanced HIP model (cHIP)
as a baseline for $\Delta$-ML. Subsequently, we leverage the design
flexibility afforded by cHIP to expand a second, smaller catalyst dataset,
DB2, into DB3 and conduct screening (Fig. 1c).

##  II Methods and computational details

###  II.1 HIP model

In the context of homogeneous catalysis, assessing the binding free energies
between catalysts and substrates at each step of the catalytic cycle aids in
understanding reaction kinetics. Herein, we multiply the Hammett equation
Hammett (1935, 1937) by $-RT$, where $R$ is the ideal gas constant and $T$ is
the temperature, to approximate changes in binding energy as a simple product,

$\Delta
E_{lm}=-RT\mathrm{log}\left(\frac{K_{lm}}{K_{0m}}\right)\simeq\rho_{m}\sigma_{l}$
(1)

where $\rho_{m}$ and $\sigma_{l}$ are constants for the metal $m$ and ligand
group $l$, respectively. $K_{lm}$ and $K_{0m}$ are equilibrium constants, with
the subscript $0$ designating a reference ligand group. In this work, a ligand
group refers to all the ligands around one central metal in a complex, and
furthermore, we also consider Hammett-based approximations of DFT-obtained
relative binding energies, i.e. neglecting all thermal contributions.
Although empirical $\sigma$ values for common substituents in the ionization
of benzoic acid derivatives can be found in the literature, such parameters
are absent for many ligands pertinent to homogeneous catalysis. Furthermore,
caution is warranted when assuming the transferability of these values for
chemistries of different natures Pearson  _et al._ (1952). Note that in Eq. 1,
the necessity of establishing a ligand as a reference is due to the ligand
space being larger compared to metals.
The HIP model, as introduced by Bragato et al. Bragato  _et al._ (2020, 2023),
enables the investigation of similar reactions by extracting linear scaling
factors between them and eliminating reliance on external references. It
comprises the following 3 steps:

####  II.1.1 Model setup

The model begins with an ansatz assuming that there exists an offset $\Delta
E_{0m}$. Then each change in binding energy can be predicted with

$\Delta E_{lm}\simeq\rho_{m}\sigma_{l}+\Delta E_{0m}$ (2)

Furthermore, the binding energy changes can be stored in a matrix M, where $X$
is the number of metals and $Y$ is the number of ligand groups,

$\mathbf{M}=\begin{bmatrix}\Delta E_{11}&\Delta E_{12}&\ldots&\Delta
E_{1m}&\ldots&\Delta E_{1X}\\\ \Delta E_{21}&\Delta E_{22}&\ldots&\Delta
E_{2m}&\ldots&\Delta E_{2X}\\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\\
\Delta E_{l1}&\Delta E_{l2}&\ldots&\Delta E_{lm}&\ldots&\Delta E_{lX}\\\
\vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\\ \Delta E_{Y1}&\Delta
E_{Y2}&\ldots&\Delta E_{Ym}&\ldots&\Delta E_{YX}\end{bmatrix}$ (3)

For each column, the internal reference $\Delta E_{0m}$ is defined as its
median.

####  II.1.2 Solving for $\rho$

Hammett’s equation (Eq. 1) suggests a linear scaling relationship between
energies of complexes with the same ligands but different metals. An initial
set of $\rho$s can then be the pairwise scaling factors $c_{mn}$ between any
two columns $m$ and $n$ of M, thereby eliminating reference bias Bragato  _et
al._ (2020). Consequently, $c_{mn}=\frac{\rho_{m}}{\rho_{n}}\simeq\frac{\Delta
E_{lm}}{\Delta E_{ln}}$, or

$c_{mn}\rho_{n}-\rho_{m}=0$ (4)

$c_{mn}$ is computed as the slope of the line of best fit between all $\Delta
E_{lm}$ and $\Delta E_{ln}$ for $1\leq l\leq Y$ (see Fig. 2). The procedure
adopts Theil-Sen regression Theil (1950); Sen (1968), evaluating the median of
$s=\binom{Y}{2}$ pairwise slopes $(\Delta E_{lm}-\Delta E_{km})/(\Delta
E_{ln}-\Delta E_{kn})$ for $1\leq l<k\leq Y$. Ordering the slopes in a list
$S$, we get

$c_{mn}=\begin{cases}S_{\frac{s+1}{2}},&\text{if $s$ is odd}.\\\
\frac{S_{\frac{s}{2}}+S_{\frac{s}{2}+1}}{2},&\text{if $s$ is
even}.\end{cases}$ (5)

This method offers the advantage of being more robust towards outliers, but it
scales quadratically with the number of data points.

Fig. 2: Binding energies for complexes with metals $m$ and $n$. Each point
represents a distinct ligand combination. The regression line, obtained
through Theil-Sen regression Theil (1950); Sen (1968); Bragato  _et al._
(2020), has a slope representing the median of all pairwise slopes.

Accounting for all permutations of $m$ and $n$, $m\neq n$, Eq. 4 yields an
overdetermined system of linear equations $\mathbf{C\boldsymbol{\rho}=0}$
which can be used to solve for $\rho$s. A comprehensive description of this
matrix is provided in the supplementary information section (SI).

####  II.1.3 Solving for $\sigma$

Subsequently, using the $\rho$s and matrix M entries, we calculate $\sigma$
for each ligand group as

$\sigma_{l}=\frac{1}{X}\sum_{m=1}^{X}\frac{\Delta E_{lm}}{\rho_{m}}$ (6)

The $\rho$ of each metal is then refined via another Theil-Sen regression. The
slopes to evaluate in this case are $(\Delta E_{lm}-\Delta
E_{km})/(\sigma_{l}-\sigma_{k})$ for $1\leq l<k\leq Y$, and the new $\rho_{m}$
is the median slope. After this refinement, a satisfying level of self-
consistency is reached and further iterations are no longer necessary. In this
work, $\sigma$ is in energy units, and $\rho$ is considered a unitless pre-
factor.

###  II.2 Combination rule

Fig. 3: Test of combination rule for experimentally obtained substituent
parameters describing reactions of various chemistries (see text) published
decades ago by Siegel Siegel (1979), Kaplan Kaplan (1961), JafféJaffé (1953).
Substituent constants ($\bar{\sigma}$) were obtained by (a) summing published
$\sigma$, and (b) after linear regression for each of the three published sets
(this work).

In cases where the $\sigma$s of individual substituents are known, one can
assume that an additive combination rule can be used to retrieve the effects
of any combination of them. This idea was generalized and confirmed already in
1953 by Jaffé who compiled overwhelming evidence in support of this effect
Jaffé (1953). We note for this work that conversely individual ligand
contributions can also be inferred as soon as sufficiently many $\sigma$s for
combinations of substituents (groups) are known. We have exploited the latter
idea to first quantify $\sigma$s for individual ligands via linear regression
and to subsequently add them for estimating $\sigma$s of novel ligand
combinations.

In order to reconfirm the validity of this approach we revisited the
previously published data. In particular, the effect of a group of ligands $l$
is approximated as

$\sigma_{l}\simeq\sum_{i=1}^{N_{i}}\sigma_{i}$ (7)

for a multisubstituted system. Here, $N_{i}$ is the number of ligands in the
group $l$, and $\sigma_{i}$ is the effect of ligand $i$ in a monosubstituted
system. We estimate $\sigma_{i}$ with $\bar{\sigma}_{i}$ by solving the system
of equations

$\mathbf{D\boldsymbol{\bar{\sigma}=\sigma_{l}}}$ (8)

where $D_{IJ}$ indicates the number of appearances of substituent $J$ in
compound $I$, $\boldsymbol{\sigma_{l}}$ contains the sums of substituent
effects for each compound. $\boldsymbol{\bar{\sigma}}$ is the vector of single
substituent effects that can be solved via the linear least squares method.

Results on display in Fig. 3 confirm our expectation that $\sigma$s of
combinations are additive in $\sigma$s of single ligands. These experimental
constants were obtained from studies on the hydrolysis of phosphonium salts
Siegel (1979), alcoholysis of isocyanates Kaplan (1961), and various reactions
involving benzoic acids Jaffé (1953). The datasets encompassed di- and
trisubstituted compounds featuring small substituents such as Cl, CH3, OCH3,
NO2, etc., each with established Hammett parameters. Furthermore, note that
the sums of parameters obtained through linear regression (Fig. 3b) are
consistently closer to the experiments than the sums of Hammett parameters.
This enhanced accuracy of the least squares method, presumably due to improved
regularization and balancing, suggests its capability to robustly account for
environment-specific synergistic effects, typically absent within the
arbitrarily selected experiments resulting in the initial Hammett parameters.
We also report the performance of other combination rules in the SI, which
revealed less accuracy than the additive rule.

For estimating relative binding energies to catalyst complexes in the SM
coupling reaction we have first applied Eq. 8 to ligand pairs using the
$\sigma$s obtained from HIP as $\boldsymbol{\sigma_{l}}$. Then, cHIP
predictions, $\Delta E^{\mathrm{{}^{c}}}$, can be obtained for any ligand pair
$ij$ and catalyst metal $m$ via

$\displaystyle\Delta E_{ijm}\simeq\Delta
E_{ijm}^{\mathrm{{}^{c}}}=\rho_{m}\bar{\sigma}_{ij}+\Delta
E_{\mathrm{0}m}=\rho_{m}(\sigma_{i}+\sigma_{j})+\Delta E_{\mathrm{0}m}$ (9)

###  II.3 $\mathrm{\Delta}$-ML

To compare the above model to existing ML methods, we adopted an ML approach
with Hammett to yield learning curves by fitting Hammett parameters to a
growing training set and testing on fixed out-of-sample data. To obtain
predictions for all data points, the data was divided into 5 folds, and each
was used as a test set once while training on the 4 others. Due to varied
training set sizes in the cHIP model, certain ligand combinations present in
the test set might be absent from the training sets, especially with smaller
training sets. Hence, a categorical regression using one-hot encoding was
employed to estimate $\sigma$ values for unknown ligands from known ones
Bragato  _et al._ (2020). Ligand constants from this step were used only in
cases where they could not be estimated during training.

The cHIP results served as a baseline for $\mathrm{\Delta}$-ML with KRR
Ramakrishnan  _et al._ (2015). KRR, a supervised ML technique initially
introduced in chemistry for learning molecular atomization energies Hansen
_et al._ (2013), maps data from the input space to a feature space and
calculates the dot product of the transformed vectors. The mapped data in this
case are the representations, which contain information derived from the
molecular structure. For a given set of $N$ training instances, the corrected
predictions after $\mathrm{\Delta}$-ML are obtained using

$\Delta E\mathrm{{}^{\Delta}}=\Delta
E\mathrm{{}^{c}}+\sum_{t=1}^{N}\alpha_{t}k(\mathbf{x}_{t},\mathbf{x}_{q})$
(10)

where the second term is the KRR-predicted residual. $\mathbf{x}$ are the
representations and $k$ is a similarity measure between the training compounds
$t$ and the query compounds $q$, respectively. These similarity measures were
obtained with a Laplacian kernel (Eq. 11), or a Gaussian kernel (Eq. 12) for
computations using SLATM as a representation.

$k(\mathbf{x}_{t},\mathbf{x}_{q})=\mathrm{exp}\left(-\frac{||\mathbf{x}_{t}-\mathbf{x}_{q}||_{1}}{\sigma^{\prime}}\right)$
(11)
$k(\mathbf{x}_{t},\mathbf{x}_{q})=\mathrm{exp}\left(-\frac{||\mathbf{x}_{t}-\mathbf{x}_{q}||_{2}^{2}}{{2\sigma^{\prime}}^{2}}\right)$
(12)

Here, $\sigma^{\prime}$ is a hyperparameter optimized for every training set
size using grid search, not to be confused with $\sigma$ in the Hammett
equation. $\boldsymbol{\alpha}$ is a vector of regression coefficients that is
obtained using

$\boldsymbol{\alpha}=(\mathrm{\mathbf{K}}+\lambda\mathbf{\mathbf{I}})^{-1}\mathbf{\mathbf{y}}$
(13)

where $\lambda$ is a regularizer, optimized at every training set size,
$\mathbf{I}$ the identity matrix, $\mathrm{\mathbf{y}}$ a vector containing
the training properties, and $\mathrm{\mathbf{K}}$ a kernel matrix containing
similarity measures between all compounds in the training set.

###  II.4 Datasets

Table 1: Overview of all datasets used and predicted in this work, including catalyst and reaction step details. All 108 molecular graphs of ligands are provided in the SI. |  Purpose |  Catalyst structure |  Metals |  $\\#$ of Ligands |  Reaction steps |  $\\#$ of data entries |  Data origin
---|---|---|---|---|---|---|---
DB1 |  Test combination rule |  $L_{i}-M_{m}-L_{j}$ |  Ni, Pd, Pt, Cu, Ag, Au |  91, see SI |  Oxidative addition |  25116 |  7054 from DFT Meyer  _et al._ (2018) \+ 18062 from KRR using MBDF and Laplacian kernel (this work)
DB2 |  Catalyst discovery |  $L_{i}-M_{m}-L_{i}$ |  Ni, Pd, Pt, Cu, Ag, Au |  16, see SI |  Oxidative addition, transmetalation, reductive elimination |  291 |  291 from DFT (97 per reaction step) Busch  _et al._ (2017)
DB3 |  Novel catalysts |  $L_{i}-M_{m}-L_{j}$ |  Ni, Pd, Pt, Cu, Ag, Au |  16, see SI |  Oxidative addition, transmetalation, reductive elimination |  720 |  cHIP (this work)
Fig. 4: Test of ML model used to augment the DFT data in DB1 (Table 1).
Learning curves (test error of relative binding energies vs training set size)
for oxidative addition for different ML methods. L: Laplacian kernel, G:
Gaussian kernel. The augmentation was done using the MBDF-based model trained
on all 7054 DFT training points published in Ref. Meyer  _et al._ (2018).

Two datasets were used in this work, as summarized in Table 1.
The first one, referred to as Database 1 (DB1) was obtained from Ref. Meyer
_et al._ (2018). It contains a total of 91 ligands of types phosphines (P),
N-heterocyclic carbenes (NHC), pyridines (Py), and other common ligands
(Other). Their chemical structures are provided in the SI. Those ligands were
combined with six transition metals (Ni, Pd, Pt, Cu, Ag, and Au) to form
catalysts having the structure $L_{i}-M_{m}-L_{j}$, where $L_{i}$ and $L_{j}$
are ligands and $M_{m}$ is a metal, spanning a total set of 25116 compounds.
It contained substrate-catalyst relative binding energies relative to the
oxidative addition step in the SM C-C cross-coupling reaction depicted in Fig.
1a for 4186 $L_{i}-L_{j}$ combinations, each coupled with all 6 metals. The
distributions of the energies by metal and by ligand type combinations, shown
in Fig. S1 and S2 respectively, primarily show that the energies are more
strongly correlated with metals than with ligands.
A subset of 7054 geometries in DB1 was optimized using the AiiDA Pizzi  _et
al._ (2016) at the B3LYP-D3/3-21G Grimme  _et al._ (2010, 2011) level of
theory for the Ni, Pd, Cu, and Ag complexes, and B3LYP-D3/def2-SVP Weigend and
Ahlrichs (2005a) for the Pt and Au complexes in Gaussian09 Frisch  _et al._
(2016). Subsequently, B3LYP-D3/def2-TZVP Weigend and Ahlrichs (2005b) single-
point calculations were performed. The remaining 18062 energies were predicted
by us using a KRR model trained on the DFT energies using the Many-Body
Distribution Functional (MBDF) Khan  _et al._ (2023) representation and a
Laplacian kernel. Three other representations and kernel combinations were
built for comparison, namely Coulomb Matrix Rupp  _et al._ (2012) and Bag of
Bonds (BoB) Hansen  _et al._ (2015) with a Laplacian kernel, and Spectrum of
London and Axilrod–Teller–Muto potential (SLATM) Huang and von Lilienfeld
(2020) with a Gaussian kernel, hence reproducing Meyer et al.’s work Meyer
_et al._ (2018). As shown in Fig. 4, the comparison leads to the conclusion
that MBDF, with the Laplacian kernel, yields the best result.

The second and smaller dataset (Database 2 or DB2) was obtained from Ref.
Busch  _et al._ (2017) and provides relative binding free energies for all 3
intermediate steps depicted in Fig. 1a. It contains symmetrical complexes,
composed of the same 6 metals as in the first dataset and 16 ligands. 10 out
of those 16 ligands were also present in the first one, and the energies of
some Cu-based complexes were not provided, yielding only 97 complexes per
reaction step. The geometries of these complexes were optimized using
M06/def2-SVP Zhao and Truhlar (2008a, b); Weigend and Ahlrichs (2005a) in
Gaussian09 Frisch  _et al._ (2016) while accounting for solvation in
tetrahydrofuran using the implicit SMD model Marenich  _et al._ (2009).

##  III Results and discussion

###  III.1 cHIP on oxidative addition (DB1)

The naive HIP model of changes in binding for 912/2 = 4186 global $\sigma$’s
reached a mean absolute error (MAE) $\sim$2.5 kcal/mol for DB1. Application of
the combination rule to 91 substituent specific $\sigma$s within cHIP (Eq. 9)
increased the MAE by less than 1 kcal/mol to $\sim$3.4 kcal/mol. Corresponding
scatter plots of 25116 model predictions versus reference data numbers (used
for fitting) are shown in Figs. 5 and S3 for cHIP and HIP, respectively. Such
predictive power, only on the order of a few percentage points of the range of
the property (see Fig. S1) is promising. We note that it is on par with
popular density functional approximations, as well as with previous HIP
results obtained for estimating activation energies in SN2 reactions Bragato
_et al._ (2020).

Fig. 5: cHIP-predicted changes in binding energies against reference energies
for DB1 (25k compounds) where MAE = 3.4 kcal/mol. Insets display complexes
that deviate most (MAE $>$ 30 kcal/mol). Atom colors are gray, blue, white,
green, red, orange, silver, dark cyan, and dark orange for C, N, H, Cl, O, P,
Ag, Pd, and Cu, respectively.

Note how in Fig. 5, no skewing is observed (see also the error distribution
curve per metal in Fig. S5). As displayed as insets, outliers correspond to
varying metals. However, they all have in common that there is one P ligand.
Furthermore, all underestimated outliers correspond to catalysts that share
the same ligands, proazaphosphatrane, and 2-fluoropyridine.

Most outliers of the cHIP model (Fig. 5) were also outliers already for the
HIP model (Fig. S3). This suggests that, beyond the decrease in dimensionality
caused by the combination rule, these shortcomings are likely to be caused by
the Hammett equation’s inadequacy in describing those specific ligands. This
inadequacy can only be partly explained by steric hindrance since the dataset
also comprised several bulky NHC ligands which were not outliers.

Performing the regression on subsets according to the categories of each of
its ligands further improved the prediction accuracy. In Fig. 8, all the cHIP
models fitted on the subsets had lower errors than the full dataset model.
These observations agree with the statement that a Hammett correlation occurs
between closely related species Chattopadhyay  _et al._ (1976). They are also
in line with the fact that regression is more difficult the higher the
dimensionality Lemm  _et al._ (2023). As such, cHIP promises to be a useful
model for combinatorially scaling spaces (the combinations of ligands in this
case) with low-dimensional chemistry-specific properties, and where limited
training instances are available.

The individual $\sigma$s were retrieved by applying the combination rule on
the HIP predictions to produce the Hammett plot in Fig. 6. Moreover, the
distinct clustering of complexes by their central metal and the linear trends
in Fig. 6 validate the adequacy of the partitioning of $\rho$ and $\sigma$.

Fig. 6: Demonstration of cHIP. Oxidative addition relative binding energies
(DB1, see Table 1) are shown as a function of averaged $\sigma$ obtained from
cHIP. For the sake of simplicity, only 5 examples from each ligand type
combination (given as legends) are plotted for each of the three metals. Lines
correspond to cHIP predictions.

A closer look at the calculation of the individual $\sigma$s for DB1 in Fig. 7
revealed a MAE of 2.5 kcal/mol between the $\sigma$s from HIP and cHIP. While
an overestimation is usually observed with the additive rule when summing
existing Hammett parameters Jaffé (1953); Bhasha Sayyed and H. Suresh (2009),
we have circumvented this by fitting those parameters with linear regression.
The corresponding error distribution of cHIP $\sigma$s (inset of Fig 7)
illustrates the welcome absence of any bias.

Fig. 7: Test of combination rule for individually obtained substituent
parameters using DB1 (Table 1). Averaged $\bar{\sigma}$ (cHIP on DB1) vs
reference $\sigma$ (HIP on DB1) for combinations of ligands $i$ and $j$ . The
inset shows the corresponding error distribution.

###  III.2 $\Delta$-ML

When regressing cHIP onto the entire DB1 (DFT + ML augmented instances), the
prediction error ceases to improve, leveling off at $\sim$4 kcal/mol (see Fig.
8). Note how the offset of the plateau is located at $\sim$1k training
instances which roughly corresponds to the total number of parameters to fit
in Eq. 9. While several physics-based representations, such as CM Rupp  _et
al._ (2012), global MBDF Khan  _et al._ (2023), BoB Hansen  _et al._ (2015),
or SLATM Huang and von Lilienfeld (2020), enable KRR models to systematically
improve with training set size (see Fig. 4), DB1 does not contain sufficient
DFT instances to allow for convergence lower than 2 kcal/mol. Understanding
catalytic yield greatly relies on thermodynamics, where equilibrium constants
exhibit exponential scaling with free energy differences, underscoring the
significance of predicting such changes with chemical accuracy (1 kcal/mol).
Encouragingly, when combining cHIP as a baseline with a machine-learned
correction, $\Delta$-ML, the resulting learning curve on DB1 continues to
improve with training set size, reaching a MAE corresponding to chemical
accuracy for $\sim$20k training instances.

The systematically decreasing standard deviations of the prediction errors in
the learning curves are equally promising, and can be attributed to an
increasingly slimmer error distribution, similar to previously noted trends
for machine learning models of formation energies of crystals Faber  _et al._
(2016).

Fig. 8: Mean absolute error of predicting relative binding energies in the
oxidative addition step as a function of training set size. Errors of cHIP
models on subsets (colored) and full DB1 (Table 1) plateau rapidly. ML
corresponds to the KRR/MBDF line shown in Fig. 4. $\Delta$-ML model trained on
DB1 results with cHIP baseline results in lower offset and enables convergence
to chemical accuracy. Error bars indicate standard deviations.

###  III.3 Catalyst discovery (DB2)

Fig. 9: Volcano plot: Negative relative binding free energies of each step are
plotted as a function of that of the oxidative step (oxi). Ideal catalysts lie
at the top of the volcano and vertical lines represent the ideal range as
identified by Busch et al. Busch  _et al._ (2017). a) catalysts sourced from
DB2 (Table 1). b) novel catalysts predicted using cHIP, the 198 most
interesting catalysts lie in between the two intersections of the
transmetalation with either oxidative addition or reductive elimination. Two
inexpensive (Ni-based) catalysts in the optimal regime are indicated by
arrows.

We have studied the utility of cHIP in catalyst discovery through volcano
plots. For homogeneous catalysis, such plots are built by establishing linear
scaling relationships between all the intermediate steps against a reference
step Busch  _et al._ (2015) using a descriptor such as the catalyst-substrate
binding free energy. This allows for identifying an ideal range of energies in
which only certain catalysts fall, aligning with Sabatier’s principle Sabatier
(1913). DB2 was used in this phase as it contains relative binding free
energies for all 3 steps.

The fitting of HIP to the entire dataset, illustrated in Figure 9a, resulted
in MAEs consistently below 3.5 kcal/mol for all steps. Leveraging the effects
of 16 single ligands, cHIP successfully predicted the ligand effects of 120
new ligand combinations. Pairing these with each of the 6 metals, we predicted
substrate binding free energy changes for an additional 720 catalysts,
reported in DB3.

As depicted in Fig. 9b, 198 of the new catalysts lie at the top of the
predicted volcano plot. Among these, 145 displayed oxidative addition relative
binding free energies ranging from -34.0 to 17.0 kcal/mol, previously
identified as an optimal range by Busch et al. Busch  _et al._ (2017). The top
of the volcano plot underscores the tunability of Ni-based catalysts through
various ligand combinations. This is an attractive prospect given the cost-
effectiveness and abundance of nickel. However, it is crucial to consider the
cost of the ligands. The most cost-effective catalyst identified by cHIP is
Aphos-Ni-P(t-Bu)3, representing about 67% of the cost of the least expensive
catalyst found in DB2, Pd(Ace)2, based on ligand and metal prices provided by
Sigma-Aldrich Mil .

##  IV Conclusion

Our study demonstrates the efficacy of employing an additive combination rule
with Hammett’s equation. We have exemplified its applicability to the
prediction and analysis of organometallic complexes relevant to the catalysis
of the Suzuki-Miyaura (SM) cross-coupling reaction. We exploit fitted Hammett
parameters obtained from linear least squares regression across all available
ligand combinations, surpassing the prediction performance of published
Hammett parameters. Due to its simplicity, this approach offers significant
computational advantages, obviating the need for geometric coordinates or
extensive computing resources, therefore serving as a quick yet useful
screening tool. It also proves valuable when dealing with smaller chemical
compound subspaces. Furthermore, our findings illustrate its utility as a
baseline for $\Delta$-ML, reaching predictive power with chemical accuracy.
The ability to separate ligand pair effects into single ligand effects
facilitates the exploration of larger catalyst spaces and ligand tuning. This
was demonstrated for a dataset comprising symmetrical catalysts created
through the combination of 16 ligands and 6 metals. Our model identified 145
new catalyst candidates for the SM reaction, including some based on Ni
implying potentially substantial cost savings. For example, we identified the
phosphine ligand-based Ni catalyst, Aphos-Ni-P($t$-Bu)3, which seems to fall
in line with other phosphine ligands such as ProPhos Yang  _et al._ (2024).
Future research directions will include extending this approach to complexes
with more than two ligands, other catalysts, and conducting deeper
investigations into the model’s outliers (P-containing ligands).

## Concflicts of interest

There are no conflicts to declare.

###### Acknowledgements.

We acknowledge the support of the Natural Sciences and Engineering Research
Council of Canada (NSERC), RGPIN-2023-04853. O.A.v.L. has received funding
from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (grant agreement No. 772834). This
research was undertaken thanks in part to funding provided to the University
of Toronto’s Acceleration Consortium from the Canada First Research Excellence
Fund, grant number: CFREF-2022-00042. O.A.v.L. has received support as the Ed
Clark Chair of Advanced Materials and as a Canada CIFAR AI Chair.

## References

  * Yet (2018) L. Yet,  _Privileged structures in drug discovery: medicinal chemistry and synthesis_ (John Wiley & Sons, 2018).
  * Shen  _et al._ (2019) D. Shen, Y. Xu, and S.-L. Shi, Journal of the American Chemical Society 141, 14938 (2019).
  * Ohmiya (2020) H. Ohmiya, ACS Catalysis 10, 6862 (2020).
  * Miyaura  _et al._ (1979) N. Miyaura, K. Yamada, and A. Suzuki, Tetrahedron Letters 20, 3437 (1979).
  * Miyaura and Suzuki (1995) N. Miyaura and A. Suzuki, Chemical reviews 95, 2457 (1995).
  * Suzuki (2011) A. Suzuki, Angewandte chemie international edition 50, 6722 (2011).
  * Graedel  _et al._ (2015) T. E. Graedel, E. M. Harper, N. T. Nassar, and B. K. Reck, Proceedings of the National Academy of Sciences 112, 6295–6300 (2015).
  * Han (2013) F.-S. Han, Chemical Society Reviews 42, 5270 (2013).
  * Collins  _et al._ (2014) K. D. Collins, T. Gensch, and F. Glorius, Nature chemistry 6, 859 (2014).
  * Shimizu  _et al._ (1998) K. D. Shimizu, M. L. Snapper, and A. H. Hoveyda, Chemistry–A European Journal 4, 1885 (1998).
  * Isbrandt  _et al._ (2019) E. S. Isbrandt, R. J. Sullivan, and S. G. Newman, Angewandte Chemie International Edition 58, 7180 (2019).
  * Nandy  _et al._ (2021) A. Nandy, C. Duan, M. G. Taylor, F. Liu, A. H. Steeves, and H. J. Kulik, Chemical Reviews 121, 9927 (2021).
  * Kitchin (2018) J. R. Kitchin, Nature Catalysis 1, 230 (2018).
  * Burger  _et al._ (2020) B. Burger, P. M. Maffettone, V. V. Gusev, C. M. Aitchison, Y. Bai, X. Wang, X. Li, B. M. Alston, B. Li, R. Clowes, _et al._ , Nature 583, 237 (2020).
  * Huang  _et al._ (2023) B. Huang, G. F. von Rudorff, and O. A. von Lilienfeld, Science 381, 170 (2023).
  * Strieth-Kalthoff  _et al._ (2020) F. Strieth-Kalthoff, F. Sandfort, M. H. Segler, and F. Glorius, Chemical Society Reviews 49, 6154 (2020).
  * Rupp  _et al._ (2012) M. Rupp, A. Tkatchenko, K.-R. Müller, and O. A. von Lilienfeld, Physical review letters 108, 058301 (2012).
  * Ahneman  _et al._ (2018) D. T. Ahneman, J. G. Estrada, S. Lin, S. D. Dreher, and A. G. Doyle, Science 360, 186 (2018).
  * Reid and Sigman (2019) J. P. Reid and M. S. Sigman, Nature 571, 343 (2019).
  * Jorner  _et al._ (2021) K. Jorner, A. Tomberg, C. Bauer, C. Sköld, and P.-O. Norrby, Nature Reviews Chemistry 5, 240 (2021).
  * dos Passos Gomes  _et al._ (2021) G. dos Passos Gomes, R. Pollice, and A. Aspuru-Guzik, Trends in Chemistry 3, 96 (2021).
  * Meyer  _et al._ (2018) B. Meyer, B. Sawatlon, S. Heinen, O. A. von Lilienfeld, and C. Corminboeuf, Chemical science 9, 7069 (2018).
  * Schilter  _et al._ (2023) O. Schilter, A. Vaucher, P. Schwaller, and T. Laino, Digital Discovery 2, 728 (2023).
  * Huang and von Lilienfeld (2020) B. Huang and O. A. von Lilienfeld, Nature chemistry 12, 945 (2020).
  * Hansen  _et al._ (2015) K. Hansen, F. Biegler, R. Ramakrishnan, W. Pronobis, O. A. von Lilienfeld, K.-R. Muller, and A. Tkatchenko, The journal of physical chemistry letters 6, 2326 (2015).
  * Khan  _et al._ (2023) D. Khan, S. Heinen, and O. A. von Lilienfeld, The Journal of Chemical Physics 159 (2023).
  * Damewood  _et al._ (2023) J. Damewood, J. Karaguesian, J. R. Lunger, A. R. Tan, M. Xie, J. Peng, and R. Gómez-Bombarelli, Annual Review of Materials Research 53, 399 (2023).
  * Chang  _et al._ (2019) A. M. Chang, J. G. Freeze, and V. S. Batista, Chemical Science 10, 6844 (2019).
  * von Lilienfeld  _et al._ (2020) O. A. von Lilienfeld, K.-R. Müller, and A. Tkatchenko, Nature Reviews Chemistry 4, 347 (2020).
  * Ramakrishnan  _et al._ (2015) R. Ramakrishnan, P. O. Dral, M. Rupp, and O. A. von Lilienfeld, Journal of Chemical Theory and Computation 11, 2087–2096 (2015).
  * Hammett (1935) L. P. Hammett, Chemical reviews 17, 125 (1935).
  * Hammett (1937) L. P. Hammett, Journal of the American Chemical Society 59, 96 (1937).
  * Jaffé and Jones (1964) H. H. Jaffé and H. L. Jones, in  _Advances in Heterocyclic Chemistry_ , Vol. 3 (Elsevier, 1964) pp. 209–261.
  * Chattopadhyay  _et al._ (1976) A. K. Chattopadhyay, A. Bhattacharyya, and S. C. Lahiri, Zeitschrift für Physikalische Chemie 102, 151–158 (1976).
  * Bragato  _et al._ (2020) M. Bragato, G. F. von Rudorff, and O. A. von Lilienfeld, Chemical science 11, 11859 (2020).
  * Bragato  _et al._ (2023) M. Bragato, G. F. von Rudorff, and O. A. von Lilienfeld, Occam’s razor for ai: Coarse-graining Hammett inspired product ansatz in chemical space (2023), arXiv:2305.07010 [physics.chem-ph] .
  * Dong  _et al._ (2010) Z.-B. Dong, G. Manolikakes, L. Shi, P. Knochel, and H. Mayr, Chemistry–A European Journal 16, 248 (2010).
  * Jaffé (1953) H. H. Jaffé, Chemical Reviews 53, 191–261 (1953).
  * Al-Matar and Rockstraw (2004) A. K. Al-Matar and D. A. Rockstraw, Journal of computational chemistry 25, 660 (2004).
  * Delhommelle and Millié (2001) J. Delhommelle and P. Millié, Molecular Physics 99, 619 (2001).
  * Fyta and Netz (2012) M. Fyta and R. R. Netz, The Journal of chemical physics 136 (2012).
  * Lorentz (1881) H. A. Lorentz, Annalen der Physik 248, 127–136 (1881).
  * Berthelot (1898) D. Berthelot, Compt. Rendus 126, 15 (1898).
  * Fender and Halsey Jr (1962) B. Fender and G. Halsey Jr, The Journal of Chemical Physics 36, 1881 (1962).
  * Waldman and Hagler (1993) M. Waldman and A. T. Hagler, Journal of computational chemistry 14, 1077 (1993).
  * Pearson  _et al._ (1952) D. Pearson, J. Baxter, and J. Martin, The Journal of Organic Chemistry 17, 1511 (1952).
  * Theil (1950) H. Theil, Indagationes mathematicae 12, 173 (1950).
  * Sen (1968) P. K. Sen, Journal of the American statistical association 63, 1379 (1968).
  * Siegel (1979) B. Siegel, Journal of the American Chemical Society 101, 2265 (1979).
  * Kaplan (1961) M. Kaplan, Journal of Chemical and Engineering Data 6, 272 (1961).
  * Hansen  _et al._ (2013) K. Hansen, G. Montavon, F. Biegler, S. Fazli, M. Rupp, M. Scheffler, O. A. von Lilienfeld, A. Tkatchenko, and K.-R. Müller, Journal of Chemical Theory and Computation 9, 3404 (2013).
  * Busch  _et al._ (2017) M. Busch, M. D. Wodrich, and C. Corminboeuf, ACS Catalysis 7, 5643 (2017).
  * Pizzi  _et al._ (2016) G. Pizzi, A. Cepellotti, R. Sabatini, N. Marzari, and B. Kozinsky, Computational Materials Science 111, 218 (2016).
  * Grimme  _et al._ (2010) S. Grimme, J. Antony, S. Ehrlich, and H. Krieg, The Journal of chemical physics 132, 154104 (2010).
  * Grimme  _et al._ (2011) S. Grimme, S. Ehrlich, and L. Goerigk, Journal of computational chemistry 32, 1456 (2011).
  * Weigend and Ahlrichs (2005a) F. Weigend and R. Ahlrichs, Physical Chemistry Chemical Physics 7, 3297 (2005a).
  * Frisch  _et al._ (2016) M. J. Frisch, G. W. Trucks, H. B. Schlegel, G. E. Scuseria, M. A. Robb, J. R. Cheeseman, G. Scalmani, V. Barone, G. A. Petersson, H. Nakatsuji, X. Li, M. Caricato, A. V. Marenich, J. Bloino, B. G. Janesko, R. Gomperts, B. Mennucci, H. P. Hratchian, J. V. Ortiz, A. F. Izmaylov, J. L. Sonnenberg, D. Williams-Young, F. Ding, F. Lipparini, F. Egidi, J. Goings, B. Peng, A. Petrone, T. Henderson, D. Ranasinghe, V. G. Zakrzewski, J. Gao, N. Rega, G. Zheng, W. Liang, M. Hada, M. Ehara, K. Toyota, R. Fukuda, J. Hasegawa, M. Ishida, T. Nakajima, Y. Honda, O. Kitao, H. Nakai, T. Vreven, K. Throssell, J. A. Montgomery, Jr., J. E. Peralta, F. Ogliaro, M. J. Bearpark, J. J. Heyd, E. N. Brothers, K. N. Kudin, V. N. Staroverov, T. A. Keith, R. Kobayashi, J. Normand, K. Raghavachari, A. P. Rendell, J. C. Burant, S. S. Iyengar, J. Tomasi, M. Cossi, J. M. Millam, M. Klene, C. Adamo, R. Cammi, J. W. Ochterski, R. L. Martin, K. Morokuma, O. Farkas, J. B. Foresman, and D. J. Fox, Gaussian˜09 Revision D.01 (2016), gaussian Inc. Wallingford CT.
  * Weigend and Ahlrichs (2005b) F. Weigend and R. Ahlrichs, Physical Chemistry Chemical Physics 7, 3297 (2005b).
  * Zhao and Truhlar (2008a) Y. Zhao and D. G. Truhlar, Accounts of chemical research 41, 157 (2008a).
  * Zhao and Truhlar (2008b) Y. Zhao and D. G. Truhlar, Theoretical chemistry accounts 120, 215 (2008b).
  * Marenich  _et al._ (2009) A. V. Marenich, C. J. Cramer, and D. G. Truhlar, The Journal of Physical Chemistry B 113, 6378 (2009).
  * Lemm  _et al._ (2023) D. Lemm, G. F. von Rudorff, and O. A. von Lilienfeld, Machine Learning: Science and Technology 4, 045043 (2023).
  * Bhasha Sayyed and H. Suresh (2009) F. Bhasha Sayyed and C. H. Suresh, New Journal of Chemistry 33, 2465–2471 (2009).
  * Faber  _et al._ (2016) F. A. Faber, A. Lindmaa, O. A. von Lilienfeld, and R. Armiento, Phys. Rev. Lett. 117, 135502 (2016).
  * Busch  _et al._ (2015) M. Busch, M. D. Wodrich, and C. Corminboeuf, Chemical science 6, 6754 (2015).
  * Sabatier (1913) P. Sabatier, La catalyse en chimie organique, librairie polytechnique (1913).
  * (67) Millipore Sigma, https://www.sigmaaldrich.com/CA/en, accessed: 2024-03-08.
  * Yang  _et al._ (2024) J. Yang, M. C. Neary, and T. Diao, Journal of the American Chemical Society (2024).


0\\}\right]\geq r(\gamma-4\varepsilon_{0})\sum_{i=1}^{n}\beta_{i}\right)\geq
1-\delta.$

###### Claim 5

For any $t>0$, we have

$\displaystyle\mathbb{P}\left(\forall\bm{\beta}\in[0,1]^{n}:\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]\leq
4r\left(rd+t\right)\sum_{i=1}^{n}\beta_{i}\right)\geq 1-2ne^{-4Mt^{2}}$

Based on these three claims, when

$r<\frac{\gamma-4\varepsilon_{0}}{16d},\quad
t=\frac{r(\gamma-4\varepsilon_{0})}{4},\quad
n\geq\frac{\ln(6/\delta)}{2\varepsilon_{0}^{2}}\quad\text{and}\quad
M\geq\max\left\\{\frac{\ln(4n/\delta)}{\gamma^{2}},\frac{4\ln(6n/\delta)}{r^{2}(\gamma-4\varepsilon_{0})^{2}}\right\\}$

we know that with probability at least $1-\delta$, for any
$\bm{\beta}\in[0,1]^{n}$, we have

$\displaystyle\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right]+\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]-\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]$
$\displaystyle\geq\left[-t\sum_{i=1}^{n}\beta_{i}\right]+\left[r(\gamma-4\varepsilon_{0})\sum_{i=1}^{n}\beta_{i}\right]+\left[-4r\left(rd+t\right)\sum_{i=1}^{n}\beta_{i}\right]$
$\displaystyle=\left[-t+r(\gamma-4\varepsilon_{0})-4r(rd+t)\right]\sum_{i=1}^{n}\beta_{i}$
$\displaystyle\geq\frac{r(\gamma-4\varepsilon_{0})}{8}\sum_{i=1}^{n}\beta_{i}.$

Since $\|\bar{\bm{v}}(\bm{\omega})\|_{2}\leq 1$ holds for all
$\bm{\omega}\in\mathbb{S}^{d-1}$ and $|a_{j}|=1$ for all $j\in[2M]$, then we
have for all $\bm{\beta}\in[0,1]^{n}$

$\displaystyle\max_{\bm{v}_{1},...,\bm{v}_{2M}\in\mathbb{B}^{d}}\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}a_{j}\bm{v}_{j}^{\top}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]$
$\displaystyle=\max_{\bm{v}_{1},...,\bm{v}_{2M}\in\mathbb{B}^{d}}\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}\bm{v}_{j}^{\top}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]\geq\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right].$

Furthermore, since

$\displaystyle\max_{\bm{v}_{1},...,\bm{v}_{2M}\in\mathbb{B}^{d}}\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}\bm{v}_{j}^{\top}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]$
$\displaystyle=\max_{\bm{v}_{1},...,\bm{v}_{2M}\in\mathbb{B}^{d}}\frac{r}{2M}\sum_{j=1}^{2M}\bm{v}_{j}^{\top}\left[\sum_{i=1}^{n}y_{i}\beta_{i}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]$
$\displaystyle=\frac{r}{2M}\sum_{j=1}^{2M}\max_{\bm{v}_{j}\in\mathbb{B}^{d}}\bm{v}_{j}^{\top}\left[\sum_{i=1}^{n}y_{i}\beta_{i}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]$
$\displaystyle=\frac{r}{2M}\sum_{j=1}^{2M}\left\|\sum_{i=1}^{n}y_{i}\beta_{i}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right\|_{2}$

where the equality holds when we set

$\bm{v}^{*}_{j}=\frac{\sum_{i=1}^{n}y_{i}\beta_{i}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}}{\left\|\sum_{i=1}^{n}y_{i}\beta_{i}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right\|_{2}}.$

∎

This means that

$\displaystyle\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right]+\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}a_{j}(a_{j}\bm{v}_{j}^{*})^{\top}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]-\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]$
$\displaystyle\geq\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right]+\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]-\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]$
$\displaystyle\geq\frac{r(\gamma-4\varepsilon_{0})}{8}\sum_{i=1}^{n}\beta_{i}.$

This further indicates that

$\displaystyle\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}\left[(\bm{\omega}_{j}+ra_{j}\bm{v}^{*}_{j})^{\top}x_{i}\right]_{+}\right]$
$\displaystyle\geq\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right]+\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}a_{j}(a_{j}\bm{v}_{j}^{*})^{\top}x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]$
$\displaystyle\quad-\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]$
$\displaystyle\geq\frac{r(\gamma-4\varepsilon_{0})}{8}\sum_{i=1}^{n}\beta_{i}.$

Since

$\displaystyle\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}\left[(\bm{\omega}_{j}+ra_{j}\bm{v}^{*}_{j})^{\top}x_{i}\right]_{+}\right]$
$\displaystyle=\frac{1}{2M}\sum_{j=1}^{2M}a_{j}\left[\sum_{i=1}^{n}y_{i}\beta_{i}\left[(\bm{\omega}_{j}+ra_{j}\bm{v}^{*}_{j})^{\top}x_{i}\right]_{+}\right]$
$\displaystyle\leq\frac{1}{2M}\sum_{j=1}^{2M}\left|\sum_{i=1}^{n}y_{i}\beta_{i}\left[(\bm{\omega}_{j}+ra_{j}\bm{v}^{*}_{j})^{\top}x_{i}\right]_{+}\right|$
$\displaystyle\leq\max_{j\in[2M]}\left|\sum_{i=1}^{n}y_{i}\beta_{i}\left[(\bm{\omega}_{j}+ra_{j}\bm{v}^{*}_{j})^{\top}x_{i}\right]_{+}\right|,$

we have

$\displaystyle\max_{j\in[2M]}\left|\sum_{i=1}^{n}y_{i}\beta_{i}\left[(\bm{\omega}_{j}+ra_{j}\bm{v}^{*}_{j})^{\top}x_{i}\right]_{+}\right|\geq\frac{r(\gamma-4\varepsilon_{0})}{8}\sum_{i=1}^{n}\beta_{i}\geq\frac{r(\gamma-4\varepsilon_{0})}{8}\max_{\bm{u}\in\mathbb{B}^{d}}\left|\sum_{i=1}^{n}y_{i}\beta_{i}(\bm{u}^{\top}x_{i})\right|.$

###  L.1 Proof of Claim 3

###### Proof.

For any $t>0$, by Chernoff-Hoeffding’s inequality we have

$\displaystyle\mathbb{P}\left(\left|\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right|\geq
t\right)\leq 2e^{-4Mt^{2}},$

by the fact that for each $x_{i}$,

$\mathbb{E}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right]=\frac{1}{2M}\sum_{j=1}^{2M}a_{j}\mathbb{E}_{\bm{\omega}\sim\mathcal{N}(\bm{0}_{d},I_{d})}[(\bm{\omega}^{\top}x_{i})_{+}]=0\cdot\mathbb{E}_{\bm{\omega}\sim\mathcal{N}(\bm{0}_{d},I_{d})}[(\bm{\omega}^{\top}x_{i})_{+}]=0.$

This indicates that

$\displaystyle\mathbb{P}\left(\bigcup_{i=1}^{n}\left\\{\left|\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right|\geq
t\right\\}\right)\leq\sum_{i=1}^{n}\mathbb{P}\left(\left|\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right|\geq
t\right)\leq 2ne^{-4Mt^{2}}.$

Therefore, we have

$\displaystyle\mathbb{P}\left[\left|\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right]\right|\leq
t\sum_{i=1}^{n}\beta_{i}\right]$
$\displaystyle\geq\mathbb{P}\left(\bigcap_{i=1}^{n}\left\\{\left|\frac{1}{2M}\sum_{j=1}^{2M}a_{j}(\bm{\omega}_{j}^{\top}x_{i})_{+}\right|\leq
t\right\\}\right)$ $\displaystyle\geq 1-2n\exp\left(-4Mt^{2}\right).$

∎

###  L.2 Proof of Claim 4

###### Proof.

By Assumption that there exists a function
$\bar{\bm{v}}(\omega):\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ with
$\|\bar{\bm{v}}(\omega)\|_{2}\leq 1$ such that

$\mathbb{P}\left(Y\int\bar{\bm{v}}^{\top}(\bm{\omega})X\mathbb{I}\\{X^{\top}\omega\geq
0\\}\mu(d\omega)\geq\gamma\right)\geq 1-\varepsilon,$

now we will show how to use this assumption to lower bound the probability

$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{\frac{y_{i}}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}[x_{i}^{\top}\bm{\omega}_{j}\geq
0]\geq\frac{\gamma}{2}\right\\}\geq 1-2\varepsilon\right).$

Now we define the following event,

$\displaystyle A$
$\displaystyle=\left\\{\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{y_{i}\int\bar{\bm{v}}^{\top}(\omega)x_{i}\mathbb{[}x_{i}^{\top}\omega\geq
0]\mu(d\omega)\geq{\gamma}\right\\}\geq 1-2\varepsilon_{0}\right\\},$
$\displaystyle B_{i}$
$\displaystyle=\left\\{\left|\frac{y_{i}}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}[x_{i}^{\top}\bm{\omega}_{j}\geq
0]-y_{i}\int\bar{\bm{v}}^{\top}(\omega)x_{i}\mathbb{[}x_{i}^{\top}\omega\geq
0]\mu(d\omega)\right|\leq\frac{\gamma}{2}\right\\},\quad i\in[n].$

Then it is easy to see that

$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{\frac{y_{i}}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}[x_{i}^{\top}\bm{\omega}_{j}\geq
0]\geq\frac{\gamma}{2}\right\\}\geq
1-2\varepsilon\right)\geq\mathbb{P}\left\\{A\cap\left(\bigcap_{i=1}^{n}B_{i}\right)\right\\}.$

By Chernoff-Hoelffding’s inequality, we have

$\displaystyle\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{y_{i}\int\bar{\bm{v}}^{\top}(\omega)x_{i}\mathbb{[}x_{i}^{\top}\omega\geq
0]\mu(d\omega)\geq{\gamma}\right\\}-\mathbb{E}\bm{1}\left[Y\int\bar{\bm{v}}^{\top}(\bm{\omega})X\mathbb{I}\\{X^{\top}\omega\geq
0\\}\mu(d\omega)\geq\gamma\right]\right|\leq\varepsilon\right)$
$\displaystyle\quad\geq 1-2e^{-2n\varepsilon_{0}^{2}},$

and this indicates that

$\displaystyle\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{y_{i}\int\bar{\bm{v}}^{\top}(\omega)x_{i}\mathbb{[}x_{i}^{\top}\omega\geq
0]\mu(d\omega)\geq{\gamma}\right\\}\geq\mathbb{E}\bm{1}\left[Y\int\bar{\bm{v}}^{\top}(\bm{\omega})X\mathbb{I}\\{X^{\top}\omega\geq
0\\}\mu(d\omega)\geq\gamma\right]-\varepsilon\right)$ $\displaystyle\quad\geq
1-2e^{-2n\varepsilon_{0}^{2}},$

which further implies that

$\displaystyle\mathbb{P}(A)=\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{y_{i}\int\bar{\bm{v}}^{\top}(\omega)x_{i}\mathbb{[}x_{i}^{\top}\omega\geq
0]\mu(d\omega)\geq{\gamma}\right\\}\geq 1-2\varepsilon\right)\geq
1-2e^{-2n\varepsilon_{0}^{2}}$

by the fact that

$\mathbb{E}\bm{1}\left[Y\int\bar{\bm{v}}^{\top}(\bm{\omega})X\mathbb{I}\\{X^{\top}\omega\geq
0\\}\mu(d\omega)\geq\gamma\right]=\mathbb{P}\left(Y\int\bar{\bm{v}}^{\top}(\bm{\omega})X\mathbb{I}\\{X^{\top}\omega\geq
0\\}\mu(d\omega)\geq\gamma\right)\geq 1-\varepsilon.$

Now we show the lower bound of $\mathbb{P}(B_{i})$ for each $i\in[n]$. By
Chernoff inequality, for each $i\in[n]$, we have

$\displaystyle\mathbb{P}(B_{i})$
$\displaystyle=\mathbb{P}\left(\left|\frac{y_{i}}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}[x_{i}^{\top}\bm{\omega}_{j}\geq
0]-y_{i}\int\bar{\bm{v}}^{\top}(\omega)x_{i}\mathbb{[}x_{i}^{\top}\omega\geq
0]\mu(d\omega)\right|\leq\frac{\gamma}{2}\right)\geq 1-2e^{-M\gamma^{2}}.$

Above all, by union bounds

$\displaystyle\mathbb{P}\left\\{A^{c}\cup\left(\bigcup_{i=1}^{n}B_{i}^{c}\right)\right\\}\leq\mathbb{P}(A^{c})+\sum_{i=1}^{n}\mathbb{P}(B_{i}^{c})\leq
2e^{-2n\varepsilon_{0}^{2}}+2ne^{-M\gamma^{2}}.$

This means that if $n\geq{\frac{\ln(2/\delta)}{2\varepsilon_{0}^{2}}}$ and
$M\geq\frac{\ln(4n/\delta)}{\gamma^{2}}$, then

$\displaystyle\mathbb{P}\left\\{A^{c}\cup\left(\bigcup_{i=1}^{n}B_{i}^{c}\right)\right\\}\leq\mathbb{P}(A^{c})+\sum_{i=1}^{n}\mathbb{P}(B_{i}^{c})\leq{\delta}.$

This indicates that

$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathbb{I}\left\\{\frac{y_{i}}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}[x_{i}^{\top}\bm{\omega}_{j}\geq
0]\geq\frac{\gamma}{2}\right\\}\geq
1-2\varepsilon\right)\geq\mathbb{P}\left\\{A\cap\left(\bigcap_{i=1}^{n}B_{i}\right)\right\\}\geq
1-\delta.$

Thus, if $n\geq{\frac{\ln(2/\delta)}{2\varepsilon_{0}^{2}}}$ and
$M\geq\frac{\ln(4n/\delta)}{\gamma^{2}}$, then

$\displaystyle\mathbb{P}\left(\forall\bm{\beta}\in[0,1]^{n}:\sum_{i=1}^{n}y_{i}\beta_{i}\left[\frac{r}{2M}\sum_{j=1}^{2M}\bar{\bm{v}}^{\top}(\bm{\omega}_{j})x_{i}\mathbb{I}\\{\bm{\omega}_{j}^{\top}x_{i}\geq
0\\}\right]\geq r(\gamma-4\varepsilon_{0})\sum_{i=1}^{n}\beta_{i}\right)\geq
1-\delta.$

∎

###  L.3 Proof of Claim 5

###### Proof.

By Chernoff-Hoeffding’s inequality, for each $i\in[n]$, we have

$\displaystyle\mathbb{P}\left(\left|\frac{1}{2M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1-\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)\right|\geq
t\right)\leq 2e^{-4Mt^{2}}.$

Therefore, by union bounds, we have

$\displaystyle\mathbb{P}\left(\bigcup_{i=1}^{n}\left\\{\frac{1}{2M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\geq\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)+t\right\\}\right)\leq
2ne^{-4Mt^{2}},$

which further indicates that

$\mathbb{P}\left(\bigcap_{i=1}^{n}\left\\{\frac{1}{2M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\leq\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)+t\right\\}\right)\geq
1-2ne^{-4Mt^{2}}.$

Therefore,

$\displaystyle\mathbb{P}\left(\forall\bm{\beta}\in[0,1]^{n}:\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]\leq
4r\sum_{i=1}^{n}\beta_{i}\left(\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)+t\right)\right)$
$\displaystyle\geq\mathbb{P}\left(\bigcap_{i=1}^{n}\left\\{\frac{1}{2M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\leq\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)+t\right\\}\right)\geq
1-2ne^{-4Mt^{2}}$

Now we only need to calculate the following probability,

$\displaystyle\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right),$

where the random vector $\bm{\omega}$ is a uniform random vector on the
surface of a $d$-dimensional ball, i.e., $\bm{\omega}\sim
U(\mathbb{S}^{d-1})$. We know that if $\bm{\omega}_{\mathcal{N}}$ is a
$d$-dimensional Gaussian random vector of mean $\bm{0}_{d}$ and variance
matrix $I_{d}$, then the random vector
$\bm{\omega}_{\mathcal{N}}/\|\bm{\omega}_{\mathcal{N}}\|_{2}\sim
U(\mathbb{S}^{d-1})$. Therefore, for each $i\in[n]$, we have

$\displaystyle\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)$
$\displaystyle=\mathbb{P}_{\bm{\omega}_{\mathcal{N}}\sim\mathcal{N}(\bm{0}_{d},I_{d})}\left(|\bm{\omega}_{\mathcal{N}}^{\top}x_{i}|<r\|\bm{\omega}_{\mathcal{N}}\|_{2}\right)$
$\displaystyle=\int_{0}^{+\infty}\mathbb{P}\left(|\bm{\omega}_{\mathcal{N}}^{\top}x_{i}|<r\|\bm{\omega}_{\mathcal{N}}\|_{2},\|\bm{\omega}_{\mathcal{N}}\|^{2}_{2}=t^{2}\right)f_{\chi^{2}(d)}(t^{2})dt$
$\displaystyle\text{by }\|\bm{\omega}_{\mathcal{N}}\|_{2}^{2}\sim\chi^{2}(d)$
$\displaystyle\leq\int_{0}^{+\infty}\mathbb{P}\left(|\bm{\omega}_{\mathcal{N}}^{\top}x_{i}|<rt^{2}\right)f_{\chi^{2}(d)}(t^{2})dt$
$\displaystyle\leq\int_{0}^{+\infty}\frac{rt^{2}}{\sqrt{2\pi}}f_{\chi^{2}(d)}(t^{2})dt$
$\displaystyle=\frac{r}{\sqrt{2\pi}}\int_{0}^{+\infty}t^{2}f_{\chi^{2}(d)}(t^{2})dt$
$\displaystyle\leq\frac{r}{\sqrt{2\pi}}\left(\int_{0}^{+\infty}tf_{\chi^{2}(d)}(t^{2})dt+\int_{0}^{+\infty}t^{3}f_{\chi^{2}(d)}(t^{2})dt\right)$
$\displaystyle=\frac{r}{2\sqrt{2\pi}}\left(\int_{0}^{+\infty}f_{\chi^{2}(d)}(t^{2})d(t^{2})+\int_{0}^{+\infty}t^{2}f_{\chi^{2}(d)}(t^{2})d(t^{2})\right)$
$\displaystyle=\frac{r}{2\sqrt{2\pi}}\left(\int_{0}^{+\infty}f_{\chi^{2}(d)}(t)dt+\int_{0}^{+\infty}tf_{\chi^{2}(d)}(t)dt\right)$
$\displaystyle=\frac{r}{2\sqrt{2\pi}}\left(1+d\right)\leq rd.$

This indicates that

$\displaystyle\mathbb{P}\left(\forall\bm{\beta}\in[0,1]^{n}:\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]\leq
4r\left(rd+t\right)\sum_{i=1}^{n}\beta_{i}\right)$
$\displaystyle\geq\mathbb{P}\left(\forall\bm{\beta}\in[0,1]^{n}:\sum_{i=1}^{n}\beta_{i}\left[\frac{2r}{M}\sum_{j:|\bm{\omega}^{\top}_{j}x_{i}|<r}1\right]\leq
4r\sum_{i=1}^{n}\beta_{i}\left(\mathbb{P}\left(|\bm{\omega}^{\top}x_{i}|<r\right)+t\right)\right)$
$\displaystyle\geq 1-2ne^{-4Mt^{2}}$

∎