# On the Robustness of Text Vectorizers

Rémi Catellier  Samuel Vaiter  Damien Garreau

###### Abstract

A fundamental issue in machine learning is the robustness of the model with
respect to changes in the input. In natural language processing, models
typically contain a first embedding layer, transforming a sequence of tokens
into vector representations. While the robustness with respect to changes of
continuous inputs is well-understood, the situation is less clear when
considering discrete changes, for instance replacing a word by another in an
input sentence. Our work formally proves that popular embedding schemes, such
as concatenation, TF-IDF, and Paragraph Vector (a.k.a. doc2vec), exhibit
robustness in the Hölder or Lipschitz sense with respect to the Hamming
distance. We provide quantitative bounds for these schemes and demonstrate how
the constants involved are affected by the length of the document. These
findings are exemplified through a series of numerical examples.

Natural Language Processing, Theory, Robustness, Embedding, Tokenization

##  1 Introduction

Recent advances in natural language processing (NLP) have exceeded all
expectations. In particular, the advent of large language models such as BERT
(Devlin et al., 2018) and GPT (Brown et al., 2020) are transforming radically
the way we interact with computers. They typically rely on a deep neural
network (DNN) architecture and are trained on a variety of tasks such as
sentiment analysis, translation, and text summarization.

A known issue with DNNs is the existence of _adversarial examples_ : examples
modified in order to radically change the output of the model. Initially
popularized in the context of image classification (Szegedy et al., 2014),
such examples also exist in NLP and a flourishing literature exists on this
topic (Zhang et al., 2020). This problem has sparked a tremendous interest
into the _robustness_ of models with respect to small changes in the input. In
this paper, we focus on the robustness of the _vectorization_ NLP pipelines:
the transformation of the input document into a vector representation. We will
consider documents as ordered sequences of tokens, not necessarily
corresponding to words. For instance, GPT 2 uses Byte Pair encoding (Gage,
1994; Sennrich et al., 2016), which relies on tokens corresponding to sub-
words.

As far as we reckon, there are essentially three main schools of thought when
it comes to vectorization:
_(i)_ concatenation of vectors corresponding to each token of the document.
These vectors are often called _word vectors_ when the tokens are individual
words. They can either be one-hot representations of the tokens, or obtained
by a mapping learned from data. A celebrated approach to produce word vectors
is word2vec (Mikolov et al., 2013a, b), which transports semantic properties
to the embedding space. Many other methods exist, such as GloVe (Pennington et
al., 2014), EMF (Li et al., 2015), WordPiece (Wu et al., 2016), FastText
(Bojanowski et al., 2017), and ELMo (Peters et al., 2018). Positional
information is typically added to the token embeddings.
_(ii)_ TF-IDF (term frequency - inverse document frequency), taking words as
tokens and simply considering the frequencies of each individual word in the
document. These frequencies are reweighted by an overall importance term to
take into account the lesser importance of frequently appearing words such as
articles. This is the historical approach to text vectorization (Luhn, 1957;
Jones, 1972).
_(iii)_ _ad hoc_ approaches. Notably, Paragraph Vector (also known as doc2vec
(Le & Mikolov, 2014)) extends the ideas of word2vec. Although we will focus on
doc2vec in this work, we emphasize that there exists other _ad hoc_
approaches, such as skip-thought vectors (Kiros et al., 2015), quick-thought
(Logeswaran & Lee, 2018), or universal sentence encoder (Cer et al., 2018).

_A priori_ , vectorizers are not designed to be robust to small changes. Even
when modifying a single word of the input document, the embedding could change
drastically. Thus, we ask the following question:

> _Are text vectorizers provably robust with respect to modifying a small
> subset of the document?_

Typical notions of robustness in machine learning deals with _continuous_
input data: changing slightly the observation means that for instance its
$\ell^{2}$-norm evolves infinitesimally. The challenge of our analysis is the
fundamentally _discrete_ nature of text data. Changing a word in a document is
usually not innocuous – one can think of extreme cases where the meaning of
this word is flipped – and vectorizers sensitive to the semantics of input
documents should capture this phenomenon. Nevertheless, we show that the
answer is positive for all vectorizers that we study. Another difficulty is
that the mathematical formalization of some of these vectorizers was not the
main concern of the community. A necessary first step is thus to give an
unequivocal definition of our objects of interest.

#### Contributions.

In this paper, we analyze the robustness of vectorizers as their local
regularity (Lipschitz, Hölder) with respect to the Hamming distance (Section
2). We prove:
$\bullet$ the $1/2$-Hölder continuity of concatenation of token and positional
embeddings (Proposition 3.1);
$\bullet$ the Lipschitz continuity of TF-IDF (Proposition 4.1), and the
$1/2$-Hölder continuity of it normalized variant (Proposition 4.2);
$\bullet$ the Lipschitz continuity of doc2vec (Theorem 5.1). As a necessary
step to derive the latter, we make two new mathematical contributions (see
Appendix), we propose:
$\bullet$ a local Lipschitz analysis of the softmax (Theorem H.6);
$\bullet$ a Grönwall–Bellman–Bahouri result (Theorem G.1) needed when casting
the doc2vec analysis as an ODE problem. The code for all experiments of the
paper is available at https://github.com/dgarreau/vectorizer-robustness.

#### Related work.

_(Adversarial examples)._ A major motivation for studying robustness is its
impact on the existence of adversarial examples. In the case of DNNs,
robustness often means Lipschitz continuity with respect to the inputs. For
instance, one can show that a network having a small Lipschitz constant
prevents the existence of small adversarial changes. More precisely, Hein &
Andriushchenko (2017) provide a lower bound on the norm of the input
manipulation needed to change the classifier decision inversely proportional
to the Lipschitz constant of the network. This was later extended by Weng et
al. (2018b) to DNNs with ReLU activations. Quantitatively, Weng et al. (2018a)
show that fully connected layers have a Lipschitz constant potentially as
large as the operator norm of the weight matrix. From a practical point of
view, it has also been noticed that enforcing the Lipschitz constants of the
layers to remain low does improve the robustness (Cisse et al., 2017).
_(Generalization & interpolation)._ It is known that robust algorithms
generalize better. In particular, Xu & Mannor (2012) derive generalization
bounds for generic algorithms depending in their robustness. The definition of
robustness here includes Lipschitz continuous DNNs. More recently, Bubeck &
Sellke (2021) extending (Bubeck et al., 2020) showed that in order to train
Lipschitz continuous models, one has to take a large number of parameters.
_(Theory of vectorizers)._ Surprisingly, the robustness of vectorizers
received little attention until now on the theoretical side, and all previous
works on robustness assume _continuous_ input. Nevertheless, there exist some
theoretical works on similar problems. Most notably, Arora et al. (2016)
analyze a large class of word vectorizers and explain how the intriguing
alignment properties observed experimentally appear.

#### Notations.

For $u\in\mathbb{R}^{p}$, we denote by $\left\lVert u\right\rVert$ its
Euclidean norm. Let $g:\mathbb{R}\times\mathbb{R}^{d}\to\mathbb{R}$ be a
function. The derivative in the time variable ($\mu$) is denoted by
$\partial_{\mu}g$ whereas $\nabla g$ (resp. $\nabla^{2}g$) denotes the
Jacobian (resp. the Hessian) of $g$ in the space variable. We let
$\mathds{1}=(1,\ldots,1)^{\top}\in\mathbb{R}^{d}$. For a matrix $R$,
$\sigma_{\min}(R)$ is its smallest singular value. For a given set
$\mathcal{S}$, $\left\lvert\mathcal{S}\right\rvert$ is its cardinal.

##  2 Framework

Let us now present the mathematical framework in which we perform our
analysis. We consider tokens from a finite dictionary $\mathcal{D}$,
identified as $[D]\vcentcolon=\\{1,\ldots,D\\}$. A _document_ $x$ built on
$\mathcal{D}$ is a finite sequence of elements of $\mathcal{D}$, and we write
$[D]^{*}$ for the set of all documents. Thus the central object of our work, a
vectorizer, is simply a mapping $\varphi:[D]^{*}\to\mathbb{R}^{d}$, where $d$
is the dimension of the embedding. The _length_ of $x$ will be denoted by
$T(x)$, and therefore $x$ can be written as $(x_{1},\ldots,x_{T(x)})$. The set
of all documents over $\mathcal{D}$ of length $T$ will be denoted
$[D]^{T}\subset[D]^{*}$. When there is no ambiguity, we remove the dependency
in $x$ from our notation, _e.g._ , $T(x)$ becomes $T$.

As discussed in the related work, robustness is often synonym with _Lipschitz
continuity_ of the model – distance between outputs lies within a constant
factor of the distance between inputs. As distance between input documents $x$
and $\tilde{x}$ of same length, we consider the _Hamming distance_ , which is
the number of indices such that $x_{t}$ and $\tilde{x}_{t}$ differ:

$\operatorname{d_{H}}(x,\tilde{x})\vcentcolon=\left\lvert\\{t\in[T]:x_{t}\neq\tilde{x}_{t}\\}\right\rvert\,.$

The distance between outputs will simply be measured by the Euclidean norm in
$\mathbb{R}^{d}$. In definitive, for a given document length $T$, what we call
Lipschitz continuity of the vectorizer $\varphi$ can be written as

$\forall
x,\tilde{x}\in[D]^{T},\quad\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert\leq
C\operatorname{d_{H}}(x,\tilde{x})\,,$ (1)

where $C$ is called the Lipschitz constant. Another way to quantify robustness
is to allow for an exponent in Eq. (1):

$\forall
x,\tilde{x}\in[D]^{T},\quad\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert\leq
C\operatorname{d_{H}}(x,\tilde{x})^{\beta}\,,$ (2)

with $1\geq\beta>0$. This is known as Hölder continuity, and coincides with
Lipschitz continuity whenever $\beta=1$. While it is known that Lipschitz
continuity implies Hölder continuity on the real line when $\beta\leq 1$, this
is not the case here, since $\operatorname{d_{H}}$ takes values in
$\mathbb{N}$. Thus in our setting, Lipschitz continuity is a weaker notion of
robustness than Hölder continuity.

Often we obtain more precise results, depending explicitly on the set of
indices such that the documents differ. To this extent, for a given subset
$\mathcal{S}$ of $[T]$, we define the _set of $\mathcal{S}$-close documents_
$B_{\mathcal{S}}(x)$ of $x\in[D]^{T}$ as

$B_{\mathcal{S}}(x)=\\{\tilde{x}\in[D]^{T}\,:\,x_{i}=\tilde{x}_{i}\text{ for
}i\not\in\mathcal{S}\\}\,.$

Said alternatively, $\tilde{x}\in B_{\mathcal{S}}(x)$ if it is obtained by
replacing the tokens of $x$ with indices belonging to $\mathcal{S}$ by
arbitrary tokens in $\mathcal{D}$. We note that $B_{\mathcal{S}}(x)$ is a
subset of the Hamming ball of radius $\left\lvert S\right\rvert$. Let us
consider for instance the document $x=$ “the quick brown fox” and the set of
perturbed indices $\mathcal{S}=\\{2,3\\}$ Here, $x$ has length $T=4$,
$\left\lvert\mathcal{S}\right\rvert=2$, and an element of $B_{\mathcal{S}}(x)$
is the document $\tilde{x}=$ “the slow blue fox.”

##  3 Warm-up: concatenation

Concatenation embeddings generally proceed by first mapping each token $x_{t}$
of $x$ to a vector $u(x_{t},t)\in\mathbb{R}^{d}$. In a second step, these
vector representations are concatenated together to form $\varphi(x)$. We
assume that the representation $u(x_{t},t)$ can be written as

$u(x_{t},t)=[u_{e}(x_{t});u_{p}(t)]\in\mathbb{R}^{d}\,,$ (3)

where $u_{e}\in\mathbb{R}^{d_{e}}$ denotes vector representations of
individual tokens, while $u_{p}\in\mathbb{R}^{d_{p}}$ encodes positional
information, and we define $d\vcentcolon=d_{e}+d_{p}$.

#### Token embeddings.

As noted in the introduction, there are essentially two widespread choices for
$u_{e}$: either use _sparse_ representations for individual tokens or use
_dense_ representations. The first approach is often synonymous with the use
of _one-hot encodings_ , hence considering the mapping
$u_{e}:j\mapsto\mathds{1}_{j}$ as a building brick, where, for any
$j\in\mathcal{D}$, we define $\mathds{1}_{j}$ the $j$-th vector of the
canonical basis of $\mathbb{R}^{D}$. This has the advantage of simplicity. One
caveat is that, although sparse, one-hot vectors have dimensionality
$d_{e}=D$—the size of the dictionary. Regarding dense embeddings, as discussed
in the introduction, the mapping $j\mapsto u_{e}(j)$ is learned from data and
can encompass some semantic properties. In all these examples, $u_{e}(j)$
typically has dimensionality $d_{e}\ll D$ (for instance, gensim takes
$d_{e}=100$ in its word2vec implementation).

#### Positional embeddings.

A common choice is to learn positional embeddings, jointly with token
embeddings. It is also possible to use deterministic positional embeddings,
such as one-hot vectors — $u_{p}(t)=\mathds{1}_{t}\in\mathbb{R}^{T_{\max}}$,
where $T_{\max}$ is a maximal document size, or more complicated functions of
$t$. For instance, the original transformers architecture uses a sinusoidal
transformation of $t$ as positional embedding (Vaswani et al., 2017). Further,
it is also possible to incorporate additional positional information in the
embedding – for instance BERT incorporates segment position information
corresponding to the index of the sentence the token belongs to (Devlin et
al., 2018, Figure 2). Finally, one can simply ignore $u_{p}$ altogether,
relying simply on the order of the $u(x_{t})$ to convey the positional
information. Let us note that when $d_{e}=d_{p}$, one can add $u_{e}$ and
$u_{p}$ in Eq. (3) instead of concatenating them, a possibility to which our
analysis is robust.

#### Concatenation.

For a given $u$, the embedding $\varphi(x)$ of a document $x$ is formed by
_concatenating_ the $u(x_{t},t)$s for $t\in[T]$. Formally, if $T\geq
T_{\max}$, then the concatenation $\varphi(x)$ of $(x_{1},\dots,x_{T})$ is
defined as

$\varphi(x)\vcentcolon=[u(x_{1},1);\ldots;u(x_{T_{\max}},T_{\max})]\in\mathbb{R}^{dT_{\max}}\,,$

and if $T<T_{\max}$, as (_zero-padding_),

$\varphi(x)\vcentcolon=[u(x_{1},1);\ldots;u(x_{T},T);0;\ldots;0]\in\mathbb{R}^{dT_{\max}}\,.$

Since the embedding is explicit in this case, it is straightforward to show
the following:

######  Proposition 3.1 (Robustness of concatenation).

Let $x\in[D]^{T}$, $\mathcal{S}\subseteq[T]$, and $\tilde{x}\in
B_{\mathcal{S}}(x)$. Then

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert\leq\max_{j\neq
k}\left\lVert
u_{e}(j)-u_{e}(k)\right\rVert\cdot\sqrt{\left\lvert\mathcal{S}\right\rvert\wedge
T_{\max}}\,.$

In particular, for small perturbation of the input document, concatenation is
$1/2$-Hölder with respect to the Hamming distance. Closer inspection of the
proof reveals that the constant depends only on the perturbed tokens: if the
changes made are close from the point of view of $u_{e}$, then $\varphi(x)$
and $\varphi(\tilde{x})$ remain close.

##  4 TF-IDF transform

Let $x$ be a document of length $T$ built on $\mathcal{D}$. In this section,
we will assume that tokens correspond to individual words. Forgetting the
sequential nature of natural language, one can simply look at the words
appearing in $x$ with repetitions – this is informally called a _bag-of-words_
representation. Any given word $j\in\mathcal{D}$ appears in this
representation with _multiplicity_ $m_{j}(x)$. The TF-IDF transform of $x$ is
a vector $\varphi(x)\in\mathbb{R}^{D}$, with each coordinate of $\varphi(x)$
corresponding to a word of the dictionary. Component-wise, $\varphi(x)$ is a
product of two terms: the _term frequency_ $f_{j}$ and the _inverse document
frequency_ $v_{j}$:

$\forall
j\in\mathcal{D},\quad\begin{cases}f_{j}&\vcentcolon=\frac{m_{j}}{T}\,,\\\
v_{j}&\vcentcolon=\log\frac{\left\lvert\mathcal{C}\right\rvert}{\left\lvert\\{z\in\mathcal{C}\text{
s.t. }j\in z\\}\right\rvert}\,,\end{cases}$ (4)

where $\mathcal{C}$ is a set of documents. We will assume that $v_{j}>0$. The
exact expressions appearing in Eq. (4) can vary depending on implementation,
we use here the most common definitions (in particular, they are the default
choices used by scikit-learn (Pedregosa et al., 2011)). The (non-normalized)
TF-IDF of $x$ can be written $\varphi(x)_{j}=f_{j}v_{j}$ for all
$j\in\mathcal{D}$. Intuitively, one wants to quantify the importance of each
word in the document, while ignoring common words appearing in many documents
such as articles. Finally, it is common to normalize $\varphi(x)$, generally
using the Euclidean norm. We denote by
$\phi(x)\vcentcolon=\varphi(x)/\left\lVert\varphi(x)\right\rVert$ the
normalized TF-IDF of $x$.

###  4.1 Robustness results

As we saw in the previous section, the TF-IDF transform of a given document
can be given _in closed-form_ as a function of the word multiplicities and the
given coefficients. This allows a simple analysis, at least in the non-
normalized case.

######  Proposition 4.1 (Robustness of non-normalized TF-IDF).

Let $x\in[D]^{T}$, $\mathcal{S}\subseteq[T]$, and $\tilde{x}\in
B_{\mathcal{S}}(x)$. Let $m_{\max}$ be the maximal word multiplicity in $x$
and $v_{\max}$ be the maximal inverse document frequency over $\mathcal{D}$.
Then

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert\leq
4m_{\max}v_{\max}\frac{\left\lvert\mathcal{S}\right\rvert}{T}\,.$

In other words, non-normalized TF-IDF is Lipschitz continuous for the Hamming
distance, with Lipschitz constant inversely proportional to the common length
of the documents. In reality, the dependency in $T$ is slightly more
complicated since nothing prevents $m_{\max}$ from being as large as $T$ in
pathological cases (when all the words of the document are identical). In any
case, we uncover a satisfying fact about TF-IDF: small changes in long
documents do not matter much. Taking into account the normalization, we have a
similar result:

######  Proposition 4.2 (Robustness of normalized TF-IDF).

Let $x\in[D]^{T}$. Let $v_{\min}$ be the minimal inverse document frequency
associated to the words of $x$. Let $\mathcal{S}\subseteq[T]$ such that
$\left\lvert\mathcal{S}\right\rvert\leq\left\lVert\varphi(x)\right\rVert/(4m_{\max}v_{\max})$
and $\tilde{x}\in B_{\mathcal{S}}(x)$. Then

$\left\lVert\phi(x)-\phi(\tilde{x})\right\rVert\leq\frac{4m_{\max}^{1/2}v_{\max}^{1/2}D^{1/4}}{v_{\min}^{1/2}}\sqrt{\frac{\left\lvert\mathcal{S}\right\rvert}{T}}\,.$

In plain words, normalized TF-IDF is $1/2$-Hölder with respect to the Hamming
distance. Again, the constant appearing decreases with the length of the base
document. A close inspection of the proof also reveals that the $D$ is
actually equal to $D(x)$, the size of the local dictionary.

Figure 1: Normalized TF-IDF, influence of $T$. Documents of increasing length
$t$, $5$ random replacements. Proposition 4.2 gives a bound in
$\mathcal{O}(1/\sqrt{T})$.

###  4.2 Experimental validation

