# An Experimental Investigation of
Part-Of-Speech Taggers for Vietnamese

Tuan-Phong Nguyen, Quoc-Tuan Truong, Xuan-Nam Nguyen, Anh-Cuong Le This work
was done in 2016, when Tuan-Phong Nguyen, Quoc-Tuan Truong and Xuan-Nam Nguyen
were students at the University of Engineering and Technology, VNU Hanoi,
Vietnam. The corresponding author, Anh-Cuong Le, is with the Faculty of
Information Technology, Ton Duc Thang University, Ho Chi Minh city, Vietnam.
E-mail<EMAIL_ADDRESS>
###### Abstract

Part-of-speech (POS) tagging plays an important role in Natural Language
Processing (NLP). Its applications can be found in many NLP tasks such as
named entity recognition, syntactic parsing, dependency parsing and text
chunking. In the investigation conducted in this paper, we utilize the
technologies of two widely-used toolkits, ClearNLP and Stanford POS Tagger, as
well as develop two new POS taggers for Vietnamese, then compare them to three
well-known Vietnamese taggers, namely JVnTagger, vnTagger and RDRPOSTagger. We
make a systematic comparison to find out the tagger having the best
performance. We also design a new feature set to measure the performance of
the statistical taggers. Our new taggers built from Stanford Tagger and
ClearNLP with the new feature set can outperform all other current Vietnamese
taggers in term of tagging accuracy. Moreover, we also analyze the affection
of some features to the performance of statistical taggers. Lastly, the
experimental results also reveal that the transformation-based tagger,
RDRPOSTagger, can run significantly faster than any other statistical tagger.

###### Index Terms:

Part-of-speech tagger, Vietnamese language

##  1 Introduction

In Natural Language Processing, part-of-speech (POS) tagging is the process to
assign a part-of-speech to each word in a text according to its definition and
context. POS tagging is a core task of NLP. The part-of-speech information can
be used in many other NLP tasks, including named entity recognition, syntactic
parsing, dependency parsing and text chunking. In common languages such as
English and French, studies in POS tagging are very successful. Recent studies
for these languages [1, 2, 3, 4, 5] can yield state-of-the-art results at
approximately 97-98% for overall accuracy. However, for less common languages
such as Vietnamese, current results are not as good as for Western languages.
Recent studies on Vietnamese POS tagging such as [6, 7] can only achieves
approximately 92-93% for precision.

Several POS tagging approaches have been studied. The most common ones are
stochastic tagging, rule-based tagging and transformation-based tagging
whereas the last one is a combination of the others. All of these three
approaches treat POS tagging as a supervised problem that requires a pre-
annotated corpus as training data set. For English and other Western
languages, almost studies that provide state-of-the-art results are based on
the supervised learning. Similarly, the most widely-used taggers for
Vietnamese, JVnTagger [8], vnTagger [6] and RDRPOSTagger [7], also treat POS
tagging as a supervised learning problem. While JVnTagger and vnTagger are
stochastic-based tagger, RDRPOSTagger implements a transformation-based
approach. Although these three taggers are reported to have the highest
accuracies for Vietnamese POS tagging, they can only give the precision of
92-93%. Meanwhile, two well-known open-source toolkits, ClearNLP [2] and
Stanford POS Tagger [1], which use stochastic tagging algorithms can provide
overall accuracies of over 97% for English. It would be unfair to compare the
results for two different languages because they have distinct
characteristics. Therefore, our questions are “How well can the two
international toolkits perform POS tagging for Vietnamese?” and “Which is the
most effective approach for Vietnamese part-of-speech tagging?”. The purpose
of the investigation conducted in this paper is to answer those questions by
doing a systematic comparison of the taggers. Beside the precision of taggers,
their tagging speed is also considered because many recent NLP tasks have to
deal with very large-scale data in which speed plays a vital role.

For our experiments, we use Vietnamese Treebank corpora [9] which is the most
common corpus and has been utilized by many studies on Vietnamese POS tagging
and is one resource from a national project named “Building Basic Resources
and Tools for Vietnamese Language and Speech Processing”
(VLSP)111https://vlsp.org.vn/. Vietnamese Treebank contains about 27k POS-
tagged sentences. In spite of its popularity, there have been several errors
in this data that can draw the precision of taggers. All of those errors that
we detected are also reported in this paper. By using 10-fold cross-validation
method on the configured corpus, it is revealed that the new taggers we built
from ClearNLP and Stanford POS Tagger produce the most accurate results at
94.19% and 94.53% for precision, which also are the best Vietnamese POS
tagging results known to us. Meanwhile, the highest tagging speed belongs to
the transformation-based tagger, RDRPOSTagger, which can assign tags for over
161k words per second in average while running on a personal computer.

The remainder of this paper is organized as follows. In section 2, we briefly
introduce general knowledge about the main approaches that have been applied
in POS tagging task. We also give some information about particular
characteristics of Vietnamese language and the experimental data, Vietnamese
Treebank corpora. Section 3 represents the methods used by the POS taggers. In
section 4, we talk about the main contribution of this paper including the
error fixing process for the experimental data, the experimental results on
the taggers and the comparison of their accuracies and tagging speeds.
Finally, we conclude this paper in section 5.

##  2 Background

This section provides some background information of part-of-speech tagging
approaches that have been used so far. The related works are also covered.
Moreover, we also give some details about Vietnamese language and Vietnamese
Treebank.

###  2.1 Approaches for POS tagging

Part-of-speech tagging is commonly treated as a supervised learning problem.
Each POS tagger takes the information from its training data to determine the
tag for each word in input text. In most cases, a word might have only one
possible tag. The other case is that a word has several possible tags; or a
word has not appeared in the lexicon extracted from the training data. The
process to choose the right tag for a word in these cases is based on which
kind of used tagging algorithm. There are three main kinds of tagging
approaches within POS tagging, which are stochastic tagging, rule-based
tagging and transformation-based tagging.

Stochastic (probabilistic) tagging approach is one of the most widely-used
ones in recent studies for POS tagging. The general idea of stochastic taggers
is that they make use of training corpus to determine the probability of a
specific word having a specific tag in a given context. Common methods of
stochastic approach are Maximum Entropy (MaxEnt), Conditional Random Fields
(CRFs), Hidden Markov Models (HMMs). Many studies on English POS tagging using
stochastic approaches can gain state-of-the-art results, such as [1, 2, 4].

Rule-based tagging is actually different from stochastic tagging. Rule-based
tagging algorithm uses a set of hand-written rules to determine the tag for
each word. This leads to a fact that this set of rules must be properly
written and checked by experts on linguistic.

Meanwhile, transformation-based tagging is a combination of the features of
the two algorithms above. This algorithm applies disambiguation rules like the
rule-based tagging, but these rules are not hand-written. They are
automatically extracted from the training corpus. Taggers using this kind of
algorithm are usually referred to Brill’s one [10]. There are three main steps
in his algorithm. Firstly, the tagger initially assigns for each word in the
input text with the tag which is the most frequent for this word in the
lexicon extracted from the training corpus. After that, it traverses through a
list of transformation rules to choose the rule that enhances tagging accuracy
the most. Then this transformation rule will be applied to every word. The
loop through three stages is continued until it optimizes the tagging
accuracy.

For all of those approaches listed above, a pre-annotated corpus is
prerequisite. On the other hand, there is also unsupervised POS tagging
algorithm [11, 12] that does not require any pre-tagged corpus.

For Vietnamese POS tagging, [13] compares three tagging methods which are
CRFs-based, MEMs-based and SVM-based tagging. However, the comparison does not
contain terms of unknown words accuracy and tagging speed. Moreover, all of
those methods are based on stochastic tagging. It is necessary to
systematically compare all of those characteristics of the taggers in a same
evaluation scheme and also the accuracies of different kinds of approach to
find out the most accurate one for Vietnamese POS tagging.

###  2.2 Vietnamese language

In this section, we talk about some specific characteristics of Vietnamese
language compared to the Western languages and also some information of
Vietnamese Treebank, the corpus which we use for experiments.

####  2.2.1 The language

Vietnamese is an Austroasiatic language and the national and official language
of Vietnam. It is the native language of Kinh people. Vietnamese is spoken
throughout the world because of Vietnamese emigration. The Vietnamese alphabet
in use today is a Latin alphabet with additional diacritics and letters.

In Vietnamese, there is no word delimiter. Spaces are used to separate the
syllables rather than the words. For example, in the sentence “[học sinh]
[học] [sinh học]” (“students study biology”), there are two times that “học
sinh” appears, the first space between “học sinh” is the separation of two
syllables of the word “học sinh” (“students”), however, the second one is not.

Vietnamese is an inflectionless language whose word forms never change as in
occidental languages. There are many cases in that a word has more than one
part-of-speech tags in different contexts. For instance, in the sentence “[học
sinh] [ngồi] [quanh] [bàn]1 [để] [bàn]2 [về] [bài] [toán]” (“students sit
around the [table]1 in order to [discuss]2 about a Math exercise”), the first
word bàn is a noun but the second one is a verb. Part-of-speech for Vietnamese
words is usually ambiguous so that they must be classified based on their
syntactic functions and meaning in their current context.

####  2.2.2 Vietnamese Treebank

Vietnamese Treebank [9] is the largest annotated corpora for Vietnamese. It is
one of the resources from the KC01/06-10 project named “Building Basic
Resources and Tools for Vietnamese Language and Speech Processing” which
belongs to the National Key Science and Technology Tasks for the 5-Year Period
of 2006-2010. The first version of the treebank consists of 10,165 sentences
which are manually segmented and POS-tagged. This number in the current
version of the treebank is increased to 27,871 annotated
sentences222https://vlsp.org.vn/resources-vlsp2013. The raw texts of the
treebank are collected from the social and political sections of the Youth
online daily newspaper. The minimal and maximal sentence lengths are 1 and 165
words respectively.

Table I: Vietnamese tagset. No. | Category | Description
---|---|---
1 | Np | Proper noun
2 | Nc | Classifier
3 | Nu | Unit noun
4 | N | Common noun
5 | V | Verb
6 | A | Adjective
7 | P | Pronoun
8 | R | Adverb
9 | L | Determiner
10 | M | Numeral
11 | E | Preposition
12 | C | Subordinating conjunction
13 | Cc | Coordinating conjunction
14 | I | Interjection
15 | T | Auxiliary, modal words
16 | Y | Abbreviation
17 | Z | Bound morpheme
18 | X | Unknown

The tagset designed for Vietnamese Treebank is presented in Table I. Beside
these eighteen basic tags, there are also compound tags such as Ny
(abbreviated noun), Nb (foreign noun) or Vb (foreign verb).

##  3 Method analysis

This section provides information about the general methods used by current
Vietnamese POS taggers and two taggers for common languages. While
RDRPOSTagger uses a transformation-based learning approach, all of four other
taggers, ClearNLP, Stanford POS Tagger, vnTagger and JVnTagger, are
stochastic-based taggers using either MaxEnt, CRFs models or support vector
classification.

###  3.1 Existing Vietnamese POS taggers

####  3.1.1 JVnTagger

JVnTagger is a stochastic-based POS tagger for Vietnamese and is implemented
in Java. This tagger is based on CRFs and MaxEnt models. JVnTagger is a branch
product of VLSP project and also a module of JVnTextPro, a widely used toolkit
for Vietnamese language processing developed by Nguyen and Phan [8]. This
tagger is also called by the other name, VietTagger.

Table II: Default feature set used in JVnTagger. $w_{i}$: the word at position $i$ in the 5-word window. $t_{i}$: the POS tag of $w_{i}$. Model | Type | Template
---|---|---
MaxEnt and CRFs | Lexicon |  | $w_{\\{-2,-1,0,1,2\\}}$
---
$(w_{-1},w_{0})$, $(w_{0},w_{1})$
Binary |  |  $w_{i}$ contains all uppercase characters or not $(i=-1,0)$,
---
$w_{i}$ has the initial character uppercase or not $(i=-1,0)$,
$w_{i}$ is a number or not $(i=-1,0,1)$,
$w_{i}$ contains numbers or not $(i=-1,0,1)$,
$w_{i}$ contains hyphens or not $(i=-1,0)$,
$w_{i}$ contains commas or not $(i=-1,0)$,
$w_{i}$ is a punctuation mark or not $(i=-1,0,1)$
| Vietnamese
---
specialized features
|  possible tags of $w_{i}$ in dictionary $(i=-1,0,1)$,
---
$w_{0}$ is full repetitive or not,
$w_{0}$ is partial repetitive or not,
the first syllable of $w_{0}$,
the last syllable of $w_{0}$
CRFs | Edge feature | $(t_{-1},t_{0})$

