\begin{document}

\title{Time-Varying Multi-Objective Optimization: \\ Tradeoff Regret Bounds}

\author{Allahkaram Shafiei, Vyacheslav Kungurtsev, Jakub Marecek
\thanks{All authors are at the Czech Technical University.}}
\maketitle

\begin{abstract}
Multi-objective optimization studies the process of seeking multiple competing desiderata in some operation. Solution techniques highlight marginal tradeoffs associated with weighing one objective over others. In this paper, we consider time-varying multi-objective optimization, in which the objectives are parametrized by a continuously varying parameter and a prescribed computational budget is available at each time instant to algorithmically adjust the decision variables to accommodate for the changes. 
We prove regret bounds indicating the relative guarantees on performance for the competing objectives.
\end{abstract}

 \section{Introduction} 
 During the last decades, substantial research efforts have been devoted to learning and decision making in environments with functionally relevant streaming data with potentially changing statistical properties. In many engineering design problems with social impact, including optimal power flow and sensor networks \cite{derenick2007convex,baran1989optimal}, mobile robots \cite{wang2013optimal}, and non-linear distributed flow equations \cite{bard1988convex}, there are potentially multiple criteria to consider in characterizing the best learning or decision-making performance. Formally, such multi-criteria optimization problems are classed as multi-objective optimization.
 
 The setting of a dynamically changing and uncertain environment lends itself to what is classed as online optimization,
where the cost function changes over time and an adaptive
decision pertaining only to the past information has to be
made at each stage. The standard convergence criteria in online optimization is
the level of \emph{regret}, a quantity capturing the difference between
the accumulated cost incurred up to some arbitrary time and
the cost obtained from the best fixed point chosen in hindsight.

In machine-learning applications of multi objective  optimization, the time-varying aspects could capture, e.g., time-varying group structure or some form of a concept drift. In game theory, the time-varying aspects could capture time-varying pay-offs (or time-varying price elasticity of the demand) in extensive forms of Stackelberg-like games, or time-varying demands in congestion games.

Our contributions include:
\begin{itemize}
\item introduction of regret tradeoffs as the appropriate metric for grading solvers for online multi-objective optimization
\item  an on-line proximal-gradient algorithm for handling multiple time-varying convex objectives,
\item  theoretical guarantees for the algorithm.
\end{itemize}

 
\section{Related work}
Proximal Gradient Descent is a natural approach for minimizing both single and multiple objectives. One of the most widely studied methods for multiobjective optimization problems is steepest descent, e.g., \cite{geoffrion1968proper,gonccalves2021globally}.
 
  Subsequently, a proximal point method \cite{bonnel2005proximal}, that can be applied
to non-smooth problems, was considered. However, this method is just a conceptual scheme and does not necessarily generate subproblems that are easy to solve.
For non-smooth problems, a subgradient method was also developed in [10]. A very engrossing recent paper~\cite{zhou2020regret} has presented the regret bounds for classical for n online convex optimization  OCO algorithms for relative Lipschitz, but possibly non-differentiable, that has been proven to converge at a rate of $O(\frac{1}{\sqrt{K}})$ in $K$ iteration. More closely to our work, H.Tanabe \cite{tanabe2019proximal} proposed proximal gradient methods for unconstrained multiobjective optimization problems with, and without line searches in which every component of objective functions are defined by 
$F_i(x)=f_i(x)+g_i(x)$. 

Next we describe the literature on online time varying convex single objective optimization. As the first innovative paper in in this space, Zinkevich \cite{zinkevich2003online} proposed a gradient
descent algorithm with a regret bound of $O(\sqrt{K})$. In the case that cost functions are strongly convex, the regret bound of the online gradient descent algorithm was further 
reduced to be $O(\log(K))$ with suitably chosen step size by  several online algorithms presented in \cite{hazan2007logarithmic}. 

 \section{Problem Formulation}
 We begin with describing the problem of Time-Varying Multi-Objective Optimization. Suppose we have a sequence of convex cost
functions
   $\phi_{i,t}(x):=f_{i,t}(x)+g_{i,t}(x)$ where $f_{i,t}$ are smooth and $g_{i,t}$ non-smooth. The index $t$ corresponds to the time step, and $i$ indexes the objective function among the set of interest. 
  At each time step $t\in [T]:=\{1,2,...,T\}$, a decision maker chooses an action $x^t\in\mathbb{R}$
