# CoAnnotating: Uncertainty-Guided Work Allocation between
Human and Large Language Models for Data Annotation

Minzhi Li †§ Taiwei Shi ‡ Caleb Ziems ¶
Min-Yen Kan † Nancy F. Chen § Zhengyuan Liu § Diyi Yang ¶
†National University of Singapore §Institute for Infocomm Research (I2R),
A*STAR
‡University of Southern California ¶Stanford University
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Annotated data plays a critical role in Natural Language Processing (NLP) in
training models and evaluating their performance. Given recent developments in
Large Language Models (LLMs), models such as ChatGPT demonstrate zero-shot
capability on many text-annotation tasks, comparable with or even exceeding
human annotators. Such LLMs can serve as alternatives for manual annotation,
due to lower costs and higher scalability. However, limited work has leveraged
LLMs as complementary annotators, nor explored how annotation work is best
allocated among humans and LLMs to achieve both quality and cost objectives.
We propose CoAnnotating, a novel paradigm for Human-LLM co-annotation of
unstructured texts at scale. Under this framework, we utilize uncertainty to
estimate LLMs’ annotation capability. Our empirical study shows CoAnnotating
to be an effective means to allocate work from results on different datasets,
with up to 21% performance improvement over random baseline. For code
implementation, see https://github.com/SALT-NLP/CoAnnotating.

##  1 Introduction

Labeled data plays a critical role in establishing benchmarks and developing
models for Natural Language Processing (NLP). Although Large Language Models
(LLMs) like ChatGPT have demonstrated their strong zero-shot performance in
various tasks such as question answering, reasoning, natural language
inference, sentiment analysis, and named entity recognition, results obtained
by fine-tuned language models still outperform LLMs on most of these tasks
(Qin et al., 2023; Zhong et al., 2023; Ziems et al., 2023). Therefore,
collecting labeled data for model training and fine-tuning is still valuable.
Instead of deploying LLMs directly for downstream uses, it is worthwhile to
investigate how researchers can leverage LLMs’ zero-shot capability in
labeling text data to construct high-quality datasets and improve the
performance of fine-tuned models.

Figure 1: CoAnnotating framework. It differs from previous work by considering
how to allocate data within the same dataset to humans and ChatGPT by
obtaining responses from ChatGPT using different variations of prompts and
estimating ChatGPT’s annotation expertise with the use of uncertainty metrics
such as entropy.

Typically, researchers recruit human annotators such as experts or crowd
workers to perform data annotation (Kittur et al., 2008; Snow et al., 2008).
Some challenges in manual annotation includes high costs of recruiting and
training annotators, annotation inconsistency and human subjectivity (Lingren
et al., 2014; Grosman et al., 2020). Recent work explored how LLMs perform
relative to crowd workers (Ding et al., 2022) and results showed that it is
possible for LLMs like ChatGPT to replace large-scale manual annotation (Huang
et al., 2023; Kuzman et al., 2023). In some cases, LLMs’ annotation quality
even outperforms human annotators on certain tasks (Gilardi et al., 2023).
Given the much lower annotation cost than crowd workers, LLMs are considered
to have great potential to increase the cost efficiency of the data annotation
process. However, some studies also show that, relative to human performance,
LLMs’ zero-shot performance falls short on more difficult and pragmatic tasks
(Wang et al., 2021; Kocoń et al., 2023). They suggest that practitioners
should use caution when using LLMs to annotate data (Reiss, 2023; Huang et
al., 2023). Such prior works view humans and LLMs as competitors, measuring
the accuracy of LLM labels as a replacement for human annotation, rather than
considering how humans and LLMs might collaborate in an efficient manner. It
is Human-LLM collaboration that motivates this work. We propose the
CoAnnotating framework, which aims to balance the complementary profiles of
humans and LLMs in terms of their respective annotation quality and cost. Our
work tackles the problem of Human-LLM co-annotation from a _resource
allocation_ perspective. Following Gentile et al. (2022), Diao et al. (2023)
and Wang et al. (2021), we consider model confidence as a reliable signal for
the model’s expected performance. As we consider allocating a given datapoint
for an LLM to annotate, we can use the inverse of the model’s uncertainty to
estimate our confidence in that allocation. Under CoAnnotating, we quantify
LLMs’ annotating expertise on the instance-level (estimating how well LLMs can
annotate the given data point) beyond task-level (evaluating how LLMs performs
on overall for each dataset). As such, a more informed allocation decision can
be made with this fine-grained and contextualized instance-level perspective,
rather than broad and coarse dataset-level expertise.

We show that our proposed method using the uncertainty of responses can
achieve a more efficient and more accurate work allocation than the random
allocation baseline. Our results also show that confidence scores generated by
LLMs are generally well-calibrated but not always reliable. It is possible to
outsource some annotation work to achieve human-level performance for more
straightforward tasks like topic understanding. On the other hand, a tradeoff
between annotation quality and annotation cost is inevitable for more nuanced
tasks. Our framework establishes a guide to effectively allocate AI and human
efforts in collaborative annotation, and in doing so, it provides key insights
into the capacities of LLMs, as well as the nature of the tasks and data that
remain outside these capacities.

##  2 Related Work

###  2.1 Weak Supervision

In a traditional supervised learning setting, every training data point is
labeled by human annotators. However, acquiring manually annotated labels for
training data can be prohibitively costly and time-consuming. Weak supervision
helps to address the challenge using partially and imperfectly labeled data
for training (Zhang et al., 2022). Weak supervision techniques obtain these
noisy labels by tapping into heuristics (Ratner et al., 2017; Meng et al.,
2018; Awasthi et al., 2020), feature annotation (Mann and McCallum, 2010),
external knowledge bases (Hoffmann et al., 2011; Min et al., 2013), pretrained
models (Bach et al., 2019; Zhang et al., 2021) and third-party tools (Lison et
al., 2020). Moreover, weak supervision can be combined with the active
learning framework (Gonsior et al., 2020) to select the most informative data
to be annotated by humans and utilize weak supervision to decide noisy labels.
Given LLMs’ stunning zero-shot capabilities, our work explores the possibility
of using them as a more efficient labeling source, thus freeing up resources
to be reinvested in the research pipeline.

###  2.2 LLMs for Annotation

Most prior works frame the decision for human or LLM annotation as one of
competition rather than collaboration between these modes. These show that
LLMs like GPT-3 davinci-003 have strong zero-shot sentiment analysis
performance (Ding et al., 2022). ChatGPT (gpt-3.5-turbo) performs surprisingly
well on automatic genre detection in under-resourced languages like Slovenian
(Kuzman et al., 2023). ChatGPT can even achieve high accuracy on some of the
most nuanced tasks like implicit hate speech detection (Huang et al., 2023).
Similarly, GPT-4 is able to annotate texts that require reasoning and
contextual knowledge and provide explanations that could facilitate
interpretive research (Törnberg, 2023). These results show the great potential
of LLMs as data annotation tools with just simple prompt design and without
much manual labeling efforts (Kuzman et al., 2023).

However, there is still room to close significant performance gaps between
LLMs’ performance and existing fine-tuned baselines on some challenging tasks.
LLMs struggle with named entity recognition (Ding et al., 2022; Qin et al.,
2023), relational reasoning (Bang et al., 2023), affective tasks (Kocoń et
al., 2023; Amin et al., 2023) and semantic similarity tasks (Kocmi and
Federmann, 2023; Wang et al., 2023). Moreover, it does not outperform fine-
tuned baselines for generation tasks like question answering and text
summarization (Tan et al., 2023; Wang et al., 2023). These works all take the
perspective that LLMs and humans are competitors, making task-level
comparisons between LLMs and humans/fine-tuned models for each dataset. Our
work views LLMs and humans as potential collaborators, with the possibility to
work with each other to annotate the same dataset.

###  2.3 Human-Machine Collaboration for Dataset Creation

The quality of the dataset and the cost of creating a dataset are two
important but sometimes conflicting objectives in dataset creation. Previous
work suggests a human-AI collaborative framework that utilizes language
models’ generation capability and human revision and evaluation skills
(Tekiroglu et al., 2020; Yuan et al., 2021; Bartolo et al., 2021; Liu et al.,
2022) to create valuable datasets of high quality. For cost efficiency, some
have proposed averaging or majority vote over human and machine outputs
(Chaganty et al., 2018; Ziems et al., 2023) and some initial empirical
explorations such as analyzing the random combination of distillation of LLM
and manual annotation (Kang et al., 2023) as well as active labeling
assignments via the logit outputs (Wang et al., 2021). Our framework takes
both quality and cost into consideration by using uncertainty metrics to make
informed human-AI work-allocation decisions to ensure cost efficiency without
compromising quality.

##  3 CoAnnotating Framework

Figure 2: Workflow of CoAnnotating. The framework consists of uncertainty-
guided expertise estimation, work allocation, and cost performance Pareto
analysis. With insights gained from Pareto analysis on the pilot dataset,
uncertainty-guided work allocation can be applied on the original unlabeled
dataset to achieve greater cost efficiency.

Our CoAnnotating framework sets up a guide for annotating text data
collaboratively (Figure 2). For a given unlabeled train dataset
$D_{t}=\\{t_{1},t_{2},...t_{m}\\}$ where $t_{i}$ is the i-th instance in the
dataset, our framework automatically decides whether each data instance should
be annotated by human or by the LLMs (Section 3.3) by computing the
uncertainty level of the LLMs’s annotations for each instance (Section 3.2),
with the goal of achieving a higher annotation quality and a lower annotation
cost for a given dataset (Section 3.4).

###  3.1 Prompt Construction

Previous work shows that LLMs’ performance can be highly sensitive to
perturbations in input (Jang and Lukasiewicz, 2023). Therefore, we introduce a
set of diverse types of prompts $P_{i}=\\{p_{i1},p_{i2},...,p_{ik}\\}$ for
each instance $t_{i}$. Besides the (1) basic instruction format, we vary the
prompts by swapping its sequence of sentences (2; symmetric perturbation),
paraphrasing the instruction (3; semantic perturbation), enquiring in various
question formats (4; True/False, 5; Textual Short Responses 6; Multiple Choice
Question) and asking with confirmation bias (7; negation perturbation).

| Text = Sentence1: {sentence1}
---
Sentence2: {sentence2}
Prompt |  Type
Please label if the following two sentences are paraphrases of each other. Please give your answer as “paraphrase” or “not paraphrase”. {Text} |  Instruction
{Text} Please label if the two sentences above are paraphrases of each other. Please give your answer as “paraphrase” or “not paraphrase”. |  Sequence Swapping
Given the following two sentences, please classify the relationship of the following two sentences as “paraphrase” or “not paraphrase”. {Text} |  Paraphrase
Is it true that the following two sentences are/are not paraphrases of each other? Give your answer as “true” or “false”. {Text} |  True/False
What relationship do the following two sentences have? Is it “paraphrase” or “not paraphrase”? {Text} |  Question Answering
Please choose one option that best describes the relationship between the following two sentences. {Text} (A) Paraphrase (B) Not paraphrase |  Multiple Choice Question
I think the following two sentences are/are not paraphrases of each other. Do you agree? {Text} |  Question with Confirmation Bias

Table 1: Examples of our 7 designed prompt types asking ChatGPT to annotate
each instance for the concrete task of paraphrase detection.

###  3.2 Uncertainty Computation

In a real-world setting, there is no gold data on which to gauge the model’s
expected accuracy and thus decide on the optimal annotation strategy.=
However, model confidence can serve as a reliable signal for model performance
(Gentile et al., 2022; Diao et al., 2023; Wang et al., 2021). Therefore we
compute the LLM uncertainty $u_{i}$ to guide the work-allocation process. We
compute $u_{i}$ in two ways which are easy to implement and have proven
effectiveness in previous literature (Diao et al., 2023):= (1) self-evaluation
and (2) entropy. In each case, for $t_{i}$ by prompting LLMs $k$ times with
different prompts in $P_{i}$ we get $k$ annotations
$A_{i}=\\{a_{i1},a_{i2},...,a_{ik}\\}$ for each instance. As an ablation study
(5.4), we also prompt LLMs k times with the same prompt to get $k$ annotations
to study the effect of prompt perturbations.

#### Self-Evaluation.

