# Gender-Inclusive Grammatical Error Correction through Augmentation

Gunnar Lund, Kostiantyn Omelianchuk, Igor Samokhin
Grammarly
<EMAIL_ADDRESS>
###### Abstract

In this paper we show that GEC systems display gender bias related to the use
of masculine and feminine terms and the gender-neutral singular they. We
develop parallel datasets of texts with masculine and feminine terms, and
singular they, and use them to quantify gender bias in three competitive GEC
systems. We contribute a novel data augmentation technique for singular they
leveraging linguistic insights about its distribution relative to plural they.
We demonstrate that both this data augmentation technique and a refinement of
a similar augmentation technique for masculine and feminine terms can generate
training data that reduces bias in GEC systems, especially with respect to
singular they while maintaining the same level of quality.

##  1 Introduction

Natural Language Processing (NLP) systems are well known to exhibit
sensitivity to social characteristics, a sensitivity that may lead to harms
for users interacting with these systems. In this work, we examine how NLP
systems performing the task of Grammatical Error Correction (GEC) are
sensitive to gender characteristics in English and how this sensitivity
represents bias that harms users of these systems. We propose a new data
augmentation technique to address bias related to singular they, and show how
it can mitigate gender bias. We also show how this technique interacts with
prior work on data augmentation methods to reduce bias.

The expression of gender in English is complex, and to focus our study, we
identify discrete biases that GEC systems may exhibit. First, we build on
other works on gender bias in NLP by examining how masculine and feminine
terms impact the behavior of GEC systems. Discrepant behavior between
sentences that contain one or the other is evidence of bias. Second, we
examine the behavior of GEC systems with a gender-neutral pronominal paradigm
in English commonly called singular they. The linguistic properties of this
paradigm introduce additional kinds of biases relative to masculine or
feminine pronouns. Additionally, we make our evaluation datasets publicly
available111https://github.com/grammarly/gender-inclusive-gec.

To prevent these adverse behaviors, we apply techniques to generate synthetic
training data that address different aspects of these behaviors. First, we
adopt Counterfactual Data Augmentation (CDA), which is used successfully to
reduce bias in word embedding models (Lu et al., 2019; Maudslay et al., 2020),
and apply it to the GEC case. Second, we introduce a new technique for
generating training data with they pronouns that have unambiguously singular
reference using insight from theoretical linguistics to target model bias with
gender-neutral sentences. Because these techniques are data-oriented, the
innovations should theoretically generalize beyond the GEC domain to other NLP
tasks as well.

Our main contributions are:

  * •

We introduce a novel technique for creating singular they data, leveraging
specific linguistic features of this use of the pronoun. Additionally, we
refine previous approaches to addressing discrepancies in model behavior
between texts with masculine and feminine pronouns and show their application
outside of the context of masked language models.

  * •

We qualitatively and quantitatively measure biases in competitive GEC systems
by comparing model performance on parallel test sets containing singular they
pronouns, masculine terms, and feminine terms.

  * •

We show how our data augmentation techniques, both in isolation and
combination, mitigate these biases when used to create training data for these
GEC systems with a minimal impact to overall performance.

##  2 Background

###  2.1 Gender and Bias in NLP and GEC

####  2.1.1 Conceptual grounding

To orient this work, we highlight two recent calls-to-action regarding the
study of bias and gender in NLP systems. First, following Devinney et al.
(2022), we mean to be explicit about the conception of gender and gendered
language we assume. In particular, we are concerned with gendered linguistic
content, and not the gender of the authors or readers of that content. We
recognize that the expression of gender in English is notional; the use of
some nouns and pronouns is linked to particular gendered conceptual categories
(McConnell-Ginet, 2013; Ackerman, 2019). Additionally, the use of language
with gendered content represents one aspect of gender performativity which
produces and reifies these gendered categories.

Second, following Blodgett et al. (2020), “bias” is an inherently normative
concept. In the context of NLP systems, it must be understood in terms of the
potential harms that those systems may cause and to whom those harms may be
caused. Therefore, we directly focus on mitigating harms themselves as they
relate to the GEC task and how users of these systems interact with them and
may be affected by them. Unlike some studies of bias in upstream contexts like
word embeddings, users interact with GEC systems directly; these users choose
to incorporate these systems’ suggestions into their emails, essays, and
tweets, and bias may impact anyone interacting with such text.

Further, because the GEC task is an inherently normative one on its own—these
systems offer suggestions to correct a user’s text and are designed in
accordance with preexisting normative notions of “correct” or “fluent”
English—GEC systems necessarily also participate in the production of gendered
categories. The norms assumed when constructing these systems and datasets in
this regard may conflict with other norms about language use. For example,
there are norms against the use of singular they in some language communities.
Some English speakers do not accept singular they as a grammatical
construction of English (Bjorkman, 2017, a.o.), and some prescriptive grammars
advise against the use of singular they (c.f., Strunk and White, 1999). People
who are non-binary and use they pronouns, e.g., cannot refer to themselves
"correctly" within these circumscribed norms of language use. As we discuss
below, the operationalization of these norms in GEC systems may lead to harm.
We adopt the view that GEC systems should reflect the most permissive
distribution of singular they. This distribution is discussed further in
section 3.2.

Our work has a notable limitation in that we do not investigate bias with
respect to neopronouns like ze or xe. We leave extensions of CDA-like
techniques to these pronouns for future work.

####  2.1.2 Two biases

We identify two areas where GEC systems can produce biased, and therefore
potentially harmful, outcomes. Importantly, this is not an exhaustive account
of potential biases GEC systems exhibit, but we think this is as good a
starting point as any.

First, a GEC system can be implicitly biased if it consistently performs
better on texts containing words of one gendered category over another. This
is an allocative harm. If a GEC system performs worse on texts that are about
people who use one pronoun or another, texts about those people may contain
more grammatical errors, impacting their relative opportunity. For example, a
user writing letters of recommendation may inadvertently include more
grammatical errors in letters for individuals using masculine pronouns, as a
system could perform worse on texts with masculine pronouns than feminine
pronouns, and this could impact the relative reception those letters receive
compared to similar letters with feminine pronouns.

Second, a GEC system can be explicitly biased if it offers corrections that
reify harmful notions about particular gendered categories, including the
reinforcement of stereotypes and misgendering or erasure of individuals
referred to in the user’s text. This is a representational harm. This harm is
explicitly called out by participants in a survey on harms of AI systems with
respect to non-binary individuals (Dev et al., 2021). The examples below are
representative of these kinds of corrections. The first is an instance of
misgendering, replacing singular they with a masculine pronoun; the second is
an instance of erasure, implying that they has a correct use only as a plural
pronoun.

  1. 1.

I asked Alex their phone number. -> I asked Alex his phone number.

  2. 2.

They are a linguist. -> They are linguists.

We find evidence for both of these biases by analyzing the following GEC
systems (table 1)

  1. 1.

GECToR Omelianchuk et al. (2020), sequence tagging approach, which was a
state-of-the-art GEC model in 2020

  2. 2.

Fine-tuned BART model Lewis et al. (2020), which represents another popular
and competitive approach - sequence to sequence

  3. 3.

EditScorer Sorokin (2022), the recent ranker approach, that is the second-best
result on BEA Shared Task 2019, as of April
2023222http://nlpprogress.com/english/grammatical_error_correction.html.

Our quantitative analysis revealed that, for all three systems, there is a
significant gap (from -6.2% to -9.5% F05 points) between the original and
augmented with singular they examples versions of the BEA-dev subset, which we
call bea-195. The details on how we built these datasets and evaluation
approach is provided in sections 4.1 and 4.2. Detailed evaluation results are
available in appendix table 7.

System | bea-dev-full | bea-195 | bea-556
---|---|---|---
| F05 | F05 orig | F05 st aug | diff | F05 orig | F05 mf aug | diff
GECToR (roberta-base) | 54.57% | 58.28% | 48.74% | -9.54% | 59.23% | 58.96% | -0.27%
BART (seq2seq) | 52.74% | 56.36% | 50.13% | -6.23% | 58.61% | 58.79% | 0.18%
EditScorer (roberta-large) | 58.92% | 60.6% | 54.16% | -6.44% | 62.55% | 61.59% | -0.96%

Table 1:  Scores on BEA-dev subsets for strong GEC baselines.

We hypothesize that these biases share a partial cause: an imbalance in the
training data. If, e.g., the training data with masculine words is of a higher
quality than that with feminine words, there may be a performance gap. In the
case of unnecessary corrections of singular they, we hypothesize that the
imbalance is caused by an extreme lack of singular they sentences relative to
plural they sentences. In the remainder of this paper, we show that the
introduction of synthetic data helps mitigate these biases.

###  2.2 Related work

####  2.2.1 Data augmentation

Data augmentation has been used in other NLP domains to mitigate gender bias,
but most of these works focus on just the masculine and feminine gender
categories in English and limit the application of these techniques to word
embedding models. Zhao et al. (2018); Rudinger et al. (2018); Lu et al. (2019)
show that coreference resolution systems are sensitive to masculine and
feminine words in otherwise equivalent sentences. Lu et al. (2019) use what
they call Counterfactual Data Augmentation (CDA) to reduce this sensitivity.
In CDA, masculine pronouns are swapped for feminine ones and vice versa. They
also swap definitionally gendered common nouns like actor and actress. They
set aside data where the swapping candidates are in a cluster with a proper
name.

Maudslay et al. (2020) extend Lu et al. (2019) CDA and implement additional
name swapping, where the gendered associations of names were determined using
census data from the US Social Security Administration. They use this
technique to minimize gendered differences in word embedding spaces as
measured by WED (Bolukbasi et al., 2016). As in Lu et al., Maudslay et al.
limit their method to masculine and feminine categories.

In addition, gender-neutral data augmentation methods have been proposed in
concurrent works by Sun et al. (2021) and Vanmassenhove et al. (2021). These
methods have different goals than ours and are designed to produce different
kinds of data. We discuss the differences between these methods and our own in
section 3.3.

To our knowledge, ours is the first work to use CDA techniques to reduce bias
in GEC systems and the first to use singular they augmentation to inject
synthetic training data to reduce bias with singular they sentences.

####  2.2.2 Singular they and NLP systems

Previous works investigating bias towards singular they sentences have
generally focused on coreference resolution systems. Cao and Daumé III (2021)
develop a dataset to evaluate these systems on naturalistic texts about
individuals who identify as non-binary, where 35% of the pronouns are singular
they. They report that the Stanford system is the highest scoring on this
dataset with an F1 score of 34.3%. This same system reports a much higher F1
score of 60% on the CONLL 2012 test set.

Baumler and Rudinger (2022) compare coreference resolution system performance
directly on singular they sentences compared to plural they sentences along
the lines of the Winograd or Winogender schemata (Levesque et al., 2012;
Rudinger et al., 2018; Zhao et al., 2018). They find across-the-board gaps in
system performance between the two test sets.

Outside of coreference resolution, Dev et al. (2021) investigate biased
representations with BERT in a masked word prediction task. They find that for
masked pronouns, BERT has a high accuracy in the prediction of masculine and
feminine pronouns, but accuracy considerably lowers for singular they.

##  3 Description of the data augmentation methods

We use two data augmentation methods. First, we follow Lu et al. (2019) and
others in swapping out feminine words for masculine words and vice versa.
Second, we propose a novel augmentation method for generating singular they
data from sentences containing masculine and feminine pronouns. We treat
singular they differently because language internal facts about English
necessitate a separate treatment: unlike he and she, they has a second life as
a plural pronoun.

###  3.1 Feminine/Masculine CDA (FM-CDA)

Consistent with masculine/feminine-term swapping methods in other works, we
swap three kinds of nominal terms:

  * •

Pronouns: Swap masculine pronouns for their feminine counterparts and vice
versa. Ex: him $\rightarrow$ her. Because the masculine and feminine
pronominal paradigms are partly syncretic—the feminine pronoun her can be
accusative or possessive and map to him or his, respectively—token POS tags,
generated by a proprietary POS tagger, were used to appropriately match terms
to their case-same counterpart.

  * •

Common nouns: Swap definitionally feminine common nouns for their masculine
gendered counterparts and vice versa. Ex: actor $\rightarrow$ actress. The
selection and mapping of these nouns were hand-curated by industry experts.

  * •

Names: Swap first names that are usually associated with feminine terms for
names usually associated with masculine terms and vice versa. We partnered
with industry experts to curate dictionaries of masculine and feminine names.
Because names don’t necessarily have gendered counterparts in the way that
pronouns or common nouns do, an arbitrary mapping of names was created. Names
occurring in both lists were excluded from swapping.

Unlike some previous work involving CDA on fully unsupervised tasks where the
creation of a single counterpart sentence is sufficient, GEC training data
consists of pairs of ungrammatical source text and grammatical target text.
This introduces challenges similar to those that CDA faces for machine
translation data consisting of parallel texts (Saunders and Byrne, 2020; Wang
et al., 2022) Because, e.g., the POS tagger may perform differently on the two
texts, especially given that the source text is ungrammatical, the swapping
algorithm may produce inconsistent swaps if applied separately to the source
and target texts. This inconsistency can introduce grammatical errors between
the source and target texts and negatively impact model performance.

To avoid this, an additional algorithm ensures a consistent swap between the
source and target text where possible. We first apply our algorithm to the
grammatically corrected target text. Then we use an alignment algorithm to
align the target and source texts and isolate the differing segments of the
texts. For each differing segment, we determine if the number of tokens in the
source and target segments is the same, and if not, we discard the data. Then
we compare every token in the source and target segments; if the source word
would have the same swap as the target, we replace the source word with its
differently gendered counterpart. If neither word is swappable, we do nothing.
If there is a mismatch in the swap between source word and target word, we
discard the data point. For the evaluation set discussed below, we
reintroduced this discarded data and manually edited the data to introduce
singular they pronouns and ensure that the results are parallel.