and after committing to this decision, a convex cost functions $\phi_{i,t}(x)$ is disclosed and the decision maker is faced with a loss of $\phi_{i,t}(x^{t})$. In this scenario, due to lack of
access to the cost functions before the decision is made, the decision does not necessarily correspond to the minimizers, and the decision maker faces a so-called regret. Regret is defined as the difference between the accumulated cost over time and the cost incurred by the best fixed decision, when all functions are known in advance, see \cite{hazan2007logarithmic,Hazan2010,zinkevich2003online}. Let us consider 

 \[
F(x,t) = \begin{pmatrix}
 f_{1,t}(x)+g_{1,t}(x) \\ f_{2,t}(x)+g_{2,t}(x) \\ ... \\
 f_{N,t}(x)+g_{N,t}(x) \end{pmatrix}=\begin{pmatrix}
 \phi_{1,t}(x) \\  \phi_{2,t}(x) \\ ... \\
  \phi_{N,t}(x) \end{pmatrix}.
 \]
 At time $t$, we consider the following  time-varying vector optimization 
 \begin{equation}\label{eq:prob1}
     \min\limits_{x\in\mathbb{R}^n} \,\left( F(x,t):=F_t(x)
\right) \end{equation}
 where $F:\mathbb{R}^n\to \mathbb{R}^m$ and, each $f_{i,t}$ is $L_{f_{i,t}}$ Lipschitz continuously differentiable and $g_i$ is convex with a simple prox evaluation. Throughout the entire paper, our discussion on \eqref{eq:prob1} and proposed algorithm are motivated by the following:
 As can be surmised from the definition, there is rarely a singleton that is a Pareto optimal point. Usually, there is a continuum of solutions. As such one can consider a \emph{Pareto front} which indicates the set of Pareto optimal points. The front represents the objective values reached by the components of the range of $F(x)$ and it is usually a surface of $m-1$ dimensions. One can consider it as representing the tradeoffs associated with the optimization problem, to lower $i$'s value, i.e. $f_i(x)$, how much would you have to raise $f_j(x)$ or, if not that, $f_t(x)$ (with $i\neq j\neq k$)? Because of the fundamental generality of the concept of a solution to a vector optimization problem, finding a solution can be defined as (see, e.g., for a survey~\cite{marler2004survey} and for a text~\cite{jahn2009vector}):
 
 \begin{enumerate}
     \item Visualizing the entire Pareto front, or some portion of it
     \item Finding \emph{any} point on the Pareto front
     \item Finding some point that satisfies an additional criteria, effectively making this a bilevel optimization problem. 
 \end{enumerate}
 In regards to the second option, one can notice that this can be done, in the convex case, by solving the so called ``scalarized" problem:
 \[
 \min\limits_{x\in\mathbb{R}^n} \sum\limits_{i=1}^N \omega_i f_i(x),\,\sum \omega_i=1, \,0\le \omega_i\le 1
 \]
 for any valid choice of $\{\omega_i\}$. This reduces the problem to simple unconstrained optimization. This leaves the choice of said constants, however, arbitrary, and thus not all that informative. Although the parameters are weights balancing the relative importance of the objective functions, poor relative scaling across $f_i(x)$ can make any informed choice of $\{\omega_i\}$ insurmountable. For example if $f_1(x)=1000 x^2$ and $f_2(x) = 0.001 (x-2)^2$, taking $\omega_1=\omega_2=0.5$ clearly pushes the solution of the scalarized problem to be the solution of minimizing $f_1(x)$. 
 
 As an additional problem aspect, we consider the time varying case, i.e., each $f_i(x)$ changes over time, e.g., due to data streaming with concept drift. With a finite processing capacity at each time instant, we seek an Algorithm that appropriately balances the objectives at each time instant. This problem is considered in~\cite{tanabe2019proximal} and regret is quantified in terms of distance to \emph{some} Pareto optimal point. 
 
 In this paper, we introduce scalarization at the \emph{algorithmic} level for time varying multiobjective optimization. In particular, at each iteration we consider computing a set of steps each of which intend to move an iterate towards the solution of the problem of minimizing $f_i(x)$ exclusively. We then form a convex combination of these steps with chosen coefficients. We then derive \emph{tradeoff regret bounds} indicating how the choice of said coefficients results in guarantees in regards to suboptimality for every objective. We assert that this would be the most transparently informative theoretical guarantees, in terms of exactly mapping algorithmic choices to comparative performance for every objective function, and as such a natural and important contribution to the consideration of time varying multi-objective optimization. 
 
 

Now we shall present our formal assumptions in regards to the problem, in particular the functional properties of $F$ as well as the Algorithm we are proposing and studying the properties of in this paper. With these definitions in place, On-Line Multi-Objective Proximal Gradient Decent Algorithm is presented above, where the parameter $\alpha_i$ is such as $\sum_{i=1}^N\alpha_i=1$  for $0\le\alpha_i\le 1$.
 \begin{assumption}[Problem Structure]
 \label{ass1}
