# Predicting Query-Item Relationship using Adversarial Training and Robust
Modeling Techniques

Min Seok Kim  Kakao CorporationSouth Korea<EMAIL_ADDRESS>
(2022)

###### Abstract.

We present an effective way to predict search query-item relationship. We
combine pre-trained transformer and LSTM models, and increase model robustness
using adversarial training, exponential moving average, multi-sampled dropout,
and diversity based ensemble, to tackle an extremely difficult problem of
predicting against queries not seen before. All of our strategies focus on
increasing robustness of deep learning models and are applicable in any task
where deep learning models are used. Applying our strategies, we achieved 10th
place in KDD Cup 2022 Product Substitution Classification task.

Search Relevance, KDD Cup 2022, Deep Learning, Adversarial Training,
Transformer, LSTM

††journalyear: 2022††copyright: rightsretained††conference: To be presented at
KDD Cup 2022 Workshop: ESCI Challenge for Improving Product Search; August 17,
2022; Washington, DC, USA††booktitle: KDD Cup 2022 Workshop: ESCI Challenge
for Improving Product Search, August 17, 2022, Washington, DC, USA††ccs:
Information systems Query representation††ccs: Applied computing Online
shopping

##  1\. Introduction

KDD Cup 2022 presents a problem of having to accurately describe the
relationship between user search queries and shopping items, in motivation to
improve customer experience and search engagement. The competition presents
Shopping Queries Dataset (Reddy et al., 2022), a multilingual e-commerce
dataset in three languages: English, Spanish and Japanese.

Among the three tasks presented in the competition, the goal of “Product
Substitute Identification” (task 3) is to correctly identify whether a search
query and and an item are in a substitute relationship or not. A relationship
is considered substitute when an item fails to fulfill some aspects of the
query but can be functioned as substitute of a completely relevant item. The
competition’s evaluation metric is Micro F1 Score as classes are imbalanced.

In this work, we discuss a simple but effective model architecture and
training techniques that placed us among top-10 solutions in KDD Cup 2022.
Built upon a solid validation strategy, where models are evaluated based on
“unseen” query - item pairs, our solution is a simple combination of pre-
trained transformer (Vaswani et al., 2017) (Devlin et al., 2018) and LSTM
(Hochreiter and Schmidhuber, 1997), trained using effective techniques to
increase model robustness, such as exponential moving average of weights,
multi-sampled dropout, dynamic learning rate scheduling for different layers.
Our final solution is a mix of models fused with diversity based ensemble. As
all our strategies are task-independent and focus on increasing robustness of
deep learning models in general, we believe our methodologies are easily
applicable to any other tasks where deep learning models are used.

##  2\. Proposed Solution

###  2.1. Redefining the Problem

We realized that dataset had been split into train and public test set grouped
by queries, so that queries in public test set do not appear in train set and
vice versa. So we redefine the problem as identifying relationship between
“unseen” queries and items, which makes the problem extremely difficult.
Realizing this difference was crucial as wrong validation strategy may not be
able to properly mimic the competition evaluation environment.

Table 1. Model Performance for each Technique Applied Technique | Cross Validation Score | Relative Gain/Loss vs. Control
---|---|---
DeBERTa-v3-Large (Baseline) | 0.8229 | +0.0000
Add LSTM Head | 0.8226 | -0.0003
Add LSTM Head with higher LR | 0.8234 | +0.0005
Adversarial Training | 0.8262 | +0.0028
Exponential Moving Average | 0.8265 | +0.0003
Multi-Sampled Dropout | 0.8267 | +0.0002
Cosine Schedule → StepLR | 0.8267 | +0.0005
XLM-RoBERTa-Large | 0.8237 | -0.0026
RemBERT | 0.8247 | -0.0030

###  2.2. Validation Strategy

When dataset is split into a regular random train-test split, model training
worked relatively well and validation loss would successfully decrease for 8
to 10 epochs. However, same model, trained the same way, on a train-test split
where sets of queries (ex. airpods) would appear only on either train or test
set, model training will not work well and validation loss would not decrease
for a single epoch. We presume this occurs as the given problem is not a
general text classification task but requires identification of two texts:
search query and item. So we decided to split the given train dataset in the
same manner.

As there exists class imbalance between substitute labels and non-substitute
labels, we use stratification to ensure equal distribution of each class in
local train and test sets. To sum up, we use StratifiedGroupKFold cross
validation, where K is 5, and grouped on queries, and determined model
performance solely upon micro f1 score on all folds.

All of our experiments are run in a strict comparison environment, where there
always exists a control model for comparison and only a single hyper-parameter
would be changed for the experiment model.

###  2.3. Model Backbone

We started out the competition, after some exploratory data analysis, with an
agressive model selection. We tried out both classic LSTM models and pre-
trained transformers and the latter scored around 0.05 higher in previously
mentioned cross validation setting. Including the multilingual-BERT model
(Devlin et al., 2018) used as competition baseline model, we tried out many
models including XLM-RoBERTa (Conneau et al., 2019), RemBERT (Chung et al.,
2021) to check basic model performance. DeBERTa-V3-Large (He et al., 2021)
came out to be the most effective pre-trained model by far, achieving micro-f1
score of 0.8229, and selected as our baseline model.

For model input, we concat search query and item titie using special token in
following manner: “¡Query¿ [Special Token] ¡Item Title¿”. Item title goes
through a very simple preprocessing of only cleaning special characters. More
intense cleaning, such as underscoring, deteriorated model performance.
Maximum sequence length is set to 78, covering approximately 99.7 percent of
all data samples.

Figure 1. Visualization of Final Model Structure

###  2.4. LSTM Head

We improve our model structure by adding an LSTM layer after DeBERTa backbone.
Note that the added LSTM layer is not pre-trained. As training finished in one
or two epochs, applying DeBERTa-V3-Large’s learning rate of 5e-6 was not
adequate and actually led to a decrease of -0.0003 in f1 score. So the LSTM
layer would need higher learning rate than other pre-trained layers. We
initially set learning rate for pre-trained DeBERTa layers to 5e-6 and LSTM
layer to 1e-3 and use learning rate scheduling to decrease the rates during
model training. Applying LSTM head with adjusted learning rate led to a f1
score gain of +0.0005.

###  2.5. Adversarial Training

We apply Adversarial Weight Perturbation (Wu et al., 2020) to increase model
robustness. We use adversarial learning rate of 1e-4. Starting adversarial
training from the very beginning was most effective, instead of starting at a
later period (ex. epoch 2), as entire training ended in a very short period.
After applying Adversarial Weight Perturbation, training became much more
stable: validation loss would decrease for 3 to 4 epochs instead of a single
epoch. This led to a f1 score gain of +0.0028.

###  2.6. Exponential Moving Average

We calculated exponential moving average of weights during mini-batch
training. We applied a decay of 0.999 when calculating new average of weights.
Doing so led to a relative micro-f1 score gain of +0.0003.

###  2.7. Multi-Sampled Dropout

We apply Multi-Sampled Dropout (Inoue, 2019) for better generalization. After
DeBERTa’s pooling layer, we add 5 dropout layers with different masks, each
with a dropout rate of 0.5. Output of each dropout layers will be passed to
fully connected layers, which all share the same weights. Output of all fully
connected layers were averaged.

At this point, the final model structure is shown in Figure 1. It is a simple
model with a pre-trained DeBERTa backbone, LSTM head, pooling layer
initialized using pre-trained DeBERTa weights, multi-sampled dropout layers,
and finally the classification layer.

###  2.8. Learning Rate Scheduling

We used cosine learning rate scheduling throughout the competition. Towards
the end of competition, we tried out StepLR schedule with decay every epoch,
decayed by gamma of 0.2. Changing learning rate scheduler resulted a +0.0005
change in competition metric.

###  2.9. Diversity based Model Ensemble

After applying all modifications mentioned above, we re-trained the top few
backbone models for a secondary model selection, to check whether our
modifications would impact some backbone models to a greater degree and to use
some of the models in ensemble. As a result, the RemBERT model, which had a
-0.003 f1 score loss in the original model selection, came out close second
with only 0.0003 score difference with DeBERTa-V3-Large. Although applying
both 2.6 Exponential Moving Average and 2.7 Multi-Sampled Dropout led to a
total of +0.0005 score gain for DeBERTa-V3-Large model, we can see that
applying the same strategies on the RemBERT model led to much greater score
gain.

In addition to a soft-voting based ensemble, a technique where model
prediction probabilities are summed to get final predictions, we use a
diversity based approach when ensembling different models. For model
diversity, instead of using the same backbone twice during model ensemble, it
was shown to be more effective to use two different backbones, even if it’s
single model score was relatively lower. Along with DeBERTa-V3-Large and
RemBERT models, using the XLM-RoBERTa-Large model, despite its lower f1 score,
in the end led to both highest public and private leaderboard scores among all
ensemble combinations.

