Meta Learning for Support Recovery of High-Dimensional Ising Models
Authors: Huiming Xie
Jean Honorio
Venue: Accepted by TMLR ()

Abstract: In this paper, we consider the meta learning problem for estimating the graphs associated with high-dimensional Ising models, using the method of $\ell_1$-regularized logistic regression for neighborhood selection of each node. Our goal is to use the information learned from the auxiliary tasks in the learning of the novel task to reduce its sufficient sample complexity. To this end, we propose a novel generative model as well as an improper estimation method. In our setting, all the tasks are similar in their random model parameters and supports. By pooling all the samples from the auxiliary tasks to improperly estimate a single parameter vector, we can recover the true support union, assumed small in size, with a high probability with a sufficient sample complexity of $n = O(d^3 \log p/K)$ per task, for $K$ tasks of Ising models with $p$ nodes and a maximum neighborhood size $d$. This is very relevant for meta learning where there are many tasks $K = O(d^3 \log p)$, each with very few samples, i.e., $n = O(1)$, in an scenario where multi-task learning fails. We prove a matching information-theoretic lower bound for the necessary number of samples per task, which is $n = \Omega(d^3 \log p/K)$, and thus, our algorithm is minimax optimal. Finally, with the support for the novel task restricted to the estimated support union, we prove that consistent neighborhood selection for the novel task can be obtained with a sufficient sample complexity of $O(d^3 \log d)$. This reduces the original sample complexity of $n = O(d^3 \log p)$ for learning a single task. We also prove a matching information-theoretic lower bound of $\Omega(d^3 \log d)$ for the necessary number of samples.

Published in Transactions on Machine Learning Research (08/2024)
Meta Learning for Support Recovery of High-Dimensional Ising Models
Huiming Xie
rie339@purdue.edt
Deportment of Statistics
Purdue Universily
Jean Honorio
Jhonori@@unmmmlllccom edu.
School of Computing and Information Systems The University of Melbourne
Reviewed on OpenReview: https: ottp::///penreviee net/ forum? id=n40EWuiss)
Abstract
In this paper, we consider the meta learning problem for estimating the graphs associated with high-dimensional Ising models, using the method of f--reullarized logistic regression for neighborhood selection of each node. Our goal to use the information learned from the auxiliary tasks in the learning of the novel task to reduce its sufficient sample complexity. To this end, propose novel generative model as well In our setting, all the lasks are similar in their rundom model parameters and supports. By pooling all the samples from the auxiliary tasks to improperly estimate a single parameter vector, we can recover the true support union, assumed small in size, with a high probability with a sufficient sample complexity of n = Odd log K) per task, for K tasks of Ising models with p nodes and maximum neighborhood size d. This very relevant for meta learning where there are many tasks K O(d togp), each with very few samples, i.e., O(1), in scenario where multi-task learning fails. We prove matching information-theoredt lower bound for the necessary number of samples per task, which is n ((d log K), and thus, our algorithm is minimax optimal. Finally, with the support for the novel task restricted to the estimated support union, we prove that consistent neighborhood selection for the novel task can be obtained with a sufficient sample complexity of Odd log d). This reduces the original sample complexity of = (d log for learning single task. We also prove matching information-theorelia lower bound of (dd log d) for the necessary number of samples.
improper estimation method.
1 Introduction
Markov random fields (MRF) are an important class of probability models that find its applications in a wide variety of fields spanning statistical physics [sing 1925 social network analysis (Snell 1980), computer vision (Geman & Geman 1993) and natural language processing (Manning & Schutze, 1999). A Markov random field an undirected graph where each node represents a random variable, and the graph structure carries certain assumptions about the conditional independence of these random variables. A prototypical example of Markov random field is the Ising model, where the random variables are discrete, and in particular, binary. Several other types of Markov random ficlds can be viewed as general setting of the Ising model Snell 1980 Delecting statistical dependencies, which boils down to estimating the graph structure in the Ising model, is therefore a fundamentally significant problem to solve. Many efforts have been made for the single-task problem, among which Ravikumar et al. (2010) proved that with relatively low computational complexity, consistent model selection can be achieved with a sample size of n = O(d log for a graph of p nodes with maximum neighborhood size d by neighborhood selection for each node using li-regularized
1

---

Published in Transactions on Machine Learning Research (08/2024)
logistic regression. This simple method with theoretically supported reasonable performance has received considerable attention.
In practice, however, one may not be able to obtain as many samples for the high-dimensional settings where both p and can be large. The more common situation in reality is that one has only a few samples for a task; nonetheless, there are usually many related tasks (each with very few samples) of a similar kind. For instance, for an Ising model problem, there could be only n O(1) samples per task for K = O(d logp) tasks. Consider for instance the case of K = 5000 tasks but only a few 2 samples per task. Learning from related tasks has been previously considered in (Trum & Pratt 1998 Nichol et al. 2018). This challenge is also commonly met in the application of other machine learning algorithms (Vilalta & Drissi 2002 Finn
let al. 2017 Vanschoren 2018). One general way to tackle this kind of difficulty is through mela learning Wanschoren 2018), or learning to learn {Lake et al. 2015), where we learn from multiple learning episodes
that oftentimes cover a distribution of related tasks a family of tasks, order to gain some experience for the learning of a novel task (in that family), in the hope of reducing the sample complexity for the latter
(Hospedales et al. 2022.
Meta learning has been widely used in machine learning problems to help increase sample efficiency, but
majority of prior works are experimental in nature, without theoretical guarantees (Lake et al. 2013 Lemke
et al.
2015 Vinyals et al., 2016 Ravi & Larochelle 2017: Finn et al.] 2017 Snell et al. 2017
Grant et al.
2018
Yoon et al.)
2018 Hospedales et al.) 2022). There have been some efforts on building the theoretical
foundation of seeta-learnin, but they only pertain generalization bounds in learning theory (Maurer 2005
Pentina & Lampert
2014 Amit & Meir 2018 Denevi et al.] 2018 Khodak et al.] 2019 H Huang et al. 2020
Tripuraneni et al.
2020 Farid & Majumdar 2027 Chen & Chen 2022 Guan al. 2022) and convergence
rates in optimization (Fallah et al.) 2020 Finn et al. 2019 Khodak et al. 2019 Gao & Sener 2020). In the
above works, performance is only viewed in terms of risks (e.g., misclassification rate, mean squared error)
and not in terms of support recovery. For Markov random fields, there have been some theoretical results for the models associated with Gaussian or sub-Gaussian random vectors, which is a continuous type of Markov random field (Zhang et al. 2021). For discrete lype, or Ising model as its prototype, similar works on mela learning do not exist.
There has been some work on the multi-task learning problem the Ising model [Gonçalves et al. 2015 Guo el al. 2015). Note that there is an intrinsic difference between mulli-lask learning and mela learning, where multi- task learning is learning one model for each of the different K tasks simultaneously while for meta learning we learn a single model from different tasks for the easier learning of a novel task. The challenging situation of having many tasks but only a few samples per task (e.g., K = 5000 tasks each with 2 samples) would also render the multi-task learning method meaningless, as each task cannot be learned individually with these few samples per task.
To the best of our knowledge, are the first to theoretically prove the sufficient sample complexity for the meta learning problem of the Ising model selection. For the Tsing model, we follow the practice of Ravikuman ct al. (2010) in using f f1-regularized logistic regression and converting the model selection problem into one of neig hood selection. Based on this method, for the meta learning problem on Ising models, we propose a novel generative model by introducing randomness to the parameter vectors of the Ising models with reasonable and flexible assumptions for similarity among different tasks, which serves as a good generalization of the metadata for the Ising model, and hence our theoretical results can be applied to wide range of distributions for the parameters in the Ising models under some mild conditions. We also propose an improper estimation method in the meta learning problem for Ising model selection where we pool all the samples from the auxiliary tasks together to estimate a single common parameter vector (see Definition 3.1. rather than estimate an individual parameter vector for each auxiliary task, and then we recover the support union from the single common parameter vector. Next, we estimate the parameter vector for the novel task by restricting its support in the estimated support union. While the sample complexity of multi-task learning is n n= (ce log p) (Guo et al. 2015). we have successfully shown that to learn the support union of all the tasks requires each task to have a sample complexity of only O(d log p/ K) per task for each of the K tasks]
For our result on meta learning, the sample complexity per task O(1/K) while for multi-task learning Cuo all 2015) the sample complexity per task is O(1). Thus, for us, the more tasks the better, while for multi-task, the more tasks, the more data needed.
2