\begin{itemize}
	 		\item[$\rm{(i)}$] For all $i,t$ functions $f_{i,t}(\cdot) : \mathbb{R}^n \rightarrow \mathbb{R}$ are continuously 
	 			differentiable such that the gradient is Lipschitz with constant $L_{f_{i,t}}$: \begin{equation*}
	 				\|\nabla f_{i,t} (x) - \nabla f_{i,t}(y)\| \leq L_{f_{i,t}}\|x-y\|,\,\,\,\,\forall x,y\in\mathbb{R}^n 
	 			\end{equation*}
	 	
	 		\item[$\rm{(ii)}$] For all $t$, the function $g_{i,t}(\cdot) : \mathbb{R}^n \rightarrow (-\infty,\infty]$ is proper, 
	 			lower semi-continuous, and convex, but not necessarily differentiable. Also, assume that ${\rm dom}(g_{i,t}(\cdot))=\{x\in\mathbb{R}^n:~g_{i,t}(x)<\infty\}$ is non-empty and closed. 
	 			\item [$\rm{(iii)}$] Corresponding to each objectives $\phi_{i,t}$ we consider $T_{i,t}(x)={\rm prox}_{C_ig_{i,t}}(x-C_i\nabla f_{i,t}(x))$
	 	\end{itemize} 
 	\end{assumption} 
 	
  This following assumptions are typical in the analysis of online algorithms and make real-time algorithmic path-following of solutions feasible.
   In particular, we consider the online streaming setting with a finite sampling rate, which we assume permits
 for $K$ iterations of the proximal-gradient steps between two updates of the inputs. 

  

 \begin{assumption}[Sufficient Processing Power] \label{as:timeK} 
 At all times $t\in[T]$, the algorithm executes at least $K$ iterations before receiving the new input.
 \end{assumption}
 

  \section{Preliminaries and Algorithm}
 
  We also assume a bound on the magnitude of change between two inputs at times $t$, $t+1$:
 
 \begin{assumption}[Slow Changes] \label{as:varying} 
 The observations as compared to estimates of the function values from the previous time step are bounded, i.e.,
 \[
 \mathop {\sup }\limits_{t\ge 1} \max_{i\in[N]} \left\{ \begin{array}{l}
 |f_{i,t}(x^{t+1}) - f_{i,t} (x^t)|,\\
 |g_{i,t}(x^{t+1}) - g_{i,t} (x^t)| 
 \end{array} \right\} \le e
 \]
 where $x^t$ is generated by Algorithm 1.
 \end{assumption} 
 

We consider two measures of quality of the solution trajectory:

$(A)$: The \emph{dynamic regret bound} (see, e.g.,  \cite{zinkevich2003online}, and reference therein) defined as:

\[{\mathop{\rm Re}\nolimits} {g_i} = \sum\limits_{t = 1}^T {\phi_{i,t} ({x^t}) - } \sum\limits_{t= 1}^T {\phi_{i,t}(x^{\rm opt,t,i})}, ~~~i\in[N]\]

where  $\phi_{i,t}  = {f_{i,t}} + {g_{i,t}}$ and $x^{{\rm opt},t,i}\in\argmin_x \phi_{i,t}(x)$.\\
In the case of static regret \cite{hazan2017online}, $x^{\rm opt,t,i}$ is replaced by  $x^{\rm opt,i}\in\argmin_{x\in X}\sum_{t=1}^T\phi_{i,t}(x)$, i.e, 
\[{\rm S-Reg}_i=\sum_{t=1}^T\phi_{i,t}(x^t)-\min_{x\in X}\sum_{t=1}^T\phi_{i,t}(x)\]
In addition, we will consider the following quantities:
\begin{align}
    &
    v_t=\sum_{i=1}^{t}\|x^{i+1}-x^i\|\\&
    w_t=\sum_{j=1}^t\max_{i\in[N]}\|x^{\rm opt,j+1,i}-x^{\rm opt,j,i}\|\\&
    \sigma_t=\sum_{j=1}^t\sum_{i=1}^Nd(0,\partial\phi_{i,j}(x^j))\\&
    \phi_t(x)=\min_{i\in[N]}\phi_{i,t}(x),~~x^{\rm opt,t}=\sum_{i=1}^N\alpha_ix^{\rm opt,t,i}
\end{align}

