\section{Solution for the bargaining game}
We use the notation of $[K]=\{1,2,\dots,K\}$.
   
\begin{claim}
Assume that    $g_i\neq0$ for all $i \in [K]$. Let $G$ be the $d\times K$ matrix whose columns are the gradients $g_i$. The solution to $\arg\max_{\Delta\theta\in B_\epsilon}\sum_i p_{i}\log(\Delta\theta^\top g_i)$ is (up to scaling) $\sum_i\alpha_i g_i$ where $\alpha\in\mathbb{R}^K_+$ is the solution to $G^\top G\alpha=p/\alpha$ where $p/\alpha$ is the element-wise reciprocal.  

\end{claim}

\begin{proof}
The derivative of this objective is $\sum_{i=1}^K\frac{p_i}{\Delta\theta^\top g_i}g_i$. Since $p_i>0$, for all vectors $\Delta\theta$ such that $\forall i:\Delta\theta^Tg_i>0$ the utilities are monotonically increasing with the norm of $\Delta\theta$. Thus, from the Pareto optimality assumption by Nash, the optimal solution has to be on the boundary of $B_\epsilon$. From this we see that the gradient at the optimal point $\sum_{i=1}^K\frac{p_i}{\Delta\theta^\top g_i}g_i$ must be in the radial direction, i.e., $\sum_{i=1}^K\frac{p_i}{\Delta\theta^\top g_i}g_i\parallel\Delta\theta$ or $\sum_{i=1}^K\frac{p_i}{\Delta\theta^\top g_i}g_i=\lambda\Delta\theta$. Since the gradients are independent we must have $\Delta\theta=\sum_i \alpha_ig_i$ and $\forall i:\frac{p_i}{\Delta\theta^\top g_i}=\lambda \alpha_i$ or $\forall i:{\Delta\theta^\top g_i}=\frac{p_i}{\lambda \alpha_i}$. As the inner product must be positive for a descent direction we can conclude $\lambda>0$; we set $\lambda=1$ to ascertain the direction of $\Delta\theta$ (the norm might be larger then $\epsilon$). Now finding the bargaining solution is reduced to finding $\alpha\in\mathbb{R}^K$ with $\alpha_i>0$ such that $\forall i:{\Delta\theta^\top g_i}=\sum_j \alpha_jg_j^\top g_i=\frac{p_i}{\alpha_i}$. This is equivalent to requiring that $G^\top G\alpha=p/\alpha$ where $p/\alpha$ is the element-wise reciprocal.
\end{proof}


\section{Convergence}
We adopt the following implicit assumption from the previous paper \citep{navon2022multi}: if we reach a Pareto stationary solution at some step, the algorithm halts.
We also adopt the following explicit assumptions:\begin{assumption}\label{assump:independence}
We assume that for a sequence $\{\theta^{(t)}\}_{t=1}^\infty$ generated by our algorithm, the set of the gradient vectors $g_1^{(t)},...,g_K^{(t)}$ at any point on the sequence and at any partial limit are linearly independent unless that point is a Pareto stationary point. 
\end{assumption}
\begin{assumption}\label{assump:diff}
We assume that all loss functions are differentiable, bounded below and that all sub-level sets are bounded. The input domain is open and convex.
\end{assumption}

\begin{assumption}\label{assump:L-smooth}
We assume that all the loss functions are L-smooth,
\begin{equation}
    ||\nabla\ell_i(x)-\nabla\ell_i(y)||\leq L||x-y|| \quad .
\end{equation}
\end{assumption}


\begin{lemma}\label{Kenji_lemma}
(Lemma A.1 of \citealp{navon2022multi})\ If $\mathcal{L}$ is differential and L-smooth (assumption \ref{assump:L-smooth}) then 
$\mathcal{L}(\theta')\leq \mathcal{L}(\theta)+\nabla\mathcal{L}(\theta)^\top (\theta'-\theta)+\frac{L}{2}\|\theta'-\theta\|^{2}$.
\end{lemma}


\subsection{With changing p without extra  assumption}

\begin{theorem} 
Suppose that Assumptions  \ref{assump:independence}, \ref{assump:diff}, and  \ref{assump:L-smooth}.  Let $\{\theta^{(t)}\}_{t=1}^\infty$ be the sequence generated by the update rule $\theta^{(t+1)}=\theta^{(t)}-\mu^{(t)}\Delta\theta^{(t)}$ where $\Delta\theta^{(t)}=\sum_{i=1}^K\alpha^{(t)}_ig_i^{(t)}$ is the Nash bargaining solution $(G^{(t)})^\top G^{(t)}\alpha^{(t)}=p^{(t)}/\alpha^{(t)}$. Set $\mu^{(t)}=\frac{1}{K}\sum_{i=1}^{K}p^{(t)}_{i}(L\alpha^{(t)}_i)^{-1}$. The sequence $\{\theta^{(t)}\}_{t=1}^\infty$ has a subsequence that converges to a Pareto stationary point $\theta^*$. Moreover all the loss functions $(\ell_1(\theta^{(t)}),...,\ell_K(\theta^{(t)}))$ converge to $(\ell_1(\theta^*),...,\ell_K(\theta^*))$.
\end{theorem}

\begin{proof}
We first note that if for some step we reach a Pareto stationary solution the algorithm halts and sequence stays fixed at that point and therefore converges; Next, we assume that we never get to an exact Pareto stationary solution at any finite step.
Since $\sum_{i=1}^K p_{i}^{(t)}=1$ and  $\Delta\theta^{(t)}=G^{(t)}\alpha^{(t)}$,
$$
||\Delta\theta^{(t)}||^2=(\alpha^{(t)})^\top ( G^{(t)})^\top G^{(t)}\alpha^{(t)}=(\alpha^{(t)})^\top(p^{(t)}/\alpha^{(t)})=\sum_{i=1}^K\alpha_i^{(t)}\cdot (p_{i}^{(t)}/\alpha_i^{(t)})=1.
$$ 
For each loss $\ell_i$  for $i\in[K]$,  using Lemma \ref{Kenji_lemma}
 and $(g_i^{(t)})^\top\Delta\theta^{(t)}=(g_i^{(t)})^\top G^{(t)}\alpha^{(t)}=p_i^{(t)}/\alpha_i^{(t)}$,

\begin{align} 
    \ell_i(\theta^{(t+1)})&\leq \ell_i(\theta^{(t)})-  \mu^{(t)}\nabla\ell_i(\theta^{(t)})^\top\Delta\theta^{(t)}+\frac{L}{2}||\mu^{(t)}\Delta\theta^{(t)}||^2
    \\ &= \ell_i(\theta^{(t)})- \mu^{(t)}\frac{p_i^{(t)}}{\alpha^{(t)}_i}+\frac{(\mu^{(t)})^2 L}{2}
\end{align}\\ 
We average over the above inequality over all losses and get for $\mathcal{L}(\theta)=\frac{1}{K}\sum_{i=1}^K\ell_i(\theta)$:
\begin{align}
    &\mathcal{L}(\theta^{(t+1)})\leq \mathcal{L}(\theta^{(t)})- \mu^{(t)}\frac{1}{K}\sum_{i=1}^K\frac{p_i^{(t)}}{\alpha^{(t)}_i}+\frac{(\mu^{(t)})^2L}{2}=
    \mathcal{L}(\theta^{(t)})-L(\mu^{(t)})^2+\frac{(\mu^{(t)})^2L}{2}
    =\mathcal{L}(\theta^{(t)})-\frac{L(\mu^{(t)})^2}{2}. 
\end{align}
By rearranging, this shows that  $\mathcal{L}(\theta^{(t+1)}) \le\mathcal{L}(\theta^{(t)}) $ and   $\frac{L(\mu^{(t)})^2}{2}\le \mathcal{L}(\theta^{(t)})-\mathcal{L}(\theta^{(t+1)})$. From the first inequality,  the sequence   $\mathcal{(L}(\theta^{(t)}))_t$ is  non-increasing. As $\mathcal{L}(\theta^{(t)}) \in \RR$ is bounded below and $\mathcal{(L}(\theta^{(t)}))_t$ is non-increasing, the monotone convergence theorem concludes that the sequence $\mathcal{(L}(\theta^{(t)}))_t$ converges to a finite limit. Since a convergent sequence is a Cauchy sequence, $\frac{L(\mu^{(t)})^2}{2}\le \mathcal{L}(\theta_{}^{t})-\mathcal{L}(\theta_{}^{t+1}) \rightarrow 0$  as $t \rightarrow \infty$.
This implies that  $\mu^{(t)}\to 0$ as $t \rightarrow \infty$.
It follows that $\frac{1}{K}\sum_{i=1} ^{K}p_i^{(t)}/\alpha^{(t)}_i\to0$ as $t \rightarrow \infty$.
 Since $p_i^{(t)}>0$ and $\alpha^{(t)}_i>0$, it  implies that $p_i^{(t)}/\alpha^{(t)}_i \rightarrow 0$ for all $i \in [K]$. Since $p_i>0$ and $\sum_{i} p_i=1$, there exists $i \in [K]$ such that  $ p_i^{(t)}\nrightarrow 0$ as  $t \rightarrow \infty$. Combining these two facts, there exists $i \in [K]$ such that  $ \alpha^{(t)}_i \rightarrow \infty$ as  $t \rightarrow \infty$.  It follows that $||\alpha^{(t)}||\to\infty$ as  $t \rightarrow \infty$.