There are two kinds of feature used in JVnTagger, which are context features
for both CRFs and MaxEnt models and an edge feature for CRFs model as listed
in Table II. Both models of JVnTagger use 1-gram and 2-gram features for
predicting tags of all words. For unknown words, this toolkit uses some rules
to detect whether each word is in a specific form or not to determine its
part-of-speech tag.

Additionally, there is a particular feature extracted by looking up the
current word in a tags-of-word dictionary which contains possible tags of over
31k Vietnamese words extracted before. This feature applies for both the
current word, the previous and the next words. Besides, in Vietnamese,
repetitive word is a special feature, therefore, JVnTagger adds full-
repetitive and partial-repetitive word features to enhance the accuracy of
predicting tag A (adjective) as well. Word prefix and suffix are also vital
features in POS tagging task of many other languages.

The CRFs model of JVnTagger had been trained by FlexCrfs toolkit [14]. Due to
the nature of CRFs model, there is an edge feature extracted directly by
FlexCrfs as described in Table II.

The F-measure results of JVnTagger are reported at 90.40% for CRFs model and
91.03% for MaxEnt model using 5-fold cross-validation evaluation on Vietnamese
Treebank corpus of over 10k annotated sentences.

####  3.1.2 vnTagger

vnTagger [6] is also a stochastic-based POS tagger for Vietnamese. The main
method of this tagger is Maximum Entropy. vnTagger is written in Java and its
architecture is mainly based on the basis of Stanford POS Tagger [1].

Table III: Default feature set used in vnTagger. Usage | Template
---|---
All words |  | $w_{\\{-1,0,1\\}}$
---
$t_{-1},(t_{-2},t_{-1})$
Unknown words |  |  $w_{0}$ contains a number or not,
---
$w_{0}$ contains an uppercase character or not,
$w_{0}$ contains all uppercase characters or not,
$w_{0}$ contains a hyphen or not,
the first syllable of $w_{0}$,
the last syllable of $w_{0}$,
conjunction of the two first syllables of $w_{0}$,
conjunction of the two last syllables of $w_{0}$,
number of syllables in $w_{0}$

There are two kinds of feature used in the MaxEnt model of this tagger, which
are presented in Table III. The first one is the set of features used for all
words. This tagger uses a one-pass, left-to-right tagging algorithm, which
only make use of information from history. It only captures 1-gram features
for words in a window of size 3, and the information of the tags in the left
side of the current words. The other kind of feature is used for predicting
tags of unknown words. These features mainly help to catch the word shape.

The highest accuracy is reported at 93.40% in overall and 80.69% for unknown
words when using 10-fold cross-validation on Vietnamese Treebank corpus of
10,165 annotated sentences.

####  3.1.3 RDRPOSTagger

RDRPOSTagger [7] is a Ripple Down Rules-based Part-Of-Speech Tagger which is
based upon transformation-based learning, a method which is firstly introduced
by Eric Brill [10] as mentioned above. For English, it reaches accuracy scores
of up to 96.57% when training and testing on selected sections of the Penn WSJ
Treebank corpus [15]. For Vietnamese, it approaches 93.42% for overall
accuracy using 5-fold cross-validation on Vietnamese Treebank corpus of 28k
annotated sentences. This toolkit has both Java-implemented and Python-
implemented versions.

The difference between the approach of RDRPOSTagger to Brill’s is that
RDRPOSTagger exploits a failure-driven approach to automatically restructure
transformation rules in the form of a Single Classification Ripple Down Rules
(SCRDR) tree. It accepts interactions between rules, but a rule only changes
the outputs of some previous rules in a controlled context. All rules are
structured in a SCRDR tree which allows a new exception rule to be added when
the tree returns an incorrect classification.

The learning process of the tagger is described in Figure 1. The initial
tagger developed in this toolkit is based on the lexicon which is generated
from the golden-standard corpus. To deal with unknown words, the initial
tagger utilizes several regular expressions or heuristics whereas the most
frequent tag in the training corpus is exploited to label unknown words. The
initialized corpus is returned by performing the initial tagger on the raw
corpus. By comparing the initialized corpus with the golden one, an object-
driven dictionary of pairs (Object, correctTag) is produced in which Object
captures the 5-word window context covering the current word and its tag from
the initialized corpus, and the correctTag is the corresponding tag of the
current word in the golden corpus.

Figure 1: Diagram demonstrating the learning process of the RDRPOSTagger
learner.

There are 27 rule templates applied for Rule selector to select the most
suitable rules to build the SCRDR tree. The templates are presented in Table
IV. The SCRDR tree of rules is initialized by building the default rule and
all exception rules of the default one in the form of if currentTag = “TAG”
then tag = “TAG” at the layer-1 exception structure. The learner then
generates new exception rules to every node of the tree due to three
constraints described in [16].

Table IV: Short descriptions of rule templates used for Rule selector of RDRPOSTagger. No. | Type | Template
---|---|---
1 | Word | $w_{\\{-2,-1,0,1,2\\}}$
2 | Word bigrams |  | $(w_{-2},w_{0}),(w_{-1},w_{0}),$
---
$(w_{-1},w_{1}),(w_{0},w_{1}),(w_{0},w_{2})$
3 | Word trigrams |  | $(w_{-2},w_{-1},w_{0}),(w_{-1},w_{0},w_{1}),$
---
$(w_{0},w_{1},w_{2})$
4 | POS tags | $t_{\\{-2,-1,0,1,2\\}}$
5 | POS bigrams | $(t_{-2},t_{-1}),(t_{-1},t_{1}),(t_{1},t_{2})$
6 | Combined |  | $(t_{-1},w_{0}),(w_{0},t_{1}),(t_{-1},w_{0},t_{1}),$
---
$(t_{-2},t_{-1},w_{0}),(w_{0},t_{1},t_{2})$
7 | Suffix |  suffixes of length 1 to 4 of $w_{0}$

The tagging process of this tagger firstly assigns tags for unlabeled text by
using the initial tagger. Next, for each initially tagged word, the
corresponding Object will be created. Finally, each word will be tagged by
passing its object through the learned SCRDR tree. If the default node is the
last fired node satisfying the object, the final tag returned is the tag
produced by the initial tagger.

###  3.2 POS taggers for common languages

####  3.2.1 Stanford POS Tagger

Stanford POS Tagger [1] is also a Java-implemented tagger based on stochastic
approach. This tagger is the implementation of a log-linear part-of-speech
tagging algorithm described in [1] and is developed at Stanford University. At
the time of this work (i.e., 2016), Stanford POS Tagger has pre-trained models
for English, Chinese, Arabic, French and Germany. It can be re-trained in any
other language.

The approach described in [1] is based on two main factors, a cyclic
dependency network and the MaxEnt model. General idea of the cyclic (or
bidirectional) dependency network is to overcome weaknesses of the
unidirectional case. In the unidirectional case, only one direction of the
tagging sequence is considered at each local point. For instance, in a left-
to-right first-order HMM, the current tag $t_{0}$ is predicted based on only
the previous tag $t_{-1}$ and the current word $w_{0}$. However, it is clear
that the identity of a tag is also correlated with tag and word identities in
both left and right sides. The approach of Stanford POS Tagger follows this
idea combined with Maximum Entropy models to provide efficient bidirectional
inference.

(a) Left-to-Right Inference

(b) Right-to-Left Inference

(c) Bidirectional Dependency Network

Figure 2: Dependency networks.

As reported in [1], with many rich bidirectional-context features and a few
additional handcrafted features for unknown words, Stanford POS Tagger can
reach the overall accuracy of 97.24% and unknown word accuracy of 89.04%.

####  3.2.2 ClearNLP

ClearNLP [2] is a toolkit written in Java that contains low-level NPL
components (e.g., dependency parsing, named entity recognition, sentiment
analysis, part-of-speech tagging), developed by NLP Research Group at Emory
University. In our experiments, we use the last released version of ClearNLP –
version 3.2.0.

The POS tagging component in ClearNLP is a implementation of the method
described in [2]. General idea of this method is to have two models in the
tagger and find the most suitable model to assign tags for input sentence
based on its domain. Firstly, two separated models, one is optimized for a
general domain and the other is optimized for a domain specific to the
training data, are trained. They suppose that the domain-specific and
generalized models perform better to sentences similar and not similar to the
training data, respectively. Hence, during decoding, they dynamically select
one of the models by measuring similarities between input sentences and the
training data. Some first versions of ClearNLP use dynamic model selection but
later versions only use the generalized model to perform the tagging process.

ClearNLP utilizes Liblinear L2-regularization, L1-loss support vector
classification [17] for training models and tagging process. It is reported in
[2] that this method can gain the overall accuracy of 97.46% for English POS
tagging.

##  4 Experiments

In this section, the process to fix errors in POS-tagged sentences of
Vietnamese Treebank corpus is firstly represented. Next, the experimental
results of the taggers will be presented.

###  4.1 Data processing

Vietnamese Treebank corpus was built manually. Some serious errors in this
data were found while doing experiments. All of those errors are reported in
Table V.

Table V: Error analysis on Vietnamese Treebank. Kind of error | Modification | Occurrence
---|---|---
VN/Np | VN/Ny | 238
¡number¿/M tuổi/Nu | ¡number¿/M tuổi/N | 184
| Word segmentation error (two underscores
---
between a pair of syllables)
Remove one underscore | 105
| Tokenization error (two punctuation marks
---
inside a token)
Separate those tokens | 99
ð (Icelandic character) | đ (Vietnamese character) | 73
More than two tags in one word | Remove the wrong tag | 50

The #1 row in Table V presents error in which the word “VN” (the abbreviation
of “Việt Nam”) is tagged as Np (proper name). The right tag for the word “VN”
in this case is actually Ny (abbreviated noun).

The second most frequent error is shown in the #2 row in Table V. The context
is that a number (tagged with M) is followed by the word “tuổi” (“years old”)
and the POS tags of “tuổi” are not uniform in the whole corpus. There are 184
times in which the tagged sequence is “¡number¿/M tuổi/Nu” (Nu is unit noun
tag which can be used for “kilograms”, “meters”, etc.) and 246 times that the
tagged sequence is “¡number¿/M tuổi/N” (N is noun). Since the tag N is more
suitable for the word “tuổi” in this situation, all 184 occurrences of
“¡number¿/M tuổi/Nu” are replaced by the other one.

There are 105 times of word segmentation error in which the separator of
syllables is duplicated. Moreover, there are also 99 times of tokenization
error, and 73 times that the character “đ” is typed wrongly. The last kind of
error is that a single word has two POS tags, which happens 50 times.

Obviously, those errors do affect performance of POS taggers significantly.
All of them were discovered during the experiments and were fixed manually to
improve the accuracy of the taggers.

After modifying the corpus, we divide it into ten equal partitions which will
be used for 10-fold cross-validation. In each fold, nine of ten partitions are
used as the training data, the other one is used as the test set. There are
about 1.5% – 2% of words in the test set which are unknown in every fold, as
shown in Table VI.

Table VI: The experimental datasets. | Fold
---
| Total number
---
of words
| Number of
---
unknown words
1 | 63277 | 1164
2 | 63855 | 1203
3 | 63482 | 1247
4 | 62228 | 1168
5 | 59854 | 1056
6 | 63652 | 1216
7 | 63759 | 1146
8 | 63071 | 1224
9 | 65121 | 1242
10 | 63552 | 1288

###  4.2 Evaluation

In our experiments, we firstly evaluate the current Vietnamese POS taggers
which are vnTagger, JVnTagger and RDRPOSTagger with their default settings.
Next, we design a set of features to evaluate the statistical taggers,
including two international ones, Stanford Tagger and ClearNLP, and a current
Vietnamese one, JVnTagger. There are two terms of the taggers that we measure,
which are tagging accuracy and speed. The accuracy is measured using 10-fold
cross-validation method on the datasets described above. The speed test is
processed on a personal computer with 4 Intel Core i5-3337U CPUs @ 1.80GHz and
6GB of memory. The data used for the speed test is a corpus of 10k sentences
collected from Vietnamese websites. This corpus was automatically segmented by
UETsegmenter [18] and contains about 250k words. All taggers use their single-
threaded implementation for the speed test. Moreover, the test is processed
many times to take the average speed of the taggers. We only use the Java-
implemented version of RDRPOSTagger in the experiments because it is claimed
by the author that this version runs significantly faster than the other one.

Table VII: The accuracy results (%) of current Vietnamese POS taggers with their default settings. Ovr.: the overall accuracy. Unk.: the unknown words accuracy. Spd.: the tagging speed (words per second). Feature set | vnTagger | JVn – MaxEnt | RDRPOSTagger | JVn – CRFs
---|---|---|---|---
Accuracy | Spd. | Accuracy | Spd. | Accuracy | Spd. | Accuracy | Spd.
Ovr. | Unk. | Ovr. | Unk. | Ovr. | Unk. | Ovr. | Unk.
default | 93.88 | 77.70 | 13k | 93.83 | 79.60 | 50k | 93.68 | 66.07 | 161k | 93.59 | 69.51 | 47k