###  3.2 Singular they CDA (St-CDA)

Singular they is an inherently referential phenomenon. As is evident in the
name, it is distinguished from plural they because it refers to singular
individuals. Further, theoretical and experimental linguistic works show that
the overall distribution of singular they is conditioned by the nature of the
singular antecedent and discourse participants’ relation to the antecedent
(Bjorkman, 2017; Ackerman, 2019; Moulton et al., 2020; Konnelly and Cowper,
2020; Han and Moulton, 2022). Speakers may be sensitive to linguistic vs. non-
linguistic antecedents (Moulton et al., 2020), specificity and definiteness of
the antecedent (Bjorkman, 2017; Konnelly and Cowper, 2020), the discourse
participant’s knowledge of the referent’s gender identity (Bjorkman, 2017;
Ackerman, 2019; Konnelly and Cowper, 2020), and the association of a lexical
item or name with a particular gender category (Bjorkman, 2017; Ackerman,
2019; Moulton et al., 2020). In the case of the broadest distribution,
singular they is used in the same ways that masculine and feminine pronouns
are used—the referent’s preference largely dictates the choice of pronoun–but
they may additionally be used when the referent’s preference is not known
(Konnelly and Cowper, 2020).

Differently than feminine and masculine pronouns, we hypothesize that adverse
model behavior with singular they is at least partially caused by its
infrequency relative to plural they. Therefore, it is not enough to simply
create data that has they pronouns; it must also be evidently singular as
well. We leverage these linguistic insights about antecedenthood to identify
contexts where swapping will result in unambiguous cases of singular they by
identifying singular antecedents of the pronouns in the text.

