面板数据回归的Coresets

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
本文介绍了面板数据设置中回归问题的重置问题。我们首先定义了面板数据回归问题的几种变体的重置集，然后给出了构造大小多项式依赖于1/$\\varepsilon$（其中$\\varepsilon$是误差参数）和回归参数个数的重置集的有效算法--与面板数据中个体的个数或每个个体被观察的时间单位无关。我们的方法是基于Feldman-Langberg框架，其中一个关键步骤是上界“总灵敏度”，即在所有可能的回归参数选择中，所有个体时间对的最大影响之和。在经验上，我们用合成的和现实世界的数据集来评估我们的方法；用我们的方法构造的coreset的大小比完整的数据集要小得多，并且coreset确实加快了计算回归目标的运行时间。
---
英文标题：
《Coresets for Regressions with Panel Data》
---
作者：
Lingxiao Huang, K. Sudhir, Nisheeth K. Vishnoi
---
最新提交年份：
2020
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Machine Learning        机器学习
分类描述：Papers on all aspects of machine learning research (supervised, unsupervised, reinforcement learning, bandit problems, and so on) including also robustness, explanation, fairness, and methodology. cs.LG is also an appropriate primary category for applications of machine learning methods.
关于机器学习研究的所有方面的论文（有监督的，无监督的，强化学习，强盗问题，等等），包括健壮性，解释性，公平性和方法论。对于机器学习方法的应用，CS.LG也是一个合适的主要类别。
--
一级分类：Computer Science        计算机科学
二级分类：Computational Geometry        计算几何
分类描述：Roughly includes material in ACM Subject Classes I.3.5 and F.2.2.
大致包括ACM课程I.3.5和F.2.2中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Economics        经济学
二级分类：Econometrics        计量经济学
分类描述：Econometric Theory, Micro-Econometrics, Macro-Econometrics, Empirical Content of Economic Relations discovered via New Methods, Methodological Aspects of the Application of Statistical Inference to Economic Data.
计量经济学理论，微观计量经济学，宏观计量经济学，通过新方法发现的经济关系的实证内容，统计推论应用于经济数据的方法论方面。
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
英文摘要：
  This paper introduces the problem of coresets for regression problems to panel data settings. We first define coresets for several variants of regression problems with panel data and then present efficient algorithms to construct coresets of size that depend polynomially on 1/$\\varepsilon$ (where $\\varepsilon$ is the error parameter) and the number of regression parameters - independent of the number of individuals in the panel data or the time units each individual is observed for. Our approach is based on the Feldman-Langberg framework in which a key step is to upper bound the \"total sensitivity\" that is roughly the sum of maximum influences of all individual-time pairs taken over all possible choices of regression parameters. Empirically, we assess our approach with synthetic and real-world datasets; the coreset sizes constructed using our approach are much smaller than the full dataset and coresets indeed accelerate the running time of computing the regression objective.
---
PDF下载：
--> English_Paper.pdf (753.74 KB)

2022-4-16 11:12:15 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：面板数据回归 Cores RESET 面板数据 Sets