Previous work shows that LLMs are well calibrated and can provide information
about their uncertainty themselves (Wang et al., 2021; Kadavath et al., 2022;
Diao et al., 2023). We ask the model to directly output its confidence score
(Lin et al., 2022) by postpending the phrase "and please give a confidence
score on a scale of 0 to 1 for your prediction". The uncertainty for $t_{i}$
is calculated by:

$u_{i}=1-\frac{1}{k}\sum_{j=1}^{k}P_{\theta}(a_{ij}|p_{ij})$

where $P_{\theta}(a_{ij}|p_{ij})$ is the probability of a class label being
annotated by ChatGPT given the prompt $p_{ij}$. We obtain its value by
extracting the confidence score provided by LLMs directly.

#### Entropy.

Entropy is a measure of the impurity in a set of data and can be used to
quantify the uncertainty associated with the class labels. The larger the
entropy value, the more uncertain the responses are. We can use this metric to
estimate the uncertainty level:

$u_{i}=-\sum_{j=1}^{k}P_{\theta}(a_{ij}|p_{ij})\ln P_{\theta}(a_{ij}|p_{ij})$

where $P_{\theta}(a_{ij}|p_{ij})$ is calculated as the frequency of a certain
prediction among all predictions.

###  3.3 Work Allocation Strategies

Building upon the aforementioned uncertainty level estimation, we can then use
the uncertainty level $u_{i}$ to guide the work allocation.

#### Random Allocation.

Random allocation is chosen as a baseline strategy for comparison. This is the
strategy that randomly samples $n$ instances ($0\leq n\leq m$) in $D_{t}$ to
be annotated by LLMs while the remaining $m-n$ data is annotated by humans.

#### Self-Evaluation Guided Allocation.

Wang et al. (2021) introduces an active label assignment approach that ranks
outputs by their logits. Not all LLM APIs support this computation, so we
modify this baseline with our self-evaluation approach, sorting instances by
the self-reported confidence scores in decreasing order. We then select the
top $n$ instances ($0\leq n\leq m$) in $D_{t}$ with the lowest level of
uncertainty as the best candidates for LLM annotation. The remaining $m-n$
data points are allocated to human annotators.

#### Entropy Guided Allocation.

It is not possible to entirely ensure the reliability of black box LLMs self-
reported confidence. Therefore, we also propose the use of entropy across
LLMs’ responses to gauge their certainty and reliability. We sort the
instances by their respective entropy values in increasing order and select
the top $n$ instances ($0\leq n\leq m$) in $D_{t}$ with the lowest level of
uncertainty to be annotated by LLMs. Again, the remaining $m-n$ data points
with inconsistent responses will be allocated for human annotation.

###  3.4 Strategy Selection

We frame the co-annotation process as a multi-objective optimization problem
with two main objectives, maximizing annotation quality and minimizing
annotation cost. We can determine annotation quality by the classification
performance of a model fine-tuned using a certain co-annotation strategy. The
total annotation cost is the sum of manual annotation costs and those incurred
by the LLM. Inspired by Kang et al. (2023), we apply the Pareto efficiency
concept in strategy selection. Here, the Pareto efficient scenario refers to
the situation where it is impossible to increase the classification
performance of the fine-tuned model without incurring a higher annotation
cost. By adopting different allocation strategies and setting different
proportions of data allocated to LLMs, we get various allocation patterns with
different annotation qualities and costs. We can then plot the performances of
each quality-cost combination and approximate the Pareto frontier by
interpolating the discrete data points Abdolrashidi et al. (2021); Treviso et
al. (2022). Practitioners can plot annotation quality against the cost for
pilot data to gain a better understanding of this tradeoff, and they can use
the Pareto efficient points to decide which ratio of data they should
outsource to LLMs at their desired budget level.

##  4 Experiments

###  4.1 Datasets

We use six classification datasets for different types of tasks. Since LLM
inference costs much less than a human salary, we know the simple allocation
decision is to choose LLMs over humans whenever an LLM achieves a utility
greater than or equal to that of human annotators. For a more challenging
setting, we identify tasks in which LLMs are known to struggle with
discriminating the underlying constructs (Pikuliak, 2023; Wang et al., 2021).
In such cases, there is a tradeoff between annotation quality and annotation
cost and CoAnnotating facilitates better decision-making in such contexts. If
the size of the train data is too large, we will take a stratified random
sampling for approximately 1000 samples.

#### Topic Classification

is a challenging task for large pretrained language models like GPT-3 (Wang et
al., 2021). We choose two representative datasets: TREC (Li and Roth, 2002)
and AG News (Zhang et al., 2015). AG News contains news titles and their
descriptions, which were gathered by an academic news search engine, and which
span four topics:  world, sports, business, and science/technology. TREC
contains of English questions with six manually labeled class labels:
abbreviation; entity; description and abstract concept; human being; location;
and numeric value.

#### Semantic Similarity

is known to challenge ChatGPT (Jang and Lukasiewicz, 2023). We select MRPC
(Dolan and Brockett, 2005) and TempoWiC (Loureiro et al., 2022) as two
representative datasets for semantic similarity understanding. MRPC is a
corpus of sentence pairs extracted from online news and annotated by humans
for whether the sentences are semantically equivalent. TempoWiC contains
annotated tweet pairs for whether there is a meaning shift of the target word.

#### Nuanced Comprehension

We also experiment with Tweet Stance Detection (Mohammad et al., 2016a) and
Conversation Gone Awry (Zhang et al., 2018) to explore the collaboration
paradigm on tasks requiring more nuanced comprehension. Tweet Stance Detection
in SemEval-2016 (Mohammad et al., 2016b) is a dataset of tweets annotated with
the author’s stance (favorable, neutral, and negative) toward a certain topic
and we select the topic of abortion.

Figure 3: Distribution of entropy and confidence values. Figure 4: Scatter
plots of the average alignment of ChatGPT’s annotation with human annotation
for train data against the threshold. We vary the threshold for different
metrics during work allocation to investigate the effectiveness of different
metrics in quantifying ChatGPT’s annotation capability.

###  4.2 LLM Annotation

We obtain responses from ChatGPT (gpt-3.5-turbo) due to its high-quality
annotations and low inference cost (Kuzman et al., 2023) using different
prompts carefully crafted in Table 1. If the response is an ambiguous answer
such as "I cannot determine the class of the text", we encode it as a new
class label which can result in higher uncertainty metrics. The uncertainty
computation decides whether annotation will be finally allocated to ChatGPT,
and if so, we decide the final label with a majority vote across ChatGPT’s
generations (Wang et al., 2022).

###  4.3 Evaluation

To evaluate the quality of datasets annotated with different strategies, we
fine-tune the same RoBERTa base classifier and calculate macro F1 scores on
test data for a fair comparison. We report macro F1 as a more accurate
representation of the performance due to the unbalanced nature of LLMs’
annotations for some datasets.

In terms of cost, we only consider monetary cost in this work. We calculate
human annotation costs based on what was reported in the dataset paper. If the
information is not applicable, we assume each instance is annotated by 5
independent annotators with a wage of $\$15/$hour. We calculate ChatGPT
annotation cost using the product of the token length of the input prompt and
the price of calling API for (gpt-3.5-turbo) ($\$0.002/1k$ tokens) at the time
of experimentation.

##  5 Results

| AGNews | TREC | Stance Detection
---|---|---|---
% ChatGPT | $0$ | $20$ | $40$ | $60$ | $80$ | 100 | $0$ | 20 | 40 | 60 | 80 | 100 | $0$ | 20 | 40 | 60 | 80 | $100$
Strategies | Macro F1
$Random$ | $88.2$ | $87.9$ | $85.8$ | $79.8$ | $81.8$ | 82.6 | $92.1$ | $88.1$ | $86.1$ | $81.6$ | $76.4$ | 75.8 | $60.2$ | $53.9$ | $53.6$ | $55.0$ | $50.4$ | 53.6
$Self-Evaluation$ | $88.2$ | $86.0$ | $84.9$ | $84.1^{*}$ | $82.1$ | 82.1 | $92.1$ | $91.5$ | $87.2$ | $\textbf{86.5}^{*}$ | $76.4$ | 74.3 | $60.2$ | $56.9$ | $54.8$ | $54.4$ | $52.8$ | $52.9$
$Entropy(Diff.Prompts)$ | $88.2$ | 88.4 | 88.2 | $\textbf{87.4}^{*}$ | $84.0$ | 82.6 | $92.1$ | 91.9 | 87.4 | $80.8$ | 79.2 | 75.8 | $60.2$ | 58.2 | 55.1 | 56.8 | 54.7 | 53.6
$Entropy(SamePrompt)$ | $88.2$ | $85.1$ | $85.5$ | $85.4^{*}$ | 84.7 | 81.4 | $92.1$ | $90.8$ | $87.1$ | $83.7$ | $76.2$ | 74.0 | $60.2$ | $54.2$ | $53.3$ | $54.0$ | $52.1$ | $47.8$
| TempoWIC | MRPC | Conversation
% ChatGPT | $0$ | $20$ | $40$ | $60$ | $80$ | 100 | $0$ | 20 | 40 | 60 | 80 | 100 | $0$ | 20 | 40 | 60 | 80 | $100$
Strategies | Macro F1
$Random$ | $57.5$ | $55.9$ | $53.2$ | $46.2$ | $50.3$ | 42.0 | $83.4$ | $78.6$ | $74.4$ | $70.3$ | $65.8$ | 65.9 | $71.3$ | $63.1$ | $54.5$ | $57.1$ | $50.0$ | $54.1$
$Self-Evaluation$ | $57.5$ | $57.8$ | $55.9^{*}$ | $51.8^{*}$ | $52.9^{*}$ | 43.0 | $83.4$ | $79.7$ | $77.8$ | $71.5$ | $63.9$ | 58.6 | $71.3$ | $\textbf{70.1}^{*}$ | $62.6$ | $\textbf{64.2}^{*}$ | $50.4$ | $50.7$
$Entropy(Diff.Prompts)$ | $57.5$ | $\textbf{58.4}^{*}$ | $\textbf{56.9}^{*}$ | $\textbf{55.9}^{*}$ | $\textbf{53.8}^{*}$ | 42.0 | $83.4$ | 80.0 | $\textbf{79.8}^{*}$ | $\textbf{76.6}^{*}$ | $\textbf{73.1}^{*}$ | 65.9 | $71.3$ | $66.5$ | $\textbf{64.2}^{*}$ | $62.6$ | $\textbf{56.2}^{*}$ | $54.1$
$Entropy(SamePrompt)$ | $57.5$ | $56.3$ | $53.5$ | $52.9^{*}$ | $43.8$ | 42.0 | $83.4$ | $79.2$ | $72.7$ | $67.7$ | $68.6$ | 65.7 | $71.3$ | $55.4$ | $55.4$ | $54.1$ | $54.8$ | 54.6

Table 2: Test performance of fine-tuned RoBERTa under different allocation
strategies. We vary the percentage of data allocated to ChatGPT for annotation
and carry out finetuning using train data annotated under different strategies
for all six datasets. Figure with superscript * means the result under that
strategy is significantly better than baseline strategy at 10% significance
level.

###  5.1 Strategy Comparison

We plot the histograms for distribution of uncertainty metrics (entropy with
different prompts and same prompt as well as confidence score). From Figure 3,
we can observe that the model tends to be confident with its predictions with
a skewed distribution towards high confidence value although we ask ChatGPT to
normalize its answer.

We hypothesize that a lower level of uncertainty in ChatGPT’s response
indicates a higher degree of reliability in the label. Therefore, we set
different thresholds for entropy (lower than an entropy threshold) and self-
confidence score (higher than a confidence threshold) to select data that
ChatGPT is more certain about. For those instances selected, we evaluate
ChatGPT’s annotation quality by calculating its alignment with the gold label
(human annotation). Figure 4’s decreasing trends for entropy-guided allocation
(green and blue dots) on all datasets validate our hypothesis of an inverse
relationship between uncertainty and annotation quality. It justifies the
helpfulness of using the entropy of ChatGPT’s annotations as an estimate for
its annotating expertise. Importantly, we observe that ChatGPT’s self-reported
confidence scores (orange dots) are not consistently a good estimate for its
annotation quality. For some datasets such as AG News (top left), most of the
data (94.3% with calculation) has high self-reported confidence ranging from
0.8 to 1, which leads to a weak separation of data in terms of annotation
quality. For MRPC (top middle), there is a decreasing trend where data
instances with higher confidence scores in fact have a poorer alignment with
gold labels. This shows that the reliability of using self-reported confidence
from LLMs is not guaranteed.