In order to check the accuracy of Proposition 4.2, we ran some numerical
experiments. We considered movie reviews from the IMDB dataset as documents
and the TF-IDF implementation from scikit-learn with $L^{2}$ normalization.

#### Influence of the document length.

In a first set of experiments, we investigated the behavior of
$\left\lVert\phi(x)-\phi(\tilde{x})\right\rVert$ with respect to the length
$T$ of $x$. To this extent, for several documents, we created a sequence of
growing documents by considering the first $t$ words of the documents, with
$t$ ranging from $5$ to $T$. For each value of $t$, we replaced $5$ words in
the intermediary document and repeated this experiment several time. The words
to replace were chosen uniformly at random in the document, and the
replacements uniformly at random in $\mathcal{D}$, and we estimated the
supremum of $\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert$ by taking
the maximum over these repetitions. Proposition 4.2 predicts that, since
$\left\lvert\mathcal{S}\right\rvert$ is kept constant here, the supremum of
$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert$ over all possible
replacements should be upper bounded by $1/\sqrt{T}$ (up to numerical
constants). This appears to be empirically true (see Figure 1).

#### Influence of the number of removals.

In a second set of experiments, we looked at the dependency of
$\left\lVert\phi(x)-\phi(\tilde{x})\right\rVert$ with respect to
$\left\lvert\mathcal{S}\right\rvert$. This time keeping $x$ fixed, we
gradually increased the number of replaced words from $1$ to $T$. Since $T$ is
fixed, Proposition 4.2 predicts that the supremum of
$\left\lVert\phi(x)-\phi(\tilde{x})\right\rVert$ over all possible
replacements should behave at most as
$\sqrt{\left\lvert\mathcal{S}\right\rvert}$. This also appears to be
empirically true, see Figure 2.

Figure 2: Normalized TF-IDF, influence of $\left\lvert S\right\rvert$. For a
given document, $s$ words are replaced at random with $s$ ranging from $1$ to
$T$. Proposition 4.2 gives a bound in
$\mathcal{O}\left(\sqrt{\left\lvert\mathcal{S}\right\rvert}\right)$.

##  5 Paragraph Vector (doc2vec)

We now turn to the most challenging part of our analysis, doc2vec. On a high
level, a token embedding matrix is learned jointly with a document embedding
matrix on a corpus, aiming to predict correctly a missing token in a given
context. The key difference with other vectorizers is that, at inference time,
another minimization problem is solved by the model. Different documents yield
different optimization problems, and therefore it is quite challenging to see
where the resulting minimizer is located with respect to the original
embedding.

###  5.1 A primer on doc2vec

The key idea underlying paragraph vector is neural probabilistic language
modeling (Bengio et al., 2000): predict words of a document knowing (i) the
context of the missing word in the document, and (ii) some global information
about the document, encoded as a vector $q\in\mathbb{R}^{d}$. Thus the key
concept is the probability of observing word $j$ at position $t$ given some
context $c(t)$ and vector $q$. This is written informally as
$\mathbb{P}\left(j\middle|c(t),q\right)$, and we describe its exact
formulation in the next paragraphs. Two models are proposed in Le & Mikolov
(2014): _distributed memory_ (PVDM) model, similar to the _continuous bag of
words_ model of Mikolov et al. (2013a), and _distributed bag of words_
(PVDBOW) model, similar to the _skip gram_ model. We first focus on the PVDM
model, PVDBOW being a simplified version thereof, referring to Figure 3 for a
visual help.

Figure 3: Overview of the doc2vec vectorizer, PVDM model. For a given
document, for each token position $t$, the model considers the context $c(t)$
of $x_{t}$. The one-hot representation of the tokens in $c(t)$ (which are of
size $D$) are either average or concatenated, then projected to the embedding
layer ($\mathbb{R}^{d}$, in blue). At this stage, the document embedding
$q\in\mathbb{R}^{d}$ is added to this local representation, which is then
lifted back to $y_{t}\in\mathbb{R}^{D}$. Taking a softmax transform of $y_{t}$
yields a discrete distribution on $\mathcal{D}$, which is compared to the
truth ($x_{t}$) using cross-entropy (top part, dotted line). During training,
PV minimizes objective (8) to find satisfying token embeddings $P$, document
embedding $q$, and lifting $R$. At inference time, $P$ and $R$ are frozen and
only $q$ is allowed to vary.

#### Local information.

For a document $x$ with length $T$, for any $\nu<t<T-\nu$, we define the
_neighborhood_ of $t$ as

$\gamma(t)\vcentcolon=(t-\nu,\ldots,t-1,t+1,\ldots,t+\nu)\,.$ (5)

Here, $\nu$ is an hyperparameter often called _context size_ (or window size),
quantifying the breath of the context considered by the model. To this
neighborhood corresponds the _context_

$c(t)\vcentcolon=(x_{t-\nu},\ldots,x_{t-1},x_{t+1},\ldots,x_{t+\nu})\,.$ (6)

Intuitively, $c(t)$ corresponds to the tokens surrounding $x_{t}$ in the
document $x$. The tokens contained in $c(t)$ are then mapped to their one-hot
representations, which are aggregated together. There are two natural ways to
do this, either computing the _mean_ (PVDMmean) or the _concatenation_ of
these vectors (PVDMconcat). Thus, at this stage, the local information at
index $t$ is summarized as a vector $h_{t}$, with

$h_{t}\vcentcolon=\frac{1}{2\nu}\sum_{s\in\gamma(t)}\mathds{1}_{x_{s}}\in\mathbb{R}^{D}$

if average is used, and

$h_{t}\vcentcolon=[\mathds{1}_{x_{t-\nu}};\ldots;\mathds{1}_{x_{t-1}};\mathds{1}_{x_{t+1}};\ldots;\mathds{1}_{x_{t+\nu}}]\in\mathbb{R}^{2\nu
D}$

if concatenation is used (see bottom layer of Figure 3).

#### Projecting and lifting.

This local information is then projected into $\mathbb{R}^{d}$, with $d\ll D$,
the embedding space. At this stage, the document vector $q\in\mathbb{R}^{d}$
is added to the local representation. This intermediary representation is
lifted back to $\mathbb{R}^{D}$. PVDM relies on two matrices $P$ and $R$ such
that each context is mapped to

$y_{t}\vcentcolon=R(Ph_{t}+q)=\pi_{t}+Rq\in\mathbb{R}^{D}\,,$

where $\pi_{t}\vcentcolon=RPh_{t}\in\mathbb{R}^{D}$. Here, $P$ has size
$d\times D$ for PVDMmean, and $d\times 2\nu D$ for PVDMconcat, while $R$ has
size $D\times d$. When tokens are words, the columns of $P$ are called _word
vectors_ , since they correspond to $d$ dimensional embeddings for individual
words. We refer to the intermediate layers of Figure 3 for a visual help.

#### Prediction.

Finally, the prediction for $x_{t}$ is encoded as the _softmax_ of $y_{t}$,
where the softmax $\sigma:\mathbb{R}^{D}\to\mathbb{R}^{D}$ is defined for
$u\in\mathbb{R}^{D}$ as

$\displaystyle\sigma(u)=\left(\frac{\operatorname{e}^{u_{j}}}{\sum_{k=1}^{D}\operatorname{e}^{u_{k}}}\right)_{1\leq
j\leq D}\,.$ (7)

In particular, all components of $\sigma(y_{t})$ lie between $0$ and $1$ and
sum to one, and reading coordinate $j$ of $\sigma(y_{t})$ can be interpreted
as reading the predicted probability of token $j$. To summarize,
$\sigma(y_{t})$ encodes a discrete distribution over $\mathcal{D}$ that
depends on the context of $x_{t}$ and the document vector $q$ (topmost layer
of Figure 3).

#### Training.

Let us call $x^{(1)},\ldots,x^{(N)}$ the documents in our training set, with
lengths $T_{1},\ldots,T_{N}$. To each of these documents correspond an
embedding $q^{(i)}\in\mathbb{R}^{d}$, which can be seen as the columns of a
matrix $Q\in\mathbb{R}^{d\times N}$, each giving rise to $y_{t}^{(i)}$. The
columns of $Q$ are often referred to as _document vectors_. The key idea here
is to learn $P,Q,$ and $R$ so that the predicted tokens at position $t$ are
accurate for all documents. Seeing $\sigma(y_{t}^{(i)})$ as a discrete
probability distribution on $\mathcal{D}$, a natural way to compare it to the
groundtruth ($x_{t}^{(i)}$) is to compute the _cross-entropy_ between the
distribution putting mass one at $x_{t}^{(i)}$ and $\sigma(y_{t}^{(i)})$, that
is,

$\ell_{t}^{(i)}\vcentcolon=-\log\sigma(y_{t}^{(i)})_{x_{t}^{(i)}}\vcentcolon=\psi_{x_{t}^{(i)}}(y_{t}^{(i)})\,,$

where we defined $\psi\vcentcolon=-\log\sigma$ coordinate-wise. The
optimization problem solved by PV is written

$\operatorname*{Minimize}_{P,Q,R}\sum_{i=1}^{N}\frac{1}{T_{i}}\sum_{t\in
x^{(i)}}\psi_{x_{t}^{(t)}}(y_{t}^{(i)})\,,$ (8)

where $t\in x^{(i)}$ means $t$ ranging from $\nu+1$ to $T_{i}-\nu-1$. Problem
(8) is solved by stochastic gradient descent, or ADAM (Kingma & Ba, 2015).

#### Inference.

Let us describe the embedding of a new document $x$, assuming that the model
was trained on a corpus. The way inference works for the PV model is to keep
$P$ and $R$ fixed, and to optimize solely in $q\in\mathbb{R}^{d}$

$\operatorname*{Minimize}_{q\in\mathbb{R}^{d}}\frac{1}{T}\sum_{t\in
x}\psi_{x_{t}}(y_{t})\,.$ (9)

An important observation is that $q\mapsto\psi_{x_{t}}(\pi_{t}+Rq)$ is a
convex function, although not strictly (see Appendix). Therefore, a
regularization term is often added to Eq. (9), a point which we will clarify
in the next section. Also noting that $q$ has only $d$ parameters, solving PV
inference (9) efficiently is not too challenging.

#### The case of PVDBOW.

PVDBOW is another model falling under the PV umbrella. In a nutshell,
following the idea of the distributed bag of word model, PVDBOW works the
other way around and uses only the representation of the document to predict
tokens. At position $t$, no local information is taken into account and we put
$\pi_{t}=0$ in that case. The predicted token distribution for the document is
encoded as before (as $\sigma(y_{t})=\sigma(Rq)$), and its quality also
measured as $\psi_{x_{t}}(y_{t})$ for all tokens in the document, leading to
the same optimization problems. To summarize, PVDBOW is a simplified,
lightweight version of PVDM, simply obtained by taking $\pi_{t}=0$ in our
framework. In particular, there is no matrix $P$, which leads to fewer
parameters, and thus easier training and inference, a fact which was pointed
out by Le & Mikolov (2014). Nevertheless, they recognize that PVDBOW still
performs well as an embedding, and recommend considering as an embedding the
concatenation of PVDM and PVDBOW.

#### Hierarchical softmax and negative sampling.

In practice, as advocated by Le & Mikolov (2014), two additional expedients
are used. First, the softmax is replaced by _hierarchical softmax_ (Morin &
Bengio, 2005). In a nutshell, each call of $\sigma$ has a computational cost
linear in $D$, which can be as large as $10^{5}$ in practice. A solution is to
replace the softmax by a tree-based approximation thereof, which computation
is much faster. Second, following Mikolov et al. (2013a), it is common to
incorporate tokens with a negative association to the token to predict when
computing $\ell_{t}$, leading to faster training. These two possibilities are
non-trivial modifications to the PV model and we do not consider them in our
analysis.

###  5.2 Robustness result

Before stating our robustness result, let us explain why it is challenging and
outline the proof technique. As detailed in the previous section, the
embedding of a document $x$ of length $T$ is found by solving

$q_{0}=\operatorname*{arg\,min}_{q\in\mathbb{R}^{d}}\left\\{F(q)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}\right\\}\,,$ (10)

where $F(q)\vcentcolon=\frac{1}{T}\sum_{t\in x}\psi_{x_{t}}(\pi_{t}+Rq)$. The
regularization term $\alpha\left\lVert q\right\rVert^{2}/2$ with $\alpha>0$
ensures uniqueness of the solution. Indeed, the softmax is invariant by
translation by a vector proportional to $\mathds{1}$, and solutions to (9) are
not unique. As before, consider $\tilde{x}$, a modified version of $x$ where
tokens with indices in $\mathcal{S}$ have been replaced by others. The
embedding $q_{1}$ of $\tilde{x}$ is found by solving

$q_{1}=\operatorname*{arg\,min}_{t\in
x}\left\\{G(q)+\frac{\alpha}{2}\left\lVert q\right\rVert^{2}\right\\}\,,$ (11)

where $G(q)\vcentcolon=\frac{1}{T}\sum_{t\in
x}\psi_{\tilde{x}_{t}}(\tilde{\pi}_{t}+Rq)$, and $\tilde{\pi}_{t}$ is defined
analogously to $\pi_{t}$. The main challenge here is that $q_{0}$ and $q_{1}$
are solutions of distinct optimization problems, which can be quite different
if $\left\lvert\mathcal{S}\right\rvert$ is large.

#### From discrete to continuous.

The solution we propose to connect between these two problems is to
interpolate smoothly between them. There are many ways to do this, and we
settle for the simplest: linear interpolation. More precisely, we define for
all $\mu\in[0,1]$ and $q\in\mathbb{R}^{d}$ by

$\Psi^{\text{lin}}(\mu,q)\vcentcolon=(1-\mu)F(q)+\mu G(q)\,.$ (12)

Subsequently, for all $\mu\in[0,1]$, we can solve the following regularized
optimization problem:

$q(\mu)\vcentcolon=\operatorname*{arg\,min}_{q\in\mathbb{R}^{d}}\left\\{\Psi^{\text{lin}}(\mu,q)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}\right\\}\,,$ (13)

giving rise to a continuous trajectory in the embedding space (see Figure 4
for an illustration). One can think of $q(\mu)$ as the embedding of a
fictitious document traveling halfway between $x$ and $\tilde{x}$ as $\mu$
ranges from $0$ to $1$.

Figure 4: Continuously interpolating between $q_{0}$, the embedding of $x$ (in
red), and $q_{1}$, the embedding of $\tilde{x}$ (in black). Visualization in a
$2$-dimensional slice of $\mathbb{R}^{d}$. To each $\mu\in[0,1]$ corresponds a
solution to (13), appearing here as a point of the trajectory between $q_{0}$
and $q_{1}$ (solid orange line). Dynamics of this trajectory are described by
Eq. (14). Different document perturbations lead to different embeddings and
associated trajectories (dotted lines).

#### Dynamics of interpolation.

This approach is powerful, since it allows us to transform a problem which is
discrete in nature (elements of a sum are modified) to a continuous one (time
parameter varies). In particular, the dynamics of $\mu\mapsto q(\mu)$ are
described by an ordinary differential equation (ODE). Indeed, for all
$\mu\in[0,1]$, since
$q\mapsto\Psi^{\text{lin}}(\mu,q)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}$ is a strongly convex function, $q(\mu)$ is the (unique)
critical point of $q\to\nabla\Psi^{\text{lin}}(\mu,q)+\alpha q$, where
$\nabla$ denotes derivative with respect to the _space_ coordinate ($q$). That
is, for all $\mu\in[0,1]$,

$\nabla\Psi^{\text{lin}}(\mu,q(\mu))+\alpha q(\mu)=0\,.$

Differentiating, we get that for all $\mu\in[0,1]$,

$\left(\nabla^{2}\Psi^{\text{lin}}(\mu,q(\mu))+\alpha\operatorname{I}\right)q^{\prime}(\mu)+\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,q(\mu))=0\,,$
(14)

where $g^{\prime}$ denotes derivative with respect to the _time_ coordinate
($\mu$) and $\operatorname{I}$ the identity matrix. Let us set

$\Phi^{\text{lin}}(\mu,q)\vcentcolon=-\left(\nabla^{2}\Psi^{\text{lin}}(\mu,q)+\alpha\operatorname{I}\right)^{-1}\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,q)\,.$
(15)

Then, Eq. (14) can be rewritten as
$q^{\prime}(\mu)=\Phi^{\text{lin}}(q(\mu),\mu)$.

#### Spectrum of the Hessian of the log-softmax.

Looking back at the ODE problem, it appears that one needs to understand
precisely the behavior of $\Phi^{\text{lin}}$. Intuitively, an ill-behaved
function could lead to the explosion of the solution of the ODE, preventing
the existence of reasonable bounds on $\left\lVert q(\mu)-q(0)\right\rVert$
for large $\mu$. This understanding relies on the control of the smallest
positive eigenvalue of $\nabla^{2}\Psi^{\text{lin}}$, $\lambda_{1}(\mu,q)$.
Coming back to the definition of $\Psi^{\text{lin}}$ (Eq. (12)), $F$, and $G$,
we see that $\lambda_{1}$ closely related to $\lambda_{\min}$, the smallest
positive eigenvalue of the Hessian of the log-softmax, for which we have
precise results (Lemma H.5 and Theorem H.9).

#### Grönwall-type result.

Once that a precise control is achieved on $\Phi^{\text{lin}}$, one may have
hoped to use standard Grönwall type inequalities such as Pachpatte (2004) to
obtain quantitative bounds on $\left\lVert q(1)-q(0)\right\rVert$. However, in
our setting, the growth of $\Phi^{\text{lin}}$ prevents us from getting
explicit bounds and we had to prove a new result (Theorem G.1) which is
actually true in a more general setting than that of doc2vec. Specifying this
result, we get:

Figure 5: Influence of the length of the document on the robustness of
doc2vec. Five random replacements, from left to right: PVDMmean, PVDMconcat,
and PVDBOW.

Figure 6: Influence of the number of words replaced on the robustness of
doc2vec. From left to right: PVDMmean, PVDMconcat, and PVDBOW.

######  Theorem 5.1 (Bounded trajectories).

Let $x\in[D]^{T}$, $\mathcal{S}\subseteq[T]$, and $\tilde{x}\in
B_{\mathcal{S}}(x)$. Suppose that $R\in\mathbb{R}^{D\times d}$ is such that
$\sigma_{\min}(R)>0$ and $\mathrm{Im}(R)\subset\mathds{1}^{\perp}$. Let
$\mu\mapsto q(\mu)$ be the solution of ODE (14). Then, there exist two
constants $c=c(\alpha)>0$ and $L=L(\left\lVert q(0)\right\rVert)>0$ depending
explicitly on $P,R$, $\nu$, and $D$ such that, whenever
$\left\lvert\mathcal{S}\right\rvert/T\leq c$,

$\sup_{\mu\in[0,1]}\left\lVert q(\mu)-q(0)\right\rVert\leq
L\frac{\left\lvert\mathcal{S}\right\rvert}{T}\,.$

Since $\varphi(x)=q(0)$ and $\varphi(\tilde{x})=q(1)$, a corollary of Theorem
5.1 is that the doc2vec embedding is Lipschitz continuous with respect to the
Hamming distance, with Lipschitz constant at most inversely proportional to
the document lengTheorem Coming back to our initial question, Theorem 5.1
guarantees that, for documents of reasonable length and small perturbations,
doc2vec embeddings can not vary too greatly. We emphasize that Theorem 5.1 is
true for all three doc2vec models.

