Mixed-Sample SGD: an End-to-end Analysis of Supervised Transfer Learning
Authors: Yuyang Deng
Samory Kpotufe
Venue: NeurIPS 2025 poster ()
Keywords: Transfer learning
domain adaptation
Primary area: theory

Abstract: Theoretical works on supervised transfer learning (STL)---where the learner has access to labeled samples from both source and target distributions---have for the most part focused on statistical aspects of the problem, while efficient optimization has received less attention. 
We consider the problem of designing an SGD procedure 
for STL that alternates sampling between source and target data, while maintaining statistical transfer guarantees without prior knowledge of the quality of the source data. 
A main algorithmic difficulty is in understanding how to design such an adaptive sub-sampling mechanism at each SGD step, to automatically gain from the source when it is informative, or bias towards the target and avoid negative transfer when the source is less informative. 
 
 We show that, such a mixed-sample SGD procedure is feasible for general prediction tasks with convex losses, rooted in tracking an abstract sequence of constrained convex programs that serve to maintain the desired transfer guarantees. 
 We instantiate these results in the concrete setting of linear regression with square loss, and show that the procedure converges, with $1/\sqrt{T}$ rate, to a solution whose statistical performance on the target is adaptive to the a priori unknown quality of the source. Experiments with synthetic and real datasets support the theory.