Figure 5: Pareto curves under different allocation strategies (random, entropy
guided, self-evaluation guided). The Pareto frontier is highlighted,
illustrating the optimal choices that are Pareto efficient.

The purpose of achieving a higher quality for train data is to ensure that it
can teach the classifier accurate information through fine-tuning. In Table 2,
we carry out comparisons of different allocation strategies in terms of test
performance after fine-tuning with such data labeled. We see that holding the
proportion of data allocated to ChatGPT fixed (e.g., taking the setup of 40%
for TempoWIC as an example), our proposed uncertainty-guided allocation using
self-evaluation and entropy results in a better-annotated dataset, reflected
by its higher test F1 (56.9) than the random allocation baseline (53.2). More
often than not, entropy-guided allocation is better than confidence-guided
allocation. This is probably due to the skewed distribution of self-reported
confidence, resulting in a poorer distinguishability between instances LLMs
are better or worse at annotating.

Dataset | Text | Groundtruth | ChatGPT
---|---|---|---
AG News |  Title: Sprint Set to Debut Video-Streaming Cell Phone Description: OVERLAND PARK, Kan. (AP) – Channel surfing is moving off the couch as Sprint Corp… | Sci/Tech | Business
TREC |  What does A&W of root beer fame stand for? | Abbreviation | Entity
Stance Detection |  @user As a former fetus I oppose #ProlifeYouth #SemST | Negative | Neutral
Conversation |  rjoccolenty: Shouldn’t her name be Zainab Yusef and not Zainab Khan? Bluebolt94: Does the credits at the end of the episode say ”Zainab Yusef”? No they say ”Zainab Khan” and Yusef called her ”Mrs. Khan” during the episode. So no, her name is ”Zainab Khan”. – AnemoneProjectors: The Khans are clearly not as traditional as the Masoods, or Afia would have been called Afia Yusef. We already know this! And what GS said. Watch the show properly P ––  | True | False
MRPC |  Sentence1: At 5 p.m. EDT , Henri had maximum sustained winds near 50 mph , with some gusts reaching 60 mph. Sentence2: At 8 p.m. Friday , Henri was becoming disorganized , but still had maximum sustained winds near 50 mph , with stronger gusts.  | Not paraphrase | Paraphrase
TempoWiC |  tweet 1: If you need some to watch on Netflix, containment is so good. tweet 2: I have a lot of questions about the containment series. target word: containment | Same | Different

Table 3: Specific instances with high entropy values for ChatGPT annotations.

###  5.2 Pareto Efficient Allocation

By plotting test performance against annotation cost (Figure 5), practitioners
can visualize the tradeoff in annotation quality achievable at different
budgets with collaboration between human and an LLM like ChatGPT by studying
the Pareto frontier. Points along the highlighted Pareto frontier mean it is
theoretically impossible to achieve a higher test accuracy without increasing
the budget, and it is also impossible to reduce the cost but achieve the same
level of annotation quality. Furthermore, it provides information on the
approximate proportion that can be outsourced to ChatGPT to achieve human-
level performance. For more straightforward tasks like topic classification,
part of the annotation work could be potentially outsourced to ChatGPT and
lead to a cost reduction (e.g., AG News: 33%) by ensuring human-level
annotation performance. For datasets requiring nuanced comprehensions like
Stance Detection and Conversation Gone Awry, any level of outsourcing to the
current version of ChatGPT compromises annotation quality. Practitioners can
choose among the Pareto efficient points based on their budgets.

###  5.3 Qualitative Analysis

We select some instances with entropy values higher than 0.8 from each dataset
(Table 3) to understand the current challenges faced by ChatGPT in annotating
data. We find that ChatGPT has high uncertainty for instances containing
sarcasm and incomplete sentences that require more inference during opinion
mining. For example, in deciding the stance towards abortion for the tweet “as
a former fetus I oppose”, the incomplete nature of this sentence causes
confusion to ChatGPT. Also, it struggles with numerical reasoning as seen from
its inability to compare wind speed during paraphrase detection and may be
misled by some keywords (“Corp”) related to other incorrect classes
(“business”) in topic classification.

###  5.4 Ablation Study

We carry out inferences with the same instruction-formatted prompt for the
same number of times and compute the entropy for ChatGPT’s responses. From
Figure 4, we observe some extent of effectiveness of computing entropy using
the same prompt in quantifying ChatGPT’s capability, as reflected by a
decreasing pattern of alignment with the increased threshold. However, it
serves as a much weaker method to quantify expertise compared with our method
with different prompt designs since the majority of the data has zero entropy
(see Figure 3). This suggests that ChatGPT’s responses are generally
consistent within multiple applications of the same prompt. In Table 2, the
test performance of entropy-guided allocation under different prompts is
consistently higher than when based on a single prompt. The performance gap
gives strong evidence of the utility of applying different prompt types in
Table 1.

##  6 Conclusion

This work introduces CoAnnotating, a framework which takes a collaborative
angle to view the relationship between humans and LLMs when annotating each
dataset. Under this framework, we use uncertainty metrics to estimate LLMs’
annotating capability and guide effective work allocation. Moreover, we apply
the Pareto efficiency concept for practitioners to compare strategies and
understand cost-performance tradeoffs. The empirical results demonstrate the
effectiveness of our proposed framework in achieving greater cost efficiency.
Overall, our framework provides important insights around the reliability of
self-reported confidence score by LLMs, the sensitivity of ChatGPT’s responses
to prompt variations as well as the extent to which human resources can be
freed by LLMs to be put on more meaningful areas.

##  7 Limitations

Since LLMs has been trained on a large number of datasets, there may be data
leakage issue where LLMs has seen some datasets in our experiment, making
entropy values obtained for LLMs’ responses lower. As an initial exploration
of the co-annotating concept, this work aims for human-level performance in
annotating datasets. It does not consider the scope of superhuman-level
performance where we treat human annotation in each dataset as gold labels.
Future work can further investigate the instances where LLMs actually
annotates better than humans. We consider annotating profiles of human and
LLMs as two groups but this framework can be further enriched by taking
variations within each group (expert, crowd workers, different LLMs) into
considerations. More exploration can also be carried out to investigate how to
design prompts in a way that can increase LLMs’s annotating expertise so that
more annotation work can be outsourced to LLMs for greater cost efficiency.
Moreover, this work only did experiments for classification tasks and English
datasets. However, the idea of CoAnnotating is generalizable to generation
tasks and datasets in other languages as well, which are meaningful to study
in future work.

## Ethical Statement

We are aware of the potential ethical concerns of using LLMs as potential
labelers in the data annotation process in terms of the perpetuation of
existing biases in LLMs. Since LLMs are trained on vast amounts of texts on
the Internet, they can unavoidably incorporate the biases present in these
data sources. Such biases could be under-representation of certain demographic
groups, cultural stereotypes as well as linguistic biases. However, we believe
that the benefit of proposing a collaborative co-annotation framework
outweighs the potential risks related to the framework.

## Acknowledgement

We are thankful to the members of SALT Lab and WING Lab as well as anonymous
EMNLP reviewers for their helpful feedback. Minzhi Li is supported by the
A*STAR Computing and Information Science (ACIS) Scholarship. Caleb Ziems is
supported by the NSF Graduate Research Fellowship under Grant No. DGE-2039655.
We would like to acknowledge a grant from the Office of Naval Research to DY,
and National Research Foundation, Singapore under its AI Singapore Programme
(AISG Award No: AISG2-GC-2022-005).

