学习线性时间不变动态系统（LTID）的参数是当前兴趣的问题。在许多应用程序中，人们有兴趣联合学习多个相关LTID的参数，这仍然是未探究的日期。为此，我们开发一个联合估计器，用于学习共享常见基矩阵的LTID的过渡矩阵。此外，我们建立有限时间误差界限，取决于底层的样本大小，维度，任务数和转换矩阵的光谱属性。结果是在轻度规律假设下获得的，并在单独学习每个系统的比较中，展示从LTID的汇集信息汇总信息。我们还研究了错过过渡矩阵的联合结构的影响，并显示成立的结果在适度误操作的存在下是强大的。

根据线性随机微分方程进化的扩散过程是连续时间动态决策模型的重要家族。最佳政策对它们进行了充分研究，并确定了漂移矩阵。然而，对于不确定的漂移矩阵的扩散过程的数据驱动的控制知之甚少，因为常规离散时间分析技术不适用。此外，尽管该任务可以被视为涉及探索和剥削权衡取舍的强化学习问题，但确保系统稳定性是设计最佳政策的基本组成部分。我们确定流行的汤普森采样算法可以快速学习最佳动作，仅产生了时间根的遗憾，并在短时间内稳定了系统。据我们所知，这是汤普森在扩散过程控制问题中抽样的第一个结果。我们通过从两个飞机和血糖控制的两个设置的实际参数矩阵的经验模拟来验证理论结果。此外，我们观察到，与最先进的算法相比，汤普森采样显着改善（最坏的）遗憾，这表明汤普森采样以一种更加保护的方式探索。我们的理论分析涉及特定的特定最优歧管，该歧管将漂移参数的局部几何形状与扩散过程的最佳控制。我们希望这项技术具有更广泛的兴趣。

元学习或学习学习，寻求设计算法，可以利用以前的经验快速学习新技能或适应新环境。表示学习 - 用于执行元学习的关键工具 - 了解可以在多个任务中传输知识的数据表示，这在数据稀缺的状态方面是必不可少的。尽管最近在Meta-Leature的实践中感兴趣的兴趣，但缺乏元学习算法的理论基础，特别是在学习可转让陈述的背景下。在本文中，我们专注于多任务线性回归的问题 - 其中多个线性回归模型共享常见的低维线性表示。在这里，我们提供了可提供的快速，采样高效的算法，解决了（1）的双重挑战，从多个相关任务和（2）将此知识转移到新的，看不见的任务中的常见功能。两者都是元学习的一般问题的核心。最后，我们通过在学习这些线性特征的样本复杂性上提供信息定理下限来补充这些结果。

We study representation learning for efficient imitation learning over linear systems. In particular, we consider a setting where learning is split into two phases: (a) a pre-training step where a shared $k$-dimensional representation is learned from $H$ source policies, and (b) a target policy fine-tuning step where the learned representation is used to parameterize the policy class. We find that the imitation gap over trajectories generated by the learned target policy is bounded by $\tilde{O}\left( \frac{k n_x}{HN_{\mathrm{shared}}} + \frac{k n_u}{N_{\mathrm{target}}}\right)$, where $n_x > k$ is the state dimension, $n_u$ is the input dimension, $N_{\mathrm{shared}}$ denotes the total amount of data collected for each policy during representation learning, and $N_{\mathrm{target}}$ is the amount of target task data. This result formalizes the intuition that aggregating data across related tasks to learn a representation can significantly improve the sample efficiency of learning a target task. The trends suggested by this bound are corroborated in simulation.

我们考虑估计与I.I.D的排名$ 1 $矩阵因素的问题。高斯，排名$ 1 $的测量值，这些测量值非线性转化和损坏。考虑到非线性的两种典型选择，我们研究了从随机初始化开始的此非convex优化问题的天然交流更新规则的收敛性能。我们通过得出确定性递归，即使在高维问题中也是准确的，我们显示出算法的样本分割版本的敏锐收敛保证。值得注意的是，虽然无限样本的种群更新是非信息性的，并提示单个步骤中的精确恢复，但算法 - 我们的确定性预测 - 从随机初始化中迅速地收敛。我们尖锐的非反应分析也暴露了此问题的其他几种细粒度，包括非线性和噪声水平如何影响收敛行为。从技术层面上讲，我们的结果可以通过证明我们的确定性递归可以通过我们的确定性顺序来预测我们的确定性序列，而当每次迭代都以$ n $观测来运行时，我们的确定性顺序可以通过$ n^{ - 1/2} $的波动。我们的技术利用了源自有关高维$ m $估计文献的遗留工具，并为通过随机数据的其他高维优化问题的随机初始化而彻底地分析了高阶迭代算法的途径。

