∎

11institutetext:  Max Grieshammer 22institutetext: Michael Stingl
33institutetext: Andrian Uihlein 44institutetext: Chair of Applied Mathematics
(Continuous Optimization), Friedrich-Alexander Universität Erlangen-Nürnberg
(FAU), Cauerstr. 11, 91058 Erlangen, Germany
44email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

Lukas Pflug55institutetext: Competence Unit for Scientific Computing,
Friedrich-Alexander Universität Erlangen-Nürnberg (FAU), Martensstr. 5a, 91058
Erlangen, Germany
55email<EMAIL_ADDRESS>

# On step sizes rules for the continuous stochastic gradient scheme

Convergence results for constant step sizes and an Armijo-type line search

Max Grieshammer  Lukas Pflug  Michael Stingl  Andrian Uihlein

(Received: date / Accepted: date)

###### Abstract

The recently proposed continuous stochastic gradient descent (CSG) scheme
represents an efficient method for the solution of a large class of stochastic
optimization problems. During the course of the iterations, CSG uses a
tailored convex combination of previously drawn gradient and objective
function samples to approximate the full gradient and objective function value
at the current position. It was shown that the error in these approximations
tends to zero during the optimization process and thus, CSG more and more
behaves like a full gradient descent algorithm. In this contribution, we show
that convergence results for constant step sizes known from full gradient
descent schemes carry over to CSG. Furthermore, we augment CSG by an Armijo-
type backtracking line search based on the gradient and objective function
approximations and provide convergence results for this variant. The resulting
novel methods are applicable for a large class of optimization problems. Their
performance is demonstrated in comparison to other stochastic gradient schemes
known from literature.

###### Keywords:

Stochastic gradient scheme Convergence analysis Step size rule Backtracking
line search Constant step size

###### MSC:

65K05 90C06 90C15 90C30

##  1 Introduction

In this contribution, we consider optimization problems with an expected-
valued cost function, i.e.,

$\min_{u\in\mathcal{U}}\;\int_{\mathcal{X}}j(u,x)\mu(\mathrm{d}x),$ (1)

with an admissible set $\mathcal{U}$, a parameter set $\mathcal{X}$, $j\in
C^{1}(\mathcal{U}\times\mathcal{X};\mathbb{R})$ and a (probability) measure
$\mu$. Such problems arise naturally in the context of machine learning and
noisy simulations Intro01 ; Intro04 . They also appear in other large scale
optimization problems, such as topology or shape optimization, where one is
interested in a design that is optimal for a continuous spectrum of outer
parameters, e.g. Intro02 ; Intro03 ; semmler2015shape . One usually does not
consider deterministic approaches for the solution of this type of problems,
as they are generally too computationally expensive or even intractable.
Instead, one uses stochastic optimization schemes like stochastic gradient
descent (SG) Monro1951  or stochastic average gradient descent (SAG)
LeRoux2017 , to name the most prominent examples.

The continuous stochastic gradient descent (CSG) method, recently proposed in
pflug_CSG , shares properties with both, stochastic, as well as full gradient
methods. Contrary to SG, in CSG the gradient samples
$\nabla_{1}j(u_{n},x_{n})$ and objective functional samples $j(u_{n},x_{n})$
drawn in the $n$-th iteration are not discarded after each iteration. Instead,
a tailored convex combination of said samples is used, in order to obtain an
approximation of the full gradient and the objective function value. In
pflug2021csg , several methods of obtaining the weights of this convex
combination were presented and analyzed in an even more general setting than
(1). The results presented in this contribution can also be generalized in the
same fashion. However, for the sake of readability and since our focus lies on
step size rules instead, we consider only problems of the form (1) and refer
to (pflug2021csg, , Remark 2.3) for further details.

A key advantage of CSG against most stochastic optimization methods is that
the approximation error in both the gradient and the objective function
converges to 0 during the optimization process (Lemma 6), which has already
been shown for diminishing step sizes in (pflug2021csg, , Theorem 4.7). Thus,
in the course of the iterations, CSG more and more behaves like a full
gradient descent algorithm. Therefore, the question which convergence
properties of gradient descent carry over to CSG, arises naturally. Special
interest lies in the known disadvantages of SG-type methods, like the lack of
efficient stopping criteria (cf. Patel2016 ) and an advanced choice of step
sizes, or learning rate, as it is often called in the machine learning
context.

While stopping criteria based on approximate first order conditions are rather
straight-forward to implement thanks to Lemma 6, we want to further discuss
the step size dependency of SG methods. In most cases, finding an optimal step
size requires knowledge of properties of the function which are usually not
available. On the other hand, simpler step size rules, like constant step
sizes, come with very strict assumptions with respect to (1). As an example,
linear convergence rates for strongly convex objective functions with a finite
sum structure (discrete measure $\mu$ in (1)) were proven under the proposed
strong growth condition in (StrongGrowthCondition, , Section 6). However, this
condition is (as stated by the authors) not satisfied in most applications, as
it requires any optimal solution of (1) to be stationary for each individual
component of the objective function. An overview of different convergence
results for adaptive or fixed step size rules can be found in Steps01 ;
Steps02 ; lacostejulien2012simpler ; Paquette2020 ; Polyak2021 ; Tan2016  and
the references therein.

In this contribution, we show that CSG is able to work with step size rules
known from classical deterministic optimization methods. We prove that every
accumulation point of the sequence generated by CSG carried out with a
sufficiently small constant step size is a stationary point of (1) and that
the sequence in fact converges for non-pathological (see Remark 3) cases.

Furthermore, we introduce a backtracking Armijo-type line search based on
gradient and objective function approximations and prove that this yields the
same convergence results as for the constant step sizes mentioned above. Thus,
the resulting optimization method is widely independent of the step size rule.

Before going into detail, we want to state an informal version of the
convergence results established later in this work. The full set of
assumptions can be found in in Section 2.1 and the main convergence results
are given in Theorem 3.1, Theorem 3.2 and Theorem 4.1.

###### Main Result

Assume that the objective function in (1) has a Lipschitz continuous gradient
and is not chosen as a pathological counter example.

Then every accumulation point of the sequence generated by CSG with
sufficiently small constant step size or backtracking line search is
stationary. Moreover, we obtain convergence in the objective function values.

### Structure of the paper

In Section 2, we introduce the quantities appearing in (1) and our needed
assumptions in detail. Additionally, we provide auxiliary results for later
sections. Section 3 contains our convergence results for CSG used with
constant step sizes. In Section 4, we introduce CSG with a backtracking scheme
and provide convergence results for this method. In Section 5 a heuristic
scheme to approximate the needed Lipschitz constant is presented. Lastly, in
Section 6, we document numerical experiments that analyze the stability of the
new CSG versions. Furthermore, we combine backtracking CSG with the heuristic
scheme to approximate the Lipschitz constant to obtain a method that does not
require any step size rule at all and test the stability of this algorithm for
different problems.

##  2 Assumptions And Auxiliary Results

In this section, we introduce our general setting and formulate the
assumptions we make throughout this contribution. Additionally, the basic CSG
algorithm is presented and some preliminary results are stated.

###  2.1 Setting

######  Definition 1 (Objective function)

For ${d_{\textnormal{o}}},{d_{\textnormal{r}}}\in\mathbb{N}$, we introduce the
set of admissible optimization variables
$\mathcal{U}\subset\mathbb{R}^{d_{\textnormal{o}}}$ and the parameter set
$\mathcal{X}\subset\mathbb{R}^{d_{\textnormal{r}}}$. The objective function
$J:\mathcal{U}\to\mathbb{R}$ is then given by

$J(u):=\mathbb{E}\left[j(u,X)\right]=\int_{\mathcal{X}}j(u,x)\mu(\mathrm{d}x),$

where we assume $j\in C^{1}(\mathcal{U}\times\mathcal{X}\,;\,\mathbb{R})$ to
be measurable and $X\sim\mu$.

Since $\mathcal{U}$ and $\mathcal{X}$ are finite dimensional, we do not have
to consider specific norms on these spaces and can instead choose them problem
specific. In the following, we will denote them simply by
$\|\cdot\|_{\mathcal{U}}$ and $\|\cdot\|_{\mathcal{X}}$.

During the optimization, we need to draw random samples of the random variable
$X$. As stated in the following assumption, we need the sequence of samples
$(x_{n})_{n\in\mathbb{N}}\subset\mathcal{X}$ to be dense in
$\operatorname{supp}(\mu)$. This, however, is automatically satisfied with
probability 1, as can be seen in Remark 1.

######  Assumption 2.1 (Sample sequence)

The sequence $(x_{n})_{n\in\mathbb{N}}$ is dense in
$\operatorname{supp}(\mu)$, where

$\operatorname{supp}(\mu):=\left\\{x\in\mathcal{X}\,:\,\mu\left(\mathcal{B}_{\varepsilon}(x)\right)>0\text{
for all }\varepsilon>0\right\\}.$

Here, $\mathcal{B}_{\varepsilon}(x)$ denotes the open ball with radius
$\varepsilon>0$ centered at $x\in\mathcal{X}$ and $(x_{n})_{n\in\mathbb{N}}$
is a sequence of independent identically distributed realizations of the
random variable $X\sim\mu$.

Notice that $\operatorname{supp}(\mu)$ is a closed subset of
$\mathbb{R}^{d_{\textnormal{r}}}$.

###### Remark 1

Let $x\in\operatorname{supp}(\mu)$ and $\varepsilon>0$. Then, given an
independent identically distributed sequence $x_{1},x_{2},\ldots\sim\mu$, we
have

$\mathbb{P}\big{(}x_{n}\not\in\mathcal{B}_{\varepsilon}(x)\big{)}=1-\mu(\mathcal{B}_{\varepsilon}(x))<1.$

Hence, by the Borel-Cantelli Lemma (klenke2013probability, , Theorem 2.7),

$\mathbb{P}\big{(}x_{n}\not\in\mathcal{B}_{\varepsilon}(x)\text{ for all
}n\in\mathbb{N}\big{)}=0.$

Thus, the sequence $(x_{n})_{n\in\mathbb{N}}$ is dense in
$\operatorname{supp}(\mu)$ with probability 1.

As for the original CSG method, the sets $\mathcal{U}$ and $\mathcal{X}$ need
to satisfy the following regularity conditions, compare (pflug2021csg, ,
Assumption 2.7):

######  Assumption 2.2 (Regularity of $\mathcal{U}$, $\mathcal{X}$ and $\mu$)

The set $\mathcal{U}\subset\mathbb{R}^{d_{\textnormal{o}}}$ is compact and
convex. The set $\mathcal{X}\subset\mathbb{R}^{d_{\textnormal{r}}}$ is open
and bounded with $\operatorname{supp}(\mu)\subset\mathcal{X}$. This can always
be achieved, as long as
$\operatorname{supp}(\mu)\subset\mathbb{R}^{d_{\textnormal{r}}}$ is bounded.

Finally, as in the deterministic case, we assume the gradient of the objective
function to be Lipschitz continuous, in order to obtain convergence for
constant step sizes.

######  Assumption 2.3 (Regularity of $\nabla J$)

$J:\mathcal{U}\to\mathbb{R}$ is $L$-smooth, i.e., there exists $L>0$ such that

$\left\|\nabla J(u_{1})-\nabla J(u_{2})\right\|_{\mathcal{U}}\leq
L\|u_{1}-u_{2}\|_{\mathcal{U}}\quad\text{for all }u_{1},u_{2}\in\mathcal{U}.$

Algorithm 1 General CSG method

1: while Termination condition not met do

2: Sample objective function (optional):$\quad j_{n}:=j(u_{n},x_{n})$

3: Sample gradient:$\quad g_{n}:=\nabla_{1}j(u_{n},x_{n})$

4: Calculate weights $\alpha_{k}$