## References

  * Abdolrashidi et al. (2021) AmirAli Abdolrashidi, Lisa Wang, Shivani Agrawal, Jonathan Malmaud, Oleg Rybakov, Chas Leichner, and Lukasz Lew. 2021.  Pareto-optimal quantized resnet is mostly 4-bit.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , pages 3091–3099.
  * Amin et al. (2023) Mostafa M Amin, Erik Cambria, and Björn W Schuller. 2023.  Will affective computing emerge from foundation models and general ai? a first evaluation on chatgpt.  _arXiv preprint arXiv:2303.03186_.
  * Ando and Zhang (2005) Rie Kubota Ando and Tong Zhang. 2005.  A framework for learning predictive structures from multiple tasks and unlabeled data.  _Journal of Machine Learning Research_ , 6:1817–1853.
  * Andrew and Gao (2007) Galen Andrew and Jianfeng Gao. 2007.  Scalable training of $L_{1}$-regularized log-linear models.  In _Proceedings of the 24th International Conference on Machine Learning_ , pages 33–40.
  * Awasthi et al. (2020) Abhijeet Awasthi, Sabyasachi Ghosh, Rasna Goyal, and Sunita Sarawagi. 2020.  Learning from rules generalizing labeled exemplars.  _arXiv preprint arXiv:2004.06025_.
  * Bach et al. (2019) Stephen H Bach, Daniel Rodriguez, Yintao Liu, Chong Luo, Haidong Shao, Cassandra Xia, Souvik Sen, Alex Ratner, Braden Hancock, Houman Alborzi, et al. 2019.  Snorkel drybell: A case study in deploying weak supervision at industrial scale.  In _Proceedings of the 2019 International Conference on Management of Data_ , pages 362–375.
  * Bang et al. (2023) Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al. 2023.  A multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity.  _arXiv preprint arXiv:2302.04023_.
  * Bartolo et al. (2021) Max Bartolo, Tristan Thrush, Sebastian Riedel, Pontus Stenetorp, Robin Jia, and Douwe Kiela. 2021.  Models in the loop: Aiding crowdworkers with generative annotation assistants.  _arXiv preprint arXiv:2112.09062_.
  * Chaganty et al. (2018) Arun Tejasvi Chaganty, Stephen Mussman, and Percy Liang. 2018.  The price of debiasing automatic metrics in natural language evaluation.  _arXiv preprint arXiv:1807.02202_.
  * Diao et al. (2023) Shizhe Diao, Pengcheng Wang, Yong Lin, and Tong Zhang. 2023.  Active prompting with chain-of-thought for large language models.  _arXiv preprint arXiv:2302.12246_.
  * Ding et al. (2022) Bosheng Ding, Chengwei Qin, Linlin Liu, Lidong Bing, Shafiq Joty, and Boyang Li. 2022.  Is gpt-3 a good data annotator?  _arXiv preprint arXiv:2212.10450_.
  * Dolan and Brockett (2005) Bill Dolan and Chris Brockett. 2005.  Automatically constructing a corpus of sentential paraphrases.  In _Third International Workshop on Paraphrasing (IWP2005)_.
  * Gentile et al. (2022) Claudio Gentile, Zhilei Wang, and Tong Zhang. 2022.  Fast rates in pool-based batch active learning.  _arXiv preprint arXiv:2202.05448_.
  * Gilardi et al. (2023) Fabrizio Gilardi, Meysam Alizadeh, and Maël Kubli. 2023.  Chatgpt outperforms crowd-workers for text-annotation tasks.  _arXiv preprint arXiv:2303.15056_.
  * Gonsior et al. (2020) Julius Gonsior, Maik Thiele, and Wolfgang Lehner. 2020.  Weakal: Combining active learning and weak supervision.  In _Discovery Science: 23rd International Conference, DS 2020, Thessaloniki, Greece, October 19–21, 2020, Proceedings 23_ , pages 34–49. Springer.
  * Grosman et al. (2020) Jonatas S Grosman, Pedro HT Furtado, Ariane MB Rodrigues, Guilherme G Schardong, Simone DJ Barbosa, and Hélio CV Lopes. 2020.  Eras: Improving the quality control in the annotation process for natural language processing tasks.  _Information Systems_ , 93:101553.
  * Hoffmann et al. (2011) Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke Zettlemoyer, and Daniel S Weld. 2011.  Knowledge-based weak supervision for information extraction of overlapping relations.  In _Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies_ , pages 541–550.
  * Huang et al. (2023) Fan Huang, Haewoon Kwak, and Jisun An. 2023.  Is chatgpt better than human annotators? potential and limitations of chatgpt in explaining implicit hate speech.  _arXiv preprint arXiv:2302.07736_.
  * Jang and Lukasiewicz (2023) Myeongjun Jang and Thomas Lukasiewicz. 2023.  Consistency analysis of chatgpt.  _arXiv preprint arXiv:2303.06273_.
  * Kadavath et al. (2022) Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield Dodds, Nova DasSarma, Eli Tran-Johnson, et al. 2022.  Language models (mostly) know what they know.  _arXiv preprint arXiv:2207.05221_.
  * Kang et al. (2023) Junmo Kang, Wei Xu, and Alan Ritter. 2023.  Distill or annotate? cost-efficient fine-tuning of compact models.  _arXiv preprint arXiv:2305.01645_.
  * Kittur et al. (2008) Aniket Kittur, Ed H Chi, and Bongwon Suh. 2008.  Crowdsourcing user studies with mechanical turk.  In _Proceedings of the SIGCHI conference on human factors in computing systems_ , pages 453–456.
  * Kocmi and Federmann (2023) Tom Kocmi and Christian Federmann. 2023.  Large language models are state-of-the-art evaluators of translation quality.  _arXiv preprint arXiv:2302.14520_.
  * Kocoń et al. (2023) Jan Kocoń, Igor Cichecki, Oliwier Kaszyca, Mateusz Kochanek, Dominika Szydło, Joanna Baran, Julita Bielaniewicz, Marcin Gruza, Arkadiusz Janz, Kamil Kanclerz, et al. 2023.  Chatgpt: Jack of all trades, master of none.  _arXiv preprint arXiv:2302.10724_.
  * Kuzman et al. (2023) Taja Kuzman, Nikola Ljubešić, and Igor Mozetič. 2023.  Chatgpt: Beginning of an end of manual annotation? use case of automatic genre identification.  _arXiv preprint arXiv:2303.03953_.
  * Li and Roth (2002) Xin Li and Dan Roth. 2002.  Learning question classifiers.  In _COLING 2002: The 19th International Conference on Computational Linguistics_.
  * Lin et al. (2022) Stephanie Lin, Jacob Hilton, and Owain Evans. 2022.  Teaching models to express their uncertainty in words.  _arXiv preprint arXiv:2205.14334_.
  * Lingren et al. (2014) Todd Lingren, Louise Deleger, Katalin Molnar, Haijun Zhai, Jareen Meinzen-Derr, Megan Kaiser, Laura Stoutenborough, Qi Li, and Imre Solti. 2014.  Evaluating the impact of pre-annotation on annotation speed and potential bias: natural language processing gold standard development for clinical named entity recognition in clinical trial announcements.  _Journal of the American Medical Informatics Association_ , 21(3):406–413.
  * Lison et al. (2020) Pierre Lison, Aliaksandr Hubin, Jeremy Barnes, and Samia Touileb. 2020.  Named entity recognition without labelled data: A weak supervision approach.  _arXiv preprint arXiv:2004.14723_.
  * Liu et al. (2022) Alisa Liu, Swabha Swayamdipta, Noah A Smith, and Yejin Choi. 2022.  Wanli: Worker and ai collaboration for natural language inference dataset creation.  _arXiv preprint arXiv:2201.05955_.
  * Loureiro et al. (2022) Daniel Loureiro, Aminette D’Souza, Areej Nasser Muhajab, Isabella A White, Gabriel Wong, Luis Espinosa Anke, Leonardo Neves, Francesco Barbieri, and Jose Camacho-Collados. 2022.  Tempowic: An evaluation benchmark for detecting meaning shift in social media.  _arXiv preprint arXiv:2209.07216_.
  * Mann and McCallum (2010) Gideon S Mann and Andrew McCallum. 2010.  Generalized expectation criteria for semi-supervised learning with weakly labeled data.  _Journal of machine learning research_ , 11(2).
  * Meng et al. (2018) Yu Meng, Jiaming Shen, Chao Zhang, and Jiawei Han. 2018.  Weakly-supervised neural text classification.  In _proceedings of the 27th ACM International Conference on information and knowledge management_ , pages 983–992.
  * Min et al. (2013) Bonan Min, Ralph Grishman, Li Wan, Chang Wang, and David Gondek. 2013.  Distant supervision for relation extraction with an incomplete knowledge base.  In _Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 777–782.
  * Mohammad et al. (2016a) Saif Mohammad, Svetlana Kiritchenko, Parinaz Sobhani, Xiaodan Zhu, and Colin Cherry. 2016a.  Semeval-2016 task 6: Detecting stance in tweets.  In _Proceedings of the 10th international workshop on semantic evaluation (SemEval-2016)_ , pages 31–41.
  * Mohammad et al. (2016b) Saif Mohammad, Svetlana Kiritchenko, Parinaz Sobhani, Xiaodan Zhu, and Colin Cherry. 2016b.  SemEval-2016 task 6: Detecting stance in tweets.  In _Proceedings of the 10th International Workshop on Semantic Evaluation (SemEval-2016)_ , pages 31–41, San Diego, California. Association for Computational Linguistics.
  * Pikuliak (2023) Matúš Pikuliak. 2023.  Chatgpt survey: Performance on nlp datasets.  https://www.opensamizdat.com/posts/chatgpt_survey.
  * Qin et al. (2023) Chengwei Qin, Aston Zhang, Zhuosheng Zhang, Jiaao Chen, Michihiro Yasunaga, and Diyi Yang. 2023.  Is chatgpt a general-purpose natural language processing task solver?  _arXiv preprint arXiv:2302.06476_.
  * Rasooli and Tetreault (2015) Mohammad Sadegh Rasooli and Joel R. Tetreault. 2015.  Yara parser: A fast and accurate dependency parser.  _Computing Research Repository_ , arXiv:1503.06733.  Version 2.
  * Ratner et al. (2017) Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré. 2017.  Snorkel: Rapid training data creation with weak supervision.  In _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , volume 11, page 269. NIH Public Access.
  * Reiss (2023) Michael Reiss. 2023.  Testing the reliability of chatgpt for text annotation and classification: A cautionary remark.
  * Snow et al. (2008) Rion Snow, Brendan O’connor, Dan Jurafsky, and Andrew Y Ng. 2008.  Cheap and fast–but is it good? evaluating non-expert annotations for natural language tasks.  In _Proceedings of the 2008 conference on empirical methods in natural language processing_ , pages 254–263.
  * Tan et al. (2023) Yiming Tan, Dehai Min, Yu Li, Wenbo Li, Nan Hu, Yongrui Chen, and Guilin Qi. 2023.  Evaluation of chatgpt as a question answering system for answering complex questions.  _arXiv preprint arXiv:2303.07992_.
  * Tekiroglu et al. (2020) Serra Sinem Tekiroglu, Yi-Ling Chung, and Marco Guerini. 2020.  Generating counter narratives against online hate speech: Data and strategies.  _arXiv preprint arXiv:2004.04216_.
  * Törnberg (2023) Petter Törnberg. 2023.  Chatgpt-4 outperforms experts and crowd workers in annotating political twitter messages with zero-shot learning.  _arXiv preprint arXiv:2304.06588_.
  * Treviso et al. (2022) Marcos Treviso, António Góis, Patrick Fernandes, Erick Fonseca, and Andre Martins. 2022.  Predicting attention sparsity in transformers.  In _Proceedings of the Sixth Workshop on Structured Prediction for NLP_ , pages 67–81, Dublin, Ireland. Association for Computational Linguistics.
  * Wang et al. (2023) Jiaan Wang, Yunlong Liang, Fandong Meng, Haoxiang Shi, Zhixu Li, Jinan Xu, Jianfeng Qu, and Jie Zhou. 2023.  Is chatgpt a good nlg evaluator? a preliminary study.  _arXiv preprint arXiv:2303.04048_.
  * Wang et al. (2021) Shuohang Wang, Yang Liu, Yichong Xu, Chenguang Zhu, and Michael Zeng. 2021.  Want to reduce labeling cost? gpt-3 can help.  _arXiv preprint arXiv:2108.13487_.
  * Wang et al. (2022) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, and Denny Zhou. 2022.  Self-consistency improves chain of thought reasoning in language models.  _arXiv preprint arXiv:2203.11171_.
  * Yuan et al. (2021) Ann Yuan, Daphne Ippolito, Vitaly Nikolaev, Chris Callison-Burch, Andy Coenen, and Sebastian Gehrmann. 2021.  Synthbio: A case study in human-ai collaborative curation of text datasets.  _arXiv preprint arXiv:2111.06467_.
  * Zhang et al. (2022) Jieyu Zhang, Cheng-Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner. 2022.  A survey on programmatic weak supervision.  _arXiv preprint arXiv:2202.05433_.
  * Zhang et al. (2021) Jieyu Zhang, Bohan Wang, Xiangchen Song, Yujing Wang, Yaming Yang, Jing Bai, and Alexander Ratner. 2021.  Creating training sets via weak indirect supervision.  _arXiv preprint arXiv:2110.03484_.
  * Zhang et al. (2018) Justine Zhang, Jonathan P Chang, Cristian Danescu-Niculescu-Mizil, Lucas Dixon, Yiqing Hua, Nithum Thain, and Dario Taraborelli. 2018.  Conversations gone awry: Detecting early signs of conversational failure.  _arXiv preprint arXiv:1805.05345_.
  * Zhang et al. (2015) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  _Advances in neural information processing systems_ , 28.
  * Zhong et al. (2023) Qihuang Zhong, Liang Ding, Juhua Liu, Bo Du, and Dacheng Tao. 2023.  Can chatgpt understand too? a comparative study on chatgpt and fine-tuned bert.  _arXiv preprint arXiv:2302.10198_.
  * Ziems et al. (2023) Caleb Ziems, William Held, Omar Shaikh, Jiaao Chen, Zhehao Zhang, and Diyi Yang. 2023.  Can large language models transform computational social science?  _arXiv preprint arXiv:2305.03514_.


# Learning to optimize with convergence guarantees
using nonlinear system theory

