Optimization with Access to Auxiliary Information
Authors: El Mahdi Chayti
Sai Praneeth Karimireddy
Venue: Accepted by TMLR ()

Abstract: We investigate the fundamental optimization question of minimizing a \emph{target} function $f(x)$, whose gradients are expensive to compute or have limited availability, given access to some \emph{auxiliary} side function $h(x)$ whose gradients are cheap or more available. This formulation captures many settings of practical relevance, such as i) re-using batches in SGD, ii) transfer learning, iii) federated learning, iv) training with compressed models/dropout, etcetera. We propose two generic new algorithms that apply in all these settings; we also prove that we can benefit from this framework under the Hessian similarity assumption between the target and side information. A benefit is obtained when this similarity measure is small; we also show a potential benefit from stochasticity when the auxiliary noise is correlated with that of the target function.

Published in Transactions on Machine Learning Research (02/2024)
Optimization with Access to Auxiliary Information
El Mahdi Chayti EPFL
el-mahdi, hhw.hhdddd.chhllpppp...cc.c
Sai Praneeth Karimireddy UC Berkeley
sa.karimnnrreddy@eeeeeeeee....e edu
Reviewed on OpenReview: https: // openreview. net/ forum? id= koYggSkH8
Abstract
We investigate the fundamental optimization question of minimizing a larget function f(xx), whose gradients are expensive to compute or have limited availability, given access to some auriliary side function h(x)) whose gradients are cheap more available. This formulation captures many settings of practical relevance, such as i) re-using batches in SGD, ii) transfer learning, iii) federated learning, iv) training with compressed models/dropout, Et cetera. We propose two generic new algorithms that apply in all these settings; we also prove that we can benefit from this framework under the Hessian similarity assumption between the target and side information. benefit obtained when this similarity measure small; we also show a potential benefit from stochasticity when the auxiliary noise is correlated with that of the target function.
1 Introduction
Motivation.
Stochastic optimization methods such as SGD (Robbins & Monro 1951b) or Adam (Kingma & Ba 2014) are arguably at the core of the success of large-scale machine learning (LeCun et al.) 2015 Schmidhuber 2015). This success has led significant (perhaps even excessive) research efforts dedicated designing new variants of these methods (Schmidt et al. 2020 In all these methods, massive datasets are collected centrally on server, and immense parallel computational resources of data center are leveraged to perform training (Goyal et al. 2017 Brown et al. 2020). Meanwhile, modern machine learning is moving away from this centralized training setup with new paradigms emerging, such as i) distributed/fedeen /federated learning, ii) semi-supervised learning, iii) personalized/ saalliized/mmiii-taaaa.a mulliitask learning. iv) model compression, Et cetera. Relatively little attention has boen dovoted to these more practical settings from the optimization community. In this work, we focus on exlending the framework and lools of stochastic optimization ion ion to bear on these novel problems.
At the heart of these newly emergent training paradigms lies the following fundamental optimization question: We want to minimize target loss function f((x), but computing its stochastic gradients is either very expensive or unreliable due to limited data. However, we assume having access to some auxiliary loss function h(x) whose stochastic gradient computation relatively cheaper or more available. For example, in transfor learning, f() would represent the downstream task we care about and for which we have very little data available, whereas h(x)) would be the pretraining task for which we have plenty of data (Yosinski al., 2) Similarly, in semi-supervised learning, f(x) would represent the loss over our clean labeled data, whereas h(z) represents the loss over unlabeled noisily labeled data (Chapelle et al.) 2009 Our challenge is the following question:
How we leverage auxiliary h(x:) to speed up the optimization of our target loss function f(x)?
Of course, if f()) and h(z) are entirely unrelated, our task is impossible, and we cannot hope for any speedup over simply running standard stochastic optimization methods (e.g., SGD) on f(x). Thus, the additional

---