---

Published in Transactions on Machine Learning Research (08/2024)
and in fact the more tasks the better for solving this problem. Here d is the maximum neighborhood size in the graphs of the Ising models for all tasks, and is the number of nodes in graph, which is also the same for all tasks. Furthermore, we have proved that with the knowledge from the auxiliary tasks, learning on a novel task for neighborhood selection requires a sufficient sample complexity of only O(d log d), independent of p, which is far less than that without restriction, O logp) (Ravikumar al., 2010), since we have assumed sparse graphical models which d & p. In this sense, we have smaller sufficient sample complexity for both auxiliary and novel tasks than those in all previous works, which have magnitude depending on p. particularly in the form of log p. We also show that Mid p/K) samples per auxiliary task and [2 log d) samples for the novel task are necessary for the recovery success, which proves that our meta learning method is minimax optimal.
Finally, we want to point out that, as part our contribution, we define a Bayesian generative model (see Definition 3. Bayesian meta learning has been previously studied (Grant al. 2018 Yoon et al. 2018 but the focus on proposing general problem-independeen algorithms, which a marginal likelihood (with respect to common parameter) is approximated by estimating the parameter of each auxiliary task. In contrast, avoid estimating each auxiiiary task parameter. Furthermore, our main contribution is theoretical guarantees of our procedure to efficiently recover the support union from auxiliary tasks through improper estimation, and to then estimate the parameter of the novel task, both with significantly better sample complexities.
2 Preliminaries
This section provides the background the Ising model selection. The notations to be used throughout the paper is summarized in Table
Table 1: Notation used in this paper.
Notation
Description
sign(z)
Sign of x e
||a|]
4--norm of vector E R", i.e., >
ii aa:
||a||
fz-norm of vector E R", ie., 2 ts -orm of vector a E R", i.e., max la.
T
||a]]oc
||Al||
The fı-nrr of matrix A mmxn ie., Lisismasis |4yl
||l oo
-o-operator-norm of matrix A E Rmxn Le., maxigigm Σ |Ai
Amin(A)
Minimum eigenvalue of matrix A E Rm* Maximum eigenvalue of matrix
Amax (A)
mm
||-All|
(z-operator-norm matrix mux i.e. V Amaz (AT Support set of vector E R.", i.e. (ila; & 0, Sisp) Support set matrix E RPXP, i.e. ((ij)(as Number of elements in set S Complement of set
supp(a)
supp(A)
[sl
se
Sub-vector of vector R" indexed by the entries in set S, ie., (at)iEs
As,
Sub-matrix of matrix Am*xn indexed by elements in S₁ x S2, i.e, (A4.s))ss)).55)
AGB E mm
The Hadamard product of A, B RM i.e., [A @ B], A.g Bij f(n) = O(g(n) if 0 S f(n) S Kg(n) for some constant 0 < < xc
O(g(n))
((((n)
f(n) ((g(n)) if f()) K' (')) for some constant K' 0
O(g(n))
f(n) = O(g(n)) if 0 < K" g(n) S f(n) < Kg(n) for some constants K' > >0
2.1 Ising Model and Model Selection
In this paper, we focus on the Ising model, i.e., the binary pairwise Markov random fields, for which we provide a definition here. Definition 2.1. Let X X2,, Xp) +11, denote a p-dimensional binary random vector, and each random variable X, is associated with vertex V of undirected graph G with verter set
3

---

Published in Transactions on Machine Learning Research (08/2024)
== (I....,p} and edge set E V X. is said to form an Ising model associated with G if the distribution takes the form
Po. (x) = 2(04) exp Σ
03
(1)
(a.))E
for some parameter frr E R, where the portition function Z(0*) ensures that the distribution sums to one.
A typical graphical model selection aims to infer the edge set E. A stronger criterion is signed edge recovery, i.., to infer the edge sign vector
sign (0),; if (8, E F otherwise.
E1
(2)
0,
2.2 Neighborhood-basee Logistic Regression
The signed edge recovery is equivalent recovering, for each vertex V, its neighborhood set M(r) =
{t tr, E), together with the correct signs sign(f;;) for all t E (r() (Ravikumar et al. 2010 Such information can be summarized as the signed neighborhood sel
N1 = e
(3)
which can be recovered naturally from the sign-sparsity pattern of the (p - 1) dimenssioaa sub-vector of parameters
8 10 rr
associated with each vertex r. To estimate prr we can make use of the casily derivod conditional distribution of X,, given the other variables X,r = {X,ll E \r):
exp(22, Eievy 03 Po- (x, exp(2r, EievYo 0, +1
(4)
The problem can thus be viewed as logistic regression where X₂ is the response variable and all other variables X,, act as the covariates. For a sparse problem, it is also natural to use the l-rrgularizzr (Tibshirani 1996.. Formally stated, given X7 (z(11,, (2)) (()),, set of i.i.d. samples, the regularized regression problem is convex program of the form Ravikumar et al. 2010
min E(O 2() + 1110
5
Prr ERP-1
(8) is the re-scaled negative log likelihood and À is regularization (8) (r))) where x() == - log Po, (x. parameter to be specified by the user. We can then use the estimate d, to estimate the signed neighborhood according to
Nr (Gi V \r, Or * 0).
3
Our Novel Generative Model and Improper Estimation Method
In this section, we introduce our novel generative model as well as our novel improper estimation method for the meta learning problem on Ising models.
3.1 Our Novel Generative Model for Meta Learning on lsing Models
We consider multiple Ising models whose parameters are generated randomly, which is more reasonable and flexible than the deterministic settings in previous work on multi-takk learning (Guo al. 2015). Formally, define the following family of Ising models with random parameters:
4

---

Published in Transactions on Machine Learning Research (08/2024)
Definition 3.1. Let x x2_ ..... x E (-1,+1]p be (k)) i..d. p-dimensional random vectors for each k EE (1,2....,K]) K). Let x be the s-th entry of the p-dimensional vector X(a) for 1 S S p. Say are given K undirected graphs with the same number of nodes p, i.e., G = =V, E(K) with the same verter set V (1,2.....,7) and polentially different edge sels E(k) CVX x V for 1 S S K. Each random variable _ is associated with verter E V in the k-th graph G We soy {x(-) "sisn(t),ssss forms family of p p-dimensional random Ising models of size K if, for S K,
(k)
(i) the samples X x(k)
x-O) i.d Poos, where ml8)
P Pecas (x,
exp {
Σ
0th (2) (R) Li.s Lizt
7(0(k))
(s.1)E
for some parometer Tihe) and the purtition function Z(ō(k) ensuring that the distribution sums to one; (ti)
g(k) = 0 + (k)
(8)
with 0, (k) E (R((, 0 deterministic and A 1 S k S K are i.i.d random vectors drawn from distribution P; and
(iit) we have for S S K,
P Pawmp(supp(A(") C supp(o)] = 1.
(9)
Remark 3.2. With respect to Definition 3.1 task k consist of: graph G(h),, Ising model parameterized
by g(k) with support defined by the edge set of G and samples x((), xx(6) ,..., x(h) coming from the probability distribution defined by the Ising model parameterized by g(k)
n(t)
For meta learning problem, we have K auxiliary tasks and one novel task, forming family of p-dimensional random Ising models of size K + 1. We can refer to 0 as the true common parameter vector and $ = supp(O) is what we call the true support union. We can then understand the maximum neighborhood size d for all where S, is the neighborhood set of each node r E V in the lalent
graphs as d = max [[S) [S2),..., deterministic graph parametrized by 0, defined as: S, == (t E Vl E S}. We assume < p (d is small in size compared p), so that the graphs are fairly sparsc. By restricting the parameter cstimation of the novel task to the true support union that can be estimated using the auxiliary lasks, we can potentially reduce the sample complexity for the novel task by a large margin.
Remark 3.3. Note that condition 1 restricts the support of the randomness in the parameter of each task to supp(Ø), which guarantees that the support of each task supp(((*)) S supp(0) for S k K + 1, with probability 1. For instance, for an arbilrary entry (s,1) supp(0), we have two cases: for lask k. if (k) = - then from equation [S] we have g(k) = 0, so that (s,t) & supp(((k)) and supp(0(k) C supp(f), i.e., we get proper subset; else if A (k) + +-0,t, then by the same token, have (s,t) (upp((())). Fither way we arrive at supp( C su) Suppose the contrary we do not impose condition ( then it will be hard for us to estimate a common porameter or support union useful for all the tasks. On the other hand, there is still great flezibillty in the family of distributions since graphs from different tasks can have edge structures with no intersection with arbitrary probability, and we do not assume entries in A (1k) to be small in absolule value.
3.2 Our Improper Estimation Method for Meta Learning Ising Models
Our estimation procedure be divided into two steps. The first step to recover S from the K auxiliary tasks by estimating 0. The second step is the signed edge recovery for task K + I with its support restricted to the estimated support union. Considering the sparsity of the problem, we will use the l--reuularzee logistic regression in both steps.
5

---

Published in Transactions on Machine Learning Research (08/2024)
Estimating the Support Union from K Tasks. Here we improperly estimate single parameter 0 although we know that each of the auxiliary tasks k = =, ,...., K has its own true parameter ((k), Since we are only interested on the joint support of the auxiliary tasks, this improper estimation does not need to estimate K parameters instead.
Specifically, for the first. step, we pool all the samples from the K tasks and estimate 0 by minimizing the e-regulaaized logistic loss between 0 and the estimate. For clearer presentation, we assumne that each auxiliary task has the same number of samples, i.c., n for 1 S k S K. Note that do not assume for the novel task. Then, for each node E V, given the samples from all the K auxiliary for which we use shorthand notation { this regularizod regression problem is a convex program of the form
that ne (1+)
tasks {x!²)
Og- arg min E(0vr (27H)) + ,11 ER
(10)
where
K E(O ((11)1)7)1)) = K log Fa, (1 (1) 11xr)
(11)
is the averaged re-scaled negative log likelihood of all the auxiliary tasks and À > is regularization parameter to be specified by the user, which potentially depends on n, d and K. Note that (00 is an improper estimation we estimate a single parameter vector using data from different distributions. We can further write E(Orri (K) k E K (0) (k)) where {2T) (k) is another shorthand notation
for (x(*) JigisH and (0 (a) (3)) = - E Po (a ( for s k $ K. With our estimate i for the true common parameter vector 0, we can use supp(O) as the estimate of the true support union S supp(())
Estimating the Support of the Novel Task. For the second step of our estimation, we aim to estimate the true parameter vector g(K+1) with knowledge from auxiliary tasks. Supposc we have successfully recovered the true support union S from the first step. Since the true support of the novel task parameter supp(0K+1) S is assumed in the problem setting, we can perform regularized logistic regression with an additional restriction:
@(K+1) = arg min ((K+))
(2T (K+)) ((++)) + (
(12)
s.t. supp(0 S supp((,r)
where
ny (K+1)
g(K+)) (B, 127 (27
(K+1) ((K+)))()))))))))))))))))) (K++1)
Σ log Fo (z 12
(K+1) ((A)))).. 1
(13)
Here (27 (x ((K+1)) = {x( k+))
1 denotes the (K+1) samples from the (K + 1)-th task, and
X(++1) is the regularization parameter for the novel task, which potentially depends on n (K+1) p, d.
4
Theoretical Results
4.1
Assumptions
The success of our method requires some assumptions on the structure of the logistic regression, most of which are the dependency and incoherence conditions the work by Ravikumar et al. (2010); Guo et al. (215) generalized to our meta learning sctting (see Assumptions 4.1
4.5 4.6 We also make assumptions regarding the randomness in the parameters for each task, which, intuitively speaking, make the tasks similar in some sense (see Assumption

---

Published in Transactions on Machine Learning Research (08/2024)
4.1.1 Assumptions in Auxiliary Tasks
The assumptions for the support union estimation are stated in terms of the Hessian of the likelihood function
E (r {} evaluated the true common parameter Or for each node r E V. More specifically, the
Hessian for any fixed node V is (p- (p-1)x(p-1) matrix of the form Q E Σ log x which has an explicit expression
(k) |x [x)
},
K
Blm(X (b); 00 (x(()) T
Q K
(14)
R=1
where
4exp(2ur ExEryT Brt21s)
n/u 0) (exp(2u, Exery (pt1(e) + 1)2
(15)
Here v( 0) is the variance function. Note that our expectation is taken with respect to the joint distribution of the data (x{*) JisiSmIIACK and the random variables {A (R) K in the parameters.
k==
Dependency Condition. Following the dependency condition imposed by Ravikunar et al. (2010). we assume that the subset of the Fisher information matrix corresponding to the relevant covariates in the true support union has bounded cigenvalues. We have:
Assumption 4.1. There cxist constants Cuia > 0 and D Dmax > O such that
Amin ((Qr)s.s) 2 Cmin
(16)
for all E V and
K E[X (1) (x S D Dmax.
A Amax
(17)
K
These assumptions make sure that the covariates are not excessively dependent.
Incoherence Condition. To prevent the large number of irrelevant covariates (the ones outside the support) having too strong an effect the relevant covariates (the ones in the support), as pointed out by Ravikumar et al. (20TO), the following assumption is required:
Assumption 4.2. There exists an a E (0, such that
(())))
a1-a,
(18)
for all r E V.
Our assumptions above, made only on the true common parameter for meta-learning, are similar to assumptions made for all tasks in multi-task learning (Guo et al. 2015). Thus, our assumptions are less restrictive.
Additional Assumptions on (A (1) h The success of our method also relies on some reasonable and flexible assumptions on the centering of the random variables (A()) JIsKS underlying the parameters of each task reasonable in the sense that the tasks are similar enough to provide useful information, and flexible that there is little inductive bias as possible.
For simplicity, without writing down the samples for the auxiliary tasks, we use a shorthand notation Vi(ā to denote the gradient of the loss function for the improper estimation, evaluated at the true common parameter vector 0; similarly (0(#)) means the gradient of the loss function for the k-th auxiliary task evaluated at the true parameter for that particular task, ie., ((k), With little abuse of notation in writing Vl & Ek (0())))(()), have
7

---

Published in Transactions on Machine Learning Research (08/2024)
Assumption 4.3. For any O,
8 log 1og(2p/s) (2p/s) S E,
P ((E
[0)ll
(19)
nk
for all V.
The constants 8 and 2 above are just for ease of calculation, and can be substituted with other constants without harm. Note that Ve = K Σ (e()) is just the counterpart of ve(0,)), with the gradient of loss for each lask evaluated at their own true parameters (()), which depend on each random A (k) opposed to all evaluated the common parameter vector 8,, in Ve(0))).
Remark 4.4. In calculating the expectation over the joint distribrution of X and A in this assumplion, n and K are eliminated due the i.i.d. (A(4) JisssK, and conditioned on which, the i.i.d. property of samples ( heignisksK follous. Hence, the requirement on K tasks is just one on the distribution P of (A(K) for the family of Ising models. The assumption helps specify some symmetry for the family of distributions and is compatible with the primal-dual witness.
Illustrative Example. Here we provide an illustrative example to help with intuitive comprehen- sion: the quantity in the assumption can be written explicitly as |Ea>r [ (Exxoe (x,
It can be checked that with a common latent graph with 3 nodes, 3 edges and 0 (1, setting of A resulting in the tasks parameter supports to have only 2 edges each with values 0 A E {(1.75, 1.75, 0), (1.75, O, 1.75), (0, 1.75, 1.75)) with equal probabilities will fulfill our condition with the desired quantity around 0. A straightforward example for higher dimensions is to have graph with the above 3-node graph repeated multiple times, noticing that the combination of removing edges would also give rise to potentially numerous different tasks. More details of calculation and illustration can be found in Appendix
E xx~ (x,x,
4.1.2 Assumptions in Novel Task
Our assumptions for the novel task is analogous to those for the improper estimation using auxiliary tasks, but with the parameters and the random variables restricted to the true support union S. We base the assumption on the Hessian of the likelihood function Ef E[-e((<1)(0s (27(*+a) Js
(K++)) [K+"))} evaluated at the true
parameter for the (K + 1)-th task, 0(*+1)
Q(K+1); E E(
== log Pagksn (X(K+))) S. x(K+1)).
This is given as the explicit expression
Q(K+1) = Bin(x (K+)
)x (K++)) (x(X((x) TT.
(20)
Let use ; supp(((kt)) to denote the true support of the (K + 1)-th task which satisfies S(K+)) C S. Similarly, we define s(k+1) = {t E vi(r,t) E s(K+1)). We again follow the assumptions made by Ravikumar
et al. 20100:
Assumption 4.5 (Dependency Condition). There exist constants ((K+1) > 0 and ((K+1) such that
Amia ((Q(+())))))))))) s(*++))(++))
(((( 2 (K++))
(21)
for all E V and
Amax (E[X (K+1) (x
(x(+)))TD) max
(22)

---

Published in Transactions on Machine Learning Research (08/2024)
Assumption 4.6 (Incoherence Condition). There exists (k+1)) (0, such that
(1( (s (( ((Q) (1
I - (K+1))
(23)
for all E..
Our assumptions above, made only on novel task parameter ((K+1) for meta-learning, are similar assumptions made for all tasks in multi-task learning (Guo et al. 2015). Thus, our assumptions are less restrictive.
4.2
Main Theorems
4.2.1 Support Union Recovery
Our first theorem demonstrates that the sufficient sample complexity for the recovery of the true support union S by our estimator in 10 is (dd logp/K) K') per task for each of the K tasks. This means that for the situation with numerous tasks K = (d log the sufficient sample complexity per task is as small as O(1). From the condition we obtained on the regularizing paramcter X, we can also see that having more tasks will give a good estimate of the support union with less penalty, without having to increase the number of samples per task the more tasks the better this case.
Theorem 4.7. For family of p-dimensional random Ising models of size described in Definition 3.1 4-3 are satisfied. Let {2T) (k) be set of n ii.dd samples from the model specified by g(k), and {XTH H denote all the samples from the K tasks. Suppose
with (kk) = for < k K, suppose. Assumptions 4-1 4-2
that the regulorization parameter X selected to satisfy 2 BV logg
nk for some constant 3 0, then there exists positive constant L, independent of (n, p, d, K), such that if nK > Ldd logp, then, for estimating the Ising model with the true common purameler 0, for some constand > 0, the sollowing properlies hold with probability at least 1 1-((esp(eeX(nK))
(a) For each node r E VV, the & f1-regularized logistic regression and so uniquely specifies a signed neighborhood N=(r).
10 given data ) K has a unique solution,
(b) For each V, the estimated signed neighborkood (+(r) correctly ezcludes all edges not in the true neighborhood, so that supp(o) S supp(0). Moreover, correctly includes all edges (r, 1) for which 10rel 2 10 vdd, along with their correct sign. Cmin
Proof sketch for Theorem 4.7 We use the primal-dual witness approach (Wainwright 2009 Ravikumar et al, 2010 and the proof can be divided into two parts. The first part shows that imposing the dependence and incoherence assumptions (Assumptions 4.1 and 1.2 on the population version of the Fisher information matrix Q guarantees (with high probability) that analogous conditions hold for the sample Fisher information matrir QN := (( ( []] (see (38) in Appendix): the second part of the proof is devoted to show that if the dependence condition and incoherence condition are imposed on the sample Fisher information matris Q.V, then the growth condition and choice of X from Theorem 4.7 are sufficient to ensure that the graph associated with the true common parameter vector is recovered with high probability (Ravikumar
et al. 2010
The first part of the proof mainly use techniques such as norm inequalities and union bounds Hoeffding Ocxpp(bb* + log for some constant b b> O,
1994 Ravikumar et al. 2010) to get a high probability which in burn yields the growth condition in on number of samples per task and number of tasks K.
In the second part, the key is to verify the strict dual feasibility (Rockafellar 2015 Using some norm
incqualities and following method used in a different context (Rothman et al. 2008 Ravikumar et al. 2010
show that it suffices to bound the random term Ve(a (27)
(p(k) (X)
20

---

Published in Transactions on Machine Learning Research (08/2024)
which decompose into two parts as follows
(0 (27)(8))
(0 (27) 11o0
K
(k) (0 (27]())) blo0 (24)
Using Hoeffding's Inequality with latent conditional independence (LCI) (e & Honorio 2019 with latent
variables (A))) k=1 |22 can be bounded with high probability in the sense that
82nk
Y2 > = eexp
(-8 8
logg
(25)
Also note that Yi = VE(0,r)) - K Ek= ((( (0(4)
using the shorthand notations in
19
We can then bound
|| by writing
|1 I|Y B(Y)) = & 1| B())) + |[E(()) )
(26)
Using Assumption
4.3 it is not hard to derive that
8onk (- 8
P( 2 5) S 2exp
+ log
(27)
For the term || BBY))l we can get the same rate decay with respect to (n, p, d, K) by using LCI Hoeffding's inequality [Ke Honorio 2019) again. Then applying union bounds and setting to be times constant, we get the rate O(exp( -cpp(ccckk) as in Theorem 4.7 well as the condition on A. The detailed
proof is in Appendix D
We also prove the following information lower bound on the failure of support union recovery for some family of Ising models.
Theorem 4.8. For some family of p-dimensional Ising models of size K with porameters (olk) jk=1 suppose 2 5, g(k) = H @ ((k) for 1 k S K with (R) E [-1/d", 1/d symmetric, degree d E Z+ even and E (0, 13pxP such that H is symmetric and H, 1 iff (i.j) E E. Thus == E, the support union of the K Ising models. Assume E randomly generated in the following way:
(1) Obtain permutation (T1, T2. ..2.....7p. Tp) of V= (1,2,..... .......... p} uniformly at random.
(a) Let uptj == Tī for SJSd/2
(iit) For i= 1 P, add (Ti, Ti+5) to E for 1 /
Thus d is the degree of the grophs in all tosks. Suppose that for each of the K distributions, we have n samples randomly drawm from them. Then for any estimate S of S, we have
2mpK /d3 + log 2
P($#5) 2
(28)
plogp - p - log 2p
The detailed proof is in Appendix
t
According to Thcorem 4.8 if the sample size distribution is S (d3 logp)/(4K) - d3 (4K)))) (d' log(Sp)) union of the Ising models specified in Theorem 4.8 Thus a sample complexity lidd logp/K) per task is necessary for the support union recovery of the p-dimensional Ising models tasks, which, combined with Theorem 4.7 indicates that our estimate 10 is minimax optimal with necessary and sufficient sample complexity of (dd logp/ K) per task.
then with probability larger than 1/2, any method will fail to recover the support
10

---

Published in Transactions on Machine Learning Research (08/2024)
4.2.2 Support Recovery for Novel Task
For the novel task, the following thcorem provides the sufficient conditions and a probability lower bound for the sign-consistency of the estimate, from which we can conclude that using the knowledge learned from the auxiliary tasks, the consistent signed neighborhood selection for the novel task can be achieved in a sufficient sample complexity of (K(+)) O(d logd).
Theorem 4.9. Suppose we have recovered the true support union of family of p-dimensional random Ising models of size K described in Definilion 3. 7 Assume |S] O(d). For a novel lask with porameter
gl(+1) such that supp(B(K+1)) [ S and satisfying Assumptions 4-8 4-0 suppose the regularization parameter
is chosen such that x(++1) 2 BV Lood niR+1J for some constant 33 0, then there erists a positive constant L, independent of (n( pp, d), such that if (K++1) > Ldd log then for some constont 0, the following properties hold with probability at least 1 1 (exxxp(e(A((tt))) (K(+)))).
logd
(a) For each node T E V, the E E-rregdarized logistic regression for estimating (LK+1) in the novel task, given data {2T ( a unique solution OCK+1), and so uniquely specifies a signed neighborhood M == (sign(0)u (0ll000))u yuluu E VV,r, 0(K+1) #0}
(b) For each r V, the estimated signed neighborhood (r)++1(r) correctly excludes all edges not in the true (sign(0/& (+++)) yulu julu E V \ r, o # 03. Moreover, il correctly includes all edges C Vd)(k+1), along with their correct sign.
neighborhood 11++)(()) with Ft
(r)
[((+1)]
10
mim
Remark 4.10. Note that the constants B, L and we use in the theorems are just some general constants for convenience of notation. The ones used in Theorem are not related to those in Theorem
Proof sketch for Theorem 4.9 We use the primal-dual witness approach again (Wainwright 2009 Ravikumar et al. 2010p. We have supposed that we have recovered the true support union from our estimate for the true common parameter, θ. The constraint in [2] then enables us to convert the problem into one without the restriction and with a parameter and data of dimension |S,] with |S,| s d for all r E V,, for we can combine the constraint straightforward into the minimization problem.
(0(K-1))
arg min { (((K+) (XT,
(K+1) (((+)))))))++)+ + ((K+1) 11 3
(29)
Sr
0s, ER
and (8(K+1) sc Ising model, but with dimension reduced from p to [Sr], and consequently to d. The detailed proof is in Appendix
In this way, we solve convex program analogous to which is learning on a single
We also prove the following information theoretic lower bound for the failure of support recovery for some Ising model where the support set is a subset of a known set S.
Theorem 4.11. For n samples generated from some p-dimensional Ising model, suppose the true parameter dxx symmeetric and H E (0, 13px such that H is symmetric and Hij = 1 iff (i.j) E E(K+1), Thus S(K+1) := E(K+1) is the support set of the Ising model. Assume E(++ chosen uniformly at random from the edge set family E (E{E (ESS: (i.j) E E = (i. E E} for known edge set S. Assume |S| = Odd). Then for any estimate S(K+)) of S(K-),, we have
matria is = H @ D with I E E- l- Logd Toga
P[S(K+1) + s(K+1) 21
4n
(30)
(log2) log d) d'
The detailed proof is in the Appendix
According to Thoorem 4.11 if n < log2 d log d 2 log d, then P(S(K+1) + S(K+)) 2 which indicates that the necessary sample complexity for the support recovery of the novel task is 2(d log d) and our estimate is minimax optimal. Therefore, our two-step meta learning method is minimax optimal.
8
11

---

Published in Transactions on Machine Learning Research (08/2024)
5 Experiments
Synthetic Experiments. To help illustrate and validate thcories, we conduct group of synthetic experiments and report the success rales (over 100 repetitions) for recovery of the true support union. We run the experiments with different number of nodes p E (50, 100, 200) and degree d 3, as well as with 50 nodes and three different degrees d E {3, 5, 7] We set the number of tasks scaling as K = d3 logp, with sample size for each auxiliary task n = Cd p/ K for C' ranging from 1 to upwards of 200. Then based on the estimated support union using C = 200, we use different sample sizes (K++) = C' log d for the novel task when C" changes from to 200 and calculate the success rates (over 100 repetitions) for signed edge recovery of the novel lask. We plot. the success rales against, C and C' for the steps respectively in Figure _ and Figure g The curves approximately lie top of one another the success rates tend to in Our results compare favorably against alternative methods.
each step, as predicted by Theorem 4.7 and 4.9
See Appendix B.I for more details.
50
p=100
p=200
d=3
da5
d=7
Success Rate
Success Rate
0.6
0.6
0.4
0.4
0.2
0.2
2
5
10
20
50
100
200
2
5
10
20
50
100
200
Figure 1: The success rates (over 100 repetitions) for support union recovery vs. the choice of C, for different number of nodes p (left) and different degrees d (right).
p=50
p=100
p=200
d=3
d=5
d=7
Success Rate
0.8
Success Rate
0.6
0.6
0.4
0.4
0.2
0.2
5
10
20
50
100
200
2
5
10
20
50
100
200
C'
Figure The success rates (over 100 repetitions) for signed edge recovery for novel task restricted to the
estimated support union based C = 200 the choice of C", for different number of nodes p (Ieft) and different degrecs d (right).
Real-world Data Experiments. As another motivation and validation of our method, used the real-world dataset "1000 Functional Connectomes" at http://www wiwrr. wttp:///oeeeeeeeoooooooooo 1000/ from 1128 subjects, 41 sites worldwide, and 157 brain regions. Each task comes from different research lab with different magnetic resonance imaging scanmers /equrmmenn with different physical properties. There are labs around the world that collect MRI from different subsets of subjects/ subjects/persons persons one lab a task, one brain region variable/node. Exploratory rescarch was performed to unveil which brain region interactions (edges the graph) are important. Similarly, different labs might not have the same underlying true graph (support), but it is reasonable to believe that they have some similarities. Specially, because it is partially
12

---

Published in Transactions on Machine Learning Research (08/2024)
known that the "default mode network" is graph that works when people awake but resting - this data is resting state functional magnetic resonance imaging. We estimated the support union from K = 40 auxiliary tasks with precision 0.8821, recall 0.8918 and Fl-score 0.8869. We used task 41 as the novel task, which support was estimated with precision 0.7133, recall 0.5528 and Fi-score 0.6228. Both Fi-score results are better than the ones from comparison methods. See Appendix B.2 for more details, and for interpretation of certain inter and intra symmetry between the left and right side the brain.
6 Concluding Remarks
Our method and analysis in this paper can be extended to more general cases of Markov random fields. Since logistic regression can be generalized to multi-class logistic regression, the analysis performed on the meta learning problem for Ising model can find its analog in multi-class discrete Markov random fields (Ravikumar ett al. 2010). Some other interesting directions for future work based on our method include but not limited to meta learning for general continuous Markov random fields, meta learning for graphical models with hyper-edges that connect multiple nodes instead only two, or time time-narying graphical models, etc. We believe our results can provide solid foundation and open novel perspective for meta learning in Markov random fields and related graphical models.
Broader Impact
This theoretical work does not present any foreseeable societal consequence.
References
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-Bayes theory. International Conference on Machine Learning, 35:205-214, 2018.
George Casella and Edward I George. Explaining the gibbs sampler. The American Statistician, 46(3): 167-174, 1992.
Lisha Chen and Tianyi Chen. Is Bayesian model-agnostic meta learning better than model-agnostic meta learning, provably? In Artificial Intelligence and Statistics, volume 151, pp. 1733 1774. PMLR, 2022.
Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Learning learn around common mean. In Neural Information Processing Systems, volume 31, 2018.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. On the convergence theory of gradient- based model-agnostic meta-learning algorithms. In Arlificial Intelligence and Statistics, pp. 1082-1092, 2020.
Alec Farid and Anirudha Majumdar. Generalization bounds for meta-learning via PAC-Bayes and uniform stability, In Neural Information Processing Systems, volume 34, pp. 2173 2186, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pp. 1126-1135. PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning, International Conference on Machine Learning, pp. 1920-1930, 2019.
Katelyn Gao and Ozan Sener. Modeling and optimization trade-off in meta-learning. Tn Neural Information Processing Systems, volume 33, pp. 11154 11165, 2020.
Stuart Geman and Donald Geman Stochastic relaxation, gibbs distributions and the bayesian restoration of images. Journal of Applied Statistics, 20(5-)):25-6)) 1993.
Asish Ghoshal and Jean Honorio. Information-theoree limits of bayesian network structure learning. In Artificial Intelligence and Statistics, pp. 767-775. PMIRR 2017.
13

---

Published in Transactions on Machine Learning Research (08/2024)
André R. Gonçalves, Fernando J Von Zuben, and Arindam Banerjee. Multi-label structure learning with Ising model selection. In Fuenty-Fourth International Joinl Conference Artificial Intelligence, 2015.
Erin Grant, Chelsea Finn, Sergey Levine, Trevor Darrell, and Thomas Griffiths. Recasting gradient- based meta-learning as hierarchical Bayes. International Conference on Learning Representations, 2018.
Jiechao Guan, Yong Liu, and Zhiwu Lu. Fine--rained analysis of stability and generalization for modern meta learning algorithms. In Neural Information Processing Systems, volume 35, pp. 18487-18500, 2022.
Jian Guo, Jie Cheng, Elizaveta Levina, George Michailidis, and Ji Zhu. Estimating heterogeneous graphical models for discrele data with an application roll call voting. The Annals of Applied Stalistics, 9(2):211, 2015.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pp. 409 426. Springer, 1994.
Jean Honorio. Lipschitz paramctrization of probabilistic graphical models. Uncertainty in Artificial Intelligence, pp. 347 354, 2011.
Roger A Horn and Charles R Johnson. Matriz analysis. Cambridge university press, 2012.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: A survey. IEEE Transactions on Pallern Analysis and Machine Intelligence, 44(9):51 5169, 2022.
Yimin Huang, Weiran Huang, Liang Li, and Zhenguo Li. Meta-learning PAC-Bayes priors in model averaging. Association for the Advancement of Artificial Intelligence Conference, pp. 4198-4205, 2020.
Ernst Ising. Beitrag zur theorie des ferromagnetismus. Zeitschrift für Physik, 31(1):253 258, 1925.
Chuyang Ke and Jean Honorio. Exact inference with latent variables in arbitrary domain. arXiv preprint arXiv:1902.0000 2019.
Mikhail Khodak, Maria-Florina Balcan, and Amect Talwalkar. Provable guarantees for gradient-baser meta-learning. International Conference on Machine Learning, 36:424-433, 2019.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6666):1332 1122-133,--1 2015.
Christiane Lemke, Marcin Budka, and Bogdan Gabrys. Metalearning: a survey of trends and technologies. Artificial intelligence review, 44(1):117 (100:)11-130,.---
130, 2015.
Christopher Manning and Hinrich Schutze. Foundations of statistical natural language processing. MIT press, 1999.
Andreas Maurer. Algorithmic stability and meta-learning, Journal of Machine Learning Research, 6(Jun): 967-994, 2005.
Alex Nichol, Joshua Achiam, and John Schulman. On first-order mela-learning algorithms. arXie preprinl urXiv:1803.02999 2018.
Anastasia Pentina and Christoph H. Lampert. PAC-Bayesian bound for lifelong learning. International Conference on Machine Learning, 31:991 999, 2014.
Sachin Ravi and Hugo Larochelle. Optimization as model for few-shot learning. International Conference Learning Representations, 2017.
Pradeep Ravikumar, Martin Wainwright, and John D Laflerty. High-dimensional Ising model selection using l-rreularized logistic regression. The Annals of Statistics, 38(3):1287 1319, 2010.
Ralph Tyrell Rockafellar. Conver analysis. Princeton university press, 2015.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Adam J Rothman, Peter J Bickel, Elizaveta Levina, and Ji Zhu. Sparse permutation invariant covariance estimation. Electronic. Journal of Slatistics, 2:494-515, 2008.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Neural Information Processing Systems, pp- 4077-4087, 2017.
R Kindermann Snell. Markov random fields and their applications. American Mathematical Sociely, 1980.
Sebastian Thrun and Lorien Pratt. Learning learn: Introduction and overview. In Learning to learn, pp. 3-17. Springer, 1998.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistionl Sociely: Series B (Methadological), 58(1):267 288, 1996.
Nilesh Tripuraneni, Michael I. Jordan, and Chi Jin. On the theory of transfer learning: The importance of task diversity. Neural Information Processing Systems, 33, 2020.
Joaquin Vanschoren. Meta-learning: A survey, arXiv preprint arXim:810000545 2018.
Ricardo Vilalta and Youssef Drissi. perspective view and survey of meta-learning. Artificial intelligence review, 18(2):77 95, 2002.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In Neural Information Processing Systems, pp. 3330-3638, 2016.
Martin J Wainwright. Sharp thresholds for high-dimensional and noisy recovery of sparsity using & f--constrained quadratic programming, IEEE Transactions on Information Theory, 55(5):2183-22)) 22002 2009.
N.A. Weiss, P.T. Holmes, and M. Hardy. Course in Probability. Pearson Addison Wesley, 2005. ISBN 9780321189547.. URL https://boock: boapoookk.googgee..oo.oo hwtp.//oooo/////.ccp/a//.......
Jaesik Yoon, Taesup Kim, Ousmane Dia, Sungwoong Kim, Yoshua Bengio, and Sungjin Ahn. Bayesian model-agnostic meta-learning. In Newral Information Processing Systems, volume 31, 2018.
Qian Zhang, Yilin Zheng, and Jean Honorio. Meta learning for support recovery in high-dimensional precision matrix estimation. In International Conference on Machine Learning, pp. 12642 12652. PMLR, 2021.
15


Reviews:
[{"review_id": "hh8VVjtUpd", "reviewer": "Reviewer_PgBo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nOverall, the paper is well written with clearly presented theoretical results.\n\nExperiments on real-world data are performed to validate the theories.\n\n## Weaknesses\n\n1. Although there are sufficient discussions on the related works of Ising models, very limited discussion is provided on the theoretical results of meta learning, which also provide sample complexity bounds.\nIt would be better if a comparison can be made for the results in this paper and some other related theoretical results of meta learning.\n\n\n\n2. The generative model essentially models the distribution of the Ising model parameters. How is the generative model related to Bayesian meta learning, which also models the distribution of the task-specific parameters? \n\n\n3. It would be better if the experiments in Figures 1 and 2 can perform on a wider range of $p$ and $d$ to validate the dependence on $p$ and $d$ for the theoretical sample complexity.\n\n4. It would be better if some discussions can be provided on when the assumptions in Section 4.1.2 can hold.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes to use meta learning to estimate the graphs for high-dimensional Ising models. Specifically, a generative model is used to produce random samples of the Ising model parameters.\nAn Improper Estimation Method is used which involves two steps. The first step is to estimate the Support Union from $K$ existing tasks, and the second step is to estimate the Support of the novel task.\n\nTheoretical results are provided on the sample complexity of the method with a matching lower bound, which indicates the algorithm is minimax optimal.\nFurthermore, it is also guaranteed that when the novel task is restricted to the estimated support union, the sample complexity is reduced, depending only on the max neighborhood size instead of the graph size.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Discuss the existing theoretical results on meta learning, see an example related work list below. Also, discuss how the results in these works compare to yours.\n\n[1] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. \"Learning to learn around a common mean\". NeurIPS, 2018.\n\n[2] Ron Amit and Ron Meir. \"Meta-learning by adjusting priors based on extended PAC-Bayes theory\". ICML, 2018.\n\n[3] Katelyn Gao and Ozan Sener. \"Modeling and optimiza- tion trade-off in meta-learning\". NeurIPS, 2020.\n\n[4] Alec Farid and Anirudha Majumdar. \"Generalization bounds for meta-learning via PAC-Bayes and uniform stability\". NeurIPS, 2021.\n\n[5] Lisha Chen and Tianyi Chen. \"Is Bayesian Model-Agnostic Meta Learning Better than Model-Agnostic Meta Learning, Provably?\". AISTATS, 2022.\n\n[6] Jiechao Guan, Liu Yong, and Lu Zhiwu. \"Fine-grained analysis of stability and generalization for modern meta learning algorithms\". NeurIPS, 2022.\n\n2. Discuss the relation of the proposed generative model with Bayesian meta learning.\n\n3. Discuss when the assumptions in Section 4.1.2 can hold.", "broader_impact_concerns": "No separate Broader Impact section is found.\n\nBut in the Concluding Remarks section some discussion of future extensions of this work is dicussed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JmOlcYpspU", "reviewer": "Reviewer_DpYs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n* This is a natural problem.\n* The assumptions are stated clearly.\n* The paper proves matching lower and upper bounds for the sample complexity.\n* Experimental evidence is provided to support the theoretical results.\n* The paper can motivate studying other Markov random fields and graphical models.\n\nWeaknesses:\n* Some of the notation is undefined.\n* Some assumptions are written in a convoluted way or are hard to check.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the sample complexity of meta-learning of signed-support recovery of Ising models.\n\nGiven a group of Ising models whose parameters are sampled independently from a probability distribution (as defined in Definition 3.1), the paper studies how many samples are needed from each model in order to (a) estimate the \"common parameter vector\" of the models and (b) estimate the signed-support vector of a new independent copy of the model given enough samples from it.\n\nThe paper also shows that the proved sample complexities are minimax-optimal.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is acceptable from my point of view, but I'd request some clarifications to improve readability.\n\n* Please explain what you mean by *improper* estimation.\n* At the top of Section 3.1, it is claimed that your generative model is \"more reasonable and flexible than the deterministic settings in previous work.\" Why? Specifically, why is this a *reasonable* model? Please elaborate.\n* After Definition 3.1, you immediately talk about the \"novel task.\" But it becomes clear much later what exactly is this novel task (I.e., estimating the support of the K+1-th Ising model). It seems you're using the words \"Ising model\" and \"task\" interchangeably, which is confusing.\n* There are a few undefined (but guessable) matrix notation. Please define these: $\\overline{Q}_{S_r S_r}, \\Lambda, |||\\cdot|||, \\bigodot$.\n* Writing $\\overline{Q}\\_{S S}$ for $\\overline{Q}\\_{S_rS_r}$ is extremely confusing.\n* Is Assumption 4.1 required for *all* nodes $r$? Please clarify.\n* Assumption 4.3 is unnatural and hard to check for an arbitrary model. Can you simplify it or provide conditions under which it holds?\n* Using $C^*$ as a parameter name is unfortunate. Some people may confuse $*$ with multiplication.\n* The results on real-world data experiments were quite surprising to me, as it doesn't seem to satisfy the assumptions you have made. Perhaps that section can be expanded and maybe you can explain what are some other cases where your method works although some of the assumptions do not hold.\n* In your main theorems, when you write, for instance, \"the estimated signed neighborhood correctly includes all edges such that etc.,\" perhaps you should add that these edges are included *with the correct sign*. (These are signed sets, so inclusion is not really well-defined for them.)", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MtMxERbwq3", "reviewer": "Reviewer_Dgbh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. The submission is clearly written and easy to follow. \n\n2. The theoretical analysis is thorough. \n\n3. The assumptions while might be strong are clearly discussed with clear motivation.    \n\n4. Both synthetic and empirical results are provided supporting the proposed method. \n\nWeaknesses\n\nI find the empirical results are lacking a little. \n\n1. For the real-world experiment, one naively solution is to use all the data and pretend they are all for the novel task. This can be a competing method to try. \n2. How many random seeds have we tried in the synthetic experiments. Can we also provide the std of the results or a histogram over different seeds? It would be great to show that the improvement of the proposed method is significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission considers meta learning in the context of Ising model learning. \n\nThe major contribution is on theoretical side. Specifically, the proposed method is shown to recover the support unition and also the support of a novel task with high probability. Finite-sample results are also provided, showing comparable and improved complexity. \n\nEmpirically, both synthetic and real-world results are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the two suggestions in the weakness section.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all appreciate the contributions of the paper. 

The authors and the reviewers had a good interaction that helped improve the paper.
Decision: Accept (poster)