We present the performance of the current Vietnamese taggers in Table VII. As
we can see, the accuracy results of the taggers are pretty similar to each
other’s with their default feature sets. The most accurate ones are vnTagger
and MaxEnt model of JVnTagger. Especially, these two taggers provide very high
accuracies for unknown words. Their specialized features for this kind of word
seem to be very effective. Inside the JVnTagger toolkit, the two models
provides different results. The MaxEnt model of JVnTagger is far more accurate
than the CRFs one. Because these two models use the same feature set, we
suspect that the MaxEnt model is more efficient than the CRFs one for
Vietnamese POS tagging in term of the tagging accuracy. These two models can
provide nearly similar tagging speeds which are 50k and 47k words per second.
That may be caused by their same feature set (the CRFs model only has an extra
feature so its speed is slightly lower). vnTagger has some complicated
features such as the conjunction of two tags and uses an outdated version of
Stanford Tagger so that its tagging speed is quite low. Meanwhile, the only
tagger that does not make use of statistical approach, RDRPOSTagger, produces
an impressive tagging speed at 161k words per second. The tagging speed of a
transformation-based tagger is mainly based on the speed of its initial
tagger. RDRPOSTagger only uses a lexicon for the initial tagger so that it can
perform really fast. Nevertheless, its accuracy for unknown words is not good.
Its initial tagger just uses some rules to assign initial tags and then it
traverses through the rule tree to determine the final result for the each
word. Those rules seem to be unable to handle the unknown words well.

Table VIII: Feature set designed for experiments of four statistical taggers. Dist. Semantics: distributional semantics, $ds_{i}$ is the cluster id of the word $w_{i}$ in the Brown cluster set. Feature set | Template
---|---
Simple |  | $w_{\\{-2,-1,0,1,2\\}}$
---
$(w_{-1},w_{0}),(w_{0},w_{1}),(w_{-1},w_{1})$
$w_{0}$ has initial uppercase letter?
$w_{0}$ contains number(s)?
$w_{0}$ contains punctuation mark(s)?
$w_{0}$ contains all uppercase letters?
$w_{0}$ is first or middle or last token?
Bidirectional | $(w_{0},t_{-1}),(w_{0},t_{1})$
Affix |  |  the first syllable of $w_{0}$
---
the last syllable of $w_{0}$
Dist. Semantics | $ds_{-1},ds_{0},ds_{1}$

The major of the taggers in our experiments is statistical taggers. In the
next evaluation, we will create a unique scheme to evaluate these taggers
which are Stanford POS Tagger, ClearNLP and JVnTagger. Although vnTagger is
also an statistical one, we do not carry it to the second evaluation because
it is based on the basis of Stanford Tagger as mentioned.

It is worth repeating that the performance of each statistical tagger is
mainly based on its feature set. The feature set we designed for the second
evalution is presented in Table VIII. Firstly, a simple feature set will be
applied to all of the taggers. This set only contains the 1-gram, 2-gram
features for words and some simple one to catch the word shape and the
position of the word in the sentence. Next, we will continuously add more
advanced features to the feature set to discover which one makes big impact.
The three kinds of avanced feature are bidirectional-context, affix and
distributional semantic ones. Whereas, the first and the third one are new to
the current Vietnamese POS taggers. The second one is important for predicting
the tags of unknown words.

Table IX: The accuracy results (%) of the four statistical taggers. spl: the simple feature set. bi: the bidirectional-context feature set. affix: the affix features. ds: the distributional semantic features. Feature set | Stanford | ClearNLP | JVn – MaxEnt | JVn – CRFs
---|---|---|---|---
Accuracy | Spd. | Accuracy | Spd. | Accuracy | Spd. | Accuracy | Spd.
Ovr. | Unk. | Ovr. | Unk. | Ovr. | Unk. | Ovr. | Unk.
spl | 93.96 | 72.19 | 105k | 92.95 | 68.36 | 107k | 92.53 | 67.38 | 102k | 91.57 | 67.34 | 99k
spl+bi | 94.24 | 72.40 | 11k | 93.08 | 68.35 | 93k | N/A
spl+bi+affix | 94.42 | 78.03 | 10k | 93.83 | 75.89 | 90k
spl+bi+affix+ds | 94.53 | 81.00 | 8k | 94.19 | 79.01 | 64k

The performance of four statistical taggers are presented in Table IX. Because
JVnTagger does not support the bidirectional-context features so we do not
have results for it with the feature sets containing this kind of feature.
From Table IX, we can see that with the same simple feature set, these taggers
can perform with very similar speeds which are approximately 100k words per
second. However, their accuracies are different. With the same feature set,
the MaxEnt model of Stanford Tagger can significantly outperform the MaxEnt
model of JVnTagger. We suspect that it is caused by the algorithm for
optimization and some advanced techniques used in Stanford Tagger. Moreover,
with this simple feature set, Stanford Tagger also outperforms any other
Vietnamese tagger with its default settings in the first evaluation presented
above. Stanford Tagger’s techniques seem to be really efficient. Next, inside
JVnTagger, with the same feature set, the MaxEnt model still performs better
than the CRFs one, again, just like the results conducted in Table VII.

Bidirectional tagging is one of the techniques that have not been applied for
current statistical Vietnamese POS taggers. In this experiment, we add two
bidirectional-context features which are $(w_{0},t_{-1})$ and $(w_{0},t_{1})$
to the feature set. These two features capture the information of the tags
nearby the current word. The results in Table IX reveals that bidirectional-
context features help to increase the overall accuracy of Stanford Tagger
significantly. Moreover, it also draws the tagging speed of this tagger
dramatically. However, this kind of feature only makes small impact for
ClearNLP which use SVMs for machine learning process, in terms of tagging
accuracy and speed.

Bidirectional-context features do not affect the accuracy of unknown words.
Meanwhile, affix feature plays an important role to predict Vietnamese part-
of-speech tags. In the next phase of the evaluation, we add the features to
catch the first and the last syllable of the current predicting word to
discover its impact on the tagging accuracy. As revealed in Table IX, we can
conclude that affix features can help to increase the unknown words accuracy
sharply, approximately 6% for both Stanford Tagger and ClearNLP. Especially,
those features make a very big improvement in the overall accuracy of
ClearNLP. Moreover, the tagging speeds of these taggers are affected a little
bit with these added features.

The last kind of advanced feature is the distributional semantic one. This is
a new technique which has been applied to other languages successfully. To
extract this feature, we build 1000 clusters of words based on Brown
clustering algorithm [19] using a popular
implementation333https://github.com/percyliang/brown-cluster. The input corpus
consists of 2m articles collected from Vietnamese websites. The result in
Table IX shows that distributional semantic features also help to improve the
unknown words accuracy of the taggers, at approximately 3% for both taggers.
The overall precision is also increased especially in ClearNLP. The tagging
speeds of the tagger are decreased about 20% to 30% after adding this kind of
feature.

Overall, Stanford POS Tagger is the one that has the best performance with
every feature set. ClearNLP also has a good performance. With the full set of
features (spl+bi+affix+ds), both of these two international taggers can
outperform the current Vietnamese ones with their default settings in term of
tagging accuracy. It leads to the fact that some of the specialized features
in current Vietnamese taggers are not really useful. The final results of
Stanford Tagger and ClearNLP are also the most accurate ones for Vietnamese
POS tagging known to us.

##  5 Conclusion

In this paper, we present an experimental investigation of five part-of-speech
taggers for Vietnamese. In the investigation, there are four statistical
taggers, Stanford POS Tagger, ClearNLP, vnTagger and JVnTagger. The other one
is RDRPOSTagger, a transformation-based tagger. In term of tagging accuracy,
we evaluate the statistical taggers by continuously adding several kinds of
feature to them. The result reveals that bidirectional tagging algorithm,
affix features and distributional semantic features help to improve the
tagging accuracy of the statistical taggers significantly. With the full
provided feature set, both Stanford Tagger and ClearNLP can outperform the
current Vietnamese taggers. In the speed test, RDRPOSTagger produces an
impressive tagging speed. The experimental results also show that tagging
speed of any statistical tagger is mainly based on its feature set. With a
simple feature set, all of the statistical taggers in our experiments can
perform at nearly similar speeds. However, giving an complex feature set to
the taggers can draw their tagging speeds deeply.

## Acknowledgment

This work has been supported by Vietnam National University, Hanoi (VNU-H),
under Project No. QG.14.04.

## References

  * [1] K. Toutanova, D. Klein, C. D. Manning, and Y. Singer, “Feature-rich part-of-speech tagging with a cyclic dependency network,” in _Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume 1_. Association for Computational Linguistics, 2003, pp. 173–180.
  * [2] J. D. Choi and M. Palmer, “Fast and robust part-of-speech tagging using dynamic model selection,” in _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Short Papers-Volume 2_. Association for Computational Linguistics, 2012, pp. 363–367.
  * [3] A. Søgaard, “Semisupervised condensed nearest neighbor for part-of-speech tagging,” in _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers-Volume 2_. Association for Computational Linguistics, 2011, pp. 48–52.
  * [4] Z. Huang, W. Xu, and K. Yu, “Bidirectional LSTM-CRF models for sequence tagging,” _arXiv preprint arXiv:1508.01991_ , 2015.
  * [5] P. Denis and B. Sagot, “Coupling an annotated corpus and a lexicon for state-of-the-art POS tagging,” _Language resources and evaluation_ , vol. 46, no. 4, pp. 721–736, 2012.
  * [6] P. Le-Hong, A. Roussanaly, T. M. H. Nguyen, and M. Rossignol, “An empirical study of maximum entropy approach for part-of-speech tagging of Vietnamese texts,” in _Traitement Automatique des Langues Naturelles-TALN 2010_ , 2010, p. 12.
  * [7] D. Q. Nguyen, D. Q. Nguyen, D. D. Pham, and S. B. Pham, “RDRPOSTagger: A Ripple Down Rules-based Part-Of-Speech Tagger,” in _Proceedings of the Demonstrations at the 14th Conference of the European Chapter of the Association for Computational Linguistics_. Gothenburg, Sweden: Association for Computational Linguistics, April 2014, pp. 17–20.
  * [8] C.-T. Nguyen, X.-H. Phan, and T.-T. Nguyen, “JVnTextPro: A tool to process Vietnamese texts,” Tech. rep., Version 2.0, http://jvntextpro. sourceforge. net, Tech. Rep., 2010.
  * [9] P.-T. Nguyen, X.-L. Vu, T.-M.-H. Nguyen, V.-H. Nguyen, and H.-P. Le, “Building a large syntactically-annotated corpus of Vietnamese,” in _Proceedings of the Third Linguistic Annotation Workshop_. Association for Computational Linguistics, 2009, pp. 182–185.
  * [10] E. Brill, “A simple rule-based part of speech tagger,” in _Proceedings of the workshop on Speech and Natural Language_. Association for Computational Linguistics, 1992, pp. 112–116.
  * [11] R. Prins and G. Van Noord, “Unsupervised POS-Tagging Improves Parsing Accuracy and Parsing Efficiency,” in _IWPT_ , 2001.
  * [12] E. Brill, “Unsupervised learning of disambiguation rules for part of speech tagging,” in _Proceedings of the third workshop on very large corpora_ , vol. 30. Somerset, New Jersey: Association for Computational Linguistics, 1995, pp. 1–13.
  * [13] O. T. Tran, C. A. Le, T. Q. Ha, and Q. H. Le, “An experimental study on Vietnamese POS tagging,” in _International Conference on Asian Language Processing, 2009. IALP’09._ IEEE, 2009, pp. 23–27.
  * [14] X.-H. Phan and L.-M. Nguyen, “Flexcrfs: Flexible conditional random field toolkit,” http://flexcrfs.sourceforge.net/index.html, 2005.
  * [15] M. P. Marcus, M. A. Marcinkiewicz, and B. Santorini, “Building a large annotated corpus of English: The Penn Treebank,” _Computational linguistics_ , vol. 19, no. 2, pp. 313–330, 1993.
  * [16] D. Q. Nguyen, D. Q. Nguyen, D. D. Pham, and S. B. Pham, “A robust transformation-based learning approach using ripple down rules for part-of-speech tagging,” _AI Communications_ , no. Preprint, pp. 1–14, 2014\.
  * [17] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin, “LIBLINEAR: A library for large linear classification,” _The Journal of Machine Learning Research_ , vol. 9, pp. 1871–1874, 2008.
  * [18] T.-P. Nguyen and A.-C. Le, “A hybrid approach to vietnamese word segmentation,” in _2016 IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF)_. IEEE, 2016, pp. 114–119.
  * [19] P. F. Brown, P. V. deSouza, R. L. Mercer, V. J. D. Pietra, and J. C. Lai, “Class-based n-gram models of natural language,” _Comput. Linguist._ , vol. 18, no. 4, pp. 467–479, Dec. 1992.