\begin{algorithm}[t!]
    \caption{On-Line Multi-Objective Proximal Gradient Decent}
    \SetAlgoLined
    \DontPrintSemicolon
    \textbf{Input:} Initial iterate $x^1$ solving the problem with data $f_{i,1}(x),g_{i,1}(x)$ parameters $C_i\in(0,\frac{1}{L_{f_{i,t}}}]$, $\alpha_i>0$, and let $x^{1,0}\gets x^1$ 
    
    
    \textbf{\bf for $t=1,2,...,T$ do}  
    
     \quad $x^{t,0}\gets x^{t}$;
     
    Receive data $f_{i,t}(x^t),g_{i,t}(x^t)$;
    
    \hspace{1cm} {\bf for $k=0,1,2,...,K$ do} 
  
  \hspace{1cm} $y^{t,k+1,i}\gets {\rm prox}_{C_{i} g_{i,t}}(x^{t,k}-C_{i}\nabla f_{i,t}(x^{t,k}) )\, \forall i$;\\
  
  \hspace{1cm} $x^{t,k+1}\gets\sum\limits_{i = 1}^N {{\alpha _i}{y^{t,k+1,i}}}$;
  
  \hspace{1cm} 
  \hspace{0.3cm} $k\gets k+1$
  
   \hspace{0.5cm} {\bf end for } 
   
  \hspace{0.5cm} $x^{t+1,0}\gets x^{t,K}$ and $x^{t+1}\gets x^{t,K+1}$; 
  
    \hspace{0.5cm} {\bf end for} 
    \label{alg:PoEG}
\end{algorithm}

 The following lemma is a key result throughout the paper.

 \begin{lemma}\label{eq:lemmaestimate}
Let $f$ be convex and smooth, and $g$ be non-smooth and $\phi=f+g$ then 
\begin{align}
   & \phi(T(x))-\phi(y)\le \frac{1}{2C}[\|x-y\|^2-\|T(x)-y\|^2]\\& {\rm and} ~~ \phi(T(x))\le \phi(x).
\end{align}
where $T(x)={\rm prox}_{Cg}(x-C\nabla f(x))$, $C\in(0,\frac{1}{L_f}]$ and $L_f$ is Lipschitz constant for $\nabla f$.
 \end{lemma}
 \begin{proof}
 Take $G(x):=\frac{1}{C}(x-T(x))$. Owing to the convexity of $f$ one can obviously see that 
 \begin{align}\label{eq:r1}
     f(y)\le f(x)+\nabla f(x)^T(y-x)+\frac{L_f}{2}\|x-y\|^2~~~\forall x,y\in\mathbb{R}^n.
 \end{align}
 Plugging $y=x-CG(x)$ in \eqref{eq:r1} one obtains that \begin{align}
     f(x-CG(x))&\le f(x)+\nabla f(x)^T((x-CG(x))-x)+\frac{L_fC^2}{2}\|G(x)\|^2\\
     &\le f(x)-C\nabla f(x)^T(G(x))+\frac{C}{2}\|G(x)\|^2.
 \end{align}
 Now, from $x-CG(x)={\rm prox}_{Cg}(x-C\nabla f(x))$ it follows that \[G(x)-\nabla f(x)\in\partial g(x-CG(x)).\]
 Therefore 
 \begin{align}\label{eq:r2}
     g(x-CG(x))\le g(y)-\left(G(x)-\nabla f(x)\right)^T(y-x-CG(x)).
 \end{align}
 Therefore, by simplifying and taking into account \eqref{eq:r2}, one has 
 \begin{align*}
     \phi(x-CG(x))&=f(x-CG(x))+g(x-CG(x))\\&\le f(x)-C\nabla f(x)^T(G(x))+\frac{C}{2}\|G(x)\|^2+g(x-CG(x))\\&\le f(y)-\nabla f(x)^T(y-x)-C\nabla f(x)^T(G(x))+\frac{C}{2}\|G(x)\|^2+g(x-CG(x))\\&
     \le f(y)-\nabla f(x)^T(y-x)-C\nabla f(x)^T(G(x))\\&+\frac{C}{2}\|G(x)\|^2+g(y)-(G(x)-\nabla f(x))^T(y-x+CG(x))\\&=
     \phi(y)-\nabla f(x)^T(y-x)-C\nabla f(x)^T(G(x))+\frac{C}{2}\|G(x)\|^2-G(x)^T(y-x)\\&-C\|G(x)\|\nabla f(x)^T(y-x)+C\nabla f(x)^T(G(x))
     \\&\le
     \phi(y)+\frac{1}{2C}[\|x-y\|^2-\|(x-y)-CG(x)\|^2],
 \end{align*}
 and since $x-CG(x)=T(x)$ the desired result follows by the previous. 
 
 \end{proof}

 \section{ Main Results}
 
 Our main result provides a bound on the expected dynamic regret of the online multi-objective proximal gradient descent (Algorithm 1). Depending on the coefficients $\alpha_i$, there are two cases, i) if there is $i\in[N]$ such that $\alpha_i\ne1$ and ii) if there is $i\in[N]$ such that $\alpha_i=1$ and for all $j\ne i$, $\alpha_j=0$. For case i), we have  
