Dynamic Regret for Online Composite Optimization

$V(T)$ is used to solve problems where cost functions may change along a non-stationary variant of a sequential stochastic optimization. It has been obtained minimax regret bounds $\mathcal{O}(T^{\frac{2}{3}}V(T)^{\frac{1}{3}})$ and $\mathcal{O}(T^{\frac{1}{2}}V(T)^{\frac{1}{2}})$ for convex and strongly convex functions, respectively, in a non-stationary setting under noisy gradient access[20].

where $\{M_{1},M_{2},...,M_{T}\}$ is computed accroding to the past observations or side information. For instance, one of the choice could be $M_{t}=\nabla F_{t-1}(u_{t-1})$[21]. This work about online Frank-Wolfe algorithm established $\mathcal{O}(\sqrt{T}(1+V(T)+\sqrt{F(T)}))$ dynamic regret for convex and smooth loss function in non-stationary settings.

If the reference points move slowly, $S(T)$ may be smaller than $D(T)$. On the contrary, $D(T)$ may be smaller than $S(T)$. Specially, $D(T)$ and $S(T)$ are also utilized to represent those variations in the optimal points $x_{t}^{*}:=arg\min_{x\in\mathcal{X}}f_{t}(x)$[22, 23]. Related works on path variation are significantly more than the first two. Earlier research on OGM showed that the dynamic regret has an upper bound $\mathcal{O}(\sqrt{T}(D(T)+1))$ for convex cost functions[17]. Then, authors improved that there exists a lower bound $\mathcal{O}(\sqrt{T(D(T)+1)})$[24]. By adding strict conditions, a regret bound of order $\mathcal{O}(D(T)+1)$ was established for strongly and smooth convex loss functions[25]. Another study on Online Multiple Gradient Descent for smooth and strongly convex functions improved the regret bound to $\mathcal{O}(min(D(T),S(T)))$[23].

where $0\leqslant\beta<1$[26]. Larger weights are allocated for the future parts than the previous parts. When $\beta=0$, $D_{0}(T)$ is equal to $D(T)$ and when $0<\beta<1$, $D_{0}(T)<D_{\beta}(T)<T^{\beta}D_{0}(T)$. Therefore, $D_{\beta}(T)$ is an extension of $D(T)$. In the literature, online optimization based on $D_{\beta}(T)$ is few. One related work using $D_{\beta}(T)$ is on proximal online gradient algorithm[26]. The authors established a dynamic regret of order $\mathcal{O}(\sqrt{T^{1-\beta}D_{\beta}(T)}+\sqrt{T})$ for convex loss functions.

In addition, there are plenty of works studying about online composite optimization. In [28], inexact online proximal gradient algorithm was proposed for loss functions composed of strongly convex, smooth term and convex term, where the loss relies on the estimated gradient information of the smooth convex function and the approximate proximal operator. Coincidentally, for allowing the loss functions to be subsampled, inexact gradient was added into online proximal gradient algorithm for a finite sum of composite functions[29]. When both algorithms are applied to the exact gradient case, the upper bounds are both in order of $\mathcal{O}(1+D(T))$. Furthermore, considering inexact scenarios by approximate gradients, approximate proximal operator and communication noise[30], online inexact distributed proximal gradient method (DPGM) guaranteed Q-linearly convergence to the optimal solution with some error. Decentralized algorithms are also proposed for solving composite optimization, as the composite loss function of each agent may be held privately. An unconstrained problem is considered firstly. An online DPGM was proposed in [27] for each private cost function composed of strongly convex, smooth function and convex nonsmooth regularizer, obtaining a regret bound of order $\mathcal{O}(\log T(1+D(T)))$. Later, some works use mirror descent algorithm for constrained problems. A distributed online primal-dual mirror descent algorithm is developed to handle composite objective functions, which consist of local convex functions and regularizers with time-varying coupled inequality constraints[31].

In this paper, we revisit OPG algorithm for composite functions with a time-varying regularizer and discuss dynamic regret in terms of $D_{\beta}(T)$. Most related works about OPG consider a time-invariant $r(x)$[26, 32, 33, 34, 35], while our problem extends the stationary regularizer to time-varying scenario.