The key assumption here is that $\left\lvert\mathcal{S}\right\rvert$ is small
enough. We argue that it is only natural to ask so: indeed, if one is allowed
to modify every single token of $x$, this yield a completely different
document (although having the same length), which could _a priori_ be embedded
anywhere. The other main assumptions concern the matrix $R$. Experimentally,
we observe that $\sigma_{\min}(R)>0$ holds (see Section I.3). Requiring that
$\mathrm{Im}(R)\subset\mathds{1}^{\perp}$ is not too restricting: because of
the translation invariance by $\mathds{1}$ of the softmax, one can always
normalize $R$ by removing the average line from each line. The main limitation
of Theorem 5.1 is the dependency of $c$ and $L$ in the problems parameters.
Exact expression can be found in Appendix (Theorem F.7).

###  5.3 Experimental validation

In order to verify the validity of Theorem 5.1, we ran similar experiments to
those presented in Section 4. We considered again movie reviews from the IMDB
dataset. As vectorizer, we trained doc2vec models from scratch on a subset of
the IMDB dataset ($10^{3}$ reviews). The associated dictionary has size
$D=18,416$: we took tokens as words of the English dictionary. Note that one
can also consider sub-word tokens, but in that case replacing a word in the
document usually implies replacing several tokens. We chose $d=50$ as
dimension of the embedding. We took $\nu=5$ as context size parameter.

We present results of experiments regarding the influence of the document
length in Figure 5. Theorem 5.1 predicts that, since
$\left\lvert\mathcal{S}\right\rvert$ is kept constant here, the supremum of
$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert$ over all replacements
should be upper bounded by $1/T$ (up to numerical constants). This appears to
be empirically true.

We present results of experiments regarding the influence of the number of
replaced words in Figure 6. Here we took the number of replaced words from
$\nu+1$ to $T-\nu-1$ to avoid for border effects. Since $T$ is fixed, Theorem
5.1 predicts that the supremum of
$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert$ over all possible
replacements should behave at most linearly in
$\left\lvert\mathcal{S}\right\rvert$. This appears to be empirically true.

We present in Appendix (Section I) additional results with another
implementation, gensim (Řehůřek & Sojka, 2010). In particular, this
implementation uses hierarchical softmax. The results are consistent with the
behavior presented here.

##  6 Conclusion

In this paper, we proved that several popular text vectorizers are robust, in
the sense that they are either Lipschitz or Hölder continuous with respect to
the Hamming distance. Proving this robustness was possible for concatenation
and TF-IDF thanks to elementary computations, but required a much more
challenging mathematical analysis for doc2vec requiring two new results (local
Lipschitz continuity of the softmax and a new Grönwall–Bellman–Bahouri non-
explosion lemma).

Let us outline future research directions. First, we studied the robustness of
the _true_ solution of (8) and (9). In practice, this problem is solved thanks
to gradient descent, and it would be interesting to measure the impact of this
approximation. A second line of work would consist in obtaining refined
results when we put a random model on the distribution of the words of the
document, similarly to what is done in (Arora et al., 2016).

## Acknowledgements

This work was supported by the French government under the management of the
Agence Nationale de la Recherche, grant agreements GraVa ANR-18-CE40-0005,
NEMATIC ANR-21-CE45-0010, and NIM-ML ANR-21-CE23-0005-01. D.G. acknowledges
the support of EU Horizon 2020 project AI4Media (contract no. 951911) and
would like to thank Charbel Yachouchi for his preliminary work. S.V. would
like to thank Nicolas Patry for fruitful discussion about NLP embeddings.

## References

  * Agarwal et al. (2005) Agarwal, R. P., Deng, S., and Zhang, W.  Generalization of a retarded Gronwall-like inequality and its applications.  _Appl. Math. Comput._ , 165(3):599–612, 2005\.
  * Alghamdi et al. (2022) Alghamdi, W., Hsu, H., Jeong, H., Wang, H., Michalak, P. W., Asoodeh, S., and Calmon, F. P.  Beyond adult and compas: Fairness in multi-class prediction.  In _NeurIPS_ , 2022.
  * Arnold (1978) Arnold, V. I.  _Ordinary Differential Equations_.  MIT Press, 1978.
  * Arora et al. (2016) Arora, S., Li, Y., Liang, Y., Ma, T., and Risteski, A.  A latent variable model approach to PMI-based word embeddings.  _TACL_ , 4:385–399, 2016.
  * Bailleul & Catellier (2020) Bailleul, I. and Catellier, R.  Non-explosion criteria for rough differential equations driven by unbounded vector fields.  _Ann. Fac. Sci. Toulouse Math._ , 29(3):721–759, 2020.
  * Bengio et al. (2000) Bengio, Y., Ducharme, R., and Vincent, P.  A neural probabilistic language model.  In _NeurIPS_ , 2000.
  * Bojanowski et al. (2017) Bojanowski, P., Grave, E., Joulin, A., and Mikolov, T.  Enriching word vectors with subword information.  _TACL_ , 5:135–146, 2017.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _NeurIPS_ , 2020.
  * Bubeck & Sellke (2021) Bubeck, S. and Sellke, M.  A universal law of robustness via isoperimetry.  In _NeurIPS_ , 2021.
  * Bubeck et al. (2020) Bubeck, S., Eldan, R., Lee, Y. T., and Mikulincer, D.  Network size and size of the weights in memorization with two-layers neural networks.  In _NeurIPS_ , 2020.
  * Cer et al. (2018) Cer, D., Yang, Y., Kong, S.-y., Hua, N., Limtiaco, N., John, R. S., Constant, N., Guajardo-Cespedes, M., Yuan, S., Tar, C., et al.  Universal sentence encoder.  _arXiv preprint arXiv:1803.11175_ , 2018.
  * Cisse et al. (2017) Cisse, M., Bojanowski, P., Grave, E., Dauphin, Y., and Usunier, N.  Parseval networks: Improving robustness to adversarial examples.  In _ICML_ , 2017.
  * Dannan (1985) Dannan, F. M.  Integral inequalities of Gronwall-Bellman-Bihari type and asymptotic behavior of certain second order nonlinear differential equations.  _J. Math. Anal. Appl._ , 108(1):151–164, 1985\.
  * Devlin et al. (2018) Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_ , 2018.
  * Gage (1994) Gage, P.  A new algorithm for data compression.  _C Users Journal_ , 12(2):23–38, 1994.
  * Gao & Pavel (2017) Gao, B. and Pavel, L.  On the properties of the softmax function with application in game theory and reinforcement learning.  _arXiv preprint arXiv:1704.00805_ , 2017.
  * Garreau & Mardaoui (2021) Garreau, D. and Mardaoui, D.  What does LIME really see in images?  In _ICML_ , 2021.
  * Hein & Andriushchenko (2017) Hein, M. and Andriushchenko, M.  Formal guarantees on the robustness of a classifier against adversarial manipulation.  In _NeurIPS_ , 2017.
  * Jones (1972) Jones, K. S.  A statistical interpretation of term specificity and its application in retrieval.  _J. Doc._ , 1972.
  * Kim (2009) Kim, Y.-H.  Gronwall, Bellman and Pachpatte type integral inequalities with applications.  _Nonlinear Anal. Theory Methods Appl._ , 71(12):2641–2656, 2009.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J.  Adam: A Method for Stochastic Optimization.  In _ICLR_ , 2015.
  * Kiros et al. (2015) Kiros, R., Zhu, Y., Salakhutdinov, R. R., Zemel, R., Urtasun, R., Torralba, A., and Fidler, S.  Skip-thought vectors.  In _NeurIPS_ , 2015.
  * Le & Mikolov (2014) Le, Q. and Mikolov, T.  Distributed representations of sentences and documents.  In _ICML_ , 2014.
  * Li et al. (2015) Li, Y., Xu, L., Tian, F., Jiang, L., Zhong, X., and Chen, E.  Word embedding revisited: A new representation learning and explicit matrix factorization perspective.  In _AISTAT_ , 2015.
  * Logeswaran & Lee (2018) Logeswaran, L. and Lee, H.  An efficient framework for learning sentence representations.  In _International Conference on Learning Representations_ , 2018.
  * Luhn (1957) Luhn, H. P.  A statistical approach to mechanized encoding and searching of literary information.  _IBM J. Res. Dev._ , 1(4):309–317, 1957.
  * Mikolov et al. (2013a) Mikolov, T., Chen, K., Corrado, G. S., and Dean, J.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_ , 2013a.
  * Mikolov et al. (2013b) Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J.  Distributed representations of words and phrases and their compositionality.  _NeurIPS_ , 2013b.
  * Morin & Bengio (2005) Morin, F. and Bengio, Y.  Hierarchical probabilistic neural network language model.  In _AISTAT_ , 2005.
  * Pachpatte (2004) Pachpatte, B. G.  On some new nonlinear retarded integral inequalities.  _J. Inequal. Pure Appl. Math_ , 5(3):80, 2004\.
  * Pedregosa et al. (2011) Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E.  Scikit-learn: Machine learning in Python.  _JMLR_ , 12:2825–2830, 2011.
  * Pennington et al. (2014) Pennington, J., Socher, R., and Manning, C. D.  Glove: Global vectors for word representation.  In _EMNLP_ , 2014.
  * Peters et al. (2018) Peters, M. E., Neumann, M., Iyyer, M., Gardner, M., Clark, C., Lee, K., and Zettlemoyer, L.  Deep contextualized word representations.  In _NAACL_ , 2018.
  * Řehůřek & Sojka (2010) Řehůřek, R. and Sojka, P.  Software Framework for Topic Modelling with Large Corpora.  In _Proc. of the LREC 2010 Workshop on New Challenges for NLP Frameworks_ , 2010.
  * Sennrich et al. (2016) Sennrich, R., Haddow, B., and Birch, A.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1715–1725. Association for Computational Linguistics, 2016.
  * Steele (2004) Steele, J. M.  _The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities_.  Cambridge University Press, 2004.
  * Szegedy et al. (2014) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  In _ICLR_ , 2014.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Wei et al. (2023) Wei, D., Wu, H., Wu, M., Chen, P.-Y., Barrett, C., and Farchi, E.  Convex bounds on the softmax function with applications to robustness verification.  In _AISTATS_ , 2023.
  * Weng et al. (2018a) Weng, L., Zhang, H., Chen, H., Song, Z., Hsieh, C.-J., Daniel, L., Boning, D., and Dhillon, I.  Towards fast computation of certified robustness for ReLU networks.  In _ICML_ , 2018a.
  * Weng et al. (2018b) Weng, T.-W., Zhang, H., Chen, P.-Y., Yi, J., Su, D., Gao, Y., Hsieh, C.-J., and Daniel, L.  Evaluating the robustness of neural networks: An extreme value theory approach.  In _ICLR_ , 2018b.
  * Wu et al. (2016) Wu, Y., Schuster, M., Chen, Z., Le, Q. V., Norouzi, M., Macherey, W., Krikun, M., Cao, Y., Gao, Q., Macherey, K., et al.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _arXiv preprint arXiv:1609.08144_ , 2016.
  * Xu & Mannor (2012) Xu, H. and Mannor, S.  Robustness and generalization.  _Mach. Learn._ , 86(3):391–423, 2012.
  * Zhang et al. (2020) Zhang, W. E., Sheng, Q. Z., Alhazmi, A., and Li, C.  Adversarial attacks on deep-learning models in natural language processing: A survey.  _ACM Trans. Intell. Syst. Technol._ , 11(3):1–41, 2020.

##  Appendix A General organization

This Appendix is organized as follows: in Section B (resp. C) we collect the
missing proofs for Section 3 (resp. 4) of the main paper.

The next five sections are dedicated to the proof of Theorem 5.1: First, in
Section D, we formally prove that the dynamics of the interpolation scheme
between two minimizers follow an ordinary differential equation (ODE). We
actually show a more general result and provide technical conditions on the
interpolation $\Psi$ under which we are able to formulate the interpolation
between minimization problems as an ODE. Next, in Section E, we derive
quantitative bounds for the solution of this ODE. We show how to specialize
this result in the doc2vec setting in Section F, proving Theorem 5.1 in the
process. The main tool used to obtain these bounds is a general Grönwall-
Bellman-Bahouri type result for ODE with exponentially-growing coefficients.
This result (Theorem G.1), as well as all other technical results concerning
ODEs, is stated and proved in Section G . In order to specialize our result to
the doc2vec setting, we needed a fine-grained study of the (log-)softmax
function. In particular, we derive a new bound on the softmax function
(Theorem H.9), which is proved in Section H.

We conclude this Appendix with additional experimental results supporting our
claims in Section I.

##  Appendix B Omitted proofs for concatenation

###  B.1 Proof of Proposition 3.1

By definition of $\varphi$ and Pythagoras theorem,

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert^{2}=\sum_{t\in\mathcal{S}\cap[T_{\max}]}\left\lVert
u(x_{t},t)-u(\tilde{x}_{t},t)\right\rVert^{2}\,.$

By definition of $u$ (Eq. (3)), one has

$u(x_{t},t)-u(\tilde{x}_{t},t)=[u_{e}(x_{t})-u(\tilde{x}_{t});0]\,,$ (16)

and therefore

$\left\lVert u(x_{t},t)-u(\tilde{x}_{t},t)\right\rVert^{2}=\left\lVert
u_{e}(x_{t})-u(\tilde{x}_{t})\right\rVert^{2}\,.$

We deduce that

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert^{2}\leq\left\lvert\mathcal{S}\cap[T_{\max}]\right\rvert\cdot\max_{j\neq
k}\left\lVert u_{e}(j)-u_{e}(k)\right\rVert^{2}\,.$

∎

######  Remark B.1 (Concatenation _v.s._ sum).

Replacing the concatenation by a sum in the definition of $u$ (Eq. (3)) does
not change the proof. Indeed, the key step Eq. (16) remains unchanged in that
case: the key idea here is that position tokens are the same for words in the
same position, and cancel out when forming the difference.

##  Appendix C Omitted proofs for TF-IDF vectorization

###  C.1 Proof of Proposition 4.1

By definition, we can write

$\varphi(x)=\sum_{j=1}^{D}f_{j}v_{j}\mathds{1}_{j}=\frac{1}{T}\sum_{j=1}^{D}m_{j}v_{j}\mathds{1}_{j}\,.$

Similarly, since $\tilde{x}$ has same length as $x$,

$\varphi(\tilde{x})=\frac{1}{T}\sum_{j=1}^{D}\tilde{m}_{j}v_{j}\mathds{1}_{j}\,,$

where we let $\tilde{m}_{j}$ denote the multiplicity of word $j$ in document
$\tilde{x}$. We deduce that

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert^{2}=\frac{1}{T^{2}}\sum_{j=1}^{D}(m_{j}-\tilde{m}_{j})^{2}v_{j}^{2}\,.$

By letting $v_{\max}$ be the maximal inverse document frequency on
$\mathcal{D}$, we already see that

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert^{2}\leq\frac{v_{\max}^{2}}{T^{2}}\sum_{j=1}^{D}(m_{j}-\tilde{m}_{j})^{2}\,.$

In the previous display, only terms such that $m_{j}\neq\tilde{m}_{j}$ count.
Using the inequality between $p$-norms, we have

$\sum_{m_{j}\neq\tilde{m}_{j}}(m_{j}-\tilde{m}_{j})^{2}\leq\left(\sum_{m_{j}\neq\tilde{m}_{j}}\left\lvert
m_{j}-\tilde{m}_{j}\right\rvert\right)^{2}\,.$

Now, by the triangle inequality,

$\sum_{m_{j}\neq\tilde{m}_{j}}\left\lvert
m_{j}-\tilde{m}_{j}\right\rvert\leq\sum_{m_{j}\neq\tilde{m}_{j}}m_{j}+\sum_{m_{j}\neq\tilde{m}_{j}}\tilde{m}_{j}\,.$

We notice that these two sums are equal: every removed word has to appear
somewhere. Moreover, $\left\lvert\\{j\text{ s.t.
}m_{j}\neq\tilde{m}_{j}\right\rvert\leq 2\left\lvert\mathcal{S}\right\rvert$,
since modifying one word changes at most two multiplicities, and this happens
at most $\left\lvert\mathcal{S}\right\rvert$ times. Therefore, we have proved
that

$\sum_{m_{j}\neq\tilde{m}_{j}}\left\lvert m_{j}-\tilde{m}_{j}\right\rvert\leq
4m_{\max}\left\lvert\mathcal{S}\right\rvert\,,$ (17)

where we recall that $m_{\max}$ is the maximal multiplicity of words of $x$.
Backtracking, we have

$\left\lVert\varphi(x)-\varphi(\tilde{x})\right\rVert^{2}\leq\frac{v_{\max}^{2}}{T^{2}}\cdot
16m_{\max}^{2}\left\lvert\mathcal{S}\right\rvert^{2}\,,$

and we can conclude by simply taking the square root of this last display. ∎

###  C.2 Proof of Proposition 4.2

We notice that

$\left\lVert\phi(x)-\phi(\tilde{x})\right\rVert^{2}=1+1-2\phi(x)^{\top}\phi(\tilde{x})=2-2\frac{\varphi(x)^{\top}\varphi(\tilde{x})}{\left\lVert\varphi(x)\right\rVert\left\lVert\varphi(\tilde{x})\right\rVert}\,.$
(18)

In this last term we recognize the _cosine similarity_ between $\varphi(x)$
and $\varphi(\tilde{x})$. Since we are working under the assumptions of Lemma
C.1, we have

$\frac{\varphi(x)^{\top}\varphi(\tilde{x})}{\left\lVert\varphi(x)\right\rVert\left\lVert\varphi(\tilde{x})\right\rVert}\geq
1-\frac{8m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert}{\left\lVert\varphi(x)\right\rVert}\,.$

Coming back to Eq. (18), we see that

$\left\lVert\phi(x)-\phi(\tilde{x})\right\rVert^{2}\leq\frac{16m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert}{\left\lVert\varphi(x)\right\rVert}\,.$

We conclude by using Lemma C.2 and taking the square root. ∎

###  C.3 Auxilliary results

We have the following result, key to the proof of Prop. 4.2, and of
independent interest:

######  Lemma C.1 (Cosine similarity robustness).

Let $x$ be a document. Let $\mathcal{S}\subseteq[T]$ such that
$\left\lvert\mathcal{S}\right\rvert\leq\left\lVert\varphi(x)\right\rVert/(4m_{\max}v_{\max})$
and $\tilde{x}\in B_{\mathcal{S}}(x)$. Then

$\frac{\varphi(x)^{\top}\varphi(\tilde{x})}{\left\lVert\varphi(x)\right\rVert\left\lVert\varphi(\tilde{x})\right\rVert}\geq
1-\frac{8m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert}{\left\lVert\varphi(x)\right\rVert}\,.$
(19)

###### Proof.

By homogeneity, we can multiply numerator and denominator in Eq. (19) by $T$
and deal with multiplicities instead of frequencies in this proof. We first
focus on the numerator and write

$\varphi(x)^{\top}\varphi(\tilde{x})=\varphi(x)^{\top}(\varphi(x)+\varphi(\tilde{x})-\varphi(x))=\left\lVert\varphi(x)\right\rVert^{2}+\sum_{j=1}^{D}m_{j}(\tilde{m}_{j}-m_{j})v_{j}^{2}\,,$
(20)

by definition of $\varphi$. Using Cauchy-Schwarz inequality, we find that

$\sum_{j=1}^{D}m_{j}(m_{j}-\tilde{m}_{j})v_{j}^{2}\leq\sqrt{\sum_{j}m_{j}v_{j}^{2}}\sqrt{\sum_{j}(m_{j}-\tilde{m}_{j})^{2}v_{j}^{2}}\,.$

In the first part of the right-hand side we recognize
$\left\lVert\varphi(x)\right\rVert$, and in the second part, the same quantity
bounded in the proof of Proposition 4.1. We deduce that

$\sum_{j}m_{j}(m_{j}-\tilde{m}_{j})v_{j}^{2}\leq\left\lVert\varphi(x)\right\rVert\cdot
4m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert\,.$

Coming back to Eq. (20), we have proved that

$\varphi(x)^{\top}\varphi(\tilde{x})\geq\left\lVert\varphi(x)\right\rVert^{2}-4m_{\max}v_{\max}\left\lVert\varphi(x)\right\rVert\left\lvert\mathcal{S}\right\rvert\,,$

which is positive under our assumption. Let us now look into the denominator
of Eq. (19). Using the triangle inequality and Proposition 4.1, we write

$\left\lVert\varphi(\tilde{x})\right\rVert\leq\left\lVert\varphi(x)\right\rVert+4m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert\,.$

Putting everything together, we have

$\frac{\varphi(x)^{\top}\varphi(\tilde{x})}{\left\lVert\varphi(x)\right\rVert\left\lVert\varphi(\tilde{x})\right\rVert}\geq\frac{\left\lVert\varphi(x)\right\rVert^{2}-4m_{\max}v_{\max}\left\lVert\varphi(x)\right\rVert\left\lvert\mathcal{S}\right\rvert}{\left\lVert\varphi(x)\right\rVert\cdot(\left\lVert\varphi(x)\right\rVert+4m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert)}=\frac{1-u}{1+u}\,,$

with
$u\vcentcolon=4m_{\max}v_{\max}\left\lvert\mathcal{S}\right\rvert/\left\lVert\varphi(x)\right\rVert$.
Again, by our assumption, $u\in(0,1)$. It is straightforward to show that
$(1-u)/(1+u)\geq 1-2u$ for all $u\in(0,1)$, and we deduce the result. ∎

We also have the following:

######  Lemma C.2 (Lower bound on $\left\lVert\varphi(x)\right\rVert$).

Let $x$ be a document. Let $v_{\min}$ be the minimum inverse document
frequency for words contained in $x$ and $D(x)$ the size of the local
dictionary. Then

$\left\lVert\varphi(x)\right\rVert\geq\frac{Tv_{\min}}{\sqrt{D(x)}}\,.$

###### Proof.

Straightforward from the definitions and the comparison of $p$-norms. ∎

##  Appendix D Dynamics of interpolation

Recall that we are considering, for all $\mu\in[0,1]$, the following
minimization problem:

$q(\mu)\vcentcolon=\operatorname*{arg\,min}_{q\in\mathbb{R}^{d}}\left\\{\Psi^{\text{lin}}(\mu,q)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}\right\\}\,.$ (21)