Andrea Martin and Luca Furieri A. Martin and L. Furieri are with the Institute
of Mechanical Engineering, EPFL, Switzerland. E-mail addresses:
{andrea.martin<EMAIL_ADDRESS>research is supported by the Swiss
National Science Foundation through the NCCR Automation (grant agreement
51NF40_80545) and the Ambizione grant PZ00P2_208951.

###### Abstract

The increasing reliance on numerical methods for controlling dynamical systems
and training machine learning models underscores the need to devise algorithms
that dependably and efficiently navigate complex optimization landscapes.
Classical gradient descent methods offer strong theoretical guarantees for
convex problems; however, they demand meticulous hyperparameter tuning for
non-convex ones. The emerging paradigm of learning to optimize (L2O) automates
the discovery of algorithms with optimized performance leveraging learning
models and data – yet, it lacks a theoretical framework to analyze convergence
and robustness of the learned algorithms. In this paper, we fill this gap by
harnessing nonlinear system theory. Specifically, we propose an unconstrained
parametrization of all convergent algorithms for smooth non-convex objective
functions. Notably, our framework is directly compatible with automatic
differentiation tools, ensuring convergence by design while learning to
optimize.

##  I Introduction

Many fundamental tasks in machine learning (ML) and optimal control involve
solving optimization problems, that is, computing a solution

$x^{\star}=\operatorname*{arg\,min}_{x\in\mathbb{R}^{d}}~{}f(x)\,,$ (1)

for a given objective function $f(\cdot)$. As the real-world applications of
ML and optimal control grow in complexity, from training deep neural networks
(NNs) for high-dimensional classification tasks to optimally operating large-
scale cyber-physical systems, finding analytical solutions to these
optimization problems becomes prohibitive. This has led to the increased use
of numerical optimization algorithms, such as gradient descent methods, which
iteratively approach the critical points $\hat{x}$ of $f(\cdot)$, i.e., the
values $\hat{x}$ such that $\nabla\\!f(\hat{x})=0$. As we rely on iterative
algorithms to solve complex optimization problems, their ability to quickly
and robustly converge to good critical points becomes crucial.

Traditionally, the optimization literature has focused on hand-crafting
algorithms tailored to specific instances of (1), such as those showcasing
convex [1] or submodular [2] objective functions. For instance, widely-used
optimization algorithms include vanilla gradient descent, the heavy-ball
method [3], and Nesterov’s accelerated method [4]. While these algorithms come
with strong theoretical guarantees for convex optimization, their performance
on non-convex problems, such as training deep NNs, crucially depends on their
hyperparameters [5]. Besides, due to a lack of a general theory,
hyperparameter tuning is often performed by domain experts based on best
practices and know-how.

In the attempt to provide a unifying take on the analysis and synthesis of
optimization algorithms, the control theory and ML communities have
increasingly interpreted iterative update rules as evolving discrete-time
dynamical systems; we refer to the recent review and road-map paper [6] for a
comprehensive list of references. Notably, [7, 8, 9, 10, 11] have studied
robustness and worst-case performance of optimization algorithms, leading to
the design of new methods with optimized convergence rates [7, 11] or
sublinear regret guarantees in online optimization scenarios [12]. All the
results mentioned above are limited to convex objective functions. The
paradigm of feedback optimization [13, 14] implements optimization algorithms
directly in closed-loop with dynamical systems, endowing them with the ability
to self-regulate and converge towards the solution of desired nonlinear
optimization programs. Analyzing and shaping the transient performance of the
resulting closed-loop behavior remains an open venue for research.

To tackle the non-convex and time-varying optimization landscapes that are
ubiquitous in ML and optimal control, a learning to optimize (L2O) shift of
paradigm has been emerging: moving from _in silico_ algorithms designed by
hand based on general problem properties [6], towards embracing ML to discover
powerful algorithms from data. In this context, “data” refers to example
optimization problems of interest provided during a training phase – which can
take place either offline or online. Specifically, the L2O approach
parametrizes algorithms in a very general way, and performs meta-training over
these parameters; for instance, [15] encodes update rules through a long
short-term memory (LSTM) network. As observed in [16], when the distribution
of sample problems is narrow, learned algorithms can overfit the tasks and
discover shortcuts that classic algorithms do not take. When the distribution
of sample problems is sufficiently varied, the algorithm’s performance
transfers well to new tasks [15, 17, 18]. However, it has been observed that
optimizers trained as per [15] may lack convergence guarantees on almost all
unseen tasks [16] – even when they are taken from the same task distribution
[18]. A mitigation to avoid compounding errors is proposed in [18] based on
reinforcement meta-learning. For convex objective functions, provable
convergence guarantees of learned optimizers were considered in [19] by
exploiting a conservative fall-back mechanism that switches to a fixed
convergent algorithm when the learned updates are too aggressive. To the best
of the authors’ knowledge, despite the outstanding empirical performance, the
theoretical underpinnings of L2O such as convergence and robustness guarantees
of the learned algorithms stand as uncharted territory.

_Contributions:_ In this paper, we establish methods to learn high-performance
optimization algorithms that are inherently convergent for smooth non-convex
functions. From control system theory, we inherit the emphasis on convergence
and robustness guarantees [7, 11, 13, 14], ensuring learned algorithms
converge to local solutions in a provable and quantifiable way. From ML, we
embrace the ability to tackle user-defined performance metrics through
automatic differentiation, and the outstanding generalization capabilities to
previously unseen optimization problems. Our key contribution is the
reformulation of the problem of learning optimal convergent algorithms into an
equivalent, unconstrained one that is directly amenable to automatic
differentiation tools. We achieve this by dividing update rules into: $1)$ a
gradient descent step that ensures convergence, and $2)$ a learnable
innovation term that enhances performance without compromising convergence.
Notably, our method not only guarantees algorithm convergence, but it also
encompasses _all and only_ convergent algorithms, thus sidestepping
conservatism, and eliminating the need for safeguarding and early-stopping
mechanisms [15, 16, 19]. Furthermore, we achieve convergence even when dealing
with incomplete gradient measurements, making our methodology relevant for ML
with batch data. We validate the effectiveness and generalizability of our
methodology through ML benchmarks, advocating for the adoption of customizable
performance metrics that consider a blend of algorithmic speed and quality of
the solutions they converge to.

_Notation:_ The set of all sequences $\mathbf{x}=(x_{0},x_{1},x_{2},\ldots)$
where $x_{t}\in\mathbb{R}^{n}$ for all $t\in\mathbb{N}$ is denoted as
$\ell^{n}$. For $\mathbf{x}\in\ell^{n}$, we denote by
$z\mathbf{x}=(x_{1},x_{2},\ldots)$ the sequence shifted one-time-step forward.
Moreover, $\mathbf{x}$ belongs to $\ell_{2}^{n}\subset\ell^{n}$ if
$\left\lVert\mathbf{x}\right\rVert_{2}=\sqrt{\sum_{t=0}^{\infty}|x_{t}|^{2}}<\infty$,
where $|\cdot|$ denotes any vector norm. When clear from the context, we omit
the superscript $n$ from $\ell^{n}$ and $\ell^{n}_{2}$. For a function
$g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, we write
$g\left(\mathbf{x}\right)=(g(x_{0}),g(x_{1}),\ldots)\in\ell^{m}$. A causal
operator $\mathbf{A}:\ell^{n}\rightarrow\ell^{m}$ such that
$\mathbf{A}(\mathbf{x})=(A_{0}(x_{0}),A_{1}(x_{1:0}),\ldots,A_{t}(x_{t:0}),\ldots)$
is said to be $\ell_{2}$-stable if $\mathbf{A}(\mathbf{x})\in\ell_{2}^{m}$ for
all $\mathbf{x}\in\ell_{2}^{n}$. Equivalently, we write
$\mathbf{A}\in\mathcal{L}_{2}$. We denote by $\left\lfloor x\right\rfloor$ the
greatest integer smaller than $x\in\mathbb{R}$ and use $a\bmod b$ to denote
the remainder of $a\in\mathbb{N}$ when divided by $b\in\mathbb{N}$.

##  II Problem Formulation

In this paper, we focus on optimization problems in the form (1) where
$f(\cdot)$ has $\beta$-Lipschitz gradients, that is,
$|\nabla\\!f(x)-\nabla\\!f(y)|\leq\beta|x-y|$ for all $x,y\in\mathbb{R}^{d}$.
We denote the set of such $\beta$-smooth functions by $\mathcal{S}_{\beta}$.
Further, it is assumed that $f(\cdot)$ is bounded from below. We describe an
iterative optimization algorithm via the recursion

$x_{t+1}=x_{t}+u_{t}=x_{t}+\pi_{t}(f,x_{t:0})\,,\quad t\in\mathbb{N}\,,$ (2)

where $x_{0}\in\mathbb{R}^{d}$ is the initial guess, $x_{t}\in\mathbb{R}^{d}$
is the candidate solution vector after $t$ iterations, and
$u_{t}=\pi_{t}(f,x_{t:0})\in\mathbb{R}^{d}$ is the algorithm update rule. We
can write (2) compactly as

$z\mathbf{x}=\mathbf{x}+\bm{\pi}(f,\mathbf{x})+z\bm{\delta}^{x_{0}}\,,$ (3)

where
$\bm{\pi}(f,\cdot)=\left(\pi_{0}(f,x_{0}),\pi_{1}(f,x_{1:0}),\ldots\right)$ is
a causal operator for any objective function $f$. The initial state sequence
$\bm{\delta}^{x_{0}}$ is defined as
$\bm{\delta}^{x_{0}}=(x_{0},0,\ldots)\in\ell_{2}$. We proceed to define the
fundamental notion of convergent algorithms.

###### Definition 1

Consider the iteration (2). An update rule $\bm{\pi}(f,\mathbf{x})$ is
_convergent_ for $f$ if for any $x_{0}\in\mathbb{R}^{d}$

$\lim_{t\rightarrow\infty}\pi_{t}(f,x_{t:0})=0,\quad\lim_{t\rightarrow\infty}\nabla\\!f(x_{t})=0\,.$
(4)

Equivalently, we write $\bm{\pi}\in\Gamma(f)$. Additionally, if

$\displaystyle\left\lVert\nabla\\!f(\mathbf{x})\right\rVert^{2}=K_{\nabla}<\infty\,,\quad\left\lVert\bm{\pi}(f,\mathbf{x})\right\rVert^{2}=K_{\bm{\pi}}<\infty\,,$
(5)

we say the algorithm is _square-sum convergent_ for $f$. Equivalently, we
write $\bm{\pi}\in\Sigma(f)$.

Note that every update rule in $\Sigma(f)$ also lies in $\Gamma(f)$ for every
$f\in\mathcal{S}_{\beta}$. In particular, although (4) and (5) both guarantee
convergence to a critical point of $f$ as $t\rightarrow\infty$, (5) further
quantifies how fast and robustly an algorithm converges based on $K_{\nabla}$
and $K_{\bm{\pi}}$. Further, we observe that classical convergence bounds for
smooth convex optimization in the form $|x_{t}-x^{\star}|\leq
K\rho^{t}|x_{0}-x^{\star}|$, where $K>0$, see, e.g, [7, 11], readily imply
that $\nabla f(\mathbf{x})\in\ell_{2}$.

Given a distribution $\mathcal{F}$ over functions in $\mathcal{S}_{\beta}$ and
a distribution $\mathcal{X}_{0}$ over initial solutions
$x_{0}\in\mathbb{R}^{d}$, the problem of designing an optimal convergent
algorithm is formulated as

$\displaystyle~{}\min_{\bm{\pi}}$
$\displaystyle\mathbb{E}_{f\sim\mathcal{F},x_{0}\sim\mathcal{X}_{0}}\left[\mathtt{MetaLoss}(f,\mathbf{x})\right]$
(6a) $\displaystyle\operatorname*{subject~{}to}$ $\displaystyle\quad
x_{t+1}=x_{t}+\pi_{t}(f,x_{t:0}),$ (6b)
$\displaystyle\quad\bm{\pi}(f,\mathbf{x})\in\Sigma(f),~{}\forall
f\in\mathcal{S}_{\beta}\,,$ (6c)

where $\Sigma(f)$ can be relaxed to $\Gamma(f)$ depending on the design
specifications. As suggested in [15, 17, 18], a useful choice for
$\mathtt{MetaLoss}(f,\mathbf{x})$ in (6a) is given by

$\mathtt{MetaLoss}(f,\mathbf{x})=\sum_{t=0}^{T}\alpha_{t}|\nabla\\!f(x_{t})|^{2}+\gamma_{t}f(x_{t})\,,$
(7)

where $\alpha_{t}\geq 0$ and $\gamma_{t}\geq 0$ aim to strike a balance
between the speed of convergence and the quality of the solution found after
$T\in\mathbb{N}$ steps. At the same time, the constraint (6c) ensures
convergence to a critical point $\hat{x}$ satisfying $\nabla\\!f(\hat{x})=0$
for any future problem instance $f\in\mathcal{S}_{\beta}$.

######  Remark 1 (The value of convergence)

Excluding update rules that fail to comply with (6c) is essential, as (6c)
guarantees convergence of the algorithm being designed, even if the meta-
optimization is stopped prematurely. Notably, convergence to a local solution
for possibly unseen instances of
$f_{\operatorname{new}}\in\mathcal{S}_{\beta}$ is a necessary condition to
“generalize” to solving optimization problems drawn from a distribution
$\mathcal{F}^{\prime}$ different from $\mathcal{F}$, and to achieve sublinear
meta-regret in online convex optimization frameworks [12].

##  III Main Results

This section characterizes update rules that converge according to Definition
1, and describes how to learn over them. First, given full gradient
measurements, we establish a complete parametrization of all and only the
algorithms that converge in the sum-square sense as per (6c). Second, for the
case – common in ML and deep learning applications – where
$f(x)=\sum_{i=1}^{M}f_{i}(x)$ and only partial gradients $\nabla\\!f_{i}(x)$
are available at each step, we parametrize algorithms that converge
asymptotically as per (4). In both scenarios, we directly parametrize
convergent update rules via a vector $\theta\in\mathbb{R}^{D}$, thus enabling
unconstrained learning of convergent-by-design algorithms via automatic
differentiation tools.

###  III-A Learning over all square-sum convergent algorithms

We start by proving that any update rule in the form

$\bm{\pi}(f,\mathbf{x})=-\eta\nabla\\!f(\mathbf{x})+\mathbf{v}\,,$ (8)

lies in $\Sigma(f)$ for any $\mathbf{v}\in\ell_{2}$ and any
$f\in\mathcal{S}_{\beta}$, as long as $0<\eta<\beta^{-1}$. In other words, if
we enhance standard gradient descent with an $\ell_{2}$ “innovation” term –
designed, e.g., to escape a bad local minimum or a saddle point – we preserve
square-sum convergence to a critical point of $f$.

###### Lemma 1