We will now show that $||p^{(t)}/\alpha^{(t)}||$ is bounded for $t\to\infty$. As the sequence $\mathcal{L}(\theta^{(t)})$ is decreasing we have that the sequence $\theta^{(t)}$ is in the sublevel set $\{\theta:\mathcal{L}(\theta)\leq \mathcal{L}(\theta_0)\}$ which is closed and bounded and therefore compact. If follows that there exists $M<\infty$ such that $||g^{(t)}_i||\leq M$ for all $t$ and $i\in[K]$. We have for all $i$ and $t$, 
$|p_i^{(t)}/\alpha^{(t)}_i|=|(g^{(t)}_i)^T\Delta\theta^{(t)}|\leq||g^{(t)}_i||\leq M <\infty$, and so $||p^{(t)}/\alpha^{(t)}||$ is bounded. 
Combining these two results we have $||p^{(t)}/\alpha^{(t)}||\geq \sigma_K((G^{(t)})^\top G^{(t)})||\alpha^{(t)}||$ where $\sigma_K((G^{(t)})^\top G^{(t)})$ is the smallest singular value of $(G^{(t)})^\top G^{(t)}$.
Since the norm of $\alpha^{(t)}$ goes to infinity and the norm $p^{(t)}/\alpha^{(t)}$ is bounded, it follows that $\sigma_K((G^{(t)})^\top G^{(t)})\to 0$.

Now, since $\{\theta : \mathcal{L}(\theta)\leq \mathcal{L}({\theta_0})\}$ is compact there exists a subsequence $\theta^{(t_j)}$ that converges to some point $\theta^*$. As $\sigma_K((G^{(t)})^T G^{(t)})\rightarrow 0$ we have from continuity that $\sigma_K(G_*^\top G_*)=0$ where $G_*$ is the matrix of gradients at $\theta^*$. This means that the gradients at $\theta^*$ are linearly dependent and therefore $\theta^*$ is Pareto stationary by assumption \ref{assump:independence}. Since all loss functions  $\ell_i$ are the are differentiable, all loss functions $\ell_i$ are continuous. Thus, we have from the continuity of $\ell_i$ that  $\ell_i(\theta^{(t)})\xrightarrow{t\rightarrow\infty}\ell_i(\theta^*)$.
\end{proof}

\subsection{With changing p with an extra assumption}

\begin{assumption}\label{assump:p}
We assume that $ p_i^{(t)}\nrightarrow 0$ as  $t \rightarrow \infty$ for all $i \in [K]$.
\end{assumption}


\begin{theorem} 
Suppose that Assumptions  \ref{assump:independence}, \ref{assump:diff},  \ref{assump:L-smooth}, and \ref{assump:p} hold. Let $\{\theta^{(t)}\}_{t=1}^\infty$ be the sequence generated by the update rule $\theta^{(t+1)}=\theta^{(t)}-\mu^{(t)}\Delta\theta^{(t)}$ where $\Delta\theta^{(t)}=\sum_{i=1}^K\alpha^{(t)}_ig_i^{(t)}$ is the Nash bargaining solution $(G^{(t)})^\top G^{(t)}\alpha^{(t)}=p^{(t)}/\alpha^{(t)}$. Set $\mu^{(t)}=\min_{i\in[K]}p^{(t)}_{i}(L\alpha^{(t)}_i)^{-1}$. The sequence $\{\theta^{(t)}\}_{t=1}^\infty$ has a subsequence that converges to a Pareto stationary point $\theta^*$. Moreover all the loss functions $(\ell_1(\theta^{(t)}),...,\ell_K(\theta^{(t)}))$ converge to $(\ell_1(\theta^*),...,\ell_K(\theta^*))$.
\end{theorem}


\begin{proof}
We first note that if for some step we reach a Pareto stationary solution the algorithm halts and sequence stays fixed at that point and therefore converges; Next, we assume that we never get to an exact Pareto stationary solution at any finite step.
Since $\sum_{i=1}^K p_{i}^{(t)}=1$ and  $\Delta\theta^{(t)}=G^{(t)}\alpha^{(t)}$,
$$
||\Delta\theta^{(t)}||^2=(\alpha^{(t)})^\top ( G^{(t)})^\top G^{(t)}\alpha^{(t)}=(\alpha^{(t)})^\top(p^{(t)}/\alpha^{(t)})=\sum_{i=1}^K\alpha_i^{(t)}\cdot (p_{i}^{(t)}/\alpha_i^{(t)})=1.
$$ 
For each loss $\ell_i$  for $i\in[K]$,  using Lemma \ref{Kenji_lemma}
 and $(g_i^{(t)})^\top\Delta\theta^{(t)}=(g_i^{(t)})^\top G^{(t)}\alpha^{(t)}=p_i^{(t)}/\alpha_i^{(t)}$,

\begin{align} 
    \ell_i(\theta^{(t+1)})&\leq \ell_i(\theta^{(t)})-  \mu^{(t)}\nabla\ell_i(\theta^{(t)})^\top\Delta\theta^{(t)}+\frac{L}{2}||\mu^{(t)}\Delta\theta^{(t)}||^2
    \\ \label{eq:temp2} &= \ell_i(\theta^{(t)})- \mu^{(t)}\frac{p_i^{(t)}}{\alpha^{(t)}_i}+\frac{(\mu^{(t)})^2 L}{2}\\
    &=\ell_i(\theta^{(t)})- \frac{p_i^{(t)}\mu^{(t)}}{\alpha^{(t)}_i}+\frac{\mu^{(t)}}{2}\min_j\frac{p_i^{(t)}}{\alpha_j^{(t)}}
    \\ &  \le \ell_i(\theta^{(t)})- \frac{p_i^{(t)}\mu^{(t)}}{\alpha^{(t)}_i}+\frac{}{}\frac{p_i^{(t)}\mu^{(t)}}{2\alpha_j^{(t)}}   
    \\&  \leq \ell_i(\theta^{(t)})-\frac{p_i^{(t)}\mu^{(t)}}{2\alpha^{(t)}_i}<\ell_i(\theta^{(t)}),
\end{align}\\ 
where the last inequality used $p_i^{(t)}>0$. This shows that our update decreases all the loss functions. 
We can average over inequality (\ref{eq:temp2}) over all losses and get for $\mathcal{L}(\theta)=\frac{1}{K}\sum_{i=1}^K\ell_i(\theta)$:
\begin{align}
    &\mathcal{L}(\theta^{(t+1)})\leq \mathcal{L}(\theta^{(t)})- \mu^{(t)}\frac{1}{K}\sum_{i=1}^K\frac{p_i^{(t)}}{\alpha^{(t)}_i}+\frac{(\mu^{(t)})^2L}{2}\leq
    \mathcal{L}(\theta^{(t)})-L(\mu^{(t)})^2+\frac{(\mu^{(t)})^2L}{2}
    =\mathcal{L}(\theta^{(t)})-\frac{L(\mu^{(t)})^2}{2}. 
\end{align}
Thus, we have $\frac{L(\mu^{(t)})^2}{2}\le \mathcal{L}(\theta^{(t)})-\mathcal{L}(\theta^{(t+1)})$. As $\mathcal{L}(\theta^{(t)}) \in \RR$ is bounded below and monotonically decreasing, the sequence $\mathcal{(L}(\theta^{(t)}))_t$ converges. Therefore, $\frac{L(\mu^{(t)})^2}{2}\le \mathcal{L}(\theta_{}^{t})-\mathcal{L}(\theta_{}^{t+1}) \rightarrow 0$  as $t \rightarrow \infty$.
This implies that  $\mu^{(t)}\to 0$. It follows that $\min_{i\in[K]} p_i^{(t)}/\alpha^{(t)}_i\to0$. Since  $ p_i^{(t)}\nrightarrow 0$ as  $t \rightarrow \infty$ (Assumption \ref{assump:p}),  
and this implies  that $||\alpha^{(t)}||\to\infty$.

We will now show that $||p^{(t)}/\alpha^{(t)}||$ is bounded for $t\to\infty$. As the sequence $\mathcal{L}(\theta^{(t)})$ is decreasing we have that the sequence $\theta^{(t)}$ is in the sublevel set $\{\theta:\mathcal{L}(\theta)\leq \mathcal{L}(\theta_0)\}$ which is closed and bounded and therefore compact. If follows that there exists $M<\infty$ such that $||g^{(t)}_i||\leq M$ for all $t$ and $i\in[K]$. We have for all $i$ and $t$, 
$|p_i^{(t)}/\alpha^{(t)}_i|=|(g^{(t)}_i)^T\Delta\theta^{(t)}|\leq||g^{(t)}_i||\leq M <\infty$, and so $||p^{(t)}/\alpha^{(t)}||$ is bounded. 
Combining these two results we have $||p^{(t)}/\alpha^{(t)}||\geq \sigma_K((G^{(t)})^\top G^{(t)})||\alpha^{(t)}||$ where $\sigma_K((G^{(t)})^\top G^{(t)})$ is the smallest singular value of $(G^{(t)})^\top G^{(t)}$.
Since the norm of $\alpha^{(t)}$ goes to infinity and the norm $p^{(t)}/\alpha^{(t)}$ is bounded, it follows that $\sigma_K((G^{(t)})^\top G^{(t)})\to 0$.

Now, since $\{\theta : \mathcal{L}(\theta)\leq \mathcal{L}({\theta_0})\}$ is compact there exists a subsequence $\theta^{(t_j)}$ that converges to some point $\theta^*$. As $\sigma_K((G^{(t)})^T G^{(t)})\rightarrow 0$ we have from continuity that $\sigma_K(G_*^\top G_*)=0$ where $G_*$ is the matrix of gradients at $\theta^*$. This means that the gradients at $\theta^*$ are linearly dependent and therefore $\theta^*$ is Pareto stationary by assumption \ref{assump:independence}. As for all $i$ the sequence $(\ell_i(\theta^{(t)}))_{t=1}^\infty$ is monotonically decreasing and bounded below they all converges. Since $\ell_i(\theta^*)$ is the limit of a subsequence we get that $\ell_i(\theta^{(t)})\xrightarrow{t\rightarrow\infty}\ell_i(\theta^*)$.
\end{proof}