For data diversity, we ensured each of our ensemble models were trained on
different datasets. We realized two days before the end of competition that
there was some non-overlapping data between task1 and task 3. As more data can
make deep learning models more robust, we secured task 1’s non-overlapping
234,286 samples of data, which is a 12.8 percent increase in the numbers of
total train data. Table 2 shows cross validation scores for the combined
dataset. Note that cross validation scores decrease when evaluated on the
combined dataset which does not mean decrease in model performance but a
change due to the extra data. In the end, we selected DeBERTa-V3-Large
validated on fold 0 and trained on the rest, and RemBERT model validated on
fold 2 and trained on the remaining folds. Unfortunately, we had to use XLM-
RoBERTa-Large model trained only on task 3 data and could not apply some
techniques such as multi-sampled dropout and exponential moving average, due
to time constraints.

Table 2. Final Submitted Models Summary Model | CV (Task 1+3) | 2.4 | 2.5 | 2.6 | 2.7 | 2.8
---|---|---|---|---|---|---
DeBERTa-v3-Large | 0.8165 | O | O | O | O | O
RemBERT | 0.8162 | O | O | O | O | O
XLM-RoBERTa-Large | - | O | O | X | X | O

Table 2 describes our set of final models. In summary, our final submission
uses three backbone models: DeBERTa-v3-Large, RemBERT, and XLM-RoBERTa-Large.
For the first two models, both task 3 and task 1 data were used for training.

###  2.10. Accelerated Inference

The competition submission environment used a single NVIDIA V100 GPU (16GB
RAM) and had a timeout of 120 minutes for docker environment setup and both
public and private test set evaluations. To maximize the number of models used
for ensemble, we applied float16 precision, which improved inference speed by
2.3 times. More specifically, we were able to reduce inference time of public
test set’s 277044 samples for a DeBERTa-v3-Large model, from 23 minutes to 10
minutes when sequence length was 78. For sequences of length 256, inference
time decreased from 82 minutes to 36 minutes.

Table 3. Inference Times for Different Float Precisions Sequence Length | Float32 Precision | Float16 Precision
---|---|---
78 | 23 minutes | 10 minutes
256 | 82 minutes | 36 minutes

##  3\. Conclusion

In this work, we discussed our approach of effectively capturing the
relationship between search queries and shopping items, as part of our 10th
place solution in KDD Cup 2022. Built upon a solid validation strategy, where
models are evaluated based on “unseen” query - item pairs, our solution is a
simple combination and pre-trained transformer backbone and LSTM head, trained
using techniques to increase model robustness, including adversarial training,
exponential moving average, multi-sampled dropout, dynamic learning rate
scheduling for different layers. Our final solution is an ensemble of models
selected based on both model and data diversity. We believe our methods
presented in this paper would help increase robustness of deep learning models
in general.

## References

  * (1)
  * Chung et al. (2021) Hyung Won Chung, Thibault Févry, Henry Tsai, Melvin Johnson, and Sebastian Ruder. 2021.  Rethinking Embedding Coupling in Pre-trained Language Models. In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_. OpenReview.net.  https://openreview.net/forum?id=xpFFI_NtgpW
  * Conneau et al. (2019) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Unsupervised Cross-lingual Representation Learning at Scale.  _CoRR_ abs/1911.02116 (2019).  arXiv:1911.02116 http://arxiv.org/abs/1911.02116
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _CoRR_ abs/1810.04805 (2018).  arXiv:1810.04805 http://arxiv.org/abs/1810.04805
  * He et al. (2021) Pengcheng He, Jianfeng Gao, and Weizhu Chen. 2021.  DeBERTaV3: Improving DeBERTa using ELECTRA-Style Pre-Training with Gradient-Disentangled Embedding Sharing.  arXiv:2111.09543 [cs.CL]
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural Comput._ 9, 8 (nov 1997), 1735–1780.  https://doi.org/10.1162/neco.1997.9.8.1735
  * Inoue (2019) Hiroshi Inoue. 2019\.  Multi-Sample Dropout for Accelerated Training and Better Generalization.  https://doi.org/10.48550/ARXIV.1905.09788
  * Reddy et al. (2022) Chandan K. Reddy, Lluís Màrquez, Fran Valero, Nikhil Rao, Hugo Zaragoza, Sambaran Bandyopadhyay, Arnab Biswas, Anlu Xing, and Karthik Subbian. 2022.  Shopping Queries Dataset: A Large-Scale ESCI Benchmark for Improving Product Search.  arXiv:2206.06588
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is All you Need. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * Wu et al. (2020) Dongxian Wu, Shu-Tao Xia, and Yisen Wang. 2020.  Adversarial Weight Perturbation Helps Robust Generalization. In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ (Vancouver, BC, Canada) _(NIPS’20)_. Curran Associates Inc., Red Hook, NY, USA, Article 249, 12 pages.


# Safepaths: Vaccine Diary Protocol and Decentralized Vaccine Coordination
System using a Privacy Preserving User Centric Experience

Abhishek Singh  MIT Media Lab Ramesh Raskar  MIT Media Lab Anna Lysyanskaya
Brown University

###### Abstract

In this early draft, we present an end to end decentralized protocol for the
secure and privacy preserving workflow of vaccination, vaccination status
verification, and adverse reactions or symptoms reporting. The proposed system
improves the efficiency, privacy, equity and effectiveness of the existing
manual system while remaining inter-operable with its capabilities. We also
discuss various security concerns and alternate methodologies based on the
proposed protocols.

##  1 Introduction

#### Motivation:

Recent announcements of vaccines have created a sense of hope for the near
future of the society currently burdened with lock-downs and quarantines.
However, a lot of effort and coordination is required to go from successful
vaccines to successful vaccination programs to curb the disease spread. We
believe a user-centric design using vaccination cards and/or mobile phones can
play a critical role in the micro-planning and last mile issues. In this work,
we integrate work in user privacy, cryptography, and user interaction to
design secure and private protocols which span from the starting step of
vaccination program enrolment to all the way to symptoms reporting from
potential side effects of vaccination.
We consider the first four of the following parts of the system:

  * •

Indicating eligibility based on priority tiers (anonymity via vaccine
coupons),

  * •

Second dose coordination (privacy preserving record linkage),

  * •

vaccine verification/passports (interoperability and privacy),

  * •

Safety and efficacy monitoring (crowdsourced monitoring of safety and efficacy
using private aggregation)

  * •

Trust and communication (social media analytics, contextual messaging)

Figure 1: Entity and information flow depicting the system at a high level. We
project this diagram as the backbone of the proposed system. We describe the
detailed information flow and privacy preserving mechanisms in the next
figures.

#### Participants:

Let us consider the different participants and their corresponding roles.

  * •

Issuer is a trusted entity that initiates the enrolment process by
distributing the coupons which would be eventually used for getting vaccinated
as described later. In our use-case the issuer could be CDC or any similar
authoritative body that currently monitors the distribution of the vaccines.
Later, the issuer also issues the vaccination credentials, or badges. Strictly
speaking, the latter issuer (the badge issuer) need not be the same entity.

  * •

Distributor is the entity that receives the vaccination coupons from the
issuer and distributes it locally to individuals. In our use-case the
distributor could be the city government office.

  * •

User is the person who wants to get vaccinated and use their vaccination
status later on to obtain a vaccination passport that will be used as a proof
of vaccination status.

  * •

Pharmacy is the entity that performs the vaccination. This could be nearby
health/pharmacy stores like CVS.

  * •

Verifier refers to the set of authorized users that can verify the vaccination
status of any user after their consent. This can be a venue owner that is
managing access to their facilities.

  * •

Healthcare researcher is a participant who may be on the receiving end of
alerts from users who choose to provide feedback for the benefit of the
community.

#### Phases:

We model the vaccination process as consisting of the following phases:

  * •

Setup and registration phase in which the entities establish a trust
infrastructure. In particular, the trusted Issuer generates its cryptographic
keys and publishes the public half of those keys. Other participants that
require keys generate their keys as well and obtain certificates on the public
parts of their keys. For example, a distributor may want to be able to
digitally sign a statement such as “Alice is eligible for vaccination."
Additionally, pharmacies need a way to authentically communicate the fact that
Alice has been vaccinated.

  * •

Coupon distribution phase in which the Issuer and Distributor jointly create,
for each eligible user $U_{i}$ a string $c_{i}$ that constitutes the user’s
vaccination coupon, and communicate it to the user.

  * •

Vaccination phase one in which a User uses his coupon $c_{i}$ possibly
together with other forms of identification (or biometrics) to convince a
Pharmacy of his eligibility to receive the vaccine. If the pharmacy determines
that the coupon is valid for this user, the user receives a first dose of the
vaccine together with a badge $b_{i}$ that can be used as proof of
vaccination.

  * •

Vaccination phase two in which a User uses his badge $b_{i}$, possibly
together with other forms of identification (or biometrics) to convince the
Pharmacy that he’s eligible for a second shot of the vaccine. If the pharmacy
determines that the badge is valid for this user, the user receives the second
shot of the vaccine together with an updated badge $b_{i}$ that can be used as
proof of vaccination.

  * •

Verification phase in which a User uses his badge $b_{i}$, possible together
with other forms of identification or biometrics to convince a Verifier of his
vaccination status.

  * •

Gathering useful data phase A user who has been vaccinated can use his badge
$b_{i}$ to contact healthcare researchers in case of adverse effects or to
report other helpful information about the efficacy of the vaccine.