\begin{theorem}\label{eq:maintheorem}
 Let $x^t$ , (t=1,...,T) be a sequence generated by running Algorithm 1 over $T$ time steps. Then, we have 
 \[Re{g_i} = \sum\limits_{t = 1}^T {{\phi _{i,t}}({x^t}) - \sum\limits_{t = 1}^T {{\phi _{i,t}}} ({x^{{\rm{opt}},t,i}})}  \le {\left( {{v_T} + {w_T} + K{\sigma _T}} \right)^2}{\left( {\sum\limits_{i = 1}^N {\frac{1}{{2\alpha {C_i}}}\|{x^1} - {x^{{\rm{opt}},{\rm{1}},{\rm{i}}}}} }\| \right)^2}\]
\end{theorem}

In order to prove the result, we need a technical lemma:

 \begin{lemma}\label{eq:lemma}
 The following holds.
 
 (a) For all $t$ one has
 
 \[\|x^{t+1}-x^t\|\le K\sigma_t\]
(b) For all $i\in[N]$ and $t$ one has 
\[\|x^{t+1}-x^{\rm opt,t,i}\|\le 2v_t+w_t+\|x^1-x^{\rm opt,1,i}\|\]
(c) For all $i\in[N]$ and $t$ one has \[\|x^{t,K}-x^{\rm opt,t,i}\|\le 2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\| \]
 \end{lemma}
 
 \begin{proof}
 
 (a) We can easily see by the Algorithm that 
 \begin{align}\label{eq:ine}
     \|x^{t,j+1}-x^{t,j}\|\le \|x^{t,j}-x^{t,j-1}\|\le...\le \|x^{t,2}-x^{t,1}\|
 \end{align}
 
 on the other hand since 
 \begin{align}\label{eq:ine1}
     \|x^{t,2}-x^{t,1}\|=\|\sum_{i=1}^N\alpha_i(T_{i,t}(x^{t,1})-x^{t,1})\|\le\sum_{i=1}^N\|T_{i,t}(x^{t,1})-x^{t,1}\|\le\sum_{i=1}^Nd(0,\partial\phi_{i,t}(x^t))
 \end{align}
 where in the last inequality we used \cite[Proposition 15]{shafiei2021trilevel}.
 Thanks to \eqref{eq:ine}, one obtains that 
 
 \begin{align*}
     &\|x^{t+1}-x^t\|=\|x^{t,K+1}-x^{t,1}\|=\|(x^{t,K+1}-x^{t,K})+(x^{t,K}-x^{t,K-1})+...+(x^{t,2}-x^{t,1})\|\\&
     \le \sum_{k=1}^K\|x^{t,j+1}-x^{t,j}\|\le \sum_{k=1}^K\left(\sum_{i=1}^Nd(0,\partial\phi_{i,k}(x^k))\right)=K \sum_{i=1}^Nd(0,\partial\phi_{i,t}(x^t))=K\sigma_t
 \end{align*}
 
 (b) One can write 
 \begin{align*}
     \|x^{t+1}-x^{\rm opt,t,i}\|&=\|x^{t+1}-x^t+x^t-x^{t-1,i,\rm opt}+x^{\rm opt,t-1,i}-x^{\rm opt,t,i}\|\le \|x^{t+1}-x^t\|+\\&\|x^{\rm opt,t-1,i}-x^{\rm opt,t,i}\|+\|x^t-x^{\rm opt,t-1,i}\|
 \end{align*}
 and then one gets 
 \[\|x^{t+1}-x^{\rm opt,t,i}\|-\|x^t-x^{\rm opt,t-1,i}\|\le \|x^{t+1}-x^t\|+\|x^{\rm opt,t-1,i}-x^{\rm opt,t,i}\|\]
 summing up parties the above result from $t=2$ to $t=T$ leads to 
 \[\|x^{t+1}-x^{\rm opt,t,i}\|-\|x^2-x^{1,i,\rm opt}\|\le\sum_{t=1}^T\|x^{t+1}-x^t\|+\sum_{t=2}^T\max_{i\in[N]}\|x^{\rm opt,t-1,i}-x^{\rm opt,t,i}\|\]
 therefore, \[\|x^{t+1}-x^{\rm opt,t,i}\|\le v_t+w_t+\|x^2-x^{\rm opt,1,i}\|\]
 which follows that 
 \begin{align*}
     \|x^{t+1}-x^{\rm opt,t,i}\|\le v_t+w_t+\|x^2-x^1\|+\|x^1-x^{\rm opt,1,i}\|\le 2v_t+w_t+\|x^1-x^{\rm opt,1,i}\|
 \end{align*}
 and finally the desired result can be obtained.
 \end{proof}
 
 (c) Using the last part (b) and combining \eqref{eq:ine} and \eqref{eq:ine1} derives that
 \begin{align*}
     \|x^{t,K}-x^{\rm opt,t,i}\|&\le\|x^{t,K+1}-x^{t,K}\|+\|x^{t,K+1}-x^{\rm opt,t,i}\|=\|x^{t,K+1}-x^{t,K}\|+\|x^{t+1}-x^{\rm opt,t,i}\|\\
     &\le 2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\|
 \end{align*}
 
 Returning to the proof of the main result, 
 