\section{A different version and formalization of the implicit function theorem  part}

In this section, we consider $\frac{\partial \alpha}{\partial p}$ where $\alpha$ satisfies $G^\top G \alpha = p/\alpha$.
The current version applies the implicit function theorem for the following relation of  $(p,\alpha)$:  $\frac{\partial \mathcal{L}_{\alpha,p}}{\partial \alpha}=0$ where $\mathcal{L}_{\alpha,p}=\Vert \log( G^TG\alpha) - \log(p/\alpha)\Vert_2$. However, this relation, $\frac{\partial \mathcal{L}_{\alpha,p}}{\partial \alpha}=0$, is not equivalent to the desired relation, $G^\top G \alpha = p/\alpha$, for two reasons: (1)  the resulting  implicit differentiation term, $\frac{\partial \alpha}{\partial p}=-\Big[\frac{\partial^2 \mathcal{L}_{\alpha, p}}{\partial^2\alpha}\Big]^{-1} \frac{\partial^2\mathcal{L}_{\alpha,p}}{\partial\alpha\partial p}$, is computationally more expensive than necessary, and (2)  $\mathcal{L}_{\alpha,p}$ may have stationary points  not satisfying the desired relation $G^\top G \alpha = p/\alpha$; i.e., $G^\top G \alpha = p/\alpha$ implies $\frac{\partial \mathcal{L}_{\alpha,p}}{\partial \alpha}=0$ but I am not sure about the opposite direction. 



Thus, instead of using the current version, I would suggest using the following version: 
$$
\frac{\partial \hat \alpha(p)}{\partial p}=[G^\top G+\Lambda_0]^{-1} \Lambda_1,
$$
where $\Lambda_0 ,\Lambda_1\in \RR^{K\times K}$ are diagonal matrices defined by $(\Lambda_0)_{ii}=p_i/\alpha_{i}^2 \in \RR$ and $(\Lambda_1)_{ii}=1/\alpha_{i} \in \RR$ for $i = 1,2,\dots,K$.
Here, $\hat \alpha$ is the function that satisfies $G^\top G\hat \alpha(\bar p) = \bar p/\hat \alpha(\bar p)$ for any  $\bar p$ in a neighborhood of the  $p$. This $\frac{\partial \hat \alpha(p)}{\partial p}=[G^\top G+\Lambda_0]^{-1} \Lambda_1$ can  replace  $\frac{\partial \alpha}{\partial p}=-\Big[\frac{\partial^2 \mathcal{L}_{\alpha, p}}{\partial^2\alpha}\Big]^{-1} \frac{\partial^2\mathcal{L}_{\alpha,p}}{\partial\alpha\partial p}$ and  avoid the above 2 undesired effects of $\frac{\partial \alpha}{\partial p}=-\Big[\frac{\partial^2 \mathcal{L}_{\alpha, p}}{\partial^2\alpha}\Big]^{-1} \frac{\partial^2\mathcal{L}_{\alpha,p}}{\partial\alpha\partial p}$.

This is based on the following proposition:
\begin{proposition}  \label{prop:1}
For any $(p,\alpha)$ satisfying $G^\top G \alpha = p/\alpha$, there exists an open set $U \subseteq \RR^K$ containing $p$ such that there exists  a  continuously differentiable function $\hat \alpha:U \to \RR^K$ satisfying all of the following properties: (1) $\hat \alpha(p)=\alpha$, (2) $G^\top G\hat \alpha(\bar p) = \bar p/\hat \alpha(\bar p)$ for all $\bar p \in U$, and (3)
$$
\frac{\partial \hat \alpha(p)}{\partial p}=-\left[\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar \alpha}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}\right]^{-1} \frac{\partial F(\bar p,\bar \alpha)}{\partial \bar p}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=\left[G^\top G+\Lambda_0\right]^{-1} \Lambda_1.
$$ \end{proposition}
\begin{proof} Define a function $F(\bar p,\bar \alpha)=G^\top G \bar \alpha - \bar p/\bar \alpha \in \RR^K$ where and  $\bar p \in \RR_{+}^K$ and $\bar \alpha\in \RR_{+}^K$ are independent variables of $F$ with $\RR_{+}$ being the set of strictly positive real numbers. Here,  $\bar p/\bar \alpha$ represents the coordinate-wise operation; i.e., $\bar p/\bar \alpha \in \RR^K$ with $(\bar p/\bar \alpha)_i=\bar p_{i}/\bar \alpha_i \in \RR$ for $i=1,2,\dots,K$. Then, we have 
\begin{align*}
\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar \alpha}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=G^\top G - \frac{\partial (\bar p/\bar \alpha)}{\partial \bar \alpha} \Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=G^\top G+\Lambda_0,
\end{align*}
where the last equality follows from $\frac{\partial \bar p/\bar \alpha}{\partial \bar \alpha}=-\Lambda_0$ because   
$$
\frac{\partial( \bar p/\bar \alpha)_{i}}{\partial \bar \alpha_{j}}= \begin{cases}\frac{\partial( \bar p_{j}/\bar \alpha_{j})_{}}{\partial \bar \alpha_{j}} & \text{if } i=j\\
0 & \text{otherwise} \\
\end{cases} = \begin{cases}-\bar p_i/\bar \alpha_{i}^2  & \text{if } i=j\\
0 & \text{otherwise} \\
\end{cases}
$$  
Similarly, 
\begin{align*}
\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar p}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}= - \frac{\partial (\bar p/\bar \alpha)}{\partial \bar p} \Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=-\Lambda_1,
\end{align*}
because 
$$
\frac{\partial( \bar p/\bar \alpha)_{i}}{\partial\bar p_{j}}= \begin{cases}\frac{\partial( \bar p_{j}/\bar \alpha_{j})_{}}{\partial \bar p_{j}} & \text{if } i=j\\
0 & \text{otherwise} \\
\end{cases} = \begin{cases}1/\bar \alpha_{i}  & \text{if } i=j\\
0 & \text{otherwise} \\
\end{cases}
$$
Thus, $F$ is continuously differentiable and $\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar \alpha}\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=G^\top G+\Lambda_0$ is invertible since $G^\top G$ is positive semi-definite and $\Lambda_0$ is positive definite due to the condition of $p_i>0$ for all $i \in [K]$. Therefore, the function $F$  at  $(p,\alpha)$ satisfies the condition of the implicit function theorem, which implies  the  statement of this proposition. 
\end{proof}

\subsection{A possible modification}
Numerically, maybe the following might work better:
$$
\frac{\partial \hat \alpha(p)}{\partial p}=[\Lambda_2 G^\top G+\Lambda_3]^{-1} \Lambda_4,
$$
where $\Lambda_2, \Lambda_3, \Lambda_4\in \RR^{K\times K}$ are diagonal matrices defined by $(\Lambda_2)_{ii}=\frac{1}{(G^\top G \alpha)_i}$, $(\Lambda_3)_{ii}=1/\alpha_{i} \in \RR$, and $(\Lambda_4)_{ii}=1/p_{i} \in \RR$ for $i = 1,2,\dots,K$. This is potentially better numerically because $\Lambda_3$ is less likely close to 0 (compared to $\Lambda_0$) and $G^\top G$ is normalized inside the inverse. So, the inverse might be better conditioned in terms of the ratio of smallest and largest singular values. But, I am not sure: if you are already in the phase of writing a paper (instead of the exploration phase), then you might want to ignore this modification, especially if the previous version is already working fine. 

\begin{proof}
This is derived in the exact same proof steps as in Proposition \ref{prop:1}, except that we replace the function $F(\bar p,\bar \alpha)$ with $F(\bar p,\bar \alpha)= \log(G^\top G \bar \alpha) - \log(\bar p/\bar \alpha) \in \RR^K$. Then, we have 
\begin{align*}
\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar \alpha}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=\Lambda_2 G^\top G - \Lambda_5 \frac{\partial (\bar p/\bar \alpha)}{\partial \bar \alpha} \Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=G^\top G+ \Lambda_5 \Lambda_0,
\end{align*}
\begin{align*}
\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar p}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}= -\Lambda_5 \frac{\partial (\bar p/\bar \alpha)}{\partial \bar p} \Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=-\Lambda_5\Lambda_1,
\end{align*}
where $\Lambda_5\in \RR^{K\times K}$ is a diagonal matrix defined by $(\Lambda_5)_{ii}=\frac{\alpha_i}{p_i}$. Noticing that $\Lambda_5 \Lambda_0=\Lambda_3$ and $\Lambda_5 \Lambda_1=\Lambda_4$, 
$$
\frac{\partial \hat \alpha(p)}{\partial p}=-\left[\frac{\partial F(\bar p,\bar \alpha)}{\partial \bar \alpha}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}\right]^{-1} \frac{\partial F(\bar p,\bar \alpha)}{\partial \bar p}\Big\vert_{(\bar p,\bar \alpha)=(p,\alpha)}=[\Lambda_2 G^\top G+\Lambda_3]^{-1} \Lambda_4.
$$
\end{proof}



\end{document}
\section{Introduction}
When training deep neural networks with limited labeled data,
generalization can be improved by adding auxiliary tasks. In this approach, called \textit{Auxiliary learning} (AL), the auxiliary tasks are trained jointly with the main task, and their labels can provide a signal that is useful for the main task. AL is beneficial because auxiliary annotations are often easier to obtain than annotations for the main task. This is the case when the auxiliary tasks use self-supervision \citep{oliver2018realistic,HwangPKKHK20,achituve2021self}, or their annotation process is faster. For example, learning semantic segmentation of an image may require careful and costly annotation, but can be improved if learned jointly with a depth prediction task, whose annotations can be obtained at scale \citep{StandleyZCGMS20}. 