Projection-Free Non-Smooth Convex ProgrammingKamiar Asgari, Michael J. Neely

# Projection-Free Non-Smooth Convex Programming††thanks: Submitted to the
editors 08/13/2022. This work was supported in part by one or more of: NSF
CCF-1718477, NSF SpecEES 1824418.

Kamiar Asgari University of Southern California, Los Angeles, CA (, ).
<EMAIL_ADDRESS><EMAIL_ADDRESS>Michael J. Neely22footnotemark: 2

###### Abstract

In this paper, we provide a subgradient based algorithm to solve general
constrained convex optimization without taking projections onto the domain
set. The well studied Frank-Wolfe type algorithms also avoid projections.
However, they are only designed to handle smooth objective functions. The
proposed algorithm treats both smooth and nonsmooth problems and achieves an
$O(1/\sqrt{T})$ convergence rate (which matches existing lower bounds). The
algorithm yields similar performance in expectation when the deterministic
subgradients are replaced by stochastic subgradients. Thus, the proposed
algorithm is a projection-free alternative to the Projected subgradient
Descent (PGD) and Stochastic projected subgradient Descent (SGD) algorithms.

###### keywords:

Projection-free optimization, Nonsmooth convex programming, Frank-Wolfe method

90C25

##  1 Introduction

In order to solve general convex optimization, many versions of Black-Box
first-order algorithms have been proposed. However, most of those commonly
used algorithms require a Euclidean ($L_{2}$) projection onto the domain set
at each iteration, such as the famous Projected subgradient Descent (PGD)
algorithm.111We use the more common acronym PGD for projected subgradient
descent instead of PSD. Unless there is special structure, it is not always
computationally easy to perform the projection steps. This can make PGD less
attractive for large-scale constrained optimization problems. This paper
develops an optimization algorithm that replaces projections with
(computationally easier) Linear Optimization steps.

Specifically, let $\mathcal{X}\in\mathbb{R}^{n}$ be a closed and convex set.
The problem of this paper is to minimize a general convex function
$f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ over all $x\in\mathcal{X}$. The
Euclidean projection, i.e. $L_{2}$ projection, is defined as follows. Let
$\mathcal{X}$ be a closed convex set. Define

$\pi_{\mathcal{X}}\left(y\right)\overset{def}{=}\operatorname{Argmin}_{x\in\mathcal{X}}\left\|x-y\right\|,\quad\forall
y\in\mathbb{R}^{n}$

We call $\pi_{\mathcal{X}}\left(y\right)$ the Euclidean projection of the
point $y$ onto the set $\mathcal{X}$ (as $\mathcal{X}$ is closed and convex,
the projection exists and is unique). As our algorithm is similar to PGD, let
us review PGD:

Algorithm 1 Projected subgradient Descent (PGD)

1: Require $T\in\\{1,2,\ldots\\},\beta>0,x_{0}\in\mathcal{X}$

2: for $k=0\cdots T-1$ do

3: Calculate $g_{k}\in\partial f(x_{k})$

4: $x_{k+1}=\pi_{\mathcal{X}}(x_{k}-\beta g_{k})$

5: end for

6: return $\bar{x}=\frac{1}{T+1}\sum_{k=0}^{T}x_{k}$

It can be shown that the PGD’s update rule is equivalent to solve the
following quadratic optimization problem:

$x_{k+1}=\pi_{\mathcal{X}}(x_{k}-\beta
g_{k})=\operatorname{Argmin}_{x\in\mathcal{X}}\left\\{\langle
g_{k},x\rangle+\frac{1}{2\beta}\|x-x_{k}\|^{2}\right\\}$

where $\langle x,y\rangle$ is the inner product of $x$ and $y$ in
$\mathbb{R}^{n}$.

For a general convex set, the projection step may involve a numerical
procedure that can be computationally expensive. Different algorithms to
compute a projection of a point onto a convex set have been suggested [20, 21,
12, 16]. However, for many convex sets, a linear optimization, defined by the
following equation:

(1) $\min_{x\in\mathcal{X}}\left\\{\langle g,x\rangle\right\\},\quad\text{for
a given }g\in\mathbb{R}^{n}$

can be carried out easier than a projection. Let us call sets $\mathcal{X}$
for which problems of the type Equation Eq. 1 can be solved more easily than a
projection as Appropriate sets. Our algorithm works for any domain set that is
convex. However, it shows its potential when the domain set $\mathcal{X}$ is
an Appropriate set.

Many examples of Appropriate sets are known and studied. The work [17] unifies
many Appropriate sets under the umbrella of _Atomic sets_. One famous example
is the set of matrices with bounded trace norm. The trace norm of a matrix
$A$, shown as $\|A\|_{*}$, is the sum of its singular values. For a fixed
$\tau>0$, define set $\mathcal{X}\overset{def}{=}\\{A\in\mathbb{R}^{m\times
n}:\|A\|_{*}\leq\tau$}. The projection of matrix $X\in\mathbb{R}^{m\times n}$
on the set $\mathcal{X}$ requires a Singular Value Decomposition (SVD) of $X$
which costs $O\left(mn\min\\{m,n\\}\right)$ time. Meanwhile, a linear
optimization: $\min_{X\in\mathcal{X}}\langle P,X\rangle$, requires the
calculation of the largest singular value and its respective singular vectors
of the matrix $P$. This calculation costs linear time in the number of non-
zero entries in that matrix.

###  1.1 Main Result

Similar to Frank-wolf type algorithms that are projection-free but only work
for smooth objective functions, this paper offers a projection-free algorithm
for general convex programming. This is an alternative for PGD when the
Equation Eq. 1 is easier then a projection. The algorithm is also compatible
with stochastic (noisy) subgradients, which makes it an alternative for SGD.

###  1.2 Application in network optimization

In network optimization, the constraints model channel capacity limits which
can be expressed as linear inequalities and equalities [18, 5]. The objective
function, which describes utility and fairness [4, 23], can be nonsmooth due
to piecewise linearities and/or usage of $\min[\cdot]$. For example, in multi-
access networks, the objective function can be the minimum transmission rate
dedicated to each user, and the goal is to maximize this minimum rate. These
factors, linear constraints, and nonsmooth objective function make our
algorithm suitable for this problem.

Consider the Network Utility Maximization (NUM) problem of the form:

(NUM) $\max\left\\{u(x):\langle a_{j}\,,\,x\rangle\leq b_{j}\forall
j\in\\{1,\ldots,J\\}\right\\}.$

where $u$ is a concave utility function. The feasible set in this problem is

$\mathcal{X}=\left\\{\langle a_{j}\,,\,x\rangle\leq b_{j}\forall
j\in\\{1,\ldots,J\\}\right\\}$

This set $\mathcal{X}$ is a polytope, which indeed is one of the cases where
solving a linear optimization is much easier than a projection. Indeed, the
linear optimization becomes a Linear Programming (LP) problem for which there
are a variety of efficient optimization methods [26]. It worth mentioning that
another way to write this problem uses the _exact penalty method_ [8],

(NUM2) $\min\left\\{-u(x)+\gamma\max\left\\{0,\langle a_{1}\,,\,x\rangle-
b_{1},\ldots,\langle a_{J}\,,\,x\rangle-b_{J}\right\\}\right\\}.$

This removes the inequality constraints by incorporating them into the
objective function. This removes the need to project onto a feasible set
$\mathcal{X}$. It can be proven that if there exists a Lagrange multiplier
vector for the problem Eq. NUM, then there exists a $\gamma>0$ such that the
two problems Eq. NUM and Eq. NUM2 are equivalent. The problem Eq. NUM2 can be
solved using common methods such as the subgradient descent algorithm. In
order to compare the performance we should notice that the constant $\gamma$
is typically of size $O(J)$, and the Lipschitz coefficient of the objective
function in Eq. NUM2 is proportional to $\gamma$. Thus, considering the lower
bound of nonsmooth convex optimization is proportional to the Lipschitz
coefficient of the objective function, we see that computational complexity of
the second version is typically proportional to $J$. Because our formulation
can treat nonsmooth objectives and gracefully handles projections, it can be
used to trade off the advantages of both Eq. NUM and Eq. NUM2. Specifically,
fix a nonnegative integer $J_{1}\leq J$ and define $J_{2}=J-J_{1}$. We can use
a new exact penalty function that includes only the first $J_{1}$ inequality
constraints, and a new set $\mathcal{X}_{2}$ that is defined by the remaining
$J_{2}$ constraints:

(NUM3) $\min\left\\{-u(x)+\gamma\max\left\\{0,\langle a_{1}\,,\,x\rangle-
b_{1},\ldots,\langle a_{J}\,,\,x\rangle-
b_{J_{1}}\right\\}:x\in\mathcal{X}_{2}\right\\}.$

###  1.3 History and Related Work

The original Frank-Wolfe algorithm [9] was introduced and analyzed for
polyhedral domains in $\mathbb{R}^{n}$, relying on line-search on a quadratic
upper bound on $f$. A general framework to analyze Frank-wolf type algorithms
is achieved in [17] which also provides a comprehensive overview and
comparison between many existing algorithms of that type. Using the idea of
Variance-Reduced, [14] gets better bounds for both smooth convex functions and
smooth strongly-convex functions while presenting another comparison of
different variants of Frank-Wolfe algorithms.

Using randomized smoothing, [13] proposed a variant of Frank-Wolfe for online
optimization of nonsmooth and smooth convex functions but not achieving the
optimal convergence rates. This result has been improved in [15] using the so-
called blocking technique.

In the case when the domain only consists of convex functional constrains
($\mathcal{X}=\set{x}{h_{i}(x)\leq 0,\forall i\in\\{1,\cdots,I\\}}$), [22]
develops a unique algorithm with only one projection which (with high
probability) achieves an $O(1/\sqrt{T})$ rate for general convex optimization,
and an $O(\log(T)/T)$ rate for strongly convex optimization. Using similar
assumptions (and adding an extra assumption of smoothness of constraint
functions $h_{i}$), [19] achieves a one projection algorithm with
$O(1/\sqrt{T})$ regret for general online convex optimization, and an
$O(\log(T)/T)$ regret for online strongly convex optimization. Similar
functional constraints are treated in [27] with $O(1/T)$ convergence for
general composite smooth convex and/or separable convex programs using
knowledge of a Lagrange Multiplier bound, and [28] removes the need to know
the Lagrange Multiplier bound.

In another line of work, [1] proposed a generalization of the conditional
gradient algorithm achieving rates similar to the standard stochastic gradient
algorithm using only zeroth-order information.

##  2 Preliminaries

$\mathbb{R}$ denotes the set of real numbers, and $\mathbb{R}^{n}$ is the
usual vector space of real $n$-tuples $x=(x^{(1)},\cdots,x^{(n)})$. The inner
product of $x$ and $y$ in $\mathbb{R}^{n}$ is expressed by

$\langle x,y\rangle\overset{def}{=}\sum_{i=1}^{n}x^{(i)}y^{(i)}$

In this paper the norm is standard Euclidean which is defined as:

$\|x\|\overset{def}{=}\sqrt{\sum_{i=1}^{n}\left(x^{(i)}\right)^{2}}=\sqrt{\langle
x,x\rangle}$

Consider an arbitrary function $f$ defined on the set $S$. Fix the point $x\in
S$. A vector $g$ is called a _subgradient_ of the function $f$ at the point
$x$ if

(2) $f(y)\geq f(x)+\langle g,y-x\rangle,\quad\forall y\in S$

The set of all subgradients of $f$ at $x$, $\partial f(x)$, is called the
_subdifferential_ of the function $f$ at the point $x$. Function $f$ is called
$G$-Lipschitz continuous on the set $S$ if $\forall x,y\in S$

(3) $|f(x)-f(y)|\leq G\|x-y\|$

A subset $C$ of $\mathbb{R}^{n}$ is said to be _convex_ if
$(1-\lambda)x+\lambda y\in C$ whenever $x\in C$, $y\in C$ and
$0\leq\lambda\leq 1$. A function $f$ is called _convex_ on set $C$ if $C$ is a
convex set and for all $x,y\in C$ and $\alpha\in[0,1]$ the following
inequality holds:

$f(\alpha x+(1-\alpha)y)\leq\alpha f(x)+(1-\alpha)f(y).$

###  2.1 Extension of Convex Function

An important assumption used in this paper is that $f$ is convex and
$G$-Lipschitz continuous on the whole $\mathbb{R}^{n}$. While this is a valid
assumption in many practical cases, there are cases which can violate it.