Consider the recursion $\eqref{eq:algorithm_dynamics_operator_form}$. The
update rule given by (8) with $0<\eta<\beta^{-1}$ satisfies (6c) for every
choice of $\mathbf{v}\in\ell_{2}$.

The class of algorithms in the form (8) suggests a useful separation of roles;
a gradient descent update can be used to ensure convergence, while an
innovation term $\mathbf{v}\in\ell_{2}$ can be learned to improve the
algorithm performance. Nonetheless, a crucial question regarding the
conservatism of searching over $\mathbf{v}\in\ell_{2}$ in (8) remains.

_Can _any_ convergent algorithm complying with (6c) be written as the sum of a
gradient-based update and an innovation signal $\mathbf{v}\in\ell_{2}$ as per
(8)?_

In what follows, we answer in the affirmative, further revealing that the
innovation $\mathbf{v}\in\ell_{2}$ must be parametrized as a function of
$\bm{\delta}^{x_{0}}$ in order to recover any convergent behavior using (8).
Our proof hinges on studying the closed-loop mappings induced by an update
rule $\bm{\pi}(f,\mathbf{x})$.

###### Definition 2

Consider the recursion $\eqref{eq:algorithm_dynamics_operator_form}$. For any
update rule $\bm{\pi}(f,\mathbf{x})$, the mapping
$(f,\bm{\delta}^{x_{0}}){\rightarrow}(\mathbf{x},\mathbf{u},\nabla\\!f(\mathbf{x}))$
is denoted as the _closed-loop mapping_ induced by
$\mathbf{u}=\bm{\pi}(f,\mathbf{x})$.

The terminology above is drawn from control system theory. Under a system-
theoretic lens, we can view $\bm{\pi}(f,\mathbf{x})$ as a state feedback
control policy, and
$(f,\bm{\delta}^{x_{0}}){\rightarrow}(\mathbf{x},\mathbf{u},\nabla\\!f(\mathbf{x}))$
as the corresponding closed-loop behavior. The convergence constraint
$\eqref{eq:constraint_convergence}$ thus translates to regulating the system
output signal $\mathbf{y}$ to $0$, in the sense that
$\mathbf{y}=\nabla\\!f(\mathbf{x})\in\ell_{2}$, robustly for any
$x_{0}\in\mathbb{R}^{d}$ and any $f\in\mathcal{S}_{\beta}$.

###### Lemma 2

Let $x_{0}\in\mathbb{R}^{d}$ and $f\in\mathcal{S}_{\beta}$. Define

$(f,\bm{\delta}^{x_{0}})\rightarrow(\mathbf{x}_{\bm{\pi}},\mathbf{u}_{\bm{\pi}},\nabla\\!f(\mathbf{x}_{\bm{\pi}}))\,,$
(9)

as the closed-loop mapping induced by a policy
$\mathbf{u}=\bm{\pi}(f,\mathbf{x})$. For any $\bm{\pi}(f,\mathbf{x})$
complying with (6c), there exists an operator $\mathbf{V}\in\mathcal{L}_{2}$
such that the closed-loop mapping given by

$(f,\bm{\delta}^{x_{0}})\rightarrow(\mathbf{x},-\eta\nabla\\!f(\mathbf{x})+\mathbf{V}(\bm{\delta}^{x_{0}}),\nabla\\!f(\mathbf{x}))\,,$
(10)

is equivalent to (9).

The completeness property stated above is key, as it implies that (8)
encompasses all sum-square convergent algorithms – including those that
_globally_ minimize (6a). Together with Lemma 1, Lemma 2 leads to our main
result.

###### Theorem 1

If $0<\eta<\beta^{-1}$, the meta-optimization problem (6) is equivalent to

$\displaystyle\min_{\mathbf{V}\in\mathcal{L}_{2}}$
$\displaystyle\mathbb{E}_{f\sim\mathcal{F},x_{0}\sim\mathcal{X}_{0}}\left[\mathtt{MetaLoss}(f,\mathbf{x})\right]$
(11a) $\displaystyle\operatorname*{subject~{}to}$ $\displaystyle\quad
z\mathbf{x}=\mathbf{x}-\eta\nabla\\!f(\mathbf{x})+\mathbf{V}(\bm{\delta}^{x_{0}})+z\bm{\delta}^{x_{0}}\,.$
(11b)

The value of Theorem 1 is that it reformulates the meta-optimization (6) with
sum-square convergence constraints as the _equivalent_ problem of learning an
operator $\mathbf{V}\in\mathcal{L}_{2}$ without posing additional constraints
for convergence. In practice, (11) can be tackled using operators $\mathbf{V}$
such that

$\mathbf{V}(\bm{\delta}^{x_{0}},\theta)\in\ell_{2},\quad\forall\bm{\delta}^{x_{0}}\in\ell_{2},~{}\forall\theta\in\mathbb{R}^{D}\,,$
(12)

thus translating (11) into learning the best parameter
$\theta\in\mathbb{R}^{D}$ through automatic differentiation. To ensure that
(12) holds, one can, for instance, model $\mathbf{V}$ as a stable recurrent NN
$v_{t}=\phi(\theta,v_{t-1},u_{t})$, where $\phi(\cdot)$ is contracting for all
$\theta\in\mathbb{R}^{D}$; several such models have recently been developed in
the literature [20, 21, 22] and are readily implementable.

In practice, it may prove beneficial to introduce explicit dependence of
$\mathbf{V}$ in (12) on additional input features besides
$\bm{\delta}^{x_{0}}$. Indeed, as shown in [18], learning over algorithms that
react to $(x_{t:0},\nabla f(x_{t:0}),f(x_{t:0}))$ can be effective in
transferring their meta-performance to ML tasks vastly different from those
encountered during training. While Theorem 1 proves that designing an update
rule that solely reacts to $x_{0}\sim\mathcal{X}_{0}$ is sufficient for
achieving meta-optimal behaviors, additional input features could
significantly improve how effectively we navigate the meta-optimization
landscape. For instance, by defining
$\bm{\omega}=\bm{\Omega}(\mathbf{x},\nabla f(\mathbf{x}),f(\mathbf{x}))$ and
$\mathbf{z}=\mathbf{Z}(\bm{\delta}^{x_{0}})$, where
$\bm{\Omega}:\ell\rightarrow\ell$ and $\mathbf{Z}\in\mathcal{L}_{2}$ are
operators to be freely designed, we can generate $\mathbf{v}\in\ell_{2}$ as
follows

$v_{t}=|z_{t}||\omega_{t}|^{-1}\omega_{t}\,.$ (13)

Using (13), sum-square convergence is preserved by design, as we set
$|v_{t}|=|z_{t}|$ at all times, and $\mathbf{z}\in\ell_{2}$. Further,
completeness as per Lemma 2 is maintained; this is proved by choosing
$\mathbf{Z}$ according to (21) in the Appendix and selecting
$\bm{\Omega}(\mathbf{x},\nabla
f(\mathbf{x}),f(\mathbf{x}))=\mathbf{Z}(\bm{\delta}^{x_{0}})$.

###  III-B The case of gradients with errors

In many ML and deep learning tasks, $f(x)$ is obtained as the empirical
average of the cost over a batch of input data, that is,
$f(x)=\sum_{i=0}^{M-1}f_{i}(x)$. In these cases, global gradient information
$\nabla\\!f(x)$ may not be available, and the candidate solution $x_{t}$ is
updated based on $\nabla\\!f_{i}(x_{t})$ for some $i\in[0,M-1]$ only. Drawing
connections with analysis techniques for stochastic gradient descent
(SGD),111Recall that SGD performs the update
$\pi_{t}(f,x_{t})=-\eta_{t}\nabla\\!f_{k}(x_{t})$, where $k_{t}$ is a sequence
of independent random variables uniformly distributed over the set
$\\{0,\ldots,M-1\\}$, see, e.g., [23]. we proceed to parametrize a rich class
of asymptotically convergent algorithms that rely on partial gradient
information only.

###### Theorem 2

Let $f(x)=\sum_{i=0}^{M-1}f_{i}(x)$ be separable in $M\in\mathbb{N}$
continuously differentiable components $f_{i}\in\mathcal{S}_{\beta}$
satisfying, for some positive constants $A$ and $B$,

$|\nabla\\!f_{i}(x)|\leq A+B|\nabla\\!f(x)|\,,~{}\forall
x\in\mathbb{R}^{d}\,.$ (14)

Choose any stepsize sequence $\bm{\eta}\in\ell_{2}$ such that
$\sum_{t=0}^{\infty}\eta_{t}=\infty$ with $\eta_{t}>0$ at all times, and any
$\mathbf{v}$ such that

$|v_{t}|\leq\eta_{\left\lfloor t/M\right\rfloor}(C+D|\nabla\\!f(x_{t})|)\,,$
(15)

for some positive constants $C$ and $D$. Then, the update rule

$\displaystyle\pi_{t}(f,x_{t})=-\eta_{\left\lfloor
t/M\right\rfloor}(\nabla\\!f_{t\bmod M}(x_{t})+v_{t})\,,$ (16)

is convergent according to (4), that is, $\bm{\pi}(f,\mathbf{x})\in\Gamma(f)$.

The proof of Theorem 2 adapts the analysis of [23, Proposition 2]by accounting
for the contribution of $v_{t}$ as per (16). To ensure (15), while endowing
our learned algorithms with the ability to react to input features, we propose
using

$\displaystyle v_{t}=\eta_{\left\lfloor
t/M\right\rfloor}|z_{t}||\omega_{t}|^{-1}\omega_{t}\,,\quad\mathbf{z}=\mathbf{Z}(\bm{\delta}^{x_{0}})\,,$
(17)
$\displaystyle\omega_{t}=\Omega_{t}(x_{t:0},\nabla\\!f_{\tau}(x_{t}),\ldots,\nabla\\!f_{0}(x_{0}),f_{\tau}(x_{t}),\ldots,f_{0}(x_{0}))\,,$

where $\tau=t\bmod M$, and $\bm{\Omega}:\ell\rightarrow\ell$ and
$\mathbf{Z}\in\mathcal{L}_{2}$ are operators to be freely designed. In this
way, similarly to (13), we have $|v_{t}|=\eta_{\left\lfloor
t/M\right\rfloor}|z_{t}|\leq\eta_{\left\lfloor
t/M\right\rfloor}\max_{t\in\mathbb{N}}~{}z_{t}$, and we thus satisfy (15) with
$C=\max_{t\in\mathbb{N}}~{}z_{t}$ and $D=0$.

The update rule (16) cycles through the gradients $\nabla\\!f_{i}$ and applies
an innovation signal to be learned. Coherently with standard SGD, Theorem 2
guarantees asymptotic convergence of the learned algorithm – despite the
additional presence of an innovation $\mathbf{v}$ satisfying (15). Moreover,
while (15) may restrict the set of $\bm{\pi}(f,\mathbf{x})\in\Gamma(f)$ that
our parametrization can achieve, we proceed to illustrate the rich
expressivity of learning over innovations modeled as (17).

##  IV Experiments

Motivated by [15], we consider the problem of learning to optimize the
parameters $x_{t}$ of a shallow NN for image classification with the MNIST
dataset.222The source code that reproduces our numerical examples is available
at https://github.com/andrea-martin/ConvergentL2O. Further, we investigate how
our optimizer generalizes to different network activation functions and
different initial parameter distribution $\mathcal{X}_{0}$.

We model our trainable optimizer as per (16)-(17), using a recurrent
equilibrium network333This architecture, which subsumes several existing deep
NN models, proves convenient as it provides a finite-dimensional approximation
of $\mathcal{L}_{2}$ without imposing any constraint on the parameter vector
$\theta$. [22] with depth of $r=3$ layers and internal state dimension $n=3$
as a model for $\mathbf{Z}(\theta)\in\mathcal{L}_{2}$, and a multilayer
perceptron (MLP) with $2$ hidden layers as a model for $\bm{\Omega}(\theta)$.
We instead model the shallow NN as a simple perceptron that, given a
vectorized image $s$ corresponding to a handwritten digit as input, predicts
the label $\hat{l}(s,x_{t})$ according to the criterion:

$\operatorname*{arg\,max}_{i}~{}o(s,x_{t})=\operatorname*{arg\,max}_{i}~{}[\operatorname{tanh}(sW_{t}^{\top}+b_{t})]_{i}\,,$
(18)