\begin{proof}
Take $\alpha=\min\{\alpha_i:~~\alpha_i\ne0\}$. Using the convexity of $\phi_{i,t}$ we follow that
 \[\begin{array}{l}
 {\phi _{i,t}}({x^{t+ 1}}) - {\phi _{i,t}}({x^{{\rm opt},t,i}}) = {\phi _{i,t}}({x^{t,K + 1}}) - {\phi _{i,t}}({x^{\rm opt,t,i}})\le
\left(\sum\limits_{i = 1}^N \alpha _i\phi _{i,t} y^{t,K + 1,i})\right)-\phi _{i,t}({x^{{\rm opt},t,i}})\\ 
  = \sum\limits_{i = 1}^N {{\alpha _i}[{\phi _{i,t}}({y^{t,K + 1,i}}) - {\phi _{i,t}}({x^{{\rm opt},t,i}})] + \left( {\sum\limits_{i = 1}^N {{\alpha _i}{\phi _{i,t}}({x^{{\rm opt},t,i}})} } \right) - } \,{\phi _{i,t}}({x^{{\rm opt},t,i}}) \\ 
  = \sum\limits_{i = 1}^N {{\alpha _i}[{\phi _{i,t}}({T_{i,t}}({x^{t,K}})) - {\phi _{i,t}}({x^{{\rm opt},t,i}})] + } \left( {\sum\limits_{i = 1}^N {{\alpha _i}{\phi _{i,t}}({x^{{\rm opt},t,i}})} } \right) - {\phi _{i,t}}({x^{{\rm opt},t,i}}) \\ 
  \le \sum\limits_{i = 1}^N {{\alpha _i}.\frac{1}{{{C_{i}}}}}\|{x^{t,K}} - {x^{{\rm opt},t,i}}\|^2+ \left( {\sum\limits_{i = 1}^N {{\alpha _i}{\phi _{i,t}}({x^{{\rm opt},t,i}})} } \right) - {\phi _{i,t}}({x^{{\rm opt},t,i}}) \\ 
 \end{array}\]
 Multiplying last inequality at $\alpha_i$ and summing up the result over $i$ and taking into account part (c) and applying Lemma \eqref{eq:lemma} conclude that 
\[\sum_{i=1}^N\alpha_i\left({{\phi _{i,t}}({x^{t + 1}}) - {\phi _{i,t}}({x^{{\rm opt},t,i}})}\right) \le \sum_{i=1}^N\frac{\alpha_i}{2 C_i}\left(2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\|\right)^2 \]
and since $x^{\rm opt,t,i}$ is optimal point this implies that 
\[\alpha_i\left({{\phi _{i,t}}({x^{t + 1}}) - {\phi _{i,t}}({x^{{\rm opt},t,i}})}\right)\le \sum_{i=1}^N\frac{1}{2 C_i}\left(2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\|\right)^2 \]
and subsequently, 
\[{{\phi _{i,t}}({x^{t+ 1}}) - {\phi _{i,t}}({x^{{\rm opt},t,i}})}\le \sum_{i=1}^N\frac{1}{2\alpha C_i}\left(2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\|\right)^2 \]
Using the previous and Assumption \eqref{as:varying}
one can illustrate that 
\begin{align*}
    \sum\limits_{t=1}^T \phi _{i,t}({x^t}) - \phi _{i,t}(x^{\rm opt,t,i})&=\sum\limits_{t=1}^T\phi_{i,t}(x^t)-\phi_{i,t}(x^{t+1})+\sum\limits_{t=1}^T \phi_{i,t}(x^{t+1})-\phi_{i,t}(x^{\rm opt,t,i})\\&
  \le \sum_{t=1}^T\sum_{i=1}^N\frac{1}{2\alpha C_i}\left(2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\|\right)^2\\&
  \le\left(\sum_{t=1}^T\sum_{i=1}^N\frac{1}{2\alpha C_i}\left(2v_t+w_t+K\sigma_t+\|x^1-x^{\rm opt,1,i}\|\right)\right)^2\\&
  =(v_T+w_T+K\sigma_T)^2\left(\sum_{i=1}^N\frac{1}{2\alpha C_i}\left(\|x^1-x^{\rm opt,1,i}\|\right)\right)^2
\end{align*}
where in the last inequality, one uses Assumption \eqref{as:varying}.
\end{proof}