The following theorem collects important parts from a larger _McShane-Whitney
extension theorem_ of [25]. It shows that if $f$ is convex and $G$-Lipschitz
continuous on the set $\mathcal{X}$, then $f$ can be extended to a convex and
$G$-Lipschitz continuous function on the whole of $\mathbb{R}^{n}$.

######  Theorem 2.1.

Let $\mathcal{X}$ be a convex set in $\mathbb{R}^{n}$,
$f:\mathcal{X}\rightarrow\mathbb{R}$ a convex $G$-Lipschitz continuous
function defined on $\mathcal{X}$. Then the function $\tilde{f}$ defined by:

$\tilde{f}(w)\overset{def}{=}\inf_{x\in\mathcal{X}}\\{f(x)+G\|x-w\|\\}$

satisfies the following:

  1. (i)

$\tilde{f}$ is a real valued function.

  2. (ii)

$\tilde{f}$ is a $G$-Lipschitz continuous function on $\mathbb{R}^{n}$ .

  3. (iii)

For any $x\in\mathbb{R}^{n}$, any subgradient $g\in\partial\tilde{f}(x)$ is
bounded by G: $\|g\|\leq G$.

  4. (iv)

$\tilde{f}$ is a convex function on $\mathbb{R}^{n}$.

  5. (v)

$f(w)=\tilde{f}(w)$, $\forall w\in\mathcal{X}$

######  Proof 2.2.

This theorem is a special case of the _McShane-Whitney extension theorem_ and
it is fully borrowed from different parts of [25]. However, for the sake of
convenience, the proof is collected and presented at Appendix A.

###  2.2 Problem setup

We want to provide a projection-free algorithm to solve the following
optimization:

$\min_{x\in\mathcal{X}}f(x)$

We assume that the set $\mathcal{X}$ is contained in an Euclidean ball
centered at $x_{1}\in\mathcal{X}$ and of radius $R$. This has two
consequences:

(4) $\|x-y\|\leq 2R,\quad\forall x,y\in\mathcal{X}$ (5) $\|x-x_{1}\|\leq
R,\quad\forall x\in\mathcal{X}$

Furthermore we assume that $f$ is convex and $G$-Lipschitz on $\mathbb{R}^{n}$
(if not we can use its extension $\tilde{f}$ according to the Theorem 2.1).

##  3 Projection-free Algorithm for Deterministic Optimization

We assume that the function $f$ is represented by a Black-Box first-order
oracle. This means that we can only get information by requesting the oracle
to return a subgradient of the requested point $x$ which we call
$g(x)\in\partial f(x)$. We provide the upper bound the on number of requests
from the oracle to achieve a desired accuracy.

Algorithm 2 Projection-free Algorithm

1: Require integer $T\geq 1$

2: Choose constants $\alpha>0$ and $\eta>0$ and the initial point
$x_{1}\in\mathcal{X}$

3: Choose $y_{1}=x_{1}$

4: Choose $Q_{0}=\mathbf{0}$

5: for $1\leq k\leq T-1$ do

6: Choose $Q_{k}=Q_{k-1}+y_{k}-x_{k}$

7: Choose $g_{k}=g(y_{k})\in\partial f(y_{k})$

8: Choose $x_{k+1}\in\operatorname{Argmin}_{x\in\mathcal{X}}\langle-
Q_{k},x\rangle$

9: Choose $y_{k+1}=\frac{1}{\alpha+\eta}\left(\alpha y_{k}+\eta x_{k+1}-\eta
Q_{k}-g_{k}\right)$

10: end for

11: return $\bar{x}=\frac{1}{T}\sum_{k=1}^{T}x_{k}$

######  Theorem 3.1 (Convergence of Algorithm 2).

Define $x^{*}\in\operatorname{Argmin}_{x\in\mathcal{X}}\\{f(x)\\}$. Then with
the following parameters,

$\alpha=\frac{G\sqrt{T}}{R}$ $\eta=\frac{G}{2R\sqrt{T}}$

the Algorithm 2 ensures

$f(\bar{x})-f(x^{*})\leq\frac{3RG}{\sqrt{T}}$

for any integer $T\geq 1$.

######  Proof 3.2.

See Appendix B.

Let us remember the Algorithm 1 convergence too:

######  Theorem 3.3 (PGD convergence rate).

Define $x^{*}\in\operatorname{Argmin}_{x\in\mathcal{X}}\\{f(x)\\}$. With the
following parameter,

$\beta=\frac{R}{G\sqrt{T}}$

the Algorithm 1 ensures

$f(\bar{x})-f(x^{*})\leq\frac{RG}{\sqrt{T}}$

for any integer $T\geq 1$.

######  Proof 3.4.

See Theorem 3.2. from [7].

Upper bound on the error in both algorithms are of the same order (up to a
constant) regarding the problem’s parameters. However, this does not mean that
they will always perform similarly as these are only upper bounds.
Simulations, provided on the Section 5, compare these two algorithms
numerically.

##  4 Projection-free Algorithm for Stochastic Optimization

In many applications, function $f$ is represented by a first-order
_stochastic_ oracle. The oracle takes $Y$ as input and returns $\hat{g}(Y)$
such that $\mathbb{E}\\{\hat{g}(Y)|Y\\}\in\partial f(Y)$, meaning we only have
access to a noisy but unbiased version of a subgradient. We also need to add
an extra condition:

$\mathbb{E}\\{\|\hat{g}(Y)\|^{2}|Y\\}\leq B^{2}$

for some known fixed $B\geq G$ (this simply means that the noise must have a
bounded variance). Surprisingly the algorithm works for this case too, only
the $g_{k}=g(y_{k})$ in 7 of Algorithm 2 is replaced with
$g_{k}=\hat{g}(Y_{k})$.

######  Theorem 4.1 (Convergence of Algorithm 2 with stochastic subgradient).

Define $x^{*}\in\operatorname{Argmin}_{x\in\mathcal{X}}\\{f(x)\\}$.

  * •

Then with the following parameters,

$\alpha=\frac{B\sqrt{T}}{R}$ $\eta=\frac{G}{2R\sqrt{T}}$

the Algorithm 2 with stochastic subgradient ensures

$\mathbb{E}\left\\{f(\bar{X})\right\\}-f(x^{*})\leq\frac{BR+2GR}{\sqrt{T}}$

for any integer $T\geq 1$.

  * •

Then with following parameters,

$\alpha=\frac{B\sqrt{T}}{R}$ $\eta=\frac{2B}{R\sqrt{T}}$

the Algorithm 2 with stochastic subgradient ensures

$\mathbb{E}\left\\{f(\bar{X})\right\\}-f(x^{*})\leq\frac{3GD}{2\sqrt{T}}$

for any integer $T\geq 1$.

######  Proof 4.2.

See Appendix C.

SGD algorithm is also very similar to PGD (Algorithm 1). The $g_{k}=g(x_{k})$
in 3 of Algorithm 1 is replaced with $g_{k}=\hat{g}(X_{k})$.

######  Theorem 4.3 (SGD convergence rate).

Define $x^{*}\in\operatorname{Argmin}_{x\in\mathcal{X}}\\{f(x)\\}$. With the
following parameter,

$\beta=\frac{R}{B\sqrt{T}}$

the SGD algorithm ensures

$\mathbb{E}\\{f(\bar{X})\\}-f(x^{*})\leq\frac{BR}{\sqrt{T}}$

for any integer $T\geq 1$.

######  Proof 4.4.

See Theorem 6.3. from [7].

Upper bound of the average error in both algorithms are of the same order (up
to a constant) regarding the problem’s parameters. However, if in addition to
parameter $B$ the parameter $G$ is provided, unlike PGD/SGD, our algorithm is
able to take advantage of it. Simulations, provided on the Section 5, compare
these two algorithms numerically.

##  5 Numerical results

In this section we provide two examples where our algorithm is compared with
PGD and SGD.

###  5.1 Hypercube domain with $L1$-norm objective function

This example is a good case study to see the numerical accuracy of our
algorithm as the exact minima is analytically calculable. However, this is not
an example to illustrate the computational gains. Our domain set is a
$n$-dimensional hypercube:

$\mathcal{X}=\left\\{x\in\mathbb{R}^{n}:|x^{(i)}|\leq 1,\,\forall
i\in\\{1,\cdots,n\\}\right\\}$

The set $\mathcal{X}$ is inside the Euclidean ball with radius $R=2\sqrt{n}$
centered at $x_{1}=\mathbf{0}$. Define the $L_{1}$-norm as:
$\|x\|_{1}=\sum_{i=1}^{n}|x^{(i)}|$. Let us choose the objective function
$f_{\omega}(x)=\|x-\omega\|_{1}$. It is easy to see that this function is
convex and Lipschitz continuous over $\mathbb{R}^{n}$ with coefficient

$G=\sqrt{n}$

When the exact subgradient is given to us without any error, we choose the
parameters as follows: $\beta=\frac{R}{G\sqrt{T}}$,
$\alpha=\frac{G\sqrt{T}}{R}$, $\eta=\frac{G}{2R\sqrt{T}}$.

In order to simulate an inexact subgradient, we added a mean-zero normal
distribution with covariance matrix $\sigma^{2}I_{n}$ to the exact
subgradient, i.e., $\hat{g}(y_{k})=g(y_{k})+N_{k}$ where $\\{N\\}_{k=1}^{T}$
are i.i.d, $n$ dimensional vector, samples of
$\mathcal{N}(0,\sigma^{2}I_{n})$. Thus,

$\mathbb{E}\\{\|\hat{g}(x)\|^{2}\\}=G^{2}+n\sigma^{2}$

so

$B=\sqrt{G^{2}+n\sigma^{2}}$

We choose the parameters as following: $\beta=\frac{R}{B\sqrt{T}}$,
$\alpha=\frac{B\sqrt{T}}{R}$, $\eta=\frac{G}{2R\sqrt{T}}$.

The experiments were done for different noise levels, $\sigma$, different
dimensions, $n$, and for different values of $T$. Two cases are considered in
which the parameter $\omega$ is inside or outside of the domain set,
$\mathcal{X}$. Clearly, in all of the figures, by increasing $T$, the error
decreases monotonically for both algorithms.

Four first figure show the results of the simulations for
$\omega\notin\mathcal{X}$. First observation from Fig. 1 is that both
algorithms are sensitive to the noise levels in low dimension (i.e. parameter
$n$). Another observation is that our algorithm gives a slightly better result
in high noise levels while the PGD/SGD works better in the low noises. In the
case of no-noise, they have the same performance but our algorithm shows a
more smooth convergence curve. By gradually increasing the dimension from $10$
in Fig. 1 to $500$ in the next three figures: Fig. 2, Fig. 3, and Fig. 4, both
algorithms start to show less sensitivity to the noise levels. Still our
algorithm gives a slightly better result in high noise levels while the
PGD/SGD works better in the low noise levels.

The next four first figure show the results of the simulations for
$\omega\in\mathcal{X}$. First observation from Fig. 5 is that both algorithms
are sensitive to the noise levels in low dimension (i.e. parameter $n$). While
both algorithms perform similarly in the presence of the noise, PGD/SGD
algorithm shows a very nonsmooth convergence curve in the absence of the
noise. By gradually increasing the dimension from $10$ in Fig. 5 to $500$ in
the next three figures: Fig. 6, Fig. 7, and Fig. 8, both algorithms perform
similarly in the presence of the noise. PGD/SGD algorithm shows a nonsmooth
and inferior convergence curve in the absence of the noise.

Figure 1: Dimension $n=10$ and $\omega$ is outside the set $\mathcal{X}$. Both
algorithms show a lot of sensitivity to the noise levels in low dimension.
Another observation is that our algorithm gives a slightly better result in
high noise levels while the PGD/SGD works better in the low noises. In the
case of no-noise, they have the same performance but our algorithm shows a
more smooth convergence curve. Figure 2: Dimension $n=100$ and $\omega$ is
outside the set $\mathcal{X}$. Both algorithms show less sensitivity to the
noise levels in a higher dimension. Again, our algorithm gives a slightly
better result in high noise levels while the PGD/SGD works better in the low
noises. Figure 3: Dimension $n=250$ and $\omega$ is outside the set
$\mathcal{X}$. Both algorithms show less sensitivity to the noise levels in a
higher dimension. Again, our algorithm gives a slightly better result in high
noise levels while the PGD/SGD works better in the low noises. Figure 4:
Dimension $n=500$ and $\omega$ is outside the set $\mathcal{X}$. Both
algorithms show less sensitivity to the noise levels in a higher dimension.
Again, our algorithm gives a slightly better result in high noise levels while
the PGD/SGD works better in the low noises. Figure 5: Dimension $n=10$ and
$\omega$ is inside the set $\mathcal{X}$. Both algorithms show a lot of
sensitivity to the noise levels in low dimension. While both algorithms
perform similarly in the presence of the noise, PGD/SGD algorithm shows a very
nonsmooth convergence curve in the absence of the noise. Figure 6: Dimension
$n=100$ and $\omega$ is inside the set $\mathcal{X}$. Again, both algorithms
perform similarly in the presence of the noise, PGD/SGD algorithm shows a
nonsmooth and inferior convergence curve in the absence of the noise. Figure
7: Dimension $n=250$ and $\omega$ is inside the set $\mathcal{X}$. Again, both
algorithms perform similarly in the presence of the noise, PGD/SGD algorithm
shows a nonsmooth and inferior convergence curve in the absence of the noise.
Figure 8: Dimension $n=500$ and $\omega$ is inside the set
$\mathcal{X}$.Again, both algorithms perform similarly in the presence of the
noise, PGD/SGD algorithm shows a nonsmooth and inferior convergence curve in
the absence of the noise.