In this section, we show that under mild regularity assumptions on $\Psi$, $q$
is the unique solution of the following ODE:

$\left(\nabla^{2}\Psi^{\text{lin}}(\mu,q(\mu))+\alpha\operatorname{I}\right)q^{\prime}(\mu)+\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,q(\mu))=0\,.$
(22)

#### Notation.

For any matrix $M\in\mathbb{R}^{A\times B}$, let us define the _operator norm_
of $M$ as

$\left\lVert
M\right\rVert_{\mathrm{op}}\vcentcolon=\sup\left\\{\frac{\left\lVert
Mv\right\rVert}{\left\lVert
v\right\rVert},v\in\mathbb{R}^{B}\setminus\\{0\\}\right\\}\,.$

For any $\rho>0$, we also define $B_{d}(\rho)$ the open Euclidean ball of
center $0$ and radius $\rho$. Finally, for $a_{1},a_{2}>0$, define $a_{1}\vee
a_{2}\vcentcolon=\max(a_{1},a_{2})$.

We can now state the required assumptions on $\Psi$.

######  Assumption D.1 (Convexity).

Let $d\geq 1$. We suppose that
$\Psi\in\mathcal{C}^{1,2}([0,1]\times\mathbb{R}^{d};\mathbb{R})$ and that, for
all $(\mu,q)\in[0,1]\times\mathbb{R}^{d}$, $\nabla^{2}\Psi(\mu,q)$ is a
positive semi-definite matrix.

Since $\alpha>0$, A.D.1 this guarantees that $q(\mu)$ is uniquely-defined for
each $\mu$. Next, we define some quantities related to the local Lipschitz
continuity of $\Psi$ and its derivatives.

######  Definition D.2 (Local Lipschitz semi-norms).

Let $\Psi\in\mathcal{C}^{1,2}([0,1]\times\mathbb{R}^{d};\mathbb{R})$. For all
$\rho>0$, let us define

$L_{1}(\rho)\vcentcolon=\sup_{\begin{subarray}{c}\mu\in[0,1]\\\
q\neq\tilde{q}\in
B_{d}(0,\rho)\end{subarray}}\frac{\left\lVert\nabla^{2}\Psi(\mu,q)-\nabla^{2}\Psi(\mu,\tilde{q})\right\rVert_{\mathrm{op}}}{\left\lVert
q-\tilde{q}\right\rVert}\,,\quad
L_{2}(\rho)\vcentcolon=\sup_{\begin{subarray}{c}\mu\in[0,1]\\\
q\neq\tilde{q}\in
B_{d}(0,\rho)\end{subarray}}\frac{\left\lVert\partial_{\mu}\nabla\Psi(\mu,q)-\partial_{\mu}\nabla\Psi(\mu,\tilde{q})\right\rVert}{\left\lVert
q-\tilde{q}\right\rVert}\,,$ (23)

and

$M(\rho)\vcentcolon=\sup_{\begin{subarray}{c}\mu\in[0,1]\\\ q\in
B_{d}(0,\rho)\end{subarray}}\left\lVert\partial_{\mu}\nabla\Psi(\mu,q)\right\rVert\,.$
(24)

Our second assumption on $\Psi$ at this stage is that these quantities are all
finite.

######  Assumption D.3 (Global Lipschitz continuity).

Let $\Psi\in\mathcal{C}^{1,2}([0,1]\times\mathbb{R}^{d};\mathbb{R})$. Suppose
that

$\sup_{\rho>0}\big{(}L_{1}(\rho)+L_{2}(\rho)\big{)}<+\infty\quad\text{and}\quad\sup_{\rho>0}M(\rho)<+\infty,$

where $L_{1}(\rho)$, $L_{2}(\rho)$, and $M(\rho)$ are defined in Eq. (23) and
Eq. (24).

In this setting, we are able to prove the following result:

######  Theorem D.4 (Equivalence ODE/minimization problem).

Assume that $\Psi$ satisfies A.D.1 and A.D.3. Then $\mu\mapsto q(\mu)$ is
differentiable on $[0,1]$, and $q$ is the unique solution of Eq. (22).

Note that under assumption A.D.1 the matrix
$\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}$ is invertible. One can then
rewrite Eq. (22) in a more standard form, namely

$q^{\prime}(\mu)=-\left(\nabla^{2}\Psi(\mu,q(\mu))+\alpha\operatorname{I}\right)^{-1}\partial_{\mu}\nabla\Psi(\mu,q(\mu))\,.$
(25)

Thus, to study the ODE problem, one needs the regularity properties (local
Lipschitz continuity, boundedness…) of the function

$\Phi:(\mu,q)\in[0,1]\times\mathbb{R}^{d}\mapsto\Phi(\mu,q)\vcentcolon=-\left(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}\right)^{-1}\partial_{\mu}\nabla\Psi(\mu,q)\,.$
(26)

The interplay between $\partial_{\mu}\nabla\Psi$ and $\nabla^{2}\Psi$ here is
crucial. Indeed, in Section F we will see that when specified in the doc2vec
case, the term in $\partial_{\mu}$ gives the desired quantity
$\frac{\left\lvert\mathcal{S}\right\rvert}{T}$ whereas the term in
$\nabla^{2}\Psi$ has to be handled using precise properties on the softmax
function. Theorem D.4 is standard in the ODE literature and holds as soon as
the quantities appearing in Eq. (25) are well-behaved. More precisely, this is
the case $c=0$ of Theorem G.1 in Section G. We now simply check that the
assumptions of Theorem G.1 are satisfied in the setting of Theorem D.4. This
is achieved by Lemma D.5 and Lemma D.6. We start by a result upper bounding
the norm of the inverse Hessian.

######  Lemma D.5 (Norm of inverse Hessian).

Let $\Psi:[0,1]\times\mathbb{R}^{d}\to\mathbb{R}$. Assume that A.D.1 holds.
Then,

$\forall\mu,q\in[0,1]\times\mathbb{R}^{d},\qquad\left\lVert(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I})^{-1}\right\rVert_{\mathrm{op}}\leq\frac{1}{\alpha}\,.$
(27)

The proof of Lemma D.5 exploits the fact that $\nabla^{2}\Psi$ is a non-
negative symmetric matrix and can be diagonalized in orthonormal basis with
non-negative eigenvalues. The regularization of the minimization problem with
the addition of the term $\frac{\alpha}{2}\left\lVert q\right\rVert$ can be
translated with the addition of the term $\alpha\operatorname{I}$ to the
previous Hessian matrix, which then becomes a positive definite symmetric
matrix. One then only has to estimate the smallest eigenvalue of the matrix to
conclude.

###### Proof.

By A.D.1, for all $\mu\in[0,1]$, $q\mapsto\Psi(\mu,q)$ is convex and, for any
$\mu,q\in[0,1]\times\mathbb{R}^{d}$, $\nabla^{2}\Psi(\mu,q)$ is a positive
semi-definite matrix with non-negative eigenvalues. From these,
$N_{0}(\mu,q)=\mathrm{Rank}\left(\nabla^{2}\Psi(\mu,q)\right)$ of them are
non-zero, and they can be ranked as

$0<\lambda_{1}(\mu,q)\leq\cdots\leq\lambda_{N_{0}(\mu,q)}(\mu,q)\,.$

Moreover, there exists an orthogonal matrix $P(\mu,q)$ (meaning that
$P(\mu,q)P(\mu,q)^{\top}=\operatorname{I}$) such that

$P(\mu,q)\nabla^{2}\Psi(\mu,q)P(\mu,q)^{\top}=\operatorname{diag}(0,\ldots,0,\lambda_{1}(\mu,q),\ldots,\lambda_{N_{0}}(\mu,q))\,.$

Furthermore since $\nabla^{2}\Psi(\mu,q)$ is a symmetric matrix, its range and
its kernel are orthogonal complements,
$\mathrm{Ker}\left(\nabla^{2}\Psi(\mu,q)\right)\oplus^{\perp}\mathrm{Im}(\nabla^{2}\Psi(\mu,q))=\mathbb{R}^{d}$
and

$h\in\mathrm{Im}(\nabla^{2}\Psi(\mu,q))\quad\text{if, and only if,}\quad
P(\mu,q)h=(0,\ldots,0,h_{1},\cdots,h_{N_{0}}).$

Hence

$P(\mu,q)\left(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}\right)P(\mu,q)^{\top}=\operatorname{diag}(\alpha,\ldots,\alpha,\lambda_{1}(\mu,q)+\alpha,\ldots,\lambda_{N_{0}}(\mu,q)+\alpha)\,,$

which implies that $\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}$ is an
invertible positive definite matrix such that

$P(\mu,q)\left(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}\right)^{-1}P(\mu,q)^{\top}=\operatorname{diag}\left(\frac{1}{\alpha},\ldots,\frac{1}{\alpha},\frac{1}{\lambda_{1}(\mu,q)+\alpha},\ldots,\frac{1}{\lambda_{N_{0}}(\mu,q)+\alpha}\right)\,.$

From the last display, one readily sees that the maximum eigenvalue of
$\left(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}\right)^{-1}$ is
$1/\alpha$, proving our claim. ∎

The next lemma shows how regularity assumptions on $\Psi$ translate into
regularity conditions for $\Phi$.

######  Lemma D.6 (Global-Lispchitz continuity of $\Phi$).

Let $\Psi$ such that A.D.1 and A.D.3 hold. Then $\Phi$ is globally Lipschitz
continuous in $q$ uniformly in $\mu\in[0,1]$. Moreover, for all $\rho>0$,

$\sup_{\begin{subarray}{c}\mu\in[0,1]\\\
q\neq\tilde{q}\in\mathbb{R}^{d}\end{subarray}}\frac{\left\lVert\Phi(\mu,q)-\Phi(\mu,\tilde{q})\right\rVert}{\left\lVert
q-\tilde{q}\right\rVert}\leq\frac{1}{\alpha}\left(\sup_{\rho>0}L_{2}(\rho)+\frac{\big{(}\sup_{\rho>0}L_{1}(\rho)\big{)}\big{(}\sup_{\rho>0}M(\rho)\big{)}}{\alpha}\right)\,.$
(28)

The proof of Lemma D.6 relies on the following identity, which is true for any
non-negative symmetric matrices $A,B\in\mathbb{R}^{d\times d}$ and vectors
$X,Y\in\mathbb{R}^{d}$:

$(A+\alpha\operatorname{I})^{-1}X-(B+\alpha\operatorname{I})^{-1}Y=-(A+\alpha\operatorname{I})^{-1}(A-B)(B+\alpha\operatorname{I})^{-1}X+(B+\alpha\operatorname{I})^{-1}(X-Y)\,.$
(29)

Lemma D.5 allows us to conclude.

###### Proof.

Let $q,\tilde{q}\in B_{d}(0,\rho)$. Using Eq. (29), we have

$\displaystyle\Phi(\mu,q)-\Phi(\mu,\tilde{q})=$
$\displaystyle-\left((\nabla^{2}\Psi(\mu,q)+\alpha
I)^{-1}-(\nabla^{2}\Psi(\mu,\tilde{q})+\alpha
I)^{-1}\right)\partial_{\mu}\nabla\Psi(\mu,q)$
$\displaystyle-(\nabla^{2}\Psi(\mu,\tilde{q})+\alpha
I)^{-1}\left(\partial_{\mu}\nabla\Psi(\mu,q)-\partial_{\mu}\nabla\Psi(\mu,\tilde{q})\right)$
$\displaystyle=$ $\displaystyle-(\nabla^{2}\Psi(\mu,q)+\alpha
I)^{-1}\left(\nabla^{2}\Psi(\mu,\tilde{q})-\nabla^{2}\Psi(\mu,q)\right)(\nabla^{2}\Psi(\mu,\tilde{q})+\alpha
I)^{-1}\partial_{\mu}\nabla\Psi(\mu,q)$ (30)
$\displaystyle-(\nabla^{2}\Psi(\mu,\tilde{q})+\alpha
I)^{-1}\left(\partial_{\mu}\nabla\Psi(\mu,q)-\partial_{\mu}\nabla\Psi(\mu,\tilde{q})\right)\,.$
(31)

Taking the norm and using Lemma D.5 (in particular Inequality (27)), we have
for $\rho=\left\lVert q\right\rVert\vee\left\lVert\tilde{q}\right\rVert$,

$\displaystyle\left\lVert\Phi(\mu,q)-\Phi(\mu,\tilde{q})\right\rVert\leq$
$\displaystyle\frac{1}{\alpha^{2}}\left\lVert\nabla^{2}\Psi(\mu,q)-\nabla^{2}\Psi(\mu,\tilde{q})\right\rVert_{\mathrm{op}}\left\lVert\partial_{\mu}\nabla\Psi(\mu,q)\right\rVert$
$\displaystyle+\frac{1}{\alpha}\left\lVert\partial_{\mu}\nabla\Psi(\mu,q)-\partial_{\mu}\nabla\Psi(\mu,\tilde{q})\right\rVert$
$\displaystyle\left\lVert\Phi(\mu,q)-\Phi(\mu,\tilde{q})\right\rVert\leq$
$\displaystyle\frac{1}{\alpha}\left(\frac{L_{1}(\rho)M(\rho)}{\alpha}+L_{2}(\rho)\right)\left\lVert
q-\tilde{q}\right\rVert\,.$

Taking the supremum for $\mu\in[0,1]$, $q\neq\tilde{q}$ belonging to
$B_{d}(0,\rho)$ and $\rho>0$ yields the claim. ∎

We now have all the tools to prove Theorem D.4.

###### Proof of Theorem D.4.

Note that in that setting, using Lemma D.5, for all $\mu\in[0,1]$,
$q\mapsto\Psi(\mu,q)+\frac{\alpha}{2}\left\lVert q\right\rVert^{2}$ is a
strongly convex function and has a unique minimum, which is also the unique
critical point of the gradient $q\mapsto\nabla\Psi(\mu,q)+\alpha q$. Let
$q_{0}\in\mathbb{R}^{d}$ be such that

$\\{q_{0}\\}=\operatorname*{arg\,min}\Psi(0,q)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}\,.$

Thanks to Lemma D.6, $\Phi$ satisfies the hypothesis of Theorem G.1, with

$a=\frac{1}{\alpha}\sup_{\rho>0}M(\rho),\quad
b=\frac{1}{\alpha}\left(\frac{\sup_{\rho>0}L_{1}(\rho)\sup_{\rho>0}M(\rho)}{\alpha}+\sup_{\rho>0}L_{2}(\rho)\right),\quad\text{and}\quad
c=0.$ (32)

Let $\mu\in[0,1]\to q(\mu)$ be the unique solution up to time $1$ to the ODE

$q^{\prime}(\mu)=-\left(\nabla^{2}\Psi(\mu,q(\mu))+\alpha\operatorname{I}\right)^{-1}\partial_{\mu}\nabla\Psi(\mu,q(\mu))=\Phi(\mu,q(\mu)),\quad
q(0)=q_{0}\,.$

According to Theorem G.1 applied to $\Lambda=\Phi$, it exists and is well-
defined up until $\mu=1$.

Remark that when differentiating in $\mu\in[0,1]$ the function
$\mu\mapsto\nabla\Psi(\mu,q(\mu))+\alpha q(\mu)$, we have

$\left(\nabla^{2}\Psi(\mu,q(\mu))+\alpha\operatorname{I}\right)q^{\prime}(\mu)+\partial_{\mu}\nabla\Psi(\mu,q(\mu))=\left(\nabla^{2}\Psi(\mu,q(\mu))+\alpha\operatorname{I}\right)\left(q^{\prime}(\mu)-\Phi(\mu,q(\mu))\right)=0\,.$

Hence

$\nabla\Psi(\mu,q(\mu))+\alpha q(\mu)=\nabla\Psi(0,q(0))+\alpha q(0)=0\,.$

Thus, for any $\mu\in[0,1]$,

$\\{q(\mu)\\}=\operatorname*{arg\,min}\left\\{\Psi(\mu,q)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}\right\\}\,,$

which is the promised result. ∎

######  Remark D.7 (Crude bounds under mild assumptions).

Using the same standard result (condition $c=0$ in Theorem G.1) could
naturally give us some crude bounds on $\left\lVert q(\mu)-q(0)\right\rVert$,
relying only on assumptions A.D.1 and A.D.3. More precisely, these bounds
would strongly depend on $\alpha$ and improve as $\alpha\to\infty$. Namely,
using Eq. (32) and Theorem D.4 one have for all $\mu\in[0,1]$,

$\left\lVert
q(\mu)-q(0)\right\rVert\leq\frac{\mu}{\alpha}\cdot\sup_{\rho}M(\rho)\cdot\operatorname{exp}\left(\frac{1}{\alpha}\left(\frac{1}{\alpha}\big{(}\sup_{\rho>0}L_{1}(\rho)\big{)}\big{(}\sup_{\rho}M(\rho)\big{)}+\sup_{\rho>0}L_{1}(\rho)\big{)}\right)\mu\right)\,.$

This is not the regime we aim at, since $\alpha$ is a small, fixed
regularization constant whose role is simply to ensure that the minimization
problem is well-posed.

##  Appendix E Quantitative bounds on the trajectory

Let us recall that $q$ is the minimizer of the interpolated problem (21). In
the previous section, we have made two assumptions (A.D.1 and A.D.3),
guaranteeing that $q$ is well-defined and is the unique solution to the ODE
(22). In this section, we show how to obtain quantitative bounds on
$\left\lVert q(0)-q(\mu)\right\rVert$ by studying the ODE (22). To derive
these bounds, we now make two additional assumptions on $\Psi$. The first one
is an algebraic assumption which greatly improves the computations.

