Mixture Weight Estimation and Model Prediction in Multi-source Multi-target Domain Adaptation
Authors: Yuyang Deng
Ilja Kuzborskij
Mehrdad Mahdavi
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-source domain adaptation; minimax optimization; learning theory

Abstract: We consider a problem of learning a model from multiple sources with the goal to perform
well on a new target distribution.  Such problem arises in
learning with data collected from multiple sources (e.g. crowdsourcing) or
learning in distributed systems, where the data can be highly heterogeneous. The
goal of learner is to mix these data sources in a target-distribution aware way and
simultaneously minimize the empirical risk on the mixed source.  The literature has made some tangible advancements in establishing
theory of learning on mixture domain.  However, there are still two unsolved problems. Firstly, how to estimate the optimal mixture of sources, given a target domain; Secondly, when there are numerous target domains, we have to solve empirical risk minimization for each target on possibly unique mixed source data , which is computationally expensive. In this paper we address both problems efficiently and with guarantees.
We cast the first problem, mixture weight estimation as convex-nonconcave compositional minimax, and propose an efficient stochastic
algorithm with provable stationarity guarantees.
Next, for the second problem, we identify that for certain regime,
solving ERM for each target domain individually can be avoided, and instead parameters for a target optimal
model can be viewed as a non-linear function on
a space of the mixture coefficients.
To this end, we show that in offline setting, a GD-trained overparameterized neural network can provably learn such function.
Finally, we also consider an online setting and propose an label efficient online algorithm, which predicts parameters for new models given arbitrary sequence of mixing coefficients, while enjoying optimal regret.

Mixture Weight Estimation and Model Prediction in Multi-source Multi-target Domain Adaptation
Yuyang Deng Pennsylvania State University yzd820psu. edu
Ilja Kuzborskij Google DeepMind iljak@google. com
Mehrdad Mahdavi Pennsylvania State University mzm6160psu. edu
Abstract
We consider the problem of learning model from multiple heterogeneous sources with the goal of performing well on new target distribution. The goal of learner is mix these data sources in a target-distribution aware way and simultancously minimize the empirical risk on the mixed source. The literature has made some tangible advancements in establishing theory of learning on mixture domain. How- ever, there are still two unsolved problems. Firstly, how to estimate the optimal mixture of sources, given target domain; Secondly, when there are numerous target domains, how to solve empirical risk minimization (ERM) for each target using possibly unique mixture of data sources in a computationally efficient manner. In this paper we address both problems efficiently and with guarantees. We cast the first problem, mixture weight estimation, as convex-noneoncave compositional minimax problem, and propose stationarity guarantees, Next, for the second problem, we identify that for certain regimes, solving ERM for each target domain individually can be avoided, and instead parameters for a target optimal model can be viewed as a non-linear fune- tion space of the mixture coefficients. Building upon this, show that in the offline setting, a GD-trained overparameterized neural network can provably learn such function to predict the model of target domain instead of solving designated ERM problem. Finally, we also consider an online setting and propose label efficient online algorithm, which predicts parameters for new targets given an arbitrary sequence of mixing coefficients, while enjoying regret guarantees.
efficient stochastic algorithm with provable
Introduction
With a rapidly increasing amount of decentralized data, multiple source domain adaptation has been important learning scheme in modern machine learning, e.g., in learning with data collected from multiple sources (e.g. crowdsourcing) or learning in distributed systems where the data can be highly heterogencous such federated learning. In this learning scenario, given an input space X' and output space V, we assume access to N sources of data, each with its own underlying distributions Dj.j E [N] over X' x y. Then, given i.i.d. training samples Di,..., DN. and hypothesis space H, our goal is to learn a model on combination these sources, for instance through the Empirical Risk Minimization (ERM) procedure h = arg min Σ C (h), where LB (h) is the
empirical loss of model h E 7. over data samples in Dy, and a E A is some mixing parameter, such that predictor ha entails good generalization performance on a target domain characterized by a distribution T, i.e., yielding a small true risk LT = f ((), yy) dx(x y). It is natural to measure the quality of lo in terms of the excess risk namely, the difference between the risk of optimal model for target domain hī arg minkeH LT and that achieved by A... Clearly, the performance of Ti will be influenced by several factors, such as choice of mixing coefficients
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

a' to aggregate the empirical losses, capacity of H. and discrepancy between target and source data distributions. So. in order to design a good procedure for learning ha we need to understand aforementioned trade-offs. Over the years the literature on the multiple source learning has dedicated considerable attention to this problem [25, 5, 35, 17, 12]. To this end, we consider the following bound on the excess risk of ha:
Theorem 1 (Multi-souree learning bound [17]). Given N source data distributions Di...., DN and a target data distribution T, let ha = arg mingen Σ a (h) be the ERM solution with fixed mixture weights E AN Theen for any 0, with probability at least 1 -e it holds that
a²(1) mj
(T C(H, + sup NEW
Σ f C
L. (1)1
V
where C is some constant, the complexity term is C(H, a) := =) ,H) with Ry (H) being the Rademacher complexity of H. w.r.t. data source j. and my is the number of samples from source j.
The above bound indicates that, the generalization ability of a model learnt by ERM combined sources, depends on the a--eiigttd sum of target-source discrepancies, and the number of samples drawn from each source. To entail a good generalization on target domain, it naturally motivates us to minimize right hand side of the bound over a E A to get good mixture parameter. In this paper we can cast this idea as solving the following minimax optimization problem:
N a²(i) E j=1 m,
Σ j=1 - - DEAN NER
min max
(1)
where we drop the complexity term as it becomes identical for all sources by fixing the hypothesis space H and bounding it with computable distribution-indepeneeni quantity such as VC dimen- sion [31], or it can be controlled by choice of H. or through data-dependent regularization. [17] gave simple algorithm to minimize the bound of theorem for binary classifiers and 0-1 loss, however their algorithm does not extend to more general setting. [24] also looked at minimization of similar bound with the goal to find weights for an optimal mixture, but they did not give a practical algorithm, nor provable convergence guarantee. However, none of these works aimed to solve (1) because of its complex structure, and so an efficient algorithm for solving (1) so far has not been proposed. In particular, the first difficulty with (1) is that it is a convex- nonconcve objective, which means all minimax algorithms that require inner concavity [23, 22, 27, 28] or PL-condition [30] will fail to converge to a stationary point. However, recently the literature on optimization of this type of objectives has recently made a tangible progress: The first provable
algorithm was proposed by [34], where they consider alternating gradient descent ascent algorithm. Their algorithm is deterministic, but in practice, we favor a stochastic gradient method. The second difficulty in solving (1) is its compositional structure, which means that simply replacing gradi- ent with stochastic gradient in [34] will not retain convergence guarantees. To tackle these two difficulties, propose stochastic corrected gradient descent ascent algorithm, with provable convergence guarantee for solving (1). Our method can be viewed as a variant of the Stochastic Gradient Descent- (SGDA) algorithm, and moreover here we give a positive answer to the question posed by [34], on whether an algorithm performing simultaneous updates can optimize convex-nonconcave problem?, which could be interesting by its own right.
The discussion above concerns learning with one target domain, but in practice, a more common scenario is that we have multiple target domains to adapt to. For example, in federated learning [26], millions of users might wish to learn a good model from multiple sources, which can have good performance their own data distribution. Hence, we propose to study Multi-source Multi-targer Domain Adaptation scenario DM2 Here we assume that we have M target domains, each of them characterized by its own distribution T, i E [M] over X' x Y. Adapting to M different target domains requires different mixture weights aI...., ars either obtained by solving (1), or supplied by the user. Equipped with mixing parameters, next we have solve M weighted ERM problems to tailor solutions for each target domain Te, that is
h = arg min
a,(i)C (h). i [M].
KEH
j=1
2

---

Notice that these M ERM objectives share the same component functions, so we name this problem as a co-component empirical risk minimization. straightforward and naive approach is to solve all M weighted ERMs individually which becomes computationally inefficient when dealing with a large number of data sources. Nevertheless, given the benign structure of these M ERM problems, we may inquire whether there is a computationally efficient method for discovering all solutions without the necessity of solving each one individually.
We give an affirmative answer to this question by replacing the learning of the target model by predicting the target model and propose two efficient strategies to learn such predictors (for instance, a neural network). Our algorithm designs are based on the following observation: if we assume that each empirical risk c (h) is strongly convex and smooth in parameters of hypothesis h, then the optimal parameters are given by a Lipschitz finschitt of mixture weights a. More formally, denoting w' (a) as optimal parameters of hypothesis h for o--eighted ERM, w (ax) is Lipschitz in a. This means that we can learn function (.). with, say, a neural network and gradient descent, with provably small generalization error. Moreover, analysis of generalization error allows to understand when such target model prediction is more efficient than direct learning. In particular, we look at such a phase fransition of efficiency, and conclude that when the number of targets M is much larger than number of sources N, i.. M > (((L/e))//2) learning to predict solution is more efficient than optimizing to solve all M ERMs. When M is relatively smaller, optimizing to solve ERMs is more efficient than learning to predict.
Finally, as a second learning scenario we consider an online learning setting, where mixture weights 011, .... Or are arriving sequentially, and may not even originate from the same distribution. We cast this problem as an online conparametrri regression problem with inexact labels and propose an label-efficient online algorithm to predict models.
Our contributions
The main contributions of this paper is summerized as follows:
We study the multi- souri- domain adaptation problem where there are multiple source domains and we wish to learn new model given the mixture of source domains, that can perform well on a given target domain. We build upon existing learning-the theoretic results on multi-source domain adaptation and design new algorithm for weighing of source domains, that casts this problem as a a problem. In section 2 we give the first stochastic optimization algorithm for this problem which provably converges to a stationary point. The proposed algorithm is the first provably convergent algorithm for stochastic compositional
minimax optimization
minimax problem.
We further consider the above adaptation problem with multiple target domains, the Multi- source Multi-target Domain Adaptation DM* We observe that these multiple adaptation might share common structure, which allows to avoid solving adaptation problem for each target domain individually, and instead we can replace it by direct prediction of parameters for new problem. We consider offline and online settings for prediction of target parameters, and propose computationally efficient algorithms for both. For the offline setting, in section 3.1 we propose to use two-layer neural network learn optimal parameters w (ax) using bilevel gradient descent. We show that our algorithm can achieve
On лंल excess risk. We also identify the regime where our learning based approach is more efficient compared to directly solving each target problem individually.
Finally, in section 3.2 we focus on scenario where target problems arrive sequentially (and could be dependent) and extend our study of direct target parameter prediction to the online setting. We propose a label-efficient algorithm which enjoys O(n rixx average regret.
Notation We introduce some basic definitions and notation that will be used throughout the paper. Let (r) be the ball in g-metric centered at the origin and of radius r > 0, and let (d-1(r))
(x E Rd |||||2 r} C R be the f2-norm unit sphere centered at the origin, and finally let
gd = go (1). In addition, the probability simplex is defined as A = {a E [0, 1 ||a|| 1}. Concatenation of vectors is denoted by parentheses, that is (W1,...,
vector norm || is understood as Euclidean norm, while ||x| w.) wm) = [w] T...,,, w m A max; |as]- For a matrix M.
|| denotes its spectral norm while ||M][ is its Frobenius norm. For some f 8d-1 + R
the empirical semi-norm is defined as f =(f(xx)² +... + )2).))) and is always taken
3

---