Auxiliary learning has a large potential to improve learning in the low data regime, but it gives rise to two main challenges:  Defining the joint optimization problem and performing the optimization efficiently. (1) First, given a main task at hand, it is not clear \textit{which} auxiliary tasks would benefit the main task and how tasks should be \textit{combined} into a joint optimization objective. For example, \citet{StandleyZCGMS20} showed that depth estimation is a useful auxiliary task for semantic segmentation but not the opposite. In fact, adding semantic segmentation as an auxiliary task harmed depth estimation performance. This suggests that even close-related tasks may interfere with each other. (2) Second, training with auxiliary tasks involves optimizing multiple objectives simultaneously; While training with multiple tasks can potentially improve performance via better generalization, it often underperforms compared to single-task models. 

Previous auxiliary learning research focused mainly on the first challenge: namely, weighting and combining auxiliary tasks \citep{lin2019adaptive}. The second challenge, optimizing the main task in the presence of auxiliary tasks, has been less explored. Luckily, this problem can be viewed as a case of optimization in \textit{Multi-Task Learning} (MTL). In MTL, there is extensive research on controlling optimization such that every task would benefit from the others. Specifically, several studies proposed algorithms to aggregate gradients from multiple tasks into a coherent update direction \citep{yu2020gradient,liu2021conflict,navon2022multi}. We see large potential in bringing MTL optimization ideas into auxiliary learning to address the optimization challenge.  

Here we propose a novel approach named AuxiNash{} that takes inspiration from recent advances in MTL optimization as a cooperative bargaining game \citep[Nash-MTL,][]{navon2022multi}. The idea is to view a gradient update as a shared resource, view each task as a player in a game, and have players compete over making the joint gradient similar to their own task gradient. In Nash-MTL, tasks play a symmetric role, since no task is particularly favorable. This leads to a bargaining solution that 
is proportionally fair across tasks. In contrast, task symmetry no longer holds in auxiliary learning, where there is a clear distinction between the primary task and the auxiliary ones.
As such, we propose to view auxiliary learning as an \emph{asymmetric bargaining game}. Specifically, we consider gradient aggregation as a cooperative bargaining game where each player represents a task with varying bargaining power. We formulate gradient update using asymmetric Nash bargaining solution which takes into account varying task preferences. By generalizing Nash-MTL to asymmetric games with AuxiNash, we can efficiently direct optimization solution towards various areas of the Pareto front. 

Determining the task preferences that result in optimal performance is a challenging problem for several reasons. First, the relationship between tasks can change during the optimization process, making it difficult to know in advance what preferences to use. This means that the process of preference tuning needs to be automated during training. Second, using a grid search to find the optimal preferences can be computationally expensive, and the complexity of the search increases exponentially with the number of tasks. To overcome these limitations, we propose a method for efficiently differentiating through the optimization process and using this information to automatically optimize task preferences during training. This can improve the performance of the primary task, and make it more efficient to find the optimal preferences.


\begin{figure}
    \centering
    \includegraphics[width=1.\linewidth]{figures/illustrative_new.png}
    \caption{\textit{Illustrative example}: A regression problem in $\mathbb{R}^2$ with two auxiliary tasks, one helpful and one harmful. AuxiNash{} succeeds in using the helpful auxiliary task and disregards the harmful one, as demonstrated by how it learns to weigh different tasks: The left panel shows the preference vector $p$ during optimization. As a result, AuxiNash converges to a solution with large proximity to the optimal solution, far superior to that obtained from optimizing with the main tasks alone (right panel). See Section~\ref{sec:illus} for further details. }
\label{fig:illustrative}
\end{figure}

We theoretically analyze the convergence of AuxiNash{} and show that even if the preference changes during the optimization process we are still guaranteed to converge to a Pareto stationary point. Finally, we show empirically on several benchmarks that AuxiNash{} achieves superior results to previous auxiliary learning and multi-task learning approaches. 

\paragraph{Contributions:} This paper makes the following contributions: (1) We introduce AuxiNash{} - a novel approach for auxiliary learning based on principles from asymmetric bargaining games. (2) We describe an efficient method to dynamically learn task preferences during training. (3) We theoretically show that AuxiNash{} is guaranteed to converge to a Pareto stationary point. (4) We conduct extensive experiments to demonstrate the superiority of AuxiNash{} against multiple baselines from MTL and auxiliary learning.

\section{Related Work}
 
\paragraph{Auxiliary Learning.} Learning with limited amount of training data is challenging since deep learning models tend to overfit to the training data and as a result can generalize poorly \citep{ying2019overview}. One  approach to overcome this limitation is using auxiliary learning \citep{chen2022auxiliary, kung2021efficient}. Auxiliary learning aims to improve the model performance on primary task by utilizing the information of related auxiliary tasks \citep{dery2022aang, chenmodule}. Most auxiliary learning approaches use a linear combination of the main and auxiliary losses to form a unified loss \citep{zhai2019s4l, wen2020entire}. Fine-tuning the weight of each task loss may be challenging as the search space of the grid search grows exponentially with the number of tasks. To find the beneficial auxiliary tasks, recent studies utilized the auxiliary task gradients and measure their similarity with the main task gradients \citep{lin2019adaptive, du2018adapting, shi2020auxiliary}.
\citet{NavonAMCF21} proposed to learn a non-linear network that combines all losses into a single coherent objective function. 
\paragraph{Multi-task Learning.} In multi-task learning (MTL) we aim to solve multiple tasks by sharing information between them \citep{caruana1997multitask, ruder2017overview}, usually through joint hidden representation \citep{zhang2014facial, dai2016instance, pinto2017learning, Liu2019EndToEndML}. Previous studies showed that optimizing a model using MTL helps boost performances while being computationally efficient \citep{sener2018multi, chen2017gradnorm}. However, MTL presents a number of optimization challenges such as: conflicting gradients \citep{wang2020gradient, yu2020gradient}, and flatten areas in the loss landscape \citep{schaul2019ray}. These challenges may result with performance degradation compare with single task learning. Recent studies proposed novel architectures \citep{misra2016cross, hashimoto2017joint, Liu2019EndToEndML, Chen2020JustPA} to improve MTL while others focused on aggregating the gradients of the tasks such that it is agnostic to the optimized model \citep{liu2021towards, javaloy2021rotograd}. \citet{yu2020gradient} proposed to overcome the conflicting gradients problem by subtracting normal projection of conflicted task before forming an update direction. Most gradient based methods aim to minimize the average loss function. \citet{liu2021conflict} suggested an approach that will decrease every task loss in addition to the average loss function. The closest work to our approach is Nash-MTL \citep{navon2022multi}. The authors proposed a principled approach to dynamically weight the losses of different tasks by incorporating concepts from game theory.
\paragraph{Bi-level Optimization.} Bi-Level Optimization (BLO) consists of two nested optimization problems~\citep{liao2018reviving,liu2021investigating, vicol2022implicit}. The outer optimization problem is commonly referred to as the upper-level problem, while the inner optimization problem is referred to as the lower-level problem \citep{sinha2017review}. BLO is widely used in a variety of deep learning applications, spanning hyper-parameter optimization \citep{foo2007efficient, mackay2019self}, meta learning \citep{franceschi2018bilevel}, reinforcement learning \citep{zhang2020bi, yang2019provably}, and multi-task learning \citep{liu2022auto, NavonAMCF21}. A common practice to derive the gradients of the upper-level task is using the implicit function theorem (IFT). However, applying IFT involves the calculation of an inverse-Hessian vector product which is infeasible for large deep learning models. Therefore, recent studies proposed diverse approaches to approximate the inverse-Hessian vector product. \citet{luketina2016scalable} proposed approximating the Hessian with the identity matrix, where other line of works used conjugate gradient (CG) to approximate the product \citep{foo2007efficient, pedregosa2016hyperparameter, Rajeswaran2019MetaLearningWI}. We use a truncated Neumann series and efficient vector-Jacobian products, as it was empirically shown to be more stable than CG \citep{liao2018reviving, lorraine2020optimizing, raghu2020teaching}.

\begin{figure}
    \centering
    \includegraphics[width=0.7\linewidth]{figures/multimnist.png}
    \caption{\textit{Task preferences}: By varying the preference vector $p$, we show that AuxiNash{} can control the trafe-off between tasks. Compared with Nash-MTL, AuxiNash achieves a wider range of diverse solutions, an important property for auxiliary learning. See Section~\ref{sec:multimnist} for further details.}
\label{fig:multimnist}
\end{figure}


\section{Background}

\subsection{Nash Bargaining Solution}\label{sec:nbs}

We will first give a quick introduction to cooperative bargaining games. In a bargaining game, a set of $K$ players jointly decide on an agreed-upon point in the set $A$ of all agreement points. If failing to reach an agreement, the game default to the disagreement point $D$. Each player $i\in [K]:=\{1, ...,K\}$ is equipped  with a  utility function $u_i:A\cup\{D\}\rightarrow\mathbb{R}$, which they wish to maximize. Intuitively, each player has a different objective, and each tries to only maximize their own personal utility. However,  we generally assume that there are points in the agreement set that are mutually beneficial to all players, compared to the disagreement point, and as such the players are incentivized to cooperate. The main question is on which point in the agreement set will they decide upon.\\

 Denote by $U=\{(u_1(x),...,u_K(x)):\,x\in A\}\subset\mathbb{R}^K$ the set of the utilities of all possible agreement points and $d=(u_1(D),...,u_K(D))$. The set $U$ is assumed to be convex and compact. Furthermore, we assume that there exists a point $u\in U$ for which $\forall i:u_i>d_i$. \citet{nash} showed that under these assumptions, there exists a unique solution to the bargaining game, which satisfies the following properties: Pareto optimality, symmetry, independence of irrelevant alternatives, and invariant to affine transformations \citep[see][and the supplementary material for more details]{game_theory}. This unique solution, referred to as the Nash Bargaining solution (NBS), is given by 