The contributions of this paper include: (a) solving online composite optimization problems with two time-varying nonsmooth parts in terms of $D_{\beta}(T)$; (b) obtaining a best-known dynamic regret bound for composite functions with two convex but nondifferentiable functions; (c) establishing a dynamic regret bound of OPG for functions composed of a strongly convex term and a convex but nondifferentiable term.

The paper is organized as follows. Section II describes the online composite optimization problem. In Section III, OPG algorithm is introduced, necessary assumptions are presented and main results are provided for two cases. Numerical examples of the OPG algorithm are given in Section IV. The conclusions are presented in Section V.

Notations: Let $\lVert\cdot\rVert_{1}$ represent the $\cal{l}_{1}$ norm and $\lVert\cdot\rVert$ represent the $\cal{l}_{2}$ norm by default. $\partial f(x)$ denotes the subdifferential of a convex function $f$ at $x$ and $\tilde{\nabla}f(x)$ represents one subgradient in $\partial f(x)$. Let $[N]:=\{1,2,...,N\}$. Let $\langle\cdot,\cdot\rangle$ be the Euclidean inner product on $\mathbb{R}^{n}$.

In machine learning, signal processing and statistics, many nonsmooth error functions have a wide range of applications for solving regression and classification problems[36]. In online streaming data-generating process, the probability density function may change with time[37]. There are some examples for online nonsmooth convex loss functions, by setting $y_{t}$ as label and $a_{t}$ as feature vector.

• •

  Hinge loss:

  $$f_{t}(x)=max(0,1-y_{t}a_{t}^{\top}x).$$