######  Assumption E.1 (Common kernel).

We assume that there exists a fixed subspace $E\subset\mathbb{R}^{d}$ such
that $\operatorname{dim}E=N_{0}$ and for all
$(\mu,q)\in[0,1]\times\mathbb{R}^{d}$

$\mathrm{Ker}\left(\nabla^{2}\Psi(\mu,q)\right)=E^{\perp},\quad\mathrm{Im}(\nabla^{2}\Psi(\mu,q))=E,\quad\text{
and }\quad\partial_{\mu}\nabla\Psi(\mu,q)\in E\,.$

The second one is a refined local-Lipschitz assumption (a quantitative version
of A.D.3), which will allow us to use the case $c\neq 0$ in the Gronwall-
Bahouri-Bellman type result Theorem F.7.

######  Assumption E.2 (quantitative (local)-Lipschitz continuity).

Recall $L_{1}$ and $L_{2}$ from Definition D.2, and $M$ from Eq. (24). For any
$\mu,q$, define $\lambda_{1}(\mu,q)$ the smallest positive eigenvalue of
$\nabla^{2}\Psi(\mu,q)$. For any $\rho>0$, define

$w_{-1}(\rho)\vcentcolon=\inf_{\begin{subarray}{c}\mu\in[0,1]\\\ q\in
B_{d}(0,\rho)\end{subarray}}\lambda_{1}(\mu,q)\,.$

We assume that there exist positive constants
$(\Gamma_{i})_{i\in{-1,\ldots,2}}$ and non negative constants
$(\gamma_{i})_{i\in{-1,\ldots,2}}$, such that for all $\rho>0$,

$L_{1}(\rho)\leq\Gamma_{1}\operatorname{e}^{\gamma_{1}\rho}\,,\quad
L_{1}(\rho)\leq\Gamma_{2}\operatorname{e}^{\gamma_{2}\rho}\,,\quad
M(\rho)\leq\Gamma_{0}\operatorname{e}^{\gamma_{0}\rho}\,,$

and

$w_{-1}(\rho)\geq\frac{1}{\Gamma{-1}}\operatorname{e}^{-\gamma_{-1}\rho}\,.$

Under these stronger assumptions, we can obtain the following:

######  Theorem E.3 (Quantitative bounds on the trajectory).

Assume that $\Psi$ satisfies A.D.1, A.E.1, and A.E.2. Suppose furthermore that

$4\Gamma_{-1}(\Gamma_{0}\Gamma_{-1}\Gamma_{1}+\Gamma_{2})<\operatorname{exp}\left(-2\big{(}(\gamma_{-1}+\gamma_{0}+\gamma_{1})\vee\gamma_{2}\big{)}\left(\left\lVert
q_{0}\right\rVert+\Gamma_{-1}\Gamma_{0}\operatorname{e}^{(\gamma_{-1}+\gamma_{0}+\gamma_{1})\vee\gamma_{2}\left\lVert
q_{0}\right\rVert}\right)\right)\,.$ (33)

Then $\mu\mapsto q(\mu)$ is differentiable on $[0,1]$, it is the unique
solution of Eq. (22) and furthermore

$\forall\mu\in[0,1],\qquad\left\lVert q(\mu)-q_{0}\right\rVert\leq
2\mu\Gamma_{-1}\Gamma_{0}\operatorname{e}^{(\sum_{i=-1}^{2}\gamma_{i})\left\lVert
q_{0}\right\rVert}\,.$

The proof of Theorem E.3 follows the same path as the proof of Theorem D.4,
with analogues of Lemmas D.5 and D.6. The crucial differences come from the
fundamental use of A.E.1, which somehow allows us to diagonalize the Hessian
$\nabla^{2}\Psi$ for all $\mu,q$, and thus allows is to use estimates on the
smallest positive eigenvalue of the Hessian. In practical cases, this
assumption will not allow us to use global-Lipchitz estimates. We therefore
introduce A.E.2 to deal with that. These two ingredients allow us to use the
case $c>0$ in the Grönwall-Bahouri-Bellman type lemma (Theorem G.1).

The following Lemma gives an improve bounds for the norm of the inverse of the
Hessian, using the algebraic requirement on the Hessian. Its proof is similar
to the proof of Lemma D.5, and we only point out how to modify it.

######  Lemma E.4 (Quantitative norm of inverse Hessian).

Let $\Psi:[0,1]\times\mathbb{R}^{d}\to\mathbb{R}$. Assume that A.D.1 and A.E.1
hold. Then

$\left\lVert\mathchoice{{(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I})^{-1}\,\smash{\vrule
height=7.44357pt,depth=3.25458pt}}_{\,\mathrm{Im}(\nabla^{2}\Psi(\mu,q))}}{{(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I})^{-1}\,\smash{\vrule
height=7.44357pt,depth=3.25458pt}}_{\,\mathrm{Im}(\nabla^{2}\Psi(\mu,q))}}{{(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I})^{-1}\,\smash{\vrule
height=5.23111pt,depth=2.44989pt}}_{\,\mathrm{Im}(\nabla^{2}\Psi(\mu,q))}}{{(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I})^{-1}\,\smash{\vrule
height=4.03111pt,depth=2.44989pt}}_{\,\mathrm{Im}(\nabla^{2}\Psi(\mu,q))}}\right\rVert_{\mathrm{op}}\leq\frac{1}{\lambda_{1}(\mu,q)}\,,$
(34)

where $f|_{E}$ denotes the restriction of $f$ to the set $E$.

###### Proof.

Remind that from the proof of Lemma D.5, for all
$(q,\mu)\in\mathbb{R}^{d}\times[0,1]$, we have

$P(\mu,q)\left(\nabla^{2}\Psi(\mu,q)+\alpha\operatorname{I}\right)^{-1}P(\mu,q)^{\top}=\operatorname{diag}\left(\frac{1}{\alpha},\ldots,\frac{1}{\alpha},\frac{1}{\lambda_{1}(\mu,q)+\alpha},\ldots,\frac{1}{\lambda_{N_{0}}(\mu,q)+\alpha}\right)\,.$

Assuming that A.E.1 holds, we have for all
$(\mu,q)\in[0,1]\times\mathbb{R}^{d}$, $N_{0}(\mu,q)=N_{0}$. Restricting to
$E$, we see readily that the largest eigenvalue becomes
$1/(\alpha+\lambda_{1}(\mu,q))$. ∎

Here again, by using the algebraic requirements on $\Psi$ and the local-
Lipshcitz bound we are able to derive a local-Lipschitz continuity result for
$\Phi$. Here again, the proof is quite similar to the one of Lemma E.5.

######  Lemma E.5 (Local-Lispchitz continuity of $\Phi$).

Let $\Psi$ such that A.D.1, and A.E.1 hold. Then $\Phi$ is locally-Lipschitz
continuous in $q$ uniformly in $\mu\in[0,1]$. More precisely, for all
$q,\tilde{q}\in\mathbb{R}^{d}$ and all $\mu\in[0,1]$;

$\left\lVert\Phi(\mu,q)-\Phi(\mu,\tilde{q})\right\rVert\leq\frac{1}{w_{-1}(\left\lVert\tilde{q}\right\rVert)}\left(\frac{L_{1}(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)M(\left\lVert
q\right\rVert)}{w_{-1}(\left\lVert q\right\rVert)}+L_{2}(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)\right)\left\lVert
q-\tilde{q}\right\rVert\,.$

If additionally A.E.2 holds, we get

$\left\lVert\Phi(\mu,q)-\Phi(\mu,\tilde{q})\right\rVert\leq
2\Gamma_{-1}(\Gamma_{0}\Gamma_{-1}\Gamma_{1}+\Gamma_{2})\operatorname{e}^{\big{(}(\gamma_{-1}+\gamma_{0}+\gamma_{1})\vee\gamma_{2}\big{)}\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert}\left\lVert
q-\tilde{q}\right\rVert\,,$ (35)

and

$\left\lVert\Phi(\mu,q)\right\rVert\leq\Gamma_{-1}\Gamma_{0}\operatorname{e}^{(\gamma_{-1}+\gamma_{0})\left\lVert
q\right\rVert}\,.$

###### Proof.

Since $\Psi$ satisfies A.E.1, for all $(\mu,q)\in[0,1]\times\mathbb{R}^{d}$
and all $\tilde{q}\in\mathbb{R}^{d}$
$\partial_{\mu}\nabla\Psi(\mu,q)\in\mathrm{Im}(\nabla^{2}\Psi(\mu,\tilde{q}))$,
and we can use we can use the second part of Lemma D.5, namely Inequality
(34). Indeed, Eq. (30), in norm, is upper bounded by

$\frac{1}{\lambda_{1}(\mu,q)+\alpha}L_{1}(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)\frac{1}{\lambda_{1}(\mu,\tilde{q})+\alpha}M(\left\lVert
q\right\rVert)\left\lVert q-\tilde{q}\right\rVert\,,$

while (31) is bounded by

$\frac{1}{\lambda_{1}(\mu,\tilde{q})+\alpha}L_{2}(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)\left\lVert
q-\tilde{q}\right\rVert\,.$

Summing these last two displays and using the definition of $w_{-1}$ and the
bounds of A.E.2 allows us to conclude. ∎

###### Proof of Theorem E.3.

Remark that thanks to Lemma E.5, $\Phi$ satisfies the condition of Theorem G.1
with

$a=\Gamma_{-1}\Gamma_{0},\quad
b=2\Gamma_{-1}(\Gamma_{0}\Gamma_{-1}\Gamma_{1}+\Gamma_{2})\quad\text{and}\quad
c=(\gamma_{-1}+\gamma_{0}+\gamma_{1})\vee\gamma_{2}.$

Furthermore, Eq. (35) can be translated into

$2b<\operatorname{exp}\left(-2c\left(\left\lVert
q_{0}\right\rVert+a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}\right)\right).$

which is exactly the condition of application of Theorem G.1. It ensure that
there exists a unique solution $\mu\mapsto q(\mu)$ to Eq. (22). Following the
proof of Theorem D.4 we can conclude easily. ∎

##  Appendix F Specializing our results for doc2vec

In the previous sections, we have seen that, under some technical assumptions
on $\Psi$, the mapping $q$ is solution to an ODE, and we proved some bounds on
$\left\lVert q(\mu)-q(0)\right\rVert$ (by means of Theorem E.3). In this
section, we check that these assumptions are satisfied for the $\Psi$
occurring when considering doc2vec embeddings. That is,
$\Psi=\Psi^{\text{lin}}$, where $\Psi^{\text{lin}}$ is defined by Eq. (12).
This is embodied as Theorem F.7, which is Theorem 5.1 with explicit constants.
We first prove a useful bound on the norm of $\pi_{t}$:

######  Lemma F.1 (Bound on $\pi_{t}$).

Define

$\Pi\vcentcolon=2\nu\sigma_{\max}(R)\cdot\sup_{i}\left\lVert
P_{:,i}\right\rVert\,.$

Then, for any document $x$ and any position $t\in x$, it holds that

$\left\lVert\pi_{t}\right\rVert\leq\Pi\,.$

We emphasize that Lemma F.1 is true regardless of the model used (PVDMmean,
PVDMconcat, PVDBOW), even though this bound can be strengthened for specific
models. Moreover, it only depends on the $P$ and $R$ matrices, which are fixed
matrices after training.

###### Proof.

Recall that we defined $\pi_{t}=RPh_{t}$. For PVDBOW, $h_{t}=0$ and there is
nothing to prove. Otherwise, let us first write

$\left\lVert\pi_{t}\right\rVert=\left\lVert
RPh_{t}\right\rVert\leq\sigma_{\max}(R)\cdot\left\lVert Ph_{t}\right\rVert\,$

and focus on $\left\lVert Ph_{t}\right\rVert$. Let us assume that we work with
PVDMconcat. Since, in that case, $h_{t}$ is the concatenation of $2\nu$
arbitrary one-hot vectors, $Ph_{t}$ is the sum of $2\nu$ arbitrary columns of
$P$. Using the triangle inequality, we deduce that $\left\lVert
Ph_{t}\right\rVert$ is smaller than $2\nu$ times the largest norm of a column
of $P$. When PVDMmean is used, the reasoning is similar. Ignoring the
$1/(2\nu)$ factor (which we consider to be part of $P$), the bound is the
same. ∎

Since the matrix $R$ appears in all the definition of the embeddings, one
needs some (mild) assumptions on $R$. The first one ensures that the condition
number of $R$ is not equal to $+\infty$.

######  Assumption F.2 (Condition number of $R$).

Let us $R\in\mathbb{R}^{D\times d}$. We assume that
$\mathrm{Im}(R)\subset\mathds{1}^{\perp}$, and further that the smallest
singular value of $R$ is non-negative, that is,

$\sigma_{\min}(R)>0\,.$

The requirement for the range of $R$ is needed here in order to work in the
setting of Lemma H.6 and H.8, and then use the nice bounds for the
(local)-Lipschitz constant of the softmax and its Jacobian.

######  Lemma F.3.

Suppose that A.F.2 hold. Then $\Psi^{\text{lin}}$ satisfies A.D.1.

###### Proof.

Recall that $\mathcal{S}$ denotes the set of modified words. Coming back to
the definition of $F$ and $G$, we see that, when forming the difference $F-G$,
many cancellations happen. To be more precise, replacing a word at position
$t$ only modifies $\pi_{s}$ for $s$ belonging to the neighborhood of $t$. Thus

$G(q)-F(q)=\sum_{t\in\mathcal{E}}\Big{(}\psi_{\tilde{x}_{t}}(\tilde{\pi}_{t}+Rq)-\psi_{x_{t}}(\pi_{t}+Rq)\Big{)}\,,$
(36)

where $\mathcal{E}\subseteq\\{s\in[T],\left\lvert s-t\right\rvert\leq\nu\text{
with }t\in\mathcal{S}\\}$. In particular, there is a numerical constant
$\ell>0$ such that
$\left\lvert\mathcal{E}\right\rvert\leq\ell\nu\left\lvert\mathcal{S}\right\rvert$.
From the definition of $\Psi^{\text{lin}}$, Eq. (36), and Lemma H.1, we deduce
that

$\displaystyle\nabla\Psi^{\text{lin}}(\mu,q)=$ $\displaystyle
R^{\top}\left(\mu\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\nabla\psi_{x_{t}}(\pi_{t}+Rq)-\nabla\psi_{\tilde{x}_{t}}(\tilde{\pi}_{t}+Rq)\big{)}+\frac{1}{T}\sum_{t\in
x}\nabla\psi_{x_{t}}(\pi_{t}+Rq)\right)R$ $\displaystyle=$ $\displaystyle
R^{\top}\Bigg{(}-\mu\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\sigma(\pi_{t}+Rq)-\sigma(\tilde{\pi}_{t}+Rq)\big{)}+\mu\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\mathds{1}_{x_{t}}-\mathds{1}_{\tilde{x}_{t}}\big{)}-\frac{1}{T}\sum_{t\in
x}\big{(}\sigma(\pi_{t}+Rq)-\mathds{1}_{x_{t}}\big{)}\Bigg{)},$
$\displaystyle\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,q)=$ $\displaystyle
R^{\top}\Bigg{(}\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\mathds{1}_{x_{t}}-\mathds{1}_{\tilde{x}_{t}}\big{)}-\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\sigma(\pi_{t}+Rq)-\sigma(\tilde{\pi}_{t}+Rq)\big{)}\Bigg{)}$
$\displaystyle=$ $\displaystyle
R^{\top}\left(\frac{1}{T}\sum_{t\in\mathcal{E}}\int_{0}^{1}\Big{(}\big{(}\mathds{1}_{x_{t}}-\mathds{1}_{\tilde{x}_{t}}\big{)}-\nabla\sigma(u(\pi_{t}-\tilde{\pi}_{t})+Rq)(\pi_{t}-\tilde{\pi}_{t})\Big{)}\mathop{}\\!\mathrm{d}u\right)$

and

$\nabla^{2}\Psi^{\text{lin}}(\mu,q)=R^{\top}\Bigg{(}\mu\frac{1}{T}\sum_{t\in\mathcal{E}}\left(\nabla\sigma(\pi_{t}+Rq)-\nabla\sigma(\tilde{\pi}_{t}+Rq)\right)+\frac{1}{T}\sum_{t\in
x}\nabla\sigma(\pi_{t}+Rq)\Bigg{)}R,$ (37)

where we remind that
$\nabla\sigma=\operatorname{diag}(\sigma)-\sigma\sigma^{\top}$. Hence,
$\nabla^{2}\Psi^{\text{lin}}(\mu,\cdot)$ is a symmetric non-negative matrix
and $\Psi^{\text{lin}}$ satisfies A.D.1. ∎

Next, we show that $\Psi^{\text{lin}}$ satisfies A.E.1.

######  Lemma F.4.

Suppose that A.F.2 holds. For all $\mu\in[0,1]$ and all $q\in\mathbb{R}^{d}$,

$\mathrm{Ker}\left(\nabla^{2}\Psi^{\text{lin}}(\mu,q)\right)=\\{0\\}\,,$

and $\Psi^{\text{lin}}$ satisfies A.E.1 with $N_{0}=d$. Let us recall that we
defined $\lambda_{1}$ the smallest non-zero eigenvalue of the Hessian of
$\Psi^{\text{lin}}$. Then, for all $(\mu,q)\in[0,1]\times\mathbb{R}^{d}$, it
holds that

$\lambda_{1}(\mu,q)\geq\operatorname{e}^{-2\sqrt{2}\Pi}\frac{1}{D}\sigma_{\min}(R)^{2}\operatorname{e}^{-2\sqrt{2}\sigma_{\max}(R)\left\lVert
q\right\rVert}\,.$

###### Proof.

Let us remind from Lemma H.5 the definition of $\lambda_{\min}$, namely for
$z\in\mathbb{R}^{D}$,

$\lambda_{\min}(z)=\min\left(\mathrm{Spec}\left(\operatorname{diag}\left(\sigma(z)\right)-\sigma(z)\sigma(z)^{\top}\right)\backslash\\{0\\}\right)\,.$

For $q,y\in\mathbb{R}^{d}$ and since $Ry\in\mathds{1}^{\perp}$ (thanks to
A.F.2), the minimax theorem allows us to write (using Eq. (37))

$\displaystyle\langle\nabla^{2}\Psi^{\text{lin}}(\mu,q)y,y\rangle=$
$\displaystyle\mu\frac{1}{T}\sum_{t\in
x}\left\langle\left(\nabla\sigma(\tilde{\pi}_{t}+Rq)\right)(Ry),(Ry)\right\rangle$
$\displaystyle+(1-\mu)\frac{1}{T}\sum_{t\in
x}\left\langle\left(\nabla\sigma(\pi_{t}+Rq)\right)(Ry),(Ry)\right\rangle$
$\displaystyle\geq$ $\displaystyle\frac{1}{T}\sum_{t\in
x}\left(\mu\lambda_{\min}(\tilde{\pi}_{t}+Rq)+(1-\mu)\lambda_{\min}(\pi_{t}+Rq)\right)\left\lVert
Ry\right\rVert^{2}\,.$

Here we have crucialy used A.F.2 and in particular the fact that
$\mathrm{Im}(R)\subset\mathds{1}^{\perp}$ and that
$\pi_{t}\in\mathds{1}^{\perp}$ in order to make $\lambda_{\min}$ appears. Let
us set

$\sigma_{(1)}(z)=\min_{i\in[D]}\sigma_{i}(z)\,.$

Thanks to Lemma H.5, one has