\begin{align}\label{eq:nash_barg}
    u^*=&\arg\max_{u\in U}\sum_i\log(u_i-d_i)\\
    &s.t.\,\,\forall i:\,u_i>d_i\nonumber
\end{align}
As shown in~\citet{navon2022multi}, NBS properties are suitable for the multi-task learning setup, even if the invariance to affine transformations implies that gradient norms are ignored. The symmetry assumption, however, implies that each player is interchangeable which is not the case for  auxiliary learning. Naturally, our main concern is the main task and the auxiliaries are there to support it, not compete with it. Thus, we wish to discard the symmetry assumption for the auxiliary learning setup.



\subsection{Generalized Bargaining Game}

\citet{kalai1977nonsymmetric} generalized the NBS to the asymmetric case. First, define a preference vector to control the relative trade-off between tasks $p \in \mathbb{R}^K$ with $p_i>0$ and $\sum_i p_i=1$ (see Figure~\ref{fig:multimnist}). Similar to the symmetric case, the Generalized Nash Bargaining Solution (GNBS) maximizes a weighted product of utilities,
\begin{align}\label{eq:asym_nash_barg}
    u^*=&\arg\max_{u\in U}\sum_ip_i\log(u_i-d_i)\\
    &s.t.\,\,\forall i:\,u_i>d_i\nonumber \quad.
\end{align}
The symmetric case is a special case of GNBS with uniform preferences $p_i=1/K,~\forall i\in [K]$.

\subsection{Bargaining Game for Multi-task learning}

Recently,~\citet{navon2022multi} formalized multi-task learning as a bargaining game as follows. Let $\theta \in \RR^d$ denote the parameters of a network $f(\cdot; \theta)$. At each MTL optimization step, we search for an update direction $\Delta\theta$. Define the agreement set $U=\{\Delta\theta\ \mid \Vert \Delta\theta \Vert \leq 1 \}$ as the set of all possible update directions. The disagreement point $d$ is defined to be equal to zero, i.e., to stay with the current parameters and terminate the optimization process. Let $g_i$ denote the gradient of $\theta$ w.r.t. the loss of task $i$ (for each $i\in[K]$). The utility function for task $i$ is defined as $u_i(\Delta\theta)=g_i^\top\Delta\theta$, i.e., the directional derivative in direction $\Delta\theta$. \citet{navon2022multi} assumed that the gradients $g_1,...,g_K$ are linearly independent if $\theta$ is not Pareto stationary, and we adopt that assumption in our analysis. Under this assumption, \citet{navon2022multi} show that the solution for the bargaining game at any non-Pareto stationary point $\theta$ is given by $\Delta\theta=\sum_i\alpha_ig_i$, where the weight vector $\alpha$ satisfies
\begin{align}
    G^\top G\alpha=1/\alpha.
\end{align}
Here, $G$ is the $d\times K$ matrix whose $i$-th column is the $i$-th task gradient $g_i$, and $1/\alpha$ is the element-wise reciprocal.

\begin{figure*}[t]
    \centering
\includegraphics[width=1.\linewidth]{figures/update_direction_by_preference.png}    
    \caption{\textit{Visualization of the update direction}: We show the update direction {(\textcolor{blue}{blue})} obtained by AuxiNash{} on three gradients in $\mathbb{R}^3$. We rescaled the update directions for better visibility, showing only the direction. We further show the size of the projection {(\textcolor{red}{red})} of the update to each gradient direction {(\textbf{black})}. By varying the preference vector, we observe the change in the obtained update direction. Importantly, we note that the effect on the update direction is non-trivial, as $p$ only affects the update implicitly through the bargaining solution $\alpha$.}
    \label{fig:update}
\end{figure*}


\section{Generalized Bargaining Game for Auxiliary Learning}

In this section, we first extend the result from~\citet{navon2022multi} to the asymmetric case. Next, we describe a method to learn the preference vector $p$. 

\subsection{Generalized Bargaining Solution}
We prove the following claim, which generalizes the claim of ~\citet{navon2022multi} to asymmetric  games.


\begin{claim}
Let $p\in \mathbb{R}^K_+$ with $\sum_i p_i=1$. The solution to the generalized bargaining problem $\Delta\theta^*=\arg\max_{\Delta\theta\in U}\sum_i p_i \log(\Delta\theta^\top g_i)$ is given by (up to scaling) $\sum_i\alpha_i g_i$ at any non-Pareto stationary point $\theta$, where $\alpha\in\mathbb{R}^K_+$ is the solution to $G^\top G\alpha=p/\alpha$ where $p/\alpha$ is the element-wise reciprocal.  
\end{claim}
\begin{proof}
We define $F(\Delta\theta)=\sum_i p_i \log(\Delta\theta^\top g_i)$ and have $\nabla F=\sum_{i=1}^K \frac{p_i}{\Delta\theta^T g_i} g_i$. Note that for all $\Delta\theta$ with $u_i(\Delta\theta)>0$ for all $i\in [K]$ the utilities are monotonically increasing in $\Vert \Delta\theta\Vert$, hence the optimal solution lies on the boundary of $U$, and $\nabla F|_{\Delta\theta^*}$ is parallel to $\Delta\theta^*$. This implies that  $\sum_{i=1}^K \frac{p_i}{\Delta\theta^\top g_i} g_i=\lambda \Delta\theta$ for some $\lambda > 0$. From the {linear} independence assumption, we have for the optimal solution $\Delta\theta=\sum_i\alpha_i g_i$, thus $\forall i, \Delta\theta^\top g_i=\frac{p_i}{\lambda \alpha_i}$. Setting $\lambda=1$ (as we ignore scale), the solution to the bargaining game is reduced to finding $\alpha\in \mathbb{R}^K_+$ for which $\forall i,~\Delta\theta^\top g_i=\sum_j\alpha_jg_j^\top g_j=p_i/\alpha_i$. Equivalently, the optimal solution is given by $\alpha\in \mathbb{R}^K_+$ such that $G^\top G\alpha= p/\alpha$ where $p /\alpha$ is the element-wise reciprocal.
\end{proof}

Given a preference vector $p$, we solve $G^\top G\alpha= p/\alpha$ by expressing it as the solution to an optimization problem. We first solve a convex relaxation which we follow by a concave-convex procedure (CCP) 
\citep{yuille2003concave,lipp2016variations}, similar to \citet{navon2022multi} for solving $G^\top G \alpha=p/\alpha$ w.r.t. $\alpha$. See Appendix~\ref{app:solving-the-game} for full details.



\subsection{Optimizing the Preference Vector}

The derivation in the previous section allows us to learn using a known preference vector $p$. Unfortunately, in most cases,  the preference vector is {not} known in advance. One simple solution is to treat the preferences $p_i$ as hyperparameters and set them via grid search. However, this approach has two significant limitations. First, as the number of hyperparameters increases, grid search becomes computationally expensive as it scales exponentially. Second, it is possible that the optimal preference vector would vary {during optimization}, hence using a fixed  $p$ would be sub-optimal.

To address these issues, we develop an approach for dynamically learning the task preference vector during training. This reduces the number of hyperparamters the user needs to tune to one (the preference update rate) and dynamically adjusts the preference to improve generalization. We do this by formulating the problem as bi-level optimization, which we discuss next

Let ${\mathcal{L}}_T$ denote the training loss and ${\mathcal{L}}_V$ denote the \textit{generalization} loss, given by the loss of the main task on unseen data, i.e., ${\mathcal{L}}_V=\ell_{main}^{val}$. In the auxiliary learning setup, we wish to optimize $p$ such that a network $f(\cdot;\theta)$ optimized with ${\mathcal{L}}_T(\cdot; p)$ would minimize ${\mathcal{L}}_V$. Formally, 
\begin{align*}
    p^*=\arg\min_{p} {\mathcal{L}}_V(\theta^*(p)),~~\text{s.t.}~~\theta^*(p)=\arg\min_{\theta} {\mathcal{L}}_T(\theta, p)
\end{align*}
Using the chain rule to get the derivative of the outer problem, we get
\begin{align*}
    \frac{\partial \mathcal{L}_V(p,\theta^*(p))}{\partial p} \hspace{-2pt}= \hspace{-2pt} \underbrace{\frac{\partial \mathcal{L}_V}{\partial p}}_{=0}+\frac{\partial \mathcal{L}_V}{\partial \theta} \frac{\partial \theta^*}{\partial p}
    \hspace{-2pt} = \hspace{-2pt}  \frac{\partial \mathcal{L}_V}{\partial \theta} \frac{\partial \theta^*}{\partial \alpha(p)} \frac{\partial \alpha(p)}{\partial p}
   
   
\end{align*}
As we can compute $\frac{\partial \mathcal{L}_V}{\partial \theta}$ by simple backpropagation, the main challenge is to compute $\frac{\partial \theta^*}{\partial \alpha(p)}$ and $ \frac{\partial \alpha(p)}{\partial p}$.

To compute $\frac{\partial \theta^*}{\partial \alpha(p)}$ we can (indirectly) differentiate through the optimization process using the implicit function theorem (IFT)  \citep{liao2018reviving,lorraine2020optimizing,NavonAMCF21}:
\begin{align}
    \frac{\partial \theta^*}{\partial \alpha(p)}=-\left[\frac{\partial^2{\mathcal{L}}_T}{\partial \theta\partial \theta^\top}\right]^{-1} \frac{\partial^2{\mathcal{L}}_T}{\partial\theta\partial\alpha(p)^\top}