where $W_{t}$ and $b_{t}$ are the trainable parameters of the classifier,
whose scalar entries are collected in $x_{t}$, and $[\cdot]_{i}$ denotes the
$i$-th entry of a vector. Based on (18), we also define the classification
loss $g(s,l,x_{t})$ on an image $s$ as the cross entropy loss between the
softmax transformation of $o(s,x_{t})$ and $l$, the true label of $s$, encoded
as a one-hot vector.

To encourage our learned updates (16) to promote the accuracy of the
classifier predictions (18) after $T=50$ iterations of (3), we consider the
meta-loss (7) with $\alpha_{t}=0$, $\gamma_{t}=0.95^{T-t}$, and let $f(x_{t})$
be the cross entropy loss on the training dataset. For fixed parameters
$\theta$ of $\mathbf{Z}$ and $\bm{\Omega}$, we approximate (6a) by repeating
the training of $W_{t}$ and $b_{t}$ in (18) for $10$ times, using different
initial parameters sampled from a distribution $\mathcal{X}_{0}$ that is
uniform in the interval $[0,0.01]$. Motivated by our results in Theorem 2, we
estimate $f(x_{t})$ and $\nabla\\!f(x_{t})$ in (11b) using random minibatches
of 128 images drawn sequentially. Then, we perform the minimization of (6a)
using Adam with a learning rate of $0.01$. We use $80\%$ of the MNIST training
dataset for optimizing $\theta$.

After $40$ training epochs, we freeze the value of $\theta$, and we benchmark
the performance of our learned optimizer against standard optimizers including
Adam, SGD, Nesterov’s accelerated gradient (NAG), and RMSprop. To assess the
generalization capabilities of (17), we use the remaining $20\%$ of the
training dataset to train a shallow NN that: $1)$ uses
$\operatorname{sigmoid}$ or $\operatorname{ReLU}$ as activations in (18), and
$2)$ whose initial parameters $[x_{0}]_{i}$ are sampled from independent and
identically distributed Gaussian distributions $\mathcal{N}(0,0.1)$.

We report training curves for our learned optimizer and for classical hand-
crafted algorithms in Figure 1 and the corresponding average test accuracy in
the tables below.444Following [15] for each considered scenario, we tune the
learning rate of each baseline optimizer to minimize the training loss
$f(x_{t})$, and we adopt default values for additional hyperparameters.

Step $t=20$ | $\operatorname{tanh}$ | $\operatorname{sigmoid}$ | $\operatorname{ReLU}$
---|---|---|---
Adam | $72.3\pm 3.9\%$ | $76.4\pm 1.7\%$ | $58.8\pm 11.4\%$
SGD | $45.2\pm 3.7\%$ | $79.8\pm 1.5\%$ | $49.8\pm 9.6\%$
NAG | $79.2\pm 2.0\%$ | $81.2\pm 0.9\%$ | $53.1\pm 9.9\%$
RMSprop | $69.8\pm 3.6\%$ | $73.7\pm 1.8\%$ | $60.3\pm 10.1\%$
ConvergentL2O | $\mathbf{87.0\pm 0.5}\%$ | $\mathbf{86.8\pm 0.6}\%$ | $\mathbf{86.2\pm 0.6}\%$

Step $t=100$ | $\operatorname{tanh}$ | $\operatorname{sigmoid}$ | $\operatorname{ReLU}$
---|---|---|---
Adam | $87.2\pm 2.2\%$ | $88.1\pm 0.3\%$ | $69.2\pm 12.7\%$
SGD | $82.1\pm 1.0\%$ | $88.1\pm 0.4\%$ | $74.9\pm 14.0\%$
NAG | $87.7\pm 0.7\%$ | $88.3\pm 0.4\%$ | $76.7\pm 13.2\%$
RMSprop | $84.4\pm 2.0\%$ | $85.6\pm 0.6\%$ | $75.1\pm 9.3\%$
ConvergentL2O | $\mathbf{88.4\pm 0.2}\%$ | $\mathbf{88.4\pm 0.3}\%$ | $\mathbf{87.6\pm 0.3}\%$

(a) Activation function: $\operatorname{tanh}$.  (b) Activation function:
$\operatorname{sigmoid}$.  (c) Activation function: $\operatorname{ReLU}$.

Figure 1: Training curves of learned and hand-crafted optimizers; shaded areas
and solid lines denote standard deviations and mean values, respectively.

In all considered scenarios, learned algorithms excel in finding shortcuts,
that is, in steering $x_{0}$ to a good local minimum within a few iterations;
this is reflected in the superior test accuracy achieved after only $t=20$
optimization steps. As the gradient norm diminishes, our learned algorithm
favors simple gradient-based updates to ensure convergence, as predicted by
Theorem 2. Remarkably, our algorithm generalizes well also to the optimization
landscape of the $\operatorname{ReLU}$ classifier, which may prove
particularly challenging, as highlighted in [15], due to its structural
difference with respect to $\operatorname{tanh}$ in (18). As predicted by our
theoretical results, none of our simulations exhibited the divergence
phenomena reported by [18] for the L2O approach of [15].

##  V Conclusion

In this paper, we have introduced a methodology for learning over all
convergent update rules for smooth non-convex optimization, thus enabling the
automated synthesis of more reliable, efficient, and reconfigurable
algorithms. By synergizing nonlinear system theory with the emerging L2O
paradigm, we aimed to close the gap between offline, theory-based algorithm
design and adaptable, example-driven approaches that are the hallmark of ML.

Our numerical results corroborate the transfer learning capabilities of L2O
algorithms to tasks structurally different from those in training; we believe
the control-theoretic interpretation that we have embraced will help
understand this aspect through formal robust performance analysis. Towards an
increasingly cohesive integration of algorithms with closed-loop cyber-
physical systems, further avenues for future research include extending our
framework to online and time-varying scenarios, distributed and federated
learning, and constrained optimization.

## References

  * [1] S. P. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [2] S. Fujishige, _Submodular functions and optimization_. Elsevier, 2005.
  * [3] B. T. Polyak, “Some methods of speeding up the convergence of iteration methods,” _Ussr computational mathematics and mathematical physics_ , vol. 4, no. 5, pp. 1–17, 1964.
  * [4] Y. E. Nesterov, “A method of solving a convex programming problem with convergence rate ${O}\bigl{(}\frac{1}{k^{2}}\bigr{)}$,” in _Doklady Akademii Nauk_ , vol. 269, no. 3. Russian Academy of Sciences, 1983, pp. 543–547.
  * [5] Y. Bengio, “Practical recommendations for gradient-based training of deep architectures,” in _Neural Networks: Tricks of the Trade: Second Edition_. Springer, 2012, pp. 437–478.
  * [6] F. Dörfler, Z. He, G. Belgioioso, S. Bolognani, J. Lygeros, and M. Muehlebach, “Towards a systems theory of algorithms,” _arXiv preprint arXiv:2401.14029_ , 2024.
  * [7] L. Lessard, B. Recht, and A. Packard, “Analysis and design of optimization algorithms via integral quadratic constraints,” _SIAM Journal on Optimization_ , vol. 26, no. 1, pp. 57–95, 2016.
  * [8] A. Sundararajan, B. Van Scoy, and L. Lessard, “Analysis and design of first-order distributed optimization algorithms over time-varying graphs,” _IEEE Transactions on Control of Network Systems_ , vol. 7, no. 4, pp. 1597–1608, 2020.
  * [9] L. Lessard, “The analysis of optimization algorithms: A dissipativity approach,” _IEEE Control Systems Magazine_ , vol. 42, no. 3, pp. 58–72, 2022.
  * [10] B. Goujaud, A. Dieuleveut, and A. Taylor, “On fundamental proof structures in first-order optimization,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_. IEEE, 2023, pp. 3023–3030.
  * [11] C. Scherer and C. Ebenbauer, “Convex synthesis of accelerated gradient algorithms,” _SIAM Journal on Control and Optimization_ , vol. 59, no. 6, pp. 4615–4645, 2021.
  * [12] X. Chen and E. Hazan, “Online control for meta-optimization,” in _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * [13] A. Hauswirth, S. Bolognani, G. Hug, and F. Dörfler, “Optimization algorithms as robust feedback controllers,” _arXiv preprint arXiv:2103.11329_ , 2021.
  * [14] G. Belgioioso, D. Liao-McPherson, M. H. de Badyn, S. Bolognani, R. S. Smith, J. Lygeros, and F. Dörfler, “Online feedback equilibrium seeking,” _arXiv preprint arXiv:2210.12088_ , 2022.
  * [15] M. Andrychowicz, M. Denil, S. Gomez, M. W. Hoffman, D. Pfau, T. Schaul, B. Shillingford, and N. De Freitas, “Learning to learn by gradient descent by gradient descent,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [16] T. Chen, X. Chen, W. Chen, H. Heaton, J. Liu, Z. Wang, and W. Yin, “Learning to optimize: A primer and a benchmark,” _Journal of Machine Learning Research_ , vol. 23, no. 189, pp. 1–59, 2022.
  * [17] K. Li and J. Malik, “Learning to optimize,” in _International Conference on Learning Representations_ , 2017.
  * [18] ——, “Learning to optimize neural nets,” _arXiv preprint arXiv:1703.00441_ , 2017.
  * [19] H. Heaton, X. Chen, Z. Wang, and W. Yin, “Safeguarded learned convex optimization,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 37, no. 6, 2023, pp. 7848–7855.
  * [20] J. Miller and M. Hardt, “Stable recurrent models,” _arXiv preprint arXiv:1805.10369_ , 2018.
  * [21] K.-K. K. Kim, E. R. Patrón, and R. D. Braatz, “Standard representation and unified stability analysis for dynamic artificial neural network models,” _Neural Networks_ , vol. 98, pp. 251–262, 2018.
  * [22] M. Revay, R. Wang, and I. R. Manchester, “Recurrent equilibrium networks: Flexible dynamic models with guaranteed stability and robustness,” _IEEE Transactions on Automatic Control_ , 2023.
  * [23] D. P. Bertsekas and J. N. Tsitsiklis, “Gradient convergence in gradient methods with errors,” _SIAM Journal on Optimization_ , vol. 10, no. 3, pp. 627–642, 2000.
  * [24] L. Furieri, C. L. Galimberti, and G. Ferrari-Trecate, “Neural system level synthesis: Learning over all stabilizing policies for nonlinear systems,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_. IEEE, 2022, pp. 2765–2770.

###### Proof:

Let $\nabla\\!f(x_{t})=\nabla_{\\!t}$ for compactness. For any
$t\in\mathbb{N}$ and $f\in\mathcal{S}_{\beta}$, it holds that $f(x_{t+1})\leq
f(x_{t})+\nabla_{\\!t}^{\top}(x_{t+1}-x_{t})+\frac{\beta}{2}|x_{t+1}-x_{t}|^{2}$.
Substituting $x_{t+1}-x_{t}=v_{t}-\eta\nabla_{\\!t}$ according to (8) yields

$f(x_{t+1})\leq
f(x_{t})-\eta|\nabla_{\\!t}|^{2}+\nabla_{\\!t}^{\top}v_{t}+\frac{\beta}{2}|v_{t}-\eta\nabla_{\\!t}|^{2}\,.$
(19)

Observe that for any $a,b\in\mathbb{R}^{d}$ and any $\epsilon>0$, we have that
$a^{\top}b\leq|a||b|\leq\frac{|a|^{2}}{2\epsilon}+\frac{\epsilon|b|}{2}$ and
$\frac{1}{2}|a-b|^{2}\leq|a|^{2}+|b|^{2}$ thanks to the Cauchy-Schwarz and
Young’s inequalities. Hence, we can upper-bound the right-hand side of (19) by

$f(x_{t})-\eta|\nabla_{\\!t}|^{2}+\frac{|\nabla_{\\!t}|^{2}}{2\epsilon}+\frac{\epsilon|v_{t}|^{2}}{2}+\beta\left(|v_{t}|^{2}+\eta^{2}|\nabla_{\\!t}|^{2}\right)\,.$

Collecting terms and letting $\rho=2\eta\epsilon(1-\beta\eta)-1$, we obtain

$\frac{\rho}{2\epsilon}|\nabla_{\\!t}|^{2}\leq
f(x_{t})-f(x_{t+1})+\left(\frac{\epsilon}{2}+\beta\right)|v_{t}|^{2}\,.$ (20)