$\langle\nabla^{2}\Psi^{\text{lin}}(\mu,q)y,y\rangle\geq\frac{1}{T}\sum_{t\in
x}\left(\mu
D\sigma_{(1)}(\tilde{\pi}_{t}+Rq)^{2}+(1-\mu)D\sigma_{(1)}(\pi_{t}+Rq)^{2}\right)D\left\lVert
Ry\right\rVert^{2}\,.$

Furthermore, thanks to Theorem H.9,

$\sigma_{(1)}(z)\geq\frac{1}{D}\operatorname{e}^{-\sqrt{2}\left\lVert
q\right\rVert},$

and we have

$\displaystyle\langle\nabla^{2}\Psi^{\text{lin}}(\mu,q)y,y\rangle\geq$
$\displaystyle\frac{1}{T}\sum_{t\in
x}\left(\mu\operatorname{exp}\left(-2\sqrt{2}\left\lVert\tilde{\pi}_{t}+Rq\right\rVert\right)+(1-\mu)\operatorname{exp}\left(-2\sqrt{2}\left\lVert\pi_{t}+Rq\right\rVert\right)\right)\frac{1}{D}\left\lVert
Ry\right\rVert^{2}$ $\displaystyle\geq$
$\displaystyle\operatorname{e}^{-2\sqrt{2}\Pi}\operatorname{e}^{-2\sqrt{2}\left\lVert
Rq\right\rVert}\frac{1}{D}\left\lVert Ry\right\rVert^{2}$ $\displaystyle\geq$
$\displaystyle\operatorname{e}^{-2\sqrt{2}\Pi}\operatorname{e}^{-2\sqrt{2}\sigma_{\max}(R)\left\lVert
q\right\rVert}\frac{1}{D}\sigma_{\min}(R)^{2}\left\lVert y\right\rVert^{2},$

where we remind that $\Pi$ is defined in Lemma F.1. This implies that
$\mathrm{Ker}\left(\nabla^{2}\Psi^{\text{lin}}(\mu,q)\right)=\\{0\\}$, that
$\Psi^{\text{lin}}$ fulfills A.E.1 with $N_{0}=d$, and that

$\lambda_{1}(\mu,q)\geq\operatorname{e}^{-2\sqrt{2}\Pi}\frac{1}{D}\sigma_{\min}(R)^{2}\operatorname{e}^{-2\sqrt{2}\sigma_{\max}(R)\left\lVert
q\right\rVert}.$ (38)

∎

Next, we show that $\Psi^{\text{lin}}$ satisfies A.E.2.

######  Lemma F.5 (Local Lipschitz continuity of $\Psi^{\text{lin}}$).

Suppose that A.F.2 holds. Then $\Psi^{\text{lin}}$ satisfies A.E.2 with

$\Gamma_{-1}=D\operatorname{e}^{2\sqrt{2}\Pi}\frac{1}{\sigma_{\min}(R)^{2}},\quad\Gamma_{0}=4\ell\nu\sigma_{\max}(R)\frac{\left\lvert\mathcal{S}\right\rvert}{T}\,,\quad\Gamma_{1}=\frac{8\operatorname{e}^{6\sqrt{2}\Pi}}{(D-1)}\sigma_{\max}(R)^{3}\,,\quad\Gamma_{2}=\frac{4\ell\nu\Pi\operatorname{e}^{4\sqrt{2}\Pi}}{D-1}\sigma_{\max}(R)^{2}\frac{\left\lvert\mathcal{S}\right\rvert}{T}\,,$

and

$\gamma_{-1}=2\sqrt{2}\sigma_{\max}(R)\,,\quad\gamma_{0}=0\,,\quad\gamma_{1}=3\sqrt{2}\sigma_{\max}(R)\,,\quad\text{and}\quad\gamma_{2}=2\sqrt{2}\sigma_{\max}(R)\,.$

###### Proof.

We have for all $\mu\in[0,1]$ and all $q\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,q)\right\rVert\leq$
$\displaystyle\left\lVert
R^{\top}\Bigg{(}\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\mathds{1}_{x_{t}}-\mathds{1}_{\tilde{x}_{t}}\big{)}-\frac{1}{T}\sum_{t\in\mathcal{E}}\big{(}\sigma(\pi_{t}+Rq)-\sigma(\tilde{\pi}_{t}+Rq)\big{)}\Bigg{)}\right\rVert$
$\displaystyle\leq$ $\displaystyle 4\sigma_{\max}(R)\frac{|\mathcal{E}|}{T}$
$\displaystyle\leq$ $\displaystyle
4\ell\nu\sigma_{\max}(R)\frac{\left\lvert\mathcal{S}\right\rvert}{T},$

where we have used the fact that $\left\lVert\sigma\right\rVert\leq 1$ and the
previous bound gives the value of $\Gamma_{0}$ and $\gamma_{0}$. Thanks to
Lemma H.6 $\sigma$ is locally-Lipschitz continuous and thanks to Lemma H.8,
$\nabla\sigma$ is also locally-Lipschitz continuous, hence for
$q,\tilde{q}\in\mathbb{R}^{d}$

$\displaystyle\left\lVert\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,q)-\partial_{\mu}\nabla\Psi^{\text{lin}}(\mu,\tilde{q})\right\rVert\leq$
$\displaystyle\left\lVert
R^{\top}\frac{1}{T}\sum_{t\in\mathcal{E}}\left(\int_{0}^{1}\left(\sigma(u(\pi_{t}-\tilde{\pi}_{t})+Rq)-\sigma(u(\pi_{t}-\tilde{\pi}_{t})+R\tilde{q})\right)(\pi_{t}-\tilde{\pi}_{t})\mathop{}\\!\mathrm{d}u\right)\right\rVert$
$\displaystyle\leq$ $\displaystyle
4\frac{1}{D-1}\operatorname{e}^{2\sqrt{2}(2\Pi+\sigma_{\max}(R)(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert))}\ell\nu\sigma_{\max}(R)^{2}\frac{\left\lvert\mathcal{S}\right\rvert}{T}\Pi\left\lVert
q-\tilde{q}\right\rVert$ $\displaystyle\leq$
$\displaystyle\frac{4\ell\nu\Pi\operatorname{e}^{4\sqrt{2}\Pi}}{D-1}\frac{\left\lvert\mathcal{S}\right\rvert}{T}\operatorname{e}^{2\sqrt{2}\sigma_{\max}(R)(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)}\sigma_{\max}(R)^{2}\left\lVert
q-\tilde{q}\right\rVert\,,$

where we have used Lemma H.6 and the bound $\frac{D}{D-1}\leq 2$, which gives
the value of $\Gamma_{2}$ and $\gamma_{2}$. Finally, let us remark that

$\displaystyle\left\lVert\nabla^{2}\Psi^{\text{lin}}(\mu,q)-\nabla^{2}\Psi^{\text{lin}}(\mu,q)\right\rVert_{\mathrm{op}}\leq$
$\displaystyle\mu\frac{1}{T}\sum_{t\in x}\left\lVert
R^{\top}\left(\nabla\sigma(\tilde{\pi}_{t}+Rq)-\nabla\sigma(\tilde{\pi}_{t}+R\tilde{q})\right)R\right\rVert$
$\displaystyle+(1-\mu)\frac{1}{T}\sum_{t\in x}\left\lVert
R^{\top}\left(\nabla\sigma({\pi}_{t}+Rq)-\nabla\sigma({\pi}_{t}+R\tilde{q})\right)R\right\rVert$
$\displaystyle\leq\frac{8\operatorname{e}^{6\sqrt{2}\Pi}}{(D-1)}\sigma_{\max}(R)^{3}\operatorname{e}^{3\sqrt{2}\sigma_{\max}(R)(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)}\left\lVert
q-\tilde{q}\right\rVert\,,$

which gives the value of $\Gamma_{1}$ and $\gamma_{1}$. Finally, Eq. 38 gives
directly that

$w_{-1}(\rho)=\operatorname{e}^{-2\sqrt{2}\Pi}\frac{1}{D}\sigma_{\min}(R)^{2}\operatorname{e}^{-2\sqrt{2}\sigma_{\max}(R)\left\lVert
q\right\rVert}\,,$

which concludes the proof. ∎

Next, we show that $\left\lVert q_{0}\right\rVert$ is not too large.

######  Lemma F.6 (Bound on $\left\lVert q_{0}\right\rVert$).

Suppose that A.F.2 holds. Then

$\left\lVert q_{0}\right\rVert\leq\frac{\sqrt{2}\sigma_{\max}(R)}{\alpha}\,.$

We demonstrate Lemma F.6 in practice in Section I.2. The key idea behind the
proof is that the regularization term $\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}$ prevents $q$ from escaping to infinity.

###### Proof.

Let us recall that

$q_{0}=\operatorname*{arg\,min}_{q\in\mathbb{R}^{d}}\left\\{\frac{1}{T}\sum_{t\in
x}\psi_{x_{t}}(\pi_{t}+Rq)+\frac{\alpha}{2}\left\lVert
q\right\rVert^{2}\right\\}\,.$

In view of Lemma F.3, $q_{0}$ is the unique solution of the following
equation:

$R^{\top}\left(\frac{1}{T}\sum_{t\in
x}\Big{(}\sigma(\pi_{t}+Rq)-\mathds{1}_{x_{t}}\Big{)}\right)+\alpha q=0\,.$
(39)

From Eq. (39), we deduce that

$\left\lVert q_{0}\right\rVert=\frac{1}{T\alpha}\left\lVert
R^{\top}\left(\sum_{t\in
x}\Big{(}\sigma(\pi_{t}+Rq_{0})-\mathds{1}_{x_{t}}\Big{)}\right)\right\rVert\,.$

By definition of $\sigma_{\max}(R)$ and the triangle inequality, this is upper
bounded by

$\frac{\sigma_{\max}(R)}{T\alpha}\sum_{t\in
x}\left\lVert\sigma(\pi_{t}+Rq_{0})-\mathds{1}_{x_{t}}\right\rVert\,.$ (40)

But we notice that, for any $q\in\mathbb{R}^{d}$ and $t\in x$,

$\displaystyle\left\lVert\sigma(\pi_{t}+Rq)-\mathds{1}_{x_{t}}\right\rVert^{2}=$
$\displaystyle\sum_{j\neq
x_{t}}\sigma_{j}(\pi_{t}+Rq)^{2}+(\sigma_{x_{t}}(\pi_{t}+Rq)-1)^{2}$
$\displaystyle=$
$\displaystyle\sum_{j}\sigma_{j}(\pi_{t}+Rq)^{2}+1-2\sigma_{x_{t}}(\pi_{t}+Rq)$
$\displaystyle\left\lVert\sigma(\pi_{t}+Rq)-\mathds{1}_{x_{t}}\right\rVert^{2}\leq$
$\displaystyle 2\,,$

where we have used the fact that $\left\lVert\sigma\right\rVert\leq 1$ and
$\sigma_{i}\geq 0$. Hence each term in Eq. (40) is upper bounded by
$\sqrt{2}$. Keeping in mind that the summation over $t\in x$ has at most $T$
terms, we deduce the result. ∎

We are now ready to apply case $c>0$ of Theorem G.1 to obtain the promised
quantitative bounds.

######  Theorem F.7 (Quantitative bounds for doc2vec embeddings).

Let $\Psi^{\text{lin}}$ defined in Eq. (12), and suppose A.F.2 holds. Let us
define

$A\vcentcolon=4\ell\nu
D\operatorname{e}^{2\sqrt{2}\Pi}\frac{\sigma_{\max}(R)}{\sigma_{\min}(R)^{2}}\,,$
$B\vcentcolon=64\ell\nu
D\frac{\sigma_{\max}(R)^{2}}{\sigma_{\min}(R)^{2}}\operatorname{e}^{10\sqrt{2}\Pi}\left(\frac{\sigma_{\max}(R)^{2}}{\sigma_{\min}(R)^{2}}+\frac{\Pi}{D-1}\right)\,,$

and

$C\vcentcolon=5\sqrt{2}\sigma_{\max}(R)\,.$

Suppose that

$\frac{\left\lvert\mathcal{S}\right\rvert}{T}\leq\frac{1}{2B}\operatorname{e}^{-2\left(AC+1\right)\operatorname{e}^{C\frac{\sqrt{2}\sigma_{\max}(R)}{\alpha}}}\,,$
(41)

Then

$\sup_{\mu\in[0,1]}\left\lVert q(\mu)-q_{0}\right\rVert\leq
2A\operatorname{e}^{C\left\lVert
q_{0}\right\rVert}\frac{\left\lvert\mathcal{S}\right\rvert}{T}\,.$ (42)

###### Proof.

Remark that $\Psi^{\text{lin}}$ satisfies A.(D.1) (Lemma F.3), A.(E.1) (Lemma
F.4) and A.(E.2) (Lemma F.5). Therefore the assumptions of Theorem E.3 are
satisfied. Let us note that

$\gamma_{0}\gamma_{-1}=A\frac{\left\lvert\mathcal{S}\right\rvert}{T}\,,$
$2\Gamma_{-1}(\Gamma_{-1}\Gamma_{1}\Gamma_{0}+\Gamma_{2})\leq
B\frac{\left\lvert\mathcal{S}\right\rvert}{T}$

and

$(\gamma_{-1}+\gamma_{1})\vee\gamma_{2}=C\,.$

Remark that in that setting, thanks to Lemma F.6, $\left\lVert
q_{0}\right\rVert\leq\frac{\sqrt{2}\sigma_{\max}(R)}{\alpha}$. We also have
the following straightforward bounds:

$\frac{\left\lvert\mathcal{S}\right\rvert}{T}\leq 1\quad\text{and}\quad
C\left\lVert q_{0}\right\rVert\leq\operatorname{e}^{C\left\lVert
q_{0}\right\rVert}\leq\operatorname{e}^{C\frac{\sqrt{2}\sigma_{\max}(R)}{\alpha}}\,.$

Using Eq. (41), one necessarily have

$\displaystyle 2B\frac{\left\lvert\mathcal{S}\right\rvert}{T}\leq$
$\displaystyle\operatorname{e}^{-2(AC+1)\operatorname{e}^{C\frac{\sqrt{2}\sigma_{\max}(R)}{\alpha}}}$
$\displaystyle\leq$ $\displaystyle\operatorname{e}^{-2C\left(\left\lVert
q_{0}\right\rVert+A\frac{\left\lvert\mathcal{S}\right\rvert}{T}\operatorname{e}^{C\left\lVert
q_{0}\right\rVert}\right)}\,.$

This guarantees that Eq. (33) and one can apply Theorem E.3, which yields the
desired result. ∎

##  Appendix G Grönwall-Bahouri-Bellman type result

In this section, we collect all results related to ODEs. In our setting, as
seen in Lemma D.6, and in view of A.E.2, the coefficients of Eq. 22 are not
globally Lispchitz (although locally-Lipschitz). Thus, while local existence
and uniqueness of solutions to Eq. (22) is a given (small $\mu$ regime),
existence up to time $1$ and non-explosion of the solutions is much more
challenging to achieve (large $\mu$ regime). Unfortunately, this is the regime
that we are interested into: the local behavior of the ODE at $\mu=0$ does not
tell us anything interesting, since what we aim at is the comparison between
the starting point ($\mu=0$) and final point ($\mu=1$) of the dynamic. Our
strategy is to use an _ad hoc_ extension of the Grönwall-Bahouri-Bellman lemma
to deal with our specific setting.

Our approach is inspired by proofs of Grönwall-Bellman-Bahouri type lemmas,
see for example Dannan (1985); Agarwal et al. (2005); Kim (2009); Pachpatte
(2004). It relies on an explicit integration of the integral inequality which
will pop up in the computations. Note that, instead of generic local constants
$L$, $M$, and $w_{-1}$, and in view of Section F, we will suppose that all
those quantity are locally bounded by some exponential functions. Our
derivation is very close to that of Pachpatte inequality (Pachpatte, 2004),
but here we keep track of the constants. In doing, so we gain an explicit
criteria for non-explosion of the solutions up to time $\mu=1$. To view other
applications of non-explosion on the time-one map, one could also consult
(Bailleul & Catellier, 2020) and the references therein.

######  Theorem G.1 (Grönwall-Bahouri-Bellman type inequality).

Let $\Lambda:[0,1]\times\mathbb{R}^{d}\to\mathbb{R}^{d}$ be a continuous
function and $a,b,c>0$ be numerical constants such that, for all
$q,\tilde{q}\in\mathbb{R}^{d}$,

$\sup_{\mu\in[0,1]}\left\lVert\Lambda(\mu,q)\right\rVert\leq
a\operatorname{e}^{c\left\lVert q\right\rVert}\,,$ (43)

and

$\sup_{\mu\in[0,1]}\left\lVert\Lambda(\mu,q)-\Lambda(\mu,\tilde{q})\right\rVert\leq
b\operatorname{e}^{c(\left\lVert
q\right\rVert\vee\left\lVert\tilde{q}\right\rVert)}\left\lVert
q-\tilde{q}\right\rVert\,.$ (44)

Let $q_{0}\in\mathbb{R}^{d}$ such that either $c=0$ or

$2b<\operatorname{exp}\left(-2c\left(\left\lVert
q_{0}\right\rVert+a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}\right)\right).$ (45)

Then, there exists a unique function $q:[0,1]\to\mathbb{R}^{d}$ such that
$q(0)=0$ and for all $\mu\in[0,1]$

$q^{\prime}(\mu)=\Lambda(\mu,q(\mu))\,.$ (46)

Furthermore, for all $\mu\in[0,1]$,

$\left\lVert q(\mu)-q_{0}\right\rVert\leq\begin{cases}2\mu
a\operatorname{e}^{c\left\lVert q_{0}\right\rVert}&\text{ if }c>0,\\\ \mu
a\operatorname{e}^{b}&\text{ if }c=0\,.\\\ \end{cases}$

###### Proof.

Step 1: Existence of the map satisfying (46). Note that since $\Lambda$ is
locally Lipschitz continuous, thanks to the Cauchy-Lipschitz/Picard-Lindelöf
theorem (see Arnold (1978, Chapter 2)), there exists an open interval
$I^{\star}$ of $[0,1]$ and a unique function $q:I^{\star}\to\mathbb{R}^{d}$
such that $q$ is the unique solution to Eq. (46). Note that an open interval
of $[0,1]$ which contains $0$ is necessarily of the form $[0,\tau)$ with
$0<\tau<1$ or $[0,1]$. Remark also that for all $\mu\in I^{\star}$, thanks to
the regularity assumption on $\Lambda$, on $I^{\star}$,
$\mu\mapsto\Lambda(\mu,q(\mu))$ is continuous and for $\mu\in I^{\star}$ the
following integral equation is satisfied:

$q(\mu)=q_{0}+\int_{0}^{\mu}\Lambda(\tilde{\mu},q(\tilde{\mu}))\mathop{}\\!\mathrm{d}\tilde{\mu}\,.$

Step 2: . Taking the norm in the previous display and using the triangle
inequality, we see that

$\left\lVert
q(\mu)-q_{0}\right\rVert\leq\int_{0}^{\mu}\left\lVert\Lambda(\tilde{\mu},q_{0})\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}+\int_{0}^{\mu}\left\lVert\Lambda(\tilde{\mu},q(\mu))-\Lambda(\tilde{\mu},q_{0})\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}\,.$

Using our assumptions on $\Lambda$, namely Eqs. (43) and (44), we obtain

$\left\lVert q(\mu)-q_{0}\right\rVert\leq\mu a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}+b\int_{0}^{\mu}\operatorname{e}^{c(\left\lVert
q(\tilde{\mu})\right\rVert+\left\lVert q_{0}\right\rVert)}\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}\,.$

Since $\left\lVert q(\tilde{\mu})\right\rVert-\left\lVert
q(q_{0})\right\rVert\leq\left\lVert q(\tilde{\mu})-q_{0}\right\rVert$, we
deduce that