用面板数据回归的Coresets，小黄华为TCS Labk。SudhirYale UniversityNisheeth K.VishnoiYale University2020年11月4日，用面板数据对几种回归问题的变体进行了coresets摘要，然后提出了构造大小的coresets的算法，这些coresets多项式依赖于1/ε（其中ε是误差参数）和回归参数的数量-与面板数据中的个体数量无关，在所有可能的回归参数选择的所有个体时间对中，我们用合成和现实世界的数据集来评估我们的方法；计算回归对象的coreset大小构造时间。arxiv:2011.00981 v2[CS.LG]2020.11月3日Contents1简介11.1相关工作。.............................................22`-与面板数据的回归33我们的面板数据的coreset代码44 GLSE 54.1算法的coreset定理4.1。....................................定理4.1的有用符号和有用事实。........................54.3定理4.1的证明。.......................................64.4引理4.3的证明：伪维数的上界。..................74.5引理4.4的证明：总灵敏度有界。........................85个用于GLSEK5.1验证概述的CORESET。..........................................115.2定理5.2的证明：GLSEK的上界。.........................125.3定理5.4的证明：GLSEK的下界。........................结论、限制和未来工作18A生成模型的讨论(1)23B OLSE的现有结果和方法23B。1定理B.1的证明。.......................................23B.2定理B.2的证明。.......................................241引言Panel数据，表示为asX∈Rn×T×Dandy∈Rn×T，其中实体/个体的数量，Tisthe时间段的数量和dis特征的数量在统计学中被广泛使用，并且只在机器上应用一次）[28,6]。使用观测数据推断变量之间关系的最常用方法是在时间段内包含实体。因此，面板数据的回归问题是以下关于回归变量β∈RD的优化问题，其中协方差矩阵Ω由上述参数minβ∈RD，Ω∈RT×TPI∈[N]yi-xiβ>-1yi-xiβ所导出。第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1行的第1这个回归模型的动机是Randome的ects模型（等式（1）和附录A)，在面板数据文献[，，]中常见。由于时间和空间的限制，参数空间为P=rd+q，一般采用ARQρ∈Rqq≥GLSE最小二乘估计。此外，拥有数据的组织可能只希望共享性能保证的一个问题子集，这些问题与在较小的Coreset上处理CompleteDataSet问题时获得的性能保证足够接近。由于Coresets的广泛应用和优点，它已经被开发用于各种无监督和有监督的重要限制，对于每一个可能的回归参数选择，它都接近回归目标。一个想法，因此，数据。但是，这个联合至少包含一个不受欢迎的tobservations，因为它可能很大。此外，目标。

在面板数据中，我们需要考虑如何对实体进行采样，以及在每个实体中如何使用这样一个由实体-时间对组成的coreset。我们的贡献。我们发起了对coreset的研究，用于`-与面板数据的回归，包括definition2.3)版本，以及GLSE的聚类扩展（GLSEK；定义2.4)，其中所有实体被划分为k个簇，每个簇共享相同的回归参数。ε与N和T无关。我们的主要贡献是:1.KNT，它使我们能够对coreset进行分析，类似于横截面数据的情况。对于GLSEk，回归在这个问题上，我们通过包含最小操作来定义一个coreset S上的回归目标。2.OMIN{ε-2d,d}coreset用于`-有截面数据的回归。3.～Oε-2max{qd,qd}。4.Kpolym,k,q,d,/εM介于OLSE的最大个体回归目标和最小个体回归目标之间（定义5.1）。我们提供了一个匹配的下界Ω(N)（定理5.4）fork,q,d≤2,表明coreset sizesh包含了比k,q,d,1/ε更多的因素，从而证明了M-有界假设。kρS变量使GLSE的目标函数非凸，而不是交叉-分段数据集ρβ∈RDK模型ork-means。因此，我们还不清楚GLSEK如何被简化为目标函数中高斯运算中使用的投影聚类，第二阶段将我们的GLSE的coreset构造应用于每个单独回归目标的EACHK“上下文可选性”（引理5.7）上，反过来，证明是由M-有界假设（第5.1）控制的。εε进一步，对于经验误差的可比水平，我们的coresets在样本量和coresets构造速度方面比均匀抽样INTERM性能好得多。1.1与面板数据相关的工作，依赖于生成模型，有几种方法来定义`-regression[，(1)参数与N和T无关（更多讨论见A节）。``承认大小为O(d/ε)[8]和大小为O(d)[33]的ε-coresets。利用截面数据，已经为机器学习中的一大类问题开发了coresets，以研究这些结果是否可以推广到面板数据。截面设置。2`-回归考虑以下`-回归生成模型：对于（i,t)∈[N]×[t]，yit=x>Itβi+eit，(1)βi∈rdeit∈r，包含一个额外的实体或个人指定的ectαi∈r，结果可用yit=x>Itβi+αi+eit表示。注2.1 xityitxit，yit，β∈rdyit-x>itβ缺少个体-时间对。假定`-回归函数可以表示为：对于任何回归参数ζP(Pζζpi∈[N]ψiζ,φi是否存在个体间的相关性以及βii是否唯一，φi有几个变体。βIβIβ设置导致普通最小二乘估计(OLSE)；定义2.2（普通最小二乘估计器(OLSE))(OLSE)，参数空间为RD，对于任意β∈RD，单个目标函数为φ(O)i(β):=pt∈[T]ρ(O)it(β)=pt∈[T](yit-x>itβ)。考虑当βii相同但单个时间周期之间可能存在相关性时，定义相关性的一种常见方法称为自相关关系纳(q)[，]，其中存在ρ∈Bq，其中q≥1是一个整数，Bq={x∈Rq:kxk<1}，如it=pmin{t-1,q}a=1ρaei,t-1 a+N(0,1）。

（2）这种自相关得到了广义最小二乘估计(GLSE)。对于具有(q)(integerq≥1)的广义最小二乘估计(GLSE),参数空间为ISrd×Bq，对于任一ζ=(β,ρ)∈Rd×Bq，单个目标函数为ψ（G,q)i(ζ）:=pt∈[T]ψ（G,q)it(ζ）等于(1-kρk)(yi1-x>i1β)+ptt=2(yit-x>itβ)-pmin{t-1,q}j=1ρj(yi,t-j-x>i,t-jβ).,q）itxit,yitψ（G,q）itq(xi,max{1,t-q},yi,max{1,t-q}）,。KKK≥K，关于某些GLSE的回归参数相同。定义2.4（GLSEK：GLSE的扩展）Letk，q≥1是整数。对于一个GLSEk，参数Rd×Bq-kζβ(1)。.，β(k)，ρ(1)，...,ρ(k)∈Rd×Bq^k函数是ψ（G,q,k)i(ζ）:=minl∈[k]ψ（G,q)i(β(l),ρ(l))。kβ(l),ρ(l)l∈k，即GLSE，完全是GLSE。还要注意GLSEK可以被看作是clusteredlinear regression[4]的一个广义版本，其中个体之间没有相关性。3面板数据的coreset定义在这一节中，我们展示了如何在面板数据上定义回归的coreset，包括OLSE和GLSE。Duecross-分段设置。一种方法是将个体的所有观察视为一个不可分割的群体，并选择一个个体集合作为一个coreset。然而，这种构造导致了一个与大小相关的核重置。对于较大的核重置大小，我们引入了一个广义的定义：查询空间的核重置，它捕获了OLSE和GLSE的核重置。定义3.1（查询空间[21,9])将一个索引集与一个权函数u:x→r≥0。P∑xp→r≥0x∈xxζP∑ζpx∈xx·ψxζ。x,u,P,ψ具体地，如果u(x)=1对于所有x∈x,为了简单起见，我们使用(x，P,ψ）。由于ζ的可分性，我们得到了如下的核重置：核重置3.2（查询空间[21,9]的核重置）X,u,P,ρε∈，εX,u,P,ρsxw:S→r≥0,使得对于任一ζ∈P,ρS(ζ）:=px∈Sw(X)·ρX(ζ）∈(1±ε)·ρ(ζ）。因此，我们可以应用上面的识别来识别OLSE和GLSE的CORESET。注意OLSEis是Q=0的GLSE的特例。因此，我们只需要为GLSE提供coreset dognition。我们letu=1和P=Rd×Bq。GLSE的索引集有以下形式:Z(G，q)=Zit=Xi,max{1,t-q},yi,max{1,t-q},。..退欧，YIT：（我，t)∈[N]×[t],zitqzit∈Z(G,q)ζβ,ρ∈Pψittψ（G,q)itζ-kρk·yi1-x>i1βt6ψ（G,q)itζ(yit-x>itβ)-pmin{t-1,q}j=1ρj(yi,t-j-x>i,t-jβ)。因此，(Z(G，q)，P,φ（G,q））是GLSE的一个查询空间，我们对GLSE有如下的核重集定义：定义3.3(GLSE的核重集）X∈Rn×T×Dy∈Rn×Tε，q≥pεsN×T，并有权函数w：S→R≥0，使得对于任一ζ=(β,ρ)∈P,ψ（G,q)S(ζ）:=X(i,t)∈SW(i,t)·ψ（G,q)it(ζ）∈(1±ε)·ψ（G,q)(ζ）。SεZ(G，q),P,ψ（G,q)点在此共重集中至多(q+1)·s规定，对于OLSE,参数空间为rdsinceq=0,相应的索引集为Z(O)={zit=(xit,yit):(i，t)∈[N]×[t]}。因此，OLSE的查询空间为(Z(O),Rd,ψ(O))。对于GLSEK，由于在定义2.4中的操作，目标函数ψ（G,q,k）只能分解为子函数ψ（G,q,k））而不是单独的时间对。则letu=1,Pk=rd×bq^k,和Z(G，q，k)={zi=(xi1，yi1，..,xiT，yiT):i∈[N]}。我们可以把(Z(G，q，k),Pk,ψ（G,q,k))看作一个查询空间kεZ(G，q，k),Pk,ψ（G,q,k）是N个权函数w:is→r≥0,使得对于任一ζPk，xi∈ISW(i)·ψ（G,q,k)i(ζ）∈(1±ε)·ψ（G,q,k)(ζ）。

（3）在这里，我们稍微滥用了这个记号，用ζ（G,q)it(ζ）代替了ζ（G,q)zit(ζ）。但是，Eachzi∈Z(G，q，k)由tobservations组成，因此，这个coresetSisT·stkt中的点数进一步选择一个时间段子集来估计ψ（G,q,k）i.S.N×tis{i∈[N]:ut∈[T]，S.T.，(i，T)∈S}Si∈ISJS，i{T∈[T]:(i，T)∈S}中单个i的观测值3.4（GLSEk的Coresets)X∈rn×T×dy∈rn×Tεε(0,1）,整数k,q≥1,参数spacePk,glseks的ε-coreset是一个加权集[N]×[T]和一个权函数w:S→r≥0,对于任意ζ=(β(1)，)。.，β(k)，ρ(1)，...,ρ(k))∈Pk,ψ（G,q,k)S(ζ）：=xi∈isminl∈[k]xt∈JS,iw(i,t)·ψ（G,q)it(β(l),ρ(l))∈(1±ε)·ψ（G,q,k)(ζ）。与GLSE相似，这样的一个核重集S中的点数最多为(q+1)·S.4个GLSE4核重集。在本节中，我们将介绍如何构造GLSE的核重集。我们设参数空间BEPλ=RD×BQ1-λ，对于某个常数λ∈(0,1）,其中BQ1-λ=ρ∈RQ:KρK≤1-λ。定理4.1(GLSE的Coresets）存在一个随机化算法，对于给定的面板数据etx∈rn×t×dy∈rn×tε，δ，λ，q≥-δ构造一个ε-GLSE的coreset，其大小为ε-2λ-1qd最大qd,qd·logdλ+logδ,并在时间O（NT q+NT d)中运行，q·Oε-2λ-1qd最大qd,qd·logdλ+logδ,yitntλδλδ。进一步简化:Oε-2最大qd,qd·log d=poly(q,d,1/ε)。4.1定理4.1x的算法，y，输出单个时间对的一个重置。主要思想是利用Feldman-Langberg(FL)框架使用重要性抽样（第6-7行）[，]。关键的新步骤出现在第5行，它计算GLSE的灵敏度函数，该函数定义采样分布。还要注意，基于另一个函数(O)(4行）的SIS的构造，它实际上是文献[8]中研究过的OLSE的灵敏度函数。4.2定理4.1Feldman和Langberg[]的有用符号和有用事实表明了如何通过重要性抽样来构造核重集，核重集的大小被[9]改进。定理4.2(FL框架[21,9])ε,δ,dimsn×t→r≥0i,t∈N×ts(i，t)≥supζ,pλψ（G,q)it(ζ）ψ（G,q)(ζ）和G:=p(i，t)∈[N]×[t]s(i，t))。设S X由takingoε-2G(dim·log G+log(1/δ))构造算法1：CGLSE：GLSerequire的Coreset构造；X∈Rn×T×D，Y∈Rn×T，常数ε，δ，λ∈(0,1)、整数q≥1和参数空间pλ。确保：子集S[N]×[T]连同权函数w；S→R≥0.1:Mèoε-2λ-1qd最大qd,QD·logdλ+logδ的具体情况。2：设Z∈RNT×(d+1)是其(it-t+T)第1行是zit=(xit，yit)∈RD+1for（i,t)∈[N]×[t].3:计算RNT×dwhes列构成z.4的列空间的单位基：对于每一个（我，t)∈[N]×[t]，s(O)(i)，t)èkait-t+tk.5:对于每一对（i,t)∈[N]×[t]，s（i,t)minn1,2λ-1S(O)(i，t)+Pmin{t-1,q}j=1S(O)(i，t-j)O.6：选择M对的随机样本S[N]×[t]，其中每个（i,t)∈S以概率（i,t)P(i，t)∈[N]×[t]S(i，t).7：对于每个（i,t)∈S，w(i，t)èP(i，t)∈[N]×[t]S(i，t)M·S(i，t).8：输出（S,w）.x∈Xs(x)Gwxgs·S(x).概率至少为1-δ,S是GLSE的ε-coreset。这里，灵敏度函数S测量每一个xit的最大值。与灵敏度成正比。样本复杂度由总灵敏度G和伪二次函数控制。4.3定理4.1（引理4.3）和“灵敏度”（引理4.4）的证明；引理4.3(GLSE的伪维数）(Z(G，q),u，pλ，ρ(G，q))上的权函数u:[N]×[T]→r≥0至多为O((q+d)qd)，qd，以及单个回归目标的运算次数（对于GLSE为O(qd))。

因此，我们得到引理4.3中的界O((q+d)qd)。Salgorithm1确实是GLSE的一个灵敏度函数，它度量了Eachxit∈X的最大灵敏度；由以下引理概括。引理4.4（GLSE的总灵敏度）函数:[N]×[T]→r≥0算法1的结论是，对于i,T∈N×tsi,T≥supζ∈pψ（G,q）it(ζ）ψ（G,q)(ζ）GP(i,T)∈[N]×[T]si,到λ-1qd，函数s的构造时间为O(NT q+NT d）。直观地说，如果灵敏度（i,T）很大，例如，接近1，ψ（G,q）时，它一定对某个参量ζpλ有重要的贡献。该抽样保证了我们很可能将这对（i,t）包含在从OLSE得到的φζ中，使每个单独的时间对对GLSE的灵敏度有界地变为：φ（G,q)ζ(O)ζβ,ρ∈Pλφ（G,q)iζ≥λ·ψ(O)iβ和φ（G,q)itζ≤·ψ(O)it(β)+pmin{t-1,q}j=1ψ(O)i,t-j(β)。...,xit,yitss（O）基于以下观察：对于任一ζ=(β,ρ)∈Pλ,ψ（G,q)it(ζ）ζ（G,q)(ζ）≤2·ψ（O）it(β)+pmin{t-1,q}j=1ψ（O）i,t)≤2λ-1·s(O)(i,t)+pmin{t-1,q}j=1s(O)(i,t-j)=s(i，t-j).然后它su-ces构造(O)(2-4d行（引理4.7）。因此，我们根据S.的规定得出GLSE的总灵敏度为isO(λ-1 qd)。现在我们准备证明定理4.1。证明:GOλ-1 qddimo((q+d)qd)gdimsize。对于运行时间，根据引理4.4计算灵敏度函数需要花费（NT q+NT d）的时间，而构造ε-核重置需要花费O（NT d）的时间。这就完成了证明。4.4引理4.3的证明：伪维数的上界我们的证明思想与[]类似。为了准备，我们需要以下引理来限定前馈神经网络的伪维数。引理4.5（对[2]定理8.14的重述）X,u,P,FFXζ={0,1}x∈xζPP Rmfx,ζ∈X×PFXζL运算:o算术运算+，-,×，和/在实数上。o跳转条件为>，≥，<，≤，=，6=实数的比较，和o输出0,1。然后是（X,u,P,f）至多为O(ml).Fx，这有助于将这个范围扩展到R.Lema 4.6（对[52]引理4.1的重述）X,u,P,fgxP×R→{0,1}是满足对任意x∈x，ζ∈P和r∈r,gx(ζ,r)=I[u(x)·f(x,ζ）≥r],那么(x，u，P，f)的伪维数正好是查询空间(x，u，P×r，gf)的伪维数。现在我们准备证明引理4.3。证明:un×t→r≥0I,t∈n×tgit:Pλ×r≥0→{0,1}是满足对任一ζ∈Pλ和r∈r≥0,git(ζ,r):=Ihu(I,t)·ψ（G,q）it(ζ）≥ri的指示函数。我们考虑查询空间(Z(G，q),u,Pλ×r≥0,G）。通过对pλ的认识，得到了pλ×r≥0ism=q+1+d的维数。通过对φ(G，q)it的认识，可以用L=O(qd)运算计算GIT，其中O(qd)ml(Z(G，q),u,pλ×r≥0,G）为O((q+d)qd)。然后通过引理4.6完成了证明。4.5引理4.4的证明：总敏感度的界我们通过将GLSE和OLSE之间的敏感度联系起来证明引理4.4。为了准备，我们给出了OLSE总灵敏度的上界引理。给定两个整数b≥1，表示(a，b)为矩阵inra×b的列基的运算时间。例如，通过计算矩阵INRA×B的SVD分解，可以得到它的列基，用[14]计算它的SVD分解时间为O（最小ab,ab）。算法1的引理4.7（OLSE的全灵敏度）函数(O):[N]×[T]→r≥0,证明了对于任意（i,T)∈[N]×[T],s(O)(i，T)≥supβ∈Rd'A(O)it(β)ρ(O)(β)(β)，(4)和G(O):=P(i，T)∈[N]×[T]s(O)(i，T)≤d+1。此外，函数(O)的构造时间为T(N，T，d+1)+O(N，d)。证明：证明思想来源于[]。根据算法1的第3行，RNT×DIS是一个矩阵，其列构成列空间OFZ的单位基。我们有≤d+1和Hencekak=d≤d+1。

而且，forany（我，t)∈[N]×[t]和β∈Rd,我们有Kβk≤kaβk，然后通过Cauchy-Schwarz和A的正交性，我们得到：对于任意（i,t)∈[N]×[t]和β∈rd+1,z>iTβ≤kait-t+tk·kzβk，(5),其中ait-t+是A.i的(it-t+t)第1行，t∈N×ts(O)i,tkait-t+tk(O)kakd≤d构造A代价t(NT,d+1）时间，计算所有kait-t+tk=O(NT d）时间，s(O)i,t(4)i,t∈N×tβ∈rd=(β,-1),我们有ρ(O)=(β，-1)时间iT(β)=Z>iTβ(Defn)。对于φ(O)it)≤kait-t+tk·kzβk(ineq。(5))=kait-t+tk·'A(O)(β).（defn。这就完成了证明。现在我们准备证明引理4.4。证明:[引理4.4的证明]对于任意（i,t)∈[N]×[t]，回想一下s(i,t)是bys(i,t):=minn1,2λ-1·s(O)(i，t)+pmin{t-1,q}j=1s(O)(i，t)(i，t)=1s(N)×[t]s(i，t)≤x(i，t)∈[N]×[q]2λ-1×s(O)(i，t)+pmin{t-1,q}2λ-1·p(i,t)∈[N]×[t](1+q)·s(O)(i,t)≤2λ-1(q+1)(d+1)。（引理4.7）因此，总灵敏度g=O(λ-1 qd）。根据引理4.7，构造(O)所需的时间为(NT，d+1)+O(NT，d)。我们还知道计算函数要花费（NT q）时间。Set(NT,d+1)=O(NT d）,这就完成了运行时间的证明。因此，还需要验证s(i,t)满足(i,t)≥supζ∈Pψ（G,q)it(ζ）ψ（G,q)(ζ）。由于supβ∈Rdψ(O)it(β)ψ(O)(β)≤1总是成立，我们只需考虑(i,t)=2λ-1·s(O)(i，t)+pmin{t-1,q}j=1s(O)(i，t-j)的情况。我们证明了对于任何ζ=(β,ρ)∈Pλ,ψ（G,q)(ζ）≥pλ,ψ（G,q)(ζ）。λ·ρ(O)(β)。(6)ρ∈Rqρ-1ρp>ρpρpρ=p1-kρk0。.........0-ρ1 0。.........0-ρ-ρ1。........0。.....................0.0-ρq。..-ρ.（7）则由式（7）得到pρs的最小特征值为λmin=q1-kρk(defn.pρ)≥√。(ρ∈Bq1-λ)(8)我们还得到了ρ(G，q)(ζ）=Xi∈[N](yi-xiβ)>Ω-1ρ(yi-xiβ)(Program(GLSE))=Xi∈[N]kpρ(yi-xiβ)k(p>ρpρ=Ω-1ρ)≥Xi∈[N]λ·k(yi-xiβ)k(ineq.(8))=λ·ψ(O)(β),证明了不等式（6）。对于任意（i,t)∈[N]×[t]，ψ（G,q)it(ζ）≤2·ψ（O）it(β)+pmin{t-1,q}j=1ψ（O）i,t-j(β)。（9）这在t=1时基本成立。对于t≥2,这是因为ψ（G,q）it(ζ）=(yit-x>itβ)-pmin{t-1,q}j=1ρj·(yi,t-j-x>i,t-jβ)(t≥2)≤1+pmin{t-1,q}j=1ρj×(yit-x>itβ)+pmin{t-1,q}j=1(yi,t-j-x>i,t-jβ)(Cauchy-Schwarz)=2·ψ(O)it(β)+pmin{t-1,q}j=1θ(O)it(β)+pmin{t-1,q}j=1θ(O)i,t-jβ)。(kρk≤1)现在结合不等式（6）和（9）,我们得到：对于任一项ζ=(β,ρ)∈Pλ,ζ（G,q)it(ζ）ζ（G,q)(ζ）≤2·ψ（O）it(β)+Pmin{t-1,q}j=1ψ（O）i,t-j(β)λ·ψ（O）(β)≤2λ-1·s(O)(i，t)+Pmin{t-1,q}j=1s(O)(i，t-j)=s(i，t).这就完成了证明。GLSEK5核重置紧随第4节，我们假定参数空间ispkλ=(RD×BQ1-λ)K，对于给定的常数λ∈(0,1）。给定一个面板数据etx∈Rn×T×Dandy∈Rn×T，letZ(i)∈RT×(D+1)表示一个矩阵，其第1行为(xit，yit)∈Rd+1，allt∈[T](i∈[N])。假定存在常数M≥1，使得输入数据集满足以下性质：定理5.1(M-有界数据集）M≥x∈Rn×T×Dy∈Rn×Tmi∈Nz(i)>Z(i)Mmaxβ∈Rd'A(O)i(β)KβK+1≤M·minβ∈Rd'A(O)i(β)KβK+1,tε，λ,q,k≥0.9,构造了GLSEk=ε-4λ-2mkmax qd,qd·logmqλlogmkdλ的ε-coreset,其运行时间为O（NT q+NT d）,与GLSE类似，GLSEk(k≥2)的coreset最多包含(q+1)·Oε-4λ-2mkmax qd,qd·logmqλlogkdλxit,yitntmaddmactory。

在算法2中对我们的算法进行了总结，我们对算法2进行了概述，并在下面讨论了算法2的新颖性。备注5.3算法2是一个两阶段的框架，它捕获GLSEK中的最小操作。算法2：CGLSEK：GLSEKRequire的Coreset构造：一个M-有界（常数M≥1)面板数据集X∈Rn×T×D，常数ε，λ∈(0,1)、整数k，q≥1和参数空间pkλ.确保：子集S[N]×[T]连同权函数w；S→R≥0.%构造个体子集1：Ωoε-2λ-1mkmax qd,Qd·logMqλ.2:对于每个i∈[N]，设矩阵Z(i)∈RT×(d+1)为其第t行为Z(i)t=(xit,yit)∈RD+1.3:对于每个i∈[N]，构造Z(i)，computeui:=λmax((Z(i))>Z(i))和`i:=λmin((Z(i))>Z(i))的SVD分解对于每个i∈[N]，s(O)(i)(R)UIUI+PI6=i`i.5:对于每个i∈[N]，s(i)(R)minn1,2(q+1)λ·s(O)(i)O.6:随机抽取一个大小为M的样本[N]，其中每一个i∈ISis选择w.p.s(i)pi∈[N]s(i).7：对于每一个i∈IS，为每个选定的个体构造一个时间段子集8：对于每一个i∈IS，应用CGLSE(Xi，yi，ε，20Ω，λ，q）并构造JS，i[T]和一个权函数w(i):JS，i→R≥0.9:设S{（i,T)∈[N]×[T]:i∈IS,T∈JS,i}.10：对于每一个（i,T)∈S,w(i,T)w(i)·w(i)(T).11:输出（S,w）.第一阶段。ε是NWIS→R≥0查询空间(Z(G，q,k),Pk,ψ（G,q,k))，即对于任一ζ∈PKXI∈ISW(i)·ψ（G,q,k)i(ζ）∈(1±ε)·ψ（G,q,k)i(ζ）。思想与算法1相似，不同的是我们考虑了子函数φ(G，q，k)而不是nt。在算法2的第2-4行中，我们构造了一个OLSEK的灵敏度函数(O)。在OLSEKN的目标函数中，确定S(O)的总灵敏度为edimostuiui+pj6=i`j（引理5.7）,这意味着S(O)的总灵敏度最小。然后在第5行，我们构造了一个GLSEk的灵敏度函数s，它是基于s(O)的约简（引理5.8）。第二阶段i∈ISCGLSEXi,yi,ε,20·is,λ,qJS,i[T]和一个权函数W(i):js,i→r≥0。输出={（i,t)∈[N]×[t]:i∈IS,t∈JS,i}和权函数w:S→R≥0定义如下：对于任意（i,t)∈S,w(i,t):=w(i)·w(i)(t).kΩ(N)。定理5.4（GLSEk的大小下限）tdkλ∈，X∈Rn×T×d，Y∈Rn×T，使得GLSEk的任何0.5-coreset都应该具有大小Ω(N)。5.1证明概述我们给出了一个证明概述。定理5.2的证明概述。对于GLSEk，我们提出了一个两阶段的框架（算法2):firerstcGLSEJS，ipolyq，dISkpolyk，q，dkkkqβ(1)，...,β(k)2(q+1)λψ（G,q)i(ζ）≥λ·ψ(O)i(β),并观察到任一ζ=(β(1),...,β(k),ρ(1),...,ρ(k))∈Pk,ψ（G,q,k)i(ζ）≤2(q+1)·minl∈[k]ψ(O)i(β(l)),从而给出了OLSEK的总灵敏度的一个上界。我们认为，在mostuiui+pj6=i`j，其中eui=(Z(i))>Z(i)的最大特征值是最小的。(Z(j))>Z(j)的特征值。这一事实来自以下观察:minl∈[k]kz(i)β(l),-k≤ui`j·minl∈[k]kz(j)β(l),-k,对olseksincepi∈[N]uiui+pj6=i`j≤pi∈[N]uipj∈[N]`j≤m的敏感性。定理5.4的证明概述。KN构造一个任意0.5-核重集包含所有个体观察的实例。请注意，we confidt=1，它简化为一个具有横截面数据的实例。我们的例子是对letxi1=(4i,i)yi1i∈Nζ(i)β(1)，β(2)，ρ(1)，ρ(2)β(1)i，β(2)，iρ(1)=ρ(2)=0,我们观察到了ζ（G,q,k)(ζ(i))≈ψ（G,q,k)i(ζ(i))。因此，所有的个体都应该包含在该核重集中，使得关于所有ζ(i)的回归目标近似保持。5.2定理5.2的证明：GLSEK的上界定理5.2的证明依赖于以下两个定理。该定理表明算法2是Zg，q，k，pkλ，ψ（G,q,k）的ε-核重集。