w.r.t. the training sample S. In addition, for - - R. we define an empirical inner product
(f = (g()))(()))) +...+ f(x,)9(X, )) At the same time, Il 1| II (
2 Mixture Weights Estimation via Convex-nonconcave Minimax Optimization
In this section focus on single target domain and present an Algorithm designed to solve minimax problem (1) to estimate the mixture weights. We assume that hypothesis h is parameterized by vector space {w E W ] and use fy(w) L (h) to denote the empirical risk over data source j. Similarly we define f*(w) = (h)). We do the following standard relaxations. First, for relax the square root the quadratic term w.r.t. a. Second, since the absolute value function is non-smooth, we shall use the smooth approximation function & to replace it, e.g.. g(x) = vz + c where e is some small number (here g(-) is smooth approximation of (). These relaxations lead to solving the following compositional convex-nonconen minimax optimization problem:
the sake of simplicity in computation,
min max F(a. w) = E N AEAN WEW
( Ca Max
(2)
where M diag m. :....
We are interested in developing a stochastic optimization algorithm to solve (2). a crrongly-conve--oeee nonnee--onconcwe minimax problem, and it is one of most difficult type
of minimax problem due to the absence of inner concavity. To the best of our knowledge, only Xu et
Algorithm 1: Mixture Weight Estimation
Input: Target domain T, Source domains DD Di.-.. DN. Initialization variable w w-1 2
2 :...... N Positive syper-parameters (B, B, n,7)) (see theorem 2). for f 0, ..... T 1 do
Sample minibatch Et of size B from target domain T, and ,i...., from source domains D...... DN
2) = (1 5*) (z) + ff(w
fs(w:: E5) (f7
(-" (E7) fs :
+fg (1"; (4)) - (5";
Compute gradient for w: Bw = Σラ 0 Vg( + ) (+) v.f(w()())
w = =P (w" + +78()
Make vector E RN, whose jth coordinate is 9(z)).
Compute gradient for a: g'
2CMa'.
a PAN (a* 7g()
al. [34] proposed deterministic algorithm to solve it, but it is still unknown whether a stochastic algorithm can solve it with provable guarantee. We give an affirmative answer to this question, by
proposing an algorithm built on celebrated stochastic gradient descent ascent [23]. In addition to nonconcavity nature of 2, another difficulty that arises from the compositional structure of objective that we cannot simply compute stochastic gradients, namely (with E|.] = IE[- dataa)::
Elg' (w: - f3 (w: (w::)) V. E,)] # g'(/(w)) (,(w)) (w) - V (w)),
where Eı, Ei, are independent random elements in sample space X y that capture stochasticity of the algorithm. To alleviate this issue, we borrow 'the stochastic corrected gradient' idea from [7], and maintain an auxiliary variable by introducing
2) (1 38) (zf (2f ff (4) f/( (f+(w'
E()))
+ + (rp00-/((w"::: (5(
In words, for each source j. we maintain a variable 2² serving as a correction term, to ensure that 2/ is getting closer to inner function component fw(") - fz(w"). Relying on the auxiliary variable, we then have gradient estimates
g Σ ((Vo((=)VV99 (f,(w":;))
g' = [g((2)),... g(= 20Ma'.

---

Then, denoting the projection operator onto convex set C by Pe(-), the update rule becomes
w Pw (w' + +rg"))
a PAN (a' 7g4
2.1 Convergence Analysis
In this section we are going to present the convergence guarantee for Algorithm We make the following standard assumption objective in (2).
Assumption 1. We make the following assumptions on g and f:
1. g(2) is Gg Lipschitz and Lg smooth. f)(w:) is Gy Lipschitz and Ly smooth, Vw
W.j E [
2. E [ V. (w)]l S d², VWW.
3. max wew F(a. w) S F Fmaa= max ((f+(w) fj()) & By. Vj [N].
Points I and of Assumption are standard in the literature compositional optimization [7]. Point 3 guarantees boundedness objective value, which can ensured since we are working in bounded parameter domain. Assumption also implies the following property of F.
Proposition 1. Under Assumption I, F(,, w) is L max { {4G7 g., mmin
2C
smooth, and
14
strongly convex in a.
Mauax
Next, we consider the following convergence measure:
Definition (Convergence Measure [34]). Given parameters, and w, define the following quantity as a stationary gap
VG(a, ( (a - PAN (a - aaF, w))) (w Pw (w +
Given the nonconcave nature of (2), we only able to show the convergence stationary point. Definition measures the stationarity given parameter pair (ar, w) by examining how much parameter will change if we run one step projected gradient descent-ascent on them. Alternatively, one could consider the widely employed primal function [23] as a convergence measure, (() with (a)) max F(a, w), but it is ill-suited to express stationarity since F(o,.)) .) is non-concave.
One of our main results, proved in appendix establishes the convergence rate of Algorithm 1: Theorem 2. Consider Assumption and let L. and μ be defined in Proposition 1. Then, letting G.
B θ mmxx]
No²
xLa² c
}). B 0.1, 17 (#z). 7 @ (NGGoII)). the Algorithm I
guarantees that
1
E MIVGGa'',''l
T
with the gradient complexity bounded by:
KLF Fax
KLo²
G2No² 2
2² 11
max
To the best of our knowledge, this is the first convergence proof for stochastic algorithm on solving problem. We achieve O(c-a) gradient complexity required to reach an stationary point. In contrast to the most relevant result of [34], they show the rate O(c-2) for deterministic Alternating Gradient Projection (AGP) in a strongyy-convex- -oney---oovee-nococccaa nonconcave setting. Note that our result also positively answers the question posed by [34], on whether some algorithm performing simultaneous instead of alternative updates can optimize strongly-comee--noccneee minimax problem. Finally, compared O(e-1) rate of SGDA given a noncoonex--troonlyycommam problem [23], need roughly same stochastic gradient evaluations.

---

3 Multiple Target Domains: Learning to Solve Co-component ERM
Up till now, the main focus was on the problem of learning good mixture parameters given a single tar- get domain. Now we turn to a more general setting where we have M target domains, each associated with a different data distribution which necessitates per target mixture weights a1..... avs either obtained by our algorithm, or provided by the user to guarantee good generalization on individual domains. Next, to get personalized models for these M domains, we have to solve M different ERM problems based on these mixture weights:
N min far (w) Σソ= (1)) WEW
N -,= an (n)f
min fas (w) WEW
naive way is to solve each of them, which will result in a computational complexity of M multiplied by the cost required to minimize each individual fa, to a desired precision. We note that such a solution does not exploit the benign structure of these ERM problems: they share the same component functions ( and the only difference is in the mixture weights. It naturally motivates us to ask, can we propose an efficient algorithm which avoids solving all these M co-component ERM problems from scratch? Consider the solution of minwew fa(w) == a(j) (w) as a function of a,
N Σ
w (x) == arg min WEW
1=1 (()
Fortunately, if we assume that each source empirical risk f, is strongly convex and L, smooth in model parameters, we have the following Lipschitz property (shown in appendix B.1):
Lemma 1. If each f is 2 strongly convex and Ls smooth, then w-))) is x* /NG,/uf Lipschitz.
Some basic algebra shows that in the above example w w*(a) (ax) is indeed Lipschitz in a with respect to (2 metric. The Lipschitz property allows to learn w' efficiently. In partieular, learning arbitrary Lipschitz (and bounded) vector- valued function w' RNN - IR is an instance of well-studied nonparametric regression problem [1]]. In the following we will consider algorithms for learning w" in both offline and online setting and which are provably capable of estimating w at an almost optimal rate. In offline setting, we assume that we have access to a subset of M mixture weights, say ..,,... Ca. and we shall use a two layer neural network (-)-) to learn (-). Our algorithm is GD based empirical risk minimization with adaptive label refining.
nutshell, given an a, since we do not have access to w" (ax). we will use gradient descent to jointly solve weighted ERM with a to get an approximation of w" (ax as well as optimizing neural network parameters. With a mild distributional assumption on a. we show that our algorithm guarantees that the two layer network learns w (a), that is, it achieves small excess risk Ex (h)((a) w wa))]]?
In online setting, we assume that we observe an arbitrary sequence 01 Or,, on a simplex, and we wish to predict parameters close to w wa(a)), w" (a22..... As baseline algorithm we will consider a well-known online nonparametric regression that greedily covers the simplex with local online learners and which enjoys almost-optimal regret [13]. However, in the considered online protocol, the algorithm will need access to labels, and revealing each label requires to solve (3) to some desired accuracy. Here we explore possibility that in practice we might be satisfied with e-average regret, while saving the labelling cost. To this end we propose a modification of the algorithm that randomly skips some labels, while incurring a slightly larger regret.
3.1 Offline Setting: Learning Lipschitz function with ReLU Neural Network
In this section we consider offline learning of w* The Lipschitzness guarantees that the (a()) function can be efficiently learnt on finite as, and generalizable to unseen a. Hence, we propose to use a vector-valued two layer ReLU neural network he to learn w² wa(a).
We consider two layer vector-valued neural network he R + Rd. hx(x) [a] (U'x) ().,))....,, a..aaa[UU4 (U*x)+], where parameters of the hidden layer are matrices U E R collectively captured by the parameter vector O = (rcc(UU).....eeell v)) E RdmN Here a, E (m1/ are parameters of the outpui layer. In the following the hidden layer is tuned by Algorithm 2, while parameters of the output layer are fixed throughout training. We assume that at initialization, for each Us, the first half of its rows are drawn i.i.d. from isotropic standard Gaussian and the remaining half is identical to the first half. Similarly, for each a, half of the entries are set

---

Algorithm 2: Learning w" function by neural network
Input: Number of global iteration T, Number of Iteration for inner problem R. for 1 = 1....?" doo
0 = 0¹ VV ho: (aa) (as) w!)
b Neural network parameter update
for i = n do
w [+1 GD(w Cx; K)
Label refining by K-step gradient descent
Algorithm 3: GV, a, K)
Initialize v =
for t 0.... K do
vlt1 = Pw (v'- y --
Output: v.K
to -o/1/ m and the rest to 1/ //mm (we assume that m is even). This initialization ensures that each output coordinate is and so the empirical risk is bounded by constant initialization.
We assume that we observe mixture weights 01...., On E A N i.i.d. according to some underlying distribution 4. Such mixture weights can be obtained by Algorithm 1 and their independence means that samples originating from target domains are independent from each other.
We learn the neural network by solving the following Bi-level ERM:
min R(0)= = 1 Σ [ho(as) wa:))) s.t. w'(a;) arg min WEW
Σ o;()),(w). (4)
The parameters of neural network 0 should have the well-controlled excess risk unseen
R()) = /AN [(b - w (a)))]|
To solve (4), we nested loop procedure which performs GD step neural network objective R, while in the inner loop we approximately find "labels' w (a1), -... w" (aa,) using K'sstpp GD. The entire procedure for solving (4) is described in Algorithm 2. Then, the following theorem shows that the two layer neural net optimized by Algorithm 2 learns w (ax::
Theorem 3. Let do N pollyog(N,, n). Consider a neural network of with m 2 S2 (n 2h:
Then, for the Algorithm 2 with n S 3 = + -
2
Ω
NA3a log(n)): and K >
(TTD) )) the following excess risk bound holds with probability at least 0.99:
k log Xa
R(0T+1) S O (1x*) 2
The proof given in appendix B.5 is based on more-or-less standard Neural Tangent Kernel (NTK) approximation argument [15, 4], namely we use the key fact that predictions made by a GD-trained overparameterized neural network predictor (given that the width of the network is sufficiently large). Now, such a KLS GD-trained predictor can learn Lipschitz target functions: It is well known that by learning
close those made by Kernelized Least-Squares (KLS)
sufficiently large
Reproducing kernel Hilbert space (RKHS) (with polynomial spectral decay), one can approximate Lipschitz functions well [8. 2]. Here our goal is approximate vector-valued function. however, by treating each output independently we follow existing proofs [14, 21] for scalar-valued Lipschitz regression by GD-trained neural networks and arrive at the same excess risk times d.
Optimality of our rate. Here we show that a two-layer neural network trained by a bi-level Gra- dient Descent (GD) can learn vector-valued function with O(dn-I* excess risk. If we ignore the dependency on d, our result matches the minimax rate of learning a scalar valued Lipschitz function []]].
7

---

Algorithm 4: Label efficient nonparametric online regression
Data: Radii schedule &1, 62... with E 42,, Label efficiency parameter p [0, D Set of centers
S < Ø
for f 1, ......o do
Observe Ozzi
i Ø then | + (1)
T, + ;
Create initial ball
8 + arg mss ||ox - as
Find active center
T, 0 then
W. 11
else
Wr - [T.
- Ever, We'
Predict using active center
if a4 0, I & then
T, T, (t):
D Update list active center
else
S Su {s}, + Ø;
P Create new center
Draw a Bernoulli random variable Z, such that P(Z: = p; Observe w, II [Z = 1] GD(O, oz, K);
Update pscudo label for at:
Efficiency of our learning-based approach. Given M mixture weights (a:)) M the baseline naïve approach is solve all M weighted ERM with gradient descent, accuracy level which requires O(Mx log (1/e)) time complexity. Using our approach, we first need to learn neural network with excess risk, and it needs n e ( samples, which implies that we need to solve this many weighted ERM problems, resulting a complexity of Ô d(x*) learn neural network, we just need to pay for the inference cost to predict w for each a,, Putting things together, the total time complexity θ ((x*d//e)++))) N-//2 log(1/e) + M). We observe the following regimes:
x log(1/e)). Once
When M 2 12 (2002((1 (1=2
learning is more efficient than solving M ERMs.
x <log(1/e)-1
Otherwise, directly solving M ERMs is more efficient than learning a model predictor.
Intuitively, when the number of target domains is much larger than number of source domains, our learning based approach is strictly more efficient. It is also interesting to note that our learning based approach can avoid computational overhead of M, but suffers exponential cost from the number of sources N. While solving ERMs avoids the price for N, the computational cost increases linearly in terms of M.
3.2
Online Setting: Label Efficient Nonparametric Online Regression
In previous section we discussed nonparametric offline learning of with distributional as- sumption on Oi...., aM. In this section we consider the following online learning protocol with oblivious adversary. Given known and fixed parameter p e [0, 1], and an unknown sequence (a1, w" (a:)), (a:g, w (az)), E A (D) of inputs and labels, at every round 1,2....
1. the environment reveals mixture weights a E A
2. the learner selects label W, E (D) and incurs loss l, (w.) = || - wa:)
3. the learner samples Z, Bern(p) and observes [Z, = 1) Wi, when w, GDooptimized approximation of w (a.).
In particular, we introduce Algorithm 4, a modified version of the online nonparametric regression algorithm proposed by [13]. Algorithm 4 iteratively constructs a packing of A using L² balls centered on a subset of previously observed inputs. each step I, the label (parameters) associated with the current input a; is predicted by averaging the labels of past inputs within the ball whose center Os is closest to ai the l metric (note that labels are vector-valued). If a lies outside the nearest ball, new ball with center a, is created. The radii E, of all balls shrink at rate t {-1/(1+M)

---

Note that efficient (log in the number of centers) algorithms for approximate nearest-neighhor search are well-known [19], well as hpghly-optimized open-source packages are readily available [16].
In contrast to the original algorithm by [13], where all sequentially observed labels are used to generate predictions (update local learners), algorithm variant uses only p-fraction of labels on average. This reduces label complexity at the cost of increased regret. This approach is referred to as label-efficient prediction in online learning [6, Sec. 6.2] and is beneficial when accessing labels is costly. The following theorem, shown in appendix C, establishes the regret bound of Algorithm 4.
Theorem 4 (Regret bound). Let f AN R. be arbitrary x² -Lipshitzz function with respect to -|-I| metric and let CN > O be metric-dependent constant. Then, Algorithm 4 with & L 14w satisfies
E
Σ
((llw))
(pCN (pCNIn(eTT) 4D* + (1-P)TD 4pDT(1-K
Moreover, by definition ( (ai)) = 0, so choosing f() = w", the above bound implies that:
T T - B[e((W)) s 8(pON In(eT) + 4Dx "T + p) D + 4pD (1 (1-x-1) D.
The core idea behind the proof (deferred to appendix C) involves maintaining a balance between the regret contribution of each ball and added regret term arising from approximating the target function using Voronoi partitioning. The regret contribution of each ball is logarithmic in the number of predictions made due to regret of online quadratic optimization [6. p. 42]. Ignoring log factors, the overall regret contribution equals the number of balls, which is essentially governed by the packing number with respect to the e² metric. The additional term in the regret comes from the algorithm's prediction being constant within the Voronoi cells of N induced by the current centers (considering that we predict using the nearest neighbor). Thus, an extra term equal to the product of the balls' radius and the Lipschitz constant is incurred. Finally, the label efficient algorithm we present here incurs yet another, p-dependent terms, which accounts for the missed labels.
Corollary 1. If our desired average regret is O, then Algorithm 4 has label complexity:
DR
I+N
(1- (
c/c/DD
I+N
δ
max
Note that we recover the standard version of the algorithm (non-label efficient) by trivially setting (1/c)I+N]) which
p 1, which in contrast has label complexity of order ((max((De) (D)((/))+++++ /c) strictly larger than the label efficient version as long as is not zero. When our desired regret goes to zero, the label complexity of two algorithms will tend to be the same asymptotically.
4 Experiments
To demonstrate the effectiveness of our proposed mixture weights estimation algorithm, we conducted an experiment using MNIST dataset [1] according to the following specifications. We consider scenario with 15 source distributions, and dividing them into groups. For group 1, contains 5 source distributions and each distribution contains 100 data (80 for training and 20 for testing) samples which are drawn uniformly randomly from class '0', '1' and '2'. Group 2 and 3 share similar settings but their distributions' data are drawn from class '3', *4" '5', and class '6', '7', '9', '10' respectively. The data generation process is summarized in Table 1.
Group
Classes
Domains per Group
Samples per Domain
I
0, 1, 2
5
I00
2
3, 4. 5
5
100
6, 7, 8, 9
5
100
Table 1: Classes and samples per domain for each group
To demonstrate the effectiveness of our Algorithm we implemented and run experiments with two-layer MLP neural network. We choose four different target setting: (1) target distribution

---

Target (Group
Target
Target (Group
Target
(Group 2)
(mix of Group and 2)
Average ERM
69.9 %
40.0 %
34.9 %
59,9 %
Pure target training
69.9 %
55.0%
40.0 %
55.0%
Our method
80.0 %
69.9 %
55.0 %
65.0 %
Table 2: Accuracy comparison with two baseline algorithms. Each row represents the accuracy of model learnt by Average ERM, Pure target training or Our method, on different target domain. We can see that the models learnt using mixture weights from our algorithm (Algorithm I) always yield the best accuracy.
from Group 1, (2) target distribution from Group 2, (3) target distribution from Group 3, (4) target distribution from the mix Group and Group We compare three algorithms: Weighted ERM using our learnt weights, 2. ERM averaged weights and 3. ERM solely on target domain, and presented our findings in Table 2. The results indicate that the accuracy achieved using the learnt alphas outperforms the other two approaches.
5 Discussion and Conclusions
In this paper we studied the multi-source multi-target domain adaptation problem. In the first part of the paper we gave an algorithm for adressing a minimax problem, that provably finds good mixture weights of source domains, given a single target domain. In the second part we studied the problem of domain adaptation with multiple target domains, and introduced the co-component ERM problem. We gave two concrete algorithms to solve co- component ERM problem, in offline and online settings. There are several potential future venues for future work, which we briefly discuss below.
Online mixture weight prediction Throughout Section 3, we assumed that the target domains' as are given. However, would be interesting if given new target domain, one could predict good mixture weight in an online fashion, and our Algorithm could serve as an oracle to give the inexact label. Meanwhile, since the Algorithm takes considerable time converge, a desired online algorithm should also be label-efficient.
The complexity of solving co-component ERM The co-component ERM problem we introduced in section 3 is interesting from pure optimization perspective. Even though we proposed the learning- based approach avoid heavy computation, one alternative direction develop efficient algorithms to directly solve M co-component ERM problems, and give upper and lower complexity bounds.
More structure in w* and better phase transition laws In this work we considered basic structure in co-component ERM problems (strong-convexigg and smoothness), which gave rise to Lipschitzness of w*. Lipschitz class of functions very large and in general only be learned at
rate On - ). As discussed in section 3.1 this allowed us to argue that the learning approach is more efficient than solving co-component ERM whenever M 2 (((1)))/2) However, we could potentially obtain better rates (and better laws) of learning w" having more structure in w For example, assuming that w* is H-times differentiable, the excess risk would behave as O(n x
[1]]. Thus, the learning approach would be more efficient when M 2 (((1/)) (/2HH), that with potentially much fewer sources than targets. It is intriguing question to figure our which co-component ERM problems would allows for nicer structure w*.
Alternative learning based approach for co-component ERM There may be several other learning based method to solve co-component ERM. One potential approach is Meta learning [10]. The idea is to train a meta model w Wineta by optimizing pre-defined meta objective based on some sampled mixture weights, and the goal would be find a model that can quickly adapt tasks with different mixture weights We leave this promising open problem.
10

---

Acknowledgement
The work of YD and MM was partially supported by NSF CAREER Award # 2239374 and CNS Award #1956276.
References
[1] The mnist database of handwritten digits. http://yann. lecun. comlexdh/mmist/.
[2] Bach. Breaking the curse dimensionality with convex neural networks. Journal of Machine Leurning Research, (8(1):629-681) 2017.
[3] P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
[4] L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: statistical viewpoint. Acta Numerica, 2021.
[5] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan. A theory of learning from different domains. Machine Learning, 79(1-2)1511-75, 2010.
[6] N. 2006.
and G. Lugosi. Prediction, learning, and games. Cambridge University Press,
[7] Chen, Y. Sun, and W. Yin. Solving stochastic compositional optimization is nearly as easy as solving stochastic optimization. IEEE Transactions on Signal Processing, 69:4937-4944, 2021.
[8] F. Cucker and D. X. Zhou. Learning theory: approximation theory viewpoint, volume 24. Cambridge University Press, 2007.
[9] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks, arXiv preprint arXiv:1810.02054. 2018.
[10] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learing (ICMI.), pages 1126-1 113.. PMLR, 2017.
[11] L. Györfi, M. Köhler, A. Krzyžak, and H. Walk. A distribution-free theory of nonparametric regression. Springer, 2006.
[12] Hanneke and Kpotufe. A no-free-lunch theorem for multitask learning. The Annals of Statistics, 50(6):3119 3143, 2022.
[13] E. Hazan and N. Megiddo. Online Learning with Prior Knowledge. In Learning Theory, pages 419-513. Springer, 2007.
[14] T. Hu, W. Wang, C. Lin, and G. Cheng. Regularization matters: A nonparametric perspective on overparametrized neural network. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 829-837. PMLR, 2021.
[15] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: convergence and generalization in neural networks. In Conference on Neural Information Processing Systems, 2018
[16] Johnson, M. Douze, and H. Jégou. aillion-scak similarity search with GPUs. IEEE Transactions Big Data, 7(3):535-547, 2019. 2019
[17] N. Konstantinov and C. H. Lampert. Robust learning from untrusted sources. In International Conference on Machine Learing (ICML), pages 3488-3495 PMLR, 2019.
[18] Kpotufe and F. Orabona. Regression-tre tuning in a streaming setting. Conference on Neural Information Processing Systems, 26, 2013.
[19] R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In Proceedings of the 15th annual ACM-SIAM Symposium on Discrete algorithms,, pages 798-807. Society for Industrial and Applied Mathematics, 2004.

---

[20] I. Kuzborskij and N. Cesa- Cesa-Bianchi. Nonparametric Online Regression while Learning the Metric. In Conference on Neural Information Processing Systems, 2017.
[21] I. Kuzborskij and Cs. Szepesvári. Learning lipschitz functions by gd-trained shallow overpa- rameterized relu neural networks. arXiv:2212.13844 2022.
[22] T. Lin, C. Jin, and M. Jordan. Near-optimal algorithms for minimax optimization. arXiv preprint arXiv:2002.02417, 2020.
[23] T. Lin, C. Jin, and M. I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv: 1906: 00331, 2019.
[24] Y. Mansour, M. Mohri, Ro, A. T. Suresh, and K. Wu. A theory of multiple-souse source adaptation with limited target labeled data. In Arindam Banerjee and Kenji Fukumizu, editors, International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, pages 2332-2340. PMLR, 13-15 Apr 2021.
[25] Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain adaptation: Learning bounds and algorithms. Conference on Computational Learning Theory (COLT), 2009.
[26] H. B. McMahan, E. Moore, D. Ramage, and S. Hampson. Communication--ffiiie learning of deep networks from decentralized data. arXiv preprint arXiv: 05629, 2016.
[27] A. Mokhtari, Ozdaglar, and S. Pattathil. Convergence rate of o (I/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems. arXiv preprint 1r0iv: 115, 2019.
[28] A. Mokhtari, Ozdaglar, and Pattathil. Proximal point approximations achieving a conver- gence rate of o(1/k) for smooth convex-concave saddle point problems: Optimistic gradient and extra-gradient methods. arXiv preprint arXiv: 01115, 2019.
[29] Q. Nguyen, M. Mondelli, and G. F. Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learing (ICML), pages 81 119--8129. PMLR, 2021.
[30] M. Nouiehed, M. Sanjabi, J. D. Lee, and M. Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. arXiv preprint arXiv: 1a0:::992207777 2019.
[31] S. Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithmss Cambridge University Press, 2014.
[32] N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. In Conference on Neural Information Processing Systems, pages 2199-2207, 2010.
[33] Martin J Wainwright. digh-ddimessooal statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[34] Z. Xu, H. Zhang, Y. Xu, and G. Lan. A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcavv minimax problems. Mathematical Programminng pages 1-72, 2023.
[35] C. Zhang, L. Zhang, and J. Ye. Generalization bounds for domain adaptation. Conference on Neural Information Processing Systems, 25, 2012.
12

---

A Proof of theorem 2: Stationarity of Algorithm
A.1 Proof Sketch
To prove the convergence of Algorithm to a stationary point, we first need to relate our convergence measure to actual iterates during the algorithm dynamics. Defining
Ga w) (w- Pw (w + VV F(a, F(),,,))), Gala, = "f
(a-PA -P (a (VaF(a,w))
the following statements hold:
N
2 E G||Ga(a', w']l & 172
E I|a' - -at1112 + 2G _ E || 2+1 -
ff("))
j=l
E I w11 + 4G 0² E Gl w']l S 72
N
+ +
Σ d'() 12) (ff(w")- - f((W)))
B
Bounds above show that the gradient norm can be bounded by the difference between two iterates generated by Algorithm 1, and the approximation error of our stochastic correction steps. Hence, we need to quantify how well the proposed stochastic correction step can approximate inner finite functions, i.e., the difference between =j+ and f+(w") - (w"). This gap can be bounded following standard result from [7]:
E || ++1 (s7(w') [/ ( - (1-)) E ||
[3( - (w]
w' w w=111 2,92 0²
+
- +
B
Besides above tracking error, we will also need to control the iterates gap of auxiliary variable z/:
E || +1 - z311? s (1
-
_ _ "1- +8 (1+
2 2 3
G? (I|w* w1 +
|| |w'
w 22-)
2 (+ (1+3) 2 GG /w' -w w
+8
shows that as the primal iterates approach the stationary point (i.e., iterates will not change too much), our auxiliary variable 2 also will not change too much.
Next, we are going to characterize the upper bound of E l|a - a 1111 .E ||w' - w 11 To this end, our proof relies on constructing two-level potential functions. Our first level potential function is defined as
jet =F(att wt1)
2
++1 ||att1
la
-2112-00
1
1.Gh
NL?
NG png
| -
1/21
47
1 (0(
NG?
||
||w'-w"yyj w|
+
7
1112²
||a
ad1
8y
ung
21
Then we prove the following one one-iteration relationship:
Bl
FM
20
E
w
w' 11
+ 87
1
E w' w² 112
E
w 1 - w'' 2
87
N
+
-C2Ella*t +1 - aa'l 2²112- - (1- 3)20 (r + m)
Σ
E
|| - (f/(w'-1) - [ww" (w('=11))
j=1
g² -
(1
9
2
N
-0(7+8p9)
0
E
|| --
B
1=1
13

---

where C₁ and C2 are some constant depending on 7, L, To eliminate the approximation error
E 1| (f*(w--)) (w( and difference of auxiliary iterates E construct another potential function Fi+1;
||
2j
1
we need
(1-1)
(1
2
G
pi+1 = pc+1
Σ
B
|
2/
p&n
Finally, we arrive at the following bounds.
C2 - 3" B w']l C1 7 BB w w']l 2
B[F - Fd]
o²
(2Crn 2C2n + 4n + 2/3 1 +
B
Conducting telescoping summation will yield the desired result.
A.2 Technical Lemmas
Proposition 2. gf) is Gg Lipschitz and Lg smooth, and f(() fx(1 are all Gj Lipschitz and L smooth, then F(ox, w) is == max {AG Lug + 2G Jeg, strongly convex in a.
2C
smooth, and μ 2C
mmia
Proof.
We first examine the Lipschitzness of gradient of F w.r.t. a. fx(()))) 2CMa
Va w) ((())))) (W)
Hence
VaF w) VaF(a' |0 a -all
a'll
Similarly for gradient of F w.n.t. w:
F w) - VwF(a,
a1)) - - V\)()) -V((<)) - -VS(('))
((1) Vg(ff(W) 1 [(W))(V/+(W) V((W)) - Voll(w)) -(W>))(\/+()) -
(11)) VV(ss(W)) ((W ((W))(V//+)) V((W)) Volls(W) - vA(w)))
N
N
Lp [[((W] - si(W) - (/7(W') - (/(W))|l 2G, + Σ a1))2, |w-
N
a(i)4G ||w -
wI+ Σ a1))2 1| w'll
For strong convexity, we compute Hessian w.r.t. a::
F(,. a:) 2CM > 20
I,
Mmax
so F(a, w) is 2CM strongly convex in a.
The following lemma bounds the tracking error of the stochastic correction algorithm.
Lemma (Tracking Error [7]). For Algorithm 1, under the assumptions of Theorem 2, the following
statement holds true:
E || 1 (fz(w') f/(w"))l/ < (1- 322-3)2 ( f 11
+ 14(1-))20 w w-11 2,3 0²
B'
14

---

An immediate implication of Lemma 2 is the following corollary:
Corollary 2. For Algorithm I, under the assumptions of Theorem 2, the the following statement holds true:
2+1 - ( < (1-3)" (1-)))) (//(w -
j
4 (1 - 3)2 7 G 2,8 (1- o²
(1
1- (1-5) B
Proof.
Due to Lemma 2 and updating rule for w, we have
E +| (s7(w") - //(")))|| s (1- B |2]
(Jz( (1((==1) - [/(w"
+ + G) E hg 2,32 0²
< (1- E - (ff(w'=)) f,(w"=1))]
+ +4 +4 + +53 0²
B
Then unroll the recursion in Lemma 2:
E || - (ff((")- - ff
< 31 E 11 (ff(w - - f/
4(1 3)3 232
Σ (1 8)2h
B
$ 9)2T E || (f7(w - 115(w~1)) 1)11
(1- - 3)2
4(( - G) + 223² 0²
1 - - B13
B
Besides the above lemma, we also need the following bound on tracking error between two consecutive iterates.
Lemma (Second Order Tracking Error). For Algorithm 1, under the assumptions of Theorem 2, the following slatement holds true:
B1|=/t1 +1 - =511² S (1
3 -2 - 25 11 +8
(
2 3
2
G2 (Iww* morf-ww'- wp- + || 222)
+ 8 1+ 3
&G, w' we--w-1pp 11
Proof. For the ease of presentation, we define the following two auxiliary variables:
= f((': { {()
- (w - (w(: (f.(w'-): - (ww((())))
According to updating rule of =, we have:
3+1 2/ = (1 - (1- - + (1 11 (f- + - 8/-1)
15

---

Taking expectation w.I.t. Ej. c/ 57- and t yields:
E || 2/1²
E E|[(1 - B) - +1 1 13 11-1111-- + 3.5
3
(1 - 9) (1- B || - 2 + (f5 - S3 1 ||
1+ 2 - 28
+1+
1+ 2 2/
||0U3- n/
+
B
1 2
8
(1 B)
[1 - + 1 - 1 1|
( - 2
B -15-1
3
11 B
B
(1 8)
1+ - 23
E 11 2/ 11
(1- 8
(1 B)
(1+ 2 2,9
f3 2 2 +
[+
2
2 3
3 31113 83 11
2
8
1
B
E
||
1|
+
+
2 3
E
11-1-12-11
2
1
2
8 |||} 13
2
3
where in (1) and (3) we use Young's inequality that ||a + bll² s (1+ a) ||a|| + (1 + 2) ||b|| Now we bound Ti as follows:
2)
T <4
1+
3)
2)
(IlA(w-':st :5---) - ( | 12 + ||]]( : -5
+4
1+
2
G7 (Iww* - w- + -| - w w1))
<8
1
3
and for T2:
To s 8 (1+ 2 B) G&G |w' - w-1 (1+?))
Putting pieces together will conclude the proof.
The following lemma establishes the difference between the exact gradients computed on F and the gradients we actually used in Algorithm 1.
Lemma 4 (Gradient difference). For Algorithm 1, under the assumptions of Theorem 2, the following statement holds true:
00 02 B
N d' - - -
E g V F(a', F(a s +
3=1
N E lg VaF(aa, (<tF(a,.'))12 S Σ GE (f7('') -
j=1
16

---

Proof. By the definition of B'w, we have
E g "wF(a''w''ll
- VwFld' w')
- 2
Σ (
(Vf((w (
2
Σ a' (( - - vf((W())
4G 0²
9 8G
(0-(>- VV))()))]
where at the last step we use the bounded variance assumption. Similarly by the definition of g we have:
E ga
VaF(a', w²)l =E
[[ (+1 "...)))..............
N
Σ
G E
++1
Lemma 5 (Connection between stationary measure and iterates). For Algorithm 1, if we define
Go w) = = -w- Pw (w + w. (w)) Ga w) 1)
1 (a PP-AA (a vVa w)))
then the following statements hold:
E GlaG, w²)l|= Blla² 1222 2G2
Σ
|| 1241 - (f7(W") -,(""))11
172
j=1
2 - w1 + 102 0²
B Gl w')l? v ?2
+ +8GG
1 Σ a' a1) (ff(w')) 55(w)))11
"
B
Proof.
We begin with proving the first statement. According updating rule we have
E
(a', w w²)l
1 (a "Paaa' (aa--nVaF(a w())
=E
<
2
E aa' -PA (a' - -T&a)l"
2 n/2
E |P (a' - -nga) PA (a' -nVaF(a',w))) |
1/2
<
2
a' a
a011'" +2 lgtt F(a w+)l|
N
2
<
E l a
222 Σ a'tl1
E || (f7(wt) (w(")))l
1=1
17

---

where at last step we apply Lemma 4. Similarly, for the second statement we have:
E Gw (a', w w²)l
= E
w' Pw (w' + 1/V w(a'', w w'))
7
- 72
E
I Pw (w' + ||2 + 722 E Pw (w' + xgw)) Pw (w' F
2
R
w' w + 2 1B" - v F(a', w')l|
2
w/ + 10 10
+8G Σ d'()) -
B
The following lemma connects F(a't), ww' and F(att1 ,
"(a't1,''"]
Lemma 6 (Dual Variable One Iteration Analysis). Let L == max (AGGL, + +2GgL, For Algorithm under the assumptions of Theorem the following statement holds true:
([F
H+1
.w'-1
= ,w"]l
L
L2nn
1 2n
E a a²11 (27G + 188 o²
E Bl|w!t1 -w'll-
27
2
B
- -4
Σ
a (13)
3) (ff(w - f)(
8)611-8)12200 w w-21
Proof. By the optimality of projection and updating rule of w, we have:
(rg" + (w" w(11), w² w w 0
Re-arranging terms yields:
(g. w' w(1) s - 1 141 - 1211
Adding and subtracting w F'a'; w²) gives:
(VwF(a', w'), w' - w(t)) + (g"n VwF w'), w' - -w(t1) s 7
|| || -11
Applying Cauchy-Schwartz inequality yields:
1 [| w'1l 11 < (V F (a', w'), w w²) + 1 || || -w1l2 5
-
1B /
1
27
Now, we take expectation over the randomness of Ct. Cj. and apply Lemma 4 to get:
E | w² E (V F(a", w²), w -w") + 27/ 0² g B
27
1 Σ
a()) (=f("'-V/((ww))]
18

---

Plugging in Lemma 2 yields:
E w + w'1l $ E (V V F''' w - -w") + 2 o²
27
B
N
(1 (1-3)² ,
L3 Σ a'6i
- (ff(('')) - fs(w(
+
j=1
+ 4(1 3)& |w'- ww=11| + 2,32 o²
B
On the other hand, from Proposition on the smoothness of F with parameter L we have:
F(att1 w(t))= - F(att) +1 w')
L -| w'll?
2 W ((att w²), w w")
2
L
(VF(a', w'), w w²) -wo)
// w'1l² + (VE(a't1 ww)) -w")-FF(d VF(a', w w²)
(VF(a', w'), w -w") L
|| w''l?
2
1 VF(att) .w') - -VF('', ww')l I LV | w w'1
LVT
2 (VF(a', w(t1 -wo) L
|| -w'12
2n a|atttaa'1"" || 1 w'|l
-a²11 I2'm
2 (VF(a', w'), w w') --)-
_
L L2n1)
||
w'll²
1
||att1 a²11²
2
21
Putting pieces together will conclude the proof:
E[F(att +1
w'
w
F(att1
++1 w')l
L
L²n)
E B||w - -w'12- 1 E
E||a - 1=|a=tt-aa'1 1002-(25) -22 + +8.9110971 0²
27
2
2
27
B
N
- 4120071 Σ a'())(1 -1))(11)))
f5(w" -1(
1=1
1661 - 1) 13 E w-' ww1
The following lemma connects F(at+1, w( and F(a', w²).
Lemma 7 (One Iteration Descent Lemma). For Algorithm 1, under the assumptions of Theorem the following statement holds true:
E[ +1
w
- w')l
L
Lin1)
E Ellw(t1 - w/1l2 - (6611-))2337+
"l|w" ww
27
2
3
4n11 - 8y2 1Blaat1-100 + (u-1) 2n 2
nL
a||aa - a---11
2
21
N
Σa- - 3)² (4a'
11 (f7(w- - fs (w)2
J=1
(210) 8888 1303)) o²
B
19

---

Proof. According to property of projection we have:
Sa + (a - aa), a 1+1
f
2
(5)
"
8a
+ "
- -aalt1 - -a), a'
20
(6)
1
Sa
1 +
(a' - a a='")")) a 1+1 a² 20
(7)
Since F(, w) is strongly convex for any E W. we have:
F(a't1 w*) F(a', w') (V.F(a', w') a') - -a') + H -1 a
2 (VoF(a', w/) -g-- a aett-aa) -a) + t "11att1 a
1 la' a t-1 aatl-aa
2 (Vaf(a', w') - Val(a'" ,w' a a²) aa') + 1aatt= a'1
2
(ga t- - vaf(at t-1 w w"))),a" -a')
1 (a' 1-1 t - a²)
where at second inequality we use the fact of (7). For the first dot product term, we observe that: (VaF(a' w') V. F(aa11 ,w' a aa))
(8)
= (VaF(a', w²) - V. F(a', w a a²)
+ (V.F(a', w w'-1) VaF(a-" 1-1 ),4)
(Val(a", w w -a
1-1 ww/ ,w'')),a' a a111)
L'nm w w' 2ny
1
nL?
1 ||12
+1 a²1
||a²
a²'
112
ul|aa
11-1112
2
21
(9)
where A (a a²) (a' a²-1).
For the second dot product, we have: g
Eggh - V.F 1 ao aa)
2 m1 B) E
vaF(a'-1 - 4r/(1 - 3)2 E B| -1'1""
1
a²l?
N 2 (1 - 3)2
Σ
Ge
-
fz(w"
4n(1 - -)22 ++ a²11²
1
j=1
where we plug in Lemma 4 at last step.
For the third dot product, we use the following identity:
(a at-l. a a²) = (Hlla* -112112 + 1 11a - 10-12 - (10)
So we have:
E[F(a w') F(a", w')l 2
1.21
E Iw - w
+
11 1
1
E Blla*t1 - Bllatt-aa|1
2
n
4n(1 3)²
1
nL
E ||aa"
111
11
2n
2
7/(1 - 3)²
Σ
G
1|
(/3(w"=1) - 1 1)(w"-1))|/
(11)
1=1
20

---

Recall Lemma 6 gives the following lower bound of E[F((*+) (/t/aattt"/tt))) - F(att) "w',',
ww)]
([F((tt) +1 w ) F(a"t! ww'l
(12)
L
1,21)
El|w(t]- w'112 27 - (2 + 8,88 1337) o²
a0112
24
2
B
N
y
Σ
a' (f) (000111)1BB4 B| (fz(w((1)- - -f-("
1=1
-
E w/ - w0-21?
(13)
Hence, Adding (11) and (13) yields:
B[F((**) ++ ) F(a", w")]
L
1,21)
E El|w(t1 - -w913- (16(1-8)923) 1.2m
E Bllw" [=|w"=="=11) 1|
27
2
3
E BB|aat!-
-aact!-a'11 -a'l²+ + (u- -u- 20
nL²
E Bl|aa 1---a-- 11-
29
4n(11 B32
N
Σ
(1 - 3)2 (j) + (fz(w"-l)- - (w
j=1
G2 8 8 1g) o²
B
which concludes the proof.
Lemma 8. For Algorithmm 1, under the assumptions of Theorem 2, define the following auxiliary quantity g++11
fi+1 = =(aatt 1+1 w
+ s
1
+
+
nL?
2 +
192NG3
g
+
96NG6093 1227
|
w/1
47
mmB
1
+
96NG2
|w' - -w" 1011 +
+
nL?
|a - -ae1 ae11
87
mmB
21
2
where
2
1+1
la 1+ 22112
112pe
Then the following statement holds:
E - F*] 20 E ++1
w-11
1
w Fl|w"
R
w- -
1-
+ 1 E
w r- w--21"
84
8y
+ C2BBlaa* aa11
N
(3= (4I + Gg
Σ
E ||/ (ff(w--1)
f,(w"~1))1
j=1
(270) + 88 838 13,97)) g²
(1
AG2
Σ
E || - 11
B
2
11211
where
L
192N G9GN
96N 96N
C
- 161.
4y 2
1223
1221
3
1
2T2
C2 =
7
2
417(1
8)2
21

---

Proof. According to (6) and (7):
(A#1, a -a't) 2 (g' gā- a -a))
If we define ga (2, (o(2)), .... g(2N)] + 2CMa.
(Alt) a - a 2 88 - Ba(z", t - a')
(Ba a') - d-1 a - a')
2 & Ba(x', a t1 - aa')
(Ba(e', a') - g a - a² - (a' aa))
(Bals", a²) g.- (a -a
G N
Σ
||
2/12
- a
1
1=1
nL?
|ay -
-a'
a²=1
1
A 2 + M ||| a' - -1
2n
Since 1/ (A a0 al+1)
1 a' - a²-112
c+ - -ay|²= 2 - ||
Hence we
27
2n
have:
G2 N
1
aa' -a'1112
2m 1|attt-aaa1
a²1|² -
9
Σ
|| - =-1l²²
1l
||att1--0
217
1 j=l
4
nL?
a - -aa 11= + 4 u1|a² - -1-
2
Multiplying both sides with 4
ny yields:
4G2 N
2 sui || ao - ----111 11=
2lu ||a t+| - aa11²
2
Σ 12211 j=1
g
1+1 - ==|l=_ -
1
||a - =x211
77
21,2
||0. a. 11 + 10a - a0111/ (14)
and so, putting all together,
(( H+
w - F(a', w')]
L
12n
E ++ El|w(t1- -w'1? (16(1- - 1161--8)13347 +
I'n
E El|w* B3|w"-w--11
27
2
2
2
3
4n(1 )97)
BBlaa BBlaat1-ad 10aett10a'11 -2² + I 27
E Ella* - aa 11
+
2
2m
N
Σ(1 3)² (40' + E (f+(w--1) - f3 f/(w+=1))(
#=1
- (2 + 832 8 23G?7) o²
B
22

---

Now evoking Lemma 7 together with (14) yields:
E[F(att) (+1
w + s (F(a', w') + s¹]]
1
L
L'1)
E + Bl| - -w'l1- - [16(1-8) +
L'n
E ww'
11
27
2
2
2
14
3
1
1
E |a aa11²= + (N- 1
nL
4
2L
E
aa - a 11
2
2n
4n(1 - 3)²
11
2n
n
p
N
E 3)²
G4 + n E113) - (fz(w 1)- -f((w(
j=1
o²
4G²
(2 + 888 1307))
E 2 2/1 - 2//12
B pºn
Now we plug in Lemma 3 with the fact that 1 2 1 and get:
B[F +1, w/ w(11) + 11 - (F(a", w²) + ++)]
1 L
L'n
E -
27
2
2
L'
96NG,033
96N
16L,,7 +
E | w w-
E |/w - w' 21
+
2
1rm3
12-1
12n3
+(2
11
1
BIlatt c+1
B
1 =21²+ +
7 112?2
21
E | - a2-111
2
2n
An(1 - 3)3
2n
2
N
-1- 11-89 B3? (41 7 + n12)))
Σ
E
[|]] (fz(w--1) - |1]]1 1
j=1
- -2210 + 888 1277)
(1
2 4G N
E - - 1/-
B
2
1.11
Recall our definition of potential function p++
fe+1_ =F((tt) w + h2+1
1 +
161. +
nL?
192NG90 96NG,095
| -w'1?
+
47
2
12n8
1121
- 1 +
-(3) 8y
96NG607
|| 1|v'- 11
7
111?2
2122
||a
aa'l?
+
+ 1
u2ns
2n
2
We conclude that:
192N0909
96NG2098
B[fe++1
fr >
L 3
2n1
2
161,07
E
Bl|w+t w'11
47
2
12:1
121
E f||lw' w-1
+ 87
EE
- w-221
87
[ + 1 2
3 L2
1
2L2
E Ellaot2 - -021? -
1)
An1(1
-
832
11
N
- -1 - 3) (1T2 + (122))
Σ
E
||| - (V7(w(-)) - 1)(
j=1
q²
- (11
3
2 4G2 N
- -2200 +88 1200)
!
E | - 11
B
2
11211 j=1
23

---

Lemma 9. For Algorithm 1, under the assumptions of Theorem 2. define the following auxiliary quantity Fu+1;
N -E
(1 3)
4G p yj
fett = =p+t1
E
e+
2
(1 )2
j=l
Let CI, C2 be defined in Lemma 8. If the following conditions hold
1
4(40 + +N0
+ ()
1- 1- 2 6
(1 -1- 21 )2 4G 48
20
0,
(15)
87
1 -
+ ( 0
(16)
1
(1 21
4G 24
9
G
2
0,
(17)
87
1-
then the following statement hold:
CJ ス C1 w')l
C2 " E VV
+
2
2
("C=""3388++00000333"3333333 + 40 + 12,031+ o²
B
Proof. According to Lemma 8:
B F4]
2 Ci EB/ 1l| ++ - -w'll + 87
1
E w' - 11-
+ C2 _ 1 a²|
1
B f|| 1-1 - 2
+
87
- (1-3) (1L3)(11)0))))) G
+
Σ
E E1 (fz(w*
- )
ff((((1))]
j=1
a² B
(1-
2 4G2
N
#1 Σ
E - 11.
-
-
2
11
j=1
where
L
3
192N
96N
G
n
- 161
47 2
122
1221)
3 11
212
C2 = - z4 2
4m(1 11 -)²
Now we plug in Lemma 5:
Elfe+1 - pd
2 Ci
21 1B G('''( - 2- 0²
1
-422 G27
-()((()) - -V/"''))//(((')1'
2
B
J=1
N
+C2
1/ E Va w w² G Σ E
|| (ff(w')- -
j=1
N -(1- (1-33 (4L 7 + n3
|2ا - (f+(w--1) - ff(("= - (27 + 1888L,,G, o²
Σ
E
B
y=1
- -(1-
8 2 40
Σ
R 1|
111
+
- F ||' - w- + 87 BB|lwtl-w''
87
24

---

Plugging in Lemma 2 yields:
-1 2 C2
E w']] C2 / w']l²
N
2.22 o²
-G147931 2
[d((i) (1- B (f+( f(( f)(w""1)) + G/
+
B
N
4(1 + || - w--11/ + +282 -22 0²
Gg Σ
(1 - 3) ||} - -(>(w(-)) - - //("-")]|
B
N
-1133) 3)² (11. + v0.))
ΣE|1=} -
1=1
(27GG% + -888 L,G + 2017 (?:) o²
B
(1
33 4G2 N
B ||| - 2 11
I| - w w-
+ 1
8y E Ellw- -
+ 8y
2 1º1
Rearranging the terms yields:
B| - F*1
C1 2 E G w']l + / Gaa' wi)l
2
L - -1 + N)1 - 3)(03
E "ll't-w'-p
+
87
N
(4
+ C22 Gr + 43 + (/ (1- - (1-3)² >E Blss - - -
J=1
1
E w
w 22 (8C + 2C 08L38
27 + 88792388 + +2 0² B
87
B
2
4G2 N
1
E3 2/
2
n1²11 j=1
Recall our definition of potential function Ft+1;
(1- - 22 4G² N
ptt : pe+1_
2 41
(1x(w")-1((<))
(fx(W")
9 Σ E 1
1- (1 2 n2n 1=1
25

---

Hence we have:
E[ - F7]
C1
+ L - k I Va will?
2
E
G(a
2
2
+
1
1 + C23
E =1|=-'=w-111 w1
8y
N
Σ
E
- f((")) (1 2 00]||++++ 1| - (f7(w(-1) (/(
1=1
N
(4
+ G2n + 4
+ n (1 - 3)²
Σ B ||/ - -f
-
5=1
+ 87
1
w
1- w²-2 2|2 (8Cn)
+ 02 +
+
o² B
-
1
1
2 'G N
Σ
E3
|| - 2/ 11
2
11211
j=1
(1- 2 4G N
(1- 2) 4G N
Σ
E
|
=
1 1- (1 - 2)
p
1- (1- ))
p 1=1
Now we plug in Lemma 2 and 3:
E E[ - -F
C1 7 E V w G(a w')l' G(a',"))|l + -2 Va
2
2
1
(1 - _2/² 4G² 48
4(4017213N + C2ni N)(1 9)1-98903
1 (1 - 3 p2n 3 67
88
x E w' y1
+ (1 (40n~212 21 + C2n +4 +1) (1
x Σ
E 1| - (f/(w" 1/)11
j=1
1 (1- 32 4G² 24
El BB| -
+
87
1 (1 - 2 222 3
2o
(8 + 222 32
+ +2702 + 87
+ +2 + 2252N)
B
(1 8 4G
1
(1 - 2)2
1
Σ 1
2 1,29
1 (1 - 32
1 (1 4) 2
By our assumption in (15)-(17):
1
1AC, + C2n + +N -N
1- (1 - 2) 12an 3 G7 20 0,
(1 2)2 402 48
88
1 21 + + G + 1) (1 8) 0,
1
(1- (1- 4G 24
G3 0,
87
1- (1 - 2/2 p21 3
26

---

then we can have the 'clean' bound:
B[ - F4 ス Ci y Vu C2 "
2
o²
2C2 C2 + 4n 28 2812077 + 233)
+
B
A.3 Proof of theorem 2
Summing the inequality from / = to T yields:
B - FJ] + (20172 2C2 2C21 + +, + 22, 1 2,3 o² B
+,,
T-1
Ci
+ C2 ,22 E Va
Σ
y V w']|
2 T 1=0
2
2
min
( 7, 2
[C C2
"
1
E Σ
V w G(a', w )| L V. G
T
We compute the upper and lower bound of Ci and C2. For Ci
1 L 3
2 16 G
G6,
Ci
n
4y 2
p2m8
1²11
The upper bound C
s 4y
1
holds trivially. For lower bound, since we choose
1
y min
220L 60mL2' 8V10L, 7680NG3G3
we know that O 2 1
87'
For C2:
1 - + 2" C2 =
nT
21.2
1)
2
4n1(1 - 3)2 f
The upper bound C2 S 7
+
3u holds trivially. For lower bound, since choose:
V2
)
v3
1 = min
H 36L2
0.1
33
2
holds that C2 2
2n'
Since
1 <
C1
<
1
and
1 <
<C <
1 +
3u < 2 "/ we have:
8y
47
2n
B
F
4
o²
+
3² + 47 G
23²
(18)
T
B
min
16
1
T
Σ
E
V G w || + E V. w/ll
(19)
We then need to verify the conditions (15), (16) and (17) in Lemma 9 can hold under choice of Te. By and B3 To guarantee (15) holding, we need:
1
< min
(V 128L3N' 52G² (2n + N)' 307200G303
27

---

To guarantee (16) holding, we need:
7 S min
S 100G
50122 200T.2
To guarantee (17) holding, need:
1=n 7 5 1080G703
Next examine how large the B[FT poj is. By definition of potential function, have:
E FT
N
(1- 9)
N 4G
FT
Σ
E
1|
Σ B
2
1 (1 2 1²11
/=1
j=1
(1 2) 4G
10_ Σ
E || - 1>)1
f5(w
1 - (1 - )2 122 Σ
E B||2| - 2
(1- g) 4G
N Σ
FT
Fo +
EB (ff(w f/( 1))l
B || 23 11.
B 32 12-11
j=1
j=1
By our choice = = fw( ff(w- w = w-1 we have
E[FT Fo] S Fr f.0
Next we examine how large the E.FT fr is.
F f
nT.2
192NG3
96N
F(aT, wT) + ST
+
+4130/
2 +
g
||
11
49
12n8
1221
1 96NG9
(7 7
|| 2
11a=
a111
87 1278
2n
+ 192NG3
96NG
F(a., w0) - 50+ +
1/1 + 41207, +
g
1/m0
11
2
1221888
12
1 + 96NG2
||
- w 21?
7
+ 1 n!?
||000
11-
8y
1221
2m
2
7
1/222
Fmaxx
+ 1
1a2" -17
2m
2
Notice that x- = a. w w-1 w- we have
BIFT - Fo] < F Fmax +
7
nL2
|a"
-T-
+
2n
2
According to updating rule,
28

---

E BlaaT a -=-1|== = ng
11 2n 1- 1
\ VaFla " . )/1
2nj Σ G || (ff(w' ((w'-)))
j=1
(1- (1 3)
8)2 0²
221)(2NB3) + +2)
31= GG. + 2/3
1- (1 B3 B
+2 o²
14y0G, (N L3) 2
Putting pieces together we can have the upper bound B[ |
9
(An"(NB) 12) 2r (14700 +2 2 )
E - F1 F max
2n
Plugging above bound back to (19) yields:
T
VG(aa, w²)l?
F Fmax 28 [4n(NB) 12) + 21NG2 (14700)02 + )
16 4
max
7 17
T
{16 41
( (2 44, + + 12 +
o²
+ max
{ 7 [r'n]
B
Fiax + (INNB3 + L?) + +NGG ( )
00
T
|
(TT2N8 + N2 G 1 0²
+
Define K = L/u. Recall that we choose:
1 " - kT. .7 -
T. G.g.G. NC..HAt.))
min
To guarantee RHS is less than e², we need:
Fmax me?
NB²
))
12 62G9E2" é
GoNO²
n² 1222022 KLo"
T= Ω
max
9 e²
B
θ max
'NG92'' NGG2 2
which yields the total gradient complexity:
o
R... max
kT.2 12L302 GyNo² G9Gg2' 2²
11)
2
max
29

---

B Proofs for w Approximation Algorithm
B.1 Proof of Lemma
Proof. First, we define a w) = =ン a(i) fg (w). Indeed, o(,, w) is vNG, smooth for all
W E W. To see this, we consider
V B(a w) Vw w)ll
Σ 04 Vf((w)
Σ [
N
ass [iw))
$
|a
a'll
max Vi((w)]
iEIM
i=1
$ || a'l1 Gf
S VNG ||a a'll
According to optimality conditions we have:
(w w (a), V f(a w' (a))) 2 0, - (w-w wa'),, V o(a, w w'(a') ))) 20 0
Substituting with wa'' and w"(x) in the above first and second incqualities respectively yields:
(w"(a') - -w V. F(a, w (a))) 2 0, (w" - (a'',, Dw w (a ))) 2
Adding up the above two inequalities yields:
ww(('') - w' (a), Dw w'())) V b w( (a'))) 20,
(20)
Since ((x,,) :) is μ strongly convex, have:
(w"(a') w (ax,, V w (a')) V. w (a)) ullv" (<a))" (21)
Adding (20) and (21) yields:
(w" - (a)), V V(a (aa (a')) V D(a', w (a 1 (l')) w=))l
Finally, using vNG, smoothness of t will conclude the proof:
VNGG|IW'(a') w (a) a a'l 2 -
(a))l
* || a'll 2 w'()))
B.2 Preliminaries of the proof of theorem 3
In this section, we introduce some notational preliminaries for the proof for Theorem 3. Following the framework in [21], we introduce three models, neural network predictor, random feature predictor and kernel least square predictor. In the following sections we will use w(j) to denote the jth coordinate of vector w.
Two-layer ReLU neural network (NN) predictor layer vector-valued neural network hgg N Rd:
Recall that in Section 3.1 we consider a two
hg(x) = |a] (U' x) ..... af (U*x)+),
where parameters of the hidden layer are matrices U E RmxN collectively captured by the parameter vector (veo(U"))....... vec(Ud)) E RdmN and we also define 0 veo(UU) E Nm. Here a, {+1/ /m) im are parameters of the output layer.
30

---

Next, induce the Neural Tangent Feature (NTF) operator, defined as
a)())]( T (1)aa
E R Rdd
(iLEN)
(m(m)I(uu (m)a)a/
where uy (r) rth row of U.Y Note that we dropped dependence on a on the left hand side is always assumed that the operator is applied to variable a. Also, note that the operator comes by differentiation of the neural network with respect j-th component of the hidden layer, that is &i (a) = Ves ha ha(a))loz=p? For convenience, we also introduce the following NTF matrix notation, given multiple input vectors 1 Oxp
c = (ai() of (a.,) E R Rd
Finally, it is not hard to that the of NTF operator recovers the neural network predictor:
(a) 0:
hr(a)= =
(a) 0
Using the above definitions, we can write least squares objective
R( = - (h.()a)) - w (a.)))
1 - n 1= j=1
Φ (a.))) - ((a))))))))))))))
and similarly for the pointwise loss function,
(0)) =
1 Σ
(M(()s) - wa.)(ii)
Σ
0 (a:)0 - (a)(())
i=1
1=1
and for the GD update rule:
0/ = =0 00--118 -gg,, where g/
Σ
(Haa)) - -((())
Neural Tangent Feature (NTF) predictor For parameter vector 0 Nd and 0 (0) ....... 0,¹) (the procedure for obtaining them is discussed later), we have the following NTF predictor defined as
(ob(a)) 0:1
h
(a) T TØ:1
We also use h5 1 predictor is
(ax) to indicate the jth coordinate of h (a.). Then, the objective of the NTF
12
RT (0.)
Σ
H6 (a,)0) - woa)))))
n
its pointwise counterpart is
Rel. (0.)
1 -
(o)) (ooe)--"(aee)) (a:)
Σ
a
bb (a.))
(1000-"(aai)) - -ax)))))
ni
and GD update rule defined as
0 = v (0.)
31

---

Kernel Least Squares (KLS) predictor In the following we will work with kernel function: Proposition 3 (Kernel induced by Rectified Linear Unit (ReLU) activation). The following kernel function is called the NTK function induced by the ReLU activation:
{ [( a I> a' > 03 N(dw O. (a, E E
k(a,o0)= (a)a')
The following holds for
It reproducing kernel and has analytic form k(a,a)) arccos(a a'') [15].
(a (aTa)(T
auPa..'ese k((1, a²) 1.
Eigenvalues of satisfy pa S SCK- for ENNE [2].
The NTK matrix is a symmetric matrix K E IR with entries (K)i. = k(ac; az).
Throughout, H. is the RKHS induced by k.
Having established the kernel function, assume the following about matrix K: Assumption (Smallest eigenvalue the NTK matrix), Assume that there exists fixed Ag > 0 such that P(mmin (K) Ao) 2 8%g and 8xo- E [0, 1].
Assumption is fairly standard and often satisfied with sample-dependent lower bounds:
In particular, [9] shows that Ag > whenever no two distinet inputs are parallel.
In random design setting, [4, Lemma 5.2] show that when inputs sampled from
isotropic Gaussian and n < d for some activation funetion-dependent C, Ag = 2(d) with probability at least e (n)),
In random design setting, [29] show that (for certain well-behaved family of input distributions), Amiin (K) θ (d) with high probability. More precisely, their Theorem 3.2 implies that have Amin (K) C polylog(n,, d)d with probability at least 1 - nze O(v))
In addition the NTK matrix, define its empirical counterpart for the jth component of the hidden layer, namely
K ==)(
D R
Then, it is clear that K = E[ data].
Now, for some vector с Rdd, we define the KLS predictor
E k ka ace
h
(a)
kla,, )
We also use h kls (()) to indicate the jth coordinate of h (a). The objective for KLS predictor is defined as:
(c))
hb kks (os)) w (a:))
m
for the pointwise loss function as:
Ricb. (c))
Σ
h kls. (ax,) w0 - va(()))))))
n2
and finally GD update rule is defined as:
Ct+1 Ct 1) VR (c²)
Proposition 4. Let w! be iterates generated by Algorithm Then the following statement holds true:
| - (aaw"" < (1- - 4n)'D D
32

---

B.3 Properties of ReLU Networks
In this section we include standard lemmata for analysis of shallow neural networks, and where appropriate we account for the fact that we are working with vector-valued predictors.
Proposition (Activation patterns [21]). Assume that initial parameters of a neural network are chosen as in section 3.1. Consider the set of indices of neurons that changed their activation patterns on imput a, when On is replaced by some parameters 0 (ū1,-.., umm:
a(),,) ox) {k [m]][[(" (k)a > 0} - I(ub (k))a > 0} + #0}
(ŌERN. , E A
Then, for O whose components satisfy maxe | uo S for some fixed p O, and any a E A. the following facts hold:
(a) For all k E P(O,a) a), | & | uo.
(b) E P( a:) S mp.
(c) With probability least 2e for any 0, PP(,, a)) S mp /mv.
Also
(d) Φb - poll S p V=
(e) ( Φ0) T
0 S plympp+ + vD).
Proposition 6 (Bounded gradient). The gradients of neural network are bounded:
|V(O0|| < (d)(())
[Voho(a)] d.
Proof.
The proof simply follows by definition:
m
V [oho(aa)
b (a))l
ΣΣ ΣΣ m
1 a) |a|1 sd d
i=1
and
n -obolcs)(boass)-vvoo
vŘ
Veho(a ((o()))))))))))))))))))))))))))) (ho(( w w( < (d)
12
Lemma 10 (Spectral Property of Empirical Kernel Matrix). Given set of parameter O: (ur(1),.. un (m)),, if we assume maxye]m] [lu,(r) - uo(r)) S p. then the following statements about the spectral property of its random feature and empirical gram matrix hold true:
(a) (0x))
||
5 1.
1 vn. || - Poll S vnl++ V=
(b)
Kg 5 Ko
+ 2n² v x
(c) Amin (K,) 2 (Ko) 2n² + v
Gin" log(n/v') then (Amin((K) [20) 2 1 vi and
(d) If we assume m >
X8
IP K. ( {
2 v.
33

---

Proof. We begin with proving (a), the spectral norm ((,)
[ $ (u])) ail ail 3
the spectral bound for P...
| = [(()(a))....,
$ Σ (..))) sn,
so we know | S vn. For (b Poll. by definition we have:
(1::(a)) - (
(0;;(a;) ,o(a;))?
m
(r)]((uu((r)a)))) ((r) (a:))
P(O a.)l
i=1
5n(p+ +
m
Now we show the bound on the norm K, We first examine | (a:)),(a)) - o5 (a:) Consider
Φ (ai))i(a)) - Φ5 (a:))u(a;))
((r) (r)as) (r),, - Σ (r)) a(r) (r)a,)aT aj
(r)aa) - Iuu (r)a, | T
m
- ((u)(r)a
X (1(u,(r)a,) - 1uu7 (r),,)) aa
1 (P((O,, as)) +
<2(p / )
34

---

Notice that due to triangle inequality we have K
S
Ko + [k.
Ko
Now we examine
K. Ko
K.
Ko
- K,
Kool
(22)
Σ
|o) (a;)))((a)) o3 (a)))((a;))
(23)
Σ
Φ (a,)),((a) o (a.))o((a))
(24)
iJj[nn]
2n (p
(25)
At last, we prove statement (d). According to Weyl's inequality:
Amin (Ko) 2 Amin (K)
Ko
K
According to basic concentration inequality we know that the following statement holds with proba- bility at least
2 2/log(1/v))
Ro(i.) K(i.))
mm
Taking union bound over all n entries and summing over all entries yields:
Koo
K <
||K00 Ko - K
S Σ
jo(i, - K(i,))l S
4n log(n/v))
Vm
(.E(()
To ensure the RHS less than
Aoo. we need
64n 2 log(n/v")
m
Last, since K2
K
S 2 No we know that it is also true Kr K k||s5 maxx
max
|K|
Lemma 11 (Deviation of Gradient Computed on Inexact Labels). For Algorithm 2, the following statements hold true:
sill < 4(1 (17) kt
0: RR (0))
/ T (0))
s/) 5 _/2 K + 2n² p+ (p+v²* = )) Kt.
4 33
Proof. Recall the definition of Ve. R((0.) and ge:
- (1 (a:)
2 // w (1))
a
Vo, ((..)
= (1(((((a)) (a:)
2 w')))
-ーー (h/(aa)) w((1))
2 (h) (1))
gi
Ed (a:))((a)) - w((d))
2 ( w
35

---

where w'()) [ww(() .... TI)TT E I= and w'()) =
E I...
Hence
V 0f Ri()))
g!
Φ (h) w (i)) 2
hg w'(")l(
n
/ (w' (j) w (ii)
n
4
| 2 Σ
< n sE(d]
max
- wa,)]]
i=1
S 4(1 nn) DtD.
For the second result we have
/
(R
(R))
gt)
4
4, p (hg w"())) & p/ w6))l²
n²
4
4 (w' (w'()) w (i)ii]]
n
4
/ $
n21 uun , K*D
n²
2n² V vm)
(1 - 1-1>) -27)
$
n
3 $ n 2
") (1 ky) Kt D.
K
(p 2n
m
The following theorem shows that Algorithm 2 can converge on empirical risk defined in (4).
Theorem (Convergence of Algorithm). For Algorithm 2, if we choose
48mB,
2 2566
m 2
Vv
do
A
3n3
48nBB
+ VD)
7) S min
No
Ao
256 (1 ||||| +
dn 2
88
and assume the inner iteration number of Algorithm satisfying then the following statement holds for any t E [T] and j E [d]:
ndDovv D 4By
K max
K klogg
2x log 16B3n
(26)
(1 (0(0(1)
4nC (1 un) K5 D
Ri (i() +
4n
nduu
with
4n² (1
C
24n
n
Proof. We prove by induction. We make the following inductive hypotheses:
17/00
6-1
17A0
6-1-8
(I)
R² 1
1
Ri ((8)(
Σ
(1- (1-1)(0(1-- (1y) D.
4n
4n
==
B
(II)
max
[ - u (r)
rl[m]
Au / m
36

---

where C' is the constant to be determined later. First we are going to show hypothesis (II) holding for
t ++1 1. First, by our choice of we know (1- - 17) (1-17)= - (1
ndo
Hence
in
Σ
4n
(1 pn)²
4n
17A0
==0
Now are going to bound maximal neuron drifting from initialization: for any j E [d] w
w/41(r) (r)
Σ 7 (r)
Σ Σ (r) (u((())) ai) au(h)((ar)
m
2m
1
((((a)) + -w(t)
m
72
21
(N((as) - -w( +
(wi(i) - 2 2
$ 21
V (2o) + ((-- (11-17)KEDD k
11- Ri)()) + dd((1-un)* 1/
ndu 4n
21
(1 -1y)KrD
vm
8n nAu V R((O) + +v
(dm(1-ar))5
< 2m
ndo
Vmjoy V (1 - (
vm
where at last step the fact v1 a1 for (0, 1), and triangle inequality split terms inside square root. Since we choose 7 1, we have
4n (1 2)*² + $1
2 (1 - 2))
8nBy movvm
[ (r(rl s 2n
1doo
vm
According to our choice of K:
monn 1683n
MDDxVD D
K N max
k klog
2x log
4 4By
have:
'V c 4n (1 1--2
-1))) 2))²² D 8nB
7dom novmm
2k (1 - 2)KD SnB,
vm
nuumm
Hence we conclude that:
48nB, doym
[[ (r) ue(r)]l <
Now we switch to proving hypothesis (I). According to updating rule, we have
0- 0/11
0 ng!
2
= 0 n7 $ (b: w'()))
37

---

where w'()) = [w] (i), ..... 1 (i)l. Hence
1
R0(O((+))
D 1+1 0/+1 - w w"(i)
Bi+1 0/+1 - Φ T 0//1 + B 0/+1 (j) 2
- inf pso
1
+
1
$ i+1
T 0/41 o T 0i-1|
1|
2 +(1 + p)
-
1
11 -
-i)
|
p
7:
(27)
where w wf) = (a.
For Ti:
1 12
m
T
x 7
0
0it1|
Σ
a (()a.)) - -luu (f)a:)) (r)
n1
Notice that:
(1) T a,) [(((((r) a.l)u,T (r)a:
(1 (r) a.) - (r) u.)
(L (r) a - (r(((r) T |:3i/ (r)
((0 (1 az) ) + |P()) az))) |n (r) -.,
az)
m
According to updating rule, we have:
Ju (r) w/41 T (m)
ngd (r)
2 Σ I un (0 - m/(os\||
57 1
Σ
(((((())
(r) T
(11 - -a)))
n
2nV (0))
2n
+
/m v - KI)
mm
Since we prove that maxye(m)
(1) -n((r)
S p. we have
|P(0t+1 ax)) S mp + Vmv.
Putting pieces together yields:
2
21/ R1)
Ti S m 4 (mp + Vmw)²
2n
(1-H7))KE 10) KED
m
vm
Ann (O'))
4n² (1 w))
<4(vmp+ vD)²
(28)
m
38

---

277 (K.) For T2:
0/+ - w'(i))
1
1
(0) ng!) w6)
n
1
Φ (0
2
n (hş-
w' (i))) w(
$
( 2
no (w' (j) w' (1)1){ 2
n
n
n2
1
2 n2
(h²- - he4-ww(jg -/>i||
+ + g)n _ 2 / T 2i(w'(i)
- -((''()--w()))"
< inf
1
1
-
<>0
4
inf 9>0
1+ 1
q )
(1
Ami (Ki)
2
R' R0)) + (1 + 9)
4m²
क ' w GD)l
n2
n
We choose
and the fact that a1+ a)² S (1 a):
2n 2n
n1 8. 0/+1 - wl
T2
21jdmin (k,)
R2(())) + 1
n
4n2 n3
| (w((w())- - w GD)l'
n
2nd (K1)
R²()
n
4n²
/ /)) (1 (0t D
+
2mp2anin (K,) 1
n
+ 2n +
nz
Since we choose S
n
we can re-write the above inequality as
2dman (K.)
(1 21jAmia (Ki)) T2 5
R²(( + n² Xmin (K,)
4n
2 (|Ko|| 2n² + V :)) (1 - 1-1)))
n
+ 2n 2n²(p + v 2
+ 4n [oo
(1 KOD
2ndmia (Ko) + Ann (p+ v Ri(0
<
n
n² (mnin(()) - -2 (p+ + v
Plugging Ti and T2 back to (27), and using the eigenvalue lower bound from Lemma 10 (d) yields:
( (1)))((0)))))))))))))))))
4n² (1
(1(()=))) < inf (1 11+p) 4 (1)44((vv (vmp+ + vD)²
mz) wrt D)
PS0
m
m
+ (+ 1
17A0
+ 4nm
p+
Ri(O!²)
m
2 (1-147) K2
4n
+ 222 + V
n2 (2200
2n (p + v k)
39

---

48n z Now we plug in p A
(vm45m vz)
2 (
4n (4 (0!)
4n² (1 uy)
('(O(+ - inf (1 + p)4
+
p=0
dovm
m
m
+ 1+ p)
n1v0
+ 4mny
48
R((0))
n
Aov/m
m
4n7
+2n2(donBB
2n2
48n
1 ) (1 k
Aovm
m
(29)
n?
12200
2n
48n Bx
+ v
Auymm
According to our choice of m:
48
2 255n** 4
m N
+ vv
Xo
A
we know that
48
n7
4nn
Aoym m
m
4n
48nB y
2
2 (0))
n1²
R((0')
davm
16n
488
Ao
2n²
Aaym
m
8
Plugging above inequality back to (29) yields:
R(1011) < inf (1 +p) 4 (s(v/T
By Bg + vi) 2 (4mp )
+ 22 R((01)
m (1 - #7)
p=u
do vo
16n2
4n ( (|K,) Kn
+ do 2 (1 - k7) KID
+ |+ [1+ (1
33,20
R((0)= + (1-2) 1
4n
p
dona
According to the fact that:
-
1
+
1
2a
2
<
1
1
à
2a
2a
2a
we choose p = 37,20
1, and it yields:
8n1
48
x)0;)((00)
1728 R(00))
R((0+1) 5
4
+ vt)
mmm (1 w))
+
3ndo0
An
m
16n
+ (1 1
37/20
1
4n
KD
do 8
(1 - (17) KC
R(00) + 1
8n
1
3
2oon2
31,Ao
8
40

---

Using the fact 17 S n. yields:
do
R(((+1) - 37720
8n
(+
(
(A8dnBB By
+ vv)
(
(An²
(1 (1)))(1)
Au
m
8n [K/
du (1- ( D
31/20
11110
1
R(00)
8n
6n3
3 donz
(y
2
128nm
+ vv
(1- (1-17)(11)
Ao
329m
(1
37:00
ny on
8n
(|KK0)
dn
(1 kEE D
+
R(0*)
8n
8 Ano22
3
Since n² 2 3. we know
adg
ado 8n
Hence we have:
R1(0+11
B y
vo)
128mm (1 - (177) (())
Xo
3mmm
R((0') + 811 ( | + 11) 2 (1 (1-M7) KI)
)
1
97/00
+
4n
2S¹ Aon2
no
R((0)
+
4n
B y
Vv
32n²²
+
2T²²
(2
|||
+ 8
(1 (1- -1)) (1-1))(iD. K...
4n
nido
Ao
3m
g n
Plugging lower bound of m 2
1y Aa
+ vV)
256m
yields:
1( S (1
17Au0 4n
4n
Agy 2
2ny²
(2 K +
)0²)) (1 - m7) 17)Kt RtD D.
do 8
R(00)
+
17.0
24n
Finally, according to inductive hypothesis (I), we plug in the convergence rate for R((0)) and get
R((0+1) S (1
11
R(Oo) + (1 11/00 4n
Σ
n1
1-1-8
(1- 17) nr)* K D
4n
4n
s=0
4n
217² (3 |
+
Ao
)²)
+
+
&
(1 - (1)) (1-17) KtD
11200
24n
8 n2
n1200>
[-1 +. R((0)) + +C
mdo
Σ
1 1-
(1 (1-uy)²(L - w7)* D
4n
4n
==0
4n
211²
(1
|
+ An
2
(1 (1-
17200
1-1 (1 (1- (1-11)((1 - KD) (47)
+
+
17
24n
3 8
112
4n
Now we just need to ensure that
Xgy22
27²
(1
| + 20)²
I C.
24n
We hence choose C as:
4n² (
K
+ do 2
C'
+
24n
3 n
41

---

Hence we proved that:
+ (1-
1
17000 6-s
R(00-1))
1
R((0) +
(1 17) -17) D
4n
4n
==
1700
4nC (1 - 117) KK D
R((b) +
1
4n
17A00
with
X312
4n/² ( K + )
C
24n
B.4 Relations Between Different Predictors
In this section, we are going to relate the predictions of neural network, random feature predictor and kernel OLS predictor.
Lemma 12 (Neural Network Predictor and Random Feature Predictor Coupling). Let ñ By Aoym
V
For Algorithm 2, the following statement holds for any j E [d] and t E [T]:
h//11
$/4
<
1 -
16
3 2
K + 2n²n + 22/nn
Va- (T) + (2Vmn'n + 2//nn) / (2(00)
4n
Sn
4nC (1 - (w))k) D
+ (2Vnn nn + 4v ann)
Ay
11
Proof. Notice the following canonical decomposition:
Nr (a) thj (a)
2/-1 0 0, $6 0: 41+1
Φ. T 0/ + (0++1 Φ. T
00 - %6 T 8/+
Φi [0! - ngl) + (0/+1
T - 11 10 - -b6 -0%
<i'(ot (0) n of (0)) ----nee -n(g!- -V [o + (Di+1 - - 10
0 00) n oz
Rt (0)))
= <a( - ! (a) + (0/4) - Φ. 1/10// 100m1 + no! (vo; - -g))
+ +n o V R: (0)) 0i 0: Rd (0)))
Define (a)) 1i (a) w. (a) and r (ax)
11 1
(a) w. (a) Notice that
H6 V (0.) 0i¹ V oo R0:)
$6
T
(a)
2
Σ
(a)
2 " (a)
>
Σ (aa))i(((s))
n
n i=1
T
2
= =
(a)
Φo - (a,))
i=1
+
T
(a)
(as))
05 T (a) Σ
(((s) relas)
1=1
i=1
42

---

We define the following stacked vector representation
h/41 [k--1 (an1) m. 12411 (arn)) R", F = [re (a1), "., (an)) E R..
Hence we can write the pointwise difference into the following compact form:
27 d (h/ - h ())
h/41 hpf1
D
n
+
( 1+1
T
D2
)0
71
+ 17 / T
(Vo)
RV RO:( - gi)
T2
T T
+ 1]
④
T
Unrolling the recursion to / = 0 yields:
h/41
h141
rf.
[I
2n K k ( .+1
-o! )0/m + 1)
E(1
2n R() $ (V (Vo
< R(OO') g!)
8=0
==0
II
20 Kg
2
KgJ Ki) rs.
==0
Taking spectral norm on both sides yields:
|b/
h
27
$ =
841
n
Ti
2n
+ 17
Σ [I
K
$ f
(Vog (i! g!)
n
A=
T
2n K
2
+ 17
Σ
t-
K K.
==0
Tg
We first bound Ti as follows:
Σ ==0
27
Kg
( s+1
Φ 0
2m Rgj
| 5-1
T
t+1
==0
1
2n
Amiu (KGB)
(
T
& J
n
s=0
1
A0n)
1-8
( s+1
$ )
n
43

---

where we apply triangle inequality and Sauchy-Schwartz inequality. To bound | [ - - -. 0011/1 we evoke (28))
48nBB 2nV (O!)
( (++11 D 10/1
2
+ vz)
V 22)
Ao
mm
m
Now plug in the convergence rate from Theorem 5, and obtain
( .+1
2ny (1
ndaa In
" (B)) +
4nC(1-w7)* 7/0
(y8nB + vi)
2n
S 22/n
vm ( (1-11))&BDD
Ao
vm
Putting pieces together yields:
48nBy
Au ym
T S 2
+
(1
Ag
==0
27/
(1
ado In
R((0) +
4nC(1-p77)KD
7Au
2m vm V (1))
x
+
vm
4n
48nB
vv
Σ (1
A
/ m
An
n
==0
4nC (1 un) K D
R((0)) +
+ V(1 (1- uy)
x
4n
1/
4n
488nBy
Aom y
vτ (1
/ m
An
n
X
) -
11Ao
i
V
(((o))
(1 - -w)) D (1 17)$ mn)+//1 (1--1))k))
n
4n
7
Using the fact that 1
Aon
Ann 4m
and our choice of learning rate such that py S
An
n
4n
we have:
VnAn
48mBB
+ vi)
T <
Vm
Xu
x
(1
2o7
8n
V
4n
4nC (1 11-111 w7)*
(1C(1-97)
+
AoT 8n
((1- m7)
\o1
Xon
7/d0
n
xon
For T2. similarly, we apply triangle and
inequality:
t-
To S Σ
1
T
(V
(e!)
-g))
==0
To bound $ T (Vo: (0!) - gg)
we evoke Lemma 11:
44

---

RR (0!)
2
+ 2n + v ) ) (1- Ke)
- n
Putting the above inequality back to T2 yields:
17/0
6-8
2
3 | +
+ vmm) va - (oy)KaD
T2
S 1)
2n
n
n
2
s=0
51 17
n
$/2
Σ
7
1-3 2
3
| 2n²
[y8nBy
V 1' (m)
(1 M7)&
4n
4n
n
2ov'm m
n
&
16
3
By Aoymm m
V m )
v (1 (1-1))*D
<
1
K
2n
wy)K
4n
Ao
2
For T3, we also apply Cauchy-Schward and get:
77
2 [ Kg)
T3 S
yrs
n
8=0
2
Mo r-a
[[(5 - -k:) ||r=||
n
==
2
Σ
t
11
2'= (p + v V'Va/ (
"
n
where at last step we plug in empirical gram matrix bound from Lemma 10. Now it suffices to plug in bound for (O.)
2
11A0
1 way (1
niA00
Ri(0)) + 4n (1 17)* D
T3
S 1
2m (p- + V m
n ==0
n
4n
17
S 17 2n 2 (p
2
+
V m
Vnn (1
ndo
Σ (1
t
1110
- 2 \/ Ri(()) +
8n
4n (1 -17) D
n
n
n
n,
17200
==0
<4nvTn n
48m By
V m
(1
ndo
)s
8n
R (0') +
8n
4n (1 pr7) k D
do Aoym m
4n
11d0
17A0
Putting pieces together yields:
1//m1
tf.
Vndy mm
48mB
+ Vz)
<
Ao
x
(1
Aom
1
8n
Rii (0%)
+
2o11 V
4n
AnC (1 - (1-1))*
+ (1
1 8n
V (1 - 2D) (1-17)KD
An
Xo"1
11/0
4n
Xon
+
1
n7
4n
Ao
16
3
2
K
- 2n
48nBB
m
V m
2/
V(1 - DD) D
48 y
nao
8n
v (R)(
8n
4n (1 - (1)) K D
+
4m
(1
+
Aovm
4n
11i0
noo
Let 7 =
+
45

---

(1- 77000
& 8n
b//41
- 4/nn
(0%)
4n
4n
Ao
4n
AnC/ (1 - pr)) K D
(1
77u0 An
1 8n
v (1 u7) D
+
Ao
11A00
Xo
+ (1
n7
16
3 2
K
+ 2n²n
(1-Wa)
4n
Ao
+ 4y/nn
(1-
17
8n
V
(0') +
8n
AnC (1 - 17) K D
4n
An
To
1120
1 4n
n
16
3
| + 2n²²n + 2//nn
Va (1-w))kD + (2 + 2/7nn) v (R(00)
Ao
2
8n
4nC (1 - -y) D
+ (2ynn nu + dk/nn))
1/
Lemma 13 (Neural network parameter and RF parameter coupling). For Algorithm 2, the following statement holds for any j E [d] and E [T]:
|o:
n X
48n y
n
y 48n
0o
Aovm m
m
X
Aoy m
m
48n
n
(1
) D
(1 1/ 2 D
+0
1,772
(Amax Aa)
\oym
m
XB
Ao
Proof. According to updating rule of neural network and random feature predictor, we have
0/ 0/+1
0/4
0 - 0. - n(g! v 0:
Rog R
0 0f =
2
(
((()) - nlg! (o:
0: 0
2
Σ
(o(()))((a))
(/0())))) - nílg Ro²
1
==1
0:
0.
2
((.)).) {b(a)))r((aa)
- Σ (r))((()(aa)) - r: (a:)) - 7// Vo og R(O:))
2
1
1-1
n
2
2 (b))))(h - n::.') 1/(3 Vo; R¹ ((())
0
0
x (a:) bb((:))
1|
Now taking norm on both side yields:
10/_
8//1
2 |0: 0:| + 17
/ + )r
+n
2
$
(a.)) b
tn gi Vo R(
7
n
Ti
T2
Ts
46

---

For TT:
Ti 1 (0) - 2/) r2:
n(p + V L
Wav Ri)
m
n7o0" (1-
4n (1 un) k D
s synlo v m
R Ri(0)) +
Am
11a0
where we plug in results from Lemma 10 and Theorem For T2:
T2 <
$
hn
h
16
V(- 1(1- # (2Vrn²ñ + 2/nnū) v /R(00)
S
vn
K + 2n²n + 22/nnnn
4n
Au
2
8n
4nC (1 - u*)*
+ v (2v/rñ + vnn)
Ag
1120
For T3, evoke Lemma 11:
Ta S 2 KT) s $2/11
nia (1 /17) D.
4n
Putting pieces together we have:
1.+1
0++1/l
= -110% 0:
+
21
n(p
V. m
/ Viyl
(1-
1yAo
R((n))
4n (1 w7) D
n
4n1
1120
+ 2m
7/0
16
n
4n
Xn
x
((
3
K|
|| + 2n + 2/nnn
(1-117) + (2Vnn?n + 22/an)) VR(00)
2
2nj Vn (2vnn + 4 /nnn)
8n
4nC (1 ( D
+
n
Ao
nndo
20
172u
+
2//
(1
(.)) k D.
n
An
47

---

Conducting telescoping sum yields:
|.+1
0++1|
20
1+1
V
n
R( + 4nC (1 - po) K D
VV
(p+
V
n
m
4n
1/00
=
27 1+
1720
16
Vn
1
4n
Ao
8 0
|K|| + 2n + 2/nnn)
Va- (1-mee (1--,7)KD. D (2Vinin + 2Vinm) v R((0))
x
2m 1+1
8n
4nC' (1 mn)* t
(2n + n))
11
Ao
1/.0
27
11/0
2 (1
)²(1 - -17)
4n
8=0
16
V R((00)
+nI (Vn+ + (2nn + 4n²")
16)
4nC (1 - pry) K D
S nnv
Ao
to
1720
256
3
K
-2 2/mm²)
(1-
(yy- K D + (2 + 2/nnn) /R((.)
X
+ Ao
32
V
(1
17)(K D
Recall that ń
18nB,
and
C
Agn 24n
+
4ny² (1]K]+++ )²
gnd
we conclude that:
|0c+1 0z+1| 1|?
n2
48nBB
48
2 n n(1 - 2) D 17²
(Amax + \o)2
0
222
Amym
m
Aovmm
m
1110
112
48nB
1 D
48nBy
(1- (1-1) 1)
0
n
(1
n
X
to m
m
k
Au v m
m
26
n
48m By
(88nBB
2 n (1
1 J D
0
3T2
+
(Amax + 2o)2
13
Aaym m
m
\oym
m
XB
n
48nBB y
v
2
(1
D
+0
+
Xg
Aoym m
m
Theorem 6. For Algorithm 2, the following statement holds true for any j E [d]. t E [2]]
(N((())
-h
h1)))o(aa))) 2
sup GEAN
2
48nBy Aoymm
48nBy Ao
+ /v)2 +0
n22
/48nB,
do Amym
V m
V
+
no
A1
(88n
do \ m
m
+0
12222
B8
+
V
2 n (1
) D
(Amax + A0) +
(1
1 K D
No Am m
m
X
X
If we choose K 2 log 1 p
then we have:
x
(ktp(a)) N (ai) 2 2 maxx {
(maxx
(olly(n)) polys(n)) }).
sup aEAN
vm m
48

---

Proof. We consider the following canonical decomposition:
(a) 1 S (1((a)) nit (a)) 2
+ 2(11 (1t h (a)
(15
For the first term, we
1/ - hī (a)l
2 0((() To, - -b(a) 0/]l + ( o/)l"
S (Vmp + vv)² +0
n²
488BB
+ V m
V
+ no (48n
+V V
10
Aavm m
X Aavm
+0 nT'r2 18 Auvmm
nz (1
1 D
(1- )
x D
(Amax + xo)² +
m
m
X
where we plug in Proposition 5 (e) to bound
(
( T 0 and use Lemma 13 to
bound [ (0)
8/)l_ Plugging in p=
will complete bounding first term: Aoym
18mBy
[(((a) 11 (c))
2 B dov'm
48 Ao
n2
48n
n
48n
2
+ 2 +0
+
Aov'm
Aoymm
m
48n
n
(1
(1
1 D
+ +0
(Amax
+ 2n)² +
Aaymm
m
X
X
For the second term, we use the intermediate result from [21]
| cf (a)
- h, kls (a)l s
V
By
24n
m Ao
do
2
Lemma 14 (Approximation of Lipschitz functions on the ball [2, Proposition 6)). For R larger than
constant that depends only on N. for any function 8 R.N + lK such that for all x, x E B.
supxEby If* S A and fx((x) - f*)) S A||x &llg there exists h E H. such that ||l S R and
VR
R A
sup [f* - h(x)) S A(R), (1
A(R) = cA
In
A
Theorem 7 ([32, Theorem 11), Fet = {f gd-1 + b0 for some < cc. Then with probability at least - -", v 0, for all f E F simultaneously
1111 < I1 +0 (11/11 (R(F))
+ by + (F)
by
n
where the worst-case empirical Rademacher complexity is defined as
A(F
sup
Eg sup Σ cxf(xs))
lid (E1,..., En ~ unif(=1))
X....... Na 634-1
JEF
Lemma 15. [Rademacher complexity of kernel predictor class [3] Lemma 22] Consider the following function class with bounded RKHS norm:
F= F=
h(xx) h(x)= = E cx,(x, x.) : H. ||ll S B } ==(b(x)=
Then its empirical Rademacher complexity is bounded by:
B
R(FF <
Vn
49

---

Lemma 16 (Excess risk of virtual KLS predictor learnt on optimal KLS approximator). Let hil be the optimal approximator of f*J in RKHS, and ht k (a) be KLS predictor trained by GD on sample { bl (a:) Then the following excess risk bound holds with probability at least 5:=
E
Wlls ut1 (a) - (a) S
<(1 2n87
+0
((1 278n
(1-2)i1)
R
R
n
72
71
Y1
Proof. Given a fixed function h with k I R. we consider the following class:
Æ= [(xx) = h(xx h (xx: : h E H. || S B}
According to constant shift property of Rademacher complexity [33] and Lemma 15, know
B
v
R
)(H)
0O
+
vn
vn
According to Theorem 7, we have
E
h kla (a)
h (a)))((a)
||²
2
1
1
R
klas (as) - -illlss Hass) 1
n2
+0 kls. (axs) n h (axi) /|?
B + VR
(B + VR)²
v)
+
Vn
n2
n
n2
Now, it suffices to bound (i) empirical risk term n 1==1
((an((aa))) | (ax))
hel (axi)
|| and (ii) RKHS
norm of i, kla.j
For (i), we define R. = 1 >i=1 Ficcas (ax:) (a.)) 11 kk (ai)) and recall the updating rule of kernel
OLS predictor:
klaj h t+1
hil Kc[+1 Kila = Ke/ - K 217 K T (h
kla. (h
- h
I 21 K KTK K
(hiple h
n
I 21 K T K
(hible Ribhhdd.
Hence we know that:
R4t1
2n (I-2
KK
Ro.
n
iii) RKHS norm of h K
kls
I
27 K
y. K-1
76
n
21 K
I
K 'c.
n
1
I
21 K
|| |K-'
n2
2m K
| 7
5 SV.
n
50

---

Lemma 17. [21, Lemma 8] Let ft Ex be GD-trained KLS predictors (as discussed in appendix B.2) given training samples (x,: 1-) and (x,, J..9ii==1 respectively, where yi = -xxx), + E, and y; l(xx)) + E with [ I R characterized by lemma 14. Then, with A (t) defined in lemma 14, for any E N,
11 11 < A(R)
B.5 Proof of Theorem 3
Proof. We notice the following risk decomposition:
11)((a)) wi(a)
v 4 (x) - 117 2 (a))] + +4B 1 (x) - 1 (o)) (a=) 2
polys(1) 4E 1,l (a) h (a)
(a)
+ +4E A [abs. - -a)_a)
(olyy(n)
))
S 0
max
1 X1
A(R)² +
v'm
m
Vn
2
T
v A
R
x
VR A
A
71
n2
where respectively we plug in the NN-KLS coupling result (Theorem 6). Lemma 17, excess risk of
KLS (Lemmaa 16) and approximation error of RKHS to Lipschitz function (Lemma 14), By choosing
log(n)) and optimizing over R, we recover the rate: m 2 O(n 8+ 2+, ), T 2 NA
w - (a) S 0 0A'n six).
Hence by summing over all coordinates j E [d]] we conclude the result:
E (() - - (xx) < 0o (A +
where in our case lemma implies = H² Finally we lower bound Ao using [29, Theorem 3.2] which implies that Åu (polylog(n, N))) with probability at least 1 - - n for distribution on a simplex.
51

---

C Regret Analysis of Algorithm 4
In this section, we going provide the proof for Theorem 4. Let first introduce the following definitions that will be used in our proof.
Definition 2 (Covering and Packing Numbers). An E-cover of set S w.r.t some metric || is set {xi...., x,} S such that for each
there exists E (1....,70 n) such that ||x - x S e. The covering number (S,,,, E, -I] is the smallest cardinality of s-cover. An e-packing of a set S w.r.t. some metric || is a set {xq....,x",, xmm C such that for any distinct i. E m......m. we have The packing number e,
||<] xXIl >
is the largest cardinality of a E-packing.
is well known that M(S, 2e, -1- S (S,, e, I1 II) S M(S,e, e, -I)-
Definition 3 (Metric dimension). The metric spuce (I, I1) had metric dimension d, if there exists constant Ca such that for all & > 0, X' has an E-cover at most Cae-d.
Proof. We start from the standard analysis framework for online an-paaramttic regression [13, 18, 20]. Let S, be the value of the variable S at the end of time t. Hence S. Ø. The functions Te : X + (1....,t) for 1.2.... map each data point its closest center (in norm || in S,-1,
T Ta = arg arg ||a - a,l if S; # otherwise.
t
The set T3 contain all data points ar that at time t belonged to the ball with center a, and radius Et.
Tg = ||a, a,ll S Et, S.....T).
Finally, w is the best fixed prediction for all examples (as, w.) such that t E To.
w arg min
E
Σ W.
(30)
[T&l EET.
WEW
SET.
We proceed by decomposing the regret into estimation and approximation cumulative errors,
T
T
RT( ((((,)) (4(w.))4(((())))
Σ
(wa()))) Σ (e -
1=1
1=1
The estimation term is bounded
Σ (((w)) le (W (Wwr((a)))
=
= EE Σ
((w))) - la (((w))
BE EE,,
We study the cumulative regret within a fixed ball Tg. We use (t(t) to denote the set of all points belong to ball with center Wa, at time t. That is,
(t) = {j j Ta.J tt. One property of (() is that, if x, E T.. then [t]( (Ta(t 1)1 + 1. We further define
W.
[.(0] Σ (0) w (at). According to [6, Lemma 3.1]. we have:
Σ (w.) ((w,))
Σ (e(w.)) (we))
LET.
1E2.
Recall that W. [T] Σ (ETT(I-1) W,. Then,
1
(l,, (.(w))] S 4D E
ww (w:)ll
4
1 [T,l 1)I
Σ 11 [T((i]
Σ w'(
(ET-(I-1)
SETS(()
< 4D
1
Σ
1(Z, = () ww
Tt,(t 1)
(tT,(t-1)
+ 4DE
1
Σ
H1Z, = 1)
Σ w'a)))
[T. 1)]
[t(t)]
(ET,(I-1)
jET,()
52

---

According to the convergence rate of GD on strongly-convex and smooth function, the first term is bounded by p(1 ) D. For second term:
1
112, = (a(a))
Σ w (a,)) JET,
T1(1- 1)1
[T,(1]
(t-,(
[12;=1 =
E
Σ
[T,(t]] w((a))
[t(t-1]] 1)]
(tT,(t-1)
( =
Σ E2,
w wa(a))
1)l
[T,(t)
(1-1
Σ
('[Ta( ("iTs(t- T.))
+ +11 p) [T,(t] D
(tT,(
+11 (1--)) D
P (T))
where at the second last step we use the fact that [T,(t)] [T,(t +1
(.w.) (o(w)) S
Σ
Le(w:) - (e(w))
TT.
tET.
D -
S 4D
PTT(00]
EET,
We further sum above statement over 8 Sr:
E Σ Σ ((w)) - (e(w:)
SP Σ
Im([T.]) + +1- - 2 D)
LEST TET,
SEST
s [n(T)) + - p)--p)DD--- + 4pDT(1 1 9
The first inequality is known bound on the regret under square loss [6. page 43]. We upper bound the size of the final packing ST as
|rrl S M(B.er, & Cn EN
Thus,
Σ ((((w))) - le( (Win PCNN7N (n( + +1 p)DD 4pDT(1 -
1
1
(31)
Next, bound the approximation term. Using (30) have
Σ (e((ttao)
-
(32)
t=1
Note that E, is 4D-Lisschitz because yr, & E Bz(D). Hence.
& (f(a()()))) )) - (((aa)) S 4D (amtta) f s(xx)) & 4Dw" 1D*'||axx(())) call S 4Ds
by x^ -ippschiitzesss of f. Thus, putting all together.
Σ (ww.) - Σ ellf(a)) s Ch + +4D** Σ
53

---

and recalling that ex = 1 T-N
-IN we have
E
(
T
--
dr (1+1) 1
22T
N
t=1
which completes the proof.
54


Reviews:
[{"review_id": "AiRnQ4EOh0", "reviewer": "Reviewer_u3ZP", "summary": "\nSummary:\nThe paper addresses the problem of multi-source multi-target domain adaptation, where the goal is to learn a model from multiple sources in such a way that it performs well on a new target distribution. The context for this problem includes scenarios like learning from data collected from various sources (e.g., crowdsourcing) or in distributed systems with highly heterogeneous data. The two main unsolved problems in this context are: 1) how to estimate the optimal mixture of sources for a given target domain, and 2) how to efficiently solve empirical risk minimization for each target domain when there are numerous target domains, which can be computationally expensive. The paper proposes solutions to both of these problems using convex-nonconcave compositional minimax and overparameterized neural networks with provable guarantees. Additionally, an online algorithm for predicting parameters for new models given mixing coefficients is proposed.", "questions": "How does the proposed convex-nonconcave compositional minimax approach differ from existing methods used for mixture weight estimation?\n\nCan you provide more details on the theoretical guarantees of the proposed overparameterized neural network approach for empirical risk minimization and its relationship to the specific problem context?\n\nAre there any assumptions made about the data distribution or source/target domains that could limit the generalizability of the proposed methods?\n\nHow does the proposed method perform in practice?", "limitations": "Limited Empirical Validation: The lack of empirical evaluation or real-world case studies might raise questions about the practical effectiveness and applicability of the proposed methods to real-world scenarios.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Theoretical Contributions: The paper proposes novel approaches to tackle the problems of mixture weight estimation and empirical risk minimization, utilizing convex-nonconcave compositional minimax and overparameterized neural networks, respectively. These contributions are supported with provable guarantees, which add rigor to the proposed methods.\n\nEfficiency and Scalability: The paper emphasizes the efficiency of the proposed algorithms, particularly for mixture weight estimation and empirical risk minimization for multiple target domains. The avoidance of individual ERM for each target domain in certain cases helps reduce computational overhead.\n\n", "weaknesses": "\n\nComplexity: The proposed methods, such as convex-nonconcave compositional minimax and overparameterized neural networks, might be complex and difficult to implement for practitioners who are not familiar with these advanced techniques.\n\nApplicability to All Domains: The paper may not clearly address the limitations or specific domains where the proposed techniques might not be directly applicable or might require additional adjustments.\n\nEmpirical Evaluation: The paper lacks details about empirical evaluations, such as experiments on real datasets or comparisons with other state-of-the-art methods. This could raise concerns about the practical effectiveness of the proposed algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments! We will try to address your concerns as follows.\n\n**Complexity to implement algorithm**\nOur mixture weight estimation algorithm is a single loop primal-dual algorithm, which is widely used in minimax optimization and easy to implement. The only additional effort is to implement correction step for compositional term, which is also easy-implementable by maintaining an auxilliary variable. In our provided PDF, we implement the algorithm and show the convergence to a desired weights (Figure.1 in PDF). As for the algorithm 2, it is indeed a very common neural network model training, and can be implemented by few lines of Pytorch code.\n\n**Applicability to All Domains**\nOur algorithm can automatically find the good mixture weights, given any source domains. Hence, our algorithm can work well in any multi-source learning scenario. Our provided experiments also validate the effectiveness of our algorithm.\n\n**Empirical Evaluation** As we mentioned in global rebuttal, we provide the experiments in the rebuttal pdf.\n\n\n**Comparison with existing methods used for mixture weight estimation**\n[KL19]  also propose to optimize similar objective as ours to get mixture weight, but they do not give a practical algorithm, nor the rigorous convergence guarantee.  [MMR+21]  propose to sample many mixture weights on simplex, then do ERM to get multiple candidate target models, and pick the best one who has the smallest target empirical risk as final solution. The drawback of their method is, when the dimension of the simplex is very high, you may need to sample exponentially many weights to cover the whole simplex to some accuracy. \n\n\n\n**Can you provide more details on the theoretical guarantees of the proposed overparameterized neural network approach for empirical risk minimization and its relationship to the specific problem context?**\n \nGuarantee for minimizing empirical risk of an overparameterized neural network (Theorem 3) is based on a standard Neural Tangent Kernel (NTK) approximation argument [JGH18, BMR21], namely we use the key fact that predictions made by a GD-trained overparameterized neural network are close to those made by a Kernel Least-Squares (KLS) predictor (given that the width of the network is polynomial in $n/d$).\nThe core idea has been recently explored in many papers, for instance,  [DLL+19, OS20, BMR21].\n\nIn addition to that, in our work we need to establish that such neural networks are able to learn Lipschitz vector-valued target functions with iteratively refined labels -- which in the context of our paper means that given a mixture weight, a GD-trained neural network can output parameters for a target task.\n  \nHere we extend their proof to vector-valued functions and inexact label observation setting, by analyzing the dynamic of a bi-level optimization.\n\n**Are there any assumptions made about the data distribution or source/target domains that could limit the generalizability of the proposed methods?**\nWe do not make any assumption on data distribution. Our proposed mixture weight estimation algorithm can automatically adapt to different heterogeneity level, since it takes the distributions discrepancy into account.\n\n[BMR21] P. L. Bartlett, A. Montanari, and A. Rakhlin. Deep learning: a statistical viewpoint. Acta\nNumerica, 2021.\n\n[DLL+19] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds\nglobal minima of deep neural networks. In International Conference on Machine Learning,\npages 1675–1685. PMLR, 2019.\n\n[JGH18] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: convergence and generalization\nin neural networks. In Conference on Neural Information Processing Systems, 2018.\n[KKS21] M. Konobeev, I. Kuzborskij, and Cs. Szepesv ́ari. A Distribution-dependent Analysis of Meta\nLearning. In International Conference on Machine Learing (ICML), 2021.\n\n[KL19] N. Konstantinov and C. H. Lampert. Robust learning from untrusted sources. In Interna-\ntional Conference on Machine Learing (ICML), pages 3488–3498. PMLR, 2019.\n\n[KS22] I. Kuzborskij and Cs. Szepesv ́ari. Learning lipschitz functions by gd-trained shallow overpa-\nrameterized relu neural networks. arXiv:2212.13848, 2022.\n\n[MJ05] A. Maurer and T. Jaakkola. Algorithmic stability and meta-learning. Journal of Machine\nLearning Research, 6(6), 2005.\n\n[MMR+21] Y. Mansour, M. Mohri, J. Ro, A. T. Suresh, and K. Wu. A theory of multiple-source\nadaptation with limited target labeled data. In Arindam Banerjee and Kenji Fukumizu,\neditors, International Conference on Artificial Intelligence and Statistics (AISTATS), volume\n130 of Proceedings of Machine Learning Research, pages 2332–2340. PMLR, 13–15 Apr 2021.\n\n [OS20] S. Oymak and M. Soltanolkotabi. Toward moderate overparameterization: Global conver-\ngence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in\nInformation Theory, 1(1):84–105, 2020.\n"}, {"review_id": "a9lQJON4Si", "reviewer": "Reviewer_9T2K", "summary": "Authors propose a new way to compute mixture coefficients for combining multiple empirical risk minimization objectives (w.r.t. different sources in domain adaptation) in a way that takes into account the relation to a new target domain. As an application, the authors consider the multi-source multi-target domain adaptation scenario and solve it by predicting (the weights of) new target classifiers from the mixture weights.", "questions": "- For computing $\\alpha$ in Eq. (1), one needs to compute differences in empirical risks (on target vs. source datasets). Errors in this difference seem to aggregate to errors in the solution for $\\alpha$. How does this effect the final prediction of the target model from mixture weights?\n- In meta-learning there is the approach of representing novel domains by \"meta-features\" and then map these meta-features to the hyper-parameters of novel target domains. The hyper-parameters can also be model weights, as in your case given by $w^\\ast(\\alpha)$ cited in the introducion. Consequently, the theory of meta-learning should apply also to your setting. How does this theory, e.g. [1], compare to your convergence results? Can the same phase transition be observed assuming the mixture weights are exact?\n\n[1] https://www.jmlr.org/papers/volume6/maurer05a/maurer05a.pdf\n\n------------------------------\nAfter rebuttal: My questions are addressed. I increase my score by 2.", "limitations": "- Influence of error of weight estimation should be discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The considered phase transition is interesting.\n- The weights could be provided by a domain expert who is, e.g., certain about a physical relation between the domains.\n- Convergence of the algorithm as extension of [31] is interesting.\n", "weaknesses": "- No empirical intuition if the algorithm can be implemented with reasonable effort. I consider the result as of purely theoretical interest.\n- The error in the computation of the weights $\\alpha_i$ is not taken into account in the error rates results. This could dominate the convergence rates results.\n- My impression is that, if we are able to solve Eq. (1) efficiently, then also a separate training for each target domain should give us a comperable accuracy. I don't see any argument, neither theoretical or practical, which guarantees that the proposed lagorithm improves the separate learning (which is possible with labels in the target domain).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments! We will try to address your concerns as follows.\n\n**No empirical intuition if the algorithm can be implemented with reasonable effort**\nWe implement our Algorithm 1 and provide results on MNIST dataset. It turns out the mixing parameter output by our algorithm yields a good model which can outperform naive ERM model or purely target domain learnt model.\n\n**The error in the computation of the weights**\nWe assume you mean the error between the output alpha of Algorithm 1 and optimal solution to objective Eq.2. We cannot characterize this error since it is an convex-nonconcave problem, showing the convergence to global optimal point is NP-hard.\n\n**The separate learning on target domain**\nIn practice, the target domain usually has very few labeled data, and hence learning solely on target domain will not yield a well-generalized model. Our experiment in PDF, Table.2 also validates this argument. \n\n**How does errors in the difference of empirical risks affect alpha**\n\n\nMaximizing the inner level of the difference of empirical risk is a non-concave problem, which cannot be exactly solved. Hence, we say that the whole problem of (1) is convex-nonconcave. Solving a convex-nonconcave minimax problem is NP-hard, so we can only provide a convergence to the stationary point. Since we cannot give a guarantee of the output alpha versus the global optimal alpha of (1), we cannot characterize the how good our output model is, compared to the model learnt under optimal alpha.\n\n**Comparison to meta-learning paper of [1]**\n\nThank you for pointing out this interesting relationship.\n[1] analyzes source aggregation scheme (CP-Regression) where feature vector for a new task is formed from predictions of models trained on source datasets.\nIndeed, one could imagine obtaining predictor for N+1'th task using this approach.\n\nThat said,  [1] only shows that the generalization gap, that is the difference between risk and empirical risk, can be controlled using such a scheme.\nTherefore, their result does not say anything about how close such a solution is to the best possible on the target problem.\nIn fact, achieving the best possible performance on the target problem might require a very different algorithm: For instance,  [KKS21]  show lower bounds for the meta-learning in linear case, which suggest that aggregation as in CP-Regression is a suboptimal because it does not take into account task covariance.\n\nIn our work we design an algorithm (solving Eq. (1) + solving eq.\\ in panel at the end of page 2) which in the best case achieves the best possible performance on target problem.\nThis is because our proposed algorithm is designed from the start to directly minimize the bound the gap between the risk and the best possible risk on the target task.\n\n[KKS21] M. Konobeev, I. Kuzborskij, and Cs. Szepesv ́ari. A Distribution-dependent Analysis of Meta\nLearning. In International Conference on Machine Learing (ICML), 2021\n"}, {"review_id": "rOjiGLnyb0", "reviewer": "Reviewer_3rHn", "summary": "This paper is about the multi-source multi-target domain adaptation problem. The authors formulate a minimax algorithm to find the mixture weights of source domains. Furthermore, the authors extend it to the scenario of multi-target domains and introduce the co-component ERM problem. For this problem, this paper proposes algorithms to efficiently solve co-component ERM problems, in offline and online fashions.", "questions": "As for the minimax optimization, in Eq.(1) and Eq.(2), why are the model/hypothesis parameters $\\omega$ to maximize the difference between the target and source domain? Should it be the minimization?", "limitations": "No potential negative societal impact is found in this work.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper extensively and theoretically studied the domain adaptation problem from the minimax optimization perspective. \n\nThe paper gives the convergence analysis of the proposed algorithms.\n\nFor the multi-target domain scenario, the authors provide solutions to both the offline and online settings. The solution is more efficient than training each target domain adaptation independently. ", "weaknesses": "This paper is fully theoretical. The research focus of this paper, i.e., domain adaptation, has many open benchmark datasets and thus it would be better to experimentally evaluate the proposed methods. \n\nIn line 148, it is mentioned that a deterministic algorithm exists in the literature, while this paper is focused on the stochastic one. It would be good to elaborate more on the benefits of the stochastic one and meanwhile experimental compare them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments! We will try to address your concerns as follows.\n\n**No experiments**\n\nAs we mentioned in global answer, we provide experiments with two layer MLP on MNIST dataset in rebuttal pdf.\n\n**Comparison with deterministic convex-nonconcave optimization**\nIn Xu et al 2023, they achieves convergence rate of $O(\\kappa_F^2/\\epsilon^2)$ which is faster than ours $O(\\kappa_F^4/\\epsilon^4)$. \nHowever, the problem of the deterministic algorithm is that, in practice it is too expensive to compute the full gradient, and hard to implement since we do not have enough memory to directly compute full-batch gradient.\n\n**Why use maximization over hypothesis space in Eq.1 and Eq.2**\nWe use the maximization over hypothesis space is because our bound in Theorem 1 is a uniform convergence bound, which holds for every hypothesis in the class $\\mathcal{H}$.\n\n "}, {"review_id": "FfibQ0Q0dI", "reviewer": "Reviewer_T5Nt", "summary": "Authors formulate the problem of optimizing mixture weights given the target domain as a compositional convex-concave minimax optimization problem. Then, they propose a stochastic descent ascent algorithm for solving the problem, which improves upon previous method of [31] by allowing stochastic updates. Then, authors address the second problem of: given a large number of target domain distributions, how to efficiently find model weights for all of target distributions? This is discussed in both offline and online setting. In the offline setting, a two-layer ReLU neural network is trained to output model weights; the model is essentially a \"hypernetwork\" that outputs model weights. In the online setting, nonparametric online regression method is adapted for the problem. ", "questions": "The offline version of the algorithm (Section 3.1) is quite different from the online version of the algorithm (Section 3.2). Would it be meaningful to compare them against each other? For ex, the offline version of the algorithm could be applied to online setting by occasionally computing the label, and the online version of the algorithm could be applied to offline setting as a baseline?\n\nIn line 139, two relaxations in 139-144 are explained as standard. But within which literature are these standard? Can authors provide references for such relaxations? \n\nCan stochastic versions of the Algorithm 2 exist (in terms of both $i$ and data points), which can alleviate the dependency on $M$?", "limitations": "What are alternative formulations for mixture weight estimation (1), and how would convex-nonconcave formulation compare against them? Practically, wouldn't it be too pessimistic to consider the supremum over $\\mathcal{H}$?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Authors identify an important instance of a convex-nonconcave minimax problem. The learning of mixture weights has become both theoretically and empirically important topic of research. For example, methods like Group DRO (Sagawa et al https://arxiv.org/abs/1911.08731 ) and DoReMi (Xie et al, https://arxiv.org/abs/2305.10429 ) have been drawing attention. The reduction of this learning problem to an abstract convex-nonconcave optimization problem will facilitate the adoption of techniques from a broader optimization literature.\n\nAuthors also push the state of the art on convex-nonconcave minimax problem by developing a stochastic version of the algorithm, adopting recently developed techniques such as stochastic corrected gradients.", "weaknesses": "The first half of the paper (mixture weight optimization) and the second half (model weight prediction) are related, but the connection is not very strong. These two ideas could've made good two separate papers. While making these results a single paper made this paper very rich with technical content, but on the other hand, readers of the main body of the paper shall learn much less than what they would with two separate papers. The rationale of authors seems to be that mixture weights for the second problem could be found from the algorithm from first half, but in this case, we already know model weights; thus, the second problem is not very well motivated from the first problem.\n\nThere is no numerical experiments in this paper, and hence results in the paper are not numerically validated. Also, this makes the practical utility of proposed algorithms less clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments! We will try to address your concerns as follows.\n\n**The connection between two parts of the paper**\nWe agree with you that the two parts of the paper already have their own independent interests. The reason we put them into one paper is that the two parts put together solved the multi-source multi-target domain adaptation problems, which is a complete story. \n\n**No experiments**\nAs we mentioned in global answer, we provide experiments with two layer MLP on MNIST dataset in rebuttal pdf.\n\n**The two relaxations**\nOur first relaxation is relaxing absolute value by $\\sqrt{x^2+c}$, which is used in non-smooth optimization paper, for example [CLY23]. Our second relaxation is similar to relaxing the l2 norm to squred l2 norm, which is widely used in practice, when we wish to regularize the norm of the model.\n\n**Can stochastic versions of the Algorithm 2 exist (in terms of both \n and data points), which can alleviate the dependency on M\n?**\nThanks for raising this interesting point. We believe this is feasible, by enabling the sampling idea in the dynamic of Algorithm 2. We will seriously consider it as a promising follow-up work.\n\n**Alternative formulations for mixture weight estimation.**\nTo our best knowledge, optimizing Eq.1 is the only mixture weight estimation method with theoretical support. However, we believe there must be other ways to optimize for mixture weights, which we leave as promising open problem.\n\n**Would it be too pessimistic to consider the supremum over whole hyothesis class?**\nThe supremum over hypothesis class is used to achieve uniform convergence generalization bound, but we also notice that there are some localization technique, e.g., local Rademacher complexity that could enable us to do finer generalization analysis by studying the subset of hypotheses with small risk. In domain adaptation field, a localized discrepancy measure is proposed by zhang2020localized. We believe applying this idea to multi-source learning setting will be a very interesting open problem.\n\n[CLY23] Chen, Xiaojun, Lingfeng Niu, and Yaxiang Yuan. \"Optimality conditions and a smoothing trust region newton method for nonlipschitz optimization.\" SIAM Journal on Optimization 23.3 (2013): 1528-1552."}, {"review_id": "585E0TdXsp", "reviewer": "Reviewer_Ety2", "summary": "This paper motivates the mixture weight estimation problem using Multi-source Multi-target Domain Adaptation problem. More specifically, this paper considers how to estimate the optimal mixture of sources, given a target domain; also, when there are multiple target domains, how to solve empirical risk minimization (ERM) for each target using a possibly unique mixture of data sources in a computationally efficient manner. This paper tackles both problems by constructing new efficient algorithms with a convergence guarantee.", "questions": "I appreciate the theoretical contribution made in the paper by analyzing the convergence of the proposed stochastic corrected gradient descent ascent algorithm. However, the current way of presenting these results is nothing but motivating the specific convex-nonconcave minimax problem using a contrived application of M2DA, which seems to be quite off. I would suggest the authors revise the paper by focusing on the theoretical contribution made to the convex-nonconcave minimax problem considered in eq (2) and the co-component ERM problems in eq. (3), which are interesting in their own right. However, this may require a significant rewrite of the paper and even a change in the title.", "limitations": "There are no experimental results to verify the effectiveness of the proposed algorithm, not even on synthetic data.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper provides a rigorous theoretical analysis of the optimization algorithm proposed in the paper and considers both offline and online settings for the problem.", "weaknesses": "This paper focuses more on the theoretical analysis of a specific optimization problem instead of addressing the Multi-source Multi-target Domain Adaptation (M2DA) problem.\n\n1. The bound in Theorem 1 can be quite loose; therefore, minimizing the right-hand side does not necessarily result in good weights in the target domain. As the right-hand side of this bound is minimized using empirical data, will there be an extra overfitting issue? Is there a way to bound this gap?\n\n2. If some training data from the target domain is available, i.e., $\\hat{\\mathcal{T}}$, why not use these target data in the training of $h$ so that you have N+1 dimensional domain weights?\n\n3. The relaxation from (1) to (2) seems arbitrary, especially the removal of the concave function of the square root.\n\n4. There are no experimental results to verify the effectiveness of the proposed algorithm, not even on synthetic data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**This paper is more like optimization not M2DA paper**\nWe are afraid that we have to respectfully disagree with you on this point. As we mentioned in global rebuttal, the mixing domain type of multi-source learning algorithm typically contains two parts: finding good mixing weights and solving ERM. Our primary goal is to find good mixing weights, and minimax algorithm is just the technique to achieve this. As for the second part of our paper, we consider a novel but very important setting, where there exist multiple target domains to adapt. This setting motivates a new theory topic, co-component ERM, and we provide two possible ways to solve this. \n\n**Theorem 1 can be quite loose, and Eq. 1 uses empirical risk which will result in overfitting**\nFirst, we would argue that Theorem 1 is not loose. It recovers the optimal generalization risk which is subroot in terms of number of samples.  We agree with you that\nEq. 1 is an empirical estimation of RHS of Theorem 1, where we use the empirical risk to replace the population risk in Theorem 1. The difference between empirical risk and population risk can be bounded by Rademacher complexity. We drop the Rademacher complexity terms for two reasons: first, it scales as $\\sqrt{\\frac{1}{m_i}}$, subroot function of number of samples, which is already captured by the second term in Eq. 1. Then, computing Rademacher complexity is usually expensive. Since it is not a dominating term, we drop it for computationally convenience, following [KL19]. Adding the complexity term to our objective, it will still be a convex-nonconcave problem, and our algorithm 1 still works. At last, optimizing with empirical discrepancy is a very standard technique in domain adaptation fields, for example, see [MMA09], [BBCLPV10], [ZLLJ19].\n\n**If some training data from the target domain is available, why not use target data as source as well?**\nWe agree with you that we can use target data as one additional source. Actually, our theory applies to this setting, by just changing the $N$ source to $N+1$ source, and the rest of the analysis still works.\n\n**The relaxation from (1) to (2) seems arbitrary, especially the removal of the concave function of the square root.**\nIndeed the square root term in (1) is convex in alpha, and we relaxed a convex object to strongly convex objective. This operation is quite standard in optimization, e.g., relaxing a l2 norm to squared l2 norm.\n\n**No experiment**\nAs we mentioned in global answer, we provide experiments with two layer MLP on MNIST dataset in rebuttal pdf.\n \n[KL19] N. Konstantinov and C. H. Lampert. Robust learning from untrusted sources. In Interna-\ntional Conference on Machine Learing (ICML), pages 3488–3498. PMLR, 2019\n\n[MMA09] Mansour, Yishay, Mehryar Mohri, and Afshin Rostamizadeh. \"Domain adaptation: Learning bounds and algorithms.\" arXiv preprint arXiv:0902.3430 (2009).\n\n[BBCLPV10] Ben-David, Shai, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. \"A theory of learning from different domains.\" Machine learning 79 (2010): 151-175.\n\n[ZLLJ19] Zhang, Yuchen, Tianle Liu, Mingsheng Long, and Michael Jordan. \"Bridging theory and algorithm for domain adaptation.\" In International conference on machine learning, pp. 7404-7413. PMLR, 2019."}]

Author rebuttal:
We would like to thank all reviewers for their time and constructive comments. We will gladly incorporate the suggestions. 

We observe that reviewers have two primary  concerns: the consistency of the story and the lack of empirical evaluation, which we will try to address as follows.

**The consistency of the story** How to efficiently and effectively learn from multiple source is a longstanding problem in domain adaptation. Among the effort to solve this problem, the most popular and classic method is to learn from the mixture of these sources  [KL19, MMR+21], due to its simplicity to implement, and great theoretical research value. The mixture based multi-source learning method typically contains two phases: **Phase I**, finding the 'good' mixture weight, and **Phase II**, performing ERM on the mixed domains. 

Our work is exactly aimed at proposing an efficient and effective multi-source learning algorithm, by solving the two phases of problem sequentially. The first part of our work provides the first provable algorithm for finding good mixture weight. As a side contribution, from a technical perspective, it has its own value in stochastic and compositional convex-nonconcave problem.

The second part of our work addresses the **Phase II** problem, how to efficiently perform ERM on the mixed domains, when there exists multiple target domains. We cast this problem as *Co-component Empirical Risk Minimization* problem. This problem is never studied before, and we provide two possible provable ways, learning Lipschitz function with two-layer neural network and label efficient online learning approach. We believe there will be many other potential methods, and this paper is an initiative work to inspire the follow-up works.

**The experiments** To demonstrate the effective of our Algorithm 1, we implement it and run experiments on MNIST dataset, with two layer MLP model. 

*Data generation*:  We constructed three distinct groups comprising a total of 10 source domains. The target domain shares the same class distribution as Group 1. The splitting and generation for MNIST non-IID data, including the classes within each group, the number of domains, and the samples per domain, are detailed in Table.1.

*Convergence of mixing parameter*: In Figure.1 (a), we observe that the alpha values for source domains in Group 1 converge to 0.5. This indicates that these domains have positive transfer to target domain. On the other hand, other source domains, which lack overlapping classes with the target domain, have alpha values of zero. This suggests that they provide no contribution during the training process of the target domain. Meanwhile, Figure.1 (b) shows the final alpha values of each source domain at the end of the training process.

*Effectiveness of the learnt mixing parameter*: We evaluated the accuracy using three distinct Error Risk Minimization methods: 1. Weighted ERM using our learnt weights, 2. ERM on averaged loss and 3. ERM solely on target domain, and presented our findings in Table.2. The results indicate that the accuracy achieved using the learned alphas outperforms the other two approaches. Additionally, the accuracy comparisons during training between Learned Alpha and Average Weight are plotted in Figure.2.

[MMR+21] Y. Mansour, M. Mohri, J. Ro, A. T. Suresh, and K. Wu. A theory of multiple-source
adaptation with limited target labeled data. In Arindam Banerjee and Kenji Fukumizu,
editors, International Conference on Artificial Intelligence and Statistics (AISTATS), volume
130 of Proceedings of Machine Learning Research, pages 2332–2340. PMLR, 13–15 Apr 2021.

[KL19] N. Konstantinov and C. H. Lampert. Robust learning from untrusted sources. In Interna-
tional Conference on Machine Learing (ICML), pages 3488–3498. PMLR, 2019


Meta-review: The discussion about this paper has been rich, and the authors convinced some reviewers to raise their scores by providing empirical results that were absent from the initial submission. While doubt has been raised on whether the provided empirical results are sufficient to demonstrate the effectiveness of the proposed method, I consider that the theoretical analysis is extensive enough to justify acceptance. The theoretical contributions to domain adaptation are valuable in bringing new ideas to the community.

The rebuttal also alleviated concerns about "the consistency of the story" and the clarity of a few results. The authors need to thoughtfully incorporate the empirical results and clarify the discussion in the camera-ready version.

In addition to addressing the points raised by the reviewers, I urge the authors to cite peer-reviewed publications instead of the arXiv preprint. [20] is published at COLT, [24] at AISTATS, etc.
Decision: Accept (poster)