$\displaystyle\left\lVert q(\mu)-q_{0}\right\rVert\leq\mu
a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}+b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\int_{0}^{\mu}\operatorname{e}^{c\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert}\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}\,.$

Let us define for all $\mu\in I^{\star}$,

$\mathcal{Q}(\mu)=\begin{cases}a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}+b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\frac{1}{\mu}\int_{0}^{\mu}\operatorname{e}^{c\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert}\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}&\text{ if
}\mu>0\,,\\\ a\operatorname{e}^{c\left\lVert q_{0}\right\rVert}&\text{ if
}\mu=0\,.\end{cases}$

Note that $\frac{1}{\mu}\int_{0}^{\mu}\operatorname{e}^{c\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert}\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}\to_{\mu\to
0}\operatorname{e}^{c\left\lVert q(0)-q_{0}\right\rVert}\left\lVert
q(0)-q_{0}\right\rVert=0$ and $\mathcal{Q}$ is continuous in $\mu=0$.
Furthermore, for $\mu\in I^{\star}\backslash\\{0\\}$,

$\mathcal{Q}^{\prime}(\mu)=-\frac{1}{\mu^{2}}b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\int_{0}^{\mu}\operatorname{e}^{c\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert}\left\lVert
q(\tilde{\mu})-q_{0}\right\rVert\mathop{}\\!\mathrm{d}\tilde{\mu}+\frac{1}{\mu}b\operatorname{e}^{c\left\lVert
q(\mu)-q_{0}\right\rVert}\left\lVert q(\mu)-q_{0}\right\rVert\,.$ (47)

With this notation in hand, for any $\mu\in I^{\star}\backslash\\{0\\}$,
$\left\lVert q(\mu)-q_{0}\right\rVert\leq\mu\mathcal{Q}(\mu)$. Since we
restrict our attention to $\mu\leq 1$, we have

$\left\lVert q(\mu)-q_{0}\right\rVert\leq\mathcal{Q}(\mu)\,.$ (48)

Step 3: Differential inequality. Since $x\mapsto x\operatorname{e}^{cx}$ is a
non-decreasing function, we have for $\mu\in I^{\star}\backslash\\{0\\}$

$\displaystyle\mathcal{Q}^{\prime}(\mu)$ $\displaystyle\leq
b\operatorname{e}^{2c\left\lVert q_{0}\right\rVert}\frac{\left\lVert
q(\mu)-q_{0}\right\rVert}{\mu}\operatorname{e}^{c\mu\frac{\left\lVert
q(\mu)-q_{0}\right\rVert}{\mu}}$ $\displaystyle\leq
b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\mathcal{Q}(\mu)\operatorname{e}^{c\mathcal{Q}(\mu)}\,,$
(49)

where we used Eq. (47) for a direct bound one the derivative and Eq. (48) to
obtain the last display.

Step 4: Cauchy-Lipschitz setting ($c=0$). Suppose for a moment that $c=0$ so
that we are in the standard setting of global Cauchy-Lipschitz/Picard Lindelöf
Theorem and standard Grönwall Lemma. We have for $\mu\in I^{\star}$

$\log\left(\frac{\mathcal{Q}(\mu)}{a}\right)\leq b\mu\,,$

$I^{\star}=[0,1]$ and

$\left\lVert q(\mu)-q_{0}\right\rVert\leq\mu\mathcal{Q}(\mu)\leq
a\mu\operatorname{e}^{b\mu}\,.$

Step 5: Grönwall-Bahouri-Bellman integration ($c>0$). Suppose now that $c>0$.
Let $\beta>0$. Let us remark that for all $x\geq 0$,
$x\operatorname{e}^{cx}\leq\frac{1}{c}\operatorname{e}^{2cx}$, and we have

$\mathcal{Q}^{\prime}(\mu)\leq\frac{b}{c}\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\operatorname{e}^{2c\mathcal{Q}(\mu)}\,.$ (50)

Multiplying both sides of Eq. (50) by
$\operatorname{e}^{-2c\mathcal{Q}(\mu)}$, one recognize (up to constants) the
derivative of $\operatorname{e}^{-2c\mathcal{Q}}$. Integrating from $0$ to
$\mu$, we have proved that

$\frac{\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-\operatorname{e}^{-2c\mathcal{Q}(\mu)}}{2}\leq
b\operatorname{e}^{2c\left\lVert q_{0}\right\rVert}\mu\,.$ (51)

When

$\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\mu>0\,,$ (52)

we have

$\operatorname{e}^{c\mathcal{Q}(\mu)}\leq\left(\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\mu\right)^{-\frac{1}{2}}\,.$ (53)

Furthermore, whenever Eq (45) holds (namely Eq. (52) is true for all
$\mu\in[0,1]$) we can take $I^{\star}=[0,1]$, since Eq. (53) guaranty that
$\mathcal{Q}$ does not explode.

For $\mu\in I^{\star}\backslash\\{0\\}$ which satisfies Eq. (52), when using
the previous bound and Eq. (49), we have the following inequality :

$\mathcal{Q}^{\prime}(\mu)\leq b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\left(\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\mu\right)^{-\frac{1}{2}}\mathcal{Q}(\mu)\,.$

When dividing by $\mathcal{Q}(\mu)$ and integrating, we get

$\log(\mathcal{Q}(\mu))-\log(\mathcal{Q}(0))\leq\operatorname{exp}\left(b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\int_{0}^{\mu}\left(\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\tilde{\mu}\right)^{-\frac{1}{2}}\mathop{}\\!\mathrm{d}\tilde{\mu}\right)\,.$

Therefore, for all $\mu$ which satisfies Eq. (52),

$\displaystyle\left\lVert q(\mu)-q_{0}\right\rVert\leq\mu\mathcal{Q}(\mu)\leq$
$\displaystyle\mu a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}\operatorname{exp}\left(\int_{0}^{\mu}b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\left(\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\tilde{\mu}\right)^{-\frac{1}{2}}\mathop{}\\!\mathrm{d}\tilde{\mu}\right)$
$\displaystyle\leq$ $\displaystyle\mu a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}\operatorname{exp}\left(\left(\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}\right)^{\frac{1}{2}}-\left(\operatorname{e}^{-2ca\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}}-2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\mu\right)^{\frac{1}{2}}\right)$ (54) $\displaystyle\leq$
$\displaystyle\mu a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}\operatorname{exp}\left(\left(2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\mu\right)^{\frac{1}{2}}\right)\,,$

where we have use that for $0\leq v<\tilde{v}$,
$\sqrt{\tilde{v}}-\sqrt{v}\leq\sqrt{\tilde{v}-v}$. Note that Eq. (54) makes
sense since Eq. (52) is satisfied. Finally, one can use Eq. (52) and write

$2b\operatorname{e}^{2c\left\lVert q_{0}\right\rVert}\mu\leq
2b\operatorname{e}^{2c\left\lVert
q_{0}\right\rVert}\leq\operatorname{e}^{-2ac\operatorname{e}^{2\left\lVert
q_{0}\right\rVert}}\leq 1\,,$

which gives

$\left\lVert q(\mu)-q_{0}\right\rVert\leq\mu 2a\operatorname{e}^{c\left\lVert
q_{0}\right\rVert}\,,$

which is the wanted result. ∎

######  Remark G.2 (Improving Theorem F.7).

There are several open avenues to improve Theorem F.7. One possibility is to
keep a finer the dependency in $\mu$ when bounding $\left\lVert
q(\mu)-q_{0}\right\rVert$ (namely keeping the $\mu$ factor when deriving Eq.
(48)). A second possible improvement is to use a finer inequality than
$y\leq\operatorname{e}^{y}$ when deriving Eq. (50). Unfortunately, in both
cases, we were unsuccessful in integrating these more complicated expressions
in a tractable form (derivation leading to Eq. (51)).

##  Appendix H Technical results related to the softmax function

In this section, we collect all technical facts related to the softmax
function used throughout the proofs. Let us recall that we defined the softmax
function from $\mathbb{R}^{D}$ to $\mathbb{R}^{D}$ as
$\sigma(x)=(\sigma_{1}(x),\ldots,\sigma_{D}(x))^{\top}$, where for all
$i\in[D]$,

$\sigma_{i}(x)=\frac{\operatorname{e}^{x_{i}}}{\sum_{j=1}^{D}\operatorname{e}^{x_{j}}}.$

We also defined, for all $x\in\mathbb{R}^{D}$ and all $i\in[D]$,

$\psi_{i}(x)=-\log(\sigma_{i}(x))\,.$

###  H.1 Basics on the softmax function

We start by recalling elementary properties of the softmax function.

######  Lemma H.1 (Softmax derivatives).

We have

$\frac{\partial}{\partial
x_{k}}\sigma_{\ell}(x)=\begin{cases}\sigma_{k}(x)(1-\sigma_{k}(x))&\text{ if
}k=\ell\\\ -\sigma_{k}(x)\sigma_{\ell}(x)&\text{ otherwise.}\end{cases}$

In a more concise way,

$\nabla\sigma(x)=\operatorname{diag}(\sigma(x))-\sigma(x)\sigma(x)^{\top}\,.$

A straightforward consequence of Lemma H.1 is the computation of the first
derivatives of $\psi_{i}$ (these are very standard computations, see for
instance Proposition 1 and 2 in Gao & Pavel (2017)).

######  Lemma H.2 (Gradient of $\psi_{i}$).

We have

$\frac{\partial}{\partial
x_{k}}\psi_{i}(x)=\begin{cases}-1+\sigma_{k}(x)&\text{ if }k=i\\\
\sigma_{k}(x)&\text{ otherwise.}\end{cases}$

In more concise notation, $\nabla\psi_{i}=\sigma-\mathds{1}_{i}$.

Similarly, we have:

######  Lemma H.3 (Hessian of $\psi_{i}$).

We have

$\frac{\partial^{2}}{\partial x_{k}\partial
x_{\ell}}\psi_{i}(x)=\begin{cases}\sigma\left(x\right)_{k}(1-\sigma\left(x\right)_{k})\text{
if }k=\ell\\\ -\sigma\left(x\right)_{k}\sigma\left(x\right)_{\ell}\text{
otherwise.}\end{cases}$

In more concise notation,

$\nabla^{2}\psi_{i}=\nabla\sigma=\operatorname{diag}(\sigma)-\sigma\sigma^{\top}.$
(55)

######  Corollary H.4 (Convexity of log-softmax).

For any $i\in[D]$, the function $\psi_{i}$ is convex.

The proof of the previous fact relies on the Courant minimax theorem, which
gives the value of the eigenvalue of a real symmetric matrix. Furthermore, we
also use that fact that a function such that its Hessian is a non-negative
symmetric matrix is convex.

###### Proof.

Let $x,v\in\mathbb{R}^{D}$. Since $\sum_{i}\sigma_{i}(x)=1$, we have

$\displaystyle\langle\nabla^{2}\psi_{i}(x)v,v\rangle$
$\displaystyle=\sum_{k}\sigma_{k}(x)v_{k}^{2}-\sum_{k}\sigma_{k}(x)\sum_{\ell}\sigma_{\ell}(x)v_{\ell}v_{k}$
$\displaystyle=\sum_{k}\sigma_{k}(x)v_{k}^{2}-\left(\sum_{k}\sigma_{k}(x)v_{k}\right)^{2}=\sum_{k}\sigma_{k}(x)\left(v_{k}-\sum_{\ell}\sigma_{\ell}(x)v_{\ell}\right)^{2}\geq
0\,,$

Hence, thanks to the Courant minimax principle, all the eigenvalues of
$\nabla^{2}\psi_{i}$ are non-negative. Hence $\nabla^{2}\psi_{i}$ is a non-
negative symmetric matrix, and $\psi_{i}$ is a convex function. ∎

The following proposition controls the spectrum of the Hessian of $\psi_{i}$,
that is the gradient of the softmax, in function of the minimal and maximal
values of the softmax function.

######  Lemma H.5 (Spectrum of the softmax Jacobian).

Let $\rho>0$. For $x\in\mathbb{R}^{D}$, let us define

$\sigma_{(1)}(x)\vcentcolon=\min_{i\in[D]}\sigma_{i}(x)\,,$

and

$\sigma_{(D)}(x)\vcentcolon=\max_{i\in[D]}\sigma_{i}(x)\,.$

Let us define

$\lambda_{\min}(x)\vcentcolon=\min\left\\{\mathrm{Spec}\left(\nabla\sigma(x)\right)\backslash\\{0\\}\right\\}\,,$

and

$\lambda_{\max}(x)\vcentcolon=\max\left\\{\mathrm{Spec}\left(\nabla\sigma(x)\right)\right\\}\,.$

Then

$D\sigma_{(1)}^{2}(x)\leq\lambda_{\min}(x)\leq\lambda_{\max}(x)\leq
D\sigma_{(D)}^{2}(x)\,.$

###### Proof.

According to Lemma H.3,

$\nabla\sigma(x)=\operatorname{diag}(\sigma(x))-\sigma(x)\sigma(x)^{\top}\,.$

This matrix is symmetric, and according to Corollary H.4, its eigenvalues are
non-negative real numbers. Since $\sum_{i}\sigma_{i}(x)=1$, one has

$\nabla\sigma(x)\mathds{1}=0\,,$

where, as before, $\mathds{1}=(1,\ldots,1)^{\top}$. Since for all $i\in[D]$,
$\sigma_{i}(x)\neq 0$, if $v\in\mathrm{Ker}\left(\nabla\sigma(x)\right)$ then
necessarily for all $i\in[D]$,
$v_{i}\sigma_{i}(x)-\sigma_{i}(x)\sum_{j}\sigma_{j}(x)v_{j}=0$, and
$v=v_{1}\mathds{1}$. Hence, $\mathrm{Im}(\nabla\sigma(x))=\mathds{1}^{\perp}$
and
$\mathrm{Ker}\left(\nabla\sigma(x)\right)=\operatorname{Vec}\left(\mathds{1}\right)$.
Using the Courant minimax characterization of eigenvalues, we have

$\lambda_{\min}(x)=\min_{\begin{subarray}{c}v\in\mathds{1}^{\perp}\\\
\left\lVert
v\right\rVert=1\end{subarray}}\langle\nabla\sigma(x)v,v\rangle=\min_{\begin{subarray}{c}v\in\mathds{1}^{\perp}\\\
\left\lVert
v\right\rVert=1\end{subarray}}v^{\top}\left(\nabla\sigma(x)\right)v\quad\text{and}\quad\lambda_{\max}(x)=\max_{\begin{subarray}{c}v\in\mathds{1}^{\perp}\\\
\left\lVert
v\right\rVert=1\end{subarray}}\langle\nabla\sigma(x)v,v\rangle=\max_{\begin{subarray}{c}v\in\mathds{1}^{\perp}\\\
\left\lVert
v\right\rVert=1\end{subarray}}v^{\top}\left(\nabla\sigma(x)\right)v\,.$ (56)

Note then that for $v\in\mathds{1}^{\perp}$ (and dropping the $x$ dependency),

$v^{\top}\left(\nabla\sigma(x)\right)v=\sum_{i=1}^{D}\sigma_{i}v_{i}^{2}-\left(\sum_{i=1}^{D}\sigma_{j}v_{j}\right)^{2}\,.$

Now, the Cauchy-Schwarz inequality guarantees that the previous display is
non-negative, but this is not enough to conclude. We resort to the _four-
letter identity_ (Steele (2004, Exercise 3.7), see also Garreau & Mardaoui
(2021, Proposition 13)) to write

$v^{\top}\left(\nabla\sigma(x)\right)v=\sum_{i=1}^{D}\sigma_{i}v_{i}^{2}-\left(\sum_{i=1}^{D}\sigma_{i}v_{i}\right)^{2}=\sum_{j<k}\sigma_{j}\sigma_{k}(v_{k}-v_{j})^{2}\,.$
(57)

Keeping in mind that the $\sigma_{i}$s are non-negative, this last identity
gives

$\sigma_{(1)}^{2}\sum_{j<k}\sigma_{j}\sigma_{k}(v_{k}-v_{j})^{2}\leq
v^{\top}\left(\nabla\sigma(x)\right)v\leq\sigma_{(D)}^{2}\sum_{j<k}\sigma_{j}\sigma_{k}(v_{k}-v_{j})^{2}\,.$

In the term

$\left(\sigma_{(1)}\right)^{2}\cdot\sum_{j<k}(v_{k}-v_{j})^{2}\,.$

we recognize ($D^{2}$ times) the _variance_ of the $v_{i}$s. More precisely,

$\frac{1}{D^{2}}\sum_{j<k}(v_{k}-v_{j})^{2}=\frac{1}{D}\sum_{i=1}^{D}\left(v_{i}-\frac{1}{D}\sum_{j}v_{j}\right)^{2}\,.$

Since $v\in\operatorname{Vec}\left(\mathds{1}\right)^{\bot}$, we know that
$\sum_{j}v_{j}=0$, and the previous display reduces to ($1/D$ times) the norm
of $v$. Whenever $\left\lVert v\right\rVert=1$ and $v\in\mathds{1}^{\perp}$ we
have shown

$D\sigma_{(1)}(x)^{2}\leq v^{\top}\left(\nabla\sigma(x)\right)v\leq
D\sigma_{(D)}(x)^{2}.$

Coming back to the characterization of the eigenvalues given by Eq. (56), we
deduce the result. ∎

The previous bound, associated with estimates on the infimum and supremum of
the softmax function on balls gives estimates on the (local)-Lipschitz
constant of the softmax.

######  Lemma H.6 (local-Lipschitz continuity of the softmax).

For all $x,y\in\mathbb{R}^{D}$ such that $x,y\in\mathds{1}^{\perp}$,

$\left\lVert\sigma(x)-\sigma(y)\right\rVert\leq\frac{D}{(D-1)^{2}}\operatorname{exp}\left(2\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert y\right\rVert)\right)\left\lVert
x-y\right\rVert\,.$

In order to prove the previous lemma, one only has to remember that the
operator norm for real symmetric matrices is the greatest eigenvalue, and use
the fundamental theorem of analysis.

###### Proof.

Let $x,y\in\mathds{1}^{\perp}$. We write

$\displaystyle\left\lVert\sigma(x)-\sigma(y)\right\rVert=$
$\displaystyle\left\lVert\int_{0}^{1}\nabla\sigma(u(x-y)+y)(x-y)\mathop{}\\!\mathrm{d}u\right\rVert$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\left\lVert\nabla\sigma(u(x-y)+y)\right\rVert_{\mathrm{op}}\left\lVert
x-y\right\rVert\mathop{}\\!\mathrm{d}u.$

One can then use Theorem H.9 and Lemma H.5, and we have for all $u\in[0,1]$,

$\displaystyle\left\lVert\nabla\sigma(u(x-y)+y)\right\rVert_{\mathrm{op}}$
$\displaystyle=\lambda_{\max}(u(x-y)+y)$ $\displaystyle\leq
D\sigma_{(D)}(u(x-y)+y)^{2}$ $\displaystyle\leq
D\left(\frac{1}{1+(D-1)\operatorname{e}^{-\sqrt{\frac{D}{D-1}}\left\lVert
u(x-y)+y\right\rVert}}\right)^{2}$
$\displaystyle\leq\frac{D\operatorname{e}^{2\sqrt{\frac{D}{D-1}}\left\lVert
u(x-y)+y\right\rVert}}{(D-1)^{2}}$
$\displaystyle\leq\frac{D}{(D-1)^{2}}\operatorname{e}^{2\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert y\right\rVert)}\,.$

Putting everything together, we have

$\left\lVert\sigma(x)-\sigma(y)\right\rVert\leq\frac{D}{(D-1)^{2}}\operatorname{e}^{2\sqrt{\frac{D}{D-1}}\left\lVert
x\right\rVert\vee\left\lVert y\right\rVert}\left\lVert x-y\right\rVert\,,$