第二个约简定理是对每个个体构造一个ε-核重集JS，i.定理5.5(zg,q,k,pkλ,ζ（G,q,k）的核重集）MX∈rn×t×dy∈rn×tε,δ,λ∈，q,k≥0.95,算法2的加权子组是查询空间zg,q,k,pkλ,ψ（G,q,k）的ε-核重集，即对任意ζ=(β(1)...,β(k),ρ(1)...,ρ(k))∈Pkλ,xi∈ISW(i)·ψ（G,q,k)i(ζ）1±ε)·ψ（G,q,k）(ζ）。（10）此外，SVD(T,d+1)+O(N)的构造时间。我们推迟定理5.5的证明。定理5.6（从ZG,q,k,Pkλ,ψ（G,q,k）的核重置到GLSEk的核重置）是εZG,q,k,Pkλ,ψ（G,q,k）,概率至少为0.95,算法2的输出（S,w）是GLSEk的ε-核重置。证明：算法2的Sεk(10)i∈NJS,iε(Z(i))(G，q),Pλ,ψ（G,q)_(10)行6,每个JS,ii是ε-核重置的概率为(Z(i))(G，q)，pλ，ρ(G，q)-至少为1-'A·20'A=0.95，完成了这一证明。定理5.2是定理5.5和5.6的直接推论。证明：将定理5.5和5.6结合起来，得到一个概率最小为0.9的ZG，q，k，pkλ，ψ（G,q,k）的ε-核集。根据定理4.1,S的大小为γ·Oε-2λ-1qd最大qd,qd·logdλ+logγδ,它通过插入γ的值来满足定理5.2。对于运行时间，由定理5.5计算Iss需要N·SVD(T,d+1)。此外，通过算法2的第3行，我们已经得到了对alli∈[N]的Z(i)的SVD分解。那么，对于算法2的eachi∈ISin行8，应用CGLSE，只需花费(T(q+d))。然后它的成本为(NT(q+d))。这就完成了运行时间的证明。定理5.5的证明：ISis是Z（G,q,k）,pkλ,ψ（G,q,k）的一个核重集。注意ISis的构造应用了Feldman-Langberg框架。本文的分析类似于第4节，给出了总灵敏度和伪维数的上界，讨论了(Z(G，q，k)，Pk，ρ(G，q，k))的总灵敏度的上界。引理5.7(OLSEk)s(O)N→r≥0任一i∈[N]，s(O)(i)≥supβ(1)，...，β(k)∈Rdminl∈[k]'A(O)i(β(l))pi∈[N]minl∈[k]'A(O)i(β(l)))，(11)和G(O):=pi∈[N]s(O)(i)满足G(O)=O(M)。证明了：对于所有的T∈[T]，z(i)∈RT×(d+1)是第1行isz(i)T=(xit,yit)∈rd+1的矩阵，并且证明了函数(O)的构造时间是isN·SVD(T,d+1)+O(N)的构造时间是isN·SVD(T,d+1)+O(N)的构造时间是SVD(T,d+1)+O(N)的构造时间。因此，通过与引理4.7相同的论证，我们可以证明对于任意的矩阵序列Z(1)，θ(O)i(β)=kZ(i)(β,-1)k。..,Z(N)∈rt×(d+1),s(O)(i)≥supβ(1),...,β(k)∈rdminl∈[k]kz(i)(β(l),-1)kpi∈[N]minl∈[k]kz(i)(β(l),-1)k.（12）对于任意β(1),。..,β(k)∈Rd，任意I6=j∈[N],设l？=arg minl∈[k]kZ(j)(β(l),-1)k,我们有veminl∈[k]kZ(i)(β(l),-1)k≤kZ(i)(β(l),-1)k≤ui·(kβ(l?）k+1)(defn.ofui)≤ui`j·kZ(j)(β(l),-1)k(defn.of`i)=ui`j·minl∈[k]kZ(j)(β(l),-1)k。(defn.l？）由此，我们直接得出结论:minl∈[k]kz(i)(β(l),-1)kpi∈[k]kz(i)(β(l),-1)k≤minl∈[k]kz(i)(β(l),-1)k1+pi6=i`iui·minl∈[k]kz(i)(β(l),-1)k=uiui+pi6=i`i=s(O)(i)。因此，不等式（12）成立。此外，由于输入数据集是M-有界的，我们得到了Veg(O)≤xi∈[N]uipi∈[N]`i≤M，从而完成了证明的正确性，N·SVDT,dZ(i)onui`ion(O)，从而完成了证明。注意，通过上述论证，我们还可以假定i∈[N]uiui+pi6=i`i≤M,G(O)(Z(G,q,k）,Pk,ψ（G,q,k））的全灵敏度。算法2的引理5.8（GLSEk的全灵敏度）函数s:[N]→r≥0证明，对于anyi∈[N]，s(i)≥supζ,Pkλψ（G,q,k）i(ζ）ψ（G,q,k）(ζ）,（13）和G:=pi∈[N]s(i)满足G=O(qmλ)。此外，函数s的构造时间为isN·SVD(T,d+1)+O(N),用引理5.7证明了ONS(O)时间，即s(i)=2(q+1)λ·s(O)(i)。对于任一i∈[N]和任一ζ∈Pkλ，ψ（G,q,k)i(ζ）=minl∈[k]pt∈[T]ψ（G,q)it(β(l),ρ(l))(defn.2.4)≥minl∈[k]pt∈[T]λ·ρ(O)it(β(l))(ineq.(6))=λ·minl∈[k]ψ(O)i(β(l)))。（defn。

（14）我们还注意到，对于任意(i,t)∈[N]×[t]和任意(β,ρ)∈Pλ，ψ（G,q)it(β,ρ)≤(yit-x>itβ)-pmin{t-1,q}j=1ρj·(yi,t-j-x>i,t-jβ)(defn)。对于ψ（G,q)it)≤(1+pmin{t-1,q}j=1ρj)×(yit-x>itβ)+pmin{t-1,q}j=1(yi,t-j-x>i,t-jβ)(Cauchy-Schwarz)≤2(yit-x>itβ)+pmin{t-1,q}j=1(yi,t-j-x>i,t-jβ)(kρk≤1)因此，我们得到了·ψ（G,q)it(β,ρ)≤(yit-x>itβ)+min{t-1,q}xj=1(yi,t-j-x>i,t-jβ)。（15）这意味着特例表明，ψ（G,q,k)i(ζ）=minl∈[k]pt∈[T]ψ（G,q)it(β(l),ρ(l))(defn)。2.4)≤minl∈[k]pt∈[T]2×(yit-x>itβ)+pmin{t-1,q}j=1(yi,t-j-x>i,t-jβ)(ineq。(15))≤2(q+1)·minl∈[k]pt∈[T]'A(O)it(β(l))=2(q+1)·minl∈[k]'A(O)i(β(l)).因此，我们得到了对于任意i∈[N]和ζ的pkλ，ζ（G,q,k)i(ζ）ζ（G,q,k)(ζ）≤2(q+1)·minl∈[k]ψ(O)i(β(l))λ·pi∈[N]minl∈[k]ψ(O)i(β(l)))(ineqs)。（14）和(16))≤2(q+1)λ·s(O)(i)（引理5.7)=s(i)，（通过假设）证明了不等式（13）。此外，我们得到了G=Xi∈[N]s(i)≤2(q+1)λ·G(O)=O(qmλ)，其中最后一个不等式来自引理5.7。我们完成了证明。引理4.5和4.6。引理5.9（GLSEk的伪维数）(Z(G，q，k),u,pkλ,ρ(G，q，k))上的权函数u:[N]→r≥0在最大kq(q+d)d处。证明:un→r≥0i∈ngipkλ×r。）≥0→{0,1}ζ=(β(1)，..，β(k)，ρ(1)，...,ρ(k))∈Pkλ和r∈r≥0,gi(ζ,r):=Ihu(i)·ψ（G,q,k)i(ζ）≥ri=iàl∈[k],u(i)·xt∈[T]ψ（G,q)it(β(l),ρ(l))≥r。我们考虑查询空间(Z(G，q，k),u,pkλ×r≥0,G）。通过对pkλ的认识，得到了pkλ×r≥0mkqdβ,ρ∈Pλψ（G,q)Itβ,ρ(qd)项ρbcρbcβbcβbc,c,c∈[q],c,c∈[d]和b,b,b,b∈{0,1}组成的多项式的维数。gilokqdokqdkmlz（G,q,k）,u,pkλ×r≥0,go kq(q+d)d.然后通过引理4.6完成了证明。结合上述引理和定理4.2，我们准备证明定理5.5.证明:Gz(G,q,k）,pkλ,ψ（G,q,k）oqmλdimo k(q+d)qd-每个查询空间(Z(G,q,k）,u,pkλ,ψ（G,q,k））上权函数SU:[N]→r≥0。将定理4.2中的GandDim的值插入，证明了核重置的大小为N·SVDT,dONsLemma 5.8,构造的O(N)时间为。这就完成了证明。5.3定理5.4的证明：定理5.10（GLSEkZ(G，q，k),u,pkλ,ψ（G,q,k）N,T=1,d=k=2,λ∈(0,1）,定理5.10（GLSEk的大小和灵敏度下界）lett=1,d=k=2,且存在一个实例X∈rn×T×dand Y∈rn×T，使得总灵敏度xi∈[N]supζ,pkλψ（G,q,k)i(ζ）,φ（G,q,k)(ζ）=Ω(N),且查询空间(Z(G，q,k）,u,pkλ,ψ（G,q,k））的任何0.5-核重集都应具有大小Ω(N),证明:i∈Rn×T×d。NXI1I，IYI1:对于任意i∈[N]，supζ∈Pkλψ（G,q,k)i(ζ）ψ（G,q,k)(ζ）≥.(17)i∈ni∈nζβ(1)，β(2)，ρ(1)，ρ(2)∈PKλβ(1)i，β(2)=(0,4i)和ρ(1)=ρ(2)=0。如果j≤i，则我们有ψ（G,q,k)j(ζ）=minl∈[2](yi1-x>i1β(l))=minj-i，i-j=i-j。类似地，如果j>i，我们有ψ（G,q,k)j(ζ）=minj-i，i-j=j-i。由上述方程，我们有ψ（G,q,k)(ζ）=ixj=1i-j+nxj=i+1j-i<。（18）结合ψ（G,q,k)i(ζ）=1的事实，我们证明了不等式（17）。对于核重集大小，假定[N]和一个权函数w:s→r≥0是查询空间(Z(G,q,k),u,pkλ,ψ（G,q,k))的0.5-核重集。我们只需要证明它=[N]。假设存在一个I？∈Swithw(I？）>2。设ζ=(β(1)，β(2)，ρ(1)，ρ(2))，其中β(1)=(i？，0)，β(2)=(0,i？）且ρ(1)=ρ(2)=0,我们认为XI∈SW(i)·ψ（G,q,k）i(ζ）>w(i？）·ψ（G,q,k）i？(ζ）>2(w（i？）>2和defns。=ζ>(1+)·>(1+)·ψ（G,q,k）(ζ）,(ineq。(18))Si∈SWI≤Confulture假定ati？/∈S。再设ζ=(β(1)，β(2)，ρ(1)，ρ(2)),其中β(1)=(i？，0)，β(2)=(0,i？）和ρ(1)=ρ(2)=0,我们有xi∈SW(i)·ψ（G,q,k)i(ζ）≤2ψ（G,q,k)(ζ）-⑵（G,q,k)i？(ζ）(w(i)≤2)≤2(-1)(Ineq。(18))≤(1-)·1≤(1-)·ψ（G,q,k）(ζ）,与S的假设相矛盾，完成了证明。6个经验结果合成数据集和一个真实数据集。实验采用PyCharm软件，在一个4核8GB的桌面CPU上进行。数据集为syntheticntkdq，λ=0.2。