We implement this by using HuggingFace’s Neuralcoref coreference resolution
system333https://github.com/huggingface/neuralcoref built on top of
SpaCy444Neuralcoref works with SpaCy v2.1 (https://v2.spacy.io/).. For a given
coreference cluster with a masculine or feminine pronoun, we look at the
coreferring expressions in the cluster. If we find a singular one, we perform
the swap. We consider a coreferring expression singular if it is:

  1. 1.

A singular common or proper noun.

  2. 2.

A singular possessum (e.g., his foot).

In addition, they has different verbal agreement paradigms than he or she. We
resolve this by using SpaCy’s dependency parser to identify agreeing verbs
with the swapped pronouns. We then use the pyInflect
package555https://github.com/bjascob/pyInflect to select the verbal inflection
consistent with subject agreement with they. Finally, we use POS information
to disambiguate syncretic forms of her. For reflexive pronouns, we swap in the
form themself and not themselves as this form is much less common in the
preexisting training data and is more likely to lead to a singular
interpretation of they pronouns.

As in the case of FM-CDA, we face the potential for inconsistency if this
technique is used separately for both source and target data. We use the same
algorithm as FM-CDA to perform safe swaps with an additional check on the
verbs that were corrected to agree with they in the target swapped data.

Figure 1: A graphical illustration of the St-CDA swapping process.

###  3.3 Differences between St-CDA and other approaches

To our knowledge, there are two similar approaches to generating singular they
data in Sun et al. (2021) and Vanmassenhove et al. (2021). Their approaches
differ from ours in two crucial ways. First, their techniques are meant to
create wholly gender-neutral texts, swapping out instances of definitionally
gendered noun phrases like “fireman” for “firefighter”. We do not perform
these swaps because they pronouns may corefer with definitionally gendered
words, and this data, in particular, is likely to be rare in most corpora. As
we see qualitatively, the baseline model we test seems to be particularly
likely to “correct” singular they sentences unnecessarily when there is a
definitionally gendered word in the sentence.

Second, and most crucially, we hypothesize that the performance gap with
singular they sentences is due to the relative glut of plural they data
compared to singular they data. As such, we seek to add they data that
unambiguously has singular reference. Their techniques, by contrast, may
result in data where they may have a primarily plural interpretation. By
targeting contexts where they is more likely to be interpreted singularly, we
believe St-CDA produces data that will have a higher positive impact and have
fewer adverse effects on model quality.

Ultimately, Sun et al. (2021) and Vanmassenhove et al. (2021) have different
goals than we do, and this informs the differences in our techniques. Both
works envision their technique to be used at runtime in machine translation
tasks to, e.g., ensure translations from languages with grammatical gender
result in gender neutral translations in English. While they speculate that
their techniques can be used to create augmented training data, as we do in
this paper, they do not specify what issues they intend this augmented
training data to address. By contrast, we seek to counteract a particular
imbalance between plural and singular they sentences.

##  4 Experiments with GEC

###  4.1 Description of datasets

For training data, we chose a large Lang-8 Corpus of Learner English (Mizumoto
et al., 2011), and more specifically, its “cleaned” version cLang-8 (Rothe et
al., 2021) which contains over 2 million corrected English sentences. The
downside is the noisiness of the data (even in the “cleaned” version) and the
lack of consistency in annotations. There are few other GEC datasets of
comparable size (Bryant et al., 2022). Naturally, not every sentence contains
personal pronouns, so only a subset of the dataset is suitable for data
augmentation. The size of cLang-8 allowed us to produce about 63 thousand
sentences with singular-they augmentation and 254 thousand gender-swapped
sentences, which is enough for fine-tuning purposes. In our further
experiments, we used only a random sample of 50 thousand sentences from each
augmented version of the data to make sure that the results were not impacted
by a difference in data size.

###  4.2 Evaluation approach

####  4.2.1 Description of the evaluation procedure

There is no evaluation set which would specifically contain multiple uses of
the singular they, so we need to apply data augmentation here as well. To do
this, we use the dev part of the BEA-2019 shared task (Bryant et al., 2019)
since it is one of the standard evaluation sets for GEC. Of 4384 sentences in
the BEA dataset, 195 singular they sentences were created by replacing the
pronouns “he” and “she” with singular “they.” To do this, we applied the CDA-
st algorithm described above. The data discarded by the alignment algorithm
was also collected and manually revised where possible (sentences where, e.g.,
a pronoun was inserted or changed from one gendered pronoun to another were
either eliminated or revised to eliminate the error). Finally, the entire
dataset was manually reviewed to ensure consistency between the original data
and the augmented data.

To find the difference in GEC performance on sentences with and without the
singular “they,” we evaluate on the subset of 195 sentences before
augmentation, “BEA-195-orig”, and on the 195 augmented sentences, “BEA-195-st-
aug”. The dataset size limits the conclusions we can make about the GEC
model’s performance in general, but the differences between scores obtained by
the GEC models on these two subsets are statistically significant.

We repeat this procedure for experiments involving masculine and feminine
swapping. In this case, our augmentation produced subsets of 556 sentences:
“BEA-556-orig” and “BEA-556-mf-aug”.

####  4.2.2 Error distribution analysis

To ensure that our augmentation did not affect edits and shift the error
distribution, we conducted a qualitative analysis of m2 files produced by
Errant tool on parallel sentences of the original and augmented versions of
"195" and "556" evalsets. As shown in the edit type distribution (appendix
section B.1), there are only minor differences in the number of edits (less
than 1% of edits affected). It can be explained by the fact that sometimes
Errant might represent similar edits by single or multiple edits, like in the
following example 2.
The error type distribution for both subsets is available in appendix section
B.2.

Data source | Sentence | Edits
---|---|---
original bea-dev | I love this game because my favourite | sport man belong to this
| sport man belong to this game . | => sportsman plays
mf aug bea-dev | I love this game because my favourite | sport woman => sportswoman
| sport woman belong to this game . | belong to this => plays
Table 2:  An example of a sentence with a different number of edits in an m2
file depending on data augmentation.

####  4.2.3 Questions to answer with evaluation

Running evaluation on these datasets, we are interested mainly in answering
two questions:

  * •

Is the state-of-the-art GEC model, which was not trained specifically with
singular “they” or gender-swapped data, producing worse corrections on the
augmented evaluation dataset?

  * •

If the corrections are worse, can we shrink or remove the gap in performance
by fine-tuning the model on the augmented training data?

###  4.3 Description of models

For experiments, we use GECToR (Omelianchuk et al., 2021) \- a state-of-the-
art GEC model based on the efficient sequence tagging approach to corrections.
Instead of producing a new error-free sentence, GECToR predicts a sequence of
tags denoting operations: _“keep,” “remove,” “insert_X,”_ or _“append_X.”_ The
corrected text is reconstructed from the original sentence and the tags.
Sequence tagging is computationally cheaper than autoregressive approaches,
which makes GECToR up to ten times faster than sequence-to-sequence models. At
the same time, GECToR set the state-of-the-art at the time of publication.

GECToR is trained and fine-tuned in several stages, starting from the pre-
trained language model such as RoBERTa (Liu et al., 2019). One can also start
from the fine-tuned GECToR checkpoint (available on GitHub) and fine-tune it
further on the data specifically tailored to the task at hand. However, it may
lead the catastrophic forgetting issue, and the overall performance of the
model on the general GEC test sets may deteriorate.

###  4.4 Experiment approach

We select GECToR for our fine-tuning experiments due to it being a competitive
GEC system and having code that is publicly available. We use weights of the
pre-trained GECToR (with RoBERTa-base encoder) model as initialization and
fine-tune it for 5 epochs on the following data:

  1. 1.

Original clang8 sentences ( 2.2m sentences)

  2. 2.

Mix of original and augmented clang8 sentences of one type ( 2.2m + 50k
sentences, either singular-they or gender-swapped)

  3. 3.

Mix of original and augmented clang8 sentences of both types ( 2.2m + 100k
sentences, 50k for both singular-they and gender-swapped)

We fine-tune the model for 5 epochs with early stopping after 3 epochs and 1
cold epoch. For each training data configuration, we run training 10 times
with different random seeds and report the average across all run results. The
full list of hyperparameters for fine-tuning can be found in Appendix B.

Because the baseline GECToR model is already strong enough (it was a SOTA
model in 2020) and clang-8 is high-quality data produced by another strong GEC
system gT5 xxl (Rothe et al., 2021), the fine-tuning does not lead to
substantial quality degradation. As shown in table 3, the differences in F0.5
scores are statistically insignificant.

| Used clang data | bea-dev (full)
---|---|---
# | Orig | MF | ST | F05 orig
0 | no | no | no | 54.58%
1 | yes | no | no | 54.61% ± 0.41%
2 | yes | no | yes | 54.52% ± 0.48%
3 | yes | yes | no | 54.44% ± 0.58%
4 | yes | yes | yes | 54.63% ± 0.56%

Table 3:  F0.5 on BEA-dev-full for GECToR fine-tunining experiments. For new
experiments, average over all seeds ± 2 s.d. is shown.

To evaluate the impact of adding the augmented data to the training dataset,
we used an original subset of BEA dev and its augmented manually reviewed
versions (described above). The results are shown in table 4 and table 5.

| Used clang data | bea-dev 556
---|---|---
# | Orig | MF | ST | F05 orig | F05 mf_aug | Delta
0 | no | no | no | 59.23% | 58.96% | -0.27%
1 | yes | no | no | 57.79% ± 0.82% | 57.08% ± 1.06% | -0.71%
2 | yes | no | yes | 57.58% ± 1.12% | 57.01% ± 1.2% | -0.57%
3 | yes | yes | no | 57.88% ± 0.7% | 57.33% ± 0.78% | -0.55%
4 | yes | yes | yes | 58.03% ± 0.76% | 57.5% ± 1.04% | -0.53%

Table 4:  F0.5 on BEA-dev-556 for GECToR fine-tunining experiments. For new
experiments, average over all 10 seeds ± 2 s.d. is shown.

| Used clang data | bea-dev 195
---|---|---
# | Orig | MF | ST | F05 orig | F05 st_aug | Delta
0 | no | no | no | 58.28% | 48.74% | -9.54%
1 | yes | no | no | 56.33% ± 2.1% | 50.47% ± 1.62% | -5.86%
2 | yes | no | yes | 55.71% ± 1.22% | 54.31% ± 1.62% | -1.4%
3 | yes | yes | no | 55.77% ± 1.04% | 50.33% ± 1.12% | -5.44%
4 | yes | yes | yes | 56.33% ± 1.48% | 54.86% ± 1.46% | -1.47%

Table 5:  F0.5 on BEA-dev-195 for GECToR fine-tunining experiments. For new
experiments, average over all 10 seeds ± 2 s.d. is shown.

####  4.4.1 Experiment with singular-they augmentation

We can see that for the baseline model, the gap in F0.5 between the original
and augmented (singular-they) version of BEA dev subset is quite significant
-9.54%. Fine-tuning on clang8 data led to the shrinking of the gap to -5.86%.
We think that this decrease illustrates not an improvement in gender bias, but
rather a change in the baseline value due to a shift in precision/recall after
fine-tuning. For a more fair comparison, we focused on analyzing the
difference between the fine-tuned model on a combination of original and
augmented data from clang8 (systems 2,3,4) and a model fine-tuned only on
original clang data (system 1) (table 5).

We got an improvement in the F0.5 gap for systems 2 and 4 (from -5.86% to
-1.4% and -1.47% correspondingly). This reduction is driven by the improvement
on the augmented version of bea-dev-195 subset (F0.5 +3.84% and +4.39%)
without any (0% for system 4) or with insignificant degradation in quality on
the original bea-dev-195 subset (-0.62% for system 3).

We also qualitatively examine the corrections to determine whether explicit
instances of bias are reduced through data augmentation (table 6). A linguist
manually reviewed model predictions on bea-dev-195-st-aug for systems 1-4 and
annotated predictions exhibiting explicit bias, which was defined as
pluralization of a referent coreferring with singular they or the replacement
of singular they with a gendered pronoun, or the replacement of themself with
themselves. System 4 shows the greatest improvement with 7 cases over the
baseline of 32. Examples of explicit bias are in Appendix A.

| Used clang data | bea-dev-195-st-aug
---|---|---
# | Orig | MF | ST | # | # w/o refl |
1 | yes | no | no | 32 | 29 |
2 | yes | no | yes | 8 | 7 |
3 | yes | yes | no | 34 | 30 |
4 | yes | yes | yes | 7 | 4 |

Table 6:  Number of sentences displaying explicit bias in bea-dev-195-st-aug.
First column is total sentences found to have explicit bias, second is that
count minus cases of "themself">"themselves".

####  4.4.2 Experiment with feminine/masculine augmentation

For feminine/masculine augmentation, the initial gap between the original
subset of BEA (556 sentences) and the augmented version is much smaller
-0.71%. Fine-tuning on original and feminine/masculine augmentation data
(system 3) very slightly reduces this difference only to -0.55%. It’s
interesting that even singular-they augmentation, without any other gender-
swapping, seems to provide a very similar result (difference of -0.57%).
However, given the size of confidence intervals, we cannot say that any of our
experiments had a significant impact on the gap.

####  4.4.3 Experiment with both augmentations

Finally, we tried to apply both kinds of augmentation - singular-they and
feminine/masculine CDA. The resulting model (system 4) is producing very
similar results in terms of gap difference for both BEA subsets that we used:
-1.47% on bea-195 (system 2 gap is -1.4%) and -0.53% on bea-556 (system 3 gap
is -0.55%), which is showing that multiple biases might be handled with such a
single fine-tuning approach at once. It also seems that augmented training
data of two kinds does not interfere with any one evaluation but also does not
provide additional benefits from this data interaction.

We believe that there are many other potential possibilities to incorporate
augmented data into different stages of the training or change the proportion
or the absolute number of original and augmented sentences in training data
that might lead to even better improvement with little to no quality
degradation. We would like to explore some of them in future work.

##  5 Conclusion

In this work, we developed a novel technique for data augmentation with
sentences containing they that has an unambiguous singular reference and
applied it to the GEC case. We used this technique to help develop a dataset
of singular they data to parallel data in the BEA shared task dataset that has
masculine and feminine pronouns, and with this, we show that GEC systems
display bias in their treatment of singular they sentences compared to
sentences with masculine or feminine pronouns. Additionally, we demonstrated
that this technique could be used to reduce bias in GEC systems by fine-tuning
the GEC system on the generated synthetic training data.

Because this technique is data-oriented, we believe that it has wider
applications, and other NLP systems that display degraded performance with
respect to singular they may benefit from being trained on data created
through this technique.

## Limitations

As noted, this work is limited in that it does not address neopronouns. We
speculate that the augmentation techniques deployed in this work may extend to
these pronouns as well, we recognize that they do not have the same linguistic
reality as he/she/they pronouns. Neopronouns may be similar to singular they
in being relatively infrequent in a naturalistic corpus, but they are also
different in that they don’t overlap with a frequent morphologically-identical
paradigm like plural they.

Additionally, the singular they augmentation technique we propose is specific
to English and distributional facts about English pronouns. For one, English
singular they morphologically overlaps with a plural pronoun, which is the
primary motivation for using coreference information to identify contexts
where they would have a primarily singular interpretation. This is often not
the case for other languages, as in Swedish where the gender-neutral hen is
functionally similar to singular they but morphologically and distributionally
dissimilar in that it does not overlap with a plural pronoun (Gustafsson
Sendén et al., 2015).

## Ethics Statement

### Dataset risks

We do not anticipate any risks in releasing the evaluation dataset. This
dataset was constructed through the modification of a publicly available
dataset commonly used in the evaluation of GEC systems, the dev set of the
BEA-2019 shared task (Bryant et al., 2019). These modifications involve the
change of gendered words and agreeing verbs to create parallel data across
masculine, feminine, and singular they pronouns with the goal of evaluating
bias in GEC systems. By enabling researchers to measure bias in this way, we
believe that the release of this dataset will aid further study in reducing
bias in these systems by providing a benchmark.

### Risks of describing data augmentation techniques

We caution that the singular they data augmentation technique used in this
paper was not designed to generate text that surfaces directly to users. There
may be risks to deploying data augmentation techniques at runtime as these
techniques are designed to modify gender identity terms; depending on the
context of deployment, users may be harmed by such modifications if they
result in misgendering or erasure. On the other hand, as we show in this work,
use of these techniques to generate training data can reduce bias, and we
believe that in this way, the description of this technique will aid in
reducing bias in NLP systems.

## Acknowledgements

This research was supported by Grammarly. We thank our colleagues Leonardo
Neves, Jade Razzaghi, Yichen Mo, Serhii Yavnyi, and Knar Hovakimyan for their
brilliant insights and suggestions over the course of this work. We would also
like to thank 3 anonymous reviewers for their helpful comments.

## References

  * Ackerman (2019) Lauren Ackerman. 2019.  Syntactic and cognitive issues in investigating gendered coreference.  _Glossa: a journal of general linguistics_ , 4(1).  Number: 1 Publisher: Open Library of Humanities.
  * Baumler and Rudinger (2022) Connor Baumler and Rachel Rudinger. 2022.  Recognition of They/Them as Singular Personal Pronouns in Coreference Resolution.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 3426–3432, Seattle, United States. Association for Computational Linguistics.
  * Bjorkman (2017) Bronwyn M. Bjorkman. 2017.  Singular they and the syntactic representation of gender in English.  _Glossa: a journal of general linguistics_ , 2(1).  Number: 1 Publisher: Open Library of Humanities.
  * Blodgett et al. (2020) Su Lin Blodgett, Solon Barocas, Hal Daumé III, and Hanna Wallach. 2020.  Language (Technology) is Power: A Critical Survey of "Bias" in NLP.
  * Bolukbasi et al. (2016) Tolga Bolukbasi, Kai-Wei Chang, James Zou, Venkatesh Saligrama, and Adam Kalai. 2016\.  Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embeddings.  Number: arXiv:1607.06520 arXiv:1607.06520 [cs, stat].
  * Bryant et al. (2019) Christopher Bryant, Mariano Felice, Øistein E. Andersen, and Ted Briscoe. 2019\.  The BEA-2019 Shared Task on Grammatical Error Correction.  In _Proceedings of the Fourteenth Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 52–75, Florence, Italy. Association for Computational Linguistics.
  * Bryant et al. (2022) Christopher Bryant, Zheng Yuan, Muhammad Reza Qorib, Hannan Cao, Hwee Tou Ng, and Ted Briscoe. 2022.  Grammatical Error Correction: A Survey of the State of the Art.  ArXiv:2211.05166 [cs].
  * Cao and Daumé III (2021) Yang Trista Cao and Hal Daumé III. 2021.  Toward Gender-Inclusive Coreference Resolution: An Analysis of Gender and Bias Throughout the Machine Learning Lifecycle*.  _Computational Linguistics_ , 47(3):615–661.  Place: Cambridge, MA Publisher: MIT Press.
  * Dev et al. (2021) Sunipa Dev, Masoud Monajatipoor, Anaelia Ovalle, Arjun Subramonian, J. M. Phillips, and Kai Wei Chang. 2021.  Harms of Gender Exclusivity and Challenges in Non-Binary Representation in Language Technologies.  In _EMNLP_.
  * Devinney et al. (2022) Hannah Devinney, Jenny Björklund, and Henrik Björklund. 2022.  Theories of “Gender” in NLP Bias Research.  In _2022 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’22, pages 2083–2102, New York, NY, USA. Association for Computing Machinery.
  * Gustafsson Sendén et al. (2015) Marie Gustafsson Sendén, Emma A. Bäck, and Anna Lindqvist. 2015.  Introducing a gender-neutral pronoun in a natural gender language: the influence of time on attitudes and behavior.  _Frontiers in Psychology_ , 6.
  * Han and Moulton (2022) Chung-hye Han and Keir Moulton. 2022.  Processing bound-variable singular they.  _Canadian Journal of Linguistics/Revue canadienne de linguistique_ , 67(3):267–301.  Publisher: Cambridge University Press.
  * Konnelly and Cowper (2020) Lex Konnelly and Elizabeth Cowper. 2020.  Gender diversity and morphosyntax: An account of singular they.  _Glossa: a journal of general linguistics_ , 5(1).  Number: 1 Publisher: Open Library of Humanities.
  * Levesque et al. (2012) Hector J. Levesque, Ernest Davis, and Leora Morgenstern. 2012.  The Winograd schema challenge.  In _Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning_ , KR’12, pages 552–561, Rome, Italy. AAAI Press.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  ArXiv:1907.11692 [cs].
  * Lu et al. (2019) Kaiji Lu, Piotr Mardziel, Fangjing Wu, Preetam Amancharla, and Anupam Datta. 2019\.  Gender Bias in Neural Natural Language Processing.  _arXiv:1807.11714 [cs]_.  ArXiv: 1807.11714.
  * Maudslay et al. (2020) Rowan Hall Maudslay, Hila Gonen, Ryan Cotterell, and Simone Teufel. 2020.  It’s All in the Name: Mitigating Gender Bias with Name-Based Counterfactual Data Substitution.  _arXiv:1909.00871 [cs]_.  ArXiv: 1909.00871.
  * McConnell-Ginet (2013) Sally McConnell-Ginet. 2013.  ‘ Gender and its relation to sex: The myth of ‘natural’ gender.  In _‘ Gender and its relation to sex: The myth of ‘natural’ gender_ , pages 3–38. De Gruyter Mouton.
  * Mizumoto et al. (2011) Tomoya Mizumoto, Mamoru Komachi, Masaaki Nagata, and Yuji Matsumoto. 2011.  Mining Revision Log of Language Learning SNS for Automated Japanese Error Correction of Second Language Learners.  In _Proceedings of 5th International Joint Conference on Natural Language Processing_ , pages 147–155, Chiang Mai, Thailand. Asian Federation of Natural Language Processing.
  * Moulton et al. (2020) Keir Moulton, Chung-hye Han, Trevor Block, Holly Gendron, and Sander Nederveen. 2020\.  Singular they in context.  _Glossa: a journal of general linguistics_ , 5(1).  Number: 1 Publisher: Open Library of Humanities.
  * Omelianchuk et al. (2020) Kostiantyn Omelianchuk, Vitaliy Atrasevych, Artem Chernodub, and Oleksandr Skurzhanskyi. 2020.  GECToR – Grammatical Error Correction: Tag, Not Rewrite.  ArXiv:2005.12592 [cs].
  * Omelianchuk et al. (2021) Kostiantyn Omelianchuk, Vipul Raheja, and Oleksandr Skurzhanskyi. 2021.  Text Simplification by Tagging.  In _Proceedings of the 16th Workshop on Innovative Use of NLP for Building Educational Applications_ , pages 11–25, Online. Association for Computational Linguistics.
  * Rothe et al. (2021) Sascha Rothe, Jonathan Mallinson, Eric Malmi, Sebastian Krause, and Aliaksei Severyn. 2021.  A Simple Recipe for Multilingual Grammatical Error Correction.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 702–707, Online. Association for Computational Linguistics.
  * Rudinger et al. (2018) Rachel Rudinger, Jason Naradowsky, Brian Leonard, and Benjamin Van Durme. 2018.  Gender Bias in Coreference Resolution.  _arXiv:1804.09301 [cs]_.  ArXiv: 1804.09301.
  * Saunders and Byrne (2020) Danielle Saunders and Bill Byrne. 2020.  Reducing gender bias in neural machine translation as a domain adaptation problem.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7724–7736, Online. Association for Computational Linguistics.
  * Sorokin (2022) Alexey Sorokin. 2022.  Improved grammatical error correction by ranking elementary edits.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 11416–11429, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Strunk and White (1999) William Strunk and E. B. White. 1999.  _The elements of style_ , 4th ed edition.  Allyn and Bacon, Boston.
  * Sun et al. (2021) Tony Sun, Kellie Webster, Apu Shah, William Yang Wang, and Melvin Johnson. 2021\.  They, Them, Theirs: Rewriting with Gender-Neutral English.  ArXiv:2102.06788 [cs].
  * Vanmassenhove et al. (2021) Eva Vanmassenhove, Chris Emmery, and Dimitar Shterionov. 2021.  NeuTral Rewriter: A Rule-Based and Neural Approach to Automatic Rewriting into Gender Neutral Alternatives.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 8940–8948, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Wang et al. (2022) Jun Wang, Benjamin Rubinstein, and Trevor Cohn. 2022.  Measuring and Mitigating Name Biases in Neural Machine Translation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2576–2590, Dublin, Ireland. Association for Computational Linguistics.
  * Zhao et al. (2018) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018\.  Gender Bias in Coreference Resolution: Evaluation and Debiasing Methods.  _arXiv:1804.06876 [cs]_.  ArXiv: 1804.06876.

##  Appendix A Examples of explicit bias

Here we present examples of how the systems investigated here exhibit explicit
bias. These are indicated in bold text. The list numbers correspond to the
systems indicated in Table 3.

Source text:
I said that because when I was eleven my best friend had been operated on
their back and before the operation he came with me and every day I had to
wait for them because they spendt a lot of time in the shower cleaning their
long hais , I hated that !

  1. 0.

I said that because when I was eleven my best friend had been operated on and
before the operation he came with me and every day I had to wait for them
because they spendt a lot of time in the shower cleaning their long hair . I
hated that !

  2. 1.

I said that because when I was eleven my best friend had been operated on his
back and before the operation he came with me and every day I had to wait for
them because they spendt a lot of time in the shower cleaning their long hair
. I hated that !

  3. 2.

I said that because when I was eleven my best friend had been operated on
their back and before the operation he came with me and every day I had to
wait for them because they spendt a lot of time in the shower cleaning their
long hair . I hated that !

  4. 3.

I said that because when I was eleven my best friend had been operated on
their back and before the operation he came with me and every day I had to
wait for them because they spendt a lot of time in the shower cleaning their
long hair . I hated that !

  5. 4.

I said that because when I was eleven my best friend had been operated on
their back and before the operation he came with me and every day I had to
wait for them because they spendt a lot of time in the shower cleaning their
long hair . I hated that !

Source text:
To take my friend , Taylor , as an example , their homeland were over -
developed and become an arid place when they were a child .

  1. 0.

To take my friend , Taylor , as an example , their homeland was over -
developed and became an arid place when they were children .

  2. 1.

To take my friend , Taylor , as an example , their homeland was over -
developed and became an arid place when they were children .

  3. 2.

To take my friend , Taylor , as an example , their homeland was over -
developed and became an arid place when they were a child .

  4. 3.

To take my friend , Taylor , as an example , their homeland was over -
developed and became an arid place when they were children .

  5. 4.

To take my friend , Taylor , as an example , their homeland was over -
developed and became an arid place when they were a child .

Source text:
My father has the same program in their computer and is able to buy on line
tickets w / out leaving the house and moreover w / out picking up the phone .

  1. 0.

My father has the same program on his computer and is able to buy online
tickets w / out leaving the house and moreover w / out picking up the phone .

  2. 1.

My father has the same program on his computer and is able to buy online
tickets w / out leaving the house and moreover w / out picking up the phone .

  3. 2.

My father has the same program on their computer and is able to buy online
tickets without leaving the house and moreover without picking up the phone .

  4. 3.

My father has the same program on his computer and is able to buy online
tickets w / out leaving the house and moreover w / out picking up the phone .

  5. 4.

My father has the same program on their computer and is able to buy online
tickets without leaving the house and moreover without picking up the phone .

##  Appendix B Error distribution on BEA-dev subsets

###  B.1 Edit type distribution on "195" and "556" subsets of bea_dev

| bea_dev_195 | bea_dev_556
---|---|---
| orig | st_aug | orig | mf_aug
Edit type | # edits | % edits | # edits | % edits | # edits | % edits | # edits | % edits
R (replacement) | 374 | 66.1% | 371 | 66.0% | 814 | 64.1% | 814 | 64.1%
M (missing) | 156 | 27.6% | 157 | 27.9% | 358 | 28.2% | 358 | 28.2%
U (unnecessary) | 36 | 6.4% | 34 | 6.0% | 97 | 7.6% | 96 | 7.6%
Total | 566 | 100% | 562 | 100% | 1269 | 100% | 1268 | 100%

###  B.2 Error categories distribution on "195" and "556" subsets of bea_dev

| bea_dev_195 | bea_dev_556
---|---|---
| orig | st_aug | orig | mf_aug
Error category | # edits | % edits | # edits | % edits | # edits | % edits | # edits | % edits
PUNCT | 150 | 26.5% | 150 | 26.7% | 314 | 24.7% | 314 | 24.8%
VERB:TENSE | 68 | 12.0% | 66 | 11.7% | 139 | 11.0% | 139 | 11.0%
OTHER | 45 | 8.0% | 48 | 8.5% | 121 | 9.5% | 122 | 9.6%
PREP | 46 | 8.1% | 46 | 8.2% | 115 | 9.1% | 114 | 9.0%
DET | 35 | 6.2% | 34 | 6.0% | 92 | 7.2% | 89 | 7.0%
ORTH | 44 | 7.8% | 44 | 7.8% | 84 | 6.6% | 84 | 6.6%
SPELL | 42 | 7.4% | 41 | 7.3% | 73 | 5.8% | 74 | 5.8%
VERB | 31 | 5.5% | 30 | 5.3% | 67 | 5.3% | 67 | 5.3%
VERB:FORM | 14 | 2.5% | 15 | 2.7% | 36 | 2.8% | 37 | 2.9%
PRON | 10 | 1.8% | 10 | 1.8% | 35 | 2.8% | 36 | 2.8%
NOUN | 17 | 3.0% | 17 | 3.0% | 34 | 2.7% | 35 | 2.8%
NOUN:NUM | 6 | 1.1% | 6 | 1.1% | 33 | 2.6% | 32 | 2.5%
VERB:SVA | 12 | 2.1% | 11 | 2.0% | 25 | 2.0% | 25 | 2.0%
MORPH | 8 | 1.4% | 7 | 1.2% | 24 | 1.9% | 23 | 1.8%
ADV | 12 | 2.1% | 12 | 2.1% | 16 | 1.3% | 17 | 1.3%
ADJ | 10 | 1.8% | 9 | 1.6% | 17 | 1.3% | 16 | 1.3%
WO | 5 | 0.9% | 5 | 0.9% | 12 | 0.9% | 12 | 0.9%
NOUN:POSS | 3 | 0.5% | 3 | 0.5% | 10 | 0.8% | 10 | 0.8%
PART | 5 | 0.9% | 5 | 0.9% | 8 | 0.6% | 8 | 0.6%
CONTR | 1 | 0.2% | 1 | 0.2% | 6 | 0.5% | 6 | 0.5%
CONJ | 2 | 0.4% | 2 | 0.4% | 6 | 0.5% | 6 | 0.5%
VERB:INFL | 0 | 0.0% | 0 | 0.0% | 2 | 0.2% | 2 | 0.2%
Total | 566 | 100% | 562 | 100% | 1269 | 100% | 1268 | 100%

##  Appendix C Hyperparameter values for the fine-tuning of GECToR

Hyperparameter name | Hyperparameter value
---|---
batch_size | 32
accumulation_size | 4
n_epoch | 5
patience | 3
max_len | 5
lr | 1e-05
cold_steps_count | 1
cold_lr | 0.001
tp_prob | 1
tn_prob | 1
updates_per_epoch | 10000
special_tokens_fix | 1
transformer_model | roberta-base
Pretrained model |
Inference tweaks: |
minimum error probability | 0.5
Inference tweaks: |
confidence | 0.2

##  Appendix D Hyperparameter values for the fine-tuning of BART

Hyperparameter name | Hyperparameter value
---|---
base_model | BART-Large
src_max_length | 80
tgt_max_length | 85
beam | 2
max_update | 16000
loss_criterion | label_smoothed_cross_entropy
optimizer | Adam
weight_decay | 0.0
adam_betas | (0.9, 0.98)
adam_eps | 1e-06
lr | 3e-05

##  Appendix E Full results of evaluation

System | bea-dev-full | bea-195-orig | bea-195-st-aug | bea-556-orig | bea–556-mf-aug
---|---|---|---|---|---
| P | R | F05 | P | R | F05 | P | R | F05 | P | R | F05 | P | R | F05
GECToR (roberta-base) | 64.05% | 34.28% | 54.57% | 70.11% | 34.81% | 58.28% | 56.33% | 31.67% | 48.74% | 69.46% | 37.27% | 59.23% | 68.84% | 37.46% | 58.96%
BART (seq2seq) | 57.46% | 39.7% | 52.74% | 61.32% | 42.58% | 56.63% | 53.59% | 39.86% | 50.13% | 62.73% | 46.41% | 58.61% | 63.05% | 46.29% | 58.79%
EditScorer (roberta-large) | 70.29% | 35.77% | 58.92% | 73.98% | 35.16% | 60.6% | 63.76% | 33.81% | 54.16% | 75% | 37.59% | 62.55% | 73.42% | 37.46% | 61.59%

Table 7:  Scores on BEA-dev subsets for strong GEC baselines.

| Used clang data | bea-dev (full)
---|---|---
# | Orig | MF | ST | Precision | Recall | F05 orig
0 | no | no | no | 64.05% | 34.28% | 54.58%
1 | yes | no | no | 62.29% ± 1.3% | 36.6% ± 1.58% | 54.61% ± 0.41%
2 | yes | no | yes | 62.19% ± 1.12% | 36.35% ± 0.98% | 54.52% ± 0.48%
3 | yes | yes | no | 62.38% ± 1.1% | 36.25% ± 1.34% | 54.44% ± 0.58%
4 | yes | yes | yes | 62.41% ± 0.72% | 36.46% ± 0.82% | 54.63% ± 0.56%

Table 8:  F0.5 on BEA-dev-full for GECToR fine-tunining experiments. For new
experiments, average over all seeds ± 2 s.d. is shown.


over all $i\in\mathcal{I}$, we have
$\sum_{i\in\mathcal{I}}\bar{y}_{i}{\mathbf{a}^{i}}^{\prime}(\mathbf{\hat{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k})=\sum_{i\in\mathcal{I}}\bar{y}_{i}b_{i}$
or equivalently
$\bar{\mathbf{c}}^{\prime}(\mathbf{\hat{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k})=\mathbf{b}^{\prime}\bar{\mathbf{y}}$,
satisfying (5e). Clearly,
$\\{\bar{\boldsymbol{\epsilon}}_{k}\\}_{k\in\mathcal{K}}$ and
$\bar{\mathcal{S}}$ satisfy constraints (5f)–(5h). Therefore,
$(\bar{\mathbf{c}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\bar{\mathbf{y}},\bar{\mathcal{S}})$
is feasible for $\mathbf{QIO}(\mathcal{K},\tau,\theta)$.

###### Proof 9.5

Proof of Proposition 3.6: For this proof, we first refer the reader to
Appendix 7.3 where we show a formulation to compute the true inverse stability
measure; this formulation is non-convex but we use it for proving Proposition
3.6. Note that the true inverse stability measure $\xi^{*}$ is the optimal
value of problem (12) in Appendix 7.3.

We first present a variant of (12) for each $i\in\bar{\mathcal{I}}$ separately
(i.e., $|\bar{\mathcal{I}}|$ of them) and show that the optimal objective
value of (12), i.e., $\xi^{*}$, is bounded below by the largest optimal
objective value among these $|\bar{\mathcal{I}}|$ smaller problems. Consider
the following problem for each $i\in\bar{\mathcal{I}}$:

$\displaystyle\underset{\\{\mathbf{x}^{k}\\}_{k\in\mathcal{K}},\mathcal{S}^{i}}{\text{minimize}}$
$\displaystyle\quad\sum_{k\in\mathcal{K}}\|\mathbf{x}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}$
(19a) subject to $\displaystyle\quad
D^{i}(\mathbf{x}^{k})=\underset{\mathbf{z}\in\mathcal{X}_{i}}{\min}\\{\|\mathbf{x}^{k}-\mathbf{z}\|_{\ell}\\},\quad\;\forall
k\in\mathcal{K},$ (19b) $\displaystyle\quad
D^{i}(\mathbf{x}^{k})\geq\tau+\sigma,\quad\;\forall k\in\mathcal{S}^{i},$
(19c)
$\displaystyle\quad|\mathcal{S}^{i}|\geq\lfloor(1-\theta)K\rfloor+1.\quad\;$
(19d)

Let $\zeta_{i}^{*}$ be the optimal value of the above problem for each
$i\in\bar{\mathcal{I}}$. Note that unlike in formulation (12) where
constraints of $D^{i}(\mathbf{x}^{k})\geq\tau+\sigma$ in (12c) must be
satisfied for all $i\in\hat{\mathcal{I}}$, problem (19) requires constraint
(19c) be satisfied for only one
$i\in\bar{\mathcal{I}}\subseteq\hat{\mathcal{I}}$. Hence, we have
$\zeta^{*}_{i}\leq\xi^{*}$ for all $i\in\bar{\mathcal{I}}$, or equivalently,
$\displaystyle\max_{i\in\bar{\mathcal{I}}}\\{\zeta^{*}_{i}\\}\leq\xi^{*}$.
Problem (19) is still non-convex and thus finding $\zeta_{i}^{*}$ is still a
challenge. We next show that its optimal objective value $\zeta_{i}^{*}$ is
equal to the sum of the optimal objective values of even smaller problems that
can be efficiently solved. Given $i\in\bar{\mathcal{I}}$ and
$k\in\mathcal{K}$, consider the following problem:

$\displaystyle\underset{\mathbf{x}^{k}}{\text{minimize}}$
$\displaystyle\quad\|\mathbf{x}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}$ (20a)
subject to $\displaystyle\quad
D^{i}(\mathbf{x}^{k})=\underset{\mathbf{z}\in\mathcal{X}_{i}}{\min}\\{\|\mathbf{x}^{k}-\mathbf{z}\|_{\ell}\\},$
(20b) $\displaystyle\quad D^{i}(\mathbf{x}^{k})\geq\tau+\sigma.$ (20c)

Let $\tilde{\zeta}_{ik}$ denote the optimal value of the above problem. For a
given $i$, let $\tilde{\zeta}_{i[k]}$ be the $k$-th smallest value of
$\tilde{\zeta}_{ik},k\in\mathcal{K}$. Then we have
$\displaystyle\zeta_{i}^{*}=\sum_{k=1}^{\lfloor(1-\theta)K\rfloor+1}\tilde{\zeta}_{i[k]}$.
Thus,
$\displaystyle\max_{i\in\bar{\mathcal{I}}}\bigg{\\{}{\sum_{k=1}^{\lfloor(1-\theta)K\rfloor+1}\tilde{\zeta}_{i[k]}}\bigg{\\}}=\max_{i\in\bar{\mathcal{I}}}\\{\zeta_{i}^{*}\\}\leq\xi^{*}.$

Next, we show how we can find the optimal value for formulation (20), i.e.,
$\tilde{\zeta}_{ik}$. Let
$d_{ik}^{*}=\underset{\mathbf{x}\in\mathcal{X}_{i}}{\min}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$
and $\bar{\tau}=\tau+\sigma$. Note that when $d_{ik}^{*}\geq\bar{\tau}$, we
have $\tilde{\zeta}_{ik}=0$ because $\mathbf{x}^{k}=\hat{\mathbf{x}}^{k}$
satisfies both (20b) and (20c). Now we want to show that if
$d_{ik}^{*}<\bar{\tau}$, $\tilde{\zeta}_{ik}=\bar{\tau}-d_{ik}^{*}$. To do so,
we first show that $\tilde{\zeta}_{ik}\geq\bar{\tau}-d^{*}_{ik}$. Let
$\bar{\mathbf{x}}\in\underset{\mathbf{x}\in\mathcal{X}_{i}}{\text{argmin}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$.
Suppose to the contrary that there exists an optimal solution
$\tilde{\mathbf{x}}^{k}$ that attains
$\tilde{\zeta}_{ik}<\bar{\tau}-d^{*}_{ik}$. By the definition of $d^{*}_{ik}$
we can rewrite this inequality as
$\|\tilde{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}<\bar{\tau}-\|\hat{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}$
or equivalently
$\|\tilde{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}+\|\hat{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}<\bar{\tau}$.
Furthermore, by triangular inequality the following is true:
$\|\tilde{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}\leq\|\tilde{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}+\|\hat{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}<\bar{\tau}$.
However, since $\bar{\mathbf{x}}\in\mathcal{X}_{i}$, we have
$D^{i}(\tilde{\mathbf{x}}^{k})=\underset{\mathbf{z}\in\mathcal{X}_{i}}{\min}\\{\|\tilde{\mathbf{x}}^{k}-\mathbf{z}\|_{\ell}\\}\leq\|\tilde{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}<\bar{\tau}$,
which violates (20c) and thus contradicts the feasibility of
$\tilde{\mathbf{x}}^{k}$. Thus, it must be that
$\tilde{\zeta}_{ik}\geq\bar{\tau}-d^{*}_{ik}$. All we need now is to show that
there exits a feasible solution $\tilde{\mathbf{x}}^{k}$ to problem (20) that
attains the objective function value of $\bar{\tau}-d^{*}_{ik}$. Note that if
a given $\tilde{\mathbf{x}}^{k}$ is feasible for problem (20), we must have
$D^{i}(\tilde{\mathbf{x}}^{k})=\underset{\mathbf{z}\in\mathcal{X}_{i}}{\min}\left\\{\|\tilde{\mathbf{x}}^{k}-\mathbf{z}\|_{\ell}\right\\}$
bounded below by $\bar{\tau}$ (due to (20c)). Consider
$\tilde{\mathbf{x}}^{k}=\frac{\bar{\tau}}{d^{*}_{ik}}\hat{\mathbf{x}}^{k}-\frac{\bar{\tau}}{d^{*}_{ik}}\bar{\mathbf{x}}+\bar{\mathbf{x}}$.
Clearly, $\mathbf{x}^{k}=\tilde{\mathbf{x}}^{k}$ and
$\mathbf{z}=\bar{\mathbf{x}}$ together satisfy all constraints in (20) with
equality because we have $\bar{\mathbf{x}}\in\mathcal{X}_{i}$ and

$\displaystyle\|\tilde{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}$
$\displaystyle=\|\frac{\bar{\tau}}{d^{*}_{ik}}\hat{\mathbf{x}}^{k}-\frac{\bar{\tau}}{d^{*}_{ik}}\bar{\mathbf{x}}+\bar{\mathbf{x}}-\bar{\mathbf{x}}\|_{\ell}$
(21a)
$\displaystyle=\frac{\bar{\tau}}{d^{*}_{ik}}\|\hat{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}$
(21b) $\displaystyle=\frac{\bar{\tau}}{d^{*}_{ik}}d^{*}_{ik}=\bar{\tau}.$
(21c)

Moreover, $\mathbf{x}^{k}=\tilde{\mathbf{x}}^{k}$ leads to the objective value
$\tilde{\zeta}_{ik}=\|\hat{\mathbf{x}}^{k}-\tilde{\mathbf{x}}^{k}\|_{\ell}=\|\hat{\mathbf{x}}^{k}+\frac{\bar{\tau}}{d^{*}_{ik}}\hat{\mathbf{x}}^{k}-\frac{\bar{\tau}}{d^{*}_{ik}}\bar{\mathbf{x}}+\bar{\mathbf{x}}\|_{\ell}=\frac{\bar{\tau}-d^{*}_{ik}}{d^{*}_{ik}}\|\hat{\mathbf{x}}^{k}-\bar{\mathbf{x}}\|_{\ell}=\bar{\tau}-d^{*}_{ik}$
and thus is an optimal solution to (20).

As a result,
$\displaystyle\max_{i\in\bar{\mathcal{I}}}\bigg{\\{}\sum_{k=1}^{(\lfloor(1-\theta)K\rfloor+1)}\\!\\!\\!\\!\\!\max(0,\bar{\tau}-d^{*}_{i[k]})\bigg{\\}}=\max_{i\in\bar{\mathcal{I}}}\bigg{\\{}\sum_{k=1}^{(\lfloor(1-\theta)K\rfloor+1)}\\!\\!\\!\\!\\!\tilde{\zeta}_{i[k]}\bigg{\\}}=\max_{i\in\bar{\mathcal{I}}}\\{\zeta_{i}^{*}\\}\leq\xi^{*}$.
Clearly, because $\tau<\bar{\tau}$ we have
$\displaystyle\max_{i\in\bar{\mathcal{I}}}\bigg{\\{}\sum_{k=1}^{(\lfloor(1-\theta)K\rfloor+1)}\\!\\!\\!\\!\\!\max(0,\tau-d^{*}_{i[k]})\bigg{\\}}\leq\xi^{*}$,
as desired.

###### Proof 9.6

Proof of Proposition 3.7: Given a feasible solution
$(\bar{\mathbf{v}},\bar{\mathbf{u}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}})$
for (6), let $\bar{\mathcal{I}}=\\{i\in\mathcal{I}\,|\,\bar{v}_{i}=1\\}$ and
$\bar{\mathcal{S}}=\\{k\in\mathcal{K}\,|\,\bar{u}_{k}=1\\}$. Due to
constraints (6b) and (6c), for each $k\in\bar{\mathcal{S}}$ we have
$\hat{\mathbf{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k}\in\\{\mathbf{x}\in\mathcal{X}\,|\,{\mathbf{a}^{i}}^{\prime}\mathbf{x}^{k}=b_{i},\forall
i\in\bar{\mathcal{I}}\\}=\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}$
and $\|\bar{\boldsymbol{\epsilon}}^{k}\|_{\ell}\leq\tau$. Now consider
$\bar{\mathbf{c}}\in\textup{cone}_{+}(\\{\mathbf{a}^{i}\\}_{i:\bar{v}_{i}=1})$.
This $\bar{\mathbf{c}}$ vector leads to
$\mathcal{X}^{*}(\bar{\mathbf{c}})=\arg\min\;\textbf{FO}(\bar{\mathbf{c}})=\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}$.
Recall that
$\hat{\mathbf{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k}\in\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}$;
this means that
$\hat{\mathbf{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k}\in\mathcal{X}^{*}(\bar{\mathbf{c}})$
for all $k\in\bar{\mathcal{S}}$. Moreover, because $\mathcal{X}$ is an
$n$-dimensional polytope and $|\bar{\mathcal{I}}|=n$,
$\mathcal{X}^{*}(\bar{\mathbf{c}})$ is a singleton, i.e.,
$\mathcal{X}^{*}(\bar{\mathbf{c}})=\\{\hat{\mathbf{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k}\\},\forall
k\in\bar{\mathcal{S}}$ and
$\hat{\mathbf{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k}=\hat{\mathbf{x}}^{k^{\prime}}-\bar{\boldsymbol{\epsilon}}^{k^{\prime}}$
for all $k,k^{\prime}\in\mathcal{K}$. To complete the proof, for all
$k\in\bar{\mathcal{S}}$ we have
$\displaystyle\max_{\mathbf{x}\in\mathcal{X}^{*}(\bar{\mathbf{c}})}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}=\|\hat{\mathbf{x}}^{k}-(\hat{\mathbf{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k})\|_{\ell}=\|\bar{\boldsymbol{\epsilon}}^{k}\|_{\ell}\leq\tau$.

###### Proof 9.7

Proof of Proposition 3.8: (i) Let
$\bar{\mathcal{H}}=\\{\mathbf{a}^{i}:\bar{v}_{i}=1\\}$ and
$\tilde{\mathcal{H}}=\\{\mathbf{a}^{i}:\tilde{v}_{i}=1\\}$. Because
$\bar{\mathbf{v}}\geq\tilde{\mathbf{v}}$, we have
$\tilde{\mathcal{H}}\subseteq\bar{\mathcal{H}}$ and thus
$\tilde{\mathcal{C}}\subseteq\bar{\mathcal{C}}$. Given the dataset
$\hat{\mathcal{X}}$, we want to show that for any
$\tilde{\mathbf{c}}\in\tilde{\mathcal{C}}$ there exists
$\bar{\mathbf{c}}\in\bar{\mathcal{C}}$ such that
$\underset{\mathbf{x}\in\mathcal{X}^{*}\\!(\bar{\mathbf{c}})}{\max}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}\leq\underset{\mathbf{x}\in\mathcal{X}^{*}\\!(\tilde{\mathbf{c}})}{\max}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$,
$\forall k\in\mathcal{K}$. Suppose to the contrary that there exists
$\mathbf{c}^{*}\in\tilde{\mathcal{C}}$ such that
$\underset{\mathbf{x}\in\mathcal{X}^{*}\\!(\mathbf{c}^{*})}{\max}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}<\underset{\mathbf{x}\in\mathcal{X}^{*}\\!(\mathbf{c})}{\max}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\},\forall\mathbf{c}\in\bar{\mathcal{C}}$
for some $k\in\mathcal{K}$. This means
$\mathbf{c}^{*}\in\tilde{\mathcal{C}}\setminus\bar{\mathcal{C}}$ and thus
$\tilde{\mathcal{C}}\setminus\bar{\mathcal{C}}\neq\emptyset$, which
contradicts $\tilde{\mathcal{C}}\subseteq\bar{\mathcal{C}}$. Thus, for any
$\tilde{\mathbf{c}}\in\tilde{\mathcal{C}}$ there exists
$\bar{\mathbf{c}}\in\bar{\mathcal{C}}$ such that
$\underset{\mathbf{x}\in\mathcal{X}^{*}\\!(\bar{\mathbf{c}})}{\max}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}\leq\underset{\mathbf{x}\in\mathcal{X}^{*}\\!(\tilde{\mathbf{c}})}{\max}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$,
$\forall k\in\mathcal{K}$, as desired.