\end{align}
Since computing the inverse Hessian directly is intractable, we use the algorithm proposed by \citet{lorraine2020optimizing} to efficiently estimate the inverse-Hessian vector product. This approach uses the Neumann approximation with an efficient vector-Jacobian product. Thus, we can efficiently approximate the first term, $\frac{\partial \mathcal{L}_V}{\partial \theta} \frac{\partial \theta^*}{\partial \alpha(p)}$. We note that in practice, as in customary, we do not optimize till convergence but perform a few gradient updates from the previous value. For further details, see ~\citet{vicol2022implicit} that recently examined how this affects the bi-level optimization process.
 
For the second term, $\frac{\partial \alpha(p)}{\partial p}$, we derive a simple analytical expression using the IFT in the following proposition:
\begin{proposition}\label{prop:dalpha-dp}
For any $(p,\alpha)$ satisfying $G^\top G \alpha = p/\alpha$, there exists an open set $U \subseteq \RR^K$ containing $p$ such that there exists  a  continuously differentiable function $\hat \alpha:U \to \RR^K$ satisfying all of the following properties: (1) $\hat \alpha(p)=\alpha$, (2) $G^\top G\hat \alpha(\bar{p}) = \bar{p}/\hat \alpha(\bar{p})$ for all $\bar{p} \in U$, and (3)
\begin{align}
\begin{split}
\frac{\partial \hat \alpha(p)}{\partial p}=\left[G^\top G+\Lambda_0\right]^{-1} \Lambda_1. 
\end{split}
\end{align}
Here $\Lambda_0 ,\Lambda_1\in \RR^{K\times K}$ are the diagonal matrices defined by $(\Lambda_0)_{ii}=p_i/\alpha_{i}^2 \in \RR$ and $(\Lambda_1)_{ii}=1/\alpha_{i} \in \RR$ for $i\in [K]$.
\end{proposition}
We refer the readers to Appendix~\ref{app:proofs} for the proof.

Putting everything together, we obtain the following efficient approximation,
\begin{align}\label{eq:hypergrad}
\small
\begin{split}
 \frac{\partial \mathcal{L}_V(p,\theta^*(p))}{\partial p}
&=-\frac{\partial \mathcal{L}_V}{\partial \theta} \left[\frac{\partial^2{\mathcal{L}}_T}{\partial \theta\partial \theta^\top}\right]^{-1} \frac{\partial^2{\mathcal{L}}_T}{\partial\theta\partial\alpha(p)^\top}
\times\\ 
& \qquad \left[G^\top G+\Lambda_0\right]^{-1} \Lambda_1
\end{split} 
\end{align}
We note that this approximation can be computed in a relatively efficient manner, with the cost of only several backpropagation operations to estimate the vector-Jacobian product (we use 3 in our experiments). We also note that the matrix $\left(G^\top G+\Lambda_0\right)$ that we invert is of size $K\times K$, where $K$ is the number of tasks that is generally relatively small.

 
In practice, we use a separate batch from the training set to estimate the generalization loss ${\mathcal{L}}_V$. We further discuss this design choice and provide an empirical evaluation in Section~\ref{sec:aux-set}. During the optimization process, we alternate between optimizing $\theta$ and optimizing $p$. Specifically, we update $p$ once every $N_p$ optimization steps over $\theta$. We set $N_p=25$ in our experiments. The AuxiNash{} algorithm is summarized in Alg.~\ref{alg:auxinash}.



\begin{algorithm}[t]
    \caption{AuxiNash{}}\small\label{alg:auxinash}
    \begin{algorithmic}[H]
    \STATE {\bfseries Input:} $\theta$ -- initial parameter vector, $p$ -- initial preference vector, $\{\ell_i\}_{i=1}^K$ -- differentiable loss functions, $\eta, \eta_p$ -- learning rates
   
    \FOR{$T=1,...,N$}
    \FOR{$t=1,...,N_p$}
    \STATE Compute task gradients $g_i=\nabla_{\theta}\ell_i$
    \STATE Set $G$ the matrix with columns $g_i$
    \STATE Solve for $\alpha$: $G^\top G\alpha=p/\alpha$
    \STATE Update the parameters $\theta\gets\theta-\eta G\alpha$
    \ENDFOR
    \STATE Evaluate $\nabla_p{\mathcal{L}}_V$ using Eq.~\ref{eq:hypergrad}
    \STATE Update $p\gets p-\eta_p \nabla_p{\mathcal{L}}_V$
    \ENDFOR
   
    \STATE {\bfseries Return:} $\theta$.
    \end{algorithmic}
\end{algorithm}


\begin{table*}[!t]
\setlength{\tabcolsep}{3pt}
\small
    \centering
    \caption{\textit{NYUv2}. Test performance for three tasks: semantic segmentation, depth estimation, and surface normal. Values are averages over 3 random seeds.}
    \vskip 0.11in
\resizebox{0.95\textwidth}{!}{%
\begin{tabular}{lccccccccccccccccccc}
\toprule\\
 &  &  & \multicolumn{2}{c}{Segmentation} &  & \multicolumn{2}{c}{Depth} &  & \multicolumn{8}{c}{Surface Normal} &  &  &  \\
 \cmidrule(lr){4-5} \cmidrule(lr){7-8} \cmidrule(lr){10-17}
 &  &  & \multirow{2}{*}{mIoU $\uparrow$} & \multirow{2}{*}{Pix Acc $\uparrow$} &  & \multirow{2}{*}{Abs Err $\downarrow$} & \multirow{2}{*}{Rel Err $\downarrow$} &  & \multicolumn{2}{c}{Angle Distance $\downarrow$} &  & \multicolumn{5}{c}{Within $t^\circ$  $\uparrow$}  & $\mathbf{\Delta\%} \downarrow$ \\
 \cmidrule(lr){10-11} \cmidrule(lr){13-17} \cmidrule(lr){19-19} \cmidrule(lr){20-20}
 &  &  &  &  &  &  &  &  & Mean & Median &  & 11.25 &  & 22.5 &  & 30 \\
 \midrule
 & \multicolumn{2}{c}{STL} & $38.30$ & $63.76$ &  & $0.6754$ & $0.2780$ &  & $25.01$ & $19.21$ &  & $30.14$ &  & $57.20$ &  & $69.15$ \\
  \midrule
 & \multicolumn{2}{c}{LS} & $38.43$ & $64.36$ &  & $0.5472$ & $0.2184$ &  & $29.57$ & $25.42$ &  & $20.50$ &  & $44.85$ &  & $58.20$ & $~~~8.69$ \\
 
 & \multicolumn{2}{c}{PCGrad} & $39.25$ & $64.95$ &  & $0.5389$ & $0.2141$ &  & $28.66$ & $24.26$ &  & $21.99$ &  & $47.00$ &  & $60.31$ & $~~~5.66$ \\
 
 & \multicolumn{2}{c}{CAGrad} & $39.25$ & $65.15$ &  & $0.5385$ & $0.2155$ &  & $26.11$ & $20.95$ &  & $26.96$ &  & $53.66$ &  & $66.37$ & $-1.46$ \\
 & \multicolumn{2}{c}{Nash-MTL} & $39.83$ & $66.00$ &  & $0.5235$ & $0.2075$ &  & $25.32$ & $19.87$ &  & $28.86$ &  & $55.87$ &  & $68.27$ & $-4.76$ \\
 \midrule
 
 & \multicolumn{2}{c}{GCS} & $38.96$ & $64.35$ && $0.5769$ & $0.2293$ && $29.57$ & $25.53$ && $20.64$ && $44.68$ && $57.99$ & $~~~9.54$ \\
 & \multicolumn{2}{c}{OL-AUX} & $40.51$ & $65.49$ && $0.6652$ & $0.2614$ && $\mathbf{24.65}$ & $\mathbf{18.72}$ && $\mathbf{30.92}$ && $\mathbf{58.37}$ && $\mathbf{70.12}$ & $-2.88$\\
 & \multicolumn{2}{c}{AuxiLearn} & $38.63$ & $64.20$ && $0.5415$ & $0.2173$ && $29.98$ & $25.29$ && $20.03$ && $43.94$ && $57.17$ & $~~~9.15$ &  \\
 \midrule

 & \multicolumn{2}{c}{AuxiNash{} (ours)} &
 
 $\mathbf{40.79}$ & $\mathbf{66.79}$ &  & $\mathbf{0.5092}$ & $\mathbf{0.2042}$ & & $24.90$ & $19.31$ &  & $29.83$ &  & $57.07$ &  & $69.27$ & $\mathbf{-6.80}$\\
 \bottomrule
\end{tabular}%
}
\label{tab:nyu}
\end{table*}

\section{Analysis}
We analyze the convergence properties of our proposed method in nonconvex optimization. We adopt the following three assumptions from~\citet{navon2022multi}:
\begin{assumption}\label{assump:independence}
We assume that for a sequence $\{\theta^{(t)}\}_{t=1}^\infty$ generated by our algorithm, the set of the gradient vectors $g_1^{(t)},...,g_K^{(t)}$ at any point on the sequence and at any partial limit are linearly independent unless that point is a Pareto stationary point. 
\end{assumption}
\begin{assumption}\label{assump:diff}
We assume that all loss functions are differentiable, bounded below and that all sub-level sets are bounded. The input domain is open and convex.
\end{assumption}
\begin{assumption}\label{assump:L-smooth}
We assume that all the loss functions are $L$-smooth,
\begin{equation}
    \Vert \nabla\ell_i(x)-\nabla\ell_i(y)\Vert \leq L\Vert x-y\Vert.