\begin{corollary}
In the case that there exists $i$,  $\alpha_i=1$ and for all $j\ne i$ we have $\alpha_j=0$ the problem reduces to time-varying single objective optimization, i.e, 
 $$x^{t,k+1}={\rm prox}_{C_ig_{i,j}}(x^{t,k}-C\nabla f_{i,j}(x^{t,k})).$$ 
 Then 
 \[\sum_{t=1}^{T}\phi_{i,t}(x^{t+1})-\phi_{i,t}(x^{\rm opt,t,i})\le \frac{C}{K+1}\|x^1-x^{\rm opt,1,i}\|^2, \]
 
and moreover
\[\sum_{t=1}^{T}\phi_{i,t}(x^{t})-\phi_{i,t}(x^{\rm opt,t,i})\le Te+ \frac{C}{K+1}\|x^1-x^{\rm opt,1,i}\|^2.\]
 \end{corollary}
 \begin{proof}
As can be seen from Lemma \ref{eq:lemmaestimate} we have 
\[\phi_{i,t}(x^{t,k+1})-\phi_{i,t}(x^{\rm opt,t,i})\le \frac{1}{C_i}[\|x^{t,k}-x^{\rm opt,t,i}\|^2-\|x^{t,k+1}-x^{\rm opt,t,i}\|^2].\]
Summing the result over $k$ from $1$ to $K$ we conclude that 
\[\sum_{k=1}^{K}[\phi_{i,t}(x^{t,k+1})-\phi_{i,t}(x^{\rm opt,t,i})]\le C[\|x^{t,1}-x^{\rm opt,t,i}\|^2-\|x^{t,K+1}-x^{\rm opt,t,i}\|^2], \]
where $C=\max\limits_{i\in[N]} \frac{1}{C_i}$, therefore

\[\phi_{i,t}(x^{t,K+1})-\phi_{i,t}(x^{\rm opt,t,i})\le\frac{C}{K+1}[\|x^t-x^{\rm opt,t,i}\|^2-\|x^{t+1}-x^{\rm opt,t,i}\|^2],\]
and subsequently, by summing the previous inequality over $t$ from 1 to $T$ one gives the required results.
 \end{proof}
 