(ii) Because $\bar{\mathbf{v}}\geq\tilde{\mathbf{v}}$, we have
$\tilde{\mathcal{H}}\subseteq\bar{\mathcal{H}}$ and
$\tilde{\mathcal{C}}\subseteq\bar{\mathcal{C}}$. Because
$\tilde{\mathcal{C}}\subseteq\bar{\mathcal{C}}$,

$\displaystyle\underset{\mathcal{X}\subset\mathbb{R}^{K\times
n}}{\min}\\{d(\hat{\mathcal{X}},\mathcal{X})\,|\,\bar{\mathcal{C}}\cap\mathcal{C}(\mathcal{X})=\emptyset\\}$
$\displaystyle=\underset{\mathcal{X}\subset\mathbb{R}^{K\times
n}}{\min}\\{d(\hat{\mathcal{X}},\mathcal{X})\,|\,(\tilde{\mathcal{C}}\cap\mathcal{C}(\mathcal{X}))\cup((\bar{\mathcal{C}}\setminus\tilde{\mathcal{C}})\cap\mathcal{C}(\mathcal{X}))=\emptyset\\}$
(22a) $\displaystyle=\underset{\mathcal{X}\subset\mathbb{R}^{K\times
n}}{\min}\\{d(\hat{\mathcal{X}},\mathcal{X})\,|\,\tilde{\mathcal{C}}\cap\mathcal{C}(\mathcal{X})=\emptyset\text{
and
}(\bar{\mathcal{C}}\setminus\tilde{\mathcal{C}})\cap\mathcal{C}(\mathcal{X})=\emptyset\\}$
(22b) $\displaystyle\geq\underset{\mathcal{X}\subset\mathbb{R}^{K\times
n}}{\min}\\{d(\hat{\mathcal{X}},\mathcal{X})\,|\,\tilde{\mathcal{C}}\cap\mathcal{C}(\mathcal{X})=\emptyset\\},\text{\;
as desired.\leavevmode\nobreak\ \Halmos}$ (22c)