###  1.1 Security, privacy, and usability considerations

We consider different aspects of the problem from a practical standpoint:

Unforgeability of coupons

No adversary, even if he controls the distributor, should be capable of
creating functional and valid coupons without say-so from the issuer.
Moreover, a coupon cannot be used by more than one user.

(Optional) Non-transferability of coupons

If both the issuer and the distributor are honest, then a coupon issued to
user $i$ cannot be used by any other user $j$ where $j\neq i$. This is
optional as precise personalization of coupons requires information about
specific eligible individuals, and this information may be unavailable or too
costly to obtain when the coupons are created. Moreover, users have an
incentive not to transfer their coupons to others, so that they can get
vaccinated themselves, so personalization may be unnecessary.

Unforgeability and non-transferability of badges

Similar to the unforgeability and non-transferability properties of the
coupon, the badges should also have the same property. This would mean that no
entity should be able to create functional and valid coupons without say-so
from either the distributor or the issuer.

(Trade-off) Off-line phases

A phase is off-line if it does not involve that any particular trusted
participant who isn’t explicitly part of the phase be online (require internet
connection to exchange data with servers). The more phases are off-line, the
easier are the logistics and equity aspects of it.

User privacy from the issuer

The issuer (assuming computationally bounded) should not be able to infer the
identity of the vaccinated user; from the issuer’s point of view there is no
difference whether it was Alice or Bob. This property prevents against any
centralization of the identity of the vaccinated users by any untrusted
entity.

(Trade-off) User privacy from the verifiers

The verifier should not learn anything about a user other than her vaccination
status after performing the verification protocol.

(Trade-off) Non-traceability

The verifiers should not be able track the user across different venues even
if they collude with each other.

Accessibility

Any user, even one who does not have access to smartphones or other possibly
costly devices, should be able to participate in the protocol.

Usability

The system should be easy, intuitive to use, not require excessive training to
set up, not require a significant amount of time to use. This applies not just
to users, but also to whoever administers the other components of the system:
the admins of the issuer, the distributors, the pharmacies, etc.

Trade-offs: The cost of having the vaccination phase offline is that each
Pharmacy must be able to issue a badge by itself, meaning that it will need to
have a secret key, use digital signatures, etc; also either verification of a
badge will require that the verifier know the pharmacy’s public key, or that
some more sophisticated cryptographic algorithm (such as delegatable anonymous
credentials [7]) be used.

Unless the badge is physically embedded into a user’s body, it is hard to
achieve non-transferability of badges and user privacy from verifiers at the
same time. The best we can do is to relax the assumption and have verifier
learn some attribute (possibly of the verifier’s choice) of a user’s identity,
and then the rest of the proof that a user with this attribute has been
vaccinated can be communicated via a zero-knowledge proof.

##  2 Paper card based solution

We use existing and well-studied cryptographic building blocks in the
following protocols for performing operations such as $\mathsf{sign}$ and
$\mathsf{verify}$ which can be built using a commonly used digital signature
scheme, one such example is ECDSA [3].
In the paper-based solution we focus on keeping the proposed system as inter-
operable as possible with the existing system. The user receives a coupon from
the distributor (e.g. city) and goes to the pharmacy for getting vaccinated.
Upon vaccination, the pharmacy provides the user a QR code that contains
information related to the vaccination status, we refer this piece of
information as badge. The badge can be shown by the user for proving their
vaccination status. Now we describe the protocol in more detail -

###  2.1 Protocol

#### Coupon distribution

The coupon code is generated by the issuer and delivered to the user through
the distributor. The process involves the issuer setting up a secret and
verifying key for generating the coupons such that the validity of the coupon
can be examined by only knowing the verifying key.

  * •

The Issuer $I$ (e.g. CDC) first generates its key pair
$(\mathit{sk}_{I},\mathit{vk}_{I})$ for the signature scheme. By
$\mathsf{sign}_{I}(m)$ we will denote the output of the digital signature
signing algorithm (such as the ECDSA algorithm [3]) with input as the Issuer’s
secret signing key $\mathit{sk}$ and the message $m$. By
$\mathsf{verify}_{I}(m,\sigma)$ we will denote the output of the corresponding
(e.g., ECDSA) signature verification algorithm under the verification key
$\mathit{vk}_{I}$ on input the message $m$ and a purported signature $\sigma$.

  * •

The issuer then generates $n$ coupons for a given zip code and job type of the
users by signing the tuple $m_{i}=(i,\mbox{zip code},\mbox{job type})$ for
every i’th coupon. A given coupon $c$ can be represented as

$c_{i}=\\{m_{i},\mathsf{sign}_{I}(m_{i})\\}$

Finally, the set of coupons $\mathcal{C}=\\{c_{i}|\forall i\leq n\\}$ is given
to a local distributor based on zip code and job type.

  * •

The distributor gives the coupon to the users after performing an eligibility
check.

#### Vaccination

In this phase, the user gets vaccinated and receives three QR-codes in
addition to the previously received coupon code. As shown in Figure 2, all
four QR-codes are printed on the two sides of the paper with the first side
consisting of coupon and badge, and the other side has the status and pass-
key. The high level idea is to keep detailed information about the user’s
vaccination on the first side and keep the minimal information required for
proving the vaccination status on the other side.

  * •

The user gets his coupon $c$ and shows it to the pharmacy to get vaccinated.

  * •

The pharmacy runs $\mathsf{verify}_{I}(c)$ to validate the coupon $c$ and then
checks whether the coupon has been used up already using VAMS-like
system111https://www.cdc.gov/vaccines/covid-19/reporting/vams/index.html. Upon
successful validation, pharmacy vaccinates the user.

  * •

The pharmacy collects the user’s PII and verifies that it matches the user’s
ID (e.g. - by looking at the user’s driving license). User_PII refers to the
information tied to the identity of the user (e.g. - user’s full name, date of
birth and etc.), which would be used for vaccination status verification in
the future.

  * •

The pharmacy generates a header $h$ such that $h=\\{\text{dose\\_info},c\\}$
and generates

$\text{badge\\_info}=\\{\text{dose\\_info},c,\mathsf{hash}(\text{User\\_PII,
salt})\\}$

and submits it to the issuer for signing it. Salt refers to a high entropy
number to ensure sufficient randomness of the hashed value; in particular,
this ensures that the hashed value itself does not reveal a user’s PII.

  * •

The badge issuer (that could be the same issuer as the entity that issues the
coupons or a different entity with a different signing key) receives the
pharmacy request for signing the badge_info. The issuer updates its publicly
visible registry by marking the coupon $c$ as used and signs the digest of the
user information by performing two signatures
$\mathsf{sign}_{I}(\text{badge\\_info})$ and
$\mathsf{sign}_{I}(\text{\\{vaccinated, $\mathsf{hash}$(passkey)\\}})$ and
returns it back to pharmacy. Here vaccinated refers to the minimal information
required to indicate a user is vaccinated. This could be as minimal as 0 (not
vaccinated) and 1 (vaccinated). However, the standards might require
indicating relatively more information such as second dose, date of
vaccination and etc.

  * •

The pharmacy issues two QR-codes for the user -

$\textit{badge}=\\{\text{badge\\_info},\mathsf{sign}_{I}(\text{badge\\_info})\\}$
$\textit{status}=\\{\text{\\{vaccinated,
$\mathsf{hash}(passkey)$\\}},\mathsf{sign}_{I}(\text{\\{vaccinated,
$\mathsf{hash}(passkey)$\\}})\\}$ $\textit{passkey}=\\{\text{User\\_PII,
salt}\\}$

  * •

The user has finally four QR-codes with them coupon, badge, status, and
passkey.

  * •

Second dose The user can receive the second dose in the future from any of the
pharmacy by presenting their badge which would be verified by the pharmacy
first and the vaccination procedure would the proceed as above. The granular
information about the vaccination enables the pharmacy to administer the right
second dose of vaccine for the user.

#### Verification

The verification process happens in two phases - first, the validity of the
badge is examined to make sure the user is carrying a valid vaccination proof
and then the identity of the user is examined to make sure that the QR-codes
belong to the person carying it.

  * •

The user goes to the venue and present their badge.

  * •

The venue verifies the integrity and validity of the badge by performing
$\mathsf{verify}$(badge)

  * •

The venue request the pass-key if they want to verify the identity of the
user. The identity is verified using a government issued ID. User may or may
not give the pass-key based on their preference.

Figure 2: The representation of the paper based solution and how the QR code
representation of different stickers could look like. QR code 1 carries coupon
information that is used by the user for getting vaccination, QR code 2
carries badge information that consists of information related to vaccination
and tied to user identity using passkey. QR code 3 has proof of vaccination
and the QR code 4 has passkey of the user that contains PII.

###  2.2 Security

There are security benefits of fragmenting the user information into three
distinct QR-codes. First, User_PII does not get centralized at any point under
the assumption that pharmacy and venues do not collude with CDC or with some
global data warehouse. The protocol prevents users from forging the
vaccination proof by using digital signatures. However, a user can sell their
coupon to other users in the same zip code. While using zip_code and job_type
impedes the potential buyers, more personalization could be done for the
coupons.