###  5.2 Bounded nuclear norm domain with $L1$-norm objective function

The bounded nuclear norm domain, is a well known example in which the linear
optimization has significant computational advantage over projection.

######  Definition 5.1 (Singular Value Decomposition).

SVD of a real valued $m\times n$ matrix $A$ is a factorization of the form
$A=USV^{\top}$, where U is an $m\times m$ orthogonal matrix, $S$ is an
diagonal matrix with non-negative real numbers on the diagonal, and $V$ is an
$n\times n$ orthogonal matrix. The diagonal entries $s_{i}=S_{i,i}$ are
uniquely determined by $A$ and are known as the singular values of $A$. Also,
let us call the $i$-th column of matrix $U$ by $u_{i}$ and the $i$-th column
of matrix $V$ by $v_{i}$.

######  Definition 5.2 (Nuclear norm).

Nuclear norm or Trace norm of a $m\times n$ matrix $A$ with SVD $A=USV^{\top}$
is defined as:

$\|A\|_{*}=\sum_{i=1}^{\min(m,n)}s_{i}$

Now let us define the set $\mathcal{X}$ of all real valued $m\times n$
matrices with nuclear norm smaller that $\tau$. Fix $\tau>0$,

$\mathcal{X}\overset{def}{=}\\{A\in\mathbb{R}^{m\times
n}:\|A\|_{*}\leq\tau\\}$

Until this section, algorithms were defined in the vector form. However, they
can work for matrices just by rearranging the matrices into vector forms.
Frobenius norm of a matrix is equal to its vector form $L_{2}$-norm.

######  Definition 5.3 (Frobenius norm).

Frobenius norm can be defined as:

$\|A\|_{F}=\sqrt{\sum_{i,j=1}^{m,n}|a_{i,j}|^{2}}$

######  Lemma 5.4.

Frobenius norm can be upper bounded by Nuclear norm:

$\|A\|_{F}\leq\|A\|_{*}$

######  Proof 5.5.

See [11].

Now we are ready to come up with a enclosing Euclidean ball for the set
$\mathcal{X}$. If we choose $X_{1}=\mathbf{0}$ then

$\|X_{1}-Z\|_{F}=\|Z\|_{F}\leq\|Z\|_{*}\leq\tau,\quad\forall Z\in\mathcal{X}$

Let us choose the objective function

$f_{W}(X)=\sum_{i=1}^{m}\sum_{j=1}^{n}|X_{i,j}-W_{i,j}|$

It is easy to see that this function is convex and Lipschitz continuous with
coefficient

$G=\sqrt{nm}$

When the exact subgradient is given to us without any error, we choose the
parameters as before: $\beta=\frac{R}{G\sqrt{T}}$,
$\alpha=\frac{G\sqrt{T}}{R}$, $\eta=\frac{G}{2R\sqrt{T}}$.

In order to simulate inexact subgradients, we added a mean-zero normal
distribution with covariance matrix $\sigma^{2}I_{nm}$ to the exact
subgradients, i.e., $\hat{g}(y_{k})=g(y_{k})+N_{k}$ where $\\{N_{k}\\}$ are
i.i.d, $nm$ vectors, samples of $\mathcal{N}(0,\sigma^{2}I_{nm})$. Thus,

$\mathbb{E}\\{\|\hat{g}(x)\|^{2}\\}=G^{2}+nm\sigma^{2}$

so

$B=\sqrt{G^{2}+nm\sigma^{2}}$

Thus the parameters are: $\beta=\frac{R}{B\sqrt{T}}$,
$\alpha=\frac{B\sqrt{T}}{R}$, $\eta=\frac{G}{2R\sqrt{T}}$.

We used the two following lemmas to implement our algorithm and PGD/SGD:

######  Lemma 5.6 (Linear optimization on nuclear-norm ball).

Fix a parameter $\tau>0$. Let $A$ be a $m\times n$ matrix and consider its
singular-value decomposition $A=USV^{\top}$. Then

$\operatorname{Argmin}_{\|X\|_{*}\leq\tau}\langle A,X\rangle_{F}=\tau
u_{1}v_{1}^{\top}$

######  Proof 5.7.

See [17].

######  Lemma 5.8 (Projection onto the nuclear-norm ball).

Fix a parameter $\tau>0$. Let $A$ be a $m\times n$ matrix and consider its
singular-value decomposition $A=USV^{\top}$. If $\|A\|_{*}\geq\tau$, then the
Euclidean projection of $A$ onto the nuclear-norm ball is given by

$\pi_{\|X\|_{*}\leq\tau}(A)=\sum_{i=1}^{\min(m,n)}\max(0,s_{i}-\lambda)u_{i}v_{i}^{\top}$

where $\lambda\geq 0$ is the solution to the equation

$\sum_{i=1}^{\min(m,n)}\max(0,s_{i}-\lambda)=\tau$

######  Proof 5.9.

See [2], [10].

The experiments were done for different noise levels, $\sigma$, different
dimensions, and for different values of $T$. Two cases are considered in which
the parameter $W$ is inside or outside of the domain set, $\mathcal{X}$. When
$W$ is inside, it is the optimal point. However, when the $W$ is outside, then
the optimal point is not calculable analytically (unlike the first experiment)
so we only demonstrate the value of the function $f(\bar{x})$ instead of the
error $f(\bar{x})-f(x^{*})$. Clearly, in all of the figures, by increasing
$T$, the error decreases monotonically for both algorithms.

Four first figure show the results of the simulations for
$W\notin\mathcal{X}$. First observation from Fig. 9 is that PGD/SGD shows a
superior result over our algorithm in the low noise levels. This superiority
vanishes in the higher noise levels. By gradually increasing the dimensions in
the next three figures: Fig. 10, Fig. 11, and Fig. 12, PGD/SGD, still, shows a
superior result over our algorithm in the low noise levels. This superiority
vanishes in the higher noise levels and our algorithm starts to do a better
job. Clearly, PGD/SGD is more sensitive to the noise level.

The next four first figure show the results of the simulations for
$W\in\mathcal{X}$. First observation from Fig. 13 is that in the absence of
the noise, PGD/SDG does an inferior job. However, introducing small amount of
noise improves the SGD/PGD performance dramatically. In other words, our
algorithm is showing a superior result over PGD/SDG in the low noise levels,
this superiority vanishes in the higher noise levels. By gradually increasing
the dimension in the next three figures: Fig. 14, Fig. 15, and Fig. 16, still,
in the absence of the noise, PGD/SDG does an inferior job. Again, this
superiority vanishes in the higher noise levels. One more time, introducing
small amount of noise improve the SGD/PGD performance dramatically.

Figure 9: Parameters are $n=5$, $m=5$. $W$ is outside of the set
$\mathcal{X}$. PGD/SGD is showing a superior result over our algorithm in the
low noise levels. This superiority vanishes in the higher noise levels. Figure
10: Parameters are $n=5$, $m=10$. $W$ is outside of the set $\mathcal{X}$.
PGD/SGD is showing a superior result over our algorithm in the low noise
levels. This superiority vanishes in the higher noise levels. Figure 11:
Parameters are $n=10$, $m=10$. $W$ is outside of the set $\mathcal{X}$.
PGD/SGD is showing a superior result over our algorithm in the low noise
levels. This superiority vanishes in the higher noise levels and our algorithm
does a better job. Clearly, PGD/SGD is more sensitive to the noise level.
Figure 12: Parameters are $n=10$, $m=20$. $W$ is outside of the set
$\mathcal{X}$. PGD/SGD is showing a superior result over our algorithm in the
low noise levels. This superiority vanishes in the higher noise levels and our
algorithm does a better job. Clearly, PGD/SGD is more sensitive to the noise
level. Figure 13: Parameters are $n=5$, $m=5$. $W$ is inside of the set
$\mathcal{X}$. In the absence of the noise, PGD/SDG does an inferior job.
However, introducing small amount of noise improves the SGD/PGD performance
dramatically. In other words, our algorithm is showing a superior result over
PGD/SDG in the low noise levels, this superiority vanishes in the higher noise
levels. Figure 14: Parameters are $n=5$, $m=10$. $W$ is inside of the set
$\mathcal{X}$. In the absence of the noise, PGD/SDG does an inferior job.
However, introducing small amount of noise improve the SGD/PGD performance
dramatically. In other words, our algorithm is showing a superior result over
PGD/SDG in the low noise levels, this superiority vanishes in the higher noise
levels. Figure 15: Parameters are $n=10$, $m=10$. $W$ is inside of the set
$\mathcal{X}$. In the absence of the noise, PGD/SDG does an inferior job.
However, introducing small amount of noise improve the SGD/PGD performance
dramatically. In other words, our algorithm is showing a superior result over
PGD/SDG in the low noise levels, this superiority vanishes in the higher noise
levels. Figure 16: Parameters are $n=10$, $m=20$. $W$ is inside of the set
$\mathcal{X}$. In the absence of the noise, PGD/SDG does an inferior job.
However, introducing small amount of noise improve the SGD/PGD performance
dramatically. In other words, our algorithm is showing a superior result over
PGD/SDG in the low noise levels, this superiority vanishes in the higher noise
levels.

##  6 Conclusions and Open Problems

This paper addresses the problem of solving general constrained convex
optimization without using projection. Prior works on projection-free
algorithms focus mainly on smooth problems and/or problems with special
constraint structure. The simulations and the convergence theorems show that
our algorithm’s performance is comparable with the PGD/SGD algorithm, thus it
can be a substitute for the PGD/SGD algorithm if projection-free algorithms
are favoured.

An open problem is whether our algorithm can be modified to exploit the gains
of mirror descent [6, 3]. A well known algorithm that replaces the Euclidean
norm in PGD/SGD with a Bregman divergence which results in improved
performance with respect to system dimension in certain cases (such as when
the domain set is a probability simplex). Another question arises considering
that PGD/SGD with time varying step-size reaches the improved rate, $O(1/T)$,
for nonsmooth strongly convex optimization. It is unclear how to extend our
algorithm in this scenario.

##  Appendix A Proof of the Theorem 2.1

######  Proof A.1.

This proof is collected from a larger _McShane-Whitney extension theorem_ of
[25] and presented in a condense format.

  1. (i)

Fix $w$ in $\mathbb{R}^{n}$. For fixed $z$ in the set $\mathcal{X}$ we have
for every $x$ in the set $\mathcal{X}$:

$\displaystyle f(x)+G\|x-w\|$ $\displaystyle\geq
f(z)-G\|z-x\|+G\|x-w\|,\quad\text{(By Lipschitz)}$ $\displaystyle\geq
f(z)-G\|z-x\|+G\|x-z\|-G\|z-w\|,\quad\text{(triangle inequality) }$
$\displaystyle=f(z)-G\|z-w\|$

Then taking the infimum over $x$ in the set $\mathcal{X}$ gives

$f(w)\geq f(z)-G\|z-w\|>-\infty$

  2. (ii)

Let $w_{1},w_{2}\in\mathbb{R}^{n}$ and $x\in\mathcal{X}$. Then
$\|w_{1}-x\|\leq\|w_{2}-x\|+\|w_{1}-w_{2}\|$, therefore

$\displaystyle f(x)+G\|w_{1}-x\|\leq
f(x)+G\|w_{2}-x\|+G\|w_{1}-w_{2}\|\Rightarrow$
$\displaystyle\tilde{f}(w_{1})\leq
f(x)+G\|w_{2}-x\|+G\|w_{1}-w_{2}\|\Rightarrow$
$\displaystyle\tilde{f}(w_{1})-G\|w_{1}-w_{2}\|\leq
f(x)+G\|w_{2}-x\|\Rightarrow$
$\displaystyle\tilde{f}(w_{1})-G\|w_{1}-w_{2}\|\leq\tilde{f}(w_{2})\Rightarrow$
$\displaystyle\tilde{f}(w_{1})-\tilde{f}(w_{2})\leq G\|w_{1}-w_{2}\|$