###### Proof 9.8

Proof of Lemma 4.1: Assume that there exists an optimal solution
$(\bar{\mathbf{v}},\bar{\mathbf{u}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}})$
for $\mathbf{MQIO}(\mathcal{K},\tau,\theta)$ such that
$\sum_{k=1}^{K}\bar{u}_{k}>\lceil\theta K\rceil$. Without loss of generality
let $\sum_{k=1}^{K}\bar{u}_{k}=\lceil\theta K\rceil+r$ where $r>0$. Pick any
$r$ observations for which $\bar{u}_{k}=1$ and change their values to $0$, and
denote this new vector by $\tilde{\mathbf{u}}$. Then we can construct a new
solution
$(\bar{\mathbf{v}},\tilde{\mathbf{u}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}})$,
which is still feasible for $\mathbf{MQIO}(\mathcal{K},\tau,\theta)$ because
$\|\bar{\boldsymbol{\epsilon}}^{k}\|_{\ell}\leq\tau+M_{2}(1-\bar{u}_{k})\leq\tau+M_{2}(1-\tilde{u}_{k}),\forall
k\in\mathcal{K}$ and $\sum_{k=1}^{K}\tilde{u}_{k}=\lceil\theta
K\rceil\geq\theta K$, and generates the same objective value, hence also an
optimal solution.