The proposed solution poses some privacy risks such as venues keeping track of
every user’s passkey and creating a PII database of vaccinated users by
coordinating with other venues. This can be prevented by mandating the venue
owners to only perform the scanning using a trusted app that deletes the user
record after the verification process is over. However, such a regulation
enforced privacy would not protect against worst case attackers. Another
potential privacy leakage could happen if the pharmacy does not delete their
record locally after generating the passkey. This would enable the semi-honest
pharmacy to keep a local database of private information of every user.
Pharmacies maybe required to keep the PII records in case the user loses the
vaccination card and the salt values.

Unforgeability of coupons

This property is satisfied in the current scheme through the use of digital
signatures. Under the assumption that the issuer keeps the secret signing key
(sk_I) secure with them, it would be computationally hard for any attacker to
generate a coupon with valid signature.

(Optional) Non-transferability of coupons

The coupon is personalized to the granularity of zip_code and job_type.
Therefore, the coupon is transferable across individuals sharing a common
zip_code and job_type.

Unforgeability and non-transferability of badges

The proposed scheme provides unforgeability of the badges by the usage of
digital signature where signing is performed by the issuer. Hence, as long as
the signing key (sk_I) is secretly kept by the issuer the scheme should be
unforgeable from a practical standpoint. The badges are also non-transferable
due to the hash of User_PII embedded inside it. This User_PII is personally
identifiable and hence no other user should share the same PII and hence it
should be non-transferable.

(Trade-off) Off-line phases

The proposed system is offline for the coupon distribution phase and
verification phase. However, both vaccination phase require the pharmacy to be
online and connected with internet in order to communication with the issuer
for the badge generation process.

User privacy from the issuer

Under the assumption of pre-image resistance of the hashing function used when
generating the badge, the issuer should not be able to infer the User_PII by
receiving its hash.

(Trade-off) User privacy from the verifiers

The verifier does not learn anything more than the vaccination status of the
user, however, it checks the government issued ID which belongs to the user
and hence this protocol does not provide full privacy protection against the
verifier.

(Trade-off) Non-traceability

The current protocol does not provide protection against traceability across
the venues because verifier can store User_PII shown as part of the
verification process.

Accessibility

The proposed scheme is highly accessible because it does not require any user
to own a smartphone or any other costly device.

Usability

From a usability standpoint, the scheme only requires the users to obtain a
piece of paper from a distributor and show it to the pharmacy. From the
perspective of the issuer, they are required to maintain a secure server that
has capabilities of maintaining a key infrastructure and serve the requests of
the pharmacy. The scheme requires a mechanism for the pharmacy to be able to
interact with the issuer for issuing the badge to a user. Similarly, verifier
requires a system that can use the issuer public key and perform successful
validation of the signatures. Barring the one-time software installation part,
the remaining system can work in automated fashion and mostly requires
scanning of QR-codes by the pharmacy and verifiers.

##  3 App based solution

As discussed in the Section 2.2 the paper based solution introduces some of
the security and feasibility constraints which limits the effectiveness of the
overall system. We propose the following smartphone based protocol to
circumvent some of the issues.

###  3.1 Protocol

#### Coupon distribution

The coupon distribution happens in a similar way described in the paper-based
solution. The coupon code is generated by the issuer and delivered to the user
through the distributor. Unlike the paper-based solution, the user also
generates a public-private key pair and a private data structure for their
personal information that would be useful for the upcoming phases.

  * •

The issuer generates key pairs for the signature scheme and issues the coupon
in precisely the same way as discussed in the paper-based solution.

  * •

The distributor provides coupon code

$c=\\{(i,\text{zip code, job type}),\mathsf{sign}(i,\text{zip code, job
type})\\}$

to the users which either is scanned in person by the user or gets downloaded
in the user app through a confidential URL provided by the distributor.

  * •

The user generates a public-private key pair $(pk_{U},sk_{U})$ such that
private key $sk_{U}$ is stored with the user in a secure enclave [1] or
sufficiently secure system where even the user can not see it themselves but
only decrypt information by using decryption API with the operating system
(this property would be useful later on to prevent forgeability of the
vaccination status). The user also generates

$\text{pii\\_hashes}=\mathsf{hash\\_tree}(\\{\text{User\\_PII}_{i},\text{salt}_{i}\big{|}\forall
i\in\\{\text{User\\_PII}\\}\\})\\}$

Here $\mathsf{hash\\_tree}$ takes a set of user’s PII (e.g. - name, age,
residence and etc.) and processes individual elements of the set to construct
a merkle tree [3].

  * •

Second dose The user can receive the second dose reminder through the app in
the future and they can go the pharmacy and get their badge scanned. The
pharmacy validates the badge and the vaccination procedure would the proceed
as mentioned above for the first dose.

#### Vaccination

The high level idea here is that the user presents the coupon code at the
pharmacy then user gets vaccinated and then user presents their PII to the
pharmacy so that it can be signed securely by the issuer for later use.

  * •

The user shows their coupon code in the app for scanning at the pharmacy.

  * •

The pharmacy validates the scanned coupon code $c$ and proceeds to vaccination
upon successful validation of the coupon.

  * •

After vaccinating the user, the pharmacy generates

$\text{badge\\_info}=\\{\text{dose\\_info},c,\mathsf{pii\\_hashes}\\}$
$\text{v\\_status}=\\{\text{vaccinated},pk_{U},\mathsf{pii\\_hashes}\\}$

Using the pii_hashes, user can perform selective disclosure of the information
and still be able to prove the integrity of their badge.

  * •

The pharmacy sends $h$ to be signed by the issuer and then returns the $badge$
and $status$ to the user by providing {badge_info,$\mathsf{sign}$(badge_info)}
and {v_status, $\mathsf{sign}$(v_status)} respectively.

#### Verification

In the verification phase, the goal of the user is to prove that they have
been vaccinated by providing a digitally signed information that consists of
sufficient and minimal information about the user’s vaccination status and
identity. In comparison to the paper based protocol, the user can now
selectively disclose only a subset of information by using the
$\mathsf{pii\\_hashes}$.

  * •

The user walks in to the public venue and presents their badge.

  * •

The venue scans the badge and validates the signature by performing
$\mathsf{verify}_{I}(status)$ and requests particular personal information.

  * •

The user gives information by performing consent based selective disclosure of
their private information.

  * •

The venue confirms the identity of the user based on the information received
and the government issued ID.

###  3.2 Security

This protocol has all of the properties discussed in the paper-based protocol
in the section 2.2 and further improves the security by introducing the idea
of selective disclosure of PII. This enables a fine grained control on the
personal information for an user. However, the previously discussed attack
where the venues could create a database of User_PII is still possible. To
circumvent such an attack, the app could provide anonymous credentials, which
is the current direction of our ongoing work.

Unforgeability of coupons

Similar to the paper based scheme, this current scheme protects against
unforgeability through the use of digital signatures. Under the assumption
that the issuer keeps the secret signing key (sk_I) secure with them, it would
be computationally hard for any attacker to generate a coupon with valid
signature.

(Optional) Non-transferability of coupons

Similar to the paper based scheme, the coupon is personalized to the
granularity of zip_code and job_type. Therefore, the coupon is transferable
across individuals sharing a common zip_code and job_type.

Unforgeability and non-transferability of badges

Similar to the paper based scheme, the proposed scheme provides unforgeability
of the badges by the usage of digital signature where signing is performed by
the issuer. Hence, as long as the signing key (sk_I) is secretly kept by the
issuer the scheme should be unforgeable from a practical standpoint. The
badges are also non-transferable due to the hash of User_PII embedded inside
it. This User_PII is personally identifiable and hence no other user should
share the same PII and hence it should be non-transferable.

(Trade-off) Off-line phases

Similar to the paper based scheme, the proposed system is offline for the
coupon distribution phase and verification phase. However, both vaccination
phase require the pharmacy to be online and connected with internet in order
to communication with the issuer for the badge generation process.

User privacy from the issuer

Similar to the paper based scheme, this scheme provides protects the privacy
from its leakage to the issuer. Under the assumption of pre-image resistance
of the hashing function used when generating the badge, the issuer should not
be able to infer the User_PII by receiving its hash.

(Trade-off) User privacy from the verifiers

In contrast to the paper based scheme, the proposed scheme allows selective
disclosure to the verifier. This prevents the verifier from obtaining more
private information than what is needed.

(Trade-off) Non-traceability

Similar to the paper based scheme, this scheme is also traceable across
different verifiers. However, we talk about the extension in the next section
that enables non-traceable verification.

Accessibility

The system requires users to own a smartphone and download the app. This
reduces the accessibility across the population that does not have smartphone.

Usability

Similar to the paper based scheme, this system only requires the users to
obtain an app and coupon from a distributor and show it to the pharmacy. From
the perspective of the issuer, they are required to maintain a secure server
that has capabilities of maintaining a key infrastructure and serve the
requests of the pharmacy. The scheme requires a mechanism for the pharmacy to
be able to interact with the issuer for issuing the badge to a user.
Similarly, verifier requires a system that can use the issuer public key and
perform successful validation of the signatures. Barring the one-time software
installation part, the remaining system can work in automated fashion and
mostly requires scanning of QR-codes by the pharmacy and verifiers. In
contrast to the paper based scheme, carrying a smartphone is more convenient
than a paper based credential, making this scheme more usable.