5: Calculate search
direction:$\quad\hat{G}_{n}:=\sum_{k=1}^{n}\alpha_{k}g_{k}\vphantom{\Big{(}}$

6: Compute objective function value approximation
(optional):$\quad\hat{J}_{n}:=\sum_{k=1}^{n}\alpha_{k}j_{k}\vphantom{\Big{(}}$

7: Choose stepsize $\tau_{n}$

8: Gradient step:$\quad
u_{n+1}:=\mathcal{P}_{\mathcal{U}}\big{(}u_{n}-\tau_{n}\hat{G}_{n}\big{)}\vphantom{\Big{(}}$

9: Update index:$\quad n\leftarrow n+1\vphantom{\Big{(}}$

10: end while

The general CSG method was first proposed in pflug_CSG  and can be used to
solve problems of the form (1). Additional information regarding convergence
results and the weight calculation mentioned in Step 4 can be found in
pflug2021csg . We note that the results presented in this contribution can, as
proposed in pflug2021csg , be generalized to a wider class of problems than
(1). However, in this work, we want to focus solely on step sizes rules and
therefore work only in the simpler setting (1).

###  2.2 The CSG Algorithm

For a given starting point $u_{1}\in\mathcal{U}$ and a sample sequence
$x_{1},x_{2},\ldots$ as stated in Assumption 2.1, the general CSG algorithm
was introduced in pflug_CSG  and is stated in Algorithm 1. In (pflug2021csg, ,
Section 3.1) it was thoroughly analyzed how the computation of the weights
(Step 4) can be carried out.

In Step 8, $\mathcal{P}_{\mathcal{U}}$ denotes the orthogonal projection (in
the sense of $\|\cdot\|_{\mathcal{U}})$, i.e.,

$\mathcal{P}_{\mathcal{U}}(u):=\operatorname*{arg\,min}_{\bar{u}\in\mathcal{U}}\|u-\bar{u}\|_{\mathcal{U}}.$

We will later show that the CSG method converges to stationary points, which
we define next.

######  Definition 2 (Stationary points)

Let $J\in C^{1}(\mathcal{U})$ be given. We say $u^{\ast}\in\mathcal{U}$ is a
stationary point of $J$, if there exists $t>0$ such that

$\mathcal{P}_{\mathcal{U}}\left(u^{\ast}-t\nabla J(u^{\ast})\right)=u^{\ast}.$

Furthermore, we denote by

$\mathcal{S}(J):=\left\\{u\in\mathcal{U}\,:\,\mathcal{P}_{\mathcal{U}}\left(u-t\nabla
J(u)\right)=u\text{ for some }t>0\right\\}$

the set of all stationary points of $J$.

###  2.3 Auxiliary Results

Gradient descent methods for $L$-smooth objective functions have thoroughly
been studied in the past (e.g. ProjGradientGoldstein ; ProjGradientRates ).
The key ingredients for obtaining convergence results with constant step sizes
are the descent lemma and the characteristic property of the projection
operator, which we state in the following.

######  Lemma 1 (Descent Lemma)

If $J:\mathcal{U}\to\mathbb{R}$ is $L$-smooth, then it holds

$J(u_{1})\leq J(u_{2})+\nabla
J(u_{2})^{\top}(u_{1}-u_{2})+\frac{L}{2}\|u_{1}-u_{2}\|^{2}\quad\forall
u_{1},u_{2}\in\mathcal{U}.$

######  Lemma 2 (Characteristic Property of Projection)

If $u_{n+1}=\mathcal{P}_{\mathcal{U}}(u_{n}-\tau_{n}\hat{G}_{n})$, then

$\hat{G}_{n}^{\top}(u_{n}-u_{n+1})\geq\frac{\|u_{n}-u_{n+1}\|^{2}}{\tau_{n}}.$

###### Proof

Lemma 1 corresponds to (DescentUndProjection, , Lemma 5.7). Lemma 2 is a
direct consequence of (DescentUndProjection, , Theorem 6.41).∎

Before we move on to results that are specific for the CSG method, we state a
general convergence result, which will be helpful in the later proofs.

######  Lemma 3 (Finitely many accumulation points)

Let $(u_{n})_{n\in\mathbb{N}}\subset\mathbb{R}^{d}$ be a bounded sequence.
Suppose that $(u_{n})_{n\in\mathbb{N}}$ has only finitely many accumulation
points and it holds $\|u_{n+1}-u_{n}\|\to 0$. Then $(u_{n})_{n\in\mathbb{N}}$
is convergent.

###### Proof

Let $\left\\{\bar{u}_{1},\ldots,\bar{u}_{K}\right\\}$ be the accumulation
points of $(u_{n})_{n\in\mathbb{N}}$ and define

$\delta_{0}:=\min_{\begin{subarray}{c}i,j\in\\{1,\ldots,K\\}\\\ i\neq
j\end{subarray}}\|\bar{u}_{i}-\bar{u}_{j}\|,$

i.e, the minimal distance between two accumulation points of
$(u_{n})_{n\in\mathbb{N}}$. The accumulation point closest to $u_{n}$ is
defined as:

$\bar{u}(n):=\operatorname*{arg\,min}_{u\in\\{\bar{u}_{1},\ldots,\bar{u}_{K}\\}}\|u_{n}-u\|.$

Next up, we show that there exists $N\in\mathbb{N}$ such that for all $n\geq
N$ it holds $\|u_{n}-\bar{u}(n)\|<\tfrac{\delta_{0}}{4}$. We prove this by
contradiction.

Thus, we assume there exist infinitely many $n\in\mathbb{N}$ such that
$\|u_{n}-\bar{u}(n)\|\geq\tfrac{\delta_{0}}{4}$. This subsequence is again
bounded and therefore must have an accumulation point. By construction, this
accumulation point is no accumulation point of $(u_{n})_{n\in\mathbb{N}}$,
which is a contradiction.

Now, let $N_{1}\in\mathbb{N}$ be large enough such that
$\|u_{n}-\bar{u}(n)\|<\tfrac{\delta_{0}}{4}$ for all $n\geq N_{1}$. By our
assumptions, there also exists $N_{2}\in\mathbb{N}$ with
$\|u_{n+1}-u_{n}\|<\tfrac{\delta_{0}}{4}$ for all $n\geq N_{2}$. Define
$N:=\max\\{N_{1},N_{2}\\}$.

Assume $n\geq N$ and $\bar{u}(n)\neq\bar{u}(n+1)$ we obtain

$\text{dist}\big{(}\mathcal{B}_{\delta_{0}/4}(\bar{u}(n))\,,\,\mathcal{B}_{\delta_{0}/4}(\bar{u}(n+1))\big{)}\geq\tfrac{\delta_{0}}{2}>\tfrac{\delta_{0}}{4}>\|u_{n}-u_{n+1}\|\quad\text{for
all }n\geq N,$

where $\operatorname{dist}(A,B):=\inf_{x\in A,y\in B}\|x-y\|$ for
$A,B\subset\mathbb{R}^{d}$. This is a contradiction to
$\|u_{n+1}-u_{n}\|<\tfrac{\delta_{0}}{4}$ for all $n\geq N$.

We thus conclude that
$u_{n}\in\mathcal{B}_{\frac{\delta_{0}}{4}}\big{(}\bar{u}(n)\big{)}$ implies
$u_{n+1}\in\mathcal{B}_{\frac{\delta_{0}}{4}}\big{(}\bar{u}(n)\big{)}$ as
well. Since $\bar{u}(n)$ is the only accumulation point on
$\mathcal{B}_{\frac{\delta_{0}}{4}}\big{(}\bar{u}(n)\big{)}$, it follows that
$u_{n}\to\bar{u}(N)$.∎

###  2.4 Results for CSG approximations

From now on, let $(u_{n})_{n\in\mathbb{N}}$ denote the sequence of iterates
generated by Algorithm 1. In this section, we want to show that the CSG
approximations $\hat{J}_{n}$ and $\hat{G}_{n}$ in the course of iterations
approach the values of $J(u_{n})$ and $\nabla J(u_{n})$, respectively. While
this has already been shown for diminishing step sizes in (pflug2021csg, ,
Theorem 4.7), here, for the first time, a proof for constant step sizes is
provided. This is a key result for the convergence theorems stated in Section
3 and Section 4.

######  Lemma 4 (Density result in $\mathcal{X}$)

Let $(x_{n})_{n\in\mathbb{N}}$ be the random sequence appearing in Algorithm
1. For all ${\varepsilon}>0$ there exists $N\in\mathbb{N}$ such that

$\min_{n\in\\{1,\ldots,N\\}}\|x_{n}-x\|_{{}_{\mathcal{X}}}<{\varepsilon}\quad\text{for
all }x\in\operatorname{supp}(\mu).$

###### Proof

Utilizing the compactness of
$\operatorname{supp}(\mu)\subset\mathbb{R}^{d_{\textnormal{r}}}$, there exists
$T\in\mathbb{N}$ such that
$\left(\mathcal{B}_{{\varepsilon}/2}(m_{i})\right)_{i=1,\ldots,T}$ is an open
cover of $\operatorname{supp}(\mu)$ consisting of balls with radius
$\frac{{\varepsilon}}{2}$ centered at points
$m_{i}\in\operatorname{supp}(\mu)$. Thus, for each
$x\in\operatorname{supp}(\mu)$ we can find $i_{x}\in\\{1,\ldots,T\\}$ with
$x\in\mathcal{B}_{{\varepsilon}/2}(m_{i_{x}})$. Hence, by Assumption 2.1, for
each $i=1,\ldots,T$, there exists $n_{i}\in\mathbb{N}$ satisfying

$\|x_{n_{i}}-m_{i}\|_{{}_{\mathcal{X}}}<\tfrac{{\varepsilon}}{2}.$

Defining

$N:=\max_{i\in\\{1,\ldots,T\\}}n_{i}<\infty,$

for all $x\in\operatorname{supp}(\mu)$ we have

$\displaystyle\min_{n\in\\{1,\ldots,N\\}}\|x-x_{n}\|_{{}_{\mathcal{X}}}$
$\displaystyle\leq\min_{n\in\\{1,\ldots,N\\}}\big{(}\|x-m_{i_{x}}\|_{{}_{\mathcal{X}}}+\|m_{i_{x}}-x_{n}\|_{{}_{\mathcal{X}}}\big{)}$
$\displaystyle<\tfrac{{\varepsilon}}{2}+\min_{n\in\\{1,\ldots,N\\}}\|m_{i_{x}}-x_{n}\|_{{}_{\mathcal{X}}}<\tfrac{{\varepsilon}}{2}+\tfrac{{\varepsilon}}{2}={\varepsilon}.$

∎

######  Lemma 5 (Density result in $\mathcal{U}\times\mathcal{X}$)

Let $(u_{n})_{n\in\mathbb{N}}$, $(x_{n})_{n\in\mathbb{N}}$ be the sequences of
optimization variables and sample sequence appearing in Algorithm 1. For all
${\varepsilon}>0$ there exists $N\in\mathbb{N}$ such that

$Z_{n}(x):=\min_{k\in\\{1,\ldots,n\\}}\big{(}\|u_{n}-u_{k}\|_{{}_{\mathcal{U}}}+\|x-x_{k}\|_{{}_{\mathcal{X}}}\big{)}<{\varepsilon}$

for all $n>N$ and all $x\in\operatorname{supp}(\mu)$.

###### Proof

Since $\mathcal{U}$ is compact, we can find a finite cover
$\left(\mathcal{B}_{{\varepsilon}/4}(m_{i})\right)_{i=1,\ldots,T}$ of
$\mathcal{U}$ consisting of $T\in\mathbb{N}$ balls with radius
$\frac{{\varepsilon}}{4}$ centered at points $m_{i}\in\mathcal{U}$. Define
$I\subset\\{1,\ldots,T\\}$ as

$I:=\big{\\{}i\in\\{1,\ldots,T\\}\,:\,u_{n}\in\mathcal{B}_{{\varepsilon}/4}(m_{i})\text{
for infinitely many }n\in\mathbb{N}\big{\\}}.$

By our definition of $I$, for each $i\in\\{1,\ldots,T\\}\setminus I$ there
exists $\tilde{N}_{i}\in\mathbb{N}$ such that
${u_{n}\not\in\mathcal{B}_{{\varepsilon}/4}(m_{i})}$ for all
$n>\tilde{N}_{i}$. Setting

$N_{1}:=\max_{i\in\\{1,\ldots,T\\}\setminus I}\tilde{N}_{i},$

it follows that

$u_{x}\not\in\mathcal{B}_{{\varepsilon}/4}(m_{i})\text{ for each $n>N_{1}$ and
all $i\in\\{1,\ldots,T\\}\setminus I$.}$ (2)

For $i\in I$ let $\big{(}u_{n^{(i)}_{t}}\big{)}_{t\in\mathbb{N}}$ be the
subsequence consisting of all elements of $(u_{n})_{n\in\mathbb{N}}$ that lie
in $\mathcal{B}_{{\varepsilon}/4}(m_{i})$. Since $(x_{n})_{n\in\mathbb{N}}$ is
i.i.d. and dense in $\operatorname{supp}(\mu)$, so is
$\big{(}x_{n^{(i)}_{t}}\big{)}_{t\in\mathbb{N}}$. By Lemma 4, we can find
$K_{i}\in\mathbb{N}$ such that

$\min_{t\in\\{1,\ldots,K_{i}\\}}\big{\|}x-x_{n^{(i)}_{t}}\big{\|}_{{}_{\mathcal{X}}}<\tfrac{{\varepsilon}}{2}\quad\text{
for all }x\in\operatorname{supp}(\mu).$ (3)

Define

$N_{2}:=\max_{i\in I}\max_{t\in\\{1,\ldots,K_{i}\\}}n^{(i)}_{t}$

as well as $N:=\max(N_{1},N_{2})$. By (2), for all $n>N$ there exists $i\in I$
such that

$\|u_{n}-m_{i}\|_{{}_{\mathcal{U}}}<\tfrac{{\varepsilon}}{4}.$ (4)

Now, for every $x\in\operatorname{supp}(\mu)$ and all $n>N$ it holds

$\displaystyle Z_{n}(x)$
$\displaystyle=\min_{k\in\\{1,\ldots,n\\}}\big{(}\|u_{n}-u_{k}\|_{{}_{\mathcal{U}}}+\|x-x_{k}\|_{{}_{\mathcal{X}}}\big{)}$
$\displaystyle\leq\min_{t\in\\{1,\ldots,K_{i}\\}}\Big{(}\big{\|}u_{n}-u_{n^{(i)}_{t}}\big{\|}_{{}_{\mathcal{U}}}+\big{\|}x-x_{n^{(i)}_{t}}\big{\|}_{{}_{\mathcal{X}}}\Big{)}$
$\displaystyle\leq\min_{t\in\\{1,\ldots,K_{i}\\}}\Big{(}\|u_{n}-m_{i}\|_{{}_{\mathcal{U}}}+\big{\|}m_{i}-u_{n^{(i)}_{t}}\big{\|}_{{}_{\mathcal{U}}}+\big{\|}x-x_{n^{(i)}_{t}}\big{\|}_{{}_{\mathcal{X}}}\Big{)}$
$\displaystyle<\tfrac{{\varepsilon}}{4}+\tfrac{{\varepsilon}}{4}+\tfrac{{\varepsilon}}{2}={\varepsilon},$

where we used (3), (4) and
$u_{n^{(i)}_{t}}\in\mathcal{B}_{{\varepsilon}/4}(m_{i})$ in the last line.∎

######  Lemma 6 (Approximation results for $J$ and $\nabla J$)

For all ${\varepsilon}>0$ there exists $N\in\mathbb{N}$ such that

$\left\|\hat{G}_{n}-\nabla
J(u_{n})\right\|<{\varepsilon}\quad\text{and}\quad\left\|\hat{J}_{n}-J(u_{n})\right\|<{\varepsilon}\qquad\text{for
all }n>N$

###### Proof

In pflug2021csg  it was shown that

$\left\|\hat{G}_{n}-\nabla J(u_{n})\right\|\leq
L\left(\frac{1}{n}\sum_{i=1}^{n}Z_{n}(x_{i})+d_{W}(\mu_{n},\mu)\right),$

where $d_{W}(\mu_{n},\mu)$ denotes the Wasserstein distance of the measure
$\mu_{n}$ and $\mu$ (see gibbs2002choosing ). Since $d_{W}(\mu_{n},\mu)\to 0$
(e.g., (EmpiricalDistrPaper, , Theorem 3)), there is $n_{2}\in\mathbb{N}$
satisfying

$d_{W}(\mu_{n},\mu)<\tfrac{{\varepsilon}}{2L}\quad\text{for all }n>N_{2}.$

By Lemma 5, we can also find $N_{1}\in\mathbb{N}$ such that

$Z_{n}(x)<\tfrac{{\varepsilon}}{2L}\quad\text{for all
}x\in\operatorname{supp}(\mu)\text{ and all }n>N_{1}.$

Combining the results above yields

$\left\|\hat{G}_{n}-\nabla J(u_{n})\right\|<{\varepsilon}\quad\text{for all
}n>N:=\max(N_{1},N_{2}).$

By replacing $L$ with the Lipschitz constant of $J$, the same steps as above
yield the second part of the claim.∎

##  3 Convergence Results For Constant Stepsize

In this section, we assume Assumptions 2.1, 2.2 and 2.3 to be satisfied. Our
first result considers the special case in which the objective function $J$
appearing in (1) has only finitely many stationary points on $\mathcal{U}$.
The proof of this result serves as a prototype for the later convergence
results, as they share a common idea.

######  Theorem 3.1 (Convergence for constant steps)

Assume that $J$ has only finitely many stationary points on $\mathcal{U}$.

Then CSG with a positive constant stepsize $\tau_{n}=\tau<\tfrac{2}{L}$
converges to a stationary point of $J$.

We want to sketch the proof of Theorem 3.1, before going into details. In the
deterministic case, Lemma 1 and Lemma 2 are used to show that ${J(u_{n+1})\leq
J(u_{n})}$ for all $n\in\mathbb{N}$. It then follows from a telescopic sum
argument that $\|u_{n+1}-u_{n}\|\to 0$, i.e., every accumulation point of
$(u_{n})_{n\in\mathbb{N}}$ is stationary (compare (ProjGradientRates, ,
Theorem 5.1) or (DescentUndProjection, , Theorem 10.15)).

In the case of CSG, we can not guarantee monotonicity of the objective
function values $(J(u_{n}))_{n\in\mathbb{N}}$. Instead, we split the sequence
into two subsequences. On one of these subsequences, we can guarantee a
decrease in function values, while for the other sequence we can not. However,
we prove that the latter sequence can accumulate only at stationary points of
$J$. The main idea is then that $(u_{n})_{n\in\mathbb{N}}$ can have only one
accumulation point, because “switching” between several points conflicts with
the decrease in function values that must happen for steps in between.

######  Proof (of Theorem 3.1)

By Lemma 1 we have

$\displaystyle J(u_{n+1})-J(u_{n})\leq\nabla
J(u_{n})^{\top}\left(u_{n+1}-u_{n}\right)+\tfrac{L}{2}\|u_{n+1}-u_{n}\|^{2}$
$\displaystyle\qquad=\hat{G}_{n}^{\top}\left(u_{n+1}-u_{n}\right)+\tfrac{L}{2}\|u_{n+1}-u_{n}\|^{2}+\left(\nabla
J(u_{n})-\hat{G}_{n}\right)^{\top}\left(u_{n+1}-u_{n}\right).$

Utilizing Lemma 2 and the Cauchy-Schwarz inequality, we now obtain

$\displaystyle J(u_{n+1}$ $\displaystyle)-J(u_{n})$
$\displaystyle\leq\left(\tfrac{L}{2}-\tfrac{1}{\tau}\right)\|u_{n+1}-u_{n}\|^{2}+\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|\cdot\|u_{n+1}-u_{n}\|$
$\displaystyle=\left(\left(\tfrac{L}{2}-\tfrac{1}{\tau}\right)\|u_{n+1}-u_{n}\|+\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|\right)\|u_{n+1}-u_{n}\|.$ (5)

Since $\frac{L}{2}-\frac{1}{\tau}<0$, our idea is the following:

Steps that satisfy

$\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|\leq\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{n+1}-u_{n}\|,$
(6)

i.e., steps with small errors in the gradient approximation, will yield
decreasing function values.

On the other hand, the remaining steps will satisfy $\|u_{n+1}-u_{n}\|\to 0$,
due to $\|\nabla J(u_{n})-\hat{G}_{n}\|\to 0$ (see Lemma 6). With this in
mind, we distinguish three cases: In Case 1, (6) is satisfied for almost all
steps, while in Case 2 it is satisfied for only finitely many steps. In the
last case, there are infinitely many steps satisfying and infinitely many
steps violating (6).

Case 1:

There exists $N\in\mathbb{N}$ such that

$\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|\leq\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{n+1}-u_{n}\|\quad\text{for
all }n\geq N.$

In this case, it follows from (5) that $J(u_{n+1})\leq J(u_{n})$ for all
$n\geq N$. Therefore, the sequence $(J(u_{n}))_{n\in\mathbb{N}}$ is
monotonically decreasing for almost every $n\in\mathbb{N}$. Since $J$ is
continuous and $\mathcal{U}$ is compact, $J$ is bounded and we therefore have
${J(u_{n})\to\bar{J}\in\mathbb{R}}$. Thus, it holds

$-\infty<\bar{J}-J(u_{N})=\sum_{n=N}^{\infty}\big{(}J(u_{n+1}-J(u_{n})\big{)}\leq\tfrac{1}{2}\left(\tfrac{L}{2}-\tfrac{1}{\tau}\right)\sum_{n=N}^{\infty}\|u_{n+1}-u_{n}\|^{2}.$

Since $\frac{1}{2}\left(\frac{L}{2}-\frac{1}{\tau}\right)<0$, we must have
$\|u_{n+1}-u_{n}\|\to 0$. Let $\left(u_{n_{k}}\right)_{k\in\mathbb{N}}$ be a
convergent subsequence with $u_{n_{k}}\to\overline{u}\in\mathcal{U}$.

By Lemma 6, we have $\hat{G}_{n_{k}}\to\nabla J(\overline{u})$ and thus

$\displaystyle 0$ $\displaystyle=\lim_{k\to\infty}\|u_{n_{k}+1}-u_{n_{k}}\|$
$\displaystyle=\lim_{k\to\infty}\left\|\mathcal{P}_{\mathcal{U}}\big{(}u_{n_{k}}-\tau\nabla\hat{G}_{n_{k}}\big{)}-u_{n_{k}}\right\|$
$\displaystyle=\left\|\mathcal{P}_{\mathcal{U}}\big{(}\overline{u}-\tau\nabla
J(\overline{u})\big{)}-\overline{u}\right\|,$

i.e., every accumulation point of $(u_{n})_{n\in\mathbb{N}}$ is stationary.
Since $J$ has only finitely many stationary points, Lemma 3 yields the
convergence of $(u_{n})_{n\in\mathbb{N}}$ to a stationary point of $J$.

Case 2:

There exists $N\in\mathbb{N}$ such that

$\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|>\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{n+1}-u_{n}\|\quad\text{for
all }n\geq N.$

By Lemma 6, we have $\|\nabla J(u_{n})-\hat{G}_{n}\|\to 0$. Since
$\frac{1}{2}\left(\frac{1}{\tau}-\frac{L}{2}\right)>0$, the above inequality
directly implies $\|u_{n+1}-u_{n}\|\to 0$. Analogously to Case 1, we conclude
that $(u_{n})_{n\in\mathbb{N}}$ converges to a stationary point of $J$.

Case 3:

There are infinitely many $n\in\mathbb{N}$ with

$\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|\leq\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{n+1}-u_{n}\|$

and infinitely many $n\in\mathbb{N}$ with

$\left\|\nabla
J(u_{n})-\hat{G}_{n}\right\|>\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{n+1}-u_{n}\|.$

In this case, we split $(u_{n})_{n\in\mathbb{N}}$ disjointly in the two
sequences $(u_{a(n)})_{n\in\mathbb{N}}$ and $(u_{b(n)})_{n\in\mathbb{N}}$,
such that we have

$\left\|\nabla
J(u_{a(n)})-\hat{G}_{a(n)}\right\|\leq\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{a(n)+1}-u_{a(n)}\|\quad\text{for
all }n\in\mathbb{N}$

and

$\left\|\nabla
J(u_{b(n)})-\hat{G}_{b(n)}\right\|>\tfrac{1}{2}\left(\tfrac{1}{\tau}-\tfrac{L}{2}\right)\|u_{b(n)+1}-u_{b(n)}\|\quad\text{for
all }n\in\mathbb{N}.$

We call $(u_{a(n)})_{n\in\mathbb{N}}$ the sequence of descent steps. For
$(u_{b(n)})_{n\in\mathbb{N}}$, observe that, as in Case 2, we directly obtain

$\|u_{b(n)+1}-u_{b(n)}\|\to 0$ (7)

and every accumulation point of $(u_{b(n)})_{n\in\mathbb{N}}$ is stationary.
Therefore, as in the proof of Lemma 3, for all $\varepsilon>0$ there exists
$N\in\mathbb{N}$ such that

$\min_{i\in\\{1,\ldots,K\\}}\|u_{b(n)}-\overline{u}_{i}\|<\varepsilon\quad\text{for
all }n\geq N,$ (8)

where $\overline{u}_{1},\ldots,\overline{u}_{K}$ denote the $K\in\mathbb{N}$
accumulation points of $(u_{b(n)})_{n\in\mathbb{N}}$.

Now, we prove by contradiction that
$J(\overline{u}_{1})=J(\overline{u}_{2})=\ldots=J(\overline{u}_{K})$.

Suppose that this is not the case. Then we have at least $M\geq 2$ function
values of accumulation points and

$F:=\left\\{J(u)\,:\,u=\overline{u}_{1},\ldots,\overline{u}_{K}\right\\}=\\{f_{1},f_{2},\ldots,f_{M}\\}$

for some $f_{1}>f_{2}>\ldots>f_{M}\in\mathbb{R}$. Now, choose $\varepsilon>0$
small enough, such that

$2\varepsilon<\min_{\begin{subarray}{c}i,j\in\\{1,\ldots,K\\}\\\ i\neq
j\end{subarray}}\|\bar{u}_{i}-\bar{u}_{j}\|\quad\text{and}\quad
c_{{}_{L}}\varepsilon<f_{1}-f_{2},$

where $c_{{}_{L}}$ denotes the Lipschitz constant of $J$. By (7) and (8),
there exists $N\in\mathbb{N}$ such that for all $n\geq N$ we have

$\|u_{b(n)+1}-u_{b(n)}\|<\tfrac{\varepsilon}{4}\quad\text{and}\quad\min_{i\in\\{1,\ldots,K\\}}\|u_{b(n)}-\overline{u}_{i}\|<\tfrac{\varepsilon}{4}.$
(9)

Therefore, for $n\geq N$ and $i\in\\{1,\ldots,K\\}$, we have

$\displaystyle
u_{b(n)}\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})\;$
$\displaystyle\Longrightarrow\;u_{b(n)+1}\in\mathcal{B}_{\frac{\varepsilon}{2}}(\overline{u}_{i})$
(10)
$\displaystyle\Longrightarrow\;u_{b(n)+1}\not\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{j})\text{
for all $j\neq i$.}$ (11)

Especially, for all $n\geq N$ it holds

$u_{b(n)}\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})\;\Longrightarrow\;J(u_{b(n)+1})\leq
J(\overline{u}_{i})+\tfrac{c_{{}_{L}}\varepsilon}{2}\quad\text{for all
$i=1,\ldots,K$.}$ (12)