If we start from the inequality $\|w_{2}-x\|\leq\|w_{1}-x\|+\|w_{1}-w_{2}\|$
and work as above, we get $\tilde{f}(w_{1})-\tilde{f}(w_{2})\leq
G\|w_{1}-w_{2}\|$ therefore $|\tilde{f}(w_{1})-\tilde{f}(w_{2})|\leq
G\|w_{1}-w_{2}\|$.

  3. (iii)

Fix $x$, and $g\in\partial\tilde{f}(x)$. For any $y$ We have

$\tilde{f}(x)+\langle g,y-x\rangle\leq\tilde{f}(y)\leq\tilde{f}(x)+G\|y-x\|$

Now let $y=x+\epsilon g$ for $\epsilon>0$, then

$\langle g,\epsilon g\rangle=\epsilon\|g\|^{2}\leq G\|\epsilon g\|$

so

$\|g\|\leq G$

  4. (iv)

Let $w_{1},w_{2}\in\mathbb{R}^{n}$ and $0\leq\theta\leq 1$

$\displaystyle\theta\tilde{f}(w_{1})+(1-\theta)\tilde{f}(w_{2})$
$\displaystyle=$
$\displaystyle\theta\inf_{x_{1}\in\mathcal{X}}\\{f(x_{1})+G\|w_{1}-x_{1}\|\\}+(1-\theta)\inf_{x_{2}\in\mathcal{X}}\\{f(x_{2})+G\|w_{2}-x_{2}\|\\}$
$\displaystyle=$ $\displaystyle\inf_{x_{1},x_{2}\in\mathcal{X}}\\{\theta
f(x_{1})+\theta
G\|w_{1}-x_{1}\|+(1-\theta)f(x_{2})+(1-\theta)G\|w_{2}-x_{2}\|\\}$
$\displaystyle\geq$ $\displaystyle\inf_{x_{1},x_{2}\in\mathcal{X}}\\{f(\theta
x_{1}+(1-\theta)x_{2})+G\|\theta w_{1}-\theta
x_{1}+(1-\theta)w_{2}-(1-\theta)x_{2}\|\\}$ $\displaystyle=$
$\displaystyle\inf_{y\in\mathcal{X}}\\{f(y)+G\|\theta
w_{1}+(1-\theta)w_{2}-y\|\\}$ $\displaystyle=$ $\displaystyle\tilde{f}(\theta
w_{1}+(1-\theta)w_{2})$

  5. (v)

We show that $\tilde{f}$ extends $f$. If $w\in\mathcal{X}$, then

$\tilde{f}(w)=\inf_{x\in\mathcal{X}}\\{f(x)+G\|w-x\|\\}\leq
f(w)+G\|w-w\|=f(w)$

on the other hand, if $w\in\mathcal{X}$, then

$\tilde{f}(w)=\inf_{x\in\mathcal{X}}\\{f(x)+G\|w-x\|\\}\overset{a}{\geq}\inf_{x\in\mathcal{X}}\\{f(w)\\}=f(w)$

where (_a_) is a direct use of Lipschitz continuity’s definition. Thus,
$\forall w\in\mathcal{X}$ we have $\tilde{f}(w)=f(w)$

##  Appendix B Proof of the Theorem 3.1

######  Lemma B.1.

Let function $f$ be convex on the convex set $C$. Fix $\alpha>0$, $x_{0}\in
C$. Suppose

$x^{\prime}=\operatorname{Argmin}_{x\in
C}\left\\{f(x)+\theta\|x-x_{0}\|^{2}\right\\}$

then $\forall z\in C$

$f(x^{\prime})+\theta\|x^{\prime}-x_{0}\|^{2}\leq
f(z)+\theta\|z-x_{0}\|^{2}-\theta\|z-x^{\prime}\|^{2}$

######  Proof B.2.

A special case of the Lemma 6 of [24].

######  Lemma B.3.

In Algorithm 2, $\forall t\geq 1$ we have:

$Q_{t}=\sum_{k=1}^{t}y_{k}-\sum_{k=1}^{t}x_{k}$

######  Proof B.4.

Just combine 6 and 4 from Algorithm 2 and sum over time.

######  Lemma B.5.

For any $a,b\in\mathbb{R}^{n}$ and $\theta>0$,

$\langle a,b\rangle+\frac{\theta}{2}\|a\|^{2}\geq-\frac{\|b\|^{2}}{2\theta}$

######  Proof B.6.

Combine Cauchy–Schwarz inequality:

$\langle a,b\rangle\geq-\|a\|\|b\|$

with

$\frac{\theta}{2}\|a\|^{2}+\frac{\|b\|^{2}}{2\theta}-\|a\|\|b\|=\left(\sqrt{\frac{\theta}{2}}\|a\|+\sqrt{\frac{1}{2\theta}}\|b\|\right)^{2}\geq
0$

######  Proof B.7 (Proof of the Theorem 3.1).

It is easy to verify that 9 from Algorithm 2 can be written as:

(6) $y_{k+1}=\operatorname{Argmin}_{y\in\mathbb{R}^{n}}\left\\{\langle\eta
Q_{k}+g_{k},y\rangle+\frac{\alpha}{2}\|y-y_{k}\|^{2}+\frac{\eta}{2}\|y-x_{k+1}\|^{2}\right\\}$

Notice the function:

$\langle\eta Q_{k}+g_{k},y\rangle+\frac{\eta}{2}\|y-x_{k+1}\|^{2}$

is convex, thus Equation Eq. 6 satisfies the Lemma B.1 so we get:

$\langle\eta
Q_{k}+g_{k},y_{k+1}\rangle+\frac{\alpha}{2}\|y_{k+1}-y_{k}\|^{2}+\frac{\eta}{2}\|y_{k+1}-x_{k+1}\|^{2}\\\
\leq\langle\eta
Q_{k}+g_{k},x^{*}\rangle+\frac{\alpha}{2}\|x^{*}-y_{k}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{k+1}\|^{2}+\frac{\eta}{2}\|x^{*}-x_{k+1}\|^{2}$

We have $\|x_{k+1}-x^{*}\|\leq 2R$ as $x_{k+1},x^{*}\in\mathcal{X}$,

$\langle\eta
Q_{k}+g_{k},y_{k+1}\rangle+\frac{\alpha}{2}\|y_{k+1}-y_{k}\|^{2}+\frac{\eta}{2}\|y_{k+1}-x_{k+1}\|^{2}\\\
\leq\langle\eta
Q_{k}+g_{k},x^{*}\rangle+\frac{\alpha}{2}\|x^{*}-y_{k}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{k+1}\|^{2}+2\eta
R^{2}$

Add $\langle\eta Q_{k},-x_{k+1}\rangle$ and $\langle g_{k},-y_{k}\rangle$ to
both sides

$\langle\eta Q_{k},y_{k+1}-x_{k+1}\rangle+\langle
g_{k},y_{k+1}-y_{k}\rangle+\frac{\alpha}{2}\|y_{k+1}-y_{k}\|^{2}\\\
\leq\langle\eta Q_{k},x^{*}-x_{k+1}\rangle+\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\alpha}{2}\|x^{*}-y_{k}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{k+1}\|^{2}+2\eta
R^{2}$

An easy consequence of 8 from Algorithm 2 is: $\langle
Q_{k},x_{k+1}\rangle\geq\langle Q_{k},x^{*}\rangle$ for all
$x^{*}\in\mathcal{X}$, thus

$\langle\eta Q_{k},y_{k+1}-x_{k+1}\rangle+\langle
g_{k},y_{k+1}-y_{k}\rangle+\frac{\alpha}{2}\|y_{k+1}-y_{k}\|^{2}+\frac{\eta}{2}\|y_{k+1}-x_{k+1}\|^{2}\\\
\leq\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\alpha}{2}\|x^{*}-y_{k}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{k+1}\|^{2}+2\eta
R^{2}$

A simple conclusion from Equation 6 from Algorithm 2 is:

$\langle
Q_{k},y_{k+1}-x_{k+1}\rangle=\frac{1}{2}\|Q_{k+1}\|^{2}-\frac{1}{2}\|Q_{k}\|^{2}-\frac{1}{2}\|y_{k+1}-x_{k+1}\|^{2}$

so we get:

$\frac{\eta}{2}\|Q_{k+1}\|^{2}-\frac{\eta}{2}\|Q_{k}\|^{2}+\langle
g_{k},y_{k+1}-y_{k}\rangle+\frac{\alpha}{2}\|y_{k+1}-y_{k}\|^{2}\\\
\leq\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\alpha}{2}\|x^{*}-y_{k}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{k+1}\|^{2}+2\eta
R^{2}$

Using Lemma B.5 we get:

$\frac{\eta}{2}\|Q_{k+1}\|^{2}-\frac{\eta}{2}\|Q_{k}\|^{2}-\frac{\|g_{k}\|^{2}}{2\alpha}\\\
\leq\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\alpha}{2}\|x^{*}-y_{k}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{k+1}\|^{2}+2\eta
R^{2}$

Sum from $k=1$ to $k=T-1$ to get

$\frac{\eta}{2}\|Q_{T}\|^{2}-\frac{\eta}{2}\|Q_{1}\|^{2}-(T-1)2\eta
R^{2}-\frac{1}{2\alpha}\sum_{k=1}^{T-1}\|g_{k}\|^{2}\\\
\leq\sum_{k=1}^{T-1}\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\alpha}{2}\|x^{*}-y_{1}\|^{2}-\frac{\alpha}{2}\|x^{*}-y_{T}\|^{2}$

Combining 3 and Eq. 5 from Algorithm 2 gives us: $\|x^{*}-y_{1}\|\leq R$, thus

$\frac{\eta}{2}\|Q_{T}\|^{2}-\frac{\eta}{2}\|Q_{1}\|^{2}-(T-1)2\eta
R^{2}-\frac{1}{2\alpha}\sum_{k=1}^{T-1}\|g_{k}\|^{2}\\\
\leq\sum_{k=1}^{T-1}\langle g_{k},x^{*}-y_{k}\rangle+\frac{\alpha
R^{2}}{2}-\frac{\alpha}{2}\|x^{*}-y_{T}\|^{2}$

Combining 6 and 3 from Algorithm 2 gives us:
$Q_{1}=Q_{0}+y_{1}-x_{1}=\mathbf{0}$, thus

$\frac{\eta}{2}\|Q_{T}\|^{2}-(T-1)2\eta
R^{2}-\frac{1}{2\alpha}\sum_{k=1}^{T-1}\|g_{k}\|^{2}\\\
\leq\sum_{k=1}^{T-1}\langle g_{k},x^{*}-y_{k}\rangle+\frac{\alpha
R^{2}}{2}-\frac{\alpha}{2}\|x^{*}-y_{T}\|^{2}$

Add and subtract $\langle g_{T},x^{*}-y_{T}\rangle$ to the right hand side,

$\frac{\eta}{2}\|Q_{T}\|^{2}-(T-1)2\eta
R^{2}-\frac{1}{2\alpha}\sum_{k=1}^{T-1}\|g_{k}\|^{2}\\\
\leq\sum_{k=1}^{T}\langle g_{k},x^{*}-y_{k}\rangle+\frac{\alpha
R^{2}}{2}-\frac{\alpha}{2}\|x^{*}-y_{T}\|^{2}-\langle
g_{T},x^{*}-y_{T}\rangle$

Again using Lemma B.5 we get,

$\frac{\eta}{2}\|Q_{T}\|^{2}-(T-1)2\eta
R^{2}-\frac{1}{2\alpha}\sum_{k=1}^{T-1}\|g_{k}\|^{2}\leq\sum_{k=1}^{T}\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\alpha R^{2}}{2}+\frac{\|g_{T}\|^{2}}{2\alpha}$

Rearranging,

(7) $\sum_{k=1}^{T}\langle
g_{k},x^{*}-y_{k}\rangle+\frac{\eta}{2}\|Q_{T}\|^{2}\leq\frac{\alpha
R^{2}}{2}+\frac{1}{2\alpha}\sum_{k=1}^{T}\|g_{k}\|^{2}+(T-1)2\eta R^{2}$

Using convexity of $f$ we get

$\sum_{k=0}^{T}\left(f(y_{k})-f(x^{*})\right)+\frac{\eta}{2}\|Q_{T}\|^{2}\leq\frac{\alpha
R^{2}}{2}+\frac{1}{2\alpha}\sum_{k=1}^{T}\|g_{k}\|^{2}+(T-1)2\eta R^{2}$

Using $G$-Lipschitz continuity of $f$ we get