Mixed-Sample SGD: an End-to-end Analysis of Supervised Transfer Learning
Yuyang Deng Columbia University, Statistics yd28240columbia. edu
Samory Kpotufe Columbia University, Statistics skd22175@clummie. edu
Abstract
Theoretical works on supervised transfer learning (Shre the learner has access to labeled samples from both source and target distributions- for the most part focused on statistical aspects of the problem, while efficient optimiza- tion has received less attention. We consider the problem of designing an SGD procedure for STL that alternates sampling between source and target data, while maintaining statistical transfer guarantees without prior knowledge of the quality of the source data. main algorithmic difficulty is in understanding how design such an adaptive sub-sampling mechanism at each SGD step. to automatically gain from the source when it informative, bias towards the target and avoid negative transfer when the source is less informative.
We show that, such mixed-sampl SGD procedure is feasible for general predic- tion tasks with convex losses, rooted tracking an abstract sequence of constrained convex programs that serve to maintain the desired transfer guarantees. We instan- tiate these results in the concrete setting linear regression with square loss, and show that the procedure converges, with 1/vT rate, to a solution whose statistical performance the target is adaptive to the priori unknown quality of the source. Experiments with synthetic and real datasets support the theory.
1 Introduction
supervised transfer learning (STL., some amount of target data is to complemented by a usually larger amount of related source data towards training predictor. A characteristic problem to be solved whether and how much to bias towards source target data without prior knowledge of the predictive quality of the source data for the target task. Many recent theoretical works STL have yielded important insights into general approaches that may guarantee good target performance. Our main aim in this work is understand the extent to which such insights may be incorporated into actual efficient procedures, in particular, practical stochastic gradient descent (SGD) type procedures, while maintaining good statistical guarantees for transfer.
For background, theoretical approaches for STL often take the form penalized or constrained risk minimization-e.ge e.g. minimizing empirical risk on source subject to low target risk, or vice versa more generally, some type of weighted risk minimization that aims to favor either source or target data, whichever is most beneficial (which is not usually known priori). For example, let P and Q denote source and target distributions respectively, a typical approach, say in linear regression, would be to consider weighted objective of the form (p) + (RQ (0) and solve for choice X so that 8" 8* (X*) has small target risk (f).
Equivalently, of the form ( + (1 (0) [0,1], a= A/(1 AA.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Increasing Source Sample Size
Increasing Transter Hordness
Transter Hardness
6.
-
exceess 19
2.23
2.00
1.75
12
200 430
600
1030
1200
1400
10
25 25 2gg
70
25
30
0.0
0.6 0.0
32
(o10/1
Figure 1: Simulation Results with Gaussian data, illustrating our guarantees that E(OPQ)
min min(E ((())))(())) ÓWTr. denotes the Hypothesis Transfer Learning (HTLL) (Left) we fix P. Q while increas- ing np, or (Middle) and (Right) we fix np, and push P far from Q as controlled by Amax (E.p Ea) and (f The source is least informative, i.c. source ERM 0p is worse than target ERM do. when either np is too small (Left), or as Aeas (Σp²Eg) (Og) large (Middle and Right); we that our method 0pQ automatically adapts either situations and avoids negative transfer. HTT f.m yields results comparahle to our method but it needs expensive cross-validation process to choose a proper bias parameter.
While many positive results have been derived over the years, they typically concern the target risk of the solution, upon good choice of weights (i.e., X*), but do not address the computational aspects of the problem. For instance, choosing X (or any similar bias parameter) by cross-valls voss-validation on the data (target and or source data) can be expensive as it involves many optimization passes over the combined data. Constrained risk minimization approaches, e.g., of the form min ( s.t. Ro (f) S can similarly be expensive in maintaining the constraint (typically via expensive projection steps) through optimization iterations. This leaves open the extent to which such solutions may be achieved efficiently while at the same time maintaining strong statistical guarantees on target risk, adaptively to whether source or target datasets happen to be most informative for the target task.
We initiate the study of these questions in the context prediction tasks with convex losses, and propose a variant of SGD that alternates between sampling the source and target data at a sampling rate that changes according to parameter X that automatically tracks the predictive quality of the source data. That is, for each SGD step 0c+1 0 R(0; Ae). the stochastic gradient estimates the gradient of an averaged empirical risk R(0; X,) = (0) + >e (0) depending on dç- Our main insight into the iterative choices of Xe, evident in the analysis, is to let the stochastic gradient steps effectively track a sequence of convex constrained objectives (or CP for convex program) of the form
min (0) s.t. Ro( Ro((0.)) + slack,
where &0
t-+00 0q = arg ming (f), i.e., fq.1 estimates the Q-ERM 0g in parallel. The adaptive choice of sampling rate de is then chosen to track the sequence of max-min min solutions of the corresponding Lagrangians (A, 0) x R(0, - X (Ro,)) + slack).
On one hand, such mixed-sample SGD solution replaces expensive cross-validation for the choice of bias parameter with the iterative choices of X, and also avoids costly projections onto constraint sets. On the statistical side, we can show that the solution 0p,q of the limiting CP-iee. replacing lq. in ① with its limit t achieve near optimal statistical guarantees for transfer whenever the setting, including loss functions, admit certain uniform concentration guarantees on empirical risk measures. Such statistical transfer guarantees are then shown to be inherited by the maxele SGD solution 0.. which converges in risk to pp.q at typical rate of O(1/vt).
The main difficulty in the analysis is in showing convergence in Rp of θp.Q θp.Q, while the statistical analysis of 0 0pg combines insights from recent works on STL with either constrained or
penalized objectives [2 3 4 5]. For intuition on technical difficulties, we note that recent classical works on SGD for CP's 6 rely heavily on the assumption that constraint sets are bounded, in order to at least approximately maintain constraints at each iteration via cheaper projections onto & balls. We have to proceed differently as we consider general convex settings with potentially unbounded constraint sets (e.g.. linear regression with non-invertible covariance in over- weer-paaaetriied regimes). Our analysis instead relies on carefully tracking how far iterates 0g may deviate from the constraint set, given the deviation of the first iterate and the internal variance of stochastic steps. Furthermore,

---

such control on the deviation of iterates is further complicated by the fact that, unlike in classical results such as (6) we are dealing with an evolving sequence of constraint sets given terms of Qg. which is being computed by a parallel SGD.
For the sake of presentation, will foeus the concrete case of linear regression with square loss in the main paper, while the analysis for general losses, including surrogate losses for classification, given in the appendix where we present the generalization guarantee for general convex losses in terms of Rademacher complexity. In the case of linear regression covered in the main text, the guarantees are immediately interpretable. Statistical guarantees take the form
RQ(0p:4) S RQ((%) + :ninfeqEEr):
where EQ, Ep are respectively, the best rate achievable by using the Q data alone, and the best transfer rate achievable by using the data alone. other words, the saxpless SGD solution is guaranteed to automatically bias towards whichever of the two samples is most predictive.
Many experimental results supporting these claims presented in the main paper.
Further Background. The goal of reweighing source data relative target data is rooted in early works on transfer learning and domain adaptation [see, e.g., 77.77888 9 [0]. A main idea there is to find a weighting of the data that minimizes some notion of discrepancy between weighted source and target data. The actual target risk of the solution remains opaque in much of this line of work, as the theoretical analysis instead focuses on the well rell-posedness of the chosen notion of discrepancy and its estimability from data.
different line of work, mostly focused on covariate-shifi setlings directly weighs source target data with estimated density ratios dQx/ d/x/dPx and results in rates depending on the accuracy of such estimates situations where the density ratio is well-defined [see,e.g., 12).
More closely related, and often considering linear regression settings, the approach of hypothesis transfer aims to bias regression towards the solution from the source data via penalized objectives [see.e.g.. 1 3
2 13.. Recent works of 4 5 consider constrained objectives for STL, mostly in classification settings. These various works are rather statistical in nature they focus understanding generalization properties of the solutions rather than their efficient estimation.
Setup and Preliminaries
Data Distributions. and Q denote source and target distributions over X x V,X C RR y VCC R.
General Setting and Risks. We consider a class of functions fo : X + V parametrized by E @ C Rº, For any distribution μ1, e.g., P or Q, we let R,, = (X) Y). for a loss function f. and we let 8% denote risk minimizer. The excess risk is then defined as (l) = R,,(8) R (6:) The target excess risk (-)-) is of main interest in STL.
2.1 Instantiation for Linear Settings.
As explained in the introduction, focus the case of linear regression with square loss in the main text. In this case assume E, =0, Assumption 1. For both distributions, we also assume that Y E[Y|X] is By ao---yb--uuustie and has zero mean, while is bounded, i.e., supzex ||0||| < oo.
T X for 0% in Rd.
Relating P to Q. We use the notation E,, = X and || = T Eu for E Rd. E E Rdxd
Recent results [4 15 16
18 have highlighted two essential quantities: (i) Amax AEa (Ep Eq).
which characterizes the change in marginals Px - Qx and (ii) EQ(OT) = =1107 02112000 the change in optimal predictors. The first quantity remains relevant even when 0% 0g and upper bounds error ratios ||0 07 / 13
Assumption 2. Ep is full rank, while Σq may not be.
The above assumption on Ep may be somewhat relaxed, but is relevant in the transfer setting since otherwise P may yield no information on Q (in particular, Amax (2p Eq) is ill-defined).
3

---

Empirical Quantities. Throughout we assume that the learner has access to nop labeled samples Sp pnp, and no labeled samples So Qaa. We use Xp and Xº denote the set of feature vectors from Sp and So respectively. We will also let Xp E Reexd xd and X E R denote the corresponding data matrices, and Yy E Ru and yQ E IRee denote the corresponding vectors of labels. We use SrQ to denote the union of Sp and SQ.
Next, for any measure 14, we let S.2, denote the empirical counterpart E.2, defined over X Similarly, we let (0) + ((n (0 x, y:)². The following empirical risk minimizers (ERM's) are important to the analysis even though they are never directly computed:
The
Definition 1. We let 0n. arg arg mingeR" (0) denote the minimum norm ERM.
In partieular, 0p and Og will serve as baselines, i.e., we aim to outperform their risks under Q.
Additional Notation. Given a symmetric matrix M, we use Amiin (2)) to denote its smallest non-zero eigenvalue. We write S 6 to indicate that C for some universal constant C.,
3 Procedure
Key Convex Programs. As explained in the introduction, we aim to derive an efficient procedure to approximately track the following CP's, which, as will later show, achieves rates of transfer automatically adaptive to whether the source or target data most beneficial.
min (0) subject to RQ(0) S Ro (0q.)) + GeQ: DERd
for fq. constrains Q-excess risk be of order no more than eq = O(d/nq). The solution of the limiting CP will therefore be important to our analysis, and is highlighted in the following definition.
1_000
Qq. Intuitively, the above CP's aim for an interpolator between O, and &g that
Consider the Lagrangian problem
max min Rp(O) x(Rq(0) - Ro(02) - 6EQ). X20 BERd
(3)
The auddle-point of the Lagrangian will be of importance in our anlysis.
Definition 2. We let (X* BrQ) denote the solution of above, whereby, by strong duality, &rq is the solution of the limiting CP in (
Mixed-Samples SGD. Algorithm| aims to approximate (X*, (PQ)) iteratively. However, since &o is unknown at the start of the procedure, the exact Lagrangian in 3 is undefined. Instead, the procedure maintains estimates of fq.t of 0g in parallel, and optimizes a time-varying Lagrangian (A, 0) (0) + X( terms of stochastic estimates of the constraint violations, and therefore tracks the Q-risk of iterates 0,- Iterates A can thus be used in turn to adjust the sampling rates (see setting of &,), i.c., to bias towards sampling from Sp Sq.
Rt Geq). Notice that the iterative updates of X are in
4 Main Results: Instantiation for Linear Regression
We use the notation M, supxex ||=||, My max lul and si = Amaz (8o) this section and subsequent sections. We start with the following definitions. Definition 3 (Key Lipschitz Parameters). Let p = 1100 OpQll. We then define
throughout
A (Ei))
Go = sup
(1((00=x,))) |10 0pql < 2p², (a,w) E SPo).
(((6:z.)) E(6': (2..v)) v) 6rol:
G = sup
2
1 log(T' 22n)) t (5iq)
|10 - 0 0pell² < 2p², (I, E SPQ, 101100
Ma.My

---

Algorithm 1: Biixed-Sample SGD
Input: 8u = 0q.0 0, Au O, stepsize {ar)i=o 7-1 and eq.
for t 0, .....
do
Draw & Bernoulli T+x
&. 1 then
Sample (#e: 84) uniformly from Sp
0,+1 = 02 (1(1 + Ve( 3+)
end
else
Sample (æ1, Mt) uniformly from So
0.41 = 0, - r7(1 + Ve(0;;;; m1)
end
Sample (z1, 91) uniformly from Sq
Ae+1 [1 Xe + 7) (E(0;;;0 yt) 100,,; Geq]]+
PQ.+11 Q. an VE(fQ,r; Tt, Vt)
end
Ō ppg l projection Et=o O, onto the constraint set fo: Ro)(0) Ro( S Geq cc
Output: 0pQ
Our main results for Algorithm T are provided below.
Theorem 1. Suppose parameters in Algorithm [ are
/T cq. 7 Cy T. and
Cpq for some Cyp Cyy and Cpq. Then, with probability 1 1- 5T over Sp, SQ A Aemin (Eq) E+2NQ ED T+2ng and the randomness in the procedure, the following holds for on sufficiently small function of (Go,G2, .). ey 2 G2 and Crq as a functionof (Mz, My. log T, Xtin (Σq)). The returned solution satisfies
EQ(OPQ) S min {EQ, Amax (Ep' Eq) ep {
(d((+)og(1/71)
(((d+1og(1/7) for some unversal constant co > 0. provided a cq = co
for cp = CU number of iterations
G8 GoG x X (EQ)EqEP
x&
2
Go GA+ log
I
T
The theorem is derived from both Theorem Of of Section 5.1 (on optimization rates) and Theorem of Section 5.2 on statistical rates. The exact requirements on Gr are given in Theorem 2
For completeness, in Section we provide sample-dependent upper-bounds on intervening quanti- ties, namely p. X*, Go. G2. in terms of less opaque quantities.
Adaptivity. As far discussed, the bounds of Theorem guarantee that the procedure achieves target risk always adaptive to whether the source or target is most beneficial: notice that if we were to use either the target sample alone or the source sample alone, we would be respectively achieving rates of the form E(02) S EQ. and ((p)) S Amax (Σp'Ee) EP + (lp))
other words, the returned solution Qp achieves rate that interpolates between the two. This is illustrated by the simulations results of Figure (the exact setting is described detail in Section 6.I..
4.1 Sample-dependent Choices of Parameters 7) and 7
In this section we provide sample-dependen upper-bounds on p. Go. G2 and A which drive the choice of 1 and 7 in Theorem[]
Lemma (p). Assume Σp invertible. The following upper bound holds:
(.((0)) +
My
0² = 100 -0pel
(4)
Amnin (5p)
Amiin (Ep)
5

---

Algorithm 2: Warm-up
Input: 00.0 stepsize {= - -- for / = 0, ,....,N
do
Sample (zt, M/) uniformly from So
02. Q2.t or Ve(o.,i Vt.)
end
Output: fq.N
Furthermore, let lq.N denote the output of the warmup procedure Algorithm X (Zq) 1428g" Then we can further bound (4) by the following quantity
2 with stepsize az
2
[V/xp(0 +
(E)) [1
miin (Eq)
MºM, 2 (Ep)
2
(5)
2
1 (pp)
Remark Lemmal Crmmma@rrovicnn provides a computable upper bound of p. which requires a few steps of SGD to estimate Qq. As the number of steps N increases, the [VRo(0Q term in tends to 0, and the whole bound becomes tighter approximation of (4).
Lemma 2 (Go). The following statement holds for Go: Go S 3M3p My
Lemma (Gx). The following statement holds for Gx:
MaP² + My M1 + (T' + 2x²))²²
Gx 18
-EQ-
(6)
(Atii (Se)))
Lemma (X*), Let be defined Desimition
2
The following statement holds for X*:
Amax (Ep))
X <
+
A (2q) 2 (Sq)
Remark In Lemma the second term depends on the norm of V Ri (02) divided by /eq. If Of is close to Qq. then the second term becomes small. As in Lemma one also use Algorithm find an approximation of Q. which yields a computable upper bound of X*
Analysis Overview
In this section, we will provide more detailed convergence bound and generalization bound, as well as an overview of the analysis of our algorithm. Theorem 2 provides the convergence result of Algorithm 0 with more detailed parameter setup than Theorem Theorem 3 provides the generalization guarantee of our algorithm.
5.1 Convergence Analysis
The following Theorem provides the convergence rate of Algorithm
Theorem 2. Let ||uu 0rqll, I 0.1, and a Gy be some positive real numbers such that
ore < 256 (1 + (2+)² + p²) G% S min
p 16 16 / 1og2/7 Crq
2/2
where Crq (1 2n² M M2
6og log(2/7)
and oz
log(T+2Ko)
Mn Suppose the
x (Eq)
parameters in Algorithm I are set as 17 = / 7
G3cm a4
A (Bo)) i-2ng and cu T+2ka
Cpo
Assume T 2 max 3Cpq T (lo.(log[
127 cQ
A (Eq) S and M2 2 1. With
cq GA (La)ea log 1/7

---

probability at least 1 - T over the randomness of Algorithm 7 the empirical risk of the returned solution satisfies:
(
63 + G X log +
Rp(0pq) Rp(OpQ) Go (x++Gxy10=+)
A (Eq)egV min
Moreover, the total computational complexity of the algorithm is O(dT) + time for projection.
Proof Sketch: We define Or = + Et= 0, and g( (0) Ro (60) 6eQ. First, we inductively show that, if choose properly small 17, can control all the iterates (0,, Ae) as well the final solution PQ to be stay around Qpq and X². Hence, we can apply the Go Lipschitzness on those iterates and decompose the risk as: Ry(OrQ) Rp(OrQ) S Goll0r 0roll + Rr(Or) Rr(0rq). To further bound |07 10--0pp) 0rell and (0r) Rr (0rQ), analyze the convergence of the Lagrangian function and obtain that
(pT) - Rp(0pq)+ + (g(0T))
C2 log
C3 (o(0r))
2(7 + oT)
vT
T
for some real numbers C1, C2; depending on T, Cp Go. Gx2 P. P. X² 'q and A (EQ) Next, we will
derive the lower and upper bound of g(0r) in terms of 00 0pQll:
(g(0T)))
2 2 A min (EQ)Eell0r - 0poll A g((r)) S Goll0r 0pall:
for A 60 - (Ro((( R (02) which captures the error from projecting Or onto the inexact constraint set (0) R2(0Q.T) GEQ + < 0. Plugging the above bounds together with Rp(Or)) (000pQ)= 2 -G dpQl back 77 one can solve upper bound of |0 0 ll- Notice that (7) immediately gives an upper bound of Rp(0r) Rp(0pQ) which concludes the proof.
5.2 Generalization Analysis
The following result establishes the generalization guarantee of our algorithm.
Theorem 3. Suppose QrQ satisfies (p(@p)) (p() S cp. Then with probability at least
1 - 4r over Sp and So, the excess risk of frq on Q satisfies:
EQ(OpQ) S. 26 min (EQ,>max Amax (2p' Ep + Eo(07))
To prove Theorem we first introduce some technical lemmas. The following lemma gives two information: any in the constraint set of (2) will have a small Q risk, and (ii) any that has small Q risk is covered by our constraint set with high probability.
Lemma 5. With probability least 1 2T, the following holds: for any 0 E (0: 110-0000
0ll s bEG).
we have (0) & 26EQ. For any 0 such that (o) S it is in {0 |10 0el1 < 6EQ
The next lemma shows that, 0% is in the constraint set of 2 any the constraint set with a small empirical risk P. then it should also have small population risk on P.
Lemma If 9. E {0: ||0 Boll? I <6cq], for any {0 ||0 Bllls S &co), with
probability at least 2T we huve Ep(() S 4( (tr(0ra)) + 16Ep.
The next Lemma considers the situation where O7, is not the constraint set of (2). Due to the inclusive property of our constraint set (Lemma 5), we can claim that any 0 in the constraint set has smaller Q excess risk than 87. up tp some multiplicative universal constant.
Lemma 7. 0p & {0: ||0
ll
beq), then for any 0 {0 ||0 60l13 I &6e)). with
5o probability at least 27 we have (o) < (67)(
7

---

Proof of Theorem First, if {0: 110 110-00 0o 2 I 6co). then since Rp(6pq) - Rp((pQ) -
6p, from Lemma we know with probability at least 2r, Er((rq) I 4ep 16cp = p. Hence 20 20 20 If 0
(0(O))) - 10pQ - 0 مم I Xmax
10:10000000
10 1 - 6EQ)
from Lemma 7 know (Q(0pq) S 2 (07, Hence know with probability least 27.
EQ(0pQ) s 26 (Amax (Ep Σq) EP +p E
On the other hand, since 0rg 10 110 - Aolls S ) from Lemma we know (Q(0)) s 26cQ. Putting piece together have with probability at least - 4r, it holds that
Eq(OpQ)= & 26 min {eq. Amax (Ep Σq) cp EQ(7)))
Proof of Theorem [ In Theorem 2 choosing I such that Rp((pp) - R2 S Ep, together with Theorem 3
will conclude the proof.
Experiments
In this section, we present the experimental results of our algorithm and the baseline algorithms on both synthetic and real-world datasets. We implement our algorithm using Python on an Intel
i7-8700 CPU. We use the CVXPY [99] package to implement the projection step in Algorithm T The baseline algorithms we consider are source ERM, target ERM, projected SGD (PSGD) (widely used for solving constrained problems) and Hypothesis Transfer Learning (HTL). For HTL. 5-fold cross-vale -ross-validation on the target training data to select the best bias parameter. For PSGD, we also employ CVXPY to implement the projection steps. Throughout the figures in this section, use PSSD and ÓTTT. denote the model obtained PSGD and HTL respectively. Due to page limit, we only present part of the results and defer additional ones to the appendix.
6.1 Regression Task on the Synthetic Dataset.
We start with the results the synthetic dataset. Throughout this subsection, set the model dimension d to be 50. The distribution P and Q are set to be d-dimensional multivariate Gaussian with certain mean and covariance. The label is generated as y = 8% T x + E for E {P, Q}, where 10-4, and iteration number T = 2000
for both our method and HTL. We use closed form OLS solution compute source and target ERM model. The results are demonstrated in Figure I and In Figure (Left), we fix ni = 100 and vary np from 100 to 1500. When np is small, target ERM learning can work better, while as we increase np, the source data becomes more useful. Our method can adapt to these two regimes automatically. It can also be seen that the ERM procedure has large uncertainty (variance) when the training data insufficient,
E ~ (O, 1). We choose
Increasing Source Sample Size
Increasing Source Sample Size
6,
Q excess risk
B.m
EExeess Risk
3.5
4
8/
3.0
2.5
6.
O
6.
6
1000 1200 1400
200
400
600
800
1000
1200
1400
nip
f1p
Figure 2: Linear regression results the synthetic dataset with low-rank Eg low-rank Eg. (Left) When E. is not full rank, constraint set then unbounded our method still works well. (Right) When Ep not full rank, we set we far away from P's range. In this case HTTL still biases the model towards min-norm dip and leads to bad performance. However, our method is not influenced because it directly learns from P's data.

---

Runtime Comparison on School Dataset
Increasing Source Sample Size
170
6:
0:
2500
Excess Risk
Time in second
150
GHTl
Orsco
2000
140
1500
120
500
110
200
400
600
800
1000
1200
1400
0
100
300
500
700
900
1100
1300
1500
Figure 3: Linear regression results on the School dataset. (Left) Excess risk on Q. (Right) Runtime comparison. Mixed-Samples SGD P achieves Q-risk nearly the same of that of the ideal projection method OPSAI,. while achieving significandly faster runtime.
while our method is significantly more stable. In Figure I (Middle) and (Right), we fix ni = 100, np = 500, and gradually increase Amax (Ep Σq) and (f7),, which measures the hardness of transfer. As the hardness increases, source ERM model performs poorly, while
method can always yield model that is comparable the better one between 0p and 0q. In Figure (Left), set Dg to be low rank and the target sample size to be extremely small (nQ = 50). In this case, the constraint set is unbounded but our method still works well. The rate of our method is still adaptive, while due to the limited target data, HTL struggles to find a suitable regularization parameter through volss-vaii,ttnnn, and hence loses the adaptivity. In Figure (Right), We set Ep to be low rank. We choose no = 10 and set w far away from P's range. We use SGD to compute Q ERM model since matrix inversion is unstable in this case. HTL. still computes the min-norm interpolator up as the reference model which has large risk. Due to the limited Q's data, HTL often fails finding proper bias parameter and still tries to bias the model towards Up which leads to a bad performance. Even though in some cases it finds the correct bias parameter (close zero), that means HTL fully abandons wp and cannot gain from P's data. However, our method is not influenced because it does not rely on the reference model to transfer knowledge, but directly learns on P's data.
6.2 Regression Task on the School Dataset.
To demonstrate the performance of our method on real-world data, we conduct the experiments on the School Dataset [20]. The dataset contains student information from 139 schools. The input x is a 27-dimensional vector containing student information and the label y is the student's exam score. Following [21]
the data points from the first 100 schools the source domain and the rest as the target. We set 1 10-4. We fix no = 100 and vary n. from 100 to 1 1500. Figure shows the MSE and runtime comparison with source ERM, target ERM, PSGD and HTL. We can see from Figure (Left) that our method consistently outperforms source ERM, target ERM, and comparable HTL and PSGD, and automatically adapts the better rate between source and target ERM learning. PSGD yields performance comparable to ours since it solves the same objective we proposed in but requires significantly longer time, as shown in Figure (Right).
6.3 Regression Task on the Berkeley Yearbook Dataset.
We conduct experiments on the Berkeley Yearbook Dataset 22 The dataset contains the gray-scale portraits taken in different years. The input & is the 512-dimensional vector feature extracted by ResNet18, and y is the year the photo is taken (ranging from 1905 to 2013). We construct source and target tasks by varying the proportion of male and female photos. In the source dataset, 50% of the samples are drawn from male photos and 50% from female photos. For the target training and testing dataset, the ratio is adjusted to 75% male and 25% female. We choose 1) = 10-4 for all algorithms, and iteration number T 2000 np for both our method and HTL, and T = 500 np for PSGD since we found it can converge in fewer epochs. We use closed form OLS solution to compute source and target ERM model. We fix ni = 100 and vary np from 500 to 1300. Due to the difficulty of the task and the limited target data, the target ERM model suffers from very large errors and is therefore omitted from Figure We report the MSE comparison with source ERM and HTL, well as runtime comparison with HTL. We can from the left sub-figure that our method

---

Runtime Comparison on Yearbook Dataset
Increasing Source Sample Size
500
Target RMSE/STD
5.5
Time in second
400
6,
0.m:
4.5
100
3.5
700
800
900
1000 fi
1100
1200
1300
11p = up no= 1300
Yearbook dataset. Input features dimension 512 are extracted by ResNet18. (Left) Q excess risk. (Right) Runtime comparison. In the (Left) we omit the performance of target ERM since the target ERM fails on outputting a generalizable solution and results in the error over 4000 duc to that the task very difficult source data source data and significantly outperforms the competitors.
Figure Linear regression
target sample size only 100. HTT. (fmm) has difficulty adapt to the situation where helpful than target and results in large target error, while algorithm (Qrq) gains from
can consistently outperform source ERM, target ERM and HTL, and can automatically adapt to the better rate of source and target ERM learning. The right sub-figure shows that algorithm achieves superior runtime performance compared to HTL when np < 1300, while when np reaches 1300, HTL becomes the faster one. This difference arises from the inherent nature of the two algorithms: our method primarily optimizes over the source data, so the total number iterations increases with np grows, In contrast, HTL focuses optimizing over the target data, using the source data only to compute a reference model. As a result, its runtime remains relatively stable as ny increases.
6.4 Binary Classification Task on the CIFAR-10 Dog vs Cat Dataset.
At last, demonstrate that our algorithm can work for general convex losses, we conduct the binary classification experiment on the CIFAR- 10 Dog vs Cat dataset [23], using linear classifier and logistic loss. We construct source and target tasks by varying the proportion of dog and cat
Increasing Source Samplc Size
0.20
Terget Misclssificctton
images. In the source dataset, the ratio 50% dog and 50% cat. For the target training and testing dataset, the ratio is adjusted to 80% dog and 20% cat. We use SGD with stepsize 10 and epoch number 1000 to compute P and Q ERM model and HTL model. We choose step- size for to be 10-5 and that for to be well T 2000 np in our method. We fix no = 50 and vary np from 100 to 1500. The results are reported in Figure 5] Target ERM model performs poorly since the target sample size is small, while our method can still enjoy an adaptive and slightly outperforms HTL.
0.10
Figure 5: Binary classification results on the CIFAR Dog vs Cat dataset. We use linear classifier with logistic loss. Input features of dimension 512 extracted by ResNet18. fix ni 50 and increase npp verifies that our algorithm can work on the general loss.
7 Conclusion
In this paper, we propose a concrete optimization algorithm with provable convergence and general- ization guarantee in supervised transfer learning. The analyzed procedure is a mixed-samples SGD approach that alternates between sampling from source or target data at an adaptive sampling rate. Both theoretical and experimental results show that our method is adaptive to whether the source or target data are most beneficial. This work aims to initiate the theoretical study of computationally efficient methods for transfer learning.
10

---

8 Acknowledgement
Both authors are grateful for support under NSF Award Number 2334997:CPS: Data Augmentation and Model Transfer for the Internet of Things.
References
[1] Iiaa Kuzborskij and Francesco Orabona. Stability and hypothesis transfer learning, In Interna- tional Conference on Machine Learning, pages 942-950. PMLR, 2013.
[2] Ula Kuzborskij and Francesco Orabona. Fast rates by transferring from auxiliary hypotheses. Machine Learning, 171:19,,, 2017.
[3] Shai Ben-David and Ruth Urner. On the hardness of domain adaptation and the utility of unlabeled target samples. In Algorithmic Learning Theory: 23rd International Conference, ALT Springer, 2012.
2012, Lyon, France, October 29-31, 2012. Proceedings 23, pages
[4] Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. Advances in Neural Information Processing Systems, 32, 2019.
[5] Steve Hanneke and Samory Kpotufe. A more unified theory of transfer learning. arXiv preprint arXiv:2408. 16189, 2024.
[6] Mehrdad Mahdavi, Tianbao Yang, Rong Jin, Shenghuo Zhu, and Jinfeng Yi. Stochastic gradient descent with only one projection. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25, Curran Associates, Inc., 2012.
[7] John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman. Learning bounds for domain adaptation. Advances neural information processing systems, 20, 2007.
[8] Yishay Mansour. Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.344 3430, 2009.
(9] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
[10] Mchryar Mohri and Andres Muñoz Medina. New analysis and algorithm for learning with drifting distributions. In Algorithmic Learning Theory: 23rd International Conference, ALT 20/2, Lyon, France, October 29-31, 2012. Proceedings 23, pages 124-138. Springer, 2012.
[11] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density ratio estimation machine learning. Cambridge University Press, 2012.
[12] Masashi Sugiyama, Taiji Suzuki, and Takafumi Kanamori. Density-ratio matching under the bregman divergence: unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics, 64: 14:1009-1044, 2012.
[13] Simon S Du, Jayanth Koushik, Aarti Singh, and Barnabás Póczos. Hypothesis transfer learning via transformation functions. Advances in neural information processing systems, 30, 2017.
[14] Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Minimax lower bounds for transfer learning with linear and one-hidden layer neural networks. Advances in Neural Information Processing Systems, 33: 1959-196999 2020.
[15] Xuhui Zhang. Jose Blanchet, Soumyadip Ghosh, and Mark S Squillante. A class of geometric structures in transfer learning: Minimax bounds and optimality. In International Conference on Artificial Intelligence and Statistics, pages 7794-3820 PMLR, 2022.
[16] Jiawei Ge, Shange Tang, Jianqing Fan, Cong Ma, and Chi Jin. Maximum likelihood estimation is all you need for well-specified covariate shift. arXiv preprint arXiv:2311.1561,, 2023.

---

[17] Reese Pathak, Martin J Wainwright, and Lin Xiao. Noisy recovery from random linear obser- vations: Sharp minimax rates under elliptical constraints. arXiv preprint arXiv:2303. 2023.
[18] Yihang Chen, Fanghui Liu, Taiji Suzuki, and Volkan Cevher. High-dimensional kemnel methods under covariate shift: Data-dependent implicit regularization. arXiv preprint arXiv:2406.03171, 2024.
[19] Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddeed modeling language for convex optimization. Journal of Machine Learning Research, 17(83)11-5, 2016.
[20] Arthur Asuncion, David Newman, et al. Uci machine learning repository, 2007.
[21] Mikhail Konobeev, Ilja Kuzborskij, and Csaba Szepesvári. A distribution-dependeee analysis of meta learning. International Conference on Machine Learning, pages 5697-5706. PMIR, 2021.
[22] Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, and Alexei A Efros. A century of portraits: visual historical record american high school yearbooks. In Proceedings of the IEEE International Conference Computer Vision Workshops, pages 1-7, 2015.
[23] Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
[24] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[25] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018
[26] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
[27] Sebastian Garcia, Agustin Parmisano, and Maria Jose Erquiaga. lot-23: A labeled dataset with malicious and benign iot network traffic. (No Title), 2020.
[28] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- plas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Édouard Duchesnay. Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12(85):2825-2885) 2011.
[29] Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. The Twelfth International Conference Learning Representations.
[30] Guanghui Lan. optimal method for stochastic composite optimization. Mathernatical Programming, 133(1):365-377, 2012.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly claim our contributions and scope in both abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We point out that our theoretical results are for convex functions which can be potential limitation.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
In our Theorems, we clearly list the assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We report clear experiments setup in the Experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer:
[No]
Justification: We do not make our code public at this moment. The data used in the experiments are open source data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
public/guides/ howpess/oooosuubsssssoooooooo
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips. //nips.cc/ppl wwwppbblccgguiicuceccccccoe.oopp wttpggudddee/eeebbiiiinneeee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We discuss this in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report them in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report the compute resources in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
This paper conforms, in every respect, with the NeurlPS Code of Ethic.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification:
This is theoretical paper so we are not aware of any societal impacts of it.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
Justification:
This is theoretical paper so we are not aware of any risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the references for the datasets used in the experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not have crowdsourcing experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neuripe::: /ttpaarrpp..cco/ooofeeeeeeee///s for what should or should not be described.
19

---

Algorithm 3: Biixed-Sample SGD (Restated for General θ)
Input: 8u = 0q.0 0, Au O, stepsize {ar) 7- and 7). 7, eq.
for t = 0, ...... .
do
Draw & ~ Bernoulli T+x
E. 1 then
Sample (#e. 84) uniformly from Sp
0,+1 = Pa n11 + Ve(
end
else
Sample (2t, 8t) uniformly from So 0.41 = Pa n11 + V 21,
end
Sample (21, 81 uniformly from Sq
Ae+1 [1 - -m) d + T)(((0;; ut) 1(0 xe, 3eq]]+ PQ.+11 (o(0 at Vi(0Q.1) Tt, v/))
end
0 Pa l projection + Et=o O, onto the constraint set (o (0) R2(00))) S 3eg 3 cc
Output: 0pQ
Results for General Losses
In this section, we provide the results for general convex losses. We consider a hypothesis class H = {z ho()) E G). We make the following assumption on the loss function &.
Assumption 3. ((0;x.)) y) is m--strongly convex and ma-smooth in for any (x, v) Srq-
We define ε = m1/m2 the condition number of f.
We consider general C RRD, possibly a strict subset, and therefore present a version of the algorithm that projects iterates back to O, provided projection operator Pe (see Algorithm 3): when θ = R i.e. unbounded, the operator reduces identity mapping so Algorithm reduces Algorithm D in the main paper. Note that this projection operator is usually cheap for the common choices of O for example, for the sake of regularization in practice (c.g., ridge-type regularization), often is an lz unit ball, whereby (o) = 0/ max {1, [[0]].
For the convergence analysis, we need the following definitions.
Definition 4 (Key Lipschitz Parameters). Let p = 0o opoll. We then define
Vi(0; x. w)ll 0 0- 0ro
S 2p², (x, E SrQ.
Go sup
||0|| < 1 log(T +x)
V x/.0/''///) ,3'))l
sup (e'w))ESg
110 0 0pQ | 22p² (x,1) SpQ.
|e(0; x. v/ - E(0'; xx, 3EQ
G = sup
1 + log(T + k)
||0'11 <
sup (x' (
(V((0
mi
The above definition captures the Lipschitzness of the risk function the iterates generated during our algorithm proceeding.
Definition 5 (See (6)). For e 0. let r(e) = inf (IV :0 e e, - =
This notion is used to control the distance between the return solution and solution before the last projection step, i.e., ||0r 0roil where Or + T-1 0, In linear regression, we can explicitly compute it as r(c) = A (Eq)
20

---

Theorem 4 (Strongly Convex and Smooth Result). Let p² -160 - 10ppplll? r T 0.1, and pQ Cyy be some positive numbers such that
Qrq S 256 (1+ (x*) + p²) C2 and on S min
p
P
P
CpQ S
16 16 pQ corrrgg//// 22/2Gx
where Cpq
2m 2x)
[VR 110 mi
+
609 log(2/=1
for oā
m1
(E VE(0Q,0i m1
og_ ? Ggen Assume the parameters in Algorithm 3 are 1
VT ae 1
mi 222n and
= Crq_, Assume T 2 max T42eq'
4Cpqm. r(3eg)
(log( +2xa11" )²), and r(3eQ) S 1, then, with
Gx /eg log 1/7
probability at least over the randomness of Algorithm the empirical risk of the returned solution satisfies:
G2 Gy
+ G log
X
log + + GR
Rt((0PQ) Rp(00o) & Go + Ex G
r(3EQ)VT
VT
Statistical Implications. In this section we give example of how the above Theorem 4 can be converted generically to statistical guarantees on transfer (as was done for the linear regression case).
For intuition, Theorem g guarantees that (rr()))) ) is small, i.e., close to (p(Qrq) while we also know RQ(0pQ) is also small, i.e., close to R2 (0g) (since (0p)) a projection of the average iterate onto the constraint set centered at @Q.r). Thus, if in addition, have concentration of empirical risks to true risks, we can convert the guarantees of Theorem 4 to statistical transfer guarantees.
The results below illustrate the above intuition. These results are expressed in terms of generic relations between P and Q risks given as follows.
Definition 6 (Weak Modulus
5
Given >> O, we define the modulus
(c) = sup (Eo(0) (p) I c, E)
In words, the weak modulus captures the best achievable Q risk, if the learner only has access to P's data. For instance, in linear regression, as explained in the main paper and shown in (5) it can be upper bounded as 6(c) XAmax(Xp Σq) 2Eq(0p))
We next consider some traditional concentration results for bounded losses in terms of the Rademacher complexity of the loss class.
Assumption 4 (Boundedness of Loss). We assume E(O; 10, 3) S Me for any 0 O, (z. v) E X x V.
Remark 3. The Assumption hoold for strongly convex loss given that the parameter 0 's's norm is bounded, e.g., ||@|| < B, v0 θ. For example, in linear regression, we assume the label space Y I-I-M, My My). then {(0: x. y) (0Ta x y)² 2B M + +MM.
We then introduce the Rademacher complexity which characterizes the complexity of a class and will be used derive uniform convergence result.
Definition 7 (Rademacher complexity). Let be a family of functions mapping from Z to and be the i..dd samples drawn from distribution μ. Then, the empirical Rademacher complexity of F with respect dataset Z is defined as
Z = (....... ... 2n.
Rr((F) EEE(LIT"
sup - Dn srf(es) fEF
where En are i.i.d. Rademacher random variables with PfE = 1) = P(e, -1} = 1/2. Then Rademacher complexity Rn(F) ) is defined as Rr(F) = (F)
21

---

dllogn Assumption (Bounded Rademacher Complexity of Loss Class), We assume R., o H) I Bu. for some positive real number Bug which characterizes the complexity of the loss class & o H. Remark 4. The Assumption is standard. Here we give some examples.
v
For linear classifier class H = {i + TT x 2:00 0 E R. |1 S B} with L-Lipschitz loss, the bound 124
Lemma 26. 10]10] is given by R., (f H) I LBM². //
For layer neural network class H = {I+ Wir (.......... o...)).... [W,ll & {B}} with L- Lipschitz loss, the bound 25 Theorem i given by
LM j=1 B,
(n H)
VTi
For general VC class H. S (1,11 (e, H. S
with VC dimension d, the bound 126 Corollary 3.8] is given by
n
With the above two assumptions we can derive the following rate of uniform convergence.
Proposition 1 (Uniform Convergence). Let denote either P or Q. With probability at least the following stafement holds:
sup (0) - (0) S BH.E Tmp
log 2 =
+ Moy
kEH
2np
Corollary (Statistical Transfer Guarantees). Let
Ep Buue + Mej
log 2 2np EQ
Bu.e
log
Mey
Vnp
VnQ
2nQ
Then with probability least 1 35 over the randomness of Algorithm
3 and Sp and Sq. the
returned solution satisfies
Eg(DpQ) 55 min fco, (3cp)},
provided number of iterations
2
+ GoGAy Cy
X. log &
1 TZ (oo GGo+Gyylog log
r(2EQ)EP
EP
Here we achieve transfer guarantee similar that in Theorem [I] The rate is still adaptive-ir achieves the better rate between solely target ERM and source ERM. The required iteration number depends on the cp and r(cq), also similar that in Theorem
10
Additional Experiments
In this section we provide additional experimental results.
10.1 More Results on CIFARIO Dog vs Cat dataset
Here we provide more results CIFAR10. To verify the adaptivity of the algorithm with increasing target samples, we conduct the experiment with fixed np 100 and gradually increasing no from 100 1500. We use SGD with stepsize 10-5 and epoch number 1000 compute / and Q ERM model and HTL model. We choose stepsize for 0 to be 10-5 and that for À to be 10-3 as well as T = 2000 max {np, no} in our method. We set the source dataset be 80% dog samples and 20% cat samples, and the ratio for target is adjusted to 50% dog and 50% cat. As we can see from Figure in this setting source data are not informative so the source ERM performs poorly. As target sample size increases, the target ERM can give promising performance, and our method can also adapt it. HTL performs the best in this setting, but runtime dramatically increases as the target sample size increases.
22

---

10.2 Binary Classification Results on the Malware IoT dataset
Here we provide results on the CIC-IDS-2011 dataset [27] It network traffic dataset where the goal is to predict whether the traffic is benign (normal) or malicious (abnormal). We train linear classifier with hinge loss. We use the network traffic data collected on Wednesday (Wednesday- workingHours, Satpuuuspcap_sSS1._P ISCX.csv) as the source dataset, and that on Friday (Friday-Workse Wor.oinooinnuu--- Srreooon-DDDspppppp Sepp_SSXX.com csv) as the target. We first fix the total Q sample size no 1000 and gradually increase the P sample size from 1000 3000. We set stepsize for 0 to be 10-3 and Since the abnormal data are very few, to ensure an acceptable
for À to be 10-3 and EQ- = Qnq
Type-II error, we weighted hinge loss with weight 2.2 i... (0) = 1 ()))((0 where Ro),(0), 1 denote the empirical risk on the normal data and abnormal data respectively, which is widely used in weighted SVM for imbalanced dataset (28). The results are shown in Figure 7 As we can see, as the number of abnormal data from P is growing, our method gains from the source data and yields better Type-I and Type-Il error than baselines. The runtime of our method is significantly less than HTL since HTL needs expensive cross-validation process.
11 Missing Proofs in Section 4.1
In this section, we provide the missing proofs in Section 4.1 We first introduce the following helper lemma that lower bounds the norm of the constraint gradient on the boundard of the constraint set.
Lemma (Lower and upper bound of boundary gradient). For any e O, the following statements hold:
v [R)( = =x (ÉQ).
min
R
Proof.
We start by proving the first statement. First, the 0 on the boundary of the constraint set We first decompose 0 0 0' + where 0' E (RangeEEo)) and 0 is
satisfies:
00 Sag
in the null space of Eq-
Now we examine the gradient norm:
min
V (0)
min || d 11
E2(( -o)
9: (()) =
|S0(00 - -0o) |
min 0r Range (1g)
||0- Ay I1
min Hc Rangag ( |n|
Vei
E (2q))
Increasing Target Sample Size
Increasing Target Sample Size
Runtimm Comparison on the Cifar Datoset
0.05
3300
0.00
0.35
Time in second
2300
mick
0.55
0.30
0.30
0.45
6um
1500
0.400
1300
0.55
0.15
200
400
600
1000 800
1200
1400
200
600
1000
UK 13M0
Rl
Figure 6: increase no gradually. (Left) Target excess risk (Middle) Target misclassification rate. (Right) Runtime comparison. Our method (Ōpq) is still comparable with target ERM. HTL (0Hm.) slightly outperforms ours, but ng increases, the runtime of HTL dramatically increases.
Binary Classification on the CIFARIO Dog vs Cat dataset. We fix np = 100 and
23

---

Increasing Target Sample Size
Increasing Target Sample Size
Targel Misclassification Rate
0.65
1.2
+
6,
8.
Target Type Error
0.55
0.8
0.50
0.o
0.6
010
0.4
0.40
0.2
0.35
0.0
0.30
-.2
1000
1250 1500
10001250 1530017500000 2250250027500000
Zp
Runtime Comparison on the CIC-IDS Datasct
Increasing Target Sample Size
1.2
800
8,
A
Target lype II Error
1.0
6,
Time in second
600
0,m
500
0.6
400-
0.4
300
0.2
200
0.2
2500220000001120000022222 25002750300
1700 2500
flp
00p
Figure 7: Binary Classification on the CIC-IDS-2U0 2017 dataset. We fix no 1000 (total samples from Q) and inerease np (abnormal samples) gradually. (Top-Left) Overall Target Error (igh-Right) Target Type-I Error (Bottom-Leff) Target Type-1l 11 Error [Bottom-Right Runtime comparison. Our method ($)2) achieves better overall accuracy than baselines. We also achieve better and more stable Type-Il error than all other baselines. The runtime of method also significantly less than HTT..
Proof of Lemma
Proof. Due to Jensen's inequality, we have that |00
BrQ
< <2|100
0o 6p (= +2 =2|00 BrQ
which is at most
||
2 00 0pQ 12
V (00)
V [RP((o) || + +2 8Pol
Sp
212 (Ep)
21 (Ep)
Amiu (Ep)
Since 0rQ is the minimizer of Ap within constraint set, and Og is also in the constraint set, have
(v)p((Q)
0r 0rQ
2 10 00
1
<
1..p
S.P
4Amia (Ep)
Putting pieces together have
2
(Rp(
|00 0re
1-- 5
212
(Ep)
2X2 min (Ep)
min
Proof of Lemma
Proof. For such that |0 0 0pol
1
5 2p², we examine the upper bound of its norm. According to
triangle inequality have:
||0|| S /2p+ +
0ro S 3p.
24

---

The rest of the proof follows:
(ve(0,,,,)1l |1 x (o--)] s M 101 + M2M
Proof of Lemma
Proof. The proof simply follows the definition of P:
|e(0; æ, y) E(0'; v) - 6EQl - (0 1 - y)² + (0 x ---) y)² + 6EQ
$ 2M |101² + -2M, 2M 110/11 + cQ
$ 18 M2p² M,+ + Mr + log(T + 2n
+ 6cq.
(A (Sq)
Proof of Lemma
Proof. Due the first order optimality condition have
v v
=
v v
|| / (0
To upper bound
we notice that
(0r -
< 2 Amax (Ep)
0>>|| = 2/ (fr) Re((PQ)) - R(r(0)).
Define 0' to be the model on the boundary of constraint set, and also on the range of بig. That is,
|o' 18'- - E BEq and 6' Range(Eq). Since 0ro is the minimizer of Rp(-)) in the constraint
set, we know that
[ 22 Amax (mpx v Ro(0)) Rp(Op)
2v Amax (PP
112 (0' - -0p)
2
2 2Amaxx (Ep)
88' - -pp
20max (Ep)
0¹ B0ll 22maxx (Ep) 22
|0o -6p
< 2Amax (Epp
5:1/2 (0' - -0o) + 222max (Ep) (2) 0p
v x (Ee)
2Amax (Ep)
/BcQ + 2Amax ( Ep0 - -67/|
t ($12)
To lower bound ( ||. we again evoke Lemma 8 that V (Ro / (ttin(Qo) BEQ Putting pieces together will conclude the proof.
25

---

12
Missing Proofs in Section 5.2
Proof of Lemma 5
Proof. The proof mainly follows Proposition 8 of [5].
With probability at least 1 2r, the following
0: |00 8
two facts hold. For one hand, for any 8 E
I
6EQ
we know
(0-0)=10-o@l1 s2 O 3i
+2 0
00
4
0
0Q Sig
2Eq S 26rQ-
where at the second inequality we evoke the matrix concentration result from Lemma 3 of [5]. For the other hand, for any such that (0) S <q. we have
|0
00
1 S2
3
|
80
2 mg
3
0
1 Eq
+
A0
08 1 1g
6EQ.
2
Proof of Lemma 6
Proof. First
notice the following decomposition:
||0 07 S 2 - QPQ
Ep
2 >10po 0p Ep
2
For the first term in RHS of above inequality, with probability at least
have
010 - 0pQ
2
S sallo Oroll (O) - - (V
0 0 0-
bip
Since both 0 and ÔrQ are in the constraint set of Problem 2). and ÖpQ is the optimal solution within the set, we know (VRp(Ora), 0pQ) 2 0. Hence, we know 2 ||ee 0pQ Ep s
4 (Rr(()) Rr(0ra)).
Now we proceed to bounding 2 llôra - 0%
2
Notice that with probability at least 1 - 2F
E3
2 0pQ
8%
2
Σ 4
0PQ - 0p
+
0
87
E3
Erp
Ep
8
PPQ 0p 2
+ 4
00p 07
2
< 8
0% 0p
+ 4
00p 0g
Er
< 12 03
0p
2
+4
0p
0%
1
Ep
7p
< 16cp:
where at second and fourth step we evoke matrix concentration result from Lemma of (5), at third step we use the fact that 0p is the optimal solution within the set. Putting pieces together will conclude the proof.
Proof of (
Proof. Since 07 & { 0: 10:10-00l
60l2 s <bc
then from Lemma 5 we know with probability at
least 1 2T, (g(7))
> EQ 1/ ( holds.
26

---

13
Proof of Convergence
In this section we will present the proof of the convergence result. We first introduce some useful lemmas.
13.1
Technical Lemmas
The following proposition is standard and will be used to show the sub-gaussianin of the stochastic gradients.
Proposition 2. Given random variable X, if S X s b with probability 1. then X is a (b-o)² sub-Gaussian random variable.
The next lemma establishes the convergence of 0Q
Lemma 9 (High probability convergence of lQ,:). If we choose at = Ama (EQ)()+ then with
probability least for any 2 we have:
Ati (Eq) + 2xq) |00
609 log(2/T) 1)
Ro(00x)) Ro)(0o) 5
+ 2x0
x min (EQ) + 2ni
for oB (M²
[++og((++2xp) M1 My + My
A (Fig)
Proof. We first examine the boundedness of ||0 According to updating rule of 02.+ we have
00
|10 1 - 02 y/))l
[I(I - (022x,)0Q2.4 || + ||
1 M₂M,
110 +
aml X (EQ) + 2k²))
+ log(t + 26Q) My * (Eq)
(8)
Hence compute the nub-Gaussian parameter. Notice that
v ve(0q.) u.) (io $ |a Eie |10 +
xxx2
no
log(t 2(1Q)
2M2
MyMMy
-2MM
X (Ei)
+ log(T + 22x)) MaMM
2M
+M,
X (Eo)
According
to
Proposition
we
know
Ve(lo.::0..) - (Ro( is
MM2 (1og((++22a) My + Ma.M,) A (Ee) (Se)
2
sub-Gaussian.
Now, evoke the result from Theorem 3.7 from [29] that if the gradient noise is aq aub-Gaussian. then with our choice of as, with probability at least 1 7 it holds for any integer t that
A (Éq)(1 2xq)
00
6og log(2/r)(log 1) t
Ro(00.)) - (0)
t 2nQ
(Eq) 26QQ)
27

---

The next lemma proves the sub- sub-Gaussianity of the stochastic gradient used to update 8,. Lemma 10. Ler
()V Sp, w.p. T (1+ 2)) Sq. w.p. I+X
90
and
8 (kr + AV 90
Then for any 0 E {0: 10 10:100-0pp) 0rall < 20²² and x E x we have Blexp(8 /opa) S exp(1) for 0pQ = 256 (1 + (2*)² + 42)6% 6%.
Proof. We use & to denote the event that we sample from P. and otherwise from Q. For notational convenience we define 6, = R (0) Ve(0; æ, y)ll where x, y is sampled from
f for μ denoting either P Q- We also define <rQ = rīr (o) Since
5 (Rr(0) + -V) (1 x)(I(=== Ve(0, +I +I 0) Ve(0: 2, y)) we can
verify that
Eexp (6² /op2)
1+ Eexp
[ (1+ x 1022
[[ (1 A x,
1 10020
+ 1 X
Eexp
2(1 +11+8)888
2S2Q
2(1 + 1)202
$
E Eexp
+ 1+X
E Eexp
1+
Piq
2A² exp
2260 dPQ
2(1 + +))68
1+ S
exp(
2(1 A)2
+ +dexp
Eexp(
OPQ
JPQ
dPQ
Since 0 S X S 22p + X3, so we have
E Eexp (8 /02)
< 1 X exp (2(2(>)) + +402)443/030 Eexp ((444(((2)) 422))))))++))))000
1 exp (4G8/0²22 Eexp ((4 + 4(2())) 4. 182
A
Due to our choice ui-0 256 (1 + (X*)² + p²) G3. we have
A
Eexp (6² (6²))
1+ X exp (1/8) (ex
exp (1/8) (exp(1))1 S exp((1)
1+ X
Then, we establish the convergence of the penalized objective, under the dynamic of Algorithm Lemma 11. For Algorithm!] / least 1 T:
the following statement holds true for any x 2 0 with probability at
(Rp(Or) - (r(0ro)) + ((Q((Fr)) - (R((()))(ocg) - (EQ) 662))
22
2TT
I 0² nT + +n² +n +
G2 /308 2
V2pa v
3 Blog
(x+ 2v20)
VT
VT
Cpq(log(T +2RQ) + 2)2 (X* + 22)) +
G (GA//log 3log
Cro(log(T 2xR) + 2)2
x,
T
T
where CPQ := (1 (1+22 2kQ) Mr.
6 log(2/T) A (En)
(M3
[++on[(++2gg] +2xg) MsM,) + Ms.Ma)² A (Eo) (Sq))
28

---

Proof. Define the constraint function g(0) == RQ( - Ro((0)) - beQ and L(O, = Rp(()) -
722 We first show that 00. 0ro/ 2 + 11 - x²12² s 2p², for any E [T]. We prove this
Ag(0) - 2 by induction. Assume this holding for t, and for t + 1 we have
|0+:1 - 8ra 2 = 0/ nob 0ræl l
|
= 110- 0rce 12 2 (nsoo 0. - 00- +1² |966
(1 + Xe) Ve(0 we) (1 we) ~ Sp: w.p. Ithi
where ge
(1+>)) Ve(r;; yr), (D4, ~ Sq. w.p. 1+h
Then for t + 1, we have:
|0+11 - 0ro| 1|
< | 1| -2m (VRr(())) x, 2. 0: 10-00-0000 -dra)
+ 22220 + 1/:(1 (1 + 2,
$ 0. 8roll el
2n ((0), - L( L(0pQ, 20)) + 222nd + &2
where 6,
(0+) + Ar v (0.) ob and at last step we use the convexity of Ll: \c)
According to Lemma 10 we know that
Eighl (0,) A V ( Blexp (6//03a) S exp(1)
Similarly, have:
|e++1 x²p= Ar -- 2n (oi, de- xx) + - 7de
< 1A --12 21/ (0.) (00) -EQ - yde, de de- xx))
+ 2222222 2m - 2v 2mpupp + +2n 2n
$ (1 -m)l, X12 2n [[(0,,))) L(D(,Ae)
2- 2mmpp 222nhhpp2222 2n)
where
9¹ = E(O1i v1) e(022,1 F1, Ut) - 6EQ
and
Ti = [(00r:20, w²) - ((0 Iz, xx,,,) v1) - (0.) - Reo A -((((00.))) - (0o))
and at last step we use the 7 concavity of L(f(. -). It is easy to see that
ElgA] RQ((,) - RQ(02) - cq, Elexp (12/GR) S exp(1).
Putting pieces together we have
|0++1 10+110ppc 0poll" + 1 5 (1x: 1 119+110--- -1000))-00p
12)]))=)) -2n (L(0,, x²) (aat)-L(pppp) L(0pq, 2o))
+ 222nmopp + +2v2nr.pp + 22 222nhepp + 227 + 1 + 22)
< |e 2-12 + 11100-00 0rr 3ro1() 10)-
-2n 2n [I(Or,>') I.ōrq; 2x))
2-222/12
+ 2r22 + + + ~2 + 2222mp66 +re + hir)
where the last step is due to
722
L(Or,)-- L(Ōrq, A1) Rp(())) + (0) (Rp(OpQ) + (1o(0pa)
2
29

---

Performing telescoping sum yields:
- >2p?= |A:11 - -rrol' + +
(1180 - 0roll I| + 1o - 1
-xPp + 2n + +np(1+ V2p + 22)
r, + 2/2n Σ hg + TT)( + 2/2np Σ 8, + 2V Σ
==0
==0
==0
Due to Lemma 4 of [30], we know with probability 1-1/2.
T-1
T-1
be = Toproy V 3log
2
Σ
rt S VTO /
3log 2
(9)
T
x²
1=0
A (o)2)))))) 66 1|
60g (logt/)
and also according to Lemma 9 he I
+ A min (2
for og =
2+2kg
[M3
[+ 22x)) MyM + MyM,
2
which yields:
Amia (2e)
000 2
A (Sq) (1 + 2xQ))
6og log(2//)(log s 1)
h1
+ 2nQQ
1 (Eq) + 2ni))
==0
s=0
|
2 +
(log(t + 2xQ) + 22 603 log(2 (og(2//)(logt 1)
min (EQ) + (2(2m)))
Athn (2e)
I Cpq (log(t + -2kQ) + +2)
(10)
where CpQ : 2kq) M. + 5 log(2//)
and in the first inequality we use the fact Σ 1
8 5
(Eo)
1+ 1-1 $ 11+ log Putting pieces together yields:
|0++1 - Opoll" 2 + |ee+1 - 11 - 1o0 22 +
xx +1100 -Opell + 21206 + 1 + V2p + X-)363
+ LV2npyTTgg v 3log -
+ +2 + 2kg) + 2)2 + Tym((*
(11)
Since we choose 7 =
Su vT
and 7 = Giil. where
P
p
P
cn min
)
2v26x 2(1 + V2p + X-)Go" 16 log 2 4Cro
we conclude that | opel
I' + + - -1113 s 2p².
Now by similar analysis we have that for any A2 0
|0 8ro| -
( + +1ee+1 - 212 s 0: | || +1 - X|2 - (7((((),)) - L(Prq, de))
+ 22 + 172(1 2r
2n (((01;z2,,0 91) E(0Q, Ie,
91) (()
(e(0.) E(OQ:)), de A)
+ 2n (((p) =((tQ.); \ - 1) + 2npre |0, fPQ
S 00. 0rq/ 1| + 1>: - -112 (n)(L))) - L(ārq; X1))
+ 2222 + 2 + 2x)²
+ 21r, (N. + 2) + 2 ()e + X) + 2V/2n..p.
30

---

Since 1Ag -1-1 S 22 we know X S X" + 22p Hence we have
| 0rol 0 + +1e+11 - 212 < 1 2/2 + 0: - -drll | - -21)1(0r,)) - L(ōrg, x1))
+ +2 6 + 1/ + A1) ) + +217r (x* (2=+ + 2nn/e (x* + v2p)
+ 2 A + 2nphaa + 2V2ndop
Performing telescoping sum yields:
T-1
Σ
L(0r, A) 1(0rQ, S 2/1T
2/7 (1A0 - 212 + 100-00 0rQ
2 + 7 + 2T
1
Σ
T-1
(1 +
T t=0
1=0
T-1
T-1
1 T-1
+
T
Σ
(X- + v20) + T
Σ
11 (x* + v20)
+
Σ
rd
1=0
r=0
t=
T
T-1
1
+
Σ
hat
+ v
Σ
6c.
1=0
t=0
By the definition of Lagrangian, we have
T Σ (0,) + Ag(0,)
2x² - Rp((pp)) - de ((00p)) +22x3)
2
=2
50
27 (120 212 1/=1100 0rol
1
1
1
<
21/T
+
T
+
2T
11
+ Xc) 208
1=0
3Σ r2 (x* + v20)
+
1 T Σ he (x+ + v20) + + Σ
n
1 T
Σ
ha
~2
V20 1=0
1
Σ dr.
0=
t=
Evoking the bound from
9 and I yields:
Σ (0.) + +>g(0))
_x² - (kp(pp))+
+ xZ))
T-1
< 21/ 1100 -11² + 000 100-ppq 8pQl 1| ) + 1
1140
T +
2T
1
71
Σ
(1+ (1+>)) &r
1=0
+ 1
VIC2 v 3300
2 (1++2/2p) + 1 +000 - (log(T + 2kR) + 2)2²
2
+ (x*+V20)
T
7
1
/3 3log
2x + 7 Cro (log(T + +2x2)= + 2) V2popQ v 3log 2
+ T V T /
VT
Plugging in Ao = 0, 0, = 0 and arraranggnn the terms yields:
T
T-1
Σ (R,))) - Rp(Opa)) +
Σ Ag(O.) - ( + 2n/T
1 X2
t=
0²
+ +1102
1
Σ
(1(1 + 2.) - -7))) +
V2p0 v 3 n.
T/
2T
VT
1=U
GA
1
(X* + 22/2p) + - Cpo + 2xQ) + 2)) + 2v2p)
VT
G /A/3lo0 /3l0g 2
+ Opo(log(T + 2xx) + +22
+
X.
VT
T
31

---

By our choice, 7 = Gzn. so we have
(2p(0.)) - Rp(0pe))
+ T Σ
Ag(O.) (
2n1T
t=0
G\ v 3 log 2
V20a PQ / 2
p² 1/' + +n + -10
(X v2p)
VT
G2
3 log 2
Cro(log(T + 2n²) + +2)2
+ CPo(loogT 2x²) + 2)² + V2p) +
2.
T
Define Ô7 = + Et-o Or, and then by Jensen's inequality we have
(Rp(Or) - (r((ra) ((R (0r) RQ(02) -6cq)
7
X
2
2n
S p² n/T + n16 + +n0 +
G\ v 3 log
V2po PQ
3log
(A+ v2p)+ + VT
VT
Gx 3 log 2
Cro(log(T + 2k²) + 2)² A.
+ 7 Cro(log(T +xxq) + (x* + v2p) +
T
13.2 Proof of Theorem 2
Proof. Note that Lemma 11 holds for any À 2 0. Now let's discuss by cases. If 0 is in the constraint
set, then QPQ 0r and we simply set À 0 and get the convergence:
Rp(Ôpa) Rp(0pQ)
1/T +n6 nnB G\ exy3log
3log /3/3108
V2p0 /ore///log 3log 2
(** (x+2VZ2)
VT
VT
+ T Cpq - (log(T + 2kRQ)= + 2)² (x* + V2p)
If Ör not in the constraint set, we set À RQ()2) 6EQ for notational simplicity, which yields:
7+ and define g(0) = Ro(0)
(Rp(Or) Rp((pq))+ + (g(0r))2 2(7 +
/²
G\ G 3 3
V2pa
3 3log 1
n/ Gn6 + G +
(x+2V22)
VT
VT
+ =Pp (log(T + 2 + 2)² (X- + v2p)
T
(G1/3l0p 3ogg 2 VT
+ CpQ (log(T 2x²) 2)2
g(0r)
(12)
T
Since ōr is not in the constraint set and QPQ is the projection of it onto inexact constraint set
g(f) = Ro) - Ro(0Q.)) - 6eq + co S 0, by KKT condition we know ğ(θrq) = and
0r 0pQ vo((pQ) for some > 0. Defining A (Bq(0Q,)) RQ(())), and due to
32

---

our choice of ' we know A 2 0. Then we have
g(Or) = g(Or) g(0rq)
g(Or) ((0rQ) - (0(Or) g(Or))
a(0r) )(0pQ) (Ro(0g) R2 + co)
> (vg(0 Or 0rq) - [5((0
( \| 0r 0rel -
where the inequality is due to convexity of (-). Evoking Lemma Ro()2) gives that ming(o)=o VV((p() z v ( - ED + Rl(0 RQ N
with e = 6EQ - Ro (QQ.T)
V Atin (Eq) so g(0r) 2 V Ama (EQ )rr 0T - 8PQ -A, where the second inequality is
due to that 6o S 3EQ.
On the other hand, since pp is the projection of Or onto constraint set, and ppQ is in the constraint set, know
0rrq orel
s -10r-0rr) s 2pp
Hence 0ro also falls in the set {0:110 0 8701 1| S =20² }. so the gradient upper bound Go applies
to 0rq. Hence we also know
g(Or)= g(0r)= 3((
= Ro - Ro (02) - bc (Ro(Ora) Rl( - GeQ + 6n)
< Go Or 0 || -00.
Plugging the upper and lower bound of g(rr) into 12 yields:
(V A 3EQ
0r 0ral - )
3EQ
(R((o))((((rr))) + VT
4(c,,
62
+ 2n)
p² T
+ n12 G13 + G 3log
V2pa v 3log 2
(A' a2+2V20) +
VT
VT
1 Crq (log(T + 2x²) + +2) (X* + v2p)
T
Gx 3 3 2
Opq (log(T + 2ni)) + 2)²
VT
Or - 0Pol1 Go
T
Or
G4
op
Notice the following decomposition:
Rp((T)) Rp(0pQ) (p((r)) - (pp(0p)) 2 -Co 0r - Opal
Also notice the fact (a- 1)2 > Fa²² - 13 holding for any 0,b > 0, we know
(Viinn Or 07- 1 0ral
2
0r - =rQ 2 - -2
2
2 min (EQ)3cQ
33

---

Putting pieces together yield the following inequality:
a allrr
0ro
2 - -bblōr 0pol -
- cs
where:
3VTX +
min (Eq)ce
8(c, C3 + +
Go
C'. 3 2 CpQ (log(T' + 2xq))= + 2)
+ Go.
(c + 2,1
vT
p² + Cyl (G2 + 6%) + +Gi///
/ / log 2 (x* + 2vpp) + N2pora 3 ?
VT
C. (log(T + 2ni) + 2)² (A* + 220)
A
+ VT
+
T
4lc, + mn)
2
Assume T2
Cng-(lo((1-2gg)+22
.0 b 2GoCx /
+ Go. Solving the above quadratic
G3/3lo87 &
GG, )
inequality yields:
|0r- - 6re 1
b b+ b+ /b2
+ 4ac
+
2a
8(G, + 1 Go + 16G
31og 2
oo
31 (EQ)
A
($q)cQ
2 8(c,Gg + Ci
e Cy
+GG + 0g) + Gx2 3log 2 (A*+2 + ~2porqy 3
3v T (SQ)EQ
VT
8(c,G8 Gr
OpQ (log(T + 252) + 2) (A+ + 22p)
3v T ($q)
T
16(c, G3 + cg 1) + 16G / 3log ?
A
CpQ (log(T + 2kk)) + 2)² (X* + 22))
X (
N
(Σ
2T
G + 63) + Gx log 2 (A* + 2p) + V2parq v 3log
2
where at the last step we use the fact Vab S a²462 (r(()))) Rr(()))) ( (r)) Rr((r)) R)((rq)
Finally, note the following decomposition:
2
< co 0T 0Pe fir(Or) (0r0))))
2G 3 3log 2
Go +
G0 | 0PQ -ppa
e, G2 + o
c + G3) + Giyy
3log (X+ + 2222p) + V2
31og 2
+
VT
Cro (log( + + 2kQ) + 2)² (X* + v2p)
+
T
34

---

(ogg
Since we assume 7 T27
we know
Gx A Amin (Pgkee log
R
S Go
01 -rr Ry(Or) (rr@)))
2G 3 log Go
1
Go +
|
c, 0, "
p² Dq
+ (12 + 03) + 20'
3log & +A*
+ 2V22p) + v2 3log 7/
VT
Plugging bound of |0. 0rol and Lemma 9 yields:
Rp((pp)) - Rpp(pp))
2Gx v 3 log 2
G6 J + 16G 3 2
pCpQ log (T + 2ni
2EO
Go
Go
+
Go Gg
x * (SQ)@QT
Minn (Eq)cQ
Cr
Gx Gxy log G
L Cy
+ cn (G² + G3) + Gx
log (X* + p) + pa
log
48
Go
Go
Cnp G
+ I
VT
Cn
Since we choose ED
Cpg
we know
2ep
2Cpq
T+2kg"
Vx (Se)EQ
Now simplify the above bound. By the definition of Cy we know Cy C we have
Rr(OrQ) - Rr(0rq)
2Gx, / 3lgg
[6((Go 2,16, + 16GioGi v 3log
c,
ACpolog? T
GB
Go +1
Atin (Eq))VV
(EQ)E + 2nq)
GAy1O88
L By
C, + (3)) Gg / log (X* + p) po log
+ 48
Go +
Go +1
VT
Go + 2G 22///30 bexs/3log 33og 2
16(Ga + 1) + 16G
31og
4Cpq log T (T + 2ni22)
<
+
min (ΣQ)OVT
+ ( G + (X* + p)Gx + poPO) vlog?
2 Go + Gl/
+48
VT
Again recall we choose:
T> (C
so
4CpologT
5
Gn G1g1og 1/r
Gx S Amm (Eqleq log 1/7
VA (Eq)e
vT
So have
35

---

Rp(OrQ)- Rp((pp)
32 Gu Cn
+ 16G y 3 3log 2
G2y log +
$ Go Ga+ 20' / /3000
X
(EQ))OV
VT
+ Gn G3) + v 22 v 3 3l0g 7
+ Go + +2Gg//0 3 log
VT
@xy108 log :)
Ga GGGGs (
((x" + p)Gr + porQ) V log 1 + o² c
x
Go Go+
+
A (oQ)EVT
Finally, by definition of Gy know concludes the proof:
8²
G,
d² bq
pG and d² bq 2 plovbaray /og which
Cq
( A (
[H C log
log + o
Rp(Orq) (r((r)) Go GG++Gyylog
1
+
VT
14 Proof of the Results of General Loss
In this section provide the missing proofs in Section 9 We first introduce the following lemma which establishes the convergence of auxiliary iterates fq.t to Q ERM model.
Lemma 12 (High probability convergence of fQ.1). If we choose a = 2 then with probability at least - for any t 2 we have:
RQ(0Q.) RQ(00) m1 2x
h V (2
6G3 mi + 2k)
+ 1)
t
Proof. We first examine the boundedness of |10, Define e = Ve((q, - Ve(0Q,03 va)
According to updating rule of lQ.: we have
[10q.+1 02.ool & l10g. - a, Ve(0Q,i - (f0.0 - ar Ve(0,,0 21, y,,))
a VV((0.,0 wt)1
= v |1q,, f2.00 ol 1l 2a, (e,, fq.0 02.0) + a3 ||ell
au |VVE(0 xt, we)1l
< |10,,-- - lq.oll + a, V vill
a Ve(0Q.;:
1=0
sup
1= m
1 2 (2,0)ESQ
+ log(T' + 2k)
<
sup (a.
[V((00,: x
(13)
my
where the third step is due to the co-coercivity of the gradient of the convex and smooth functions: (V vi) Ve(OQuui w1), 02.5 0q.0) >
1 m2
|V m)
Ve(OQ. 2,, w1)l
36

---

Hence we can bound || @ as
|0q - 110q.1 0q + 110..1l
1 ++ log + 2n)
sup (n
[V
m1
Hence we can compute sub-Gaussian parameter. By the definition of Go
VE(fQ vo) v R
(V S 2Gg
sup
(x.y)ESq
According to Proposition 2 we know Ve(O0,,t Ti, Me) (Ro(00.))) G7 sub-Gaussian.
Now, we evoke the result from Theorem 3.7 from [29] that the gradient noise is G% sub-Gaussian, then with choice of Otz, with probability least 1 it holds for any integer t that
(0 R2((0)) (1 2xd) 0ell 6G2 log(2/T))(og L + 1) mi + 2x)
t 2k
We further bound ||0211
|1 12 21102 - 02.002 21102
4 (Ro((Q..) RR(0g)) + 2 Q
mı
4 (Ro((QQ.))
min RQ) + 2| BER
mi
4
1
2 ( ||
+2100,0012
m.
2m
which concludes the proof.
14.1 Proof of Theorem
Proof. The proof is almost identical to that of Theorem 2 In Section 13.2 choosing Crq =
m1(1 + 2xx) m | Ro + 2110 +
603 log(2/T) and plugging in g(0) Ro(O)
mi
RQ((Q.)) 3cq + co. then have
g(Or)= = g(Or) 5(0rq)
g(rr 5(0pQ) (ō(Or) g(Or))
g(Or) ((0rg) (R2(0g) Ro((0.T) + t0)
2 (V)(0pQ); OT 0PO) - V 0
-poll -A
Let Og be such that g(0n) = 0, and then we have
min || > min V (00) - vz(0)1
5(0)
ā(0)=
2 r(3Eq) 2m1 (g(00) - g(0) = r - 2m 2m1g(00)la(0)=
r(3Eq) 2m1(Eo (RQ Ro((g)))
2 r(3Eq) 2m1c0
so g(0r) 2 (r(362) - 2m1160 11 - 8| A. Since we choose cn = Cpg and T
>
4Cpgm we r(3eg)
know r(3eg) 2m150 2 (33e0) The rest of the proof follows the same way.
37

---

14.2 Proof of Propasition!! 1
Proof. By the standard Rademacher complexity analysis (see [26 know:
log
sup
(0, - 2R, (fo H)
May
2np
DEN
Plugging in the upper bound of (f, H) from Assumption concludes the proof.
14.3 Proof of Corollary I
Proof. First, since PpQ E {0 RQ(() Ro())) I 3eq), then by Proposition | and our choice of EQ we know (Q(OpQ) & Seq with probability at least T over the randomness Sq-
Then we discuss by cases. If 8 E {0 Ro( Ro (f2) s 3ce), then since (ppppQ)
Rp)) cp. by Proposition I and our choice of ep we know with probability at least 2r over the randomness of Sp and Algorithm 3
Ep((pQ) = RR((Op)) Rp(07)
=Rp(OpQ) Rp(0pp)= + Rp(0pp)) Rp(0pQ) Rp(0pQ) (0%)
20
+ Rr(0b) Rr(()) s 3cp.
Hence (f(Q) - 8(3cp).
If 0F & (0: RQ( Rw (0()) S 3ee), then we know EQ(0)) 2 sQ with probability at least 1 over the randomness of Sq. This is because for any such that (o) I Eq. must be the set {0. RQ) - RQ(0q) - 3eq]. To see this, note that
Eq(O) S EQ(() + 2EQ s 3eq.
Hence we know
(0) < 5eQ S 5E)(07) S 55(ep). Putting piece together have with probability least 1 -37, holds that
(Q()r & 5 min feq. 8(3Er)}
38


Reviews:
[{"review_id": "VHrFRvVaOy", "reviewer": "Reviewer_vDwt", "summary": "This paper studies a class of supervised transfer learning algorithms that utilize stochastic gradient descent (SGD) to construct a regressor by minimizing the empirical risk on a source domain while constraining the empirical risk on a target domain. The authors provide a theoretical analysis of the generalization error for this approach, showing that the SGD solution converges to that of a specific hypothesis transfer learning algorithm with a well-established generalization rate. Notably, the resulting generalization error adapts between the rates achieved by training solely on the source or solely on the target data. The authors support their theoretical findings with experiments, demonstrating that their proposed algorithm achieves adaptive performance, matching the rates of either solo source or solo target training depending on the scenario.", "questions": "1. Could the authors please provide a more detailed comparison with Hanneke et al. (2024)? Specifically, I would appreciate clarification on how your theoretical framework differs from theirs, and what novel contributions your paper makes beyond their work. A clearer articulation of these distinctions would significantly strengthen my evaluation of the paper's originality and significance.\n\n2. Regarding the experimental evaluation, could the authors provide more details about the implementation of all compared methods? In particular, I noticed that the HTL method shows constant accuracy regardless of source sample size, which seems counterintuitive. Additionally, the runtime comparisons would be more convincing with implementation details to ensure fair comparison (e.g., number of iterations, optimization parameters). Addressing these concerns would improve my assessment of the paper's experimental quality.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I lean toward accepting this paper primarily due to the benefit of proposing a practical algorithm for transfer learning with rigorous theoretical error guarantees.\n\nThis paper is clearly written and addresses the relevant topic of error analysis for the SGD method in transfer learning. The theoretical and experimental contributions are well-highlighted, making the main results easily understandable. The theoretical results are supported by rigorous mathematical proofs that appear sound upon review. The clarity of the paper is generally high, with the exception of comparisons with existing work.\n\nThe paper provides error upper bounds for the mixed-sample SGD algorithm in a transfer learning setup. While the obtained error bounds match those shown by Hanneke et al. (2024), the originality of this paper lies in analyzing these bounds for the more practical mixed-sample SGD algorithm. The significance of this paper hinges on the extent of advancement beyond Hanneke et al. (2024), but unfortunately, the authors do not provide detailed comparisons with this prior work. They merely mention that Hanneke et al. (2024) focuses on classification settings, when in fact that work provides a general framework applicable to both classification and regression. Indeed, the theoretical framework of Hanneke et al. (2024) has wider applicability than this paper, and regarding error bounds, the results are equivalent. This lack of detailed comparison diminishes the clarity regarding the paper's significance.\n\nThe primary contribution may lie in providing a concrete implementation to find a predictor within the confidence set defined by Hanneke et al. (2024), effectively offering a tractable implementation of Algorithm 1 from that work. Developing such a tractable algorithm represents a significant contribution to transfer learning. However, as mentioned, the paper lacks rigorous comparisons with Hanneke et al. (2024), including clarification of the relationship between the algorithms. A more thorough comparison would substantially improve the paper.\n\nI have concerns about the experimental quality. First, the accuracies of the HTL method remain constant regardless of source sample size. The authors attribute this to HTL's difficulty in finding suitable regularization parameters through cross-validation due to limited target data. However, the relatively small error bars suggest limited impact from small sample sizes, contradicting this explanation. Without implementation details or code for HTL, I cannot verify the experimental design's adequacy. Second, runtime results are highly implementation-dependent, yet the authors provide no implementation details or code for HTL, PSGD, or their proposed methods. This raises concerns about potential unfair comparisons, such as the proposed algorithm potentially using fewer iterations than comparison algorithms. Providing implementation details would help establish the fairness of the runtime comparisons.", "was_revised": true, "final_justification": "I lean toward accepting this paper primarily because it proposes a practical algorithm for transfer learning with rigorous theoretical error guarantees. It offers significant practical benefits, particularly by reducing computational cost through the use of a first-order optimization method with adaptivity.", "rebuttal": "Thank you for your positive and insightful comments. We notice that your main concerns are the comparison with prior work, and the implementation details of the experiments. We will try to address them as follows.\n\n**Q1: Regarding performance and implementation details of HTL**\n\nIn fact, in some experiments, the performance of HTL does improve as $n_p$ increases, see, e.g., Figure 6 in the Appendix. We agree that our explanation for HTL's performance is poorly worded. Indeed, when source and target are too different, HTL is biased towards target largely so it gives similar performance as target ERM, while our method still automatically gains from the source data, and more importantly, our procedure is parameter-free---it does not require searching for a bias-parameter. For the implementation of HTL, we first use SGD to find the approximation of $\\hat\\theta_P$ as the reference model, then we perform a 5-fold cross-validation to select the best bias. Then we run SGD for $1000$ epochs to optimize the objective $\\hat R_Q(\\theta)+\\lambda ||\\theta -\\hat\\theta_P ||^2$. The same epoch number is also used for our algorithm and PSGD. \n\n**Q2: A more detailed comparison with [Hanneke and Kpotufe 2024]**\n\nWhile we achieve the same rate as in [Hanneke and Kpotufe 2024] (when specialized to regression), the constrained ERM procedure being approximated by SGD is different from the procedure proposed in [Hanneke and Kpotufe 2024] in the following respect: their procedure returns any element of the intersection of two confidence sets (so boils down to constraint satisfaction) while we consider a constrained ERM which from which it is easier to derive an SGD procedure. Our rates are of the same order, although our constants are worse. We agree with the reviewer that we should further emphasize this comparison in the work. \n\nWe will make the above two points clearer, and we again thank you for your insightful comments."}, {"review_id": "K6Aztru2Vd", "reviewer": "Reviewer_2HaD", "summary": "The paper provided an analysis of the expected error when using mixed-sample SGD algorithm in the context of supervise transfer learning. The main result is presented in Theorem 1, that provided an upper bound of the expected loss at the target distribution. More particular, it includes $\\varepsilon_Q$ (best achievable rate from $Q$ target distribution) and some quantities measure the discrepancy between source and target distributions. Other theorems (2,3) and Lemmas (1,2,3,4,5,6,7) were stated to support the proof of Theorem 1. \nIn the work, the author presented an hybrid algorithm that use both source and target data to train the model, meanwhile, the ratio between their sizes was  adjusted along the training procedure. The main reason for mixing data in the SGD is that the source-target problem has two minimization procedures at the same time, that is connected through a parameter in the Lagrangian form. The authors proposed to use mixed data with adaptive rate to deal with the situation.", "questions": "Why is there $6\\epsilon_Q$ in the constraint (2), I mean the factor $6$?\n\nDoes $\\lambda_{\\max}  (\\Sigma_p^{-1} \\Sigma_Q)$ exist?\n\nNotation $\\eta = \\frac{c_\\eta}{\\sqrt{T}}$ in Theorem 1, so $\\eta$ depends on $c_\\eta$?\n\nHow to check all conditions do not violate each other?\n\nShould have a table for all quantities to check? \n\n$\\theta_{Q,t}$ what does $t$ means here, step $t$?  equation (2)\n\nLine 46, what does $\\tilde{\\nabla}$ mean? \n\nLine 59, what does ``converge in risk\" mean? \n\nLine 142, what is $\\theta_0$?\n\nIn Theorem 2, why do we need condition $M_x \\geq 1$? Because we could be in the situation when $\\|x\\| \\leq 1$.\n\nTheorem 1 includes $\\epsilon_Q, \\epsilon_P$ but no  definition for those terms. When I track back line 72, some words describe them, still no mathematical definition. \n\nWhat is the limit of $\\lambda_t$ as $t\\rightarrow \\infty$?", "limitations": "Yes\n\nI would like to reject the paper since the poor presentation of its mathematics and the results seem to be not technically novel and challenging to prove. However, I am not familiar with the previous theoretical works in this domain. Hence, I reserve the decision when more things will be clear.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. I think the work is concrete, when results are stated, algorithm was derived, the motivation is well-stated.\n2. The flow of the proofs is clear, in which the order and link between steps were explained.\n\nWeaknesses:\n\n1. The linear regression setting is too simple. Two distributions are differed only by their covariance matrices. \n2. Poor presentation of mathematical results. It seems to me that the author assumed that readers know the problem in advance. I have a list of questions below. \n3. I am not certain that the proof is novel. The main idea is common technique in analysis and probability, consider a quantities in its local neighborhood and for others outside the neighborhood bounding it by using other properties.\n4. I am not certain that the upper  bound is Theorem 1 is optimal? The RHS of the inequality in Theorem 1 has two terms: one with respect to target distribution, other measures the discrepancy between source and target distribution. This is not surprising, since the estimator comes from mixed data. \n5. Experiments were carried out on small datasets, synthetic data and school data with very small sample sizes.  It seems to me that the authors consider it is a theoretical work. Meanwhile, the more important thing is if the proposed algorithm actually works/ outperforms other methods in various settings and deployed to help solving problems.", "was_revised": true, "final_justification": "I keep my score unchanged  due to the poor presentation and limited experiments.", "rebuttal": "The reviewer has questions about technical novelty, but this is perhaps due to a lack of familiarity with analyses on the subject matter. \n\nWe re-emphasize that the main novelty of the work is in deriving a provably efficient SGD procedure that manages to recover optimal statistical rates of transfer, which is very much not trivial. The main difficulties are outlined in between Line 60 and 71 in the Introduction, which the reviewer perhaps missed. We are happy to expand on this further if the reviewer has more specific questions. \n\n**Q1: The linear regression setting is too simple and two distributions differ only by their covariance matrices.**\n\nThe reviewer seems to have missed many important points:\n\n--- As stated repeatedly, our results apply beyond linear regression, to general convex settings (see Theorem 4 in Appendix 8), and we chose to focus on linear regression in the main body for clarity of exposition.\n\n--- In the linear regression case, **we do not restrict to changes in covariance**: we very specifically allow for changes in regression functions, as displayed in our statistical results and explained on page 5. What's surprising indeed is that the procedure can adapt to all unknown such changes, including changes in regression functions. \n\n**Q2: Optimality of Theorem 1**\n\nYes Theorem 1 is the optimal rate for transfer learning in linear regression setting. The matching lower bound is given in the recent arXiv paper [Hanneke and Kpotufe 2024, Theorem 3].\n\n**Q3: More Experiments on the large-scale dataset**\n\n\nWe agree with you that the paper would benefit from evaluations on larger datasets. \nWe have additional results on a slightly larger dataset (see experiment on Berkeley Yearbook Dataset, in Appendix 9.1, where $n_P$ ranges from $500$ to $1300$). We will add more results on the Malware-iot dataset (a large-scale malicious network traffic detection dataset) in the revised version. \n\n\n We however would like to emphasize that the focus of this work is primarily theoretical (i.e., show the feasibility of an SGD with optimal STL guarantees), and our focus in these first experiments was to show the practical promise of these insights.\n\n\n\n**Q4: Technical questions**\n\n4.1 Why is there a factor of $6$ in Eq. 2?\n\nWe choose the factor $6$ for proof convenience. We require our constraint set to have two properties (Lemma 5) :(1)  any $\\theta$ in the constraint set will have a small Q risk, and (ii) any $\\theta$ that has a\n small Q risk is covered by our constraint set with high probability. To ensure these properties\nwe require the factor to be $6$. Please check the proof of Lemma 5 for more details.\n\n4.2 Does $\\lambda_{\\max}(\\Sigma_P^{-1}\\Sigma_Q)$ exist?\n\nYes $\\lambda_{\\max}(\\Sigma_P^{-1}\\Sigma_Q)$ always exists. The reason is that  $ \\Sigma_P^{-1}\\Sigma_Q$ and $ \\Sigma_P^{-1/2}\\Sigma_Q\\Sigma_P^{-1/2}$ share the same eigenvalues, and $\\Sigma_P^{-1/2}\\Sigma_Q\\Sigma_P^{-1/2}$ is a symmetric matrix so all these eigenvalues are real. Hence $\\lambda_{\\max}(\\Sigma_P^{-1}\\Sigma_Q)$ always exists.\n\n4.3 Does $\\eta$ depend on $c_\\eta$?\n\nYes $\\eta = \\frac{c_\\eta}{\\sqrt{T}}$ and $c_\\eta$ is a factor that hides the dependence of the learning rate on the parameters $\\hat G_\\theta, \\hat G_\\lambda, \\lambda^*$ and $\\rho$.\n\n\n4.4 How to check all conditions do not violate each other?\n\nWe are not sure which conditions you refer to. If you refer to the two conditions for $\\hat\\sigma$ and $c_\\eta$ in Theorem 2, they can hold simultaneously, since the condition of $\\hat\\sigma$ does not depend on $c_\\eta$.\n\n4.5 What is the meaning of $t$ in $\\theta_{Q,t}$ in Eq. 2?\n\n$t$ denotes $t$th iteration. $\\theta_{Q,t}$ are the iterates we maintained to approximate $\\hat\\theta_{Q}$ during algorithm proceeding, since we do not have $\\hat{\\theta}_{Q}$ in hand.\n\n4.6 What is $\\tilde{\\nabla}$?\n\nIt denotes the stochastic gradient operator.\n\n4.7 What does 'converge in risk' mean?\n\nIt means $\\hat R_P(\\hat\\theta_{PQ}) \\mapsto \\hat R_P(\\tilde\\theta_{PQ})$ as the total number of iterations goes to infinity.\n\n4.8 What is $\\theta_0$?\n\nIt is the initialization of the algorithm.\n\n4.9 In Theorem 2 why do we need $M_x \\geq 1$?\n\nWe assume this only for simplifying the bound. It can be removed without affecting our main result.\n\n4.10 No definitions for $\\epsilon_P$ and $\\epsilon_Q$.\n\nWe defined these quantities. Please see Line 148. \n\n4.11 What is the limit of $\\lambda_t$?\n\n$\\lambda_t$ may not have a limit, since in convex-concave minimax problem, the last iterate could diverge under gradient descent and ascent dynamics, but the average of the iterates, $\\frac{1}{T}\\sum_{t=1}^T \\lambda_t$ converges to the saddle point $\\lambda^\\star$, when $T$ goes to infinity."}, {"review_id": "Voc29e0W4n", "reviewer": "Reviewer_7uqy", "summary": "The paper proposes mixed-sample sgd which adaptively alternates between sampling from the source and target datasets at a rate that automatically adjusts based on the source data's quality. This approach avoids computationally expensive tuning the source data's importance weight while tracking a sequence of constrained convex programs to maintain strong theoretical guarantees. The authors prove that their method converges at a rate of $1/\\sqrt{T}$ to a solution that automatically performs as well as a model trained on either the source or target data alone, whichever is better.", "questions": "Why is $\\hat{\\theta}_Q$ unknown? Since we're performing linear regression with finite samples, I would expect a closed-form solution to be available.", "limitations": "please see the weaknesses.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Disclaimer: I am not expert in optimization so most of my reviews are educated guess. If there are something wrong, please correct me. \n\n## Strengths\n- The paper provides rigorous proof for the proposed algorithm's convergence at a standard $O(1/\\sqrt{T})$ rate and, more importantly, its adaptivity. \n\n- The paper is logically structured and does an excellent job in the introduction of motivating the problem, highlighting a clear gap in the existing literature. \n\n- The paper tackles the core, practical challenge of safely and efficiently leveraging source data in transfer learning. \n\n- The proposed Mixed-Sample SGD algorithm is original. Its mechanism of using a dynamic, learnable sampling rate to approximate a constrained optimization problem is a new approach compared to prior methods that rely on expensive cross-validation or direct projections.\n\n## Weaknesses\n\n\n\n\n- The formal guarantees are derived for convex loss functions. This is a significant limitation, as it doesn't cover the non-convex nature of modern deep learning models. The authors acknowledge this, but the gap between the convex theory and some of the deep-learning-based experiments remains.\n\n- The detailed proofs contain minor  but recurring errors in the calculation of constants, particularly regarding factors of 2 and 4 when bounding gradient norms. Since empirical risk is  $\\frac{1}{n} \\sum_{ (x_i, y_i) \\in S_Q} (\\theta^\\top x_i - y_i)^2$, \nthe gradient should be \n$$\\nabla\\hat{R}_Q(\\theta) = 2\\hat{\\Sigma}_Q(\\theta-\\hat{\\theta}_Q)$$  \n\nin lemma 8. Thus, the minimum gradient norm should be $4\\epsilon \\lambda^{+}_{\\min}(\\hat{\\Sigma}_Q)$. Similarly, the factor of 2 is omitted in line 582.\n\n- A minor typo: unversal -> universal in line 148.", "was_revised": true, "final_justification": "During the rebuttal, the authors addressed other reviewers' concerns. I don't have any remaining concerns either. So I keep my score as 5.", "rebuttal": "Thank you for your time and positive comments. We will try to address your questions as follows.\n\n**Q1: The results are restricted to convex loss** \n\nFor nonconvex risk functions, it might be intractable in terms of convergence, but the statistical guarantee for the solution of the proposed QCQP will still hold.\n\n**Q2: Why not using a closed form solution of $\\hat\\theta_Q$**\n\n First, we wanted to present a procedure that applies beyond linear regression where a closed form solution may not exist. \n\nIn the case of linear regression, you are right that a closed form solution may be plugged in, but our goal is *to account for all computation*: in large dimension settings, the closed form solution requires iterative power methods to approximate which may cost $O(d^3)$ in the worst case; instead we approximate the closed-form solution in parallel and account for all computation in our results. As such, we never need to compute it exactly, especially as the algorithm may end up preferring to rely on the source when it's most informative. \nWe also apologize for the typos and will fix them. Thanks for catching them."}, {"review_id": "0qRTzEDlVM", "reviewer": "Reviewer_cNej", "summary": "This paper provides a theoretical analysis of the supervised transfer learning settings between the source and target distributions of a linear regression model. This paper shows that the returned solution is extrapolated between the source and target datasets, leaning towards the beneficial one, under the mixed-sample SGD setting. Experiments confirm the theoretical analysis", "questions": "Please see the weaknesses", "limitations": "Please see the weaknesses.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "This paper has several strengths:\n- A new theoretical result on the transfer learning setting with a linear regression (classification) model.\n- Experiments confirm theoretical results.\n\n\nWeaknesses:\n- This paper considers a simple setting where the source and target datasets share the same domain $\\mathcal{X}$ and $\\mathcal{Y}$. This setting is too strict and less applicable in practice since the transfer learning is often done between domains or datasets with the same input domain but have different labels.\n\n- The \"usefulness\" of the source dataset is indicated by the sample size, which is not always the case. In my opinion, it is chosen since this paper only focuses on the source and target datasets from the same domain for both input and output. \n\n- The presentation of this paper causes confusion, and it is not ready to appear at this venue. I recommend that authors carefully revise the manuscript to make it more readable.  For instance, Section 4.1. provides a series of lemmas and starting with an algorithm for warming up, the motivation behind the warm-up algorithm should be discussed, and the interpretation of lemmas should be also discussed carefully to understand why it is important. In addition, the importance of $\\rho$, the norm between the initial and the calculated point, should be discussed. \n\n- What is the motivation behind the use of mixed SGD?\n\n- The related works should be discussed further why this work is important in the literature instead of listing lines of works.", "was_revised": true, "final_justification": "This paper gives a theoretical understanding of the optimisation procedure to balance the contribution of source and target during training. Despite several interesting results, the original setting of this work departs from the practical setup, which limits the contribution of this work.", "rebuttal": "The reviewer has a question about the setting, which might be due to a lack of familiarity with the literature of theoretical transfer learning. \n\nWe argue that assuming input and label spaces are shared across source and target distributions is very **standard** in the theoretical transfer learning papers. See seminal works [Mansour et al 2009] [Ben-David et al 2010] [Zhang et al 2019]. However, we agree with the reviewer that modern ML also has the scenarios where source and target share different label spaces, but that is a completely different setup to this paper. In those settings, people consider different model architectures, e.g., source and target share the same representation layers but with different output heads. This is beyond the scope of this paper.\n\n[Mansour et al 2009] Mansour, Yishay, Mehryar Mohri, and Afshin Rostamizadeh. \"Domain adaptation: Learning bounds and algorithms.\" arXiv preprint arXiv:0902.3430 (2009).\n\n\n[Ben-David et al 2010] Ben-David, Shai, et al. \"A theory of learning from different domains.\" Machine learning 79.1 (2010): 151-175.\n\n[Zhang et al 2019] Zhang, Yuchen, et al. \"Bridging theory and algorithm for domain adaptation.\" International conference on machine learning. PMLR, 2019.\n\n**Q1: The \"usefulness\" of the source dataset is indicated by the sample size, which is not always the case.**\n\nWe respectfully disagree with your opinion that the usefulness of source data is measured solely by the sample size. The quality of source data is also measured by how close the two distributions are, indicated by $\\lambda_{\\max} (\\Sigma_P^{-1} \\Sigma_Q)$ and $\\mathcal{E}_Q(\\theta^*_P)$, which are also reflected by our main Theorem.  \n\n**Q2: The interpretations of the Lemmas in Section 4.1.**\n\nSince the stepsize choice depends on a bunch of quantities: upper bound of initial distance to optimal model ($\\rho$), gradient upper bound ($\\hat G_\\theta$ and $\\hat G_\\lambda$), and upper bound ($\\lambda^\\star$) (please see the conditions in Theorem 2), it is necessary to provide approaches to estimate them from the data, which are given by Lemma 1 to 4. In Lemma 1 and 4, we can see that the upper bound of $\\rho$ and $\\lambda^\\star$ depends on $\\hat \\theta_Q$, so we use a warm-up algorithm to approximate it. We will make the purpose of that section clearer.\n\n\n**Q3: The motivation behind the use of mixed SGD?**\n\nThe proposal of the algorithm is motivated by the following fact: a desired *adaptive* optimization algorithm for transfer learning should automatically detect whether the source data or the target data are more useful and sample the data from them accordingly. The probability of sampling from source or target should also be adjusted adaptively, based on the performance of current model on the target data. Our algorithm, inspired by the Lagrangian objective, exactly works in this way.\n\n**Q4: The related works should be discussed further why this work is important in the literature instead of listing lines of works.**\n\nWe discussed the importance of our work compared to prior work multiple times in the Introduction. In a nutshell, the previous works in transfer learning mainly focus on the statistical aspect of this problem, while none of them gives a concrete optimization procedure, that can achieve optimal statistical guarantee. Our work fills this blank."}]

Author rebuttal:

Meta-review: This paper analyzes the mixed-sample SGD scenario for supervised transfer learning. The setting considers alternating between source and target data during sampling, without requiring prior knowledge of source data quality. The authors propose an adaptive sampling algorithm that maintains statistical transfer guarantees, allowing the method to benefit from informative sources while avoiding negative transfer.

The reviewers generally appreciate the significance of the main contribution: the proposed algorithm is backed by rigorous theoretical analysis while remaining practical enough for real-world transfer learning scenarios. While there were shared concerns regarding the practicality of the experimental setup, I believe the theoretical contribution outweighs these limitations.

Therefore, I recommend acceptance.
Decision: Accept (poster)