As $1-\beta\eta>0$ by assumption, choosing any
$\epsilon>\frac{1}{2\eta(1-\beta\eta)}>0$ ensures that $\rho>0$. Then, summing
(20) with $t$ ranging from $0$ to $T\in\mathbb{N}$ and observing that the term
$f(x_{t})-f(x_{t+1})$ telescopes and that
$f(x_{T})\geq\inf_{x\in\mathbb{R}^{d}}f(x)$, we obtain

$\sum_{t=0}^{T}|\nabla_{\\!t}|^{2}\leq\frac{2\epsilon}{\rho}(f(x_{0})-\inf_{x\in\mathbb{R}^{d}}f(x))+\frac{\epsilon}{\rho}\left(\epsilon+2\beta\right)\sum_{t=0}^{T}|v_{t}|^{2}\,.$

As $f$ is bounded from below, the term
$f(x_{0})-\inf_{x\in\mathbb{R}^{d}}f(x)$ is finite and non-negative. Hence, as
$\mathbf{v}\in\ell_{2}$ by assumption, taking the limit of $T$ to $\infty$
yields $\left\lVert\nabla\\!f(\mathbf{x})\right\rVert^{2}<\infty$, which
concludes the proof. ∎

###### Proof:

For any $f\in\mathcal{S}_{\beta}$ and any $\bm{\pi}(f,\mathbf{x})$ complying
with (6c), select the operator $\mathbf{V}$ as

$\mathbf{V}(\bm{\delta}^{x_{0}})=\eta\nabla\\!f(\mathbf{x}_{\bm{\pi}})+\mathbf{u}_{\bm{\pi}}\,.$
(21)

Since $\bm{\pi}$ complies with (6c), we have that
$\nabla\\!f(\mathbf{x}_{\bm{\pi}})\in\ell^{d}_{2}$ and
$\mathbf{u}_{\bm{\pi}}\in\ell^{d}_{2}$ for every $x_{0}\in\mathbb{R}^{d}$
according to (5). Hence, we conclude that
$\mathbf{V}(\bm{\delta}^{x_{0}})\in\ell^{d}_{2}$ for every
$x_{0}\in\mathbb{R}^{d}$ and every $f\in\mathcal{S}_{\beta}$ as the sum of two
signals in $\ell_{2}$ lies in $\ell_{2}$.

It remains to prove that the closed-loop mapping (10) is equivalent to (9) for
$\mathbf{V}$ chosen as per (21). We prove this fact by induction with a
similar proof method as [24, Theorem 2]. For the closed-loop mapping (9), we
define
$\bm{\Psi}=(\bm{\Psi}^{\mathbf{x}},\bm{\Psi}^{\mathbf{u}},\bm{\Psi}^{\\!\bm{\nabla}})$
such that
$\bm{\bm{\Psi}^{\mathbf{x}}}(f,\bm{\delta}^{x_{0}})=\mathbf{x}_{\bm{\pi}}$,
$\bm{\bm{\Psi}^{\mathbf{u}}}(f,\bm{\delta}^{x_{0}})=\mathbf{u}_{\bm{\pi}}$ and
$\bm{\bm{\Psi}^{\\!\bm{\nabla}}}(f,\bm{\delta}^{x_{0}})=\nabla
f(\mathbf{x}_{\bm{\pi}})$. Similarly, for the closed-loop mapping (10)
corresponding to $\mathbf{V}(\bm{\delta}^{x_{0}})$ in (21), we define
$\bm{\Phi}=(\bm{\Phi}^{\mathbf{x}},\bm{\Phi}^{\mathbf{u}},\bm{\Phi}^{\\!\bm{\nabla}})$
such that $\bm{\bm{\Phi}^{\mathbf{x}}}(f,\bm{\delta}^{x_{0}})=\mathbf{x}$,
$\bm{\bm{\Phi}^{\mathbf{u}}}(f,\bm{\delta}^{x_{0}})=-\eta\nabla\\!f(\mathbf{x})+\mathbf{V}(\bm{\delta}^{x_{0}})$
and
$\bm{\bm{\Phi}^{\\!\bm{\nabla}}}(f,\bm{\delta}^{x_{0}})=\nabla\\!f(\mathbf{x})$.
For the inductive step, we assume that, for any $j\in\mathbb{N}$, we have
$\Phi^{u}_{i}=\Psi^{u}_{i}$, $\Phi^{x}_{i}=\Psi^{x}_{i}$ and
$\Phi^{\\!\nabla}_{i}=\Psi^{\nabla}_{i}$ for all $i\in\mathbb{N}$ with $0\leq
i\leq j$. By the algorithm definition (2) it holds that

$\Phi^{x}_{j+1}=\Phi^{x}_{j}+\Phi^{u}_{j}+I,~{}~{}\Psi^{x}_{j+1}=\Psi^{x}_{j}+\Psi^{u}_{j}+I\,,$

which ensures that $\Phi^{x}_{j+1}=\Psi^{x}_{j+1}$ since by inductive
assumption $\Phi^{x}_{i}=\Psi^{x}_{i}$ and $\Phi^{u}_{i}=\Psi^{u}_{i}$ for
every $0\leq i\leq j$. Hence, we also have that
$\Phi^{\\!\nabla}_{j+1}=\nabla\\!f(\Phi^{x}_{j+1})=\nabla\\!f(\Psi^{x}_{j+1})=\Psi^{\\!\nabla}_{j+1}$.
For $\mathbf{V}$ chosen as per (21), it holds that

$\Phi_{j+1}^{u}=-\eta\nabla\\!f(\Phi^{x}_{j+1})+\eta\nabla\\!f(\Psi^{x}_{j+1})+\Psi_{j+1}^{u}\,,$

which simplifies to $\Phi^{u}_{j+1}=\Psi^{u}_{j+1}$. For the base case $j=0$,
by inspection of (3), we have that $\Phi_{0}^{x}=\Psi_{0}^{x}=I$. Hence,
$\Phi^{\\!\nabla}_{0}=\nabla\\!f(\Phi_{0}^{x})=\nabla\\!f(\Psi_{0}^{x})=\Psi^{\\!\nabla}_{0}$.
Last, we also have
$\Phi^{u}_{0}=-\eta\nabla\\!f(\Phi^{x}_{0})+\eta\nabla\\!f(\Psi^{x}_{0})+\Psi_{0}^{u}=\Psi_{0}^{u}$.
∎

###### Proof:

If $0<\eta<\beta^{-1}$, we know by Lemma 1 that any algorithm in the form
$\bm{\pi}(f,\mathbf{x})=-\eta\nabla f(\mathbf{x})+\mathbf{v}$ with
$\mathbf{v}\in\ell_{2}$ belongs to $\Sigma(f)$ for any
$f\in\mathcal{S}_{\beta}$. Since $\mathbf{V}\in\mathcal{L}_{2}$ and
$\bm{\delta}^{x_{0}}\in\ell_{2}$, we then have that
$\mathbf{v}=\mathbf{V}(\bm{\delta}^{x_{0}})\in\ell_{2}$, that is, any
$\mathbf{V}\in\mathcal{L}_{2}$ leads to a feasible solution of (6). Hence, the
constraint (6c) becomes redundant, and can thus be removed from (11), after
plugging the update rule (10) in (6b).

Last, Lemma 2 ensures that for any $x_{0}\in\mathbb{R}^{d}$,
$f\in\mathcal{S}_{\beta}$, and $\bm{\pi}(f,\mathbf{x})\in\Sigma(f)$, there
exists $\mathbf{V}\in\mathcal{L}_{2}$ such that the update rule in (10)
reproduces the trajectories of $\bm{\pi}(f,\mathbf{x})$. In turn, this implies
that any feasible solution of (6) is considered in (11), from which the
equivalence follows. ∎

###### Proof:

Rolling out (2) for $M$ steps, starting from any $t$ such that $t\bmod M=0$,
and using the update rule (16) with $\tau=\left\lfloor t/M\right\rfloor$, we
obtain the iteration:

$x_{t+M}=x_{t}-\eta_{\tau}\nabla\\!f(x_{t})+\eta_{\tau}w_{t}-\eta_{\tau}\sum_{i=0}^{M-1}v_{t+i}\,,$
(22)

where the term $w_{t}$, which represents an error in the gradient direction
relative to the gradient iteration (8), is given by
$w_{t}=\sum_{i=1}^{M-1}\nabla\\!f_{i}(x_{t})-\nabla\\!f_{i}(x_{t+i})$. Under
the assumptions of Lemma 2, we have that

$\left|\sum_{i=0}^{M-1}v_{t+i}\right|\leq\sum_{i=0}^{M-1}|v_{t+i}|\leq\eta_{\tau}M(C+D|\nabla\\!f(x_{t})|)\,;$
(23)

we now proceed to show that a similar bound also holds for $|w_{t}|$. By the
triangle inequality and observing that $f_{i}\in\mathcal{S}_{\beta}$ ensures
that $\nabla\\!f_{i}$ is $\beta$-Lipschitz continuous, we have that:

$\displaystyle|w_{t}|$
$\displaystyle\leq\\!\sum_{i=1}^{M-1}\\!|\nabla\\!f_{i}(x_{t})-\nabla\\!f_{i}(x_{t+i})|\leq\beta\\!\sum_{i=1}^{M-1}\\!|x_{t}-x_{t+i}|$
$\displaystyle=\eta_{\tau}\beta|\nabla\\!f_{0}(x_{t})+v_{t}|+\beta\sum_{i=2}^{M-1}|x_{t}-x_{t+i}|\,,$
(24)

where the term $\sum_{i=2}^{M-1}|x_{t}-x_{t+i}|$ is given by:

$\eta_{\tau}\sum_{i=2}^{M-1}\left|\nabla\\!f_{0}(x_{t})+v_{t}+\sum_{j=1}^{i-1}\nabla\\!f_{j}(x_{t+j})+v_{t+j}\right|\,.$
(25)

Then, we observe that
$\eqref{eq:norm_bound_error_gradient_direction_double_sum}$ can be upper-
bounded by

$\displaystyle\eta_{\tau}(M-2)|\nabla\\!f_{0}(x_{t})+v_{t}|+\eta_{\tau}\sum_{i=2}^{M-1}\sum_{j=1}^{i-1}|\nabla\\!f_{j}(x_{t+j})+v_{t+j}|$
$\displaystyle\leq\\!\eta_{\tau}(M-2)\\!\left(\\!|\nabla\\!f_{0}(x_{t})+v_{t}|+\\!\\!\sum_{i=1}^{M-2}\\!|\nabla\\!f_{i}(x_{t+i})+v_{t+i}|\\!\right)\\!\\!\,.$

By combining the inequality above with (24), we deduce that the following
upper-bound to $|w_{t}|$ holds:

$\displaystyle\eta_{\tau}\beta(M-1)\\!\left(\\!|\nabla\\!f_{0}(x_{t})|+\\!\sum_{i=0}^{M-2}|v_{t+i}|\\!+\\!\sum_{i=1}^{M-2}\\!|\nabla\\!f_{i}(x_{t+i})|\\!\right)\\!\\!\,.$

Moreover, for any $i=1,\ldots,M-2$, it holds that:

$\displaystyle|\nabla\\!f_{i}(x_{t+i})|\\!=\\!|\nabla\\!f_{i}(x_{t+i-1}-\eta_{\tau}(\nabla\\!f_{i-1}(x_{t+i-1})+v_{t+i-1}))|$
$\displaystyle\leq|\nabla\\!f_{i}(x_{t+i-1})|+\eta_{\tau}\beta|\nabla\\!f_{i-1}(x_{t+i-1})|+\eta_{\tau}\beta|v_{t+i-1}|\,.$

By iterating the reasoning above, we have that $|\nabla\\!f_{i}(x_{t+i})|$ is
upper-bounded by $\sum_{j=0}^{i}E|\nabla\\!f_{j}(x_{t})|+F|v_{t+j}|$ for
appropriately defined positive constant $E$ and $F$. Finally, leveraging (14)
and (23), we conclude that there exists positive constant $P$ and $Q$ such
that
$\left|w_{t}-\sum_{i=0}^{M-1}v_{t+i}\right|\leq\eta_{\tau}(P+Q|\nabla\\!f(x_{t})|)$.
Having established this upper bound, the results of Lemma 2 follow from
applying [23, Proposition 1] to the recursion (22), since $f$ is bounded from
below by assumption. ∎