It is important to note that due to being decreasing the sequence $\{\phi_{i,t}(x^t)\}$, i.e.,   $\phi_{i,t}(x^{t+1})\le\phi_{i,t}(x^t)$ we can have
 \[\left\{ \begin{array}{l}
 \phi_{i,t}(x^{t+1})-\phi_{i,t}(x^{\rm opt,t,i})\le\frac{C}{T(K+1)}\|x^1-x^{\rm opt,1,i}\| \\ 
 \phi_{i,T}(x^{T})-\phi_{i,t}(x^{\rm opt,K,i})\le e+\frac{C}{T(K+1)}\|x^1-x^{\rm opt,1,i}\| \\ 
 \end{array} \right.\]

From definitions, one gets the following Lemma.
\begin{lemma}
one has 
\[\min_{x_1,...x_N\in\mathbb{R}^n}\sum_{i=1}^{N}\alpha_i\phi_{i,t}(x_i)=\phi_t(x^{\rm opt,t})\] 
\end{lemma} 
 
 \begin{proposition}
 Let $\{x^t\}$ be the iterates generated by Algorithm 1 then the following holds
  For every $x\in\mathbb{R}^n$ and $t$ one has 
 \[\|\nabla f_{i,t}(x^t)-\nabla f_{i,t}(x^{\rm opt,t,i})\|^2\le 2L(v_T+w_T+K\sigma_T)^2\left(\sum_{i=1}^N\frac{1}{2\alpha C_i}\left(\|x^1-x^{\rm opt,1,i}\|\right)\right)^2\]
 where $L = \mathop {\max }\limits_{i \in [N],t \in [T]} {L_{{f_{i,t}}}}$.
 \end{proposition}
 
 \begin{proof}
 Since $f_{i,t}$ is Lipschitz continuous with constant $L_f$, using \cite[Theorem 2.1.5]{nesterov2018lectures}, one obtain that 
 \[\|\nabla f_{i,t}(x)-\nabla f_{i,t}(x^{\rm opt,t,i})\|^2\le f_{i,t}(x)-f_{i,t}(x^{\rm opt,t,i})-\nabla f_{i,t}(x^{\rm opt,i,t})^T(x-x^{\rm opt,t,i}).\]
 For the optimality of $x^{\rm opt,t,i}$, we see that there exists $\xi^{\rm opt,t,i}\in\partial g_{i,t}(x^{\rm opt,t,i})$ such that $\xi^{\rm opt,t,i}+\nabla f_{i,t}(x^{\rm opt,t,i})=0$. Hence for all $x$ one has
 \begin{align*}
    \|\nabla f_{i,t}(x)-\nabla f_{i,t}(x^{\rm opt,t,i})\|^2&\le f_{i,t}(x)-f_{i,t}(x^{\rm opt,t,i})-\nabla f_{i,t}(x^{\rm opt,t,i})^T(x-x^{\rm opt,t,i})\\
     &=f_{i,t}(x)-f_{i,t}(x^{\rm opt,t,i})+\xi^{t,i,\rm opt}(x-x^{\rm opt,t,i})\\
     &\le f_{i,t}(x)-f_{i,t}(x^{\rm opt,t,i})+g_{i,t}(x)-g_{i,t}(x^{\rm opt,t,i})\\&
     =\phi_{i,t}(x)-\phi_{i,t}(x^{\rm opt,t,i})
 \end{align*}
 Invoking Theorem \ref{eq:maintheorem} follows the desired result. 
 \end{proof}
 

\section{Conclusions}
We have studied a time-varying multi-objective optimization problem in a setting, which has not been considered previously. We have shown properties of a natural, online proximal-gradient algorithm, when the processing power between iterations is bounded.
Going forwards, one could clearly consider alternative uses of the same algorithm (e.g., how many operations one requires per update to achieve a certain bound in terms of the dynamic regret), variant algorithms, or completely novel settings. 
In parallel with our work, Tarzanagh and Balzano \cite{OnlineBilevel2022} studied online bilevel optimization under assumptions of strong convexity throughout, which could be seen as one such novel setting. 

\paragraph*{Acknowledgements}
Allahkaram Shafiei acknowledges support of the OP RDE funded project CZ.02.1.01/0.0/0.0/16\_019/0000765 ``Research Center for Informatics''.
This work has received funding from the European Unionâ€™s Horizon Europe research and innovation programme under grant agreement No. GA 101070568.

 
\appendix 

 \section{Time-Varying MOP as a Problem in Graph Theory}
 In this section, vectors will be considered as a column vectors and use $\rm{col} \{x_1,x_2,...,x_N\}$ to indicate a column vector formed by stacking $x_1,x_2,...,x_N$ on top of each other. Set $\mathcal{V}=\{1,2,...,N\}$ and $\mathcal{S}=\{1,2,...,\mathcal{X}\}$. The adjacent matrix of a graph is defined as $\mathcal{A}^\mathcal{S}=[a_{ij}^\mathcal{S}]$ where $a_{ij}^s=1$ if the edge pair $(j,i)\in\mathcal{E}^s$, and zero otherwise. The degree matrix is defined as $\mathcal{D}^s={\rm diag}(d_1^s,d_2^s,...,d_N^s)$, with $d_i^s=\sum\limits_{j = 1}^N a_{ij}^s$. Then,
the Laplacian matrix is defined as $\mathcal{L}^s=\mathcal{D}^s-\mathcal{A}^s$
 The neighbouring set of agent $i$ is defined as $\mathcal{N}_i^s=\{j\in\mathcal{V}:~(j,i)\in\mathcal{E}^s\}$ where $\mathcal{E}^s=\{(i,j):~i,j\in\mathcal{V}\}$
 

 \begin{definition} (Time varying Pareto optimal solution)\cite{miettinen2012nonlinear}
A decision vector $z^{t,\rm opt}\in\mathbb{R}^n$ is called time-varying Pareto solution to the problem \eqref{eq:prob1} if for any time $k$ there dose not exist another decision vector $z^t\in\mathbb{R}^n$ such that $\phi_{i,t}(z^t)\le \phi_{i,t}(z^{t,\rm opt})$ for all $i\in[N]$ and $\phi_{j,t}(z^t)<\phi_{j,t}(z^{t,\rm opt})$ for at least one $j\in[N]$. Equivalently, $z^{t,\rm opt}$ is time-varying Pareto optimal solution for $F$ if there is no $z^t\in\mathbb{R}^n$ such that $F_t(z^t)\le F_k(z^{t,\rm opt})$ and $F_t(z^t)\ne F_t(x^{t,\rm opt})$ 

\end{definition}

Due to the local objective $f_i(x,t)$ is privately known to the agent 
$i$ only, distributed algorithms should be implemented to solve the problem. Introducing a local decision variable $x_i\in\mathbb{R}^n$ for agent $i$, problem \eqref{eq:prob1} can be reformulated as 
\[\begin{array}{l}
 \mathop {\min }\limits_{{x_1},...,{x_N} \in\mathbb{R}^n} \left\{ {{f_1}({x_1},t),...,{f_N}({x_N},t)} \right\} \\ 
{\rm subjcet ~to}\bar{\mathcal{T}}^{\sigma}\bar{x}=0 \\ 
 \end{array}\]
where $\bar{\mathcal{T}}^{\sigma}=\mathcal{T}^{\sigma}\otimes I_n$ and $\bar{x}={\rm col}(x_1,...,x_N)$.

\end{document}