###  3.3 Non-traceable verification

The proposed protocol has the limitation of being traceable across venues. We
propose to fix the issue by integrating anonymous credentials into the
verification protocol [4]. The anonymous credentials module can be implemented
efficiently using the recent efficient versions of anonymous credentials [2].
The user would use different attributes for obtaining their credentials.
During the verification phase, the verifier would request a random subset of
attributes from the user for which the user has to present a physical proof.
Post submission, the user would proove the signed message by performing the
verification phase of anonymous credentials [2].

##  4 Contact-less Group Verification

Figure 3: Depiction of the contactless group protocol where individuals
perform information exchange over a wireless channel securely and generate a
code on their smartphone app that proves their vaccination status to get
access.

The high-level idea of the contact-less group verification is that the user
carries a smartphone with them and the verifier shares a secret number on the
wireless channel such that only the users with correct vaccination status can
present this secret number on their screen and walk-in. Figure 3 depicts the
group verification protocol where individuals display the generated code to
the guard.
The contact-less group verification uses a secure channel for communication
between every user and the verifier to prevent against any spoofing based
threat that is possible in a wireless communication. The secure channel can be
established using the TLS protocol, for more details about the design and
implementation of the protocol, we refer the reader to the RFC [13]. To
establish the TLS connection, the verifier can share the certificate in three
possible ways -

  * •

Certificate signed by the issuer \- The issuer can provide digital certificate
for the public key of the venue and let user exchange keys with them.

  * •

Self signing certificate by scanning venue QR code - The user can scan QR code
available near the venue to obtain its digital certificate and trust it for
further establishing the secure channel.

  * •

Self signing certificate using key exchange - The venue can display a code
that can be entered by the user in their app to trust a given certificate
being broadcasted wirelessly. This code is tied to the public key used in the
a digital certificate produced by the verifier.

In the following we describe an interactive protocol that occurs wirelessly
using channels like Bluetooth, NFC and other commonly available sensors on
smartphones. The verifier system generates unique and unguessable $k$
repeatedly for small time windows. Every user performs one message exchange
with the verifier system and after this message exchange, everyone should have
a value $k$ on their device that they can show to obtain access. Here $k$ can
be a number, color, or an image the user will eventually show to the verifier
visually. The challenge $k$ can change continuously. For example, a guard at
the venue can change $k$ every minute.

  * •

The user first establishes a TLS connection with the verifier

  * •

The user then sends $\mathsf{status}$ to the verifier on the secure channel.

  * •

The verifier validates the message by performing
$\mathsf{verify}_{I}(\text{status})$ to the user.

  * •

The verifier responds with the challenge $k$ by sending
$c={\mathsf{Encrypt}(k,pk_{U})}$

  * •

The user decrypts the packet by $k=\mathsf{Decrypt}(c,\mathsf{sk}_{i})$.

  * •

The user then shows the value $k$ on the phone to the verifier.

##  5 Assessing Health Outcomes of Safety and Efficacy

The health outcome assessment requires monitoring and reporting from the user
standpoint as well as a vaccine provider standpoint. In the following section,
we describe how we merge the bottom-up and top-down approaches of health
outcome assessment being performed.

#### Upload:

Users can upload symptoms data at any point using their coupon code ($c$). The
issuer can validate the upload using the coupon number and associate it with a
verified vaccination by the pharmacy. User can also ask their doctor to submit
an adverse reaction report using the same $c$. The upload of symptoms can be
made privacy preserving by aggregating data using multi-party computation
based aggregation methods [8, 6] on top of which differentially private
mechanisms [10, 9] can be used to ensure privacy of individuals over the
aggregate statistics.

#### Download:

How can the user get an alert if their dosage batch is faulty? Or users with
specific health conditions maybe at risk? We want to achieve this without the
need for the user to reveal everything about themselves.

Figure 4: Health reporting and vaccination monitoring system would be used for
multiple scenarios including alerts, symptom check-in, vaccine recall and etc.
as shown in the figure.

Similar to GAEN [11] key server, the app can download the adverse events data
report that is public for their state, every morning. The app checks if their
own dose batch (company, batch or vaccination site) has any public alerts. The
app also checks if there is a specific alert for their health condition (e.g.
vaccine may have an adverse reaction to certain food allergy or immune health
conditions)

#### Aggregate view:

How can a vaccine maker, a US state or the CDC have a detailed or aggregate
view about the population level statistics? (i) With anonymity, a user can be
tracked using the provided coupon all through their journey. If we do not want
the user coupon to be tracked across the journey, the user can upload the
symptoms without the coupon code. (ii) If the user does not wish to upload
symptoms in the raw, we propose to use a protocol based on secure multi party
computation similar to Prio [6] to provide an aggregate statistic without
revealing the privacy of any individual. (iii) For users without an app, they
can log into V-SAFE [5] or VAERS [14] system using their coupon code.
Similarly, a doctor updating adverse reaction report can use the coupon code.

##  6 Limitations and Attacks

Trust ecosystem: It is important to highlight the role of the entire ecosystem
when the current public health emergency is over. Whether we could continue
using the same system once the vaccination drives are over at a global scale
would depend upon several factors like emerging variants, timescale of
immunity against the virus. While there might be a possibility of using some
of these systems for vaccination of other infectious diseases like flu, a
careful re-assessment of the privacy-utility trade-off would be required to
make sure that it is not happening under the pressure of public health
emergency. The key infrastructure proposed in this paper should be dismantled
in such a way that it can not be re-used for other identification process. The
database held by the issuer can be deleted once the information about
vaccination would not be required anymore, however, this might happen at a
different time period than key revocation since linked symptoms data with the
issuer’s vaccination database might be useful for retrospective studies.

Digital tools for pandemic response can have privacy and ethics issues at
various fronts [12], therefore we discuss some of the issues and potential
pitfalls for the proposed technology. The proposed protocol provides anonymity
but not privacy if the user has to interact with the system. The ability to
track the coupon $c_{i}$ for any user $i$ provides pseudoanonymity which is
not a full proof notion of privacy.

Because health services and verified access requires human interaction, we
expect systems will require users to furnish a state ID or similar equivalent.
Therefore, the name or some identifying information needs to be embedded as
part of the record code. While we store this personal information in a hashed
signature, the system does not protect against the notion of plausible
deniability. This can be solved by having the user information stored
exclusively with them while letting the user’s app to prove the correctness of
the information using zero knowledge proof.

In our proposed protocol, the pharmacy knows the information about the user,
and hence in the worst case, can collude with the issuer to reveal personal
information and identify a given user. However, this targeted attack makes the
assumption of pharmacy storing the user data instead of scanning and
processing it on an ephemeral storage.

##  7 Acknowledgements

We would like to thank Vitor Pamplona for discussions and feedback. We would
like to thank Priyanshi Katiyar for helping us with the sketches used in this
paper.

## References

  * [1] Apple.  Storing Keys in the Secure Enclave | Apple Developer Documentation, 2020.  https://developer.apple.com/documentation/security/certificate_key_and_trust_services/keys/storing_keys_in_the_secure_enclave.
  * [2] Foteini Baldimtsi and Anna Lysyanskaya.  Anonymous credentials light.  In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 1087–1098, 2013.
  * [3] Dan Boneh and Victor Shoup.  A graduate course in applied cryptography.  Draft 0.2, 2015.
  * [4] Jan Camenisch and Anna Lysyanskaya.  An efficient system for non-transferable anonymous credentials with optional anonymity revocation.  In International conference on the theory and applications of cryptographic techniques, pages 93–118. Springer, 2001.
  * [5] CDC.  Ensuring the safety of covid-19 vaccines in the united states.  Monitoring, Vaccine Safety, 2020.
  * [6] Henry Corrigan-Gibbs and Dan Boneh.  Prio: Private, robust, and scalable computation of aggregate statistics.  In Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation, NSDI’17, page 259–282, USA, 2017. USENIX Association.
  * [7] Elizabeth C. Crites and Anna Lysyanskaya.  Delegatable anonymous credentials from mercurial signatures.  Cryptology ePrint Archive, Report 2018/923, 2018.  https://eprint.iacr.org/2018/923.
  * [8] George Danezis, Cédric Fournet, Markulf Kohlweiss, and Santiago Zanella-Béguelin.  Smart meter aggregation via secret-sharing.  In Proceedings of the First ACM Workshop on Smart Energy Grid Security, SEGS ’13, page 75–80, New York, NY, USA, 2013. Association for Computing Machinery.
  * [9] Cynthia Dwork.  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer, 2008.
  * [10] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  Journal of Privacy and Confidentiality, 7(3):17–51, 2016.
  * [11] Google.  Apple and google: Exposure notifications: Using technology to help public health authorities fight covid-19, 2020.  https://www.google.com/covid19/exposurenotifications.
  * [12] Ramesh Raskar, Isabel Schunemann, Rachel Barbar, Kristen Vilcans, Jim Gray, Praneeth Vepakomma, Suraj Kapa, Andrea Nuzzo, Rajiv Gupta, Alex Berke, Dazza Greenwood, Christian Keegan, Shriank Kanaparti, Robson Beaudry, David Stansbury, Beatriz Botero Arcila, Rishank Kanaparti, Vitor Pamplona, Francesco M Benedetti, Alina Clough, Riddhiman Das, Kaushal Jain, Khahlil Louisy, Greg Nadeau, Vitor Pamplona, Steve Penrod, Yasaman Rajaee, Abhishek Singh, Greg Storm, and John Werner.  Apps gone rogue: Maintaining personal privacy in an epidemic, 2020.
  * [13] Eric Rescorla.  The Transport Layer Security (TLS) Protocol Version 1.3.  RFC 8446, August 2018.
  * [14] Weigong Zhou and Susan S Ellenberg.  Surveillance for safety after immunization: Vaccine adverse event reporting system (vaers)—.  Morbidity and Mortality Weekly Report: MMWR. Surveillance Summaries. Surveillance summaries, 2003.