特征向量扰动分析在各种数据科学应用中起着至关重要的作用。然而，大量的先前作品着重于建立$ \ ell_ {2} $ eigenVector扰动边界，这些范围通常在解决依赖特征向量的细粒度行为的任务方面非常不足。本文通过研究未知特征向量的线性函数的扰动来取得进展。在存在高斯噪声的情况下，着重于两个基本问题 - 矩阵denoising和主成分分析 - 我们开发了一个统计理论的套件，该理论表征了未知特征向量的任意线性函数的扰动。为了减轻自然``插件''估计器固有的不可忽略的偏见问题，我们开发了偏低的估计器，即（1）（1）为场景家庭实现最小的下限（模仿某些对数因素），并且（2）可以以数据驱动的方式计算，而无需样品分裂。值得注意的是，即使相关的特征间隙{\ em少于先前的统计理论所要求的，提出的估计器几乎是最佳的最佳选择。

我们考虑通过流算法从单个轨迹估计线性时间不变（LTI）动态系统的问题，这在包括增强学习（RL）和时间序列分析的若干应用中遇到。虽然LTI系统估计问题在{\ em离线}设置中进行了很好地研究，但实际上重要的流媒体/在线设置很少受到关注。如随机梯度下降（SGD）等标准流动方法不太可能起作用，因为流点可以高度相关。在这项工作中，我们提出了一种新颖的流媒体算法，SGD具有反向体验的重播（$ \ MATHSF {SGD} - \ MATHSF {RER），这是由RL文献中流行的体验重播（ER）技术的启发。 $ \ mathsf {sgd} - \ mathsf {rer} $划分为小缓冲区，并在存储在单个缓冲区中的数据后向后运行SGD。我们表明该算法精确地解构了依赖结构，并获得了从理论上最佳保证的信息，用于参数误差和预测误差。因此，我们提供了我们的第一至最佳的知识 - 最佳的SGD风格算法，用于使用一阶Oracle的线性系统识别的经典问题。此外，$ \ mathsf {sgd} - \ mathsf {rer} $可以应用于具有已知稀疏模式和非线性动态系统的稀疏LTI识别的更多常规设置。我们的工作表明，数据依赖性结构的知识可以帮助我们在统计上和计算上的算法设计中，这些算法可以“去相关”流样本。

我们研究了随机近似程序，以便基于观察来自ergodic Markov链的长度$ n $的轨迹来求近求解$ d -dimension的线性固定点方程。我们首先表现出$ t _ {\ mathrm {mix}} \ tfrac {n}} \ tfrac {n}} \ tfrac {d}} \ tfrac {d} {n} $的非渐近性界限。$ t _ {\ mathrm {mix $是混合时间。然后，我们证明了一种在适当平均迭代序列上的非渐近实例依赖性，具有匹配局部渐近最小的限制的领先术语，包括对参数$的敏锐依赖（d，t _ {\ mathrm {mix}}） $以高阶术语。我们将这些上限与非渐近Minimax的下限补充，该下限是建立平均SA估计器的实例 - 最优性。我们通过Markov噪声的政策评估导出了这些结果的推导 - 覆盖了所有$ \ lambda \中的TD（$ \ lambda $）算法，以便[0,1）$ - 和线性自回归模型。我们的实例依赖性表征为HyperParameter调整的细粒度模型选择程序的设计开放了门（例如，在运行TD（$ \ Lambda $）算法时选择$ \ lambda $的值）。

我们在具有Martingale差异噪声的可实现的时间序列框架中学习正方形损失。我们的主要结果是一个快速率的多余风险结合，这表明每当轨迹超收缩条件成立时，依赖数据的最小二乘估计器的风险与燃烧时间后的IID速率订单匹配。相比之下，从依赖数据中学习的许多现有结果都具有有效的样本量，即使在燃烧时间之后，有效的样本量也被基础过程的混合时间降低。此外，我们的结果允许协变量过程表现出远距离相关性，这些相关性大大弱于几何牙齿。我们将这种现象学习称为几乎没有混合的方式，并为其示出了几个示例：$ l^2 $和$ l^{2+\ epsilon} $ norms的有界函数类是等效的，有限的有限态Markov链，各种参数模型，以及一个无限尺寸$ \ ell^2（\ mathbb {n}）$椭圆形的广阔家族。通过将我们的主要结果实例化，以使用广义线性模型过渡对非线性动力学的系统识别，我们仅在多项式燃烧时间后获得了几乎最小的最佳超量风险。

Influence diagnostics such as influence functions and approximate maximum influence perturbations are popular in machine learning and in AI domain applications. Influence diagnostics are powerful statistical tools to identify influential datapoints or subsets of datapoints. We establish finite-sample statistical bounds, as well as computational complexity bounds, for influence functions and approximate maximum influence perturbations using efficient inverse-Hessian-vector product implementations. We illustrate our results with generalized linear models and large attention based models on synthetic and real data.

这项教程调查概述了统计学习理论中最新的非征血性进步与控制和系统识别相关。尽管在所有控制领域都取得了重大进展，但在线性系统的识别和学习线性二次调节器时，该理论是最发达的，这是本手稿的重点。从理论的角度来看，这些进步的大部分劳动都在适应现代高维统计和学习理论的工具。虽然与控制对机器学习的工具感兴趣的理论家高度相关，但基础材料并不总是容易访问。为了解决这个问题，我们提供了相关材料的独立介绍，概述了基于最新结果的所有关键思想和技术机械。我们还提出了许多开放问题和未来的方向。

学习如何有效地控制未知的动态系统对于智能自治系统至关重要。当潜在的动态随着时间的推移时，这项任务成为一个重大挑战。本文认为这一挑战，本文考虑了控制未知马尔可夫跳跃线性系统（MJS）的问题，以优化二次目标。通过采用基于模型的透视图，我们考虑对MJSS的识别自适应控制。我们首先为MJS提供系统识别算法，用于从系统状态，输入和模式的单个轨迹，从模式开关的演进中的底层中学习MJS的系统识别算法。通过混合时间参数，该算法的样本复杂性显示为$ \ mathcal {o}（1 / \ sqrt {t}）$。然后，我们提出了一种自适应控制方案，其与确定性等效控制一起执行系统识别，以使控制器以焦化方式调整。 Combining our sample complexity results with recent perturbation results for certainty equivalent control, we prove that when the episode lengths are appropriately chosen, the proposed adaptive control scheme achieves $\mathcal{O}(\sqrt{T})$ regret, which can be改进了$ \ mathcal {o}（polylog（t））$与系统的部分了解。我们的证据策略介绍了在MJSS中处理马尔可维亚跳跃的创新和较弱的稳定概念。我们的分析提供了影响学习准确性和控制性能的系统理论量的见解。提出了数值模拟，以进一步加强这些见解。

We study non-parametric estimation of the value function of an infinite-horizon $\gamma$-discounted Markov reward process (MRP) using observations from a single trajectory. We provide non-asymptotic guarantees for a general family of kernel-based multi-step temporal difference (TD) estimates, including canonical $K$-step look-ahead TD for $K = 1, 2, \ldots$ and the TD$(\lambda)$ family for $\lambda \in [0,1)$ as special cases. Our bounds capture its dependence on Bellman fluctuations, mixing time of the Markov chain, any mis-specification in the model, as well as the choice of weight function defining the estimator itself, and reveal some delicate interactions between mixing time and model mis-specification. For a given TD method applied to a well-specified model, its statistical error under trajectory data is similar to that of i.i.d. sample transition pairs, whereas under mis-specification, temporal dependence in data inflates the statistical error. However, any such deterioration can be mitigated by increased look-ahead. We complement our upper bounds by proving minimax lower bounds that establish optimality of TD-based methods with appropriately chosen look-ahead and weighting, and reveal some fundamental differences between value function estimation and ordinary non-parametric regression.

从数据中学习的方法取决于各种类型的调整参数，例如惩罚强度或步长大小。由于性能可以在很大程度上取决于这些参数，因此重要的是要比较估算器的类别 - 考虑规定的有限调谐参数集，而不是特别调谐的方法。在这项工作中，我们通过同类中最佳方法的相对性能研究方法类。我们考虑了线性回归的中心问题，即随机的各向同性地面真理，并研究了两种基本方法的估计性能，即梯度下降和脊回归。我们公布以下现象。 （1）对于一般设计，当经验数据协方差矩阵衰减的特征值缓慢，作为指数较不小于统一的功率定律时，恒定的梯度下降优于山脊回归。相反，如果特征值迅速衰减，则作为指数大于统一或指数的权力定律，我们表明山脊回归优于梯度下降。 （2）对于正交设计，我们计算了确切的最小值最佳估计器类别（达到最低最大最大最佳），这表明它等同于具有衰减学习率的梯度下降。我们发现山脊回归和梯度下降的次数均具有恒定的步长。我们的结果表明，统计性能可以在很大程度上取决于调整参数。特别是，虽然最佳调谐脊回归是我们设置中的最佳估计器，但当仅在有限的许多正则化参数上调整两种方法时，它可以用任意/无界数量的梯度下降来表现优于梯度下降。

In many modern applications of deep learning the neural network has many more parameters than the data points used for its training. Motivated by those practices, a large body of recent theoretical research has been devoted to studying overparameterized models. One of the central phenomena in this regime is the ability of the model to interpolate noisy data, but still have test error lower than the amount of noise in that data. arXiv:1906.11300 characterized for which covariance structure of the data such a phenomenon can happen in linear regression if one considers the interpolating solution with minimum $\ell_2$-norm and the data has independent components: they gave a sharp bound on the variance term and showed that it can be small if and only if the data covariance has high effective rank in a subspace of small co-dimension. We strengthen and complete their results by eliminating the independence assumption and providing sharp bounds for the bias term. Thus, our results apply in a much more general setting than those of arXiv:1906.11300, e.g., kernel regression, and not only characterize how the noise is damped but also which part of the true signal is learned. Moreover, we extend the result to the setting of ridge regression, which allows us to explain another interesting phenomenon: we give general sufficient conditions under which the optimal regularization is negative.

矩阵正常模型，高斯矩阵变化分布的系列，其协方差矩阵是两个较低尺寸因子的Kronecker乘积，经常用于模拟矩阵变化数据。张量正常模型将该家庭推广到三个或更多因素的Kronecker产品。我们研究了矩阵和张量模型中协方差矩阵的Kronecker因子的估计。我们向几个自然度量中的最大似然估计器（MLE）实现的误差显示了非因素界限。与现有范围相比，我们的结果不依赖于条件良好或稀疏的因素。对于矩阵正常模型，我们所有的所有界限都是最佳的对数因子最佳，对于张量正常模型，我们对最大因数和整体协方差矩阵的绑定是最佳的，所以提供足够的样品以获得足够的样品以获得足够的样品常量Frobenius错误。在与我们的样本复杂性范围相同的制度中，我们表明迭代程序计算称为触发器算法称为触发器算法的MLE的线性地收敛，具有高概率。我们的主要工具是Fisher信息度量诱导的正面矩阵的几何中的测地强凸性。这种强大的凸起由某些随机量子通道的扩展来决定。我们还提供了数值证据，使得将触发器算法与简单的收缩估计器组合可以提高缺乏采样制度的性能。

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

汤普森采样（TS）是在不确定性下进行决策的有效方法，其中从精心规定的分布中采样了动作，该分布根据观察到的数据进行更新。在这项工作中，我们研究了使用TS的可稳定线性季度调节剂（LQR）自适应控制的问题，其中系统动力学是未知的。先前的作品已经确定，$ \ tilde o（\ sqrt {t}）$频繁的遗憾对于LQR的自适应控制是最佳的。但是，现有方法要么仅在限制性设置中起作用，需要先验已知的稳定控制器，要么使用计算上棘手的方法。我们提出了一种有效的TS算法，用于对LQR的自适应控制，TS基于TS的自适应控制，TSAC，该算法达到了$ \ tilde o（\ sqrt {t}）$遗憾，即使对于多维系统和Lazaric（2018）。 TSAC不需要先验已知的稳定控制器，并通过在早期阶段有效探索环境来实现基础系统的快速稳定。我们的结果取决于开发新颖的下限TS提供乐观样本的概率。通过仔细规定早期的探索策略和政策更新规则，我们表明TS在适应性控制多维可稳定性LQR方面实现了最佳的遗憾。我们从经验上证明了TSAC在几个自适应控制任务中的性能和效率。

本文为信号去噪提供了一般交叉验证框架。然后将一般框架应用于非参数回归方法，例如趋势过滤和二元推车。然后显示所得到的交叉验证版本以获得最佳调谐的类似物所熟知的几乎相同的收敛速度。没有任何先前的趋势过滤或二元推车的理论分析。为了说明框架的一般性，我们还提出并研究了两个基本估算器的交叉验证版本;套索用于高维线性回归和矩阵估计的奇异值阈值阈值。我们的一般框架是由Chatterjee和Jafarov（2015）的想法的启发，并且可能适用于使用调整参数的广泛估算方法。

近似消息传递（AMP）是解决高维统计问题的有效迭代范式。但是，当迭代次数超过$ o \ big（\ frac {\ log n} {\ log log \ log \ log n} \时big）$（带有$ n $问题维度）。为了解决这一不足，本文开发了一个非吸附框架，用于理解峰值矩阵估计中的AMP。基于AMP更新的新分解和可控的残差项，我们布置了一个分析配方，以表征在存在独立初始化的情况下AMP的有限样本行为，该过程被进一步概括以进行光谱初始化。作为提出的分析配方的两个具体后果：（i）求解$ \ mathbb {z} _2 $同步时，我们预测了频谱初始化AMP的行为，最高为$ o \ big（\ frac {n} {\ mathrm {\ mathrm { poly} \ log n} \ big）$迭代，表明该算法成功而无需随后的细化阶段（如最近由\ citet {celentano2021local}推测）; （ii）我们表征了稀疏PCA中AMP的非反应性行为（在尖刺的Wigner模型中），以广泛的信噪比。