It follows from (9) and (11) that for $n\geq N+1$:

(A)

If $u_{b(n)}\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})$ and
$u_{b(n+1)}\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{j})$ for some
$j\neq i$, then there must be at least one descent step between $u_{b(n)}$ and
$u_{b(n+1)}$.

(B)

If $u_{b(n)}\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})$ and
$u_{b(n)-1}\not\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})$, then
$u_{b(n)-1}$ must be a descent step.

Observe that (A) follows directly from (9) and (11), as moving from the
vicinity of $\overline{u}_{i}$ to a neighborhood of $\overline{u}_{j}$
requires that there is an intermediate step $u_{n}$ with
$\min_{i\in\\{1,\ldots,K\\}}\|u_{b(n)}-\overline{u}_{i}\|\geq\tfrac{\varepsilon}{4}$.
Similarly, (B) is just the second condition in (11) reformulated.

Now, let $i\in\\{1,\ldots,K\\}$ be chosen such that $J(\overline{u}_{i})\leq
f_{2}$ and let $n_{0}\geq N$ be chosen such that
$u_{b(n_{0})}\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})$ and
$u_{b(n_{0})+1}\not\in\mathcal{B}_{\frac{\varepsilon}{4}}(\overline{u}_{i})$.
Using (10) and (12), we obtain

$\displaystyle J(u_{b(n_{0})+1})$ $\displaystyle\leq
J(\overline{u}_{i})+\frac{c_{{}_{L}}\varepsilon}{2}$ $\displaystyle\leq
f_{2}+\frac{c_{{}_{L}}\varepsilon}{2}$
$\displaystyle<f_{1}-\frac{c_{{}_{L}}\varepsilon}{2}$
$\displaystyle<J(u)\quad\text{for all
}u\in\mathcal{B}_{\frac{\varepsilon}{4}}\left(J^{-1}(\\{f_{1}\\})\cap\\{\overline{u}_{1},\ldots,\overline{u}_{K}\\}\right).$

Therefore, descent steps can never reach
$\mathcal{B}_{\frac{\varepsilon}{4}}\left(J^{-1}(\\{f_{1}\\}\cap\\{\overline{u}_{1},\ldots,\overline{u}_{K}\\})\right)$
again! It follows from item (B), that
$u_{n}\not\in\mathcal{B}_{\frac{\varepsilon}{4}}\left(J^{-1}(\\{f_{1}\\})\cap\\{\overline{u}_{1},\ldots,\overline{u}_{K}\\}\right)$
for all ${n\geq b(n_{0})}+1$, in contradiction to
$J^{-1}(\\{f_{1}\\})\cap\\{\overline{u}_{1},\ldots,\overline{u}_{K}\\}$
consisting of at least one accumulation point of $(u_{n})_{n\in\mathbb{N}}$.
Hence, we have

$J(\overline{u}_{1})=\ldots=J(\overline{u}_{K})=:\bar{J}.$ (13)

Next, we show that every accumulation point of $(u_{a(n)})_{n\in\mathbb{N}}$
is stationary. We prove this by contradiction.
Assume there exists a non-stationary accumulation point $\overline{u}$ of
$(u_{a(n)})_{n\in\mathbb{N}}$. Observe that

$\min_{i\in\\{1,\ldots,K\\}}\|\overline{u}-\overline{u}_{i}\|>0.$

Case 3.1:

$J(\overline{u})<\bar{J}$.

Then, by the same arguments as above, there exists $N\in\mathbb{N}$ and
${\varepsilon}>0$ s.t.

$u_{n}\not\in\bigcup_{i=1}^{K}\mathcal{B}_{\frac{\varepsilon}{4}}\left(\overline{u}_{i}\right)\quad\text{for
all }n\geq\mathbb{N}.$

This is a contradiction to $\overline{u}_{1},\ldots,\overline{u}_{K}$ being
accumulation points of $(u_{n})_{n\in\mathbb{N}}$.

Case 3.2:

$J(\overline{u})>\bar{J}$.

In this case, there exists $N\in\mathbb{N}$ and ${\varepsilon}>0$ such that
$u_{n}\not\in\mathcal{B}_{\frac{\varepsilon}{4}}\left(\overline{u}\right)$ for
all $n\geq N$. This is a contradiction to $\overline{u}$ being an accumulation
point of $(u_{n})_{n\in\mathbb{N}}$.

Case 3.3:

$J(\overline{u})=\bar{J}$.

Since $\overline{u}$ is an accumulation point of
$(u_{a(n)})_{n\in\mathbb{N}}$, there exists a subsequence
$(u_{a(n_{k})})_{k\in\mathbb{N}}$ with $u_{a(n_{k})}\to\overline{u}$. The
sequence $(u_{a(n_{k})-1})_{k\in\mathbb{N}}$ is bounded and therefore has at
least one accumulation point $\overline{u}_{-1}$ and a subsequence
$(u_{a(n_{k_{t}})-1})_{t\in\mathbb{N}}$ with
$u_{a(n_{k_{t}})-1}\to\overline{u}_{-1}$. It follows that

$\displaystyle\mathcal{P}_{\mathcal{U}}\left(\overline{u}_{-1}-\tau\nabla
J(\overline{u}_{-1})\right)$
$\displaystyle=\lim_{t\to\infty}\mathcal{P}_{\mathcal{U}}\left(u_{a(n_{k_{t}})-1}-\tau\hat{G}_{a(n_{k_{t}})-1}\right)$
$\displaystyle=\lim_{t\to\infty}u_{a(n_{k_{t}})}$
$\displaystyle=\overline{u}.$