\end{equation}
\end{assumption}
Since even single-task non-convex optimization might only admits convergence to a stationary point, the following theorem proves convergence to a Pareto stationary point when both $\theta$ and $p$ are optimized concurrently:
\begin{theorem}\label{th:novergence}
Suppose that Assumptions  \ref{assump:independence}, \ref{assump:diff}, and  \ref{assump:L-smooth} hold.  Let $\{\theta^{(t)}\}_{t=1}^\infty$ be the sequence generated by the update rule $\theta^{(t+1)}=\theta^{(t)}-\mu^{(t)}\Delta\theta^{(t)}$ where $\Delta\theta^{(t)}=\sum_{i=1}^K\alpha^{(t)}_ig_i^{(t)}$ is the weighted Nash bargaining solution $(G^{(t)})^\top G^{(t)}\alpha^{(t)}=p^{(t)}/\alpha^{(t)}$ where $p^{(t)}$ can be any discrete distribution. Set $\mu^{(t)}=\frac{1}{K}\sum_{i=1}^{K}p^{(t)}_{i}(L\alpha^{(t)}_i)^{-1}$. The sequence $\{\theta^{(t)}\}_{t=1}^\infty$ has a subsequence that converges to a Pareto stationary point $\theta^*$. Moreover all the loss functions $(\ell_1(\theta^{(t)}),...,\ell_K(\theta^{(t)}))$ converge to $(\ell_1(\theta^*),...,\ell_K(\theta^*))$.
\end{theorem}
See full proof in Appendix~\ref{app:proofs}.



\section{Experiments}



In this section, we compare AuxiNash{} with different approaches from multi-task and auxiliary learning. We use variety of datasets and learning setups to demonstrate the superiority of AuxiNash{}. To encourage future research and reproducibility, we will make our source code publicly available. Additional experimental results and details are provided in Appendix~\ref{app:exp_details}.

\paragraph{Baselines.} We compare AuxiNash{} with natural baselines from recent auxiliary and multi-task learning works. The compared methods includes (1) Single-task learning (STL), which trains a model using the main task only; (2) Linear scalarization (LS) that minimizes the sum of losses $\sum_k\ell_k$; (3) GCS \citep{du2018adapting}, an auxiliary learning approach that uses gradient similarity between primary and auxiliary tasks; (4) OL-AUX \citep{lin2019adaptive}, an auxiliary learning approach that adaptively changes the loss weight based on the gradient inner product w.r.t the main task; (5) AuxiLearn \citep{NavonAMCF21}, an auxiliary learning approach that dynamically learns non-linear combinations of different tasks; (6) PCGrad \citep{yu2020gradient}, an MTL method that removes gradient components that conflict with other tasks; (7) CAGrad \citep{liu2021conflict}, an MTL method that optimizes for the average loss while explicitly controlling the minimum decrease rate across tasks; (8) Nash-MTL \citep{navon2022multi},  an MTL approach that is equivalent to AuxiNash{} but with a fixed $p_i=1/K$ weighting.

\paragraph{Evaluation} We report the common evaluation metrics for each task. Since MTL methods treat each task equally, and these may vary in scale, we also report the overall relative multi-task performance $\Delta\%$. $\Delta\%$ is defined as the performance drop compared to the STL performance. Formally, $\Delta\%=\frac{1}{K}\sum_{k=1}^{K}(-1)^{\delta_k}(M_{m,k} - M_{b,k} )/ M_{b,k}$. We denote $M_{b,k}$ and $M_{m,k}$ as the performance of STL and the compared method on task $k$, respectively. $\delta_k=0$ if a lower value is better for the metric $M_k$ and $1$ otherwise \citep{maninis2019attentive}. In all experiments, we report the mean value based on $3$ random seeds.    

It is important to note that for MTL models, we present the results of a single model trained on all tasks. For auxiliary learning methods, we trained a unique model per task, treating it as the main task and using the remaining tasks as auxiliaries.

\subsection{Illustrative Example}\label{sec:illus}

We start with an illustrative example, showing that AuxiNash{} can utilize helpful auxiliaries while ignoring harmful ones. 

We adopt a similar problem setup as in~\citet{NavonAMCF21} and consider a regression problem with parameters $W^T=(w_1, w_2)\in\RR^2$, fully shared among tasks. The optimal parameters for the main and helpful auxiliary tasks are $W^\star$, while the optimal parameters for the harmful auxiliary are $\tilde{W}\neq W^\star$. The main task is sampled from a Normal distribution $N({W^\star}^T x, \sigma_{\text{main}})$, with $\sigma_{\text{main}} > \sigma_{\text{h}}$ where $\sigma_{\text{h}}$ denotes the standard deviation for the noise of the helpful auxiliary. 

The change in the task preference throughout the optimization process is depicted in the left panel of Figure~\ref{fig:illustrative}. AuxiNash{} identify the helpful tasks and fully ignore the harmful ones. In addition, 
Figure~\ref{fig:illustrative} right panel presents the main task's loss landscape, along with the optimal solution ($W^\star$, marked 	$\blacktriangle$), the optimal training set solution of the main  task alone (${\scriptstyle \blacksquare}$) and the solution obtained by AuxiNash{} (marked ${\small\CIRCLE}$). While using the training data alone with no auxiliary information yields a solution that generalizes poorly, AuxiNash{} converges to a solution with large proximity to the optimal solution $W^\star$, 

\begin{table}[!t]
\setlength{\tabcolsep}{2pt}
    \centering
    \caption{\textit{Cityscapes}. Test performance for three tasks: 19-class semantic segmentation, 10-class part segmentation, and disparity. }
    \vskip 0.11in
\scriptsize
\begin{tabular}{lcccccccccccc}
\toprule\\
 &  &  & \multicolumn{2}{c}{Semantic Seg.} &  & \multicolumn{2}{c}{Part Seg.} &  & {Disparity}  \\
 \cmidrule(lr){4-5} \cmidrule(lr){7-8} \cmidrule(lr){10-10}
 &  &  & mIoU $\uparrow$ & Pix Acc $\uparrow$ & & mIoU $\uparrow$ & Pix Acc $\uparrow$  &  &  Abs Err $\downarrow$  & $\mathbf{\Delta \%} \downarrow$ \\
 \midrule
 & \multicolumn{2}{c}{STL} & $48.64$ & $91.01$ &  & $53.60$ & $97.62$ &  & $1.108$ &  \\
  \midrule
 & \multicolumn{2}{c}{LS} & $37.66$ & $88.63$ &  & $40.92$ & $96.98$ &  & $1.105$ & $~~~9.84$ \\
 & \multicolumn{2}{c}{PCGrad} & $39.10$ & $89.31$ &  & $41.71$ & $97.14$ &  & $1.133$ & $~~~9.28$ \\
& \multicolumn{2}{c}{CAGrad} & $39.45$ & $89.04$ &  & $51.95$ & $97.54$ &  & $1.098$ & $~~~4.66$ \\
 & \multicolumn{2}{c}{Nash-MTL} & $51.14$ & $91.59$ &  & $56.99$ & $97.87$ &  & $1.066$ & $-3.23$ \\
 \midrule
 
 & \multicolumn{2}{c}{GCS} & $37.45$ & $88.62$ && $41.14$ & $96.97$ &&  $1.124$ & $~10.19$\\
 & \multicolumn{2}{c}{OL-AUX} & $27.63$ & $89.34$ && $51.12$ & $97.52$ && $1.397$ & $~15.16$\\
 & \multicolumn{2}{c}{AuxiLearn} & $36.18$ & $88.24$ && $40.51$ & $96.95$ && $1.141$ & $~11.3$ \\
 \midrule

 & \multicolumn{2}{c}{AuxiNash{} } & $\mathbf{52.52}$ & $\mathbf{91.91}$ &  & $\mathbf{58.53}$ & $\mathbf{97.93}$ &  & $\mathbf{1.027}$ & $\mathbf{-5.15}$ \\
 \bottomrule
\end{tabular}%
\label{tab:cityscapes}
\end{table}

\subsection{Controlling Task Preference} \label{sec:multimnist}
In this section, we wish to better understand the relationship between the preference $p$ and the obtained solution.  We note the preference vector only implicitly affects the optimization solution through the bargaining solution $\alpha$.

Here, we show that controlling the preference vector can be used to steer the optimization outcome to different parts of the Pareto front, compared to the NashMTL baseline.
We consider MTL setup with 2 tasks and use the Multi-MNIST \citep{sabour2017dynamic} dataset. In Multi-MNIST two images from the original MNIST dataset are merged into one by placing one at the top-left corner and the other at the bottom-right corner. The tasks are defined as image classification of the merged images. 
We run AuxiNash{} $11$ times with varying preference vector values $p$ and fix it throughout the training. For both tasks we report the classification accuracy. For Nash-MTL we run the experiments with different seed values. For both methods we train a variant of LeNet model for $50$ epochs with Adam optimizer and $1e-4$ as the learning rate. 

Figure~\ref{fig:multimnist} shows the results. AuxiNash{} reaches a diverse set of solutions across the Pareto front while Nash-MTL solutions are all relatively similar due to its symmetry property. 


\subsection{Analyzing the Effect of Auxiliary Set}\label{sec:aux-set}



\begin{table}[h]
\centering
    \caption{\textit{The effect of auxiliary set:} We report the mean IoU, along with the $\%$ change w.r.t STL performance.}
    \vskip 0.11in
\scriptsize
\begin{tabular}{lcccc}
\toprule
 &  \multicolumn{2}{c}{Cityscapes} & \multicolumn{2}{c}{NYUv2} \\