• •

  Generalized hinge loss:

  $$f_{t}(x)=\left\{\begin{aligned} &1-\alpha y_{t}a_{t}^{\top}x,~{}~{}&if~{}y_{t}a_{t}^{\top}x\leqslant 0\\ &1-y_{t}a_{t}^{\top}x,~{}~{}&if~{}0<y_{t}a_{t}^{\top}x<1\\ &0,~{}~{}&if~{}y_{t}a_{t}^{\top}x\geqslant 1,\end{aligned}\right.$$

  where $\alpha>1$.

• •

  Absolute loss:

  $$f_{t}(x)=max_{\alpha\in[-1,1]}\alpha(y_{t}-a_{t}^{\top}x).$$

• •

  $\epsilon$-insensitive loss:

  $$f_{t}(x)=max(|y_{t}-a_{t}^{\top}x|-\epsilon,0),$$

  where $\epsilon$ is a small postive constant.

• •

  The weighted $\cal{l}_{1}$ norm function:
  Assume the optimal solution is sparse with many zero or near-zero coefficients. To solve it, let $r_{t}(x)$ be the weighted $\cal{l}_{1}$ norm function[38, 39, 40]:

  $\displaystyle r_{t}(x):=\rho\sum_{i=1}^{N}\omega_{i}^{t}|x_{i}|,$

  (4)

  where $x_{i}$ is the $i$-th component of $N$-dimensional $x$ and $\rho>0$ is a parameter for regularizers. The weight $\omega_{i}^{t}$ $(i=1,2,...,N)$ is defined by

  $$\omega_{i}^{t}:=\left\{\begin{aligned} \epsilon,&~{}~{}if~{}|x_{i}^{t-1}|>\tau\\ 1,&~{}~{}otherwise,\end{aligned}\right.$$

  with a parameter $\tau>0$ and a small $\epsilon>0$, where $x_{i}^{t-1}$ is $t-1$-th iteration of $x_{i}$ by any proposed algorithm. The parameter $\tau$ may rely on noise statistics, e.g., the variance. By introducing the weights $\omega_{i}^{t}$, larger $|x_{i}|$ has smaller coefficients. Hence, larger $|x_{i}|$ renders a less sensitivity to the impact of the proximity operator. Therefore, the weighted $\cal{l}_{1}$ norm exploits the sparseness more efficiently.

• •

  The indicator function of time-varying set constraints:
  In a network flow problem, to handle the constraints $x\in\cal{X}_{t}$ with $\cal{X}_{t}\subset\cal{X}$ being a convex set, the authors in [28] use indicator functions based on a given network $(\cal{N},\mathcal{E})$. The relevant variables are defined as follows. $z(i,s)$ denotes the rate produced at node $i$ for traffic $s$ and $x(ij,s)$ is the flow between nodes $i$ and $j$ for traffic $s$. For brevity, let $z$ and $x$ be the stacked traffic and link rates, respectively. Time-varying nonsmooth $r_{t}(z,x)$ is composed of two functions $r(z,x)$ and $\delta_{\cal{X}_{t}}(z,x)$, where $r(z,x)=\frac{\nu}{2}(\lVert z\lVert^{2}+\lVert x\lVert^{2})$ is convex with some $\nu>0$ and $\delta_{\cal{X}_{t}}(z,x)$ is an indicator function of constraints, defined as

  $$\delta_{\cal{X}_{t}}(z,x):=\left\{\begin{aligned} +\infty,&~{}~{}x\notin\cal{X}_{t}\\ 0,&~{}~{}x\in\cal{X}_{t}.\end{aligned}\right.$$

  Here are the relevant constraints in the netwrok. The capacity constraint for link is $0\leqslant\sum_{s}x(ij,s)+w_{t}(ij)\leqslant c_{t}(ij)$, where $c_{t}(ij)$ is the time-varying link capacity and $w_{t}(ij)$ is a time-varying and non-controllable link traffic. The flow conservation constraint implies $z(s)=\bar{R}x(s)$ with the routing matrix $\bar{R}$. $z^{max}$ represents the maximal traffic rate. Therefore, the time-varying nonsmooth $r_{t}(z,x)$ can be written as

  	$\displaystyle r_{t}(z,x)=\sum_{i,s}\delta_{\{0\leqslant\sum_{s}x(ij,s)+w_{t}(ij)\leqslant c_{t}(ij)\}}$
  	$\displaystyle+\delta_{\{0\leqslant z\leqslant z^{max}\}}+\sum_{s}\delta_{\{z(s)=\bar{R}x(s)\}}+\frac{\nu}{2}(\lVert z\lVert^{2}+\lVert x\lVert^{2}).$

It is an accelerated gradient method for stochastic composite optimization[6]. Although it is a stochastic composite optimization, they also propose the accelerated gradient method for online setting. Each iteration of the method takes the form

where $\{\alpha_{t}\}$ and $\{L_{t}\}$ are two parameter sequences and $\mu$ is the strong-convexity constant of $F_{t}(x)$. It has established upper bounds on static regret in order of ${\cal{O}}(\sqrt{T})$ for convex $f_{t}(x)$ and ${\cal{O}}(\log(T))$ for strongly convex $f_{t}(x)$, by choosing suitable parameter sequences $\{\alpha_{t}\}$ and $\{L_{t}\}$[6].

It is a stochastic gradient descent algorithm for handling convex composite optimization problems[7]. For better comparison, we choose the true subgradient $\tilde{\nabla}f_{t}$ instead of the stochastic one. Each iteration of the method takes the form

where $\{\alpha_{t}\}$ and $\{\gamma_{t}\}$ are two parameter sequences, $\mu$ denotes the strong-convexity constant of $F_{t}(x)$ and $V(\cdot,\cdot)$ is the Bregman divergence, and here we choose $V(x,z)=\frac{1}{2}\lVert x-z\rVert^{2}$. Optimal convergence rates for tackling different types of stochastic composite optimization problems were discussed in [7].

It is an extension of Nesterov’s dual averaging method for composite optimization problems, where one term is the convex loss function, and the other is a regularization term[8]. Each iteration of the method takes the form

where $\{\beta_{t}\}$ is a parameter sequence and $h(x)$ is an auxiliary strongly convex function, and here we choose $h(x)=\frac{1}{2}\lVert x\rVert^{2}$. It ensures a bound ${\cal{O}}(\sqrt{T})$ on static regret with $\beta_{t}={\cal{O}}(\sqrt{T})$ for convex loss[8].