As $\overline{u}$ is not stationary by our assumption,
$\overline{u}_{-1}\neq\overline{u}$ and $\overline{u}_{-1}$ is no stationary
point of $J$. Thus, Lemma 1 combined with Lemma 2 yields

$J(\overline{u})-J(\overline{u}_{-1})\leq\left(\tfrac{L}{2}-\tfrac{1}{\tau}\right)\|\overline{u}_{-1}-\overline{u}\|^{2}<0.$

Therefore, $\overline{u}_{-1}$ is an accumulation point of
$(u_{a(n)})_{n\in\mathbb{N}}$, which satisfies
${J(\overline{u}_{-1})>J(\overline{u})=\bar{J}}$. This, however, is
impossible, as seen in Case 3.2.

In conclusion, in Case 3, all accumulation points of
$(u_{n})_{n\in\mathbb{N}}$ are stationary. Thus, on every convergent
subsequence we have $\|u_{n_{k}+1}-u_{n_{k}}\|\to 0$. Since
$(u_{n})_{n\in\mathbb{N}}$ is bounded, this already implies
$\|u_{n+1}-u_{n}\|\to 0$. Now, Lemma 3 yields the claimed convergence of
$(u_{n})_{n\in\mathbb{N}}$ to a stationary point of $J$.∎

The idea of the proof above still applies in the case that $J$ is constant on
some parts of $\mathcal{U}$, i.e., $J$ can have infinitely many stationary
points. We obtain the following convergence result:

###### Theorem 3.2

Let $\mathcal{S}(J)$ be the set of stationary points of $J$ on $U$ as defined
in Definition 2. Assume that the set

$\mathcal{N}:=\big{\\{}J(u)\,:\,u\in\mathcal{S}(J)\big{\\}}\subset\mathbb{R}$

is of Lebesgue-measure zero. Then every accumulation point of the sequence
generated by CSG with constant stepsize $\tau<\tfrac{2}{L}$ is stationary and
we have convergence in function values.

###### Remark 2

Comparing Theorem 3.1 and Theorem 3.2, observe that under the weaker
assumptions on the set of stationary points of $J$, we no longer obtain
convergence for the whole sequence of iterates. To illustrate why that is the
case, consider the function $J:\mathbb{R}^{d_{\textnormal{o}}}\to\mathbb{R}$
given by $J(u)=\cos(\pi\|u\|^{2})$ and
$\mathcal{U}=\\{u\in\mathbb{R}^{d_{\textnormal{o}}}\,:\,\|u\|^{2}\leq\frac{3}{2}\\}$.
Then, $\mathcal{S}(J)=\\{0\\}\cup\\{u\in\mathcal{U}\,:\,\|u\|=1\\}$, i.e.,
every point on the unit sphere is stationary. Thus, we can not use Lemma 3 at
the end of the proof to obtain convergence of $(u_{n})_{n\in\mathbb{N}}$.
Theoretically, it might happen that the iterates $(u_{n})_{n\in\mathbb{N}}$
cycle around the unit sphere, producing infinitely many accumulation points,
all of which have the same objective function value. This, however, did not
occur when testing this example numerically.

###### Remark 3

While the assumption in Theorem 3.2 seems unhandy at first, there is actually
a rich theory concerning such properties. For example, Sard’s Theorem SardTheo
and generalizations SardAllgemein  give that the assumption holds if $J\in
C^{d_{\textnormal{o}}}$ and $\mathcal{U}$ has smooth boundary. Even though it
can be shown that there exist functions, which do not satisfy the assumption
(e.g. AntiSard1 ; AntiSard2 ), such counter-examples need to be precisely
constructed and will most likely not appear in any application.

######  Proof (of Theorem 3.2)

Proceeding analog to the proof of Theorem 3.1, we only have to adapt two
intermediate results in Case 3:

(R1)

The objective function values of all accumulation points of
$(u_{b(n)})_{n\in\mathbb{N}}$ are equal.

(R2)

Every accumulation point of $(u_{a(n)})_{n\in\mathbb{N}}$ is stationary.

Assume first, that (R1) does not hold. Then there exist two stationary points
${\overline{u}_{1}\neq\overline{u}_{2}}$ with
$J(\overline{u}_{1})<J(\overline{u}_{2})$. Now, (A) and (B) shown in the proof
of Theorem 3.1 yield that there must exist an accumulation point
$\overline{u}_{3}$ of $(u_{b(n)})_{n\in\mathbb{N}}$, i.e., a stationary point,
with $J(\overline{u}_{1})<J(\overline{u}_{3})<J(\overline{u}_{2})$. Iterating
this procedure, we conclude that the set
$\mathcal{N}\cap\big{[}J(\overline{u}_{1}),J(\overline{u}_{2})\big{]}$ is
dense in $\big{[}J(\overline{u}_{1}),J(\overline{u}_{2})\big{]}$.

By continuity of $u\mapsto\mathcal{P}_{\mathcal{U}}\big{(}u-\tau\nabla
J(u)\big{)}-u$ and compactness of $\mathcal{U}$, we see that

$\mathcal{N}\cap\big{[}J(\overline{u}_{1}),J(\overline{u}_{2})\big{]}=\big{[}J(\overline{u}_{1}),J(\overline{u}_{2})\big{]},$

contradicting our assumption that $\lambda(\mathcal{N})=0$.

For (R2), assume that $(u_{a(n)})_{n\in\mathbb{N}}$ has a non-stationary
accumulation point $\overline{u}$. Since $\mathcal{S}(J)$ is compact, it holds

$\operatorname{dist}(\\{\overline{u}\\},\mathcal{S}(J))>0.$

Thus, by the same arguments as in Case 3.1, 3.2 and 3.3 within the proof of
Theorem 3.1, we observe that such a point $\overline{u}$ can not exist. ∎

##  4 Backtracking

For this section, we again assume that Assumptions 2.1, 2.2 and 2.3 are
satisfied.

As $\|\hat{G}_{n}-\nabla J(u_{n})\|\to 0$ and $\|\hat{J}_{n}-J(u_{n})\|\to 0$
for $n\to\infty$, we can use these approximations to refine the steplength by
a backtracking line search method.

###### Definition 3

For simplicity, we define

$s_{n}(t):=\mathcal{P}_{\mathcal{U}}\left(u_{n}-t\hat{G}_{n}\right).$

Furthermore, given $n$ gradient samples $\nabla_{1}j(u_{i},x_{i})$ and $n$
cost function samples $j(u_{i},x_{i})$, by calculating the weights
$\alpha_{i}^{(n)}(u)$ w.r.t. a given point $u\in\mathcal{U}$, we define

$\tilde{J}_{n}(u)=\sum_{i=1}^{n}\alpha_{i}^{(n)}(u)j(u_{i},x_{i})\quad\text{
and
}\quad\tilde{G}_{n}(u)=\sum_{i=1}^{n}\alpha_{i}^{(n)}(u)\nabla_{1}j(u_{i},x_{i}),$

which are approximations to $J(u)$ and $\nabla J(u)$ respectively.

Based on the well known Armijo-Wolfe conditions from continuous optimization
ArmijoCondition ; WolfeConditions1 ; WolfeConditions2 , we introduce the
following step size conditions:

###### Definition 4

For $0<c_{1}<c_{2}<1$, we call $s_{n}(\tau_{n})$ an Armijo step, if

$\displaystyle\tilde{J}_{n}(s_{n}(\tau_{n}))\leq\hat{J}_{n}-c_{1}\hat{G}_{n}^{\top}\left(u_{n}-s_{n}(\tau_{n})\right).$
(SW1) Additionally, we define the following Wolfe-type condition:
$\displaystyle\tilde{G}_{n}(s_{n}(\tau_{n}))^{\top}\left(s_{n}(\tau_{n})-u_{n}\right)\geq
c_{2}\hat{G}_{n}^{\top}\left(s_{n}(\tau_{n})-u_{n}\right).$ (SW2)

We try to obtain a stepsize that satisfies (SW1) and (SW2) by a bisection
approach, as formulated in Algorithm 2. Since we can not guarantee to find a
suitable stepsize, we perform only a fixed number $T\in\mathbb{N}$ of
backtracking steps. Notice that the curvature condition (SW2) only has an
influence, if $u_{n}-\tau_{n}\hat{G}_{n}\in\mathcal{U}$ (see line 6 in
Algorithm 2). This way, we gain the advantages of a Wolfe line search while
inside $\mathcal{U}$, without ruling out stationary points at the boundary of
$\mathcal{U}$.

For our convergence analysis, we assume that in each iteration of CSG with
line search, Algorithm 2 is initiated with the same $\eta_{n}=\eta>0$. From a
practical point of view, we might also consider a diminishing sequence
$(\eta_{n})_{n\in\mathbb{N}}$ of backtracking initializations (see Section 6).
The CSG method with backtracking line search (bCSG) is given in Algorithm 3.

Algorithm 2 Backtracking refinement

1: Given $T\in\mathbb{N}$, $0<c_{1}<c_{2}<1$ appearing in (SW1∗) and (SW2),
$u_{n}\in\mathcal{U}$, and $\eta>0$, set $t=1$, $a=0$, $b=\infty$,
$\eta_{A}=\infty$.

2: while $t\leq T$ do

3: Calculate step $s=\mathcal{P}_{\mathcal{U}}(u_{n}-\eta\hat{G}_{n})$,
weights $\alpha_{k}^{(n)}(s)$ and the approximations $\tilde{J}_{n}(s)$,
$\tilde{G}_{n}(s)$;

4: if (SW1∗) is not satisfied then

5: $b=\eta$;

6: else if $s=u_{n}-\eta\hat{G}_{n}$ and (SW2) is not satisfied then

7: $a=\eta$;$\eta_{A}=\eta$;

8: else

9: break

10: end if

11: if $b<\infty$ then

12: $\eta=\frac{a+b}{2}$;

13: else

14: $\eta=2a$;

15: end if

16: $t=t+1$;

17: end while

18: if $t=T+1$ and $\eta_{A}<\infty$ then

19: $\tau_{n}=\eta_{A}$;

20: else

21: $\tau_{n}=\eta$;

22: end if

Algorithm 3 Backtracking CSG (bCSG)

1: Given $u_{0}\in\mathcal{U}$, and a positive sequence
$(\eta_{n})_{n\in\mathbb{N}}$,

2: while Termination condition not met do

3: Sample objective function:$\quad j_{n}:=j(u_{n},x_{n})$

4: Sample gradient:$\quad g_{n}:=\nabla_{1}j(u_{n},x_{n})$

5: Calculate weights $\alpha_{k}$