which is the desired result. ∎

######  Remark H.7 (Lipschitz continuity of the softmax).

Note that usually, the Lipschitz continuity of the softmax is considered, but
with respect to the Frobenius norm. One can obtain a crude bound starting from
the squared Frobenius norm of the Jacobian, namely

$\sum_{i}\sigma_{i}^{2}(1-\sigma_{i})^{2}+\sum_{i\neq
j}\sigma_{i}^{2}\sigma_{j}^{2}\,.$ (58)

Since the Frobenius norm is always greater than the operator norm, this
implies the result for a (global) Lispchitz constant equal to $1$. A finer
study of Eq. (58) yields a better Lipschitz constant for $\sigma$. This is
what Alghamdi et al. (2022) do, proving $1/2$-Lipschitz continuity for the
softmax function (Proposition 1 in Appendix A.4).

In view of the specific form of the gradient of the softmax, this implies that
we have (almost) the same local-Lipschitz constant for the gradient of the
softmax.

######  Corollary H.8 (local-Lispchitz continuity of the softmax Jacobian).

For all $x,y\in\mathds{1}^{\perp}$,

$\left\lVert\nabla\sigma(x)-\nabla\sigma(y)\right\rVert_{\mathrm{op}}\leq\frac{2D^{2}}{(D-1)^{3}}\operatorname{e}^{3\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert y\right\rVert)}\left\lVert x-y\right\rVert\,.$

The proof is a direct consequence of the particular form of the Jacobian (see
Lemma H.1) and of the fact that

$\left\lvert\sigma_{i}(x)-\sigma_{i}(y)\right\rvert\leq\left\lVert\sigma(x)-\sigma(y)\right\rVert\,.$

###### Proof.

Let $x,y\in\mathds{1}^{\perp}$. We have

$\left\lVert\nabla\sigma(x)-\nabla\sigma(y)\right\rVert_{\mathrm{op}}=\sup_{\begin{subarray}{c}v\in\mathbb{R}^{D}\\\
\left\lVert
v\right\rVert=1\end{subarray}}v^{\top}\left(\nabla\sigma(x)-\nabla\sigma(y)\right)v\,.$

Furthermore, using the same argument as in the proof of Lemma H.5, one can
only consider $v\in\mathds{1}^{\perp}$ with $\left\lVert v\right\rVert=1$.
Applying Eq. (57) to $x$ and $y$ and forming the difference, we obtain

$\displaystyle v^{\top}\left(\nabla\sigma(x)-\nabla\sigma(y)\right)v=$
$\displaystyle\sum_{i<k}\Big{(}\sigma_{i}(x)\sigma_{k}(x)-\sigma_{i}(y)\sigma_{k}(y)\Big{)}(v_{i}-v_{k})^{2}$
$\displaystyle=$
$\displaystyle\sum_{i<k}\Big{(}\sigma_{i}(x)-\sigma_{i}(y)\Big{)}\sigma_{k}(x)(v_{i}-v_{k})^{2}+\sum_{i<k}\sigma_{i}(y)\Big{(}\sigma_{k}(x)-\sigma_{k}(y)\Big{)}(v_{i}-v_{k})^{2}$

Each of these terms can be bounded, using successively the local Lipschitz
continuity of the softmax (Lemma H.6) and the definition of $\sigma_{(D)}$.
The last display is upper bounded by

$\displaystyle\left(\frac{D}{(D-1)^{2}}\operatorname{e}^{2\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert
y\right\rVert)}\sigma_{(D)}(x)+\frac{D}{(D-1)^{2}}\operatorname{e}^{2\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert
y\right\rVert)}\sigma_{(D)}(y)\right)\sum_{i<k}(v_{i}-v_{k})^{2}\left\lVert
x-y\right\rVert\,,$

which, in turn, is smaller than

$(\sigma_{(D)}(x)+\sigma_{(D)}(y))\frac{D}{(D-1)^{2}}\operatorname{e}^{2\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert
y\right\rVert)}\sum_{i<k}(v_{i}-v_{k})^{2}\left\lVert x-y\right\rVert\,.$

Using the bound on $\sigma_{(D)}$ given by Theorem H.9, we have

$\displaystyle
v^{\top}\left(\nabla\sigma(x)-\nabla\sigma(y)\right)v\leq\frac{2D}{(D-1)^{3}}\operatorname{e}^{3\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert y\right\rVert)}\left\lVert
x-y\right\rVert\sum_{i<k}(v_{i}-v_{k})^{2}.$

Using again the same argument as in the proof of Lemma H.6, we have
$\sum_{i<k}(v_{i}-v_{k})^{2}=D$, and finally for $v\in\mathds{1}^{\perp}$ with
$\left\lVert v\right\rVert=1$, we have

$v^{\top}(\nabla\sigma(x)-\nabla\sigma(y))v\leq\frac{2D^{2}}{(D-1)^{3}}\operatorname{e}^{2\sqrt{\frac{D}{D-1}}(\left\lVert
x\right\rVert\vee\left\lVert y\right\rVert)}\left\lVert x-y\right\rVert\,,$

which gives the wanted result by taking the supremum on $v$. ∎

###  H.2 Minimization of the softmax function

In this section, we study the extremal values of the softmax function. The
reason of this study is the close connection of these extremal values with the
spectrum of the softmax and log-softmax function. Intuitively, the trivial
bound $\sigma_{i}(x)\leq 1$ can be greatly strengthened when the norm of $x$
is constrained: $\sigma_{i}(x)=1$ is achieved only when $x_{i}\to+\infty$,
which can not be if $x$ lives in a ball of radius $\rho$.

######  Theorem H.9 (Bounding the softmax function).

Let $\rho>0$ and $D\geq 2$. We have

$\min_{i\in[D]}\inf_{\begin{subarray}{c}\left\lVert x\right\rVert\leq\rho\\\
\sum_{j}x_{j}=0\end{subarray}}\sigma_{i}(x)=\frac{1}{1+(D-1)\operatorname{e}^{\sqrt{\frac{D}{D-1}}\rho}}\,.$

and

$\max_{i\in[D]}\sup_{\begin{subarray}{c}\left\lVert x\right\rVert\leq\rho\\\
\sum_{j}x_{j}=0\end{subarray}}\sigma_{i}(x)=\frac{1}{1+(D-1)\operatorname{e}^{-\sqrt{\frac{D}{D-1}}\rho}}\,.$

######  Remark H.10 (Bounding the softmax).

The softmax function is ubiquitous in machine learning, and many bounds can be
found in the literature (Wei et al., 2023). Generally, these bounds are
pointwise, and not applicable in our case since we need a global bound on the
ball of radius $\rho$ (with the additional constraint $\sum_{j}x_{j}=0$ coming
from our algebraic assumption).

###### Proof.

Step 1: the infimum is achieved and invariant by permutation. For any
$x\in\mathbb{R}^{D}$ such that $\left\lVert x\right\rVert\leq\rho$,
$\sigma_{i}(x)\in(0,1)$ for all $i\in[D]$. Furthermore,

$\nabla\sigma_{i}(x)=\sigma_{i}(x)\mathds{1}_{i}-\sigma_{i}(x)\sigma(x)\,,$

where we remind that $(\mathds{1}_{1},\ldots,\mathds{1}_{D})$ is the canonical
basis of $\mathbb{R}^{D}$. Hence $\nabla\sigma_{i}(x)\neq 0$ and the supremum
is achieved on the sphere. Note that
$B^{0}(\rho)\vcentcolon=\left\\{x\in\mathbb{R}^{D}:\left\lVert
x\right\rVert=\rho,\sum_{j}x_{j}=0\right\\}$ is a compact set, and the infimum
is a minimum. Consider $i_{0}\in[D]$ and $y\in B^{0}(\rho)$ a joint minimizer
such that

$\sigma_{i_{0}}(y)=\min_{i\in[D]}\min_{x\in B^{0}(\rho)}\sigma_{i}(x)\,.$ (59)

Remark that Eq. (59) is invariant by permutation, i.e., for any permutation
$\tau:[D]\to[D]$, we have

$\sigma_{\tau(i_{0})}(\tau\cdot y)=\sigma_{i_{0}}(y)=\min_{i\in[D]}\min_{x\in
B^{0}(\rho)}\sigma_{i}(x)\,,$

where $\tau\cdot y=(y_{\tau(i)})_{i\in\\{1,\ldots,D\\}}$. Hence, one can
suppose without loss of generality that $i_{0}=1$.

Step 2: the coordinates of a minimizer are equal under $z\mapsto
z\operatorname{e}^{-z}$ except at $i_{0}$. In this setting, since we have for
all $i\in\\{2,\ldots,D\\}$, $\sigma_{1}(y)\leq\sigma_{i}(y)$ this implies that
$y_{1}\leq y_{i}$. Using the fact that $\sum_{j}y_{j}=0$, when summing the
previous inequality for all $i\in[D]$, one gets $y_{1}\leq 0$. Note that in
fact $y_{1}<0$. Indeed, if $y_{1}=0$, we have $y_{i}=0$ for all $i\in[D]$ and
$\left\lVert y\right\rVert=0\neq\rho$.

We are in the setting of a minimization problem under constrains, namely $y$
solves

$\text{minimize }\sigma(x)\qquad\text{subject to }\quad\left\lVert
x\right\rVert^{2}=\rho^{2},\quad\langle x,\mathds{1}\rangle=0\,.$

Using the Lagrange-Multiplier Theorem, there exist $\alpha,\beta\in\mathbb{R}$
such that for the aforementioned solution $y$ we have

$\nabla\sigma(y)+\alpha\nabla\left(\left\lVert\cdot\right\rVert^{2}-\rho^{2}\right)(y)+\beta\nabla\left(\langle\cdot,\mathds{1}\rangle\right)(y)=0\,,$

which translate into

$\displaystyle\sigma_{1}(y)-\sigma_{1}(y)^{2}+2\alpha y_{1}+\beta$
$\displaystyle=0$ $\displaystyle-\sigma_{1}(y)\sigma_{i}(y)+2\alpha
y_{i}+\beta$ $\displaystyle=0$ $\displaystyle\text{for
}i\in\\{2,\ldots,D\\}\,.$

Remark that $\beta=0$ and $\alpha\neq 0$. Indeed, by summing all these
previous equality, and using that $\sum y_{i}=0$ and $\sum\sigma_{i}=1$, one
gets $D\beta=0$ and $\beta=0$. Remind that $y_{1}<0$, and since

$\sigma_{1}(y)-\sigma_{1}(y)^{2}+2\alpha y_{1}=0\,,$

if $\alpha=0$ then $\sigma_{1}(y)(1-\sigma_{1}(y))=1$, which is not possible.
Hence $\alpha\neq 0$.

We also have that for all $i,j\in\\{2,\ldots,D\\}$,

$\sigma_{1}(y)=\frac{2\alpha y_{i}}{\sigma_{i}(y)}=\frac{2\alpha
y_{j}}{\sigma_{j}(y)}\,.$

Using that fact that $\alpha\neq 0$, this implies that
$\frac{y_{i}}{\operatorname{e}^{y_{i}}}=\frac{y_{2}}{\operatorname{e}^{y_{2}}}$
for all $i\in\\{2,\ldots,D\\}$ and that

$0=y_{1}+\sum_{i=2}^{D}y_{i}=y_{1}+\left(\sum_{i=2}^{D}y_{2}\operatorname{e}^{-y_{2}}\operatorname{e}^{y_{i}}\right)=y_{1}+\left(\sum_{i=1}^{D}\operatorname{e}^{y_{i}}-\operatorname{e}^{y_{1}}\right)y_{2}\operatorname{e}^{-y_{2}}=y_{1}+\operatorname{e}^{y_{1}}\frac{1-\sigma_{1}(y)}{\sigma_{1}(y)}y_{2}\operatorname{e}^{-y_{2}}\,.$

As a consequence, for all $i\in\\{2,\ldots,D\\}$,

$y_{i}\operatorname{e}^{-y_{i}}=y_{2}\operatorname{e}^{-y_{2}}=-y_{1}\operatorname{e}^{-y_{1}}\frac{\sigma_{1}(y)}{1-\sigma_{1}(y)}\,.$
(60)

Step 3: expression of the minimum in function of the solution of
$z\operatorname{e}^{-z}=c$. Since $y_{1}<0$, the previous equality (60)
implies that $y_{i}>0$ for $i\in\\{2,\ldots,D\\}$. For any
$0<c<\operatorname{e}^{-1}$, the equation $x\operatorname{e}^{-x}=c$ has
exactly two solutions, which we call $0<y_{-}(c)<1<y_{+}(c)$. Let us define

$n=\left\lvert\left\\{2\leq i\leq
D,y_{i}=y_{-}\left(-y_{1}\operatorname{e}^{-y_{1}}\frac{\sigma_{1}(y)}{1-\sigma_{1}(y)}\right)\right\\}\right\rvert\,$

the number of “negative” solutions. By definition of $n$, we necessarily have

$\sigma_{1}(y)=\frac{\operatorname{e}^{y_{1}}}{\operatorname{e}^{y_{1}}+n\operatorname{e}^{y_{-}}+(D-1-n)\operatorname{e}^{y_{+}}}\,.$
(61)

Recall that $\sum_{j}y_{j}=0$ and $\left\lVert y\right\rVert=\rho$, hence

$\displaystyle y_{1}+ny_{-}+(D-1-n)y_{+}$ $\displaystyle=0$ (62)
$\displaystyle y_{1}^{2}+ny_{-}^{2}+(D-1-n)y_{+}^{2}$
$\displaystyle=\rho^{2}\,.$ (63)

When $n=D-1$, one can solve the previous equations and we have
$y_{1}=\\-\rho\sqrt{\frac{D}{D-1}}$ and $y_{j}=\rho\sqrt{\frac{1}{D(D-1)}}$
for all $j\in\\{2,\cdots,D\\}$, and
$\sigma_{1}(y)=\frac{1}{1+(D-1)\operatorname{e}^{\sqrt{\frac{D}{D-1}}\rho}}$.

Since the problem here is symmetric in $y_{-}$ and $y_{+}$, one can suppose
that $1\leq n\leq D-2$. Hence rewriting Eq. (62), we obtain

$y_{+}=-\left(\frac{n}{D-1-n}y_{-}+\frac{1}{D-1-n}y_{1}\right)\,.$

Replacing the value of $y_{+}$ by the right-hand side of the previous display
in Eq. (63), we obtain

$\left(n+\frac{n^{2}}{D-1-n}\right)y_{-}^{2}+2\frac{n}{D-1-n}y_{1}y_{-}-\left(\rho^{2}-y_{1}^{2}\left(1+\frac{1}{D-1-n}\right)\right)=0\,.$

Dividing by $\left(n+\frac{n^{2}}{D-1-n}\right)$, we get

$y_{-}^{2}+\frac{2}{D-1}y_{1}y_{-}-\left(\frac{D-1-n}{n(D-1)}\rho^{2}-\frac{D-n}{n(D-1)}y_{1}^{2}\right)=0\,.$

We can see the previous display as a quadratic equation in $y_{-}$, which we
now solve. There exists $\varepsilon\in\\{-1,1\\}$ such that

$y_{-}=\frac{-y_{1}-\varepsilon\sqrt{\frac{D-1-n}{n}}\Delta(y_{1})}{D-1},$

where

$\Delta(y_{1})=\sqrt{(D-1)\rho^{2}-Dy_{1}^{2}}\,.$

Note that in this setting one necessarily have

$-\sqrt{\frac{D}{D-1}}\rho\leq y_{1}\leq 0\,,$ (64)

since we have already seen that the minimization problem under constrains has
a solution, $y_{-}$ and $y_{+}$ exist and $1\leq n\leq D-2$. When the previous
condition is not satisfied, necessarily in the case $n=D-1$ or $n=0$ holds
which has already been treated.

Finally, when using the fact that $y_{+}=-\frac{1}{D-1-n}(y_{1}+ny_{-})$,

$y_{+}=\frac{-y_{1}+\varepsilon\sqrt{\frac{n}{D-1-n}}\Delta(y_{1})}{D-1}\,.$

And since $y_{+}>y_{-}$, we have

$\varepsilon\sqrt{\frac{n}{D-1-n}}>-\varepsilon\sqrt{\frac{D-1-n}{n}}\,,$

and we conclude that $\varepsilon=1$, i.e.,

$\displaystyle y_{-}$
$\displaystyle=\frac{-y_{1}-\sqrt{\frac{D-1-n}{n}}\Delta(y_{1})}{D-1}$ (65)
$\displaystyle y_{+}$
$\displaystyle=\frac{-y_{1}+\sqrt{\frac{n}{D-1-n}}\Delta(y_{1})}{D-1}\,.$ (66)

Taking a step back, we have managed to express all coordinates as an explicit
function of $y_{1}$.

Step 4: closed-form expression of the minimum. Replacing $y_{-}$ and $y_{+}$
in Eq. (61) by the expression obtained in Eqs. (65) and (66), we have to
minimize the function of $y_{1}$ defined

$\displaystyle g(y_{1})=$
$\displaystyle\frac{\operatorname{e}^{y_{1}}}{\operatorname{e}^{y_{1}}{+n\operatorname{e}^{\frac{-y_{1}-\sqrt{\frac{D-1-n}{n}}\Delta(y_{1})}{D-1}}}+(D-1-n){\operatorname{e}^{\frac{-y_{1}+\sqrt{\frac{n}{D-1-n}}\Delta(y_{1})}{D-1}}}}$
$\displaystyle=$
$\displaystyle\left(1+\operatorname{e}^{-\frac{D}{D-1}y_{1}}\left(n\operatorname{e}^{-\frac{\sqrt{\frac{D-1-n}{n}}\Delta(y_{1})}{D-1}}+(D-1-n)\operatorname{e}^{\frac{\sqrt{\frac{n}{D-1-n}}\Delta(y_{1})}{D-1}}\right)\right)^{-1}$
$\displaystyle=$
$\displaystyle\Bigg{(}1+\operatorname{e}^{-\frac{D}{D-1}y_{1}}\sqrt{n(D-1-n)}$
$\displaystyle\hskip
56.9055pt\times\left(\sqrt{\frac{n}{D-1-n}}\operatorname{e}^{-\frac{\sqrt{\frac{D-1-n}{n}}\Delta(y_{1})}{D-1}}+\sqrt{\frac{D-1-n}{n}}\operatorname{e}^{\frac{\sqrt{\frac{n}{D-1-n}}\Delta(y_{1})}{D-1}}\right)\Bigg{)}^{-1}$

Note that for $y_{1}$ satisfying Eq. (64) $y_{1}$ is non-positive. It is
elementary to show that $y\mapsto\Delta(y)$ is an increasing function on
$\mathbb{R}_{-}$. Moreover, for all $a>0$, $h:x\mapsto
a\operatorname{e}^{-\frac{x}{a}}+\frac{1}{a}\operatorname{e}^{ax}$ is an
increasing function on $\mathbb{R}_{+}$. Thus $y\mapsto h(\Delta(y)/(D-1))$ is
a decreasing mapping on $\mathbb{R}_{-}$. Hence, by taking
$a=\sqrt{\frac{D-1-n}{n}}$, we have

$h\left(\frac{\Delta(y_{1})}{D-1}\right)\leq
h(0)=\sqrt{\frac{D-1-n}{n}}+\sqrt{{\frac{n}{D-1-n}}}\,,$

and

$\sqrt{(D-1-n)n}h\left(\frac{\Delta(y)}{D-1}\right)\leq\sqrt{(D-1-n)n}\left(\sqrt{\frac{D-1-n}{n}}+\sqrt{{\frac{n}{D-1-n}}}\right)=D-1\,.$