Published in Transactions on Machine Learning Research (02/2024)
question before us is to define and take advantage of useful similarity measures between f(x) and h(æ)) In this work, we will mainly consider Hessian similarity (defined later in Assumption 3.3) and leave devising more practical similarity measures as a future direction.
Contributions. The main results in this work are
We formulate the following as stochastic optimization with auxiliary information: i)Ro-using batches in SGD, ii) Semi-supervised learning, iii) transfer learning, iv) Federated Learning, v) personalized learning, and vi) training with sparse models.
We show useful and simple trick (Fx3) to construct biased gradients using gradients from an auxiliary function.
Based on the above trick, we design a biased gradient estimator of f(x;), which reuses stochastic gradients of f(x) and combines it with gradients h(x).
We then use this estimator to develop algorithms for minimizing smooth non-convex functions. Our methods improve upon known optimal rales that don't use any side information.
Related work. Optimizing one function f while accessing another function h (or its gradients) is an important idea that has only been considered in specific cases in machine learning and optimization communities. To the best of our knowledge, this problem has never been regarded in all of its generality before this time. For this reason, we are limited to only citing works that used this idea in particular cases. Lately, masked training of neural networks was considered, for example, in (Alexandra et al. 2019 Amirkeivan et al.) 2021); this approach is a special case of our framework, where the auxiliary information is given by the sub-network (or mask). In distributed optimization, (Shamir et al. 2013) define sub-problems based on available local information; the main problem with this approach is that the defined sub-problems need to be solved precisely in theory and to high precision in practice. In Federated Learning (Konecny et al. 2016 McMahan et al. [017a] Mohri et al. 2019), the local functions (constructed using local datasets) can be seen as side information. Applying our framework recuperates an algorithm close to MiMe (Karimireddy et al., 2020a). In personalization, Chayti et al. (2021) study the collaborative personalization problem where one user optimizes its loss by using gradients from other available users (that are willing to collaborate); again, these collaborators can be seen as side information, one drawback of the approach in (Chayti al., (021] is that they need the same amount of work from the main function and the helpers, in our case we alleviate this by using the helpers more.
There is also auxiliary learning [Baifeng et al Aviv et al. Xingyu et al.) that is very similar to what we are proposing in this work. Auxiliary learning also has the goal of learning one given task using helper tasks, however, all these works come without any theoretical convergence guarantees, furthermore, our approach is more general.
The proposed framework is general enough to include all the above problems and more. More importantly, don't explicitly make assumptions on how the target function f is related to the auxiliary side information h (potentially set of functions) like in Distributed optimization or Federated learning where we assume f is the average of the side-information h. Also, it is not needed to solve the local problems precisoly as expected by DANE (Shamir et al. 2013).
2 General Framework
Our main goal is to solve the following optimization problem:
min f()),
(1)
wERs
and we suppose that we have access to an auxiliary function h(x)) that is related to f in sense that we don't specify at this level.
Specifically, we are interested in the stochastic optimization framework. We assume that the target function is of the form f(z) := Ee, (f(:; Ey] over æ Idd while the auxiliary function has the form h(x) := E,g [M(:;; En]] defined over the same parameter space. We will refer to these two functions simply as f and and stress that they should not be confused with f(; and C() It is evident that if both functions and h
2

---

Published in Transactions on Machine Learning Research (02/2024)
are unrelated, we can't hope to benefit from the auxiliary information h. Hence, we need to assume some similarity between ʃ and h. In our case, propose to use the hessian similarity (defined in assumption 3.3
Many optimization algorithms can be framed as sequential schemes that, starting from an estimate æ of the minimizer, compute the next (hopefully better estimate) xt by solving a potentially simpler problem
xt arg min (f(z))) x))
(2)
ZER"
where f(::z) is an approximation of f around the current state a, R(2; a:) is a regularization function that measures the quality of the approximation and X is a parameter that trades off the two terms.
For example, the gradient descent algorithm is obtained by choosing f(z;z) = f()) + Vf(x) (z x), R(z;æ) = 2 = - =12 and À = - where is the stepsize. Mirror descent uses the same approximation f but a different regularizer x(2;x) (=(2;))) where D& is the Bregman divergence of certain strongly-convex function #
We take inspiration from this approach in this work. However, we would like to take advantage of the existence of the auxiliary function h. We will mainly focus on first-order approximations of f throughout this work; we will also fix the regularization function R(2; x) = 1 I|| - x we note that our ideas can be easily adapted other choices of R and more involved approximations of f.
For any function h, we can always write f as
((2) = h((z)
+
(() - (2)
cheap
expensive
we call the first term "cheap", but this should not be understood strictly; can also, for example, mean more available.
A very straightforward approach is to use f whenever it is available and use h as its proxy whenever it is not; we call this approach the naive approach. This approach is equivalent to simply ignoring (in other words, using a zeroth-ordes approximation of) the "expensive" part.
A more involved strategy is to approximate the "exponsive" part f(z) h(z) as well but not as much as the "cheap" part h(2). We can do this by approximating f(z) - l1(2) around ( a global stale, or a snapshot, the idea is that it is the state of f) and approximating h(z) around y (a local state in the sense that it is updated by h). Doing this, we get the following update rule:
1
sEad y* E org min (f(=;),)) + - || y11))
2n
where fzz;y,)) = h(y) + f(x) h(z) + Vhly) T T(x (a-
- y) + (Vh(z)
+ + - x).
This is equivalent to
y- y (Vhly)> VM(>) + vf()))
(3)
We will refer to (3) as a local step because it uses a new gradient of h to update the state. The idea is that for each state æ of f, we perform a number of local steps, then update the state x based on the last "local" steps.
Control variates and SVRG.
3 can be understood as generalization of the control variate idea used in
SVRG (Johnson & Zhang 2013 To optimize function f(æ) := Σi f((x), SVRG uses the modified gradient JS = V(())) V (x) + f((z) where æ is a snapshot that is updated less frequently and is sampled randomly so that this new gradient is still unbiased. The convergence of SVRG is guaranteed by the fact that the "error" of this new gradient Elygsv - Vf |1 = O(ly - x|| [] so that if y - x + O, then convergence guaranteed without ncoding to take small step-sizes. The main idea of our work to use instead of f. another function h that is related to f: this means using gradient g = Vh(y) - Vh(z) VV)(), then if we can still guarantee that the error is Ollyy xn (1)) everything should still work fine.
3

---

Published in Transactions on Machine Learning Research (02/2024)
Other Variance reduction techniques. given the form of (3) that is very similar to the SVRG gradient, it is natural to ask what would happen when using a form similar to other variance reduction techniques such as SARAH (Nguyen et al. 2017) (this will amount to choosing a gradient g' = Vh(y') - + with g²= -Vfl" == z)). Unfortunately, this choice leads to the same theoretical rate obtained by the SVRG-like choice, the main reason being that on top of the biasedness of SARAH, the fact that h is potentially different. from f (even average) introduces another biasodness, which limits the potential gain; morcover, it not evident how to treat the case where we only have access stochastic gradients of f.
What if we can't access the true gradient of f? When f is not finite average; we can't access its true gradient: in this case, we propose replacing the "correction" V((=)= - Vh(æz) by quantity my-h that is a form of momentum (takes into account past observed gradients of f - h), the idea of using momentum is used to stabilize the estimate of the quantity Vf(x) Vh(æ) as momentum can be used to reduce the variance. Specifically, we use g Vh(y) + m We note that for this estimate we have Figg fyy = O(lv =1 [|my-h- Vf(2) + Vh(x) [2) which means that g approximates V.((y) as long as y is not far from and ms-h good estimate of the quantity Vf(=) Vh(æz)
Local steps or subproblem? note that another possible approach is, instead of defining local steps based on h, to define a subproblem that gives the next estimate of f directly by solving
x
1 x x12) + E arg min (h(y) + m x) + 2n yERd
(4)
Our results can be understood as approximating a solution to this sub-optimization problem +
Notation. For a given function J, we denote gr((;Er) an unbiased estimate of the gradient of J with randomness Ej.
General meta-algorithm. Based on the discussion above, we propose the (metaa)-lgorithm ! at the beginning of each round i, we have an estimate x'-1 of the minimizer. We sample a new (y-k; and compute 95 9g-n( (g-)), noisy unbiased estimate of the gradient of f f h; we then update m a momentum of f-fhh. h. We transfer both x and m the helper h which uses both to construct a set of biased gradicnts di. of 1)( that are updated by h. These biased gradients are then used to update the "local" states vi, then / updates its own state x' based on the last local states vō throughout this work, we simply take x, = y-k
Algorithm 1 stochastic optimization of f with access to the auxiliary h.
Require: 2o, 7, T, K
for t 1 to T do sample g)-n(x'-1 11 (1_- -/-hh) Vf((=-1)- - Vh(x--1)
update m m/ja define y = x t111
(((x--1)- V/((x-11) & momentum
for k= to K do
sample gh (
) Vhly
use it and m' to form d vf(((-)
y = nd
end for update x² end for
For our purposes we can take di = gn 1: ) + which should be a good approximation V f and m is a momentum of f h, we will consider two options: classical momentum or MVR (for momentum based variance reduction (Cutkosky & Orabona 2019
Decentralized auxiliary information. More generally, we can assume having access to N auxiliary functions ha(x) := Eç,, [, {. While we can treat this case by taking h = (L/N) ΣN hy, we propose a more interesting solution that also works if the helpers h, are racietralized and cannot live in the same server.
4

---

Published in Transactions on Machine Learning Research (02/2024)
In this case, we sample set St of helpers, each h2 E St will do the updates exactly as in A but this time o' will be constructed using all (vi,k E 5*). In our case, propose to use the average x' (1/S) Vi
3 Algorithms and Results
We discuss here some particular cases of Algorithm based choices of mi-n and di which we kept little bit vague purposcfully.
We will consider mainly two approaches. We call the first one the Naive approach and the second one we refer to as Bias correction.
We remind the reader that we can take dj = gh (1 + m
suggested by its name, naive; it simply ignores the part h or, in other words, sets m O. The main idea is to use gradients (or gradient estimates) of f whenever they are available and use gradients of h when gradients of f are not available. In our case, we alternate between one step using a gradient of f and (K 1)-steps using gradients of h without any correction. We will show that this approach suffers heavily from the bias between the gradients of f and h. It worth noting that in federated learning, this approach corresponds to Federated averaging (McMahan el al. 2017a). We remind the reader that we can take di 9n (v(-11 ct.k) + +mý---
Naive approach. This approach is exactly
Bias correction. In the absence of noise, this approach simply implements Specifically, the inner loop in Al Algorithm T does the following:
v 1 (Vh((()- Vh(w'-1) V Vf(x"-1)
c
In the noisy case (when we can only have access to noisy gradients of f), approximate the above step in the following way:
y -- (yk mi
where m/-n is a momentum of f -hh. h. We consider two methods for defining this momentum:
m (1 a)m 1-1 + ag) ax (f-hh)
(AuxMOM),
(5)
m (1 a)m 1-1
f-h + ag - (x' ,/-1
+ (1 - a)(g)))(())) ( 12- (11
(AuxMVR).
(6)
AuxMOM simply uses the classical momentum, whereas AuXMVR uses the momentum- variance reduction technique rotrode in (Cutkosky & Orabona 2019).
Assumptions. To analyze our algorithms, we will make the following assumptions on the target and the helper h.
Assumption 3.1. (Smoothness.) We assume that f has L-Lipschitz gradients and satisfy
[V Vf < L|x vll2-
Assumption 3.2. (Variance.)
The stochastic gradients gr (r), gn (æ;; (a) and gr - Cy-n) are unbiased,
and satisfy
Ex, (1g1gg
J (1,h, h).
5

---

Published in Transactions on Machine Learning Research (02/2024)
In Assumption 3.2 we assume that directly have access to unbiased gradient estimates of f h; this does not restrict in any way our work since 9, Ih is such an estimate; however, this last estimate has a variance of -i = =o + x in general, it is possible to have correlated estimate such that - < < + o If the batches ε and En are drawn such that g and gn are positively correlated, then is even possible to have - <oj.
Assumption 3.3. Hessian similarity. Finally, we will assume that for some & E [0,27] we have
VVh<))l 8.
Note that if h(-) is also smooth (satisfies Assumption 3.1 then we would have Hessian similarity with 8 < 2L since
(=) - || f())ll2 + [|)2 S 2L.
As sanity checks, = 0 corresponds to = L (this case should not lead to any benefit), and = f gives 0; we will consider these two cases to verify our convergence rates.
Discussion of the assumptions. Assumptions 3.1 and 3.2 are very common assumptions in the optimization literature. Under these two assumptions, it is well- known that SGD (Robbins & Monro 1951a Kiefer &
Wolfowitz 1952 has optimal convergence rate. Assumption 3.3 used extensively in Federated Learning
Karimireddy et al. 2020a b and was considered for personalization (Chayti et al. 2021
Relaxing the Hessian similarity. Jingzhao et al. propose a generalized smoothness assumption where the norm of the Hessian can grow with the norm of the gradient. We believe it possible to extend our theory to accommodate such an assumption. In the same spirit, we can let [(²)(x)) V2h(z)ll2 grow with (x) More important than this is finding similarity measures that apply to some of the potential applications we cite in Section 5
4 Results
We start by showing that the convergence rate of the naive approach is dominated by the gradient bias. We then show the convergence rate of our momentum variant AuxMOM that will be compared to SGD/GD. We will also state the convergence rate of our AuxMVR variant and compare it to MVR/GD. Notation. We assume f is bounded from below and denote f = inf fxx). f
=ER"
Remark. We would like to note that while we state our results for the case of one helper h, they also apply without needing any additional assumption when we have N decentralized helpers h hy from which we sample S = helper at random. In the case where S > 1, we need an additional weak-convexity assumption to deal with the averaging performed at the end of each step; this general case is treated in Appendix C.4
4.1 Naive approach
In this section, show the convergence results using the naive approach that uses gradient of f followed by K 1 gradients of h. For the analysis of this case (and only of this case), we need to make assumption on the gradient bias between f and h.
Assumption 4.1. The gradient bias between f and h is (m, boundde:: Va E Rd [[Vf(()) Vh(=))l < m| m|[Vf(>)11 + =
Theorem 4.2. There erists f and satisfying assumptions 3. such that KT L
3.
3.3
4.
with = 0, o, = σ% = 0
ΣT [VV Q({?)
Using the biased SGD analysis in Ajalloeian & Stich 2020), it is easy to prove an upper bound, but we only need a lower bound for our purposes. Theorem 4.2 shows that this naive approach cannot guarantee convergence to less than <² (up some constant).
Note. Theorem 4.2 is very loose for Federated Averaging as, in this case, the function f is directly tied to the helper entities (it is the average). Nevertheless, it's worth noting that heterogeneity and client drift,

---

Published in Transactions on Machine Learning Research (02/2024)
which are akin to gradient bias, are recognized factors that constrain the performance of FedAVG. Consequently, there have been efforts to mitigate these issues through approaches such as those discussed in KKarimiredyy et al. 2020b at.
In what follows, we will show that our two proposed algorithms solve this bias problem.
4.2 Momentum based approach
We consider the instance of Algorithm 1 with the momentum choice in 5 For clarity, a detailed Algorithm can be found the Appendix Algorithm|
Convergence rate. We prove the following theorem that gives the convergence rate of this algorithm in the non-convex case.
Theorem 4.3. Under assumptions A 43.1 and 1 = min( H, 1926K
3.2 3.3
For m such that E S o a = max( 368Kn)
Fu we get the following
T44
K-1
E E S (1
L3F
(L (L+
o7
+
+
KT
T
KT
T K
km0
Where 1 f(x²) - ," E =Bllm v((x")
E[[lm
Vh(x")) and 3 = 04 of
+ ))
Note. the condition E < - can be ensured by using a batch size T' times larger to estimate m this will at most result in doubling the number of steps T. In practice, we did not need to ensure this condition. We also note the term o K, which corresponds to the error of solving the inner problem 4 Remarkably, although we are using SGD steps of the helper h, we get 1/K error instead of 1/v K; this can be explained by the fact that we initialize using the (approximate) solution of the last inner problem which accelerates convergence; we can potentially get faster rates by using variance reduction methods on h.
We will compare this rate that of SGD under the same amount of work asked from f: O (V LF LF
which corresponds to 0 (F in expectation i.e. a point & such that E[I[V](() < e (the expectation taken over the algorithm that generated t).
LF 8² + 8
stochastic gradient calls of f necessary to get an e-stationary point à
In comparison, based on Theorem we can show the following corollary:
Corollary 4.4 (Iteration complexity of AuxMOM). Let f be chosen uniformly at random from the iterates generated by AurMOM. To guarantee E[[] ( Se, e, AurMOM needs at most
8F 0 (
8F
o
LF
+ 1 40
L
(stochastic) gradient calls of f.
In particular, see that in the dominating order of 1/s, when access to gradients of is stochastic (noisy case), we replaced Lo} by 807_,, which might be very small, either because ö < L or oî & o7. In the noiseless case (when we have full access to gradients of f), we replaced L. by 5.
Of course, the gain that we obtain is not for free; comes at the cost of using K = 0 1840 1o +1) inner steps of the helper h.
Sanity checks. For h = S, we have 5 = 0, we get the iteration complexity 00 the rate of KT-steps of SGD. For O, we have 5 L: this case, we don't gain anything as should be the case.
LF
which corresponds
7

---

Published in Transactions on Machine Learning Research (02/2024)
SVRG in the non-convex setting. In particular, because Theorem 4.3 also applies for the case where we have multiple helpers, and sample each time S = helpers. we get that SVRG converges in this case as (( which matches the known SVRG rate (Reddi et al. 2016) (up to 5 being small). More interestingly, we obtain the same convergence rate by using only one batch (no need sample) if the batch is representative enough of the data (i.e., satisfies our Hessian similarity Assumption 3.3)
Local steps help in federated learning. By employing the decentralized version of this theorem (as detailed in Appendix [.4), we can ascertain that local steps (denoted as K in our context) indeed provide a beneficial contribution to Federated Learning. This finding aligns with the results presented in (Karimireddy
ct al. 2020a
4.3 MVR based approach
We consider now the instance of Algorithm [ which uses the MVR momentum in in 6 The detailed algorithm can be found in the Appendix Algorithm 5
Stronger assumptions. For the analysis of this variant, we need a stronger similarity assumption Assumption 4.5. Stronger Hessian similarity.
38 E [0, L) VC5-n : 9s-m((,Sy-n) is 6-Lipschitz.
stronger than its counterpart Assumption 3.3 used for AuxMOM. It is reasonable to need a stronger assumption since, already, when using the MVR momentum, a stronger smoothness assumption has to hold.
Assumption 4.5
Convergence of this variant. We prove the following theorem that gives the convergence rate of this algorithm in the non-convex case.
Theorem 4.6. Under assumplions A 3.
3.2 4.5
For m such that E S o'/n/T, for a
max #, 12566"(217²) and nj min (t. 1928K us the rate
1/3
F KT(L/2486K)
This choice gives
K
184326-T
B(IV o(( 51 h
2/3
(L O
(L+8K)r
0
+
KT
T
KT
KT
T
K
k=1
Baseline. Under the same assumptions and for the same amount of work, MVR or STORM Cutkosky &
Orabona 2019) has the rate: ( 2/3
(F
LFO T
this rate corresponds to needing at most O LF
63/4
LF
(stochastic) gradient calls of f to reach a point & such [())] < s or E-stationary point. This
rate /eetteraaionn complexity known to be optimal under the strong smoothness assumption: f(( is L-smooth for all & almost surely.
Using Theorem [.6] is easy show the following corollary:
Corollary 4.7 (Iteration complexity of AuxMVR). Let & be chosen uniformly at random from the ilerates generuted by AurMVR. To guarantee B[IlV/ (()) s E, AurMVR needs most
0(
0610011A 3/2
81
of
oh T.F + 1a,
LFa
(slochastic) gradient calls of f.
The same conclusions as for AuxMOM are valid here. In the noisy case, we replaced Loj by 807 which might be very small, either because å < L o7 < o7 In the noiseless case (when have full access to gradients of [), we replaced L by 8.
Again, this palential gain is obtained at the cost of using K = 0 0Z + 11y0 +1 inner steps of the helper h.

---

Published in Transactions on Machine Learning Research (02/2024)
5 Potential applications
The optimization with access to auxiliary information proposed is general enough that we can use it in many applications where we either have access to auxiliary information explicitly, such as in auxiliary learning or transfer learning, or implicitly, such as in semi-supervised learning. We present here a non-exhaustive list of potential applications.
Reusing batches in SGD training and core-sets. In Machine Learning, the empirical risk minimization consisting of minimizing function of the form (ax) v Σ [(),,()) is ubiquitous. In many applications,
want to summarize the data-set { by smaller potentially weighted subset CS {(E.. wy )= j=
for positive weights (w,), that add up one, this referred to as a core-set (Bachem et al. 2017) p. In this case we can set h(r)) [(w.)ECc w (L, E). An even sampler problem is when we sample a batch
B C {5 of size S N, one question we can ask is how can we reuse this same batch to optimize f? In this case we set h(x) = (1/b) ESEB [(x, {)- In the case where we have many batches [Bi we can set h,(x)= = B.) CeEn, L(x, E) for each i I and use our decentralized framework to sample each time a helper h.
Note. In case h is obtained using subset. B of the dataset defining J, there is a-priori a trade-off between the similarity between f and h mcasured by the hessian similarity parameter 5(B) and the cheapness of the gradients of h. A-priori, the bigger the size of B is, the easier it is to oblain small 5(B), but the more expensive it is to compute the gradients of h. Semi-supervised learning. In Semi-supervised Learning Zhu 2005). We have a small set carefully cleaned data Z directly related to our target task and a large set of unlabeled data ž. Let us also assume there an auxiliary pre-training task defined over the source data, e.g., this can be the popular learning with contrastive loss (Chen et al., (0200). In this setting, we have a set of transformations T which preserves the semantics of the data, two unlabeled data samples $2,52 2, and feature extractor da(+) - R parameterized by æ. Then, the contrastive loss is of the form: E( (()n(i) (T(()) (2)) where the loss tries to minimize the distance between the representations ((1) and dz while simultaneously maximizing distance to Φn (G2). Similarly, we also have target loss f: Z - IR which we care about; then, we can define
f(x) = [<cez[((r;())
and
h((x) = - &T ((( (51), or (T(())) on (n())
Another way our framework can be used for semi-supervised learning is by endowing the unlabeled data with synthetic labels (either random labels as we will see for logistic regression or via Pscudo-labeling (Lee) 2013)
and defining the helper as the loss over the unlabeled data with its assigned labels.
Transfer learning. For survey, see (Zhuang et al. 2020). In this case, in addition to cleaned data set Z we have access to Z pro-training source 2. Given a fixed mask M (for masking deep layers in a neural network) and loss E, we set
f(x) = Eçez [f(x; <)) and h(x) = E [(M 2 xx
Federated learning. Consider the problem of distribuutedl/edderatee learning where data is decentralized over N workers (MeMahan et al., 2017b). Let (F)(s))..,, represent the N loss functions defined over their respective local datasets. In such settings, communication is much more expensive (say M times more expensive) than the minibatch gradient computation time (Karimireddy et al. 2018). In this case, we set
f(x) N
Σ (x))) and ha(x:) = F.(x).
Thus, we want to minimize the larget function f(x) defined over all the workers' data but only have access to the cheap loss functions defined over local data. The main goal, in this case, is to limit the number of communications and use as many local steps as possible. Our proposed two variants are very close MiMeSGDm and MiMeMVR from (Karimireddy et al., 2020a).
Personalized learning. This problem is a combination of the federated learning and transfer learning

---

Published in Transactions on Machine Learning Research (02/2024)
problems described above and is closely related to multi-task learning (Ruder 2017 Here, there are N workers, each with task (Fi (Fi........, Fx(=)), and without loss of generality, we describe the problem from the perspective of worker 1. In contrast to the delayed communication setting above, in this scenario, we only care about the local loss Fi (z)) whereas all the other worker training losses (F,(z).....,F) (x())) constitute auxiliary data:
f(z) = [F((z) = Es, (x)
and for i >>> 2
(x) = [F((z) 1,
In this setting, main concern is the limited amount of training data available any particular worker if this was not an issue, we could have simply directly minimized the local loss Fi()).
Training with compressed models. Here, we want to train a large model parameterized by æ E R4. To decrease the cost (both time and memory) of computing the backprop, we instead mask (delete) a large part of the parameters and perform backprop only on the remaining small subset of parameters (Sun et al. 2017 Yu & Huang 2019p. Suppose that our loss function & defined over sampled minibatches and parameters Also, let suppose have access to some sparse/low moarse/oow-rnk masks (IMp M,,) from which choose. Then, can define the problem as
f(z) [<<; e) and h(x) -E ((LM
Thus, to compute a minibatch stochastic gradient of h(*) requires only storing and computing a significantly smaller model 1M O æ where most of the parameters are masked out. Let DM = diag(1M) be a diagonal matrix with the same mask as 1M- The similarity condition then becomes
f(x) - (MMM @ x) mllk 5.
The quantity above first computes the Hcssian on the masked parameters 1M O x and then is averaged over the various possible masks to compute EM [DM D2 @ DM] Thus, the parameter d here measures the decomposability of the full Hessian fz)(2) along the different masked components. Again, we do not need the functions f and to be related to each other in any other way beyond this condition on the Hessians they may have completely different gradients and optimal parameters.
Does the Hessian similarity hold in these examples? In general, the answer is since already smoothness does not necessarily hold. Also, this will depend on the models have and should be treated caso-by-case basis. However, we can see from the experiment section that our algorithms perform well even for deep learning models. This work is a first attempt to unify these frameworks; we do not pretend that our answers or algorithms are the final attempt. We hope to spark further research in this direction, both theoretically and practically.
Examples where it holds. There are two special and simple examples where this similarity assumption holds. In both semi-supervised linear and logistic regressions, note that the hessian does not depend the label distribution; for this reason, construct the helper h (based on unlabeled data) with 8 = 0 (under the assunption that unlabeled data come from the same distribution as that of labeled data).
endow the unlabeled data with any label distribution and
6 Experiments
Baselines. We will consider fine-tuning and the naive approach as baselines. Fine-tuning equivalent to using the gradients of the helper all at the beginning and then only using the gradients of the main objective f. We note that in our experiments, K = corresponds to SGD with momentum; this means we are also comparing with SGDm.
6.1 Toy example
We consider simple problem that consists in optimizing a function f(z) 1/2² by enlisting the help of the function h(x)= {1 + () </(1 0))2 for æ E R.
10

---

Published in Transactions on Machine Learning Research (02/2024)
Naive
AucHom
267
100
200
2-
20
30
25
20
10
50
Figure Effect of the bias C (zeta the figure) on the naive approach (Naive), AuxMOM and Fine Tuning (FT) for K = 10,6 = and γ) min(1/2, 1/()K)). mi(K))) We can see that the naive approach fails to converge for large bias values, whereas AuxMOM converges all the time, no matter the value of the bias. Fine Tuning converges much slower for small values of 6, but beats AuxMOM for =
Effect of the bias Ç. Figure shows that indeed our algorithm AuxMOM does correct for the bias. We note that in this simple example, having a big value of Ç means that the gradients of point opposite to those of f, and hence, it's better to not use them in a naive way. However, our approach can correct for this aulomatically and hence does not suffer from increasing values of Ç. In real-world data, it is very difficult. to quantify S, thus why we can still benefit little bit (in non-extreme cases) using the naive way.
10
deta-02
26
20
30
90
23
20 30
20
26
50
Figure 2: Effect of the similarity 8 (delta in the figure) both the naive approach (Naive), AuxMOM and Fine Tuning for K = 10,ç - 10 and r- - 0.5/(1 (1++/+++0 5) for Naive and AuxMOM and r = 0.5/(1+ 6) then eta = 0.5 for Fine Tuning. We can see that the naive approach fails to benefit from small values of AuxMOM does not suffer from the same problem, whereas Fine Tuning is slower than AuxMOM.
Effect of the similarity 8. Figure 2 shows how the three approaches compare when changing 5. We note that 8 = 0.1 corresponds to L.88 = K 10 the value used in our experiment; our theory predicts that for such values of 6, the convergence is as we were using only gradients of f.
6.2 Leveraging noisy or mislabeled data
We show here how our approach can be used to leverage data with questionable quality, like the case where some of the inputs might be noisy or, in general, transformed in a way that does not preserve the labels. A second example is when part of the data is either unlabeled or has wrong labels.
Rotated features. We consider simple feed-forward neural network (Linear(28 582) + ReLU
Linear(512, 512) + ReLU + Linear(512, 10)) to classify the MNIST dataset (LeCun & Cortes 2010 which is the main task f. As a helper function h, we rotate MNIST images by certain angle E (0. 45, 90, 180); the rotation plays the role of heterogeneity; it is worth noting that this is not simple data augmentation as numbers "meanings" are not conserved under such a transformation. We used a 256 batch size for f and a 64 batch size for h; our experiments changing the batch size of h to 256 or 512 led to similar results. We plot the test accuracy that is obtained using both the naive approach and AuxMOM.
First of all, Figure 3 shows that we indeed benefit from using larger values of K up to certain level (this is predicted by our theory), this suggests that we have somehow succeeded in making new gradient of out of cach gradient of h we had.
Next, Figure shows how much the rotation angle affects the performances of the naive approach and AuxMOM. Astonishingly, AuxMOM seems to not suffer from increasing the value of the angle (which we should increase the bias).
Figure 5 shows comparison with the fine-tuning approach as well.
11

---

Published in Transactions on Machine Learning Research (02/2024)
0.8
0.6
0.2
Km
K=10
Figure 3: Fifect of (K number times we use helper h) on the test accuracy of the main task (for an angle 15). We can see that our approach, our theory predicts, benefits from bigger values of K.
Nalve
AuxMom
1.0
1.0
0.8
0.8
0.5
0.6
0.4
angle=3
0.2
angle-180
Figure Test accuracy obtained using different angles as helpers, for 10, step size r = 0.01 momentum parameter 0.1. We that, astonishingly, AuxMOM does not suffer much from the change in the angle, whereas, as expected, the bigger the angle, the worse the accuracy on the main task for the naive approach.
1.0
0.6
NalveAig
0.4
Fine Tuning
20
40
*Stertionn500
Figure 5: comparison of The Naive approach, AuxMOM, and Fine Tuning for angle 90. Again, that while not suffering from the added bias, Fine Tuning is slower than AuxMOM.
Mislabeled data. In a similar experiment, the helper h is given again by MNIST images, but this time, we choose a wrong label for each image with probability p. Figure D shows the results.
Naive
AuxMorn
1.0
0.8
0.5
0.6
pa0.2
Pr0.5
p=0.8
20
20
40
elteraBerr/50
Figure 6: Test accuracy obtained using different probabilities p helpers, for K 10, step size n 0.01 and momentum parameter = 0.1. Again, astonishingly, AuxMOM does not suffer much from the change the angle, whereas, expected, the bigger the angle, the worse the accuracy the main task.
12

---

Published in Transactions on Machine Learning Research (02/2024)
bust accurracy for different algorithms
1.0
3.4-
Concel AUINON
Connet
WiO
Comeet
10
50
Mitendiare.50
Figure 7: Comparing Coresets with and without AuxMOM. We see that with AuxMOM, we reach higher accuracy, similar to using the true dataset (W/O).
tedt acourery Rered cherther
tedt ecceracs by effecet Woothees RAN33901
WC
20
Figure 8: CIFARIÓ and CTFAR100 experiments. Again, using AuxMOM leads higher accuracy, similar to using the true dataset (W/O), whereas using the coreset alone leads to loss in accuracy.
6.3 Training with Coresets
MNIST experiment. We consider again the MNIST dataset. This time, we randomly sample a subset that has one-fifth the size of the original training set; this subset will play the role of the coresct.
We compare running SGDm solely on the subset (referred to as Coreset) to training using AuxMOM with the coreset as helper (referred to as Coreset + AuxMOM). We also consider as baselines running SGDm on the same total amount of work performed by AuxMOM and SGDm on the coresct (referred to as W/O) and running on the same amount of work done by the main function on AuxMOM (referred as AuxMOM Coreset).
The results of this experiment shown in Figure 7 compared to W/O, whereas Coreset AuxMOM reaches the same accuracy W/O (it even beats it little). Again, we see that AuxMOM bests training alone (AuxMOM Coreset here).
We see that Coresct loses around 2% accuracy
CIFAR10/100 experiments. We performed the same experiments on the CIFAR10 and CIFAR100 datasets; again, we considered a randomly sampled coreset one-fifth the size of the original training set. We note that these experiments, we used simple convolutional neural networks (two convolutions, followed each by a max-pooling layer, followed by three linear layers, to which ReLu activation is applied, except for the last layer) and constant step-size strategy, which shouldn't lead to saate-of-the-att performance.
The results depicted in Figure 8 show that, similar to the experiment with the MNIST dataset, we observe that by using AuxMOM, we rival the performance of W/O, on the other hand, Coreset loses nearly 10% accuracy.
Varying the size of the coresct. We consider the CIFARI0 dataset and assess the performance of AuxMOM and training on the coresct alone for different coresct sizes (5%, 10%, and 25%). Figure shows how AuxMOM is only influenced in that it needs more iterations to reach the same accuracy for a smaller
13

---

Published in Transactions on Machine Learning Research (02/2024)
(PAR3O 3i
CINROO 30% slx corvee
OHAIO 25% Mie cn144
87-
51
Figure 9: Effect of varying the coreset size AuxMOM and pure coreset training. We see that the smaller the size of the coreset is, the worse the performance of training on the coreset alone; however, AuxMOM is only affected in terms of the number of iterations it needs to reach given accuracy, which increases as the size of the coreset decreases.
coreset size, whereas training on the coreset alone is highly affected by the size of the corset as we see clearly that the smaller this size is, the lower the reached accuracy is.
Overhead of AuxMOM over training alone. The only additional time AuxMOM needs is the time necessary for sampling a new batch from the original dataset, computing its gradient, and updating the momentum used by AuxMOM; it should be negligible in practice.
6.4 Semi-supervised logistic regression
We consider a semi-supervised logistic regression task on the "Mushrooms" dataset from the libsvmtools repository (Chang & Lin| 2011), which has 8124 samples, each with 112 features. We divide this dataset into three equal parts: one for training and, one for testing, and the third one is unlabeled. In this context, the helper task h is constituted of the unlabeled data which we assigned random labels. Figure IO shows indeed AuxMOM accelerates convergence on the training set. More importantly, it also leads to smaller loss the test set, which suggests generalization benefit coming from using the unlabeled set.
Figure 10: Gradient norm, train loss, and test loss. We set the parameter a = 0.1, and the stepsizes were optimized using grid-search for best training loss.
7 Discussion
Fine Tuning. Fine Tuning uses the helper gradients first and then uses the gradients of f: in this sense, fine-tuning has the advantage that can be used for different functions f without having to go through the first phase each time. AuxMOM seems beat it (especially for small values of the similarity 8); however, it does not enjoy the same advantage. Can we reconcile both worlds?
Better measures of similarity? Quantifying similarity between functions of the previous stochastic form is an open problem in Machine Learning that touches many domains such as Federated learning, transfer learning, curriculum learning, and continual learning. Knowing what measure is most appropriate for each case is an interesting problem. In this work, we don't pretend to solve the latter problem.
Higher order strategics. We believe our work can be "casily" extended to higher order strategics by using proxies of f h based on higher order derivatives. We expect that, in general, if we use a given Taylor approximation, we will need to make assumptions about its error. For example, if use 2nd order Taylor
14

---

Published in Transactions on Machine Learning Research (02/2024)
approximation, expect we will need to bound the difference of the third derivatives of and h; this will be similar to the analysis of the Newton algorithm with cubic regularizationNNsstlr Dealing with the noise of the snapshot. In this work, we proposed to deal with the noise of the snapshot gradient of f - using momentum, other approaches such as using batch sizes of varying sizes with training (typically a batch size that increases as convergence near) are possible, such an approach was used SCSG et al.p.
& Polyak 2006).
Positively correlated noise. We showed in this work that we might benefit we could sample gradients of h that positively correlated with gradients of but did not mention how this can be done. This is interesting question that we intend to follow in the future.
8 Conclusion
We studied the general problem of optimizing target function with access to set of potentially decentralized helpers. Our framework is broad enough to recover many machine learning and optimization settings (ignoring the applicability of the similarity assumptions). While there are different ways of solving this problem in general, we proposed two variants AuxMOM and AuxMVR that we showed improve on known optimal convergence rates. We also showed how we could go beyond the bias correction that we have proposed; this can be potentially accomplished by using higher-order approximations of the difference between target and helper functions. Furthermore, we only considered the hessian similarity assumption in this work, but we think it is possible to other similarity measures depending the solved problem; finding such measures is outside of the scope of this work, but it might be good future direction.
9 Acknowledgements
The authors would like to express their gratitude to Martin Jaggi and the MLO team at EPFL for their valuable discussions. Additionally, we appreciate the helpful feedback provided by the TMLR reviewers.
15

---

Published in Transactions on Machine Learning Research (02/2024)
References
Ahmad Ajalloeian and Sebastian U, Stich. On the convergence of sgd with biased gradients. arXiv:2008.0005 [e], 2020.
Peste Alexandra, Iofinova. Eugenia, Vladu Adrian, and Alistarh Dan. Ac/de: Alternating com- pressel/decompresedd training of deep neural networks. arXiv:2106.14 12379 [cs.LG], 2019.
Mohtashami Amirkeivan, Jaggi Martin, and U. Stich Sebastian. Masked training of neural networks with partial gradients. arXiv:2106. 08895 fcs. 2021.
Navon Aviv, Achiluve Idan, Maron Haggai, Chechik Gal, and Fetay Ethan. Auxiliary learning by implicit differentiation. TCLR 2021. URL https://arxiv..om org/ wrg/pdf////poooooo/ooopopper 2007 .2w.9.2663.00 pdff
Olivier Bachem, Mario Lucic, and Krause Andreas. Practical coreset constructions for machine learning. arXiv:1703. 103.00677 [stat.ML/https. // arziv. org/ ab/////s///// 1703. 06476 2017.
Shi Baifeng, Hoffman Judy, Saenko Kate, Darrell Trevor, and Xu Huijuan. Auxiliary task reweighting for minimum-data learning. 34th Conference on Newral Information Processing Systems (NeurIPS 2020), Vancouver, Canada. URL
08244.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Xiviv preprint arXiv:2005.14 14 165, 2020.
Chih- Chih-Chung Chang and Jeih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions Intelligent Systems and Technology, 2:27:1 27:27, 2011. Software available at http://www. csie. edu. wwt.tt//winnnibsstttteee
Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-supervised learning (chapelle, o. al., eds.; 2b06)[book reviews). IEEE Transactions on Neural Networks, 90(3))542-5444 2009.
Mahdi Chayti, Sai Praneeth Karimireddy, Sebastian U. Stich, Nicolas Flammarion, and Martin Jaggi. Linear speedup in personalized collaborative learning. arXiv:2111.0596 [cs.LG], 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive Icarning of visual representations. In International conference machine learning, pp. 1597-1607. PMLR, 2020.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd. arXiv:1905.10011 LCs, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet in 1 hour. arxiv preprint Xrve: 77070006777 02677, 2017.
Zhang Jingzhao, Tianxing He, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelerates training: A thcoretical justification for adaptivity. arXiv:1905.1188 [math. URL
11881
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. NewrIPS, 2013.
Sai Praneeth Karimireddy, Martin Jaggi, Sakyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda. Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. ar arXiv:2008.03606 LCJ, 2020a.
Sai Pranccth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In 37th International Conference Machine Learning (TCMT), 2020b.
16

---

Published in Transactions on Machine Learning Research (02/2024)
Sai Pranceth Reddy Karimireddy, Sebastian Stich, and Martin Jaggi. Adaptive balancing of gradient and update computation times using global geometry and approximate subproblems. In International Conference on Artificial Intelligence and Statistics, pp. 1204 1213. PMLR, 2018.
J. Kiefer and Wolfowitz. Stochastic estimation the maximum of a regression function. Ann. Math. Statisl. Volume 23, Number 3, 462-466, 1952.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ar preprinl arXiv:1412.66 69800 2014.
Jakub Konecny, H. Brendan McMahan, Daniel Ramage, and Peter Richtarik. Federated optimization. : Distributed machine learning for on-device intelligence. arriv.org/ubel /a/////s/////// 02527, 2016.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yanii httt::tt/yyamm.eeaa. lecun com/exdb/nnist/
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553)) ::36 444, 2015.
Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. ICML, 2013.
Lei Lihua, Ju Cheng, Chen Jianbo, and 1. Jordan Michael. Non-convex simite-sum optimization via scsg methods. Xrxi 09156 (math. OCj. URL
09156
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-effciennt learning of deep networks from decentralized data. In Proceedings of AISTATS, pp. 1278-1282, 2017a.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication- efficient learning of deep networks from decentralized data. In Proceedings of AISTATS, pp. 1273 1282, 2017b.
M. Mohri, G. Sivek, and A. T. Suresh. Agnostic foderated learning. arXiv preprint arXiv:1902.0011 2019.
Yurii Nesterov and B.T. Polyak. Cubic regularization of newton method and its global performance. https: // link. sprönger. com/ wwwtenttodpptto pdf 10. 1007/ 110107-006-0706--2000000 pdf 2006.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 2613 2621. JMLR. org, 2017.
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. arXin:1603.06 06 fmath. OCiththshhtsp::: // aræiv. org/ www.aaass... 06160 2016.
Herbert Robbins and Sutton Monro. A stochastic approximation method the annals of mathematical statistics. Vol. 22, No. 3. pp. 400-407, 1951a.
Herbert Robbins and Sutton Monro. stochastic approximation method. The annals of mathematical stotislics, pp. 400-400 1951b.
Sebastian Ruder. An overview of multi-lask learning in deep neural networks. arXiv preprind orXiu:100600500 2017.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. Neural networks, 61:85-117, 2015.
Robin M Schmidt, Frank Schneider, and Philipp Hennig. Desconding through a crowded valley-benchmarking deep learning optimizers. arXiv preprint arXiv:2007.015/7, 2020.
Ohad Shamir, Nathan Srebro, and Tong Zhang. Commuicatiio efficient distributed optimization using an approximate newton-type method. arXiu: 7853 fes. 2013.
17

---

Published in Transactions on Machine Learning Research (02/2024)
Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang. meprop: Sparsified back propagation for accelerated deep learning with reduced overfitting. In International Conference on Machine Learning, pp- 3299 3308. PMLR, 2017.
Lin Xingyu, Singh Baweja Harjatin, Kantor George, and Held David. Adaptive auxiliary task weighting for reinforcement learning. 33rd Conference on Nearul Information Processing Systems (NeurIPS 2019), Vancouver, Canada. URL htttps://openreviev.. net http://wwee..eeeedeoooooooooss
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? arXi preprinl 1rx::14411.1992 2014.
Jiahui Yu and Thomas Huang. Universally slimmable networks and improved training techniques. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1503-1811, 2019.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Technical report, University of Wisconsin- Madison Department of Computer Sciences, 2005.
Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yougchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. A comprehensive survey transfer learning. ar 1xXx::10330647 [stat. MT. https: // arziv. org/ abs/ 1911. 02685 2020.
A
Code
The code for our experiments is available at httpp:///htttuu.ccc/////aaaaaaar
B Basic lemmas
Lemma B.1. Ya, b E c² ||a + bll
< (1+c)|aa13 + (1
Proof. The difference of the two quantities above is exactly ||a Ve bb 2 0.
Lemma B.2. VN E N, Vai.... AN Rd
+1 a.113 < NNEW |a l
Lemma B.3. is common knowledge that if f is L-smooth, .ie. satisfies 3.1 then
Va f(y) - f(x) = vf(x) (y x) + 4 111 x
C Missing proofs
C.1 Naive approach
As a reminder, the naive approach uses one unbiased gradient of f at the beginning of each cycle followed by unbiased gradients of h.
K -
We prove the following theorem: Theorem C.1.
Under Assumptions 3.1
3.2 4.1
Starting from x0 and using a step size 1j we have
T
F
Lo² 1
K
E E|IVf(a'
E
2KT
2KT
KT
For o² ( the average voriance, F B[f(x")] -
18

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm Naive(f. (f. ft)
Require: to,m², T, K for t 1 to T do
Sample 57; compute gy(x"-1,67 ,57
m' (,'=1 .5)
y x' for k: 0 to K 1 do
if k=0 then
d= m
else
Sample ek.k; Compute ( )
d' gh (1 )
end if
v =y - ndj
end for
Update xt = yk
end for
Proof. The proof is based on biased SGD theory. From Ajalloeian & Stich 2020 we have that if we the gradients g(æ) that we are using are such that
E [[g(x)] = V f(x) + b(x)
For Larget function f and gradient bias b(az). Then we have for 1) S t:
(((41))((v()) z " \V) 1600)
Li²
o
In case, by Assumption 4.1 Summing the above inequality from t = 1, A = 0 to = T. = K - and then dividing by KT we get the statement of the theorem.
||b(vt)
(c² + ml| mm[[\(())))) Iaso and of = Ik=0ož 3 + LR5
Lower bound. It is not difficult to prove that cannot do better using the naive strategy. We can for example pick in 1d largel function f(x) = f²²² and an auxiliary function h(x) (xr - -) Both functions are 1-smooth and satisfy hessian similarity with 8 ==0 O, however, Ç is not (necessarily zero), in particular, this shows that hessian similarity (Assumptior3.3) and gradient dissimilarity (Assumption 4.1] are orthoganal. To show the lower bound we can consider the perfect case where we have access to full gradients of f and
The dynamics of the naive approach can be written in the form:
++1 (1 (1- + TT ((Lee0mod((K)
Which implies
t-1
x' = (1 - 1))x"" +6 Σ (11 (0))-))---
Li40mod((K)
1=0
= (1 11 or + (())
This sequence does not converge to matter the choice of 1) < 1.
19

---

Published in Transactions on Machine Learning Research (02/2024)
C.2 Momentum with auxiliary information
C.2.1 Algorithm description
The algorithm that we proposed proceeds cycles, the beginning each cycle we have x'-1 and take K iterations of the form y y nd where yó x' di = gn(vi-1 : + m and m (1 a'mmm 1-1 + "
Then we set x' yk-
Algorithm AuxMOM(f,, h)
Require: To,m², 1), a, T, K
for t to T do
Sample 57-1: compute ( 1-,
1-1 -55-h)
m = (1 a)m' - agg an (x 1,5
y = x
for k: = to K do
Sample e Compute gh (yh cl.k)
d' gn (uki c + m'
yk+1 y nd
end for
Update x' y'k end for
We will introduce di Vh(vk-1) + m' and we note that Eld 1 = di and Eild; - d S of We will be using this fact and sometimes we will condition on yi implicitly to replace di by d.
Note. Algorithm is another version of AuxMOM that works very well in practice and scems more robust to the choice of the step size than Algorithu 3 The main difference with Algorithm 3 is that the momentum is applied on f only. For this Algorithm, we could not prove any benefit from the similarity 8.
Algorithm AuxMOM(f.h) VO
Require: To 7), a, T, for 1 to T do Sample E); compute g (x -5. - m' (11 (1-a)m²-1 + ags (x 11 1 11-1) yh ==1
for k: == 0 to K - do
Sample sli:; Compute gn ( et ) ) (1
cli
d' gg + - gn (w--11 Sh m
yk+1 y nd
end for
Update x' = yk
end for
C.2.2 Convergence rate
We prove the following thcorem that gives the convergence rate of this algorithm in the non-convex case.
20

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem C.2. Under assumptions A3.1 1 3.9.
For 368Kn and min 1445
128LBKT07
This choice gives the rale
K-
L3Fo3
+ (I+ 1925K)
0f
B(IVf(yb)
s 2
SKT
KT
6K
where F- F + 85 and B f ( vf(x") + vh(x |B3].
oi o3 ISK
+
288K of Fu = -(xx)) - f and E = E[[lm"
Furthermore, if we use a batch-size times bigger for computing an estimate m of ((x))) Vh(xz)) then by laking a = max ( 365Kn) and replacing F. by fo the expression of n, we get
F
17 = min(
L' 1925K'
14ALBK2TO?
we get the following
T
LBF
(L+ 19
80 f-h
o
/ s 24V
8KT
KT
T
6K
k=
C.2.3 Bias in helpers updates and Notation
Lemma C.3. Under the 8- 6-Bounded Hessian Dissimilarily assumplion, have Va, y E Rd ||Vh(y) Vh(x)) (z)) ff())] < 52 1y x=12
Proof. A simple application of the B-Bundded Hessian Dissimilarity assumption.
Notation We will use the following notations e' = m (f(=(-1) Vh(x'-1) to denote the momentum
error and E = B[lle*|8 [[ to denote its expected squared norm. A Bllly x²' will denote the progress made up to the k-th round of the t-th cycle, and for the progress in a whole cycle we will use A' E Ei||='
1 [|3]. We also denote d' d' gn (3k <h Vh(yt- = Vh m'm.
C.2.4 Change during each cycle
Variance of di We would like di to be vf(v(_)). ,), but it is not. In the next lemma, we control the error resulting from these two quantitics being different.
Lemma C.4. Under assumption
3.3 we have the following inequality
d vs(v 25 At 2
Proof. We have
-((y(() = Vh(v(-1) - v 1) + m
h(v)-1) V vs(v(_1) + v m -oni-Vf(at vf(w-=1) Vh(w"-1) v/(==)))
h(()-1)) vs(vi=1) V/(xi-))
Using Lemma B.1
with
we get :
E El f
& 2E[l Vf vf(((-)) + vf(x'-1)131 22I||e'113
< 28 | x - 21E
20 A 2E
21

---

Published in Transactions on Machine Learning Research (02/2024)
Distance moved in each step.
Lemma C.5. for 1j S 5 we have:
1 4 (1+
K
Proof.
1 Elll yk x² 1 1
Ellbd
nd 2
[ 1
n x +1 1
- (1 + 2K
A + (2K + 1) + ,
(1 + 2K
A + 3K
= 3
$ (1 + 2K
A + 6k7 1401:-07777000--7700000----1-11-
< (1 + 2K
| + 6K.) + 7
2E
= (1 + 2K
+ 128 F² + 1/3 1700
The condition 7 S 56K ensures 125²Ky² < 2K which finishes the proof.
Progress in one step.
Lemma C.6. For n I min 1926K ), under assumptions A3.1 and 3.S.
the following incquality is true:
2 B(s()() 5(1
2 2 kk A1l [(((v(_1) 5(1
2
(k- [/-1]]
K
L -BLIIS + 2n + 1 + 80)
Proof. The L-smoothness of guarantees
Lnd²
f(gh) - S- d +
||
2
By taking expectation conditional to the knowledge of أ we have:
Lid Blf(v() f(yi - d)
Ln²
of
Using the identity -2ab (a - -b)2 a² b², we have
Lnj
Ln²
Elf(yi) - ()) E 1I Elll - vf
E
d
12
o
2
2
Using 1) S get rid of the last term in the above inequality.
22

---

Published in Transactions on Machine Learning Research (02/2024)
Using Lemma C.4
we get
Lnj²
B[f(vi) f(b--i) -
I|dd v
+
o
2
7 4 +2 + Lr²²
s 2
2
2
Ln²
= Sn + + _ |||| +
2 Oh-
Now we multiply Lemma by 8(1 + ) Note that 1 < (1+ ) 88.
8(1 +
2 K A s 6(1+ +
2
K-k >>>
1 } ) 1-1+
12Kn E² + 6K 2
B B
K
K
K
2
+ 8(1 +
K
s 5(1 +
2
8
(1+ +
2)
2
K />>>A// 1
K
K
K
48K 61 "
(1)k-11)) 11 + 8812oR
s 6(1 + 2
(K
A
5
A
K
K
48K V
f(y 112)
+ o%
Adding the last two inequalities, we get: :
2 2 K Elf(y()) 6(1 +
) sEf((( 5(1 +
2 K
)
8
+62 K
)
+ (n + 96K ) E
+ ( 2-2 7 48 15l
2
+ (L/2 + 86)
For n S 1926 have d2n & < 0, n 96K < 2n and 1 + 48Kōnp < - which gives the lemma.
Distance moved in a cycle.
Lemma C.7. For 17 5k8 and under assumptions A 3.1 and A 43.3 with G ΣkS E V
have:
< 36K A s': B[1 x² 1
+ of
Proof. We use the fact x² = yk, which means A A The recurrence established in Lemma C.5
implics :
K
A
Σ (1 +
1 - (12K E²
1
+
K
km1
< 36K 17 E + 28 2/²
Σ | + +3K700
K
36K +
+ 3K
Where we used the fact that (1 + b R 3.
Momentum variance. Here we will bound the quantity E
23

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma C.8. Under assumptions 3.1 3.2
and for a 2 12K6n we have
E "62² GO + a² o +
E S (1
oh
2
24K
Proof.
E² = E |' VS(x"' Vh(a'-1)111
= E [1(1 - a)(m² V/(x Vhia"' + + gn(==n V5(xx-1) + Vhi(o' Vh((x"'1))13 1)
< (1 - a) 2 [[|m* 1- + (VS(x' 3) Vh((x' - (V/(x(-11) V/(xx' 1)13 + +a²07-h
S (1 a) a1+ + (1 - aa) 2 - Vh(x' -V + Vhh
+ 7
28 1-1 + d² d²
$ (1 - 8)
Where we used the L-smoothness of f to get the last incquality. We have also used the incqualities (1 a1=))(11+ + a/2) S (1 a) and (1 - a) (1 + 2/a) s 2/a true for all E (0,
We can now use Lemma C.7 to have
7282 R2
F 368 K2 G²-1 + + f- +
6k
E' $ (1 a
o
a
By taking 2 12 we ensure
2: So
365 K2
Ex S (1
E +
Gt-1 +a²0 oo 24K" t
Progress in one round.
Lemma C.9. Under the same assumptions as in LemmdC.0 we have :
7 G G
F
Fr
A' + 2n + 1
L + 86)7"07
4 K
K
Where F = (=J(('')] S*.
Proof. We use the inequality established in Lemma C.6
which can be rearranged in the following way
7
E El E + 8(1 +
2
K- (k-(k-1) D A (B(f(gA) + 5(1 + K
2 K A1)
K
+ +2m + 1 + 86)
We sum this inequality from k to K, this will give:
To Kn K"C Gt < E(((() + 5(1+ 2 " (B(s(rk) ( +84k)) 2nKE T + +1 + 80)
We note that y = -11 and y  which means A = 0 and A A'. So we have
7 G
Ft-1- Ft
L A + 2n + 1 88)
K
24

---

Published in Transactions on Machine Learning Research (02/2024)
Let's derive now the convergence rate.
We have:
{ G - _- + E' (1-
+ F + +1 + +86)n
K
365 365"K"1 GO
0 21k //
a
We will add to both sides of the first inequality the quantity 5
So
G
+ 41 _ -
FF
+ 2n + +1 + +88)n o + 477 (11 a bd +
L
366 3662K2'
G Gt-1
---1+ +d'o
a
07
4
K
2
24K
Which gives for 2 368KT
y G
! G < <0-11_ 46 + 4nao7 --h + 1 + 86) 88) + oh
(7)
4
8
2
6K
For a potential 0' Summing the inequality over t, gives
+ 2n S et
+ a
E².
K
K
L
2 of
G
Auo jujj-h + [ 80) 6k
87
T
F
4
E. +407 h + :12 _ + 8o
of 6K
nKT
al
Now laking a= 3) S 1, we
gel
1
Σ
T
G
<
FO
1
E + 1445Kn0 f- + +1 + 86) + of
L
ST
KKT
8OKNT
6K
1=1
F
1448K107 + +12 +80)n0 + oi
nKT
6k
F
144L3Kno} + of
nKT
6K
For F = F0_ +
E2 35
and
B
b
8
o
o7
ISK
oy
) 288K
+25k
Taking into account all the conditions on that were necossary, we can take
F
n = min(
1912KK
14ALBK2T
This choice gives us the rate
T
L3Fo3 T
(L + 1928K) F
G < 241
ST
KT
6K
t=1
Dealing with the term E If we use batch-size S times bigger for generating m than the other batch-sizes, then we have E <
oi In particular, for = E oi T
g..
Now by taking max ( 368K)))) ensure ar
Eo
o then
25

---

Published in Transactions on Machine Learning Research (02/2024)
1
F
4
+1 _ + 80))
of
G
+4003-h +
87
nKT
aT
6K
FO
403-h
+ 144Kkn0 n + ( + 8o) + of
+ 4E +
nKT
T
2
6K
F
808
+ ( 88) + o
L
144K8n07
ntT
6k
F
8
of
14AL3Kn0}
+
nKT
T
6K
Taking
F
7 = min
L' 1925K''
144LBK2TO?
we gel the following:
T G
LBF
(T + 1925K)
807
of
S
24
8T
T
KT
T
6K
t=1
C.3
MVR with auxiliary information
C.3.1
Algorithm description
The algorithm that we proposed proceeds in cycles, at the beginning of each cycle we have states 2-2 and
-111, To update these states, we take K + 1 iterations of the form y = y ndd where vd ===1, d
gn (1 ( and m (1 - a)mamm f-1 +agg-n(x' (x +1- g
-n nx (x--2, 2, gو
Then we set x' yxk-
Algorithm AFXMVR(F,N)
Require: mo 7, a, T,
x-1 = Eg
for /= to T do
Sample 5/-h
ct-1
g g 91 (1- 2 (/-11)
gf 9 (x' (59-h)
m' l = (1 - a) a)m 1-1 + ag f- + (1-a) a - -ffreh) Supdate momentum
2 = x '-1
for 1: to K do
Sample c Compute gn (v) Sh ct.k)
d. = gn (vi. cl.b) + m'
y y nd
end for
Update a y' end for
We will the same notations as section C.2
C.3.2 Convergence of MVR with auxiliary information
We prove the following thcorem that gives the convergence rate of this algorithm in the non-convex case.
26

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem C.10. Under assumptions 43.1
3.2 4.5
For m.
such that E S o o for
max 7. 115602k21p² and min (t.
1/3
F KT(L/2+86K)
This choice gives
1926K
K
184326-To
us the rate
8F s
2/3
(L/2+ 8
(L + 1926K) F
80 f-A
E [
s 40
+21
SKT
T
KT
KT
T
48K
1=1
Where F = f(x²) - fr and E E m
(Vf(x²))
vh(a>))11.
C.3.3 Proof
Given that the form of d' is the same as in AuxMOM (Algorithm 3 the same Lemmas still hold, except for Lemma C.S which changes to the following Lemma.
Momentum variance of AUXMVR. Here we will bound the quantity E
Lemma C.11. Under assumptions 4.5 we have
S (1 a)E + 282 1- + 2a
Combining this inequality with Lemma
C.7 we get for 1l I 5K8 and a 2 oppp
Ex s (1
5)
E 36K 62 +2 of o 6K82
Proof. First, notice that
e' m' V[(x'=1) Vh(x--1)
= (1 a)m 1- + / a 158 -
(1 a) (9/-n (/ 9/ (x .(/11))
( vf(x'-1) Vh(x'-1)
(1 a)e' - { vf(x=-1) Vh(x'-1))
+ (1 c((g)~((''1 + Vh(a''1) - g)-n - 1
Notice that el-1 is independent of the rest of the formulae which is itself centered (has a mean equal to zero),
SO
Ex s - (1- + 2220 2
Now for 17 S 5K8 we can use Lemma
C.7 and we get
20 + 28 Ex (1-1) +
18K G' 3KK7
< (1-a- a
74K (1-a+744228p)
+ 22a20 36K 28 -t 6
It is easy to verify that for a 144K283,,, we have 74 172 - a/2 which finishes the proof.
Let's now derive the convergence rate of AUXMVR.
We have
{ L 1 2n + ( + 88)m
E $1 - 36 - 6K8
We will add to both sides of the first incquality the quantity 4
So
4n
pt-1
Fd.
L + +88)
4n a = +36K "3"2""=1-22???
Gt
Ft_
2n
o
4
K
a
27

---

Published in Transactions on Machine Learning Research (02/2024)
Let's define the potential Φ'
Fr K
+ t
Ft K = 2n) I
Then
G v tf क
L
+ 86)17
144K 2012" G + 8ano +
24
4
2
0h
for a 2 1152K2 we have
14
v n/88 which means
I + 86)n + 8ano 24K5221 " G ! G Φ Φ' + +
0h
4
8
Summing the last incquality over t gives:
+ 8ao f-h + +12 88 24K83p2
L.
G
S
o
8T
nT
F
4 E + 8ao + +12 L + 8 + at
24K02n2
nT
+
hh
o- T 80:
If we use batch T times larger the beginning, we can ensure E <
T
F
4
24K52m +8007 + 1 + 1
8T
G
KT
+
TT
a hh
Now taking max + 11528 K2
get
FO
40
80 + 22 + ( + 88))00
of
Σ
G
+
8T
KT
T
T
48K'
Taking into account all the conditions on n that were necessary, take
77 min (
1
FD
1/3
F
1928K' ' K
1844228TO?
KT(L/2+88K)
This choice gives us the rate:
T
8 o
2/3
(L/2 + 80)
+ (L+ 1925K)
80
G
<
40
+2
ST
T
KT
KT
T
48K
C.4 Generalization to multiple decentralized helpers.
We consider now the case where we have N helpers: hi...., hN. This case can be easily solved by merging N all the helpers into one helper h Di=1 h; for example (it is casy to that if each h; is 8HD from f that their average h would be N Σ 8,HBHD from f. However, this is not possible if the helpers are docentralized (are not in the same place and cannot be made to be for privacy reasons for example). For this reason, we consider a Federated version our optimization problem in the presence of auxiliary decentralized information.
In this case, consider that all functions h; such that
Vz. E f(x) (²h, 58.
We will also need an additional assumption on f Assumption C.12. (Weak convexity.) ʃ is 8- weakly convex i.e. - f(x) + 61|2=113 convex.
28

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma C.13. Under Assumption C.12
the following is true
AANA, B1 11...,, Vo 2 8
Σ 1( N
x.)
all
1 N
Σ
34
x012
1 N
((x)) + alla; -=11)
About the need for Assumption C.12 Assumption C.12 becomes strong for small which is good, this should be the easiest case. however, would like point out that only need Assumption C.12 to deal with the averaging that we perform to construct the new state x'. In the case where we sample each time one and only one helper (i.e. 1), we don't need such an assumption. This assumption was made in the context of Federated Learning for example in (Karimireddy et al. 2020a)
C.4.1 Decentralized momentum version
As in C.2.1 we start from x'-1, we sample (randomly) a set St of helpers, we sample { compute ga - ,,f), share it with all of the helpers for h4, St, which each sample Sh (potentially correlated with {)) and then update m then perform K steps of yi,x = -ia- -dd once this finishes y is sent back to which then does x' = Eies' V..k
For each we will denote E = Bllmm V[(x'-1) + Vh,
and E' = Eies E+.
Theorem C.14. Under assumptions and n min( 3,, 1448K' V 128L5KTO3)
3.1
3.2 3.3
(and assumption C.12 ifS 1).
For a 368Kn)
F
This choice gives the rate
T K-1
LBFo?
(L + 1926K)
of
LIV S 241
+
8KST
T
KT
6K
(=1 k=1 SESt
where F- p +
and
4
of of
of ISK
o
Fu [(xx) - f and E E[[lmm
85
of
288K
Vf(=0) + V((=")+)
Farthermore, use batch-size T times bigger for compuling an estimate m of V((x)) Vho,(wo), then by taking max 3, 365Kn) and replacing F by FO in the expression of n, get
F
7 = min( L' 1925K
144L3K2T0?
we get the following
L3F
(L + Fo
80
ΣΣΣ 1E
B[IVS
s $21
8KST
T
KT
6K
Proof. The proof follows the same lines as the proof of in C.2.1
Two changes should be made to the proof: Gt needs be updated to G SK Eies
V || in
both Lemmas C.7 and C.
29

---

Published in Transactions on Machine Learning Research (02/2024)
In fact, in this case x' S Eiesi vi which means using convexity of the squared norm
A v 1
Σ
A (:= E
FIlbi -x 11))
iESt
Σ
1 K
)
iESt
1) 1 ΣΣ < <36K2
R [[IV//())
+ 3K
KS
iESt k +3K
36K3 18K 1/
And in the descent lemma (That modifies Lemma C.9 we will have
Kn 1 [[VV/(( <[(((()))) 5(1 2 2 A (E(J(OL +04ikl)
Vi
K
L
+ kn (
88)n o%
Where Ai,0 = and using Lemma C.13 we have
Fa 8
Σ
(B((())))+ +
EES!
Using the last inequality is easy to get
Kn G < FT-1
+1 - +
F
8A' + +mnEE +
All the rest is the same.
C.4.2
Decentralized MVR version
As in C.3.1 we start from x²-1, we sample (randomly) a set St of helpers, we sample Ej compute " " share it with all of the helpers for h4 E St, which each sample 4 (potentially correlated with {)) and then update mf, then perform K steps of yi,x yia-1 nd once this finishes y is sent back to f which then does x' = 3 Eies: vi
We can prove the following theorem under the same changes in the momentum case.
Theorem C.15. Under assumptions A3.
3.
3.2
3.3
(and assumption C.12 1). For mo- for a = max 11522"K2'p), and
mentum initialization m.! such that E
J
o
1/3
min t 1926K K
1 T84326-T07
po
we get:
(L/L2-880
T
K-1 E E[IV/(((A1)
8F
2/3
(L/2 86)
(L 19
S 40
+ 2/
8KST
T
KT
KT
iESt
807 h
+ k
48K
Where 0 = f(x0) - f and E = mmm (vf(x") - (hr
30


Reviews:
[{"review_id": "qUtTycVfzf", "reviewer": "Reviewer_ZsY4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nThis is a nice paper combining known techniques for a novel special case of optimization problem with an auxiliary objective with similar Hessian. They also motivate the problem well with many instances from ML. Authors provide intuitive algorithms and theoretical results seem plausible (see weaknesses and questions for issues). Experiments are mostly convincing (see weaknesses and questions for concerns). Application wise, the algorithms studied in this paper can potentially improve the efficiency of solving some ML problems. Authors also seem to have put some effort in providing the intuition behind their algorithms and making the proofs parsable (both scan be improved). AFAIK, this optimization angle of general auxiliary objectives was not considered in any prior work.\n\n# Weaknesses\n\n1. Algorithmic of analysis innovation is very limited as most of building blocks are known in very similar setting (special cases). However, many times authors fail to refer prior work when first introducing these concepts. For example, it not clear if the bias reduction trick can be called a contribution since it has appeared in many prior work especially in incremental gradient methods and FL. It would be better if this trick is attributed to prior work, otherwise there should be proper justification for its novelty. In another example, history of hessian similarity was never discussed. It is a widely studied assumption in FL and distributed optimization. These could be misleading to the readers.\n\n2. First few sections of the paper are very confusing and is written to imply that the problem that they study is very general. Only after reading the 5th page (!) we get to the actual problem under consideration which requires smoothness and Hessian similarity. If the objective of the paper was to study auxiliary information in general there I would have expected more justification given for their assumptions and verifying if they are satisfied in real world problem. Yes, at the last sections authors note that their assumptions may not be satisfied in real-world problems, but similar candor could be used in initial sections too.\n\n3. Various assumptions are rather strong, especially the $\\delta$-Hessian similarity and weak convexity with precisely the $\\delta$ factor for decentralized setting.\n\n4. There are a few contradictory or imprecise statements in the paper. \n  a. For example\n    i. ”we don’t explicitly make assumptions on how the target function f is related to the auxiliary side information h (potentially a set of functions) like in Distributed optimization or Federated learning where we assume f is the average of the side-information h.”\n    ii.  “Hence we need to assume some similarity between f and h. In our case, we propose to use the hessian similarity (defined in assumption 3.3)”\n  It might be better to just say assumptions are weaker than some FL assumptions. \n  c. In another example, it is not clear how alternating between K-1 steps of h update and 1 step of f update is FedAvg. Usually FedAvg, doesn’t do any f update.\n  d. “this shows that hessian similarity (Assumption3.3) and gradient dissimilarity (Assumption4.1) are orthogonal.“ This statement is hand-wavy.\n  e. Uses the term “round” without defining it. I understand it is probably coming from FL literature.\n\n5. I can see that authors have made some effort in making the proofs parsable. However there are many typos/confusion in the algorithms and proofs. Due to this it is not easy to check the veracity of the statements. Please proof read and revise them. Considering this is a journal venue with rolling submissions, it would have been better if author had proof read the paper more carefully. I will list my concerns below\n\n## Theorem 4.2 and naive algo:\n\nAfter reading the theorem further it is clear that lower bound holds even if hessian similarity is perfect. A better way to write the theorem 4.2 would be to say that under perfect hessian similarity assumption the lower bound could be arbitrarily bad depending on the gradient bias. Then say the the lower bound depends on the gradient bias. Otherwise, it is confusing to have different assumptions for naive and proposed algorithms.\n\n## Theorem 4.3 and AuxMom:\n\n1. Proof of Lemma C.8: seem to miss the term $(6 \\delta^2/a) K \\eta^2 \\sigma_h^2$ (corresponding to last term in Lemma C.7). This seems potentially fixable, but this means rest of the proof needs reworking before verification.\n2. If E0 can be removed why isn’t main theorem written with E0 removed? \n3. Final step of the theorem proof (where we eliminate E^0) is not obvious. Please elaborate the steps. It is not clear how $a=max(1/T, 32 K \\eta \\delta)$ is helpful.\n4. Even after taking care of E0, why does the upper bound have a dependence on $1/\\delta$? Shouldn’t the problem get easier as $\\delta$ is small? This term seems to be ignored in most of analysis and follow-up interpretation.\n\n### Minor errors\n1. Algorithm 3: $\\xi^{t-1}$ instead of $\\xi^{t}$\n2. Proof of  Lemma C.7: typo $K(K+1)$ instead of $K^2$\n3. Proof of Lemma C.8: typo it should be 36 instead of 32\n4. Proof of Lemma C.9:  typo missing square in the LHS\n\n## Theorem 4.5 and AuxMVR:\n\nAuxMVT seems to make some non-intuitive choices to differ from AuxMom and STORM (Originally introduced MVR). \n\n1. Why is momentum update done at end of the round whereas in AuxMom it is done at the beginning? It would be good to provide justification for this choice. Better is it possible to unify the algorithm to make it consistent?\n\n2. Why is $m^{t-1}$ directly not used like in STORM instead of $(1-a)m^{t-1} + a g_prev^{f-h}$? Can we simplify Lemma C.11 (eliminate the last variance term) using the simpler update? If yes, I highly recommend authors doing so.\n\n3. AuxMVR also departs from Algorithm 1 pseudo code, since $m^{t-1}$ is used instead of $m^t$.\n\n### Minor errors\n1. There seems to be some confusion on whether $\\xi^{t-1}$, $\\xi^{t-2}$, or $\\xi^t$ is being used at various places. Algorithm 3 uses $x^{t-1}$ and $\\xi_{f-g}$ but analysis uses $x^{t-2}$, $\\xi_{f}$ and $\\xi_{g}$.\n2. Proof of C.11: Missing overhead bar over $d^t_k$ in the final inequality LHS\n3. Proof of C.12: $\\pm$ is not a standard notation. \n4. Proof of C.13: References C.5 instead of C.12.\n5. Proof of C.16: Typo in last inequality $\\Delta^{t}$\n6. Proof of Theorem 4.5: What is $\\tilde{\\delta}$? Upper bound on $E^0$ is using wrong variance.\n\n## Experiments:\n1. It would be great if the authors can provide the code for the experiments.\n2. Fig 2: Why does speed of fine tuning stage of FT depend on the delta when $f(x) = x^2/2$ always? This is counter intuitive.\n3. MNIST: From the description it is not clear how many samples are used in f and h. Number of samples in f and h is important in the trade-off between using f and h here.\n4. Real datasets: \n  a. It would be nicer if the authors compared AuxMVR with AuxMom in the experiments.\n  b. Crucially authors do not compare against a case when the models are purely trained on f. This will characterize the gain and speed or generalization gain of using h.\n  b. What is the batchsize used for these experiments? It would be good to do run some ablation on batchsize.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Paper studies minimization of a function f whose stochastic gradients are expensive or unreliable to compute, while at the same time we have access to an auxiliary function h whose gradients are easier or more reliable to compute. Crucially, authors assume that f and h satisfy a Hessian similarity property, which is known in Federated Learnig(FL)/Decentralized Optimization literature.\n\nAuthors want to study algorithms which alternate between 1 step and K-1 steps of gradient descent steps using f and h respectively. If h is easier to compute average iteration speed could be faster. However, they show that this naive method fails under their assumption. To fix this they employ a bias correction term in the updates using the h. Further since they assume access to only stochastic gradients, bias correction is done by estimating the bias using momentum method (AuxMom). They also study a momentum-based variance reduction (known technique) like algorithm (AuxMVR) which requires additional assumption of per sample Hessian similarity. These are algorithms are shown to converge, and their converge rate is better than purely optimizing over f in some regimes. Finally, authors also provide an algorithm and results for the case with decentralized auxiliary loss for handling problems like FL under additional very strict assumption.\n\nThen authors provide some motivating problems from machine learning as transfer learning, learning from coreset, pre-training, and semi-supervised learning. Some of these example seemed a bit far fetched. Authors also note when solving a linear/logistical regression with noisy labels, their setting arises with perfectly matching Hessians. Finally, the paper provides some experimental results to verify the the practical gains of their algorithm on synthetic problems, learning from noisy data, and transfer learning. Authors note that they leave any in-depth study characterization of useful objective similarity in real applications to future work. Discussion section is fair and it raises some good points. However, when reading paper initially it wasn’t clear it was tackling problems with auxiliary losses with similar enough Hessians.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am hoping that the authors can address the following issues. Please see the weaknesses above for details and note that some sub-issues are marked as minor.\n1. Address the issues with the theoretical results and algorithm\n2. Address any potential over-claiming and cite relevant work at appropriate places\n3. Address questions about experiments\n4. Proof reading the mathematical portions and fixing imprecise/contradictory statements\n\nBased on 1 and 3 I am happy to change my answer to “claims and evidence” question.", "broader_impact_concerns": "None as this is mostly a theoretical work", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "E7sMWG7BAa", "reviewer": "Reviewer_FjHB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Below are the strengths and weaknesses I have found in the paper:\n\n* Strengths:\n  * The idea of optimizing a function $f$ via directly handling auxiliary functions $h$ is an essential problem in federated learning, data subset selection techniques (e.g., coresets), etc.\n  * Careful analysis of the results and the idea of Hessian similarity is intriguing.\n  * Variety of applications of this problem, considering this work to be the first of its line focusing on such optimization problem.\n\n\n* Weaknesses:\n   * While the paper has strong implications, the writing is done poorly. At the simplest:\n      -  Use commas.\n      -  After a dot, start with capital letters.\n      - When using abbreviations, state them beforehand, what do they stand for?\n      - There are redundant words such as \"in in\" (see page 7).\n   * When using specific data, either state it is synthetic or simply cite it. For example, the \"mushrooms\" dataset -- where did you get this data? Was it from the UCI repository? If so, did you apply any preprocessing?\n   * What does the shaded region in the graph stand for? Is it standard deviation while the lines represent the mean?\n   * I believe the experimental section is lacking an experiment in the field of subset selection (see the section below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper dives into optimizing a function $f$ via optimizing auxiliary side functions $h$ whose gradients are either more available or cheaper to compute. Such an idea is very interesting and has beneficial applications.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "First of all, please make sure to address the weaknesses raised in the previous sections. As for the additional experiment:\nIn the field of subset selection, the fact that a subset is being sampled with provable guarantees (for example see [1]), implies that the trained model is different from the same model if it was trained on the entire data. An open question in such a field is whether one can train a model on subsets in some fashion and yet retrieve a model very close (inference-related) to a model being trained on the entire data. For example, training a model on $5\\%$ of the data is very beneficial from a computational point of view, however, all subset selection techniques result in a major drop in accuracy when using such a ratio. My question here is as follows: Can you make an experiment in such a setting showing that using your technique, subset selection technique will obtain less drop in accuracy, thus making your paper an essential tool in the field of subset selection?\n\n\n\n    [1] Tukan, M., Zhou, S., Maalouf, A., Rus, D., Braverman, V. &amp; Feldman, D.. (2023). Provable Data Subset Selection For Efficient Neural Networks Training. <i>Proceedings of the 40th International Conference on Machine Learning</i>, in <i>Proceedings of Machine Learning Research</i> 202:34533-34555 Available from https://proceedings.mlr.press/v202/tukan23a.html.", "broader_impact_concerns": "I have no concerns regarding the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GugZkXJYwV", "reviewer": "Reviewer_UJ5V", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "=======**Strength:**=======\n\nS1. This paper extends variance reduction to a more general form, enabling almost plug-and-play application for various settings in machine learning.\n\nS2. Theoretical results illustrate the inefficiency of 'naive approach,' which motivates well the proposed algorithms. A detailed discussion on the choice of $K$ is also provided.\n\nS3. The alignment between theoretical findings and experimental results support well effectiveness of the proposed research.\n\n=======**Weakness:**=======\n\nW1. While the paper builds the gradient estimate for $f(x)$ based on SVRG-type estimates, it does not provide a justification for choosing SVRG over SARAH-type gradient estimators, as other alternatives exist [1, 2, 3]. \n\nW2. This paper develops two approaches, AuxMom and AuxMVR, but it lacks clarification regarding when to opt for AuxMom over AuxMVR or vice versa within the given context. \n\nW3. The numerical results presented in the paper appear to be somewhat simple in supporting of the claimed applicability across a broad range of machine learning tasks. This paper can benefit from a more diverse set of experiments.\n\n\n======= References =======\n\n[1] LM. Nguyen, J. Liu, K. Scheinberg, and M. Takáč. \"SARAH: A novel method for machine learning problems using stochastic recursive gradient.\" In International conference on machine learning, pp. 2613-2621. PMLR, 2017.\n\n[2] B. Li, M. Ma, and G. B. Giannakis. \"On the convergence of SARAH and beyond.\" In International Conference on Artificial Intelligence and Statistics, pp. 223-233. PMLR, 2020.\n\n[3] Z. L, H. Bao, X. Zhang, and P. Richtárik. \"PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization.\" In International conference on machine learning, pp. 6286-6295. PMLR, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies minimizing f(x) aided with an auxiliary function h(x) that correlates with f(x) but can be cheaper to obtain. Building on a two-loop meta algorithm extended from SVRG, the proposed approaches smartly correct the bias induced with h(x) using either momentum of momentum based 'variance reduction'. Theoretical results suggest the possible benefits of proposed approaches, and numerical results further support the theories.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Besides the weakness above, this paper can also benefit from an improved presentation. Some of typos are listed below. \n\n- Grammar error at one line above sec. 4.2, 'Hence approaches that try to reduce it like [cited work]'. \n\n- Missing '.' in the discussion of region II in AuxMom.\n\n- Second sentence in Sec. 3, --> We will consider mainly two approaches. The first one ....", "broader_impact_concerns": "NA.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a nice conceptual contribution, underpinned by sound theoretical analysis, albeit not particularly novel. The experiments do a good of providing some partial evidence in favor of the proposed methods, but the full practical implications and impact are still not clear.
Decision: Accept (poster)