$\sum_{k=0}^{T}\left(f(y_{k})-f(x^{*})\right)+\frac{\eta}{2}\|Q_{T}\|^{2}\leq\frac{\alpha
R^{2}}{2}+T\frac{G^{2}}{2\alpha}+(T-1)2\eta R^{2}$

Dividing by $T$ and using Jensen inequality

$\displaystyle
f\left(\frac{1}{T}\sum_{k=1}^{T}y_{k}\right)-f(x^{*})+\frac{1}{T}\frac{\eta}{2}\|Q_{T}\|^{2}$
$\displaystyle\leq$ $\displaystyle\frac{\alpha
R^{2}}{2T}+\frac{G^{2}}{2\alpha}+\frac{T-1}{T}2\eta R^{2}$ $\displaystyle\leq$
$\displaystyle\frac{\alpha R^{2}}{2T}+\frac{G^{2}}{2\alpha}+2\eta R^{2}$

Similar to 11 from Algorithm 2, define $\bar{y}=\frac{1}{T}\sum_{k=1}^{T}$.
Add and subtract $f(\bar{x})$ to the left hand side (LHS),

$f(\bar{x})-f(x^{*})+f(\bar{y})-f(\bar{x})+\frac{1}{T}\frac{\eta}{2}\|Q_{T}\|^{2}\leq\frac{\alpha
R^{2}}{2T}+\frac{G^{2}}{2\alpha}+2\eta R^{2}$

Using Lemma B.3 and $G$-Lipschitz continuity of $f$ we get

$f(\bar{x})-f(x^{*})-G\|\bar{y}-\bar{x}\|+T\frac{\eta}{2}\|\bar{y}-\bar{x}\|^{2}\leq\frac{\alpha
R^{2}}{2T}+\frac{G^{2}}{2\alpha}+2\eta R^{2}$

By completing the square we have

$f(\bar{x})-f(x^{*})\leq\frac{\alpha R^{2}}{2T}+\frac{G^{2}}{2\alpha}+2\eta
R^{2}+\frac{G^{2}}{2\eta T}$

Choose

$\alpha=\frac{G\sqrt{T}}{R}$

and

$\eta=\frac{2G}{R\sqrt{T}}$

which means

$f(\bar{x})-f(x^{*})\leq\frac{3RG}{\sqrt{T}}$

##  Appendix C Proof of the Theorem 4.1

######  Proof C.1 (Proof of the Theorem 4.1).

The analysis is the same up to Equation Eq. 7. Taking expectations of both
sides of Equation Eq. 7:

$\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}-(T-1)2\eta
R^{2}\leq\sum_{k=1}^{T}\mathbb{E}\left\\{\langle
g_{k},x^{*}-Y_{k}\rangle\right\\}+\frac{\alpha
R^{2}}{2}+\frac{1}{2\alpha}\sum_{k=1}^{T}\mathbb{E}\left\\{\|g_{k}\|^{2}\right\\}$

Replacing $g_{k}=\hat{g}(Y_{k})$,

$\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}-(T-1)2\eta R^{2}\\\
\leq\sum_{k=1}^{T}\mathbb{E}\left\\{\langle\hat{g}(Y_{k}),x^{*}-Y_{k}\rangle\right\\}+\frac{\alpha
R^{2}}{2}+\frac{1}{2\alpha}\sum_{k=1}^{T}\mathbb{E}\left\\{\|\hat{g}(Y_{k})\|^{2}\right\\}$

Using the following basic equivalence:
$\mathbb{E}\\{A\\}=\mathbb{E}\\{\mathbb{E}\\{A|B\\}\\}$

$\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}-(T-1)2\eta R^{2}\\\
\leq\sum_{k=1}^{T}\mathbb{E}\left\\{\langle\mathbb{E}\\{\hat{g}(Y_{k})|Y_{k}\\},x^{*}-Y_{k}\rangle\right\\}+\frac{\alpha
R^{2}}{2}+\frac{1}{2\alpha}\sum_{k=1}^{T}\mathbb{E}\left\\{\mathbb{E}\left\\{\|\hat{g}(Y_{k})\|^{2}|Y_{k}\right\\}\right\\}$

thus

$\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}-(T-1)2\eta
R^{2}\leq\sum_{k=1}^{T}\mathbb{E}\left\\{\langle\mathbb{E}\\{\hat{g}(Y_{k})|Y_{k}\\},x^{*}-Y_{k}\rangle\right\\}+\frac{\alpha
R^{2}}{2}+\frac{TB^{2}}{2\alpha}$

We know $\mathbb{E}\\{\hat{g}(Y_{k})|Y_{k}\\}=g(Y_{k})$ so using convexity of
$f$ we get,

$\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}-(T-1)2\eta
R^{2}\leq\sum_{k=1}^{T}\mathbb{E}\left\\{f(x^{*})-f(Y_{k})\right\\}+\frac{\alpha
R^{2}}{2}+\frac{TB^{2}}{2\alpha}$

Rearranging,

$\sum_{k=1}^{T}\mathbb{E}\left\\{f(Y_{k})-f(x^{*})\right\\}+\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}\leq\frac{\alpha
R^{2}}{2}+\frac{TB^{2}}{2\alpha}+(T-1)2\eta R^{2}$

Dividing by $T$ and using Jensen inequality,

$\mathbb{E}\left\\{f\left(\frac{1}{T}\sum_{k=0}^{T}Y_{k}\right)-f(x^{*})\right\\}+\frac{1}{T}\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}\leq\frac{\alpha
R^{2}}{2T}+\frac{B^{2}}{2\alpha}+2\eta R^{2}$

Add and subtract $\mathbb{E}\\{f(\bar{x})\\}$ to the LHS,

$\mathbb{E}\left\\{f(\bar{X})-f(x^{*})+f(\bar{Y})-f(\bar{X})\right\\}+\frac{1}{T}\frac{\eta}{2}\mathbb{E}\left\\{\|Q_{T}\|^{2}\right\\}\leq\frac{\alpha
R^{2}}{2T}+\frac{B^{2}}{2\alpha}+2\eta R^{2}$

Use Lemma B.3 and $G$-Lipschitz continuity of $f$ we get,

$\mathbb{E}\left\\{f(\bar{X})-f(x^{*})+G\|\bar{Y}-\bar{X}\|\right\\}+T\frac{\eta}{2}\mathbb{E}\left\\{\|\bar{Y}-\bar{X}\|^{2}\right\\}\leq\frac{\alpha
R^{2}}{2T}+\frac{B^{2}}{2\alpha}+2\eta R^{2}$

By completing the square we have,

(8) $\mathbb{E}\left\\{f(\bar{X})\right\\}-f(x^{*})\leq\frac{\alpha
R^{2}}{2T}+\frac{B^{2}}{2\alpha}+\frac{\eta D^{2}}{2}+\frac{G^{2}}{2\eta T}$

Choose

$\alpha=\frac{B\sqrt{T}}{R}$

and

$\eta=\frac{2G}{R\sqrt{T}}$

which means

$\mathbb{E}\left\\{f(\bar{X})\right\\}-f(x^{*})\leq\frac{BR+2RG}{\sqrt{T}}$

However, if we do not have access to $G$ independent from $B$ then replacing
the inequality $G\leq B$ in Equation Eq. 8 we get,

$\mathbb{E}\left\\{f(\bar{X})\right\\}-f(x^{*})\leq\frac{\alpha
R^{2}}{2T}+\frac{B^{2}}{2\alpha}+\frac{\eta D^{2}}{2}+\frac{B^{2}}{2\eta T}$

Choose

$\alpha=\frac{B\sqrt{T}}{R}$

and

$\eta=\frac{2G}{R\sqrt{T}}$

which means

$\mathbb{E}\left\\{f(\bar{X})\right\\}-f(x^{*})\leq\frac{3BR}{\sqrt{T}}$

## References

  * [1] K. Balasubramanian and S. Ghadimi, Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates, in Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, eds., vol. 31, Curran Associates, Inc., 2018, https://proceedings.neurips.cc/paper/2018/file/36d7534290610d9b7e9abed244dd2f28-Paper.pdf.
  * [2] A. Beck, First-order methods in optimization, SIAM, 2017.
  * [3] A. Beck and M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters, 31 (2003), pp. 167–175.
  * [4] D. Bertsekas, Network optimization: continuous and discrete models, vol. 8, Athena Scientific, 1998.
  * [5] D. P. Bertsekas, Linear network optimization: algorithms and codes, MIT press, 1991.
  * [6] C. Blair, Problem complexity and method efficiency in optimization (a. s. nemirovsky and d. b. yudin), SIAM Review, 27 (1985), pp. 264–265, https://doi.org/10.1137/1027074, https://doi.org/10.1137/1027074, https://arxiv.org/abs/https://doi.org/10.1137/1027074.
  * [7] S. Bubeck et al., Convex optimization: Algorithms and complexity, Foundations and Trends® in Machine Learning, 8 (2015), pp. 231–357.
  * [8] G. Di Pillo, Exact penalty methods, Algorithms for continuous optimization: the state of the art, (1994), pp. 209–253.
  * [9] M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), pp. 95–110, https://doi.org/https://doi.org/10.1002/nav.3800030109, https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800030109, https://arxiv.org/abs/https://onlinelibrary.wiley.com/doi/pdf/10.1002/nav.3800030109.
  * [10] D. Garber, On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems, SIAM Journal on Optimization, 31 (2021), pp. 727–753.
  * [11] G. H. Golub and C. F. Van Loan, Matrix computations, JHU press, 2013\.
  * [12] S.-P. Han, A successive projection method, Mathematical Programming, 40 (1988), pp. 1–14.
  * [13] E. Hazan and S. Kale, Projection-free online learning, arXiv preprint arXiv:1206.4657, (2012).
  * [14] E. Hazan and H. Luo, Variance-reduced and projection-free stochastic optimization, in Proceedings of The 33rd International Conference on Machine Learning, M. F. Balcan and K. Q. Weinberger, eds., vol. 48 of Proceedings of Machine Learning Research, New York, New York, USA, 20–22 Jun 2016, PMLR, pp. 1263–1271, https://proceedings.mlr.press/v48/hazana16.html.
  * [15] E. Hazan and E. Minasyan, Faster projection-free online learning, in Conference on Learning Theory, PMLR, 2020, pp. 1877–1893.
  * [16] A. N. Iusem and B. F. Svaiter, A row-action method for convex programming, Mathematical programming, 64 (1994), pp. 149–171.
  * [17] M. Jaggi, Revisiting frank-wolfe: Projection-free sparse convex optimization, in International Conference on Machine Learning, PMLR, 2013, pp. 427–435.
  * [18] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, Rate control for communication networks: shadow prices, proportional fairness and stability, Journal of the Operational Research society, 49 (1998), pp. 237–252.
  * [19] K. Levy and A. Krause, Projection free online learning over smooth sets, in Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, K. Chaudhuri and M. Sugiyama, eds., vol. 89 of Proceedings of Machine Learning Research, PMLR, 16–18 Apr 2019, pp. 1458–1466, https://proceedings.mlr.press/v89/levy19a.html.
  * [20] A. Lin, A class of methods for projection on a convex set, Advanced Modeling and Optimization (AMO), 5 (2003).
  * [21] A. Lin, Projection algorithms in nonlinear programming, The Johns Hopkins University, 2003.
  * [22] M. Mahdavi, T. Yang, R. Jin, S. Zhu, and J. Yi, Stochastic gradient descent with only one projection, in Advances in Neural Information Processing Systems, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, eds., vol. 25, Curran Associates, Inc., 2012, https://proceedings.neurips.cc/paper/2012/file/c52f1bd66cc19d05628bd8bf27af3ad6-Paper.pdf.
  * [23] M. J. Neely, Stochastic network optimization with application to communication and queueing systems, Synthesis Lectures on Communication Networks, 3 (2010), pp. 1–211.
  * [24] Y. Nesterov, Primal-dual subgradient methods for convex problems, Mathematical programming, 120 (2009), pp. 221–259.
  * [25] I. Petrakis, McShane-Whitney extensions in constructive analysis, Logical Methods in Computer Science, Volume 16, Issue 1 (2020), https://doi.org/10.23638/LMCS-16(1:18)2020, https://lmcs.episciences.org/6105.
  * [26] R. J. Vanderbei et al., Linear programming, Springer, 2020.
  * [27] H. Yu and M. J. Neely, A primal-dual type algorithm with the o(1/t) convergence rate for large scale constrained convex programs, in 2016 IEEE 55th Conference on Decision and Control (CDC), 2016, pp. 1900–1905, https://doi.org/10.1109/CDC.2016.7798542.
  * [28] H. Yu and M. J. Neely, A primal-dual parallel method with $o(1/\epsilon)$ convergence for constrained composite convex programs, 2017, https://doi.org/10.48550/ARXIV.1708.00322, https://arxiv.org/abs/1708.00322.