###### Proof 9.9

Proof of Proposition 4.4:  Consider a matrix $\bar{\mathbf{D}}$ constructed as
in (9). By definition, each row $k\in\mathcal{K}$ of $\bar{\mathbf{D}}$ is a
binary vector ${\mathbf{v}^{k}}^{\prime}$ and there exists
$\bar{\boldsymbol{\epsilon}}^{k}$ such that
$(\mathbf{v}^{k},\bar{\boldsymbol{\epsilon}}^{k})$ is feasible for (8). Assume
that there exists an all-one submatrix in $\bar{\mathbf{D}}$ whose rows and
columns correspond to $\bar{\mathcal{S}}$ and $\bar{\mathcal{A}}$,
respectively, such that $\bar{\mathcal{S}}\subseteq\mathcal{K}$,
$|\bar{\mathcal{S}}|\geq\theta K$, and
$\bar{\mathcal{A}}\subseteq\mathcal{I}$. Define $\bar{\mathbf{v}}$ such that
$\bar{v}_{i}=1$ for all $i\in\bar{\mathcal{A}}$ and $\bar{v}_{i}=0$ otherwise.
Then we have $\bar{\mathbf{v}}\leq\mathbf{v}^{k},\forall
k\in\bar{\mathcal{S}}$, and thus
$(\bar{\mathbf{v}},\bar{\boldsymbol{\epsilon}}^{k})$ is also feasible for (8)
for all $k\in\bar{\mathcal{S}}$. Define $\bar{\mathbf{u}}$ such that
$\bar{u}_{k}=1$ for all $k\in\bar{\mathcal{S}}$ and $\bar{u}_{k}=0$ otherwise;
note that $\sum_{k=1}^{K}\bar{u}_{k}\geq\theta K$. Let
$\boldsymbol{\epsilon}^{k}=\bar{\boldsymbol{\epsilon}}^{k}$ for
$k\in\bar{\mathcal{S}}$ and
$\boldsymbol{\epsilon}^{k}=\hat{\mathbf{x}}^{k}-\mathbf{x}^{k}$ for
$k\in\mathcal{S}\setminus\bar{\mathcal{S}}$ where $\mathbf{x}^{k}$ is
arbitrarily chosen from $\\{\mathbf{x}\in\mathcal{X}\ |\
{\mathbf{a}^{i}}^{\prime}\mathbf{x}=b_{i},\forall i\in\bar{\mathcal{A}}\\}$.
We will first show that the solution
$(\bar{\mathbf{v}},\bar{\mathbf{u}},\\{\boldsymbol{\epsilon}^{k}\\}_{k\in\mathcal{K}})$
constructed as above is feasible for problem (6). For all
$i\in\bar{\mathcal{A}}=\\{i\,|\,\bar{v}_{i}=1\\}$, we have
${\mathbf{a}^{i}}^{\prime}(\hat{\mathbf{x}}^{k}-\boldsymbol{\epsilon}^{k})={\mathbf{a}^{i}}^{\prime}\mathbf{x}^{k}=b_{i}$
for each $k\in\mathcal{K}$. Also, for all
$i\in\mathcal{I}\setminus\bar{\mathcal{A}}$ (i.e.,
$\\{i\,|\,\bar{v}_{i}=0\\}$), we have
${\mathbf{a}^{i}}^{\prime}(\hat{\mathbf{x}}^{k}-\boldsymbol{\epsilon}^{k})={\mathbf{a}^{i}}^{\prime}\mathbf{x}^{k}\geq
b_{i}$ for each $k\in\mathcal{K}$. Thus, $\bar{\mathbf{v}}$ and
$\\{\boldsymbol{\epsilon}^{k}\\}_{k\in\mathcal{K}}$ satisfy (6b). Constraint
(6c) is satisfied because
$\|\boldsymbol{\epsilon}^{k}\|_{\ell}=\|\bar{\boldsymbol{\epsilon}}^{k}\|_{\ell}\leq\tau$
for all $k\in\bar{\mathcal{S}}=\\{k\,|\,\bar{u}_{k}=1\\}$. Constraint (6d) is
satisfied as we already know $\sum_{k=1}^{K}\bar{u}_{k}\geq\theta K$. As a
result,
$(\bar{\mathbf{v}},\bar{\mathbf{u}},\\{\boldsymbol{\epsilon}^{k}\\}_{k\in\mathcal{K}})$
is feasible for (6). Then, by Theorem 3.4, there must also exist a solution
$(\bar{\mathbf{c}},\\{{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\bar{\mathbf{y}},\bar{\mathcal{S}})$
feasible for $\mathbf{QIO}(\mathcal{K},\tau,\theta)$ where
$\bar{\mathbf{c}}\in\textup{cone}(\\{\mathbf{a}^{i}\\}_{i:\bar{v}_{i}=1})=\textup{cone}(\\{\mathbf{a}^{i}\\}_{i\in\bar{\mathcal{A}}})$,
as desired.

###### Proof 9.10

Proof of Proposition 4.6: Let $P(r,k)$ denote the optimization problem solved
in Line 5 of Algorithm 2 with respect to $\hat{\mathbf{x}}^{k}$, and
$(\mathbf{v}^{(r,k)},\boldsymbol{\epsilon}^{(r,k)})\in\underset{(\mathbf{v},\boldsymbol{\epsilon})}{\text{argmax}}\
P(r,k)$. We first show that there exists
$\bar{r}\leq\displaystyle\sum_{z=z^{*}}^{n}|\mathcal{V}_{z}|$ such that
$\mathbf{v}^{(\bar{r},1)}=\mathbf{v}^{*}$ for problem $P(\bar{r},1)$ (i.e.,
with respect to the first data point $\hat{\mathbf{x}}^{1}$). For each
iteration $r\geq 2$, each cut only prevents the solution found in the previous
iteration $r-1$, i.e., $\mathbf{v}^{(r-1,1)}$, from being feasible for
constraints (8b)–(8d). This means that $P(r,1)$ can be solved
$\displaystyle\sum_{z=1}^{n}|\mathcal{V}_{z}|$ times with iteratively added
cuts to collect all solutions satisfying (8b)–(8d) with respect to
$\hat{\mathbf{x}}^{1}$. Note that because
$(\mathbf{v}^{*},\boldsymbol{\epsilon}^{k*})$ satisfies (6b) for all
$k\in\mathcal{K}$ and $u^{*}_{1}=1$,
$(\mathbf{v}^{*},\boldsymbol{\epsilon}^{1*})$ satisfies constraints (8b)–(8d)
with respect to $\hat{\mathbf{x}}^{1}$. Thus, it is guaranteed that for some
$\bar{r}\leq\displaystyle\sum_{z=1}^{n}|\mathcal{V}_{z}|$ we have
$\mathbf{v}^{(\bar{r},1)}=\mathbf{v}^{*}$. Furthermore, because the value
function of $P(r,1)$ is non-increasing in $r$, for any
$r>\displaystyle\sum_{z=z^{*}}^{n}|\mathcal{V}_{z}|$ the optimal value of
$P(r,1)$ is less than $z^{*}$ and thus $\mathbf{v}^{*}$ is not achievable.
Therefore, $\bar{r}$ must be no greater than
$\displaystyle\sum_{z=z^{*}}^{n}|\mathcal{V}_{z}|$.

Next, we need to show that when $\mathbf{v}^{(\bar{r},1)}=\mathbf{v}^{*}$ at
iteration $\bar{r}$, the algorithm achieves $\mathbf{v}^{Alg}=\mathbf{v}^{*}$
and $z^{Alg}=z^{*}$. To do so, we first show that when
$\mathbf{v}^{(\bar{r},1)}=\mathbf{v}^{*}$, Lines 4–9 of the algorithm lead to
$\bar{\mathbf{D}}_{\bar{r}}$ with an all-one submatrix with $z^{*}$ columns
and at least $\lceil\theta K\rceil$ rows. Let
$\mathcal{I}^{*}=\\{i\in\mathcal{I}\,|\,v^{*}_{i}=1\\}$ and
$\mathcal{S}^{*}=\\{k\in\mathcal{K}\,|\,u^{*}_{k}=1\\}$. For some given $r$
and $k$, $P(r,k)$ has an optimal solution with $v_{i}^{(r,k)}=0$ if
$w^{k}_{i}=0$; also, based on how the weight parameters $\mathbf{w}^{k}$ are
updated (see Section 4.3), if $v_{i}^{(r,k)}=0$ for $k=1,\ldots,k^{\prime}-1$,
we have $w^{k^{\prime}}_{i}=0$. Generalizing this observation, if
$\mathbf{v}^{(\bar{r},1)}=\mathbf{v}^{*}$ then for all $k=2,\ldots,K$ we have
$w^{k}_{i}=0$ for all $i\in\mathcal{I}\setminus\mathcal{I}^{*}$ and
$w^{k}_{i}>0$ for all $i\in\mathcal{I}^{*}$, and thus the maximum of the
objective function of $P(\bar{r},k)$ for each $k$, i.e.,
${\mathbf{w}^{k}}^{\prime}\mathbf{v}$, can be obtained when
$\mathbf{v}=\mathbf{v}^{*}$. Because
$(\mathbf{v}^{*},\boldsymbol{\epsilon}^{k*})$ satisfies all constraints of
problem (8) as well as all cuts in $P(\bar{r},k)$ generated up to iteration
$\bar{r}$ for all $k\in\mathcal{S}^{*}$, we have
$(\mathbf{v}^{*},\boldsymbol{\epsilon}^{k*})\in\underset{\mathbf{v},\boldsymbol{\epsilon}}{\text{argmax}}\
P(\bar{r},k)$. This means if ${\mathbf{v}^{*}}^{\prime}$ is assigned to the
first row of $\bar{\mathbf{D}}_{\bar{r}}$, it is guaranteed that
${\mathbf{v}^{*}}^{\prime}$ will also be assigned to rows
$k\in\mathcal{S}^{*}$ of $\bar{\mathbf{D}}_{\bar{r}}$. Clearly, the submatrix
of this $\bar{\mathbf{D}}_{\bar{r}}$ with columns and rows corresponding to
$i\in\mathcal{I}^{*}$ and $k\in\mathcal{S}^{*}$, respectively, is all-one and
we have $|\mathcal{I}^{*}|=z^{*}$ and $|\mathcal{S}^{*}|\geq\theta K$. The
clique problem in Line 10 of the algorithm (also see formulation (14)) then
takes this $\bar{\mathbf{D}}_{\bar{r}}$ as input to return its optimal
solution $\bar{\mathbf{v}}^{\bar{r}}=\mathbf{v}^{*}$ with
${\bar{\mathbf{v}}^{r^{\prime}}}\mathbf{e}=z^{*}$. Since $z^{*}$ is the
maximum achievable value (it is the optimal value of the exact MQIO problem),
it satisfies the condition in Line 12 of Algorithm 2 and thus we have
$\mathbf{v}^{Alg}=\bar{\mathbf{v}}^{\bar{r}}=\mathbf{v}^{*}$ and
$z^{Alg}=z^{*}$.

Finally, we show that the stopping criterion is valid, i.e., the while loop
condition is not violated before $\mathbf{v}^{Alg}=\mathbf{v}^{*}$ is
observed. Consider a certain iteration
$\bar{r}\leq\displaystyle\sum_{z=z^{*}}^{n}|\mathcal{V}_{z}|$ and suppose we
have $\mathbf{v}^{Alg}\neq\mathbf{v}^{*}$ and $z^{Alg}<z^{*}$ at the end of
iteration $\bar{r}$ (i.e., Lines 13–14 of Algorithm 2). For the while loop
condition to be violated in the next iteration, i.e., iteration $\bar{r}+1$,
we must have $|\mathcal{G}_{\bar{r}+1}|<z^{Alg}<z^{*},$ which means
${\mathbf{e}}^{\prime}\mathbf{v}^{(\bar{r},1)}<z^{*}$. However, this cannot
happen because we showed earlier in this proof that for all
$r\leq\displaystyle\sum_{z=z^{*}}^{n}|\mathcal{V}_{z}|$ we have
${\mathbf{e}}^{\prime}\mathbf{v}^{(r,1)}\geq z^{*}$.

###### Proof 9.11

Proof of Proposition 7.1: Proposition 3.2 implies that given a solution
$(\bar{\mathbf{c}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\bar{\mathbf{y}},\bar{\mathcal{S}})$
feasible for (10),
$(\tilde{\mathbf{c}}=\mathbf{a}^{\tilde{i}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\tilde{\mathbf{y}}=\mathbf{e}_{\tilde{i}},\bar{\mathcal{S}})$
is also feasible for any $\tilde{i}\in\bar{\mathcal{I}}=\\{i\in\mathcal{I}\
\arrowvert\ \bar{y}_{i}>0\\}$. For an arbitrary
$\tilde{i}\in\bar{\mathcal{I}}$, consider the following formulation defined
for each $k\in\mathcal{K}$:

$\displaystyle\underset{\boldsymbol{\epsilon}^{k}}{\text{minimize}}\;\Big{\\{}\,\lVert\boldsymbol{\epsilon}^{k}\rVert_{\ell}\,\Big{|}\,\mathbf{A}(\mathbf{\hat{x}}^{k}-\boldsymbol{\epsilon}^{k})\geq\mathbf{b},\;{\mathbf{a}^{\tilde{i}}}^{\prime}(\mathbf{\hat{x}}^{k}-\boldsymbol{\epsilon}^{k})=b_{\tilde{i}}\Big{\\}}.$
(23)

Let $\tilde{\boldsymbol{\epsilon}}^{k}$ be the optimal solution to (23) for
each $k\in\mathcal{K}$ (here we suppress the index $\tilde{i}$ for brevity).
Note that a solution constructed as
$(\tilde{\mathbf{c}}=\mathbf{a}^{\tilde{i}},\\{\tilde{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\tilde{\mathbf{y}}=\mathbf{e}_{\tilde{i}},\bar{\mathcal{S}})$
is also feasible for (10) because
$\lVert\tilde{\boldsymbol{\epsilon}}^{k}\rVert_{\ell}\leq\lVert\bar{\boldsymbol{\epsilon}}^{k}\rVert_{\ell}\leq\tau$
for each $k\in\bar{\mathcal{S}}$. The objective of (10), i.e., minimizing
$\tau$, is equivalent to minimizing
$\underset{k\in\bar{\mathcal{S}}}{\max}\\{\lVert\boldsymbol{\epsilon}^{k}\rVert_{\ell}\\}$.
Because
$||\tilde{\boldsymbol{\epsilon}}^{k}||_{\ell}\leq||\bar{\boldsymbol{\epsilon}}^{k}||_{\ell}\leq\tau$
for each $k\in\bar{\mathcal{S}}$, we have
$\underset{k\in\bar{\mathcal{S}}}{\max}\\{\lVert\tilde{\boldsymbol{\epsilon}}^{k}\rVert_{\ell}\\}\leq\underset{k\in\bar{\mathcal{S}}}{\max}\\{\lVert\bar{\boldsymbol{\epsilon}}^{k}\rVert_{\ell}\\}$.
That is, for any given feasible solution
$(\bar{\mathbf{c}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\bar{\mathbf{y}},\bar{\mathcal{S}})$
for (10) where $\bar{\mathbf{c}}$ is not identical to $\mathbf{a}^{i}$ for any
$i\in\mathcal{I}$, we can always construct another feasible solution
$(\tilde{\mathbf{c}}=\mathbf{a}^{\tilde{i}},\\{\tilde{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\tilde{\mathbf{y}}=\mathbf{e}_{\tilde{i}},\bar{\mathcal{S}})$
without increasing the objective value of (10), which completes the proof.

###### Proof 9.12

Proof of Lemma 7.2: Let
$\hat{\mathcal{I}}=\\{i\in\mathcal{I}\,|\,\mathbf{a}^{i}\in\hat{\mathcal{C}}\\}$.
Given shifted data $\tilde{\mathcal{X}}$, assume $\mathbf{c}=\mathbf{a}^{i}$
is not inverse-feasible for QIO($\tilde{\mathcal{X}},\tau,\theta$) for any
$i\in\hat{\mathcal{I}}$. We want to show that there is no
$\mathbf{c}\in\hat{\mathcal{C}}$ that is inverse-feasible for
QIO($\tilde{\mathcal{X}},\tau,\theta$). Suppose to the contrary that there is
$\bar{\mathbf{c}}\in\hat{\mathcal{C}}$ feasible for
QIO($\tilde{\mathcal{X}},\tau,\theta$) and let $\bar{\mathcal{I}}$ be such
that
$\bar{\mathbf{c}}\in\textup{cone}(\\{\mathbf{a}^{i}\\}_{i\in\bar{\mathcal{I}}})$.
Then, from Proposition 3.2, there must be some $\bar{i}\in\bar{\mathcal{I}}$
such that $\mathbf{c}=\mathbf{a}^{\bar{i}}$ is also feasible for
QIO($\tilde{\mathcal{X}},\tau,\theta$). Furthermore, since
$\bar{\mathbf{c}}\in\hat{\mathcal{C}}$, this means that
$\mathbf{c}=\mathbf{a}^{\bar{i}}$ must be also feasible for
QIO($\hat{\mathcal{X}},\tau,\theta$) (i.e., it must be that
$\bar{i}\in\hat{\mathcal{I}}$), which is a contradiction.

###### Proof 9.13

Proof of Proposition 7.3: Since $\bar{\mathbf{c}}$ is a strict conic
combination of the selected $\mathbf{a}^{i}$ vectors, we have
$\mathcal{X}^{*}(\bar{\mathbf{c}})=\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}$.
For each $k\in\bar{\mathcal{S}}$, let
$\tilde{\mathbf{x}}^{k}\in\underset{\mathbf{x}\in\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}}{\text{argmin}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$.
Then, for all $k\in\bar{\mathcal{S}}$ and $i\in\bar{\mathcal{I}}$, we have
$\displaystyle\max_{\mathbf{x}\in\mathcal{X}_{i}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}\leq\|\tilde{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}+\displaystyle\max_{\mathbf{x}\in\mathcal{X}_{i}}\\{\|\tilde{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}\leq\|\tilde{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}+\rho_{i}$.
Hence, for each $k\in\bar{\mathcal{S}}$,

$\displaystyle\displaystyle\max_{\mathbf{x}\in\mathcal{X}^{*}(\bar{\mathbf{c}})}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$
$\displaystyle=\displaystyle\max_{\mathbf{x}\in\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}}\;\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}$
(24a)
$\displaystyle\leq\displaystyle\min_{i\in\bar{\mathcal{I}}}\;\big{\\{}\displaystyle\max_{\mathbf{x}\in\mathcal{X}_{i}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}\big{\\}}$
(24b)
$\displaystyle\leq\displaystyle\min_{i\in\bar{\mathcal{I}}}\;\big{\\{}\|\tilde{\mathbf{x}}^{k}-\hat{\mathbf{x}}^{k}\|_{\ell}+\rho_{i}\big{\\}}$
(24c)
$\displaystyle=\displaystyle\min_{i\in\bar{\mathcal{I}}}\;\big{\\{}\underset{\mathbf{x}\in\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}}{\text{min}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}+\rho_{i}\big{\\}},$
(24d)
$\displaystyle=\underset{\mathbf{x}\in\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}}{\text{min}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}+\displaystyle\min_{i\in\bar{\mathcal{I}}}\;\\{\rho_{i}\\},$
(24e)

where the first inequality holds because we have
$\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}\subseteq\mathcal{X}_{i}$
for all $i\in\bar{\mathcal{I}}$, which leads to
$\displaystyle\max_{\mathbf{x}\in\underset{i\in\bar{\mathcal{I}}}{\cap}\mathcal{X}_{i}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\}\leq\max_{\mathbf{x}\in\mathcal{X}_{i}}\\{\|\hat{\mathbf{x}}^{k}-\mathbf{x}\|_{\ell}\\},\forall
i\in\bar{\mathcal{I}}$.

###### Proof 9.14

Proof of Lemma 8.1: Because $\bar{\alpha}^{k}_{i}=0$ for all
$i\in\bar{\mathcal{I}}$ and
$(\bar{\boldsymbol{\alpha}}^{k},\bar{\boldsymbol{\epsilon}}^{k})$ is feasible
for (15), we have
${\mathbf{a}^{i}}^{\prime}(\mathbf{\hat{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k})=b_{i}$
for all $i\in\bar{\mathcal{I}}$,
${\mathbf{a}^{i}}^{\prime}(\mathbf{\hat{x}}^{k}-\bar{\boldsymbol{\epsilon}}^{k})\geq
b_{i}$ for all $i\in\mathcal{I}\setminus\bar{\mathcal{I}}$, and
$\rVert\bar{\boldsymbol{\epsilon}}^{k}\lVert_{\ell}\leq\tau$. Let
$\bar{v}_{i}^{k}=1-\bar{\alpha}_{i}^{k}$ for all $i\in\bar{\mathcal{I}}$ and
$\bar{v}_{i}^{k}=0$ otherwise. Clearly,
$(\bar{\mathbf{v}}^{k},\bar{\boldsymbol{\epsilon}}^{k})$ satisfies all
constraints of (8).

###### Proof 9.15

Proof of Proposition 8.2: Assume that $\tilde{\mathbf{D}}$ satisfies (16) and
has an all-one submatrix whose rows and columns correspond to
$\bar{\mathcal{S}}$ and $\bar{\mathcal{A}}$, respectively, where
$\bar{\mathcal{S}}\in\mathcal{K},|\bar{\mathcal{S}}|\geq\theta K$, and
$\bar{\mathcal{A}}\in\mathcal{I}$. By definition, for each $k\in\mathcal{K}$
there exists a feasible solution
$(\bar{\boldsymbol{\alpha}}^{k},\bar{\boldsymbol{\epsilon}}^{k})$ for (15)
with respect to $\hat{\mathbf{x}}^{k}$ where $\bar{\alpha}_{i}^{k}=0$ for all
$i\in\bar{\mathcal{A}}$ and $k\in\bar{\mathcal{S}}$, and
$\bar{\alpha}_{i}^{k}>0$ otherwise. This means that, by Lemma 8.1, for each
$k\in\mathcal{K}$ there exists a corresponding feasible solution
$(\bar{\mathbf{v}}^{k},\bar{\boldsymbol{\epsilon}}^{k})$ for (8) with respect
to $\hat{\mathbf{x}}^{k}$ where $\bar{v}_{i}^{k}=1$ for all
$i\in\bar{\mathcal{A}}$ and $k\in\bar{\mathcal{S}}$, and $\bar{v}_{i}^{k}=0$
otherwise. Construct a matrix $\bar{\mathbf{D}}\in\\{0,1\\}^{K\times m}$ such
that $\bar{\mathbf{D}}_{ki}=1$ if $\bar{v}_{i}^{k}=1$ and
$\bar{\mathbf{D}}_{ki}=0$ otherwise. Note that $\bar{\mathbf{D}}$ satisfies
(9) and has an all-one submatrix whose rows and columns correspond to
$\bar{\mathcal{S}}$ and $\bar{\mathcal{A}}$, respectively, where
$\bar{\mathcal{S}}\subseteq\mathcal{K}$, $|\bar{\mathcal{S}}|\geq\theta K$,
and $\bar{\mathcal{A}}\subseteq\mathcal{I}$. Thus, by Proposition 4.4, there
exists a solution
$(\bar{\mathbf{c}},\\{\bar{\boldsymbol{\epsilon}}^{k}\\}_{k\in\mathcal{K}},\bar{\mathbf{y}},\bar{\mathcal{S}})$
feasible for $\mathbf{QIO}(\mathcal{K},\tau,\theta)$ where
$\bar{\mathbf{c}}\in\textup{cone}(\\{\mathbf{a}^{i}\\}_{i\in\bar{\mathcal{A}}})$.

##  10 Supplemental Materials for the Numerical Results

###  10.1 The Diet Problem: Data

Food items and nutrient data per serving. Food Type Lower Upper 1 2 3 4 5 6 7
8 9 limit limit Energy (KCAL) 91.53 68.94 23.51 65.49 110.88 83.28 80.50 63.20
52.16 1800.00 2500.00 Total_Fat (g) 4.95 0.71 1.80 3.48 6.84 4.41 5.80 0.94
0.18 44.00 78.00 Carbohydrate (g) 6.89 12.16 0.25 0.00 5.44 4.68 0.56 11.42
13.59 220.00 330.00 Protein (g) 4.90 3.68 1.59 7.99 6.80 5.93 6.27 2.40 0.41
56.00 NA Fiber (g) 0.00 0.06 0.00 0.00 0.28 0.29 0.00 1.19 1.81 20.00 30.00
Vitamin C (mg) 0.01 1.76 0.00 0.00 0.17 0.16 0.00 0.02 11.19 90.00 2000.00
Vitamin B6 (mg) 0.06 0.03 0.01 0.09 0.11 0.06 0.06 0.03 0.10 1.30 100.00
Vitamin B12 (mcg) 0.67 0.39 0.09 0.65 0.11 0.63 0.56 0.00 0.00 2.40 NA Calcium
(mg) 172.09 125.72 46.24 2.21 5.90 15.03 29.00 27.21 6.14 1000.00 2500.00 Iron
(mg) 0.05 0.08 0.04 0.75 0.35 0.35 0.73 0.79 0.13 8.00 45.00 Copper (mg) 0.02
0.04 0.01 0.03 0.03 0.03 0.04 0.05 0.06 0.90 10.00 Sodium (mg) 61.02 48.24
65.08 72.32 211.05 128.27 223.50 125.62 1.42 1500.00 2300.00 Vitamin A (mcg)
42.89 22.24 12.78 0.00 1.33 9.53 81.00 0.01 13.04 900.00 3000.00 Max serving 4
8 4 5 5 5 4 4 8

###  10.2 The Transshipment Problem: Problem Description and Additional
Numerical Results

Figure 7 and the following formulation show the transshipment problem we
consider.

$\displaystyle\underset{\mathbf{x}^{(p)},\mathbf{x}^{(t)}}{\text{minimize}}$
$\displaystyle\quad\sum_{i\in\mathcal{N}_{s}}c^{(p)}_{i}x_{i}^{(p)}+\sum_{i\in\mathcal{N}}\sum_{j\in\mathcal{N}}c^{(t)}_{ij}x_{ij}^{(t)}$
(25a) subject to
$\displaystyle\quad\sum_{j\in\mathcal{N}\setminus\mathcal{N}_{s}}x_{ij}^{(t)}=x_{i}^{(p)},\quad\forall
i\in\mathcal{N}_{s},$ (25b)
$\displaystyle\quad\sum_{i\in\mathcal{N}\setminus\mathcal{N}_{d}}x_{ij}^{(t)}=d_{j},\quad\forall
j\in\mathcal{N}_{d},$ (25c)
$\displaystyle\quad\sum_{j\in\mathcal{N}}x_{ij}^{(t)}-\sum_{j\in\mathcal{N}}x_{ji}^{(t)}=0,\quad\forall
i\in\mathcal{N}_{t},$ (25d) $\displaystyle\quad 0\leq
x_{i}^{(p)}\leq\pi^{(p)}_{i},0\leq x_{ij}^{(t)}\leq\pi^{(t)}_{ij},\quad\forall
i,j\in\mathcal{N},$ (25e)

where $\mathcal{N}_{s}$, $\mathcal{N}_{d}$, and $\mathcal{N}_{t}$ denote the
set of supply, demand, and transshipment nodes, respectively, and
$\mathcal{N}$ denotes the set of all nodes. Variables $\mathbf{x}^{(p)}$ and
$\mathbf{x}^{(t)}$ denote the production level at each supply node and
transshipment flow on each arc, respectively. Parameters
$\boldsymbol{\pi}^{(t)}$ and $\boldsymbol{\pi}^{(p)}$ represent the arc
capacity and production capacity, respectively.

$1$$3$$2$$4$$5$$x_{1}^{(p)}$$x_{2}^{(p)}$$x_{14}^{(t)}$$x_{13}^{(t)}$$x_{23}^{(t)}$$x_{25}^{(t)}$$x_{34}^{(t)}$$x_{35}^{(t)}$$d_{4}$$d_{5}$

Figure 7: Network for the transshipment example (Dong et al. 2018). Nodes 1
and 2 are supply nodes and 4 and 5 are demand nodes. The capacity of each arc
is 1.3 and production capacities are 3 and 1.5 for nodes 1 and 2,
respectively. The true production costs are $c_{1}^{(p)}=0.2393$ and
$c_{2}^{(p)}=0.1496$ and true transshipment costs are $c_{13}^{(t)}=0.0935$,
$c_{14}^{(t)}=0.1232$, $c_{23}^{(t)}=0.1141$, $c_{25}^{(t)}=0.0320$,
$c_{34}^{(t)}=0.1615$, and $c_{35}^{(t)}=0.0867$.

In addition to the numerical results presented in Section 5.4, we also compare
the objective function values achieved by our forward solution
$\bar{\mathbf{x}}^{t}$ (recall that
$\mathbf{x}=[{\mathbf{x}^{(p)}};{\mathbf{x}^{(t)}}]$ and
$\mathbf{c}=[{\mathbf{c}^{(p)}};{\mathbf{c}^{(t)}}]$) and that from the given
data. We adopt the metrics from the previous study on online inverse LP
(Bärmann et al. 2017); this study assumes a single noiseless (i.e., optimal)
decision at each time point and shows that both
$1/T\sum_{t=1}^{T}{\mathbf{c}^{true}}^{\prime}(\bar{\mathbf{x}}^{t}-\hat{\mathbf{x}}^{t})$
and
$1/T\sum_{t=1}^{T}{\mathbf{c}^{t}}^{\prime}(\bar{\mathbf{x}}^{t}-\hat{\mathbf{x}}^{t})$
converge to zero as $T\rightarrow\infty$. In our case, because we consider
batches of data at each time we use the following modified metrics:
$1/T\big{[}\sum_{t=1}^{T}\sum_{k=1}^{K_{t}}{\mathbf{c}^{true}}^{\prime}(\bar{\mathbf{x}}^{t}-\hat{\mathbf{x}}^{k})/K_{t}\big{]}$
and
$1/T\big{[}\sum_{t=1}^{T}\sum_{k=1}^{K_{t}}{\mathbf{c}^{t}}^{\prime}(\bar{\mathbf{x}}^{t}-\hat{\mathbf{x}}^{k})/K_{t}\big{]}$.
Note that $\mathbf{c}^{t}$ is a cost vector randomly selected from the inverse
set at time $t$. Figure 8 shows these metrics achieved by our algorithm with
noisy datasets at each iteration. Both metrics averaged over the data points
also converge; however, neither of them reaches 0 because of the noise in the
data.

(a) Average cumulative error under $\mathbf{c}^{true}$.

(b) Average cumulative error under $\mathbf{c}^{t}\in\mathcal{C}_{t}$.

Figure 8: Convergence of average cumulative objective function errors.

## References

  * Abbeel and Ng (2004) Abbeel P, Ng AY (2004) Apprenticeship learning via inverse reinforcement learning. _Proceedings of the 21st International Conference on Machine Learning (ICML 2004)_ , 1–8.
  * Ahuja and Orlin (2001) Ahuja RK, Orlin JB (2001) Inverse optimization. _Operations Research_ 49(5):771–783.
  * Aswani et al. (2018) Aswani A, Shen ZJ, Siddiq A (2018) Inverse optimization with noisy data. _Operations Research_ 66(3):870–892.
  * Aswani et al. (2019) Aswani A, Shen ZJM, Siddiq A (2019) Data-driven incentive design in the Medicare Shared Savings Program. _Operations Research_ 67(4):1002–1026.
  * Babier et al. (2018) Babier A, Chan TC, Lee T, Mahmood R, Terekhov D (2018) An ensemble learning framework for model fitting and evaluation in inverse linear optimization. _arXiv preprint arXiv:1804.04576_ .
  * Bärmann et al. (2017) Bärmann A, Pokutta S, Schneider O (2017) Emulating the expert: Inverse optimization through online learning. _Proceedings of the 34th International Conference on Machine Learning (ICML 2017)_ , volume 70, 400–410.
  * Bertsimas et al. (2012) Bertsimas D, Gupta V, Paschalidis IC (2012) Inverse optimization: A new perspective on the Black-Litterman model. _Operations Research_ 60(6):1389–1403.
  * Bertsimas et al. (2015) Bertsimas D, Gupta V, Paschalidis IC (2015) Data-driven estimation in equilibrium using inverse optimization. _Mathematical Programming_ 153(2):595–633.
  * Bertsimas and Mazumder (2014) Bertsimas D, Mazumder R (2014) Least quantile regression via modern optimization. _The Annals of Statistics_ 42(6):2494–2525.
  * Birge et al. (2017) Birge JR, Hortaçsu A, Pavlin JM (2017) Inverse optimization for the recovery of market structure from market outcomes: An application to the MISO electricity market. _Operations Research_ 65(4):837–855.
  * Boutilier et al. (2015) Boutilier JJ, Lee T, Craig T, Sharpe MB, Chan TC (2015) Models for predicting objective function weights in prostate cancer IMRT. _Medical Physics_ 42(4):1586–1595.
  * Candes et al. (2008) Candes EJ, Wakin MB, Boyd SP (2008) Enhancing sparsity by reweighted $\ell_{1}$ minimization. _Journal of Fourier Analysis and Applications_ 14(5-6):877–905.
  * Chan et al. (2014) Chan TC, Craig T, Lee T, Sharpe MB (2014) Generalized inverse multiobjective optimization with application to cancer therapy. _Operations Research_ 62(3):680–695.
  * Chan and Lee (2018) Chan TC, Lee T (2018) Trade-off preservation in inverse multi-objective convex optimization. _European Journal of Operational Research_ 270(1):25–39.
  * Chan et al. (2019) Chan TC, Lee T, Terekhov D (2019) Inverse optimization: Closed-form solutions, geometry and goodness of fit. _Management Science_ 65(3):680–695.
  * Darmon et al. (2006) Darmon N, Ferguson EL, Briend A (2006) Impact of a cost constraint on nutritionally adequate food choices for French women: An analysis by linear programming. _Journal of Nutrition Education and Behavior_ 38(2):82–90.
  * Dawande et al. (2001) Dawande M, Keskinocak P, Swaminathan JM, Tayur S (2001) On bipartite and multipartite clique problems. _Journal of Algorithms_ 41(2):388–403.
  * Dong et al. (2018) Dong C, Chen Y, Zeng B (2018) Generalized inverse optimization through online learning. _Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS 2018)_ , 86–95.
  * Erkin et al. (2010) Erkin Z, Bailey MD, Maillart LM, Schaefer AJ, Roberts MS (2010) Eliciting patients’ revealed preferences: An inverse Markov decision process approach. _Decision Analysis_ 7(4):358–365.
  * Esfahani et al. (2018) Esfahani PM, Shafieezadeh-Abadeh S, Hanasusanto GA, Kuhn D (2018) Data-driven inverse optimization with imperfect information. _Mathematical Programming_ 167(1):191–234.
  * Ghate (2015) Ghate A (2015) Inverse optimization in countably infinite linear programs. _Operations Research Letters_ 43(3):231–235.
  * Ghobadi et al. (2018) Ghobadi K, Lee T, Mahmoudzadeh H, Terekhov D (2018) Robust inverse optimization. _Operations Research Letters_ 46(3):339–344.
  * Gurobi Optimization (2020) Gurobi Optimization L (2020) Gurobi optimizer reference manual. URL http://www.gurobi.com.
  * Heuberger (2004) Heuberger C (2004) Inverse combinatorial optimization: A survey on problems, methods, and results. _Journal of Combinatorial Optimization_ 8(3):329–361.
  * Hubert et al. (2008) Hubert M, Rousseeuw PJ, Van Aelst S (2008) High-breakdown robust multivariate methods. _Statistical Science_ 23(1):92–119.
  * Iyengar and Kang (2005) Iyengar G, Kang W (2005) Inverse conic programming with applications. _Operations Research Letters_ 33(3):319–330.
  * Keshavarz et al. (2011) Keshavarz A, Wang Y, Boyd S (2011) Imputing a convex objective function. _2011 IEEE International Symposium on Intelligent Control_ , 613–619 (IEEE).
  * Koenker and Hallock (2001) Koenker R, Hallock KF (2001) Quantile regression. _Journal of Economic Perspectives_ 15(4):143–156.
  * Lamperski and Schaefer (2015) Lamperski JB, Schaefer AJ (2015) A polyhedral characterization of the inverse-feasible region of a mixed-integer program. _Operations Research Letters_ 43(6):575–578.
  * Lee et al. (2013) Lee T, Hammad M, Chan TC, Craig T, Sharpe MB (2013) Predicting objective function weights from patient anatomy in prostate IMRT treatment planning. _Medical Physics_ 40(12):121706 (9pp.).
  * Mangasarian (1979) Mangasarian O (1979) Uniqueness of solution in linear programming. _Linear Algebra and its Applications_ 25:151–162.
  * Naghavi et al. (2019) Naghavi M, Foroughi AA, Zarepisheh M (2019) Inverse optimization for multi-objective linear programming. _Optimization Letters_ 13(2):281–294.
  * Perignon et al. (2016) Perignon M, Masset G, Ferrari G, Barré T, Vieux F, Maillot M, Amiot MJ, Darmon N (2016) How low can dietary greenhouse gas emissions be reduced without impairing nutritional adequacy, affordability and acceptability of the diet? A modelling study to guide sustainable food choices. _Public Health Nutrition_ 19(14):2662–2674.
  * Rousseeuw (1984) Rousseeuw PJ (1984) Least median of squares regression. _Journal of the American Statistical Association_ 79(388):871–880.
  * Rousseeuw and Van Driessen (2006) Rousseeuw PJ, Van Driessen K (2006) Computing LTS regression for large data sets. _Data Mining and Knowledge Discovery_ 12:29–45.
  * Saez-Gallego and Morales (2017) Saez-Gallego J, Morales JM (2017) Short-term forecasting of price-responsive loads using inverse optimization. _IEEE Transactions on Smart Grid_ 9(5):4805–4814.
  * Schaefer (2009) Schaefer AJ (2009) Inverse integer programming. _Optimization Letters_ 3(4):483–489.
  * Tavaslıoğlu et al. (2018) Tavaslıoğlu O, Lee T, Valeva S, Schaefer AJ (2018) On the structure of the inverse-feasible region of a linear program. _Operations Research Letters_ 46(1):147–152.
  * Troutt et al. (2008) Troutt MD, Brandyberry AA, Sohn C, Tadisina SK (2008) Linear programming system identification: The general nonnegative parameters case. _European Journal of Operational Research_ 185(1):63–75.
  * Wang (2009) Wang L (2009) Cutting plane algorithms for the inverse mixed integer linear programming problem. _Operations Research Letters_ 37(2):114–116.
  * Xavier (2012) Xavier EC (2012) A note on a maximum k-subset intersection problem. _Information Processing Letters_ 112(12):471–472.
  * Yohai (1987) Yohai VJ (1987) High breakdown-point and high efficiency robust estimates for regression. _The Annals of Statistics_ 15(2):642–656.