6: Calculate search
direction:$\quad\hat{G}_{n}:=\sum_{k=1}^{n}\alpha_{k}g_{k}\vphantom{\Big{(}}$

7: Compute objective function value
approximation:$\quad\hat{J}_{n}:=\sum_{k=1}^{n}\alpha_{k}j_{k}\vphantom{\Big{(}}$

8: Calculate stepsize $\tau_{n}$ by Algorithm 2 with start at $\eta_{n}$.

9: Gradient step:$\quad
u_{n+1}:=\mathcal{P}_{\mathcal{U}}\big{(}u_{n}-\tau_{n}\hat{G}_{n}\big{)}\vphantom{\Big{(}}$

10: Update index:$\quad n=n+1\vphantom{\Big{(}}$

11: end while

Since all of the terms $\tilde{J}_{n}(s_{n}(\tau_{n}))$, $\hat{J}_{n}$ and
$\hat{G}_{n}$ appearing in (SW1) contain some approximation error when
compared to $J(s_{n}(\tau_{n}))$, $J(u_{n})$ and $\nabla J(u_{n})$
respectively, especially the first iterations of Algorithm 3 might profit from
a slightly weaker formulation of (SW1). Therefore, in practice, we will
replace (SW1) by the non-monotone version

$\tilde{J}_{n}(s_{n}(\tau_{n}))\leq\max_{k\in\\{0,\ldots,K\\}}\hat{J}_{n-k}-c_{1}\hat{G}_{n}^{\top}\left(u_{n}-s_{n}(\tau_{n})\right),$
(SW1∗)

for some $K\in\\{0,\ldots,n\\}$ (e.g., we choose $K=1$ throughout Section 6).

###  4.1 Convergence Results

For CSG with backtracking line search, we obtain the same convergence results
as for constant step sizes:

######  Theorem 4.1 (Convergence for backtracking line search)

Let $\mathcal{S}(J)$ be the set of stationary points of $J$ on $U$ as defined
in Definition 2. Assume that

$\mathcal{N}:=\big{\\{}J(u)\,:\,u\in\mathcal{S}(J)\big{\\}}\subset\mathbb{R}$

is of Lebesgue-measure zero and $T$ in Algorithm 2 is chosen large enough,
such that $2^{-T}\eta<\frac{2}{L}$. Then every accumulation point of the
sequence $(u_{n})_{n\in\mathbb{N}}$ generated by Algorithm 3 is stationary and
we have convergence in function values.

If $J$ satisfies the stronger assumption of having only finitely many
stationary points, $(u_{n})_{n\in\mathbb{N}}$ converges to a stationary point
of $J$.

###### Proof

Notice first, that there are only two possible outcomes of Algorithm 2: Either
$\tau_{n}$ satisfies (SW1), or $\tau_{n}=2^{-T}\eta<\frac{2}{L}$. Furthermore,
as we have seen in the proof of Lemma 3, for all $\varepsilon>0$ almost all
$u_{n}$ lie in $\varepsilon$-Balls around the accumulation points of
$(u_{n})_{n\in\mathbb{N}}$, since $(u_{n})_{n\in\mathbb{N}}$ is bounded.
Therefore, $\tilde{J}_{n}(u_{n+1})-J(u_{n+1})\to 0$ and
$\tilde{G}_{n}(u_{n+1})-\nabla J(u_{n+1})\to 0$ (compare Lemma 6). Since we
already know, that the steps with constant stepsize
$\tau_{n}=2^{-T}\eta<\frac{2}{L}$ can be split in descent steps and steps
which satisfy $\|u_{n+1}-u_{n}\|\to 0$, we now take a closer look at the
Armijo-steps, i.e., steps with $\tau_{n}\neq 2^{-T}\eta$.

If $\tau_{n}\neq 2^{-T}\eta$, by (SW1) and Lemma 2, it holds

$\displaystyle J(u_{n+1})-J(u_{n})$ $\displaystyle\leq-
c_{1}\frac{\|u_{n+1}-u_{n}\|^{2}}{\tau_{n}^{2}}+\left|J(u_{n})-\hat{J}_{n}\right|+\left|J(u_{n+1})-\tilde{J}_{n}(u_{n+1})\right|$
$\displaystyle\leq-
c_{1}\frac{\|u_{n+1}-u_{n}\|^{2}}{\tau_{\text{max}}^{2}}+\left|J(u_{n})-\hat{J}_{n}\right|+\left|J(u_{n+1})-\tilde{J}_{n}(u_{n+1})\right|.$

Therefore, we either have

$\left|J(u_{n})-\hat{J}_{n}\right|+\left|J(u_{n+1})-\tilde{J}_{n}(u_{n+1})\right|\leq
c_{1}\frac{\|u_{n+1}-u_{n}\|^{2}}{\tau_{\text{max}}^{2}},$

in which case it holds $J(u_{n+1})\leq J(u_{n})$, or

$\left|J(u_{n})-\hat{J}_{n}\right|+\left|J(u_{n+1})-\tilde{J}_{n}(u_{n+1})\right|>c_{1}\frac{\|u_{n+1}-u_{n}\|^{2}}{\tau_{\text{max}}^{2}},$

in which case $\tilde{J}_{n}(u_{n+1})-J(u_{n+1})\to 0$ and
$\hat{J}_{n}-J(u_{n})\to 0$ yield $\|u_{n+1}-u_{n}\|\to 0$.

Thus, regardless of whether or not $\tau_{n}=2^{-T}\eta$, we can split
$(u_{n})_{n\in\mathbb{N}}$ in a subsequence of descent steps and a subsequence
of steps with $\|u_{n+1}-u_{n}\|\to 0$. The rest of the proof is now identical
to the proof of Theorem 3.1 and Theorem 3.2.∎

##  5 Estimations for the Lipschitz constant of $\nabla J$

We have already seen, that the Lipschitz constant $L$ of $\nabla J$ is closely
connected with efficient bounds on the step sizes. However, in general, we can
not expect to have any knowledge of $L$ a priori. Thus, we are interested in
an approximation of $L$, that can be calculated during the optimization
process.

Investigating the proof of Lemma 1 in DescentUndProjection

$\displaystyle J(u_{1})$
$\displaystyle=J(u_{2})+\int_{0}^{1}\left\langle\nabla
J(u_{2})+t(u_{1}-u_{2})),u_{1}-u_{2}\right\rangle\mathrm{d}t$
$\displaystyle=J(u_{2})+\left\langle\nabla J(u_{2}),u_{1}-u_{2}\right\rangle$
$\displaystyle\quad\quad+\int_{0}^{1}\left\langle\nabla
J\big{(}u_{2}+t(u_{1}-u_{2})\big{)}-\nabla
J(u_{2}),u_{1}-u_{2}\right\rangle\mathrm{d}t$ $\displaystyle\leq
J(u_{2})+\left\langle\nabla J(u_{2}),u_{1}-u_{2}\right\rangle$
$\displaystyle\quad\quad+\int_{0}^{1}\left\|\nabla
J\big{(}u_{2}+t(u_{1}-u_{2})\big{)}-\nabla
J(u_{2})\right\|\cdot\left\|u_{1}-u_{2}\right\|\mathrm{d}t$ $\displaystyle\leq
J(u_{2})+\left\langle\nabla
J(u_{2}),u_{1}-u_{2}\right\rangle+\int_{0}^{1}Lt\|u_{1}-u_{2}\|^{2}\mathrm{d}t$
$\displaystyle=J(u_{2})+\left\langle\nabla
J(u_{2}),u_{1}-u_{2}\right\rangle+\tfrac{L}{2}\|u_{1}-u_{2}\|^{2},$

we observe that we do not need the true Lipschitz constant $L$ of $\nabla J$
for the second inequality. Instead, it is sufficient to choose any constant
$C=C(u_{1},u_{2})$ that satisfies

$\left\|\nabla J\big{(}u_{2}+t(u_{1}-u_{2})\big{)}-\nabla J(u_{2})\right\|\leq
C\|u_{1}-u_{2}\|\quad\text{for all }t\in[0,1].$

To motivate our approach, assume that $J$ is twice continously differentiable.
In this case, a possible approximation to the constant $C_{n}$ in iteration
$n$ is $\|\nabla^{2}J(u_{n})\|$. Therefore, utilizing the previous gradient
approximations, we obtain

$C_{n}\approx\left\|\nabla^{2}J(u_{n})\right\|\approx\frac{\left\|\nabla
J(u_{n})-\nabla
J(u_{n-1})\right\|}{\left\|u_{n}-u_{n-1}\right\|}\approx\frac{\big{\|}\hat{G}_{n}-\hat{G}_{n-1}\big{\|}}{\left\|u_{n}-u_{n-1}\right\|}.$

Then, $C_{n}^{-1}$ yields a good initial step size for our backtracking line
search. To circumvent high oscillation of $C_{n}$, which may arise from the
approximation errors of the terms involved, we project $C_{n}$ onto the
interval $\left[C_{\text{min}},C_{\text{max}}\right]\subset\mathbb{R}$, where
$0<C_{\text{min}}<C_{\text{max}}<\tfrac{2^{T+1}}{L}$, i.e.,

$C_{n}=\min\left\\{C_{\text{max}}\,,\,\max\left\\{C_{\text{min}}\,,\,\tfrac{\left\|\hat{G}_{n}-\hat{G}_{n-1}\right\|}{\left\|u_{n}-u_{n-1}\right\|}\right\\}\right\\}.$
(14)

If possible, $C_{\text{min}}$ and $C_{\text{max}}$ should be chosen according
to information concerning $L$. However, tight bounds on these quantities are
not needed, as long as $T$ is chosen large enough. The resulting SCIBL-CSG
(SCaling Independent Backtracking Line search) method is presented in
Algorithm 4. Notice that SCIBL-CSG does not require any a priori choice of
step sizes and yields the same convergence results as bCSG.

Algorithm 4 SCIBL-CSG

1: Given $u_{0}\in\mathcal{U}$,

2: while Termination condition not met do

3: Sample objective function:$\quad j_{n}:=j(u_{n},x_{n})$

4: Sample gradient:$\quad g_{n}:=\nabla_{1}j(u_{n},x_{n})$

5: Calculate weights $\alpha_{k}$

6: Calculate search
direction:$\quad\hat{G}_{n}:=\sum_{k=1}^{n}\alpha_{k}g_{k}\vphantom{\Big{(}}$

7: Compute objective function value
approximation:$\quad\hat{J}_{n}:=\sum_{k=1}^{n}\alpha_{k}j_{k}\vphantom{\Big{(}}$

8: Calculate $C_{n}$ by (14).

9: Calculate stepsize $\tau_{n}$ by Algorithm 2 with start at
$\tfrac{1}{C_{n}}$.

10: Gradient step:$\quad
u_{n+1}:=\mathcal{P}_{\mathcal{U}}\big{(}u_{n}-\tau_{n}\hat{G}_{n}\big{)}\vphantom{\Big{(}}$

11: Update index:$\quad n=n+1\vphantom{\Big{(}}$

12: end while

In the following section, we now will illustrate the presented analytical
results based on numerical experiments with several academic examples.

##  6 Numerical Experiments

The calculation of the integration weights $\alpha_{k}$ (see Algorithm 3)
plays a crucial role for the performance of any CSG algorithm. In pflug2021csg
, several methods for the weight computation have been analyzed and compared.
Since the focus of this contribution lies entirely on the step sizes, for all
numerical results concerning CSG, we choose the so called empirical weights,
which are computationally very cheap, but, given a desired precision,
typically lead to a larger number of required gradient evaluations.

In the first example, the convergence properties for CSG with constant step
sizes are analyzed in a prototype setting. Furthermore, we observe that – as
theory predicts – the basic SG method does not yield a convergent sequence of
iterates in this example, if carried out with the same step sizes.

The second example aims to demonstrate the stability of CSG with backtracking
(bCSG) with respect to the initially chosen step size
$(\eta_{n})_{n\in\mathbb{N}}$. For this, we compare the performance of bCSG
and the well-known AdaGrad AdaGradPaper  method when carried out for a large
spectrum of choices for $(\eta_{n})_{n\in\mathbb{N}}$.

In the final example, we consider a Rosenbrock-type function with
multiplicative noise and compare the performance of AdaGrad, bCSG and SCIBL-
CSG.

###  6.1 Convergence for constant step sizes

Define $\mathcal{U}=\left[-\frac{1}{2},\frac{1}{2}\right]$,
$\mathcal{X}=\left(-\frac{1}{2},\frac{1}{2}\right)$ and consider the problem

$\min_{u\in\mathcal{U}}\;\frac{1}{2}\int_{\mathcal{X}}(u-x)^{2}\mathrm{d}x.$
(15)

It is easy to see that (15) has a unique solution $u^{\ast}=0$. Furthermore,
the objective function is $L$-smooth (with Lipschitz constant 1) and even
strictly convex. Thus, by Theorem 3.1, the CSG method with a constant step
size $\tau<2$ produces a sequence $(u_{n})_{n\in\mathbb{N}}$ that satisfies
$u_{n}\to 0$.

However, even in this highly regular setting, the commonly used basic SG
method does not guarantee convergence of the iterates for a constant step
size.

To demonstrate this behavior of both CSG and SG, we draw 2000 random starting
points $u_{0}\in\mathcal{U}$ and compare the iterates produced by CSG and SG
with five different constant step sizes ($\tau\in\\{0.01,0.1,1,1.9,1.99\\}$).
The results are shown in Figure 1.

As expected, the iterates produced by the SG method do not converge to the
optimal solution, but instead remain in a neighborhood of $u^{\ast}$. The
radius of said neighborhood depends on the choice of $\tau$ and decreases for
smaller $\tau$, see (Steps01, , Theorem 4.6).

Convergence for CSG in this example has already been observed numerically in
(pflug2021csg, , Section 5.1), but has not been proven until now.

Figure 1: Comparison of the iterates produced by 500 steps of SG (red / first
row) and CSG (green / second row) with 2000 random starting points
$u_{0}\in\mathcal{U}$. Both methods have been tested for the five different
constant step sizes $\tau\in\\{0.01,0.1,1,1.9,1.99\\}$ (first to fifth
column). The shaded areas indicate the quantiles $P_{0.1,0.9}$ (light) and
$P_{0.25,0.75}$ (dark), while the solid line represents the median of the 2000
runs.

###  6.2 Stability with respect to the step size

As a basic example, we set $\mathcal{U}=[-10,10]^{5}$,
$\mathcal{X}=(-1,1)^{5}$ and consider the Problem

$\min_{u\in\mathcal{U}}\;J(u),$ (16)

where

$J(u)=-\int_{\mathcal{X}}\frac{20}{1+\|u-x\|^{2}}\,\mathrm{d}x.$

Problem (16) has the unique solution $u^{\ast}=0\in\mathcal{U}$, which can be
found analytically.

As a comparison to our method, we choose the AdaGrad AdaGradPaper  algorithm,
as it is widely used for problems of type (1). Both AdaGrad and CSG start each
iteration with a presdescribed step size $\eta_{n}>0$, based on which the
calculation of the true step size $\tau_{n}$ is performed (see Algorithm 2).
We want to test the stability of both methods with respect to the initially
chosen step length. For this purpose, we set
$\eta_{n}=\tfrac{\tau_{0}}{n^{d}}$, where $\tau_{0}>0$, $n$ is the iteration
count and $d\in[0,1]$ is fixed.

For each combination of $\tau_{0}$ and $d$, we choose 1200 random starting
points in $\mathcal{U}$ and perform 500 optimization steps with both AdaGrad
and backtracking CSG. The median of the absolute error $\|u_{500}-u^{\ast}\|$
after the optimization, depending on $d$ and $\tau_{0}$, is presented in
Figure 2.

While there are a few instances where AdaGrad yields a better result than
backtracking CSG, we observe that the performance of AdaGrad changes rapidly,
especially with respect to the parameter $d$. The backtracking CSG method on
the other hand performs superior in most cases and is much less dependent on
the choice of parameters.

Figure 2: Absolute error $|u_{n}-u^{\ast}|$ for $n=500$ of AdaGrad
AdaGradPaper  and backtracking CSG (Algorithm 3), depending on the constants
$\tau_{0}>0$ and $d\in[0,1]$ with initial choice of step size
$\eta_{n}=\tau_{0}n^{-d}$.

###  6.3 Comparison of SCIBL-CSG, bCSG and AdaGrad

As an academic example to test the performance of Algorithm 3 and Algorithm 4,
we consider a Rosenbrock function RosenbrockPaper  with multiplicative noise.
Our optimization problem reads as follows:

$\min_{u\in[-3,3]^{2}}\>\int_{\mathbb{R}}(1+x)\left((1-u_{1})^{2}+100\big{(}u_{2}-u_{1}^{2}\big{)}^{2}\right)\mu(\mathrm{d}x).$
(17)

Here, we assume the “noise” $x$ to be standard normal distributed, i.e.,
$x\sim\mathcal{N}(0,1)$. Note that $\mu$ and $\mathcal{X}$ do not satisfy
Assumption 2.2. However, as the density function corresponding to $\mu$
decreases exponentially for $|x|\to\infty$, the approximation errors in
$\hat{G}_{n}$ and $\hat{J}_{n}$ still vanish in the course of the iterations.

Problem (17) has only one stationary point, $u^{\ast}=(1,1)^{\top}$, which is
the global minimum. While $u^{\ast}$ can easily be found analytically,
optimization problems with Rosenbrock-type functions are notoriously difficult
to solve for gradient based methods (see e.g. RosenbrockTestLiteratur ).

For our test, we choose 5000 random starting points $u_{0}\in\mathcal{U}$ and
compare the absolute error $\|u_{n}-u^{\ast}\|$ in each iteration for

  1. 1.

AdaGrad with a step size of $\tau_{n}=\tfrac{1}{10\sqrt{n}}$,

  2. 2.

Backtracking CSG (bCSG) with $\eta_{n}=\tfrac{1}{40}$,

  3. 3.

Scaling independent backtracking CSG (SCIBL-CSG) with $C_{\text{min}}=10^{-8}$
and $C_{\text{max}}=10^{8}$.

Both $\tau_{n}$ in 1. and $\eta_{n}$ in 2. were chosen as the top-performers
from a small test group of candidates. The choices for $C_{\text{min}}$ and
$C_{\text{max}}$ are somewhat arbitrary, since we stated in Section 5 that
SCIBL-CSG would require almost no a priori analysis of (17).

The results are presented in Figure 3. Both bCSG and SCIBL-CSG yield
comparable results, while AdaGrad achieves hardly any progress in later
iterations.

Additionally, we want to know how reasonable the initial guess $C_{n}$
calculated in SCIBL-CSG is. For this purpose, we analyzed how many
backtracking refinements, i.e., steps of Algorithm 2, both SCIBL-CSG and bCSG
take in each iteration before accepting a step size. In total, the ordinary
bCSG required roughly 1.5 times as many refinement steps when compared to
SCIBL-CSG.

Figure 3: Evolution of the absolute error $\|u_{n}-u^{\ast}\|$ during the
optimization process for AdaGrad (red), Backtracking CSG (bCSG, blue) and
Scaling independent backtracking CSG (SCIBL-CSG, yellow). The solid lines
represent the median of the 5000 runs with different starting points, while
the shaded areas correspond to the quantiles $P_{0.25,0.75}$.

##  7 Conclusion and Outlook

In this contribution, we provided a convergence proof of the CSG method when
carried out with a small enough constant step size for optimization problems
of type (1). Additionally, it was shown that the CSG algorithm can be
augmented by an Armijo-type backtracking line search based on the objective
function and gradient approximations calculated in the course of the
iterations. The resulting method was proven to converge under mild assumptions
and was shown to yield stable results for a large spectrum of hyperparameters.
Lastly, we combined a heuristic approach for approximating the Lipschitz
constant of the gradient of the objective function with the backtracking CSG
algorithm to obtain a method that requires no a priori step size rules and
almost no information about the optimization problem.

For all three methods, we stated convergence results that are similar to
convergence results for full gradient schemes, i.e., every accumulation of the
sequence of iterates is stationary and we have convergence in the objective
function values. Furthermore, as is the case for full gradient methods, if the
optimization problem has only finitely many stationary points, the presented
CSG variants produce a sequence that is guaranteed to converge to one of these
stationary points.

Lastly, all results were numerically demonstrated by means of academic test
cases and compared to similar optimization methods from literature.

While we were able to show convergence properties of CSG which are similar to
results obtained for full gradient approaches, it remains an open question, if
we can achieve similar convergence rates as well. Furthermore, the presented
methods have so far only been tested for academic examples. Thus, we are
interested in applying the CSG method to large scale optimization problems
from e.g. topology optimization.

###### Acknowledgements.

The research was funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) - Project-ID 416229255 - CRC 1411.

## References

  * (1) Kim, C., Lee, J., Yoo, J.: Machine learning-combined topology optimization for functionary graded composite structure design.  Comput. Methods Appl. Mech. Engrg. 387, Paper No. 114158, 32 (2021).  DOI 10.1016/j.cma.2021.114158
  * (2) Evstatiev, E.G., Finn, J.M., Shadwick, B.A., Hengartner, N.: Noise and error analysis and optimization in particle-based kinetic plasma simulations.  J. Comput. Phys. 440, Paper No. 110394, 28 (2021).  DOI 10.1016/j.jcp.2021.110394
  * (3) Wadbro, E., Berggren, M.: Topology optimization of an acoustic horn.  Comput. Methods Appl. Mech. Engrg. 196(1-3), 420–436 (2006).  DOI 10.1016/j.cma.2006.05.005
  * (4) Hassan, E., Wadbro, E., Berggren, M.: Topology optimization of metallic antennas.  IEEE Trans. Antennas and Propagation 62(5), 2488–2500 (2014).  DOI 10.1109/TAP.2014.2309112
  * (5) Semmler, J., Pflug, L., Stingl, M., Leugering, G.: Shape optimization in electromagnetic applications.  In: New Trends in Shape Optimization, pp. 251–269. Springer (2015)
  * (6) Robbins, H., Monro, S.: A stochastic approximation method.  Ann. Math. Statistics 22, 400–407 (1951)
  * (7) Schmidt, M., Le Roux, N., Bach, F.: Minimizing finite sums with the stochastic average gradient.  Math. Program. 162(1-2, Ser. A), 83–112 (2017)
  * (8) Pflug, L., Bernhardt, N., Grieshammer, M., Stingl, M.: CSG: a new stochastic gradient method for the efficient solution of structural optimization problems with infinitely many states.  Struct. Multidiscip. Optim. 61(6), 2595–2611 (2020)
  * (9) Pflug, L., Grieshammer, M., Uihlein, A., Stingl, M.: Csg: A stochastic gradient method for a wide class of optimization problems appearing in a machine learning or data-driven context (2021)
  * (10) Patel, V.: Kalman-based stochastic gradient method with stop condition and insensitivity to conditioning.  SIAM J. Optim. 26(4), 2620–2648 (2016)
  * (11) Schmidt, M., Roux, N.L.: Fast convergence of stochastic gradient descent under a strong growth condition (2013)
  * (12) Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning.  SIAM Rev. 60(2), 223–311 (2018).  DOI 10.1137/16M1080173
  * (13) Cevher, V., Vũ, B.C.: On the linear convergence of the stochastic gradient method with constant step-size.  Optim. Lett. 13(5), 1177–1187 (2019).  DOI 10.1007/s11590-018-1331-1
  * (14) Lacoste-Julien, S., Schmidt, M., Bach, F.: A simpler approach to obtaining an o(1/t) convergence rate for the projected stochastic subgradient method (2012)
  * (15) Paquette, C., Scheinberg, K.: A stochastic line search method with expected complexity analysis.  SIAM J. Optim. 30(1), 349–376 (2020)
  * (16) Prazeres, M., Oberman, A.M.: Stochastic gradient descent with Polyak’s learning rate.  J. Sci. Comput. 89(1), Paper No. 25, 16 (2021).  DOI 10.1007/s10915-021-01628-3
  * (17) Tan, C., Ma, S., Dai, Y.H., Qian, Y.: Barzilai-borwein step size for stochastic gradient descent.  In: D.D. Lee, M. Sugiyama, U.V. Luxburg, I. Guyon, R. Garnett (eds.) Advances in Neural Information Processing Systems 29, pp. 685–693. Curran Associates, Inc. (2016)
  * (18) Klenke, A.: Probability theory.  Universitext. Springer-Verlag London, Ltd., London (2008).  A comprehensive course, Translated from the 2006 German original
  * (19) Goldstein, A.A.: Convex programming in Hilbert space.  Bull. Amer. Math. Soc. 70, 709–710 (1964).  DOI 10.1090/S0002-9904-1964-11178-2
  * (20) Levitin, E., Polyak, B.: Constrained minimization methods.  USSR Computational Mathematics and Mathematical Physics 6(5), 1–50 (1966).  DOI https://doi.org/10.1016/0041-5553(66)90114-5
  * (21) Beck, A.: First-order methods in optimization, _MOS-SIAM Series on Optimization_ , vol. 25.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA (2017).  DOI 10.1137/1.9781611974997.ch1
  * (22) Gibbs, A.L., Su, F.E.: On choosing and bounding probability metrics.  International statistical review 70(3), 419–435 (2002)
  * (23) Varadarajan, V.S.: On the convergence of sample probability distributions.  Sankhyā 19, 23–26 (1958)
  * (24) Sard, A.: The measure of the critical values of differentiable maps.  Bull. Amer. Math. Soc. 48, 883–890 (1942).  DOI 10.1090/S0002-9904-1942-07811-6
  * (25) Guillemin, V., Pollack, A.: Differential topology.  Prentice-Hall, Inc., Englewood Cliffs, N.J. (1974)
  * (26) Whitney, H.: A function not constant on a connected set of critical points.  Duke Mathematical Journal 1(4), 514 – 517 (1935).  DOI 10.1215/S0012-7094-35-00138-7
  * (27) Kaufman, R.: A singular map of a cube onto a square.  J. Differential Geometry 14(4), 593–594 (1981) (1979)
  * (28) Armijo, L.: Minimization of functions having Lipschitz continuous first partial derivatives.  Pacific J. Math. 16, 1–3 (1966)
  * (29) Wolfe, P.: Convergence conditions for ascent methods.  SIAM Rev. 11, 226–235 (1969).  DOI 10.1137/1011036
  * (30) Wolfe, P.: Convergence conditions for ascent methods. II. Some corrections.  SIAM Rev. 13, 185–188 (1971).  DOI 10.1137/1013035
  * (31) Duchi, J., Hazan, E., Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization.  J. Mach. Learn. Res. 12, 2121–2159 (2011)
  * (32) Rosenbrock, H.H.: An Automatic Method for Finding the Greatest or Least Value of a Function.  The Computer Journal 3(3), 175–184 (1960).  DOI 10.1093/comjnl/3.3.175
  * (33) Emiola, I., Adem, R.: Comparison of minimization methods for rosenbrock functions (2021)


# A Study on Edge-Set Graphs of Certain Graphs

Johan Kok  Tshwane Metropolitan Police Department
City of Tshwane, Republic of South Africa
<EMAIL_ADDRESS>N. K. Sudev Department of Mathematics
Vidya Academy of Science & Technology
Thalakkottukara, Thrissur - 680501, India.
<EMAIL_ADDRESS>K. P. Chithra Naduvath Mana, Nandikkara
Thrissur - 680301, India.
<EMAIL_ADDRESS>
###### Abstract

Let $G(V,E)$ simple connected graph, with $|E|=\epsilon$. In this paper, we
define an edge-set graph $\mathscr{G}_{G}$ constructed from the graph $G$ such
that any vertex $v_{s,i}$ of $\mathscr{G}_{G}$ corresponds to the $i$-th
$s$-element subset of $E(G)$ and any two vertices $v_{s,i},v_{k,m}$ of
$\mathscr{G}_{G}$ are adjacent if and only if there is at least one edge in
the edge-subset corresponding to $v_{s,i}$ which is adjacent to at least one
edge in the edge-subset corresponding to $v_{k,m}$, where $s,k$ are positive
integers. It can be noted that the edge-set graph $\mathscr{G}_{G}$ of a graph
$G$ is dependent on both the structure of $G$ as well as the number of edges
$\epsilon$. We also discuss the characteristics and properties of the edge-set
graphs corresponding to certain standard graphs.

Keywords: Edge-set graph, total edge-degree of a graph, edge-degree of vertex,
connected edge dominating set, artificial edge-set element.

Mathematics Subject Classification: 05C07, 05C38, 05C78

##  1 Introduction

For general notation and concepts in graph theory, we refer to [2], [3], [4],
[11]. All graphs mentioned in this paper are simple, connected finite and
undirected graphs unless mentioned otherwise.

Let $\mathbb{N}$ denotes the set of all positive integers. Then, the notion of
a set-graph has been introduced in [6] associated with a given non-empty set,
$A^{(n)}=\\{a_{1},a_{2},a_{3},\ldots,a_{n}\\},n\in\mathbb{N}$ as follows.

######  Definition 1.1.

[6] Let $A^{(n)}=\\{a_{1},a_{2},a_{3},\ldots,a_{n}\\},n\in\mathbb{N}$ be a
non-empty set and the $i$-th $s$-element subset of $A^{(n)}$ be denoted by
$A_{s,i}^{(n)}$. Now consider
$\mathcal{S}=\\{A_{s,i}^{(n)}:A_{s,i}^{(n)}\subseteq
A^{(n)},A_{s,i}^{(n)}\neq\emptyset\\}$. The set-graph corresponding to set
$A^{(n)}$, denoted $G_{A^{(n)}}$, is defined to be the graph with
$V(G_{A^{(n)}})=\\{v_{s,i}:A_{s,i}^{(n)}\in\mathcal{S}\\}$ and
$E(G_{A^{(n)}})=\\{v_{s,i}v_{t,j}:~{}A_{s,i}^{(n)}\cap
A_{t,j}^{(n)}\neq\emptyset\\}$, where $s\neq t~{}\text{or}~{}i\neq j$.

A detailed study on set-graphs has also been done in [6]. Some of the major
results proved in that paper, which are relevant in our present study, are
mentioned in this section.

######  Theorem 1.2.

[6] Let $G_{A^{(n)}}$ be a set-graph. Then, the vertices $v_{s,i},v_{s,j}$ of
$G_{A^{(n)}}$, corresponding to subsets $A^{(n)}_{s,i}$ and $A^{(n)}_{s,j}$ in
$\mathcal{S}$ of equal cardinality, have the same degree in $G_{A^{(n)}}$.

In other words, we can say that the vertices of a set-graph $G_{A^{(n)}}$
corresponding to the equivalent subsets (subsets having same cardinality) of a
non-empty set $A^{(n)}$ have the same degree.

The degree of a vertex in a set-graph has been determined in [6] using the
principle of inclusion and exclusion as follows.

######  Theorem 1.3.

[6] Let $G=G_{A^{(n)}}$ be a set-graph in respect of a non-empty set
$A^{(n)}=\\{a_{1},a_{2},a_{3},\ldots,a_{n}\\},n\in\mathbb{N}$ and let
$v_{k,i}$ be an arbitrary vertex of $G$ corresponding to a $k$-element subset
of $A^{(n)}$. Then,
$d_{G}(v_{k,i})=(\sum\limits_{J}(-1)^{|J|-1}\cdot|\bigcap\limits_{j\in
J}\mathcal{S}_{j}|)-1$, where $J$ is an indexing set such that $\emptyset\neq
J\subseteq\\{0,1,2,\ldots,k\\}$ and $\mathcal{S}_{j}$ is the collection of
subsets of $A^{(n)}$ containing the element $a_{j}$.

The following is an important result regarding the minimal and maximal degree
of vertices in a set-graph and the relation between them.

######  Theorem 1.4.

[6] For any vertex $v_{s,i}$ of a set-graph $G=G_{A^{(n)}}$, we have
$2^{n-1}-1\leq d_{G}(v_{s,i})\leq 2(2^{n-1}-1)$. Moreover, for any set-graph
$G=G_{A^{(n)}},\Delta(G)=2\delta(G)$.

It was also mentioned in [6] that there exists a unique vertex $v_{n,1}$
having degree $\Delta(G)$. Furthermore, it can be seen that $\Delta(G)$ is
always an even number whilst $\delta(G)$ is always an odd number.

Motivated from this study of set-graphs, in this paper, we introduce the
notion of an edge-set graph derived from a given non-empty non-trivial graph
$G$ and study the characteristics and structural properties of the edge-set
graphs of certain standard graphs.

##  2 Edge-Set Graph of a Graph

Let $A$ be a non-empty finite set. We denote $\mathcal{S}$ be the collection
of all $s$-element subsets of $A$ (arranged in some order), where $1\leq
s\leq|A|$, and the $i$-th element $\mathcal{S}$ by $A_{i,s}$. In this paper,
we study certain graphs whose vertices are labeled by distinct elements of the
collection $\mathcal{P}(A)-\\{\emptyset\\}$ in an injective manner. We denote
the vertex of a graph corresponding to the set $A_{s,i}$ by $v_{s,i}$

Using these concepts, similar to the notion of a set-graph, let us first
define the notion of an edge-set graph of a given graph $G$ as follows.

######  Definition 2.1.

Let $G(V,E)$ be a non-empty finite graph with $|E|=\epsilon$ and
$\mathcal{E}=\mathcal{P}(E)-\\{\emptyset\\}$, where $\mathcal{P}(E)$ is the
power set of the edge set $E(G)$. For $1\leq s\leq\epsilon$, let $\mathcal{S}$
be the collection of all $s$-element subsets of $E(G)$ and $E_{s,i}$ be the
$i$-th element of $\mathcal{S}$. Then, the edge-set graph corresponding to
$G$, denoted by $G_{E^{(\epsilon)}}$ or $\mathscr{G}_{G}$, is the graph with
the following properties.

  1. (i)

$|V(\mathscr{G}_{G})|=2^{\epsilon}-1$ so that there exists a one to one
correspondence between $V(\mathscr{G}_{G})$ and $\mathcal{E}$.

  2. (ii)

Two vertices, say $v_{s,i}$ and $v_{t,j}$, in $\mathscr{G}_{G}$ are adjacent
if some elements (edges of $G$) in $E_{s,i}$ is adjacent to some elements of
$E_{t,j}$ in $G$.

From the above definition, it can be seen that the edge-set graph
$\mathscr{G}_{G}$ of a given graph $G$ is dependent not only on the number of
edges $\epsilon$, but the structure of $G$ also. Therefore, we have distinct
edge-set graphs for non-isomorphic graphs of the same size.

As in the case of a set-graph $G_{A^{(n)}}$, it can be observed that an edge-
set graph $\mathscr{G}_{G}$ has an odd number of vertices. It can also be
noted that if $G$ is a trivial graph, then $\mathscr{G}_{G}$ is an empty graph
(since $\epsilon=0$). Also, we have $\mathscr{G}_{P_{2}}=K_{1}$ and
$\mathscr{G}_{P_{3}}=C_{3}$.

In this paper, we use the following conventions.

  1. (i)

If an edge $e_{j}$ is incident with vertex $v_{k}$, then we write it as
$(e_{j}\to v_{k})$.

  2. (ii)

If the edges $e_{i}$ and $e_{j}$ of a graph $G$ are adjacent, then we write it
as $e_{i}\cong e_{j}$.

  3. (iii)

The $n$ vertices of the path $P_{n}$ are positioned horizontally and the
vertices and edges are labeled from left to right as
$v_{1},v_{2},v_{3},\ldots,v_{n}$ and $e_{1},e_{2},e_{3},\ldots,e_{n-1}$,
respectively.

  4. (iv)

The $n$ vertices of the cycle $C_{n}$ are seated on the circumference of a
circle and the vertices and edges are labeled clockwise as
$v_{1},v_{2},v_{3},\ldots,v_{n}$ and $e_{1},e_{2},e_{3},\ldots,e_{n}$,
respectively such that $e_{i}=v_{i}v_{i+1}$, in the sense that
$v_{n+1}=v_{1}$.

Analogous to the degree of a vertex in a given graph $G$, we define the edge-
degree of elements (vertices or edges) in $G$ as follows.

######  Definition 2.2.

For a graph $G$ with edges $E(G)=\\{e_{i}:1\leq i\leq\epsilon\\}$, the edge-
degree of an edge $e_{i}$ of $G$ incident with vertex $v_{k}$ is equal to the
number of edges $e_{j}\to v_{k},e_{i}\neq e_{j}$ and denoted by
$d_{G(v_{k})}(e_{i})$. If the edge $e_{i}$ is incident with vertices
$v_{k},v_{l}$, then the general edge-degree of $e_{i}$ is defined to be
$d_{G}(e_{i})=d_{G(v_{k})}(e_{i})+d_{G(v_{l})}(e_{i})=d_{G}(v_{k})+d_{G}(v_{l})-2$.
(Also see [1]).

Similarly, the edge-degree of a vertex of a given graph $G$ is defined as
follows.

######  Definition 2.3.

For a graph $G$ with edges $E(G)=\\{e_{i}:1\leq i\leq\epsilon\\}$ the edge-
degree of a vertex $v_{i}$, denoted by $d_{G(e)}(v_{i})$, is defined as
$d_{G(e)}(v_{i})=\sum\limits_{(e_{l}\to v_{i})}d_{G(v_{i})}(e_{l})$.

Using the above definitions, we introduce the notion of the total edge-degree
of a graph as follows.

######  Definition 2.4.

The total edge-degree of a graph G, denoted by $d^{t}_{G(e)}(G)$, is defined
by $d^{t}_{G(e)}(G)=\sum\limits_{v_{i}\in V(G)}d_{G(e)}(v_{i})$.

Invoking these definitions given above, it can be noticed that both
$d^{t}_{G(e)}(G)$ and $d_{G(e)}(v_{i})$ are single values, while
$d_{G(v_{k})}(e_{j})\leq d_{G(v_{m})}(e_{j}),(e_{j}\to v_{k}),(e_{j}\to
v_{m})$.

######  Illustration.

The graphs having three edges $e_{1},e_{2},e_{3}$ are graphs $P_{4},C_{3}$,
and $K_{1,3}$. The corresponding edge-set graphs on the vertices
$v_{1,1}=\\{e_{1}\\},v_{1,2}=\\{e_{2}\\},v_{1,3}=\\{e_{3}\\},v_{2,1}=\\{e_{1},e_{2}\\},v_{2,2}=\\{e_{1},e_{3}\\},v_{2,3}=\\{e_{2},e_{3}\\},v_{3,1}=\\{e_{1},e_{2},e_{3}\\}$
are depicted below.

(a) $\mathscr{G}_{P_{4}}$

(b) $\mathscr{G}_{C_{4}}=\mathscr{G}_{K_{1,3}}=K_{7}$

Figure 1:

We notice that both $\mathscr{G}_{C_{3}}$ and $\mathscr{G}_{K_{1,3}}$ are
complete graphs. This observation follows from results to follow. The
following is a straight forward result and an important property of edge-set
graphs as well.

######  Proposition 2.5.

The induced graph $\langle\\{v_{1,i}:1\leq i\leq\epsilon\\}\rangle$ of the
edge-set graph $\mathscr{G}_{G}$ is isomorphic to the line graph of $G$.

###### Proof.

Let $\mathscr{G}_{G}$ the edge-set graph of a given graph $G$. Then, every
vertex $v_{1,i}$ of $\mathscr{G}_{G}$ corresponds to the singleton subset
$\\{e_{i}\\}$ of $E(G)$, where $1\leq i\leq\epsilon$ and two vertices
$v_{1,i}$ and $v_{1,j}$ of $\mathscr{G}_{G}$ are adjacent in $\mathscr{G}_{G}$
if and only if the corresponding edges $e_{i}$ and $e_{j}$ are adjacent in
$G$. Hence, the induced graph $\langle v_{1,i};1\leq i\leq\epsilon\rangle$ of
the edge-set graph $\mathscr{G}_{G}$ is isomorphic to $L(G)$. ∎

Analogous to the corresponding theorem on the relation between the minimum and
maximum degree of vertices in a set-graph, we propose the following theorem.

######  Theorem 2.6.

For the edge-set graph $\mathscr{G}_{G}$, $\epsilon\geq 1$ corresponding to a
given graph $G$, we have $\Delta(\mathscr{G}_{G})=2(2^{\epsilon-1}-1)$ and
$\delta(\mathscr{G}_{G})\geq 2(\epsilon-1)$.

###### Proof.

First part of the Theorem follows immediately by Theorem 1.4, we have
$\Delta(\mathscr{G}_{G})=2(2^{\epsilon-1}-1)$.

Next, note that the graph $G$ with $\epsilon$ edges, with
$\min\\{d^{t}_{G(e)}(G)\\}=2(\epsilon-1)$ is the path $P_{\epsilon+1}$. It can
be verified that for $P_{n},2\leq n\leq 4$,
$\delta(\mathscr{G}_{P_{\epsilon+1}})=2(\epsilon-1)$, where $\epsilon=1,2,3$.
For $P_{5}$, we have
$d^{t}_{P_{5}(e)}(P_{5})=2(4-1)=6<8=\delta(P_{5,E^{(4)}})$. In a similar way,
by mathematical induction, the result
$2(\epsilon-1)\leq\delta(P_{(\epsilon+1),E})\leq\delta(\mathscr{G}_{G})$,
$\epsilon\geq 1$ follows. ∎

The following theorem describes the condition required for an edge-set graph
to be a complete graph.

######  Theorem 2.7.

For $\epsilon\geq 4$, the edge-set graph of a given graph $G$ is complete if
and only if $G\cong K_{1,\epsilon}$. In other words, the edge-set graph of a
graph $G$, with more than three edges, is a complete graph if and only if $G$
is a star graph.

###### Proof.

First consider the graph $G=K_{1,4}$, whose central vertex is denoted by $u$
and the other vertices are denoted by $v_{1},v_{2},v_{3},v_{4}$ respectively.
Let the edges of $G$ be given by $e_{i}=uv_{i};~{}1\leq i\leq 4$. Clearly, the
number of non-empty subsets of $E(K_{1,4})$ is given by $2^{4}-1$ and each
subset has at least one edge $e_{i}\in E(K_{1,4})$ adjacent to at least one
edge $e_{j}\in E(K_{1,4})$ in each of the other subsets. Hence, pairwise there
exists an edge $v_{s,i}v_{t,j}$ for all $s$-element and $t$-element subsets of
$E(K_{1,4})$. Hence, $K_{(1,4),E^{(4)}}$ is complete. Now, assume that the
results holds for $G=K_{1,k}$, $k$ being a positive integer greater than $4$.
Now, consider the graph $G=K_{1,(k+1)}$ with $u$ as the central vertex and
$v_{k+1}$ the new vertex in $K_{1,(k+1)}$ that is not in $K_{1,k}$. Then, the
new edge $e_{k+1}=uv_{k+1}$ is adjacent to all other edges in $G$ and hence
the vertices in the edge-set graph with the set-label containing the element
$e_{k+1}$ will also be adjacent to all other vertices of the edge-set graph
$\mathscr{G}_{K_{1,k+1}}$. Therefore, $\mathscr{G}_{K_{1,k+1}}$ is also a
complete graph. Hence, by mathematical induction, the result holds for all
$K_{1,\epsilon},\epsilon\geq 4$.

Conversely, assume the edge-set graph
$\mathscr{G}_{G},~{}|V(\mathscr{G}_{G})|=2^{\epsilon}-1\geq 15$ is complete.
Therefore, $\mathscr{G}_{G}-v_{\epsilon,1}$ on
$2^{\epsilon}-2=\frac{1}{2}(2^{\epsilon+1}-1)$ vertices is complete as well.
Applying the inverse of Definition 2.1, to $\mathscr{G}_{G}-v_{\epsilon,1}$
results in a smallest graph $K_{1,\epsilon}$. Assume the edge-set graph
$\mathscr{G}_{G}$ also corresponds to $K_{1,\epsilon}+v_{i}v_{j}$ with
$v_{i}v_{j}$ an arbitrary additional edge. Now, we must consider an edge-set
graph on $2^{\epsilon+1}-1>\frac{1}{2}(2^{\epsilon+1}-1)+1$ edge-subsets. The
aforesaid edge-set graph is not isomorphic to the initial graph
$\mathscr{G}_{G},|V(\mathscr{G}_{G})|=2^{\epsilon}-1\geq 15$. Hence,
$K_{1,\epsilon}$ is the unique graph corresponding to the complete edge-set
graph, $\mathscr{G}_{G},|V(\mathscr{G}_{G})|=2^{\epsilon}-1\geq
15\Rightarrow\epsilon\geq 4$. This completes the proof. ∎

It can be followed that the edge-set graphs corresponding to $K_{1,1},K_{1,2}$
and $K_{1,3}$ are complete. Furthermore, for any edge $e_{i}$ in the cycle
$C_{n},n\geq 4$ there is exactly $n-3$ edges which are not adjacent to
$e_{i}$. By Theorem 2.3, $\mathscr{G}_{C_{n}}$ is not complete. Hence, $C_{3}$
is the only cycle for which the corresponding edge-set graph is complete.

######  Theorem 2.8.

For $\epsilon=n\geq 2$, we have $\sum\limits_{v_{i,j}\in
V(\mathscr{G}_{G})}d_{\mathscr{G}_{G}}(v_{i,j})>\sum\limits_{v_{i,j}\in
V(G_{A^{(n)}})}d_{G_{A^{(n)}}}(v_{i,j})$.

###### Proof.

Since paths have the minimally connectivity, we first prove the result for
paths. It is to be noted that For $\epsilon=n=2$, we have
$\mathscr{G}_{P_{3}}\cong K_{3}$ and $G_{A^{(2)}}\cong P_{3}$.
Hence,$\sum\limits_{v_{i,j}\in
V(\mathscr{G}_{P_{3}})}d_{\mathscr{G}_{P_{3}}}(v_{i,j})\geq\sum\limits_{v_{i,j}\in
V(\mathscr{G}_{P_{3}})}d_{\mathscr{G}_{P_{3}}}(v_{i,j})=6>4=\sum\limits_{v_{i,j}\in
V(G_{A^{(2)}})}d_{G_{A^{(2)}}}(v_{i,j})$.

Assume the result holds for all paths $P_{k+1}$ hence, by implication it holds
for all graphs $G$ on $\epsilon=n=k$ edges.

Now consider $P_{k+2}=P_{k+1}+e_{k+1}$. Note that that in the set-graph
$G_{A^{(k+1)}}$, singleton subsets are pairwise non-adjacent (see [6]) while
in an edge-set graph some pairs of singleton edge-subsets are adjacent if and
only if the corresponding edges are adjacent in $G$. Hence, it can be noted
that
$d_{\mathscr{G}_{P_{k+2}}}(v_{1,k+1})=d_{G_{A^{(k+1)}}}(v_{1,k+1})+1>d_{G_{A^{(k+1)}}}(v_{1,k+1})$.
Hence, $\delta(\mathscr{G}_{P_{k+2}})>\delta(G_{A^{(k+1)}})$. Similarly, we
have $d_{\mathscr{G}_{P_{k+2}}}(v_{s,i})\geq d_{G_{A^{(k+1)}}}(v_{s,i})$,
$\forall s,i$. We also note that $G_{A^{(k+1)}}$ has a unique vertex having
degree equal to $\Delta(G_{A^{(k+1)}})$ (see [6]) when the edge-set graph
$\mathscr{G}_{P_{k+2}}$ has four such vertices. Hence, we have
$\sum\limits_{v_{i,j}\in
V(\mathscr{G}_{P_{k+2}})}d_{\mathscr{G}_{P_{k+2}}}(v_{i,j})>\sum\limits_{v_{i,j}\in
V(G_{A^{(k+1)}})}d_{G_{A^{(k+1)}}}(v_{i,j})$. Therefore, the result follows
for all paths by mathematical induction.

Since all other connected graphs have higher connectivity than paths, the
result, $\sum\limits_{v_{i,j}\in
V(\mathscr{G}_{G})}d_{\mathscr{G}_{G}}(v_{i,j})>\sum\limits_{v_{i,j}\in
V(G_{A^{(n)}})}d_{G_{A^{(n)}}}(v_{i,j})$, holds for any connected graphs. ∎

In [6], it is proved that there exists a unique vertex $v_{n,1}$ in a set-
graph $G_{A^{(n)}}$ having degree $\Delta(G_{A^{(n)}})$. In edge-set graphs,
the analogous result does not hold. In order to discuss the existence of
multiple vertices with the maximum degree in an edge-set graph,we need the
following definition.

######  Definition 2.9.

A connected edge dominating set of a graph $G$ is an edge dominating set
$X\subseteq E(G)$ where the induced graph $\langle X\rangle$ is a connected
subgraph of $G$. The minimum number of elements in a connected edge dominating
set of a graph $G$ is called the connected edge domination number (CED-number)
of $G$.

In view of this definition, we have the following theorem.

######  Theorem 2.10.

Let $X$ be a connected edge dominating set of a graph $G$ with $\epsilon\geq
2$ and let $V_{X}(\mathscr{G}_{G})$ be the the subset of vertex set of the
edge-set graph $\mathscr{G}_{G}$ defined by
$V_{X}(\mathscr{G}_{G})=\\{v_{s,i}:E_{s,i}\in\mathcal{S},X\subseteq
E_{s,i}\\}$. Then, we have
$d_{\mathscr{G}_{G}}(v_{s,i})=\Delta(\mathscr{G}_{G}),\forall v_{s,i}\in
V_{X}(\mathscr{G}_{G})$.

###### Proof.

By the choice of $X$, it is the set-labels of some element in
$V_{X}(\mathscr{G}_{G})$. Consider any edge $e_{j}\in E(G)$. Then, we consider
the following cases.

Case-1: If $e_{j}\in X$, then there exists a vertex, say $v_{l,k}$, in
$\mathscr{G}_{G}$ corresponding to $X$, which is adjacent to all other
vertices corresponding to the edge-subsets $E_{s,i}$ containing the edge
$e_{j}$. Since $X$ is an edge dominating set onto itself, this argument holds
for all edges in $X$.

Case-2: Since $X$ is an edge dominating set, all edges in $E(G)-X$ are
adjacent to some edges in $X$. If $e_{j}\in E(G)-X$, then a similar argument
holds.

From the above two cases, we can see that any arbitrary vertex $v_{l,k}$ of
$V_{X}(\mathscr{G}_{G})$ is adjacent to all vertices in $\mathscr{G}_{G}$.
Hence, we have $d_{\mathscr{G}_{G}}(v_{s,i})=\Delta(\mathscr{G}_{G})$. ∎

######  Remark 2.11.

The edge-set $E(G)$ is the set-label of some vertex in $V(\mathscr{G}_{G})$
and for any edge $e_{i}\in E(G),i\leq\epsilon$, the edge-subsets $E(G)-e_{i}$
are connected edge dominating sets in $G$. Hence, we have
$d_{\mathscr{G}_{G}}(v_{\epsilon,1})=\Delta(\mathscr{G}_{G})$ and
$d_{\mathscr{G}_{G}}(v_{\epsilon-1,j})=\Delta(\mathscr{G}_{G})$.

By Theorem 2.7, we note that the edge-set graphs corresponding to paths,
cycles and complete graphs are not complete graphs. Hence, determining the
maximum and minimum degrees of the corresponding edge-set graphs arouses much
interest in this context.

Let us now introduce the notion of connected edge domination index of a given
graph as follows.

######  Definition 2.12.

The connected edge domination index (CED-index) of a graph $G$ is defined as
the number of smallest connected edge dominating sets in $G$ and is denoted by
$\mathfrak{E}(G)$.

The CED-indices of paths, cycles and complete graphs are determined in the
following results.

######  Proposition 2.13.

The CED-index of a path $P_{n}$ is $1$.

###### Proof.

The path $P_{n}$, $n\geq 3$ has exactly three connected edge dominating sets,
namely $\\{e_{1},e_{2},e_{3},\ldots,e_{n-2}\\}$,
$\\{e_{2},e_{3},e_{4},\ldots,e_{n-1}\\}$ and
$\\{e_{2},e_{3},e_{4},\ldots,e_{n-2}\\}$. Clearly, the third set is the
smallest connected edge dominating set. That is, number of minimal connected
edge dominating set $\mathfrak{E}(P_{n})=1$. ∎

######  Proposition 2.14.

The CED-index of a cycle $C_{n}$ is $n$.

###### Proof.

Consider the set of edge pairs $\mathfrak{S}=\\{\\{e_{i},e_{i+1}\\}:1\leq
i\leq n\\}$ of the cycle $C_{n}$, in the sense that $e_{n+1}=e_{1}$. Clearly,
$E(C_{n})-\\{e_{i},e_{j}\\}$, $\forall\\{e_{i},e_{j}\\}\in\mathfrak{S}$ are
all smallest connected edge dominating sets of $C_{n}$. Hence, we have
$\mathfrak{E}(C_{n})=n$. ∎

######  Proposition 2.15.

The CED-index of a complete graph is $\frac{n}{2}(n-1)!$.

###### Proof.

It is known that $K_{n},n\geq 3$ has $\frac{1}{2}(n-1)!$ distinct Hamiltonian
cycles (see [7]). Also, a minimal connected edge dominating set of a
Hamiltonian cycle of $K_{n}$ is also a smallest connected edge dominating set
of $K_{n}$. By Proposition 2.14, we have
$\mathfrak{E}(K_{n})=\frac{n}{2}(n-1)!$. ∎

In the proof of Proposition 2.13 it was noted that $P_{n}$, $n\geq 3$ has
exactly three connected edge dominating sets hence, $\mathscr{G}_{P_{n}}$ has
exactly four vertices with maximum degree. Let $\mathfrak{M}(\mathscr{G}_{G})$
denote the number of vertices of $\mathscr{G}_{G}$ having the maximum degree
$\Delta(\mathscr{G}_{G})$.

The number of maximum degree vertices in the edge-set graphs corresponding to
the graphs $C_{n}$ and $K_{n}$ are determined in the following results.

######  Proposition 2.16.

The number of maximum degree vertices in the edge-set graph of $C_{n}$ is
$3n+1$.

###### Proof.

Without loss of generality, any smallest connected edge dominating set of
$C_{n}$ say, $\\{e_{2},e_{3}.e_{4},\ldots,e_{n-1}\\}$ can be extended to a
larger connected edge dominating set, say
$\\{e_{2},e_{3},e_{4},\ldots,e_{n-1},e_{n}\\}$ or
$\\{e_{1},e_{2},e_{3},\ldots,e_{n-1}\\}$. Hence, an additional $2n$ such
extended edge sets exists. $E(C_{n})$ is also a connected edge dominating set
as well so invoking Proposition 2.14, implies $\mathfrak{M}(C_{n})=3n+1$. ∎

######  Proposition 2.17.

The number of maximum degree vertices in the edge-set graph of $K_{n}$ is
$\frac{1}{2}(3n+1)(n-1)!$.

###### Proof.

Similar to the reasoning in the above proposition, each of the
$\frac{1}{2}(n-1)!$ Hamiltonian cycles in $K_{n}$ is a connected edge
dominating set of $K_{n}$. Also, each of the smallest connected edge
dominating sets can be extended in the manner shown in Proposition 2.16.
Hence,
$\mathfrak{M}(C_{n})=3\frac{n}{2}(n-1)!+\frac{1}{2}(n-1)!=(\frac{3n+1}{2})(n-1)!$.
∎

The next result is another obvious but important property of edge-set graphs,
which leads to an interesting result in respect of regular graphs.

######  Theorem 2.18.

Let $e$ be an edge of a graph $G$ having the minimum edge degree in $G$. Then,
the vertex $v$ in $\mathscr{G}_{G}$ corresponding to the singleton edge-subset
$\\{e\\}$ has minimum degree in $\mathscr{G}_{G}$.

###### Proof.

Assume that the edge $e$ has minimum edge-degree $d_{G}(e)=l$. Label the edges
adjacent to $e$ as $f_{1},f_{2},f_{3},\ldots,f_{l}$. From the definition edge-
set graphs, it follows that a vertex $v$ is adjacent to $v_{s,i}$ if and only
if some of these edges $f_{i}$ belongs to $E_{s,i}$. This number of edges that
are adjacent to $e$ in $G$ is equal to the degree of $v$ in $\mathscr{G}_{G}$.

Now, assume there exists a vertex $v_{t,j}$ with
$d_{\mathscr{G}_{G}}(v_{t,j})=\delta(\mathscr{G}_{G})<d_{\mathscr{G}_{G}}(v)$.
It implies that by Definition 2.1, the vertex $v_{t,j}$ is adjacent to
$v_{k,m}$ if and only if some or all edges $g_{1},g_{2},g_{3},\ldots,g_{s}$,
which are in $E_{k,m}$ and an edge $e^{\ast}\in E_{t,j}$ is adjacent to an
edge $g_{i}\in E_{k,m}$, with $s<l$ and $d_{G}(g_{i})<s$. This contradicts the
assumption that $d_{G}(e)$ has minimum degree in $G$. Hence,
$d_{\mathscr{G}_{G}}(v)=\delta(\mathscr{G}_{G})$. ∎

As an immediate consequence of Theorem 2.18, we observe that the edge-set
graph $\mathscr{G}_{G}$ corresponding to an $r$-regular graph $G$ has
$\epsilon$ vertices, $v_{1,1},v_{1,2},v_{1,3},\ldots,v_{1,\epsilon}$, with
degree equal to $\delta(\mathscr{G}_{G})$. Also, we note that an edge $e$ is
adjacent to exactly $d_{G}(e)$ edges in $G$. Therefore, there are exactly
$\epsilon-d_{G}(e)$ edges that are not adjacent to the edge $e$ in $G$. This
leads us to the following result.

######  Proposition 2.19.

The degree of the vertex $v_{1,i}$ corresponding to $\\{e_{i}\\}$ in
$\mathscr{G}_{G}$ is given by
$d_{\mathscr{G}_{G}}(v_{1,i})=2^{\epsilon}-2^{\epsilon-d_{G}(e_{i})}$.

###### Proof.

The edge-set graph $\mathscr{G}_{G}$ has $2^{\epsilon}-1$ vertices. Exactly
$2^{\epsilon-d_{G}(e_{i})}-1$ edge-subsets do not contain an edge adjacent to
$e_{i}$ as an element. Hence, exactly $2^{\epsilon}-2^{\epsilon-d_{G}(e_{i})}$
edge-subsets do contain an edge adjacent to $e_{i}$ as an element. Therefore,
the degree of the vertex $v_{1,i}$ in $\mathscr{G}_{G}$ is
$2^{\epsilon}-2^{\epsilon-d_{G}(e_{i})}$. ∎

As a consequence of Proposition 2.19, an $r$-regular graph $G$ on $\nu$
vertices has
$\delta(\mathscr{G}_{G})=2^{\frac{1}{2}r\nu}(1-\frac{1}{2^{\frac{1}{2}(r-1)}})$.

Let us now recall the well-known theorem on Eulerian graphs.

######  Theorem 2.20.

[5] A connected graph $G$ is Eulerian if and only if $G$ has no odd degree
vertices.

In view of Theorem 2.20, we establish Eulerian nature of the edge-set graphs
in the following theorem.

######  Theorem 2.21.

The edge-set graph of any connected graph $G$ is an Eulerian graph.

###### Proof.

Let $\mathscr{G}_{G}$ is the edge-set graph of a given graph $G$ with
$\epsilon$ edges. Note that the number of subsets of $E(G)$ containing the
same $r$ edges is $2^{\epsilon-r}$, where $r\leq\epsilon$, which is always an
even integer.

Let $e_{i}$ be an arbitrary edge of $G$. Since $G$ is a connected graph, the
edge $e_{i}$ is adjacent to at least one edge in $G$. Without loss of
generality, let the edge $e_{i}$ is adjacent to $r$ edges in $G$, where $r\geq
1$. Let $e_{j_{1}},e_{j_{2}},e_{j_{3}},\ldots,e_{j_{r}}$ be the $r$ edges in
$E(G)$ that are adjacent to $e_{i}$ in $G$ Then, every vertex $v$ in
$\mathscr{G}_{G}$, whose set-label contain the element $e_{i}$ must be
adjacent to the vertices of $\mathscr{G}_{G}$, whose set-labels contain at
lease one element $e_{j_{l}}$, where $1\leq l\leq r$. Let $E_{l}$ denotes the
subset of $E(G)$ containing the element $e_{j_{l}}$. Then, by the principle of
inclusion and exclusion, we have the number of vertices in $G_{G}$ that are
adjacent to the vertex $v$ is
$|\bigcup\limits_{l=1}^{r}E_{j_{l}}|=\sum\limits_{L}(-1)^{|L|-1}|\bigcap\limits_{l\in
L}E_{j_{l}}|$, where $\emptyset\neq L\subseteq\\{1,2,3,\ldots,r\\}$. Note that
every term in the above series is an even integer and as a result
$d_{\mathscr{G}_{G}}(v)$ is always an even integer. Since $e_{i}$ is an
arbitrary edge of $G$, $v$ is also an arbitrary vertex (corresponding to the
choice of $e_{i}$) of $G_{G}$ and hence every vertex of $G_{G}$ is an even
degree vertex. Then, by Theorem 2.20, $G_{G}$ is an Eulerian graph. ∎

##  3 Conclusion and Scope for Further Studies

So far we have discussed the properties and characteristics of a new types of
graphs called edge-set graphs derived from the edge sets of given graphs. This
study is only a preliminary study on edge-set graphs and several related areas
still remain to be explored. In this paper, we have established certain
results for paths, cycles and complete graphs only. Extending these results to
more standard graphs are much interesting and challenging problems. More
fruitful results are expected on certain edge-set graphs on the effective
utilisation of Definitions 2.2, Definitions 2.3 and Definitions 2.4 to more
graph classes.

It seems to be worthy and promising for future studies on the relationship
between $\mathscr{G}_{G}$, $\mathscr{G}_{G+e}$ and, where $G+e$ is the graph
obtained by joining two non-adjacent vertices in $G$ by the edge $e$. The
results related to the edge-set graphs of the graphs obtained by different
graph operations are also open. Another important area that offer much for
further investigations is the study on the edges of the edge-set graphs and
set-graphs of given graphs. More studies are possible on the comparison of the
set-graphs and edge-set graphs derived from the edge sets of different graphs.
All these facts highlight the wide scope for further research in this area.

## References

  * [1] S. Arumugam and S. Velammal, Edge Domination in Graphs, Taiwanese Journal of Mathematics, 2(2)(1998), 173-179.
  * [2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, London, 1976.
  * [3] G. Chartrand and L. Lesniak, Graphs and Digraphs, CRC Press, 2000.
  * [4] J. T. Gross and J. Yellen, Graph Theory and its Applications, CRC Press, 2006.
  * [5] F. Harary, Graph Theory, Addison-Wesley, 1994.
  * [6] J. Kok, K. P. Chithra, N. K. Sudev and C. Susanth, A Study on Set-Graphs, International Journal of Computer Applications, 118(7)(2015), 1-5., DOI: 10.5120/20754-3173.
  * [7] J Kratochvil, D. Zeps, On the Number of Hamilton cycles in Triangulations, Journal of Graph Theory, 12(2)(1988), 191-194.
  * [8] T. A. McKee and F. R. McMorris, Topics in Intersection Graph Theory, SIAM, Philadelphia, 1999.
  * [9] K. H. Rosen, Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.
  * [10] S. K. Vaidya and R. M. Pandit, Edge Domination in Some Path and Cycle Related Graphs, ISRN Discrete Mathematics, 2014 (2014), Article ID: 975812, 1-5., DOI: 10.1155/2014/975812.
  * [11] D. B. West, Introduction to Graph Theory, Pearson Education Inc., 2001.