\cmidrule(lr){2-3} \cmidrule(lr){4-5}
 &  mIoU $\uparrow$  & Change $\%$ $\uparrow$ &  mIoU $\uparrow$  & Change $\%$ $\uparrow$ \\
\midrule
STL & $48.64$ &  & $38.30$ \\ 
STL Partial & $45.97$  & $-5.48$ &  $36.54$ &  $-4.59$\\
\midrule
AuxiNash{} &  $52.52$ & $~~~7.97$ & $40.79$ & $~~~6.50$ \\
AuxiNash{} Aux. Set & $51.81$  & $~~~6.51$ & $38.94$ & $~~~1.67$ \\
\bottomrule
\end{tabular}
\label{tab:aux_set}
\end{table}

One important question is on what data to evaluate the generalization loss $\mathcal{L}_V$. It would seem intuitive that one would need a separate validation set for that since estimating $\mathcal{L}_V$ on the training data may be biased. In practice, some previous works use a held-out auxiliary set \citep{NavonAMCF21}, while others use a separate batch from the training set \citep{liu2019self,liu2022auto}. While using an auxiliary set might be more intuitive, it requires reducing the available amount of training data which can be detrimental in the low-data regime we are interested in. 

We empirically evaluate this using the NYUv2~\citep{silberman2012indoor} and Cityscapes~\citep{Cordts2016Cityscapes} datasets. See Section~\ref{sec:scene-under} for more details. We choose semantic segmentation as the main task for both datasets. We compare the following methods (i) \textit{STL}: single task learning using the main task only, (ii) \textit{STL Partial}: STL using only $90\%$ of the training data, (iii) \textit{AuxiNash{}}: our proposed method where we optimize the preference vector using the entire training set, (iv) \textit{AuxiNash{} Aux. Set}: our proposed method, where we optimize the preference vector using $10\%$ of the data, allocated from the training set

We report the mean-IoU metric (higher is better) along with the relative change from the performance of the STL method. The results suggest that the drawback of sacrificing some of the training data overweighs the benefit of using an auxiliary set. This result aligns with the observation in~\citet{liu2022auto}.



\subsection{Scene Understanding}\label{sec:scene-under}

We follow the setup from \citet{Liu2019EndToEndML, liu2022auto, navon2022multi} and evaluate AuxiNash{} on the NYUv2 and Cityscapes datasets \citep{silberman2012indoor, Cordts2016Cityscapes}. 
The indoor scene NYUv2 dataset \citep{silberman2012indoor} contains 3 tasks: 13 classes semantic segmentation, depth estimation, and surface normal prediction. The dataset consists of $1449$ RGBD images captured from diverse indoor scenes. 

We also use the Cityscapes dataset \cite{Cordts2016Cityscapes} with 3 tasks (similar to~\citet{liu2022auto}): 19-class semantic segmentation, disparity (inverse depth) estimation, and 10-class part segmentation~\citep{de2021part}. To speed up the training phase, all images and label maps were resized to $128 \times 256$. 

For all methods, we train SegNet \citep{badrinarayanan2017segnet}, a fully convolutional model based on VGG16 architecture. We follow the training and evaluation procedure from \citet{Liu2019EndToEndML, liu2022auto, navon2022multi} and train the network for 200 epochs with Adam optimizer \citep{Kingma2015AdamAM}. We set the learning rate to $1e-4$ and halved it after $100$ epochs. 

The results are presented in Table~\ref{tab:nyu} and Table~\ref{tab:cityscapes}. Observing the results, we can see our approach AuxiNash{} outperforms other approaches by a significant margin. It is also important to note that several methods achieve a positive $\%\Delta$ score, meaning they performed worse than simply ignoring the auxiliary tasks and training on the main task alone. We believe this is due to the difficulties presented by optimizing with multiple objectives. 



\subsection{Semi-supervised Learning with SSL Auxiliaries}

\begin{table}[h]
    \setlength{\tabcolsep}{3pt}
    \centering
    \caption{\textit{CIFAR10-SSL}. Test performance for classification with a varying number of labeled data. Values are averages over 3 random seeds.}
    \vskip 0.11in
    \resizebox{0.95\linewidth}{!}{%
    \begin{tabular}{lcc}
    \toprule
    & CIFAR10-SSL-5K & CIFAR10-SSL-10K \\
   
    \midrule
    STL & $79.31 \pm 0.31$ & $83.75 \pm 0.18$\\
    \midrule
    LS & $83.17 \pm 0.54$ & $86.16\pm 0.39$ \\
    PCGrad & $82.71 \pm 0.16$ &  $86.17\pm 0.34$ \\
    CAGrad & $85.89\pm 0.63$  & $87.82 \pm 0.28$    \\
    Nash-MTL & $\mathbf{86.69\pm 0.14}$ & $\mathbf{88.68 \pm 0.14}$  \\
    \midrule
    GCS & $83.09\pm 0.34$ & $86.47\pm 0.56$  \\
    OL-AUX & $81.44 \pm 1.06$ & $85.49 \pm 0.73$ \\
    AuxiLearn & $82.83 \pm 0.57$ & ${85.52 \pm 0.57}$ \\
    \midrule
    AuxiNash{} (ours) & $\mathbf{87.01 \pm 0.52}$ & $\mathbf{88.81 \pm 0.34}$ \\
    \bottomrule
    \end{tabular}
    }
    \label{tab:cifar_ssl}
\end{table}

In semi-supervised learning one generally trains a model with a small amount of labeled data, while utilizing self-supervised tasks as auxiliaries to be optimized using unlabeled training data. 

We follow the setup from \citet{shi2020auxiliary} and evaluate AuxiNash{} on a Self-supervised Semi-supervised Learning setting \citep{zhai2019s4l}. We use CIFAR-10 dataset to form 3 tasks. We set the supervised classification as the main task along with two self-supervised learning (SSL) tasks used as auxiliaries:
(i) Rotation (ii) Exempler-MT. In Rotation, we randomly rotate each image by $[0^{\circ}, 90^{\circ}, 180^{\circ}, 270^{\circ}]$ and optimize the network to predict the angle. In Exempler-MT we apply a combination of three transformations: horizontal flip, gaussian noise, and cutout. Similarly to contrastive learning, the model is trained to extract invariant features by encouraging the original and augmented images to be close in their feature space. For the supervised task we randomly allocate samples from the training set. We repeat this experiment twice with $5K$ and $10K$ labeled training examples.
The results are presented in Table~\ref{tab:cifar_ssl}. AuxiNash{} significantly outperforms most baselines.

\subsection{Audio Classification}

\begin{table}[h]
\centering
\centering
    \caption{\textit{Speech Commands}. Test accuracy for speech classification, for models trained with $1000$ and $500$ training examples.}
    \vskip 0.11in
\begin{tabular}{lcc}
\toprule
& SC-500 &  SC-1000 \\
\midrule
STL   & $95.8 \pm 0.1 $ & $96.4 \pm 0.1$ \\
\midrule
LS  & $95.7 \pm 0.2$ & $96.7 \pm 0.1 $ \\
PCGrad  &  $95.7 \pm 0.1$ & $96.7 \pm 0.1 $ \\
CAGrad  & $95.7 \pm 0.2 $   & $95.7 \pm 0.1 $ \\
Nash-MTL  & $95.7 \pm 0.2 $  & $96.6 \pm 0.3 $\\
\midrule
GCS  & $96.3 \pm 0.1$  & $96.9 \pm 0.1 $\\
OL-AUX  & $96.2 \pm 0.2$ & $96.9 \pm 0.1 $\\
AuxiLearn  & $96.0 \pm 0.1 $ & $97.0 \pm 0.1 $\\
\midrule
AuxiNash{} (ours) & $\mathbf{96.4 \pm 0.1}$ & $\mathbf{97.2 \pm 0.1}$\\
\bottomrule
\end{tabular}
\label{tab:sc}
\end{table}


We evaluate AuxiNash on the speech commands (SC) dataset \citep{warden2018speech}, which consists of $\sim50$K speech samples of specific keywords. The data contains 30 different keywords, and each speech sample is one second long. We use a subset of the SC containing audio samples for only the 10 numbering keywords (zero to nine). As a pre-processing step, we use a short-time Fourier transform (STFT) to extract a spectrogram for each example, which we then fed to a convolutional neural network (CNN). We evaluate AuxiNash{} on 10 one-vs-all binary classification tasks. 
We repeat the experiment with a training set of sizes 500 and 1000. The results are presented in Table~\ref{tab:sc}.
\section{Conclusion and Future Work}\label{sec:con}
In this work, we formulate  auxiliary learning as an asymmetric bargaining game and use game-theoretical tools to derive an efficient algorithm. We adapt and generalize recent advancements in multi-task learning to auxiliary learning and show how they can be automatically tuned to get a significant improvement in performance. 

We evaluated AuxiNash{} on multiple datasets with different learning setups and show that it outperforms previous approaches by a significant margin. Across all experiments, it is noticeable that MTL methods perform better than auxiliary learning ones although the former treat equally the primary task and the auxiliary tasks. We suspect that this is caused by conflicting gradients and by the fact that gradient norms may vary significantly across tasks.
These results emphasize the connection between auxiliary learning and multi-task optimization. In many examples, the benefit of the auxiliary task was diminished or even completely negated by poor optimization. Thus, we suggest that auxiliary learning research should be closely aligned with MTL optimization research to effectively utilize auxiliary tasks.   

\section{Acknowledgements}

This study was funded by a grant to GC from the Israel Science Foundation (ISF 737/2018), and by
an equipment grant to GC and Bar-Ilan University from the Israel Science Foundation (ISF 2332/18).
AN and AS are supported by a grant from the Israeli higher-council of education, through the Bar-Ilan data science institute (BIU DSI). 