# Inverse Cubic Iteration

Robert M. Corless

###### Abstract

There are thousands of papers on rootfinding for nonlinear scalar equations.
Here is one more, to talk about an apparently new method, which I call
“Inverse Cubic Iteration” (ICI) in analogy to the Inverse Quadratic Iteration
in Richard Brent’s zeroin method. The possibly new method is based on a cubic
blend of tangent-line approximations for the inverse function. We rewrite this
iteration for numerical stability as an average of two Newton steps and a
secant step: only one new function evaluation and derivative evaluation is
needed for each step. The total cost of the method is therefore only trivially
more than Newton’s method, and we will see that it has order
$1+\sqrt{3}=2.732...$, thus ensuring that to achieve a given accuracy it
usually takes fewer steps than Newton’s method while using essentially the
same effort per step.

##  1 Introduction

Recently I wrote, with Erik Postma, a paper on blends of Taylor series [3]. A
“blend” is just a two-point Hermite interpolant: if we have series for $f(x)$
at $x=a$ and another series for the same function $f(x)$ at $x=b$ then we can
blend the series to get a (usually) better approximation to $f(x)$ across the
interval. The paper discusses how to compute high-order blends stably and
efficiently in Maple, and looks at some applications of them.

In contrast, this paper looks at a low-order blend, and a particular
application, namely rootfinding. In fact all we will need is a cubic. If we
just use series up to and including terms of order $1$ at each point, namely
$f(a)$ and $f^{\prime}(a)$ and $f(b)$ and $f^{\prime}(b)$ then these four
pieces of information determine, as is well known, a cubic Hermite
interpolant.

What is less well-known (but still perfectly well-known, to be honest) is that
from these same pieces of information one can usually construct a cubic
interpolant of the inverse function inv$f(y)$, also written $\breve{f}(y)$.
The data for that information is that the points of expansion are $y=f(a)$ and
$y=f(b)$, and the function values are $a$ and $b$, and the derivative values
are $1/f^{\prime}(a)$ and $1/f^{\prime}(b)$: four pieces of information which
together suffice to determine a cubic polynomial in $y$ that fits the data.

Of course we cannot have $f^{\prime}(a)=0$ or $f^{\prime}(b)=0$, and indeed
$f^{\prime}(x)=0$ anywhere near the interval is bad news for a rootfinder: the
root will be ill-conditioned, if it’s determined at all. If $f^{\prime}(x)=0$
anywhere in the interval then the function is not guaranteed to be monotonic,
and so the inverse function will not be defined in the whole neighbourhood.
Throwing caution to the winds, we’re not going to worry about this at all.

##  2 Derivation of the Formula

Nearly any numerical analysis textbook will have an expression equivalent to
the following for a cubic Hermite interpolant, fitting four pieces of
information to get a cubic polynomial that fits those pieces of information:

$\displaystyle y=$
$\displaystyle\left(1+2\,\theta\right)\left(\theta-1\right)^{2}f(a)+\theta\,\left(\theta-1\right)^{2}{hf^{\prime}(a)}$
$\displaystyle+{\theta}^{2}\left(3-2\,\theta\right)f(b)+{\theta}^{2}\left(\theta-1\right){hf^{\prime}(b)}$
(1)

where $\theta=(x-a)/(b-a)$ and $h=b-a$. When $\theta=0$, $x=a$; when
$\theta=1$, $x=b$. Since the derivative $d/d\theta=dx/d\theta\cdot d/dx=hd/dx$
we see that it all works out: $y=f(a)$ when $\theta=0$,
$dy/d\theta=hf^{\prime}(a)$ and $y=f(b)$ when $\theta=1$ and
$dy/d\theta=hf^{\prime}(b)$ when $\theta=1$.

Now we do the inverse. Put $s=(y-f(a))/(f(b)-f(a))$ and $\Delta=f(b)-f(a)$. We
see right away that we are in trouble if $f(a)=f(b)$; but then, by Rolle’s
theorem there would be a place $c$ between $a$ and $b$ where $f^{\prime}(c)=0$
if that were the case, and we have already said that we are going to ignore
that difficulty. Indeed, both Inverse Quadratic Iteration (IQI) and the secant
method also fail in that case, so at least we are in good company.

We want

$\displaystyle x=$
$\displaystyle\left(\left(1+2\,s\right)a+{\frac{s\Delta}{f^{\prime}\left(a\right)}}\right)\left(1-s\right)^{2}$
$\displaystyle+\left(\left(3-2\,s\right)b-{\frac{\left(1-s\right)\Delta}{f^{\prime}\left(b\right)}}\right){s}^{2}\>.$
(2)

By similar reasoning to before, we see that at $s=0$ then $x=a$ and
$dx/dy=1/f^{\prime}(a)$, while at $s=1$ then $x=b$ and
$dx/dy=1/f^{\prime}(b)$.

Why do this? The wonderfully simple trick of Inverse Quadratic Iteration,
namely that to find an approximate value of $x$ that makes $y=0$ one simply
substitutes $y=0$ into the Inverse formula, also works here. Putting $y=0$
means $s=(0-f(a))/(f(b)-f(a))$ (a number between $0$ and $1$) and that gets us
our definite value of $x$. Doing this blindly, we get

$\displaystyle\left(\left(1-2\,{\frac{f\left(a\right)}{\Delta}}\right)a-{\frac{f\left(a\right)}{f^{\prime}\left(a\right)}}\right)\left(1+{\frac{f\left(a\right)}{\Delta}}\right)^{2}$
$\displaystyle\qquad+{\frac{\left(f\left(a\right)\right)^{2}}{{\Delta}^{2}}\left(\left(3+2\,{\frac{f\left(a\right)}{\Delta}}\right)b-{\frac{\Delta}{f^{\prime}\left(b\right)}\left(1+{\frac{f\left(a\right)}{\Delta}}\right)}\right)}$
(3)

This is correct, but I suspect numerically useless. To be honest, I didn’t
even try it. Instead, I looked for a way to rewrite it to improve its
numerical stability.

##  3 A numerically more stable expression

After a surprisingly small amount of algebraic manipulation (perhaps a
generous share of luck was involved) I arrived at the following:

$\displaystyle x_{n+1}=$
$\displaystyle{\frac{{y_{{n}}}^{2}}{\left(y_{{n-1}}-y_{{n}}\right)^{2}}\left(x_{{n-1}}-{\frac{y_{{n-1}}}{f^{\prime}\left(x_{{n-1}}\right)}}\right)}+{\frac{{y_{{n-1}}}^{2}}{\left(y_{{n-1}}-y_{{n}}\right)^{2}}\left(x_{{n}}-{\frac{y_{{n}}}{f^{\prime}\left(x_{{n}}\right)}}\right)}$
$\displaystyle-2\,{\frac{y_{{n-1}}y_{{n}}}{\left(y_{{n-1}}-y_{{n}}\right)^{2}}\left(x_{{n}}-{\frac{y_{{n}}\left(x_{{n}}-x_{{n-1}}\right)}{y_{{n}}-y_{{n-1}}}}\right)}\>.$
(4)

Call this iteration Inverse Cubic Iteration, or ICI. Instead of presenting a
tedious transformation of the previous formula into the one above (it is
equivalent, trust me, although I did make the sleight-of-hand transformation
from $a$ and $b$ to $x_{n-1}$ and $x_{n}$, implying iteration), I will verify
that it has the appropriate behaviour in the next section; we will look there
at how quickly it converges to a root (when it converges at all). The
interesting part of this, to me, is that we can recognize all three terms in
equation (4). There is a Newton iteration starting at $x_{n-1}$, another at
$x_{n}$, and a secant iteration using both points. Then all three are averaged
together111It might be numerically better still to average the previous points
$a_{0}x_{n}+a_{1}x_{n-1}+a_{s}x_{n}$, and average the small updates
$a_{0}y_{n}/f^{\prime}(x_{n})+a_{1}y_{n-1}/f^{\prime}(x_{n-1})+a_{s}(y_{n}\Delta
x/\Delta y)$, and then use this average update to improve the average of the
previous points. Currently this is the way my implementation does it, but it
may not make much difference.: the weights are $y_{n}^{2}$, $y_{n-1}^{2}$, and
$-2y_{n}y_{n-1}$ all divided by $(y_{n}-y_{n-1})^{2}$ so that the weights all
add up to $1$, as they should. The most accurate estimate is given the most
weight, by using the residuals $y_{k}$ on the other estimates. I think this is
a rather pretty formula.

The numerical stability (or lack thereof) of the secant method and of Newton’s
method is well-understood; by writing the secant method as above we make a
“small change” to an existing value, and similarly Newton’s method is written
in as stable a way as it can be. Thus we have what is likely to be a
reasonably stable iteration formula.

Because this method uses two points $x_{n-1}$ and $x_{n}$ to generate a third
point $x_{n+1}$, it seems similar to the secant method. Because it uses
derivatives $f^{\prime}(x_{k})$ at each point, it seems similar to Newton’s
method. It is not very similar to IQI, which fits an inverse quadratic to
three points and uses that to generate a fourth. Halley’s method and other
Schröder iterations use higher derivatives and will be more expensive per
step. [It might be interesting to try to average higher-order methods in a
similar manner to speed up convergence even more; so far I have not been able
to succeed in doing so. The simple trick of replacing $f$ by
$f/\sqrt{f^{\prime}}$ which transforms Newton’s method to Halley’s method (and
speeds up secant) does not seem to work, with these weights.]

I am going to assume that we start with a single initial guess $x_{0}$ and
then generate $x_{1}$ by a single step of Newton’s method. Then it is obvious
that to carry out one step with equation (4) we need only one more function
evaluation $y_{1}=f(x_{1})$ and one more derivative evaluation
$f^{\prime}(x_{1})$, because we can record the previous $y_{0}=f(x_{0})$ and
$f^{\prime}(x_{0})$ instead of recomputing them. In the standard model of
rootfinding iteration where the dominant cost is function evaluation and
derivative evaluation, we see that this method is no more expensive than
Newton’s method itself. But instead of computing
$X_{n+1}=x_{n}-f(x_{n})/f^{\prime}(x_{n})$ and forgetting all about $x_{n-1}$,
once we have formed this Newton iteration we average it with the previous
Newton iteration together with a secant iteration: the cost of forming this
average is no more than a few floating-point operations, which we may consider
to be trivial compared to the assumed treasury-breaking expense of evaluating
$f(x)$ and $f^{\prime}(x)$. When we try this on Newton’s classical example
$z^{3}-2z-5$ with an initial guess of $z_{0}=1$ we get $29$ Digits of accuracy
after $7$ iterations ($10$ Digits of accuracy after $6$ iterations).

I will sketch the cost of this method using the normal conventions in section
5.

##  4 The order of the method

If we assume that $r$ is the root we are searching for, $f(r)=0$, and that
$x_{n-1}=r+\varepsilon_{n-1}$ and $x_{n}=r+\varepsilon_{n}$ then a
straightforward and brutal series computation in Maple shows that

$x_{n+1}=r+(\varepsilon_{n-1}\varepsilon_{n})^{2}\frac{f^{(iv)}(r)f^{\prime\prime}(r)-10f^{\prime}(r)f^{\prime\prime}(r)f^{\prime\prime\prime}(r)+15(f^{\prime\prime}(r))^{3}}{4!(f^{\prime}(r))^{3}}+\cdots\>.$
(5)

The error in the residual, which is what we will actually measure, is ever so
slightly different:
$y(x_{k})=f(r+\varepsilon_{k})=f(r)+f^{\prime}(r)\varepsilon_{k}$ and so we
can remove one $f^{\prime}(r)$ factor from the denominator term above. Notice
that each $x_{k}$ exactly solves $F(x)=f(x)-y_{k}$; this is a trivial
observation, but often useful: by iterating, we get the exact solutions to
slightly different equations. Here, though, it doesn’t matter. Both formulae
show the trend of the errors. That is, the error in the next iterate is the
square of the product of the two previous errors. This is satisfyingly
analogous to that of the secant method (product of the two previous errors)
and Newton’s method (square of the previous error). Solving the recurrence
relation $\ln\varepsilon_{n+1}=2(\ln\varepsilon_{n}+\ln\varepsilon_{n-1})$
shows that the error is asymptotically the $1+\sqrt{3}=2.732\ldots$th power of
the previous one; not quite cubic convergence, but substantially faster than
quadratic convergence.

Let’s take the method out for a spin to see if practice matches theory.
Consider the function $f(x)=(x^{2}+1)\exp(-x)-1/3$. This has two places where
$f^{\prime}(x)=0$, namely $x=(1\pm\sqrt{5})/2$. Provided we stay away from
there, we should be fine. Taking our initial guess to be $x_{0}=2.0$, we then
compute $x_{1}$ by Newton’s method as usual. Now we have two iterates to work
with; we then compute $x_{2}$, $x_{3}$, $\ldots$, $x_{8}$. Because convergence
is so rapid, and I wanted to demonstrate it, I worked with Digits set to be
$1000$. This was overkill, but it allows the plot in figure 1 to show clearly
that the error in $x_{8}$ is about $10^{-594}$. Newton’s method (red squares)
achieves only $10^{-63}$ with the same effort. The ratios
$y_{k}/(y_{k-1}y_{k-2})^{2}$ for $k=2$, $3$, $\ldots$, $8$ were, respectively,
$1.5952$, $17.048$, $4.5955$, $4.9061$, $4.9080$, $4.9081$, and $4.9080$.
These fit the curve $y_{k}=(0.6437)^{(1+\sqrt{3})^{k}}$, demonstrating the
near-cubic order of the method. The constant $0.6437$ was found by fitting to
the final data point. This trend predicts that the accuracy in $x_{9}$ would
be $4.9081(y_{8}y_{7})^{2}=1.7383\cdot 10^{-1622}$. Re-doing the computation
in $1624$ Digits and extending to $x_{9}$, we get $y_{9}=1.7383\cdot
10^{-1622}$, just as predicted.

Figure 1: Convergence to a root of $f(x)=(x^{2}+x)\exp(-x)-1/3$. The initial
guess was $x_{0}=2.0$. The next iterate was computed by Newton’s method,
$x_{1}=x_{0}-f(x_{0})/f^{\prime}(x_{0})$. Thereafter equation (4) was used.
Computing was carried out in $1000$ Digits. What is plotted is the logarithm
(base $10$) of the residual error, equivalently
$\log_{10}|y_{n}|=\log_{10}|f(x_{n})|$. The dashed blue line represents the
theoretical curve $y_{n}=(0.6437)^{(1+\sqrt{3})^{n}}$ demonstrating the
theoretical computation of the order of the method above. The constant
$0.6437$ was found by fitting the final data point. Newton’s method (red
squares) achieves only $63$ Digits of accuracy instead of ICI’s nearly $600$.

##  5 The cost of the method

The best analysis—that I know—of the cost of Newton’s method for solving a
scalar equation by iterating with constant precision is contained in [9].
There, the author weighs the cost of function evaluations and estimates that
the cost of derivative evaluations are usually a modest factor larger than
that of function evaluations; then, balancing the greater cost of Newton’s
method per step against its general need for fewer iterations, he concludes
that usually the secant method should win. Yes, the secant method usually
takes more iterations; but each one usually costs only a fraction of a Newton
step. It is only when the derivatives are unusually inexpensive that Newton’s
method wins. For the example in figure 1 this is the case: the dominant cost
of the function evaluation is the exponential, and that can be re-used in the
derivative. So, for this particular problem, ICI should win over Newton’s
method and even more decisively over the secant method. But to win over
Newton’s method, ICI needs to take fewer iterations, because the cost per step
is essentially identical to Newton’s method. ICI will never222“What, never?”
“No, never!” “What, never?” “Hardly ever!” —the crew and Captain of HMS
Pinafore take more iterations than Newton’s method. But will it take fewer?

That is actually the issue. Will we save any iterations at all? Newton’s
method typically converges very rapidly, given a good initial guess. To give a
very rough sketch, if the initial error is $2^{-2}$ and all the constants are
$1$, we can expect a double precision answer in five iterations (actually the
error then would be wasted: $2^{-64}$, and rounding errors would have made it
at best $2^{-52}$). ICI would have the sequence of errors
$\varepsilon_{0}=2^{-2}$, $\varepsilon_{1}=2^{-4}$ (same as Newton for the
$x_{1}$ iterate, of course), $\varepsilon_{2}=2^{-12}$ squaring the product
$2^{-2}\cdot 2^{-4}$, then $\varepsilon_{3}=2^{-2(12+4)}=2^{-32}$ which is the
same error that Newton achieved in four iterations. One more gets us
$\varepsilon_{4}=2^{-2(32+12)}=2^{-88}$ which is a vast overkill; still, we
have beaten Newton by one iteration with this initial error.

If instead the initial guess is only accurate to $2^{-1}$, not $2^{-2}$, then
Newton takes six iterations while ICI also takes six:
$\varepsilon_{0}=2^{-1}$, $\varepsilon_{1}=2^{-2}$, $\varepsilon_{3}=2^{-6}$,
$\varepsilon_{4}=2^{-16}$, $\varepsilon_{5}=2^{-44}$.

If instead the initial guess is accurate to $2^{-3}$ then Newton takes five
iterations, while ICI takes $\varepsilon_{1}=2^{-6}$,
$\varepsilon_{2}=2^{-18}$, $\varepsilon_{3}=2^{-48}$ and at four iterations
beats Newton.

The lesson seems clear: if one wants ultra-high precision, the ICI method will
give the same results in fewer iterations of essentially the same cost. If one
only wants a double precision result, then the number of iterations you save
may not be much, if any (and if it doesn’t really beat Newton, then it won’t
often beat the secant method). And both methods demand good initial guesses.

##  6 Initial guesses

I have been using the scheme “choose only one initial guess and let Newton’s
method determine the next iterate” above. Obviously there are alternative
strategies. I like this one because it’s usually hard enough to come up with
one initial guess to a root, let alone two.

Using this strategy also allows one to plot basins of attraction: which
initial guesses converge to which root? I took the function $f(z)=z^{3}-1$ and
sampled a $1600$ by $1600$ grid on $-2\leq x\leq 2$, $-2\leq y\leq 2$ where
$z=x+iy$ and took at most $13$ iterations of ICI starting from each gridpoint;
if the iteration converged (to $10^{-8}$) earlier, that earlier result was
recorded. Plotting the argument (phase) of the answer gives an apparent
fractal diagram, very similar to that for Newton’s method, but different in
detail. In particular, the basins of attraction are visibly disconnected. See
figures 2 and 3.

Figure 2: Approximate basins of attraction for the ICI method for
$f(z)=z^{3}-1$. Each initial guess $z_{0}=x+iy$ is coloured with the phase of
the result after $13$ iterations of ICI, namely arg$(z_{13})$ (earlier
iterations may have converged, in which case the limit is recorded). The first
iterate $z_{1}$ is obtained by Newton’s method. Computation done on a $1600$
by $1600$ grid on $-2\leq x\leq 2$, $-2\leq y\leq 2$. Notice that the fractal
structure is more complicated than that for simple Newton’s method, suggesting
that the choice of initial guess is more fraught for this method.  Figure 3:
Zooming in, we show the region $-1.45\leq x\leq-1.05$ and $-0.2\leq y\leq 0.2$
again with a $1600$ by $1600$ grid for the same function and iterations as in
figure 2. We see disconnected components.

##  7 Multiple roots and infinite derivatives

Of course this method won’t help with multiple roots. We’re dividing by
derivatives, which go to zero if we approach a multiple root. It’s true that
the method can work, but if it does it will work more slowly; even so, the
sequence $y_{k}/(y_{k-1}y_{k-2})^{2}$ will just grow without bound. I tried
this, on $f(x)=(x-2)^{2}$, with $x_{0}=0.5$, and this expectation is correct.
The method did converge in ten iterations to the double root $x=2$, with an
error of about $10^{-14}$, but note that Newton’s method also converges
linearly for this problem.

Another place for failure of rootfinding is when any derivative is
infinite—that is, at or near derivative singularities. The presence of up to
the fourth derivative in the error formula (5) suggests that this method will
be more sensitive to singularities than Newton’s method is.

##  8 Where to, next

The first question to ask is, can this work for nonlinear systems of
equations? Even though this method, stripped of its origins, is just a
weighted average of two Newton iterations and a secant iteration, all of which
can be used for systems, I find that I am dubious. It’s not clear to me what
to use for the scalar weights: replace e.g. $y_{k}^{2}/(y_{k}-y_{k-1})^{2}$ by
$\|y_{k}\|^{2}/\|y_{k}-y_{k-1}\|^{2}$ using some norm? Which norm? Perhaps it
will work, with the right choice. But even if it did, for large systems the
largest computational effort is usually spent in setting up and solving the
linear systems: full Newton iteration is rarely used, when cheaper approximate
iterations will get you there faster. Moreover, the real benefit of the higher
speed of convergence of ICI isn’t fully felt at double precision or lower—I
think it will only matter for quad precision (double-double!) or better.

I believe that the best that can be hoped for from this method is to be used
in a computer algebra system for its high-precision scalar solvers, which
currently might use other high-order iterations. It is here, if anywhere,
where this method will be useful.

There may be similar two-step iterations of higher order, perhaps starting
with “inverse quintic iteration” which uses terms up to the second derivative
and would have order $(3+\sqrt{21})/2\approx 3.79$. I have not yet
investigated any such schemes.

In ultra high-precision applications there is sometimes the option to change
precision as you go. This is effective for Newton iteration; only the final
function evaluation and derivative evaluation need to be done at the highest
precision. I have not investigated the effects of variable precision on the
efficiency of this method.

Then there are more practical matters: what to do in the inevitable case when
$y_{k}=y_{k-1}$? [This happens when the iteration converges, for instance!] Or
when $f^{\prime}(x_{k})$ is too small? It turns out that the details of the
extremely practical zeroin method [1] which combines IQI with bisection and
the secant method for increased reliability (this method is implemented in
fzero command in Matlab) matter quite a bit. More improvements on the method
can be found in [11], which make the worst-case behaviour better. Attention
needs to be paid to these details.

Then there is another academic matter: in all those tens of thousands of
papers on rootfinding, has nobody thought of this before? Really? Again, I
find that I am dubious, although as a two-step method it is technically not
one of Schröder’s iterations (which keep getting reinvented). And it’s not one
of Kalantari’s methods either [5]. But it’s such a pretty method—surely
someone would have noticed it before, and tried to write about it? Perhaps
it’s an exercise in one of the grand old numerical analysis texts, like
Rutishauser’s (which I don’t have a copy of).

There are (literally) an infinite number of iterative methods to choose from;
see the references in [7] for a pointer to the literature, including to [10]
and from there to G. W. Stewart’s translation of Schröder’s work from the
$19$th century, entitled “On infinitely many algorithms for solving
equations”. The bibliography [8] has tens of thousands of entries.

However, searching the web for “Inverse Cubic Iteration” (surely a natural
name) fails. We do find papers when searching for names like “Accelerated
Newton’s method”, such as [4]; but the ones I have found are each different to
ICI (for instance the last-cited paper finds a true third-order method; ICI is
not quite third-order but only $1+\sqrt{3}$). The method of [6], termed “Leap-
Frog Newton”, is quite similar to ICI and consists of an intermediate Newton
value followed by a secant step: this costs two function evaluations and a
derivative evaluation per step (so is more expensive per step than is ICI
which requires only one function evaluation and derivative evaluation per step
after the first one) but is genuinely third order. I found this last paper by
searching for “combining Newton and secant iterations,” so perhaps I could
find papers describing closer matches to ICI, if only I could think of the
correct search term. I am currently asking my friends and acquaintances if
they know of any. Do you?

“Six months in the laboratory can save you three days in the library.”

—folklore as told to me by Henning Rasmussen

## References

  * [1] R. P. Brent.  An algorithm with guaranteed convergence for finding a zero of a function.  The Computer Journal, 14(4):422–425, 01 1971.
  * [2] Robert M Corless and Nicolas Fillion.  A graduate introduction to numerical methods, volume 10.  Springer, 2013.
  * [3] Robert M. Corless and Erik Postma.  Blends in Maple.  arXiv 2007.05041, 2020.
  * [4] J. M. Gutiérrez and M. A. Hernández.  An acceleration of Newton’s method: Super-Halley method.  Appl. Math. Comput., 117(2–3):223–239, January 2001.
  * [5] Bahman Kalantari.  Polynomial root-finding and polynomiography.  World Scientific, 2008.
  * [6] A Bathi Kasturiarachi.  Leap-frogging Newton’s method.  International Journal of Mathematical Education in Science and Technology, 33(4):521–527, 2002.
  * [7] Ao Li and Robert M Corless.  Revisiting Gilbert Strang’s “a chaotic search for $i$”.  ACM Communications in Computer Algebra, 53(1):1–22, 2019.
  * [8] J.M. McNamee.  Numerical methods for roots of polynomials.  Elsevier Science Limited, 2007.
  * [9] A. Neumaier.  Introduction to numerical analysis.  Cambridge University Press, 2001.
  * [10] MS Petković, LD Petković, and D. Herceg.  On Schröder’s families of root-finding methods.  Journal of computational and applied mathematics, 233(8):1755–1762, 2010.
  * [11] Gautam Wilkins and Ming Gu.  A modified Brent’s method for finding zeros of functions.  Numerische Mathematik, 123(1):177–188, 2013.

Figure 4: Bonus figure: basins of attraction under ICI for Kepler’s equation
$z-0.083\sin(z)-1=0$ on a $1600$ by $1600$ grid $-30.5\leq x\leq-29.5$,
$-17.5\leq y\leq-16.5$, with tolerance $10^{-8}$ and a maximum of $30$
iterations. The pure white areas represent areas where the iteration
encountered a NaN; other colours represent different phases after $30$
iterations or convergence, whichever happened first. The picture is quite a
bit more complicated than the similar picture for Newton’s method in Figure
3.21 in [2].