每年，深度学习都会通过更深层和更广泛的神经网络展示新的和改进的经验结果。同时，使用现有的理论框架，很难在不诉诸于计数参数或遇到深度指数的样本复杂性范围的情况下，比两层更深地分析网络。尝试在不同的镜头下分析现代机器学习也许是富有成效的。在本文中，我们提出了一个新颖的信息理论框架，其遗憾和样本复杂性的概念用于分析机器学习的数据要求。通过我们的框架，我们首先通过一些经典示例进行工作，例如标量估计和线性回归，以构建直觉并引入通用技术。然后，我们使用该框架来研究由深度符号神经网络，深度恢复神经网络和深层网络产生的数据的样本复杂性，这些数据无限宽，但具有限制的权重。对于符号神经网络，我们恢复了基于VC量的参数之后的样本复杂性界限。对于后两个神经网络环境，我们建立了新的结果，这些结果表明，在这些数据生成过程中，学习的样本复杂性最多是线性和二次的网络深度。

We study the compute-optimal trade-off between model and training data set sizes for large neural networks. Our result suggests a linear relation similar to that supported by the empirical analysis of Chinchilla. While that work studies transformer-based large language models trained on the MassiveText corpus (gopher), as a starting point for development of a mathematical theory, we focus on a simpler learning model and data generating process, each based on a neural network with a sigmoidal output unit and single hidden layer of ReLU activation units. We establish an upper bound on the minimal information-theoretically achievable expected error as a function of model and data set sizes. We then derive allocations of computation that minimize this bound. We present empirical results which suggest that this approximation correctly identifies an asymptotic linear compute-optimal scaling. This approximation can also generate new insights. Among other things, it suggests that, as the input space dimension or latent space complexity grows, as might be the case for example if a longer history of tokens is taken as input to a language model, a larger fraction of the compute budget should be allocated to growing the learning model rather than training data set.

假设发行版是高斯通常促进别侵害的计算。我们考虑一个旨在实现与具有高斯的先前分配和高斯似然函数的强盗环境获得低信息比的代理，但是在应用于伯努利强盗时研究代理的性能。当代理商与Bernoulli强盗互动时，我们建立了贝叶斯遗憾的增加，相对于对高斯匪徒的信息定理束缚。如果高斯的现有分配和似然函数足够弥散，则随着时间的平方根，这种增加的增加，因此每次时间增长都会增加消失。我们的结果正式化了所谓的贝叶斯代理在漫反射错过分布的差异时所谓的贝叶斯代理人仍然有效。

我们对解决几个自然学习问题的一通流算法所需的记忆量给出了下限。在$ \ {0,1 \}^d $中的示例的环境中，可以使用$ \ kappa $ bits对最佳分类器进行编码，我们表明，使用近距离数量的示例学习的算法，$ \ tilde o（\ kappa）$，必须使用$ \ tilde \ omega（d \ kappa）$空间。我们的空间界限与问题自然参数化的环境空间的维度相匹配，即使在示例和最终分类器的大小上是二次的。例如，在$ d $ -sparse线性分类器的设置中，$ \ kappa = \ theta（d \ log d）$，我们的空间下限是$ \ tilde \ omega（d^^^ 2）$。我们的边界与流长$ n $优雅地降级，通常具有$ \ tilde \ omega \ left（d \ kappa \ cdot \ frac \ frac {\ kappa} {n} {n} \ right）$。 $ \ omega（d \ kappa）$的形式的界限以学习奇偶校验和有限字段定义的其他问题而闻名。在狭窄的样本量范围内适用的边界也以线性回归而闻名。对于最近学习应用程序中常见的类型的问题，我们的第一个范围是适用于各种输入尺寸的问题。

Authors are encouraged to submit new papers to INFORMS journals by means of a style file template, which includes the journal title. However, use of a template does not certify that the paper has been accepted for publication in the named journal. INFORMS journal templates are for the exclusive purpose of submitting to an INFORMS journal and should not be used to distribute the papers in print or online or to submit the papers to another publication.

Thompson sampling has proven effective across a wide range of stationary bandit environments. However, as we demonstrate in this paper, it can perform poorly when applied to nonstationary environments. We show that such failures are attributed to the fact that, when exploring, the algorithm does not differentiate actions based on how quickly the information acquired loses its usefulness due to nonstationarity. Building upon this insight, we propose predictive sampling, which extends Thompson sampling to do this. We establish a Bayesian regret bound and establish that, in nonstationary bandit environments, the regret incurred by Thompson sampling can far exceed that of predictive sampling. We also present implementations of predictive sampling that scale to complex bandit environments of practical interest in a computationally tractable manner. Through simulations, we demonstrate that predictive sampling outperforms Thompson sampling and other state-of-the-art algorithms across a wide range of nonstationary bandit environments.

在本文中，我们介绍了超模块化$ \ mf $ -Diverences，并为它们提供了三个应用程序：（i）我们在基于超模型$ \ MF $ - 基于独立随机变量的尾部引入了Sanov的上限。分歧并表明我们的广义萨诺夫（Sanov）严格改善了普通的界限，（ii）我们考虑了有损耗的压缩问题，该问题研究了给定失真和代码长度的一组可实现的速率。我们使用互助$ \ mf $ - 信息扩展了利率 - 延伸函数，并使用超模块化$ \ mf $ -Diverences在有限的区块长度方面提供了新的，严格的更好的界限，并且（iii）我们提供了连接具有有限输入/输出共同$ \ mf $的算法的概括误差和广义率延伸问题。该连接使我们能够使用速率函数的下限来限制学习算法的概括误差。我们的界限是基于对利率延伸函数的新下限，该函数（对于某些示例）严格改善了以前最著名的界限。此外，使用超模块化$ \ mf $ -Divergences来减少问题的尺寸并获得单字母界限。

PAC-Bayes has recently re-emerged as an effective theory with which one can derive principled learning algorithms with tight performance guarantees. However, applications of PAC-Bayes to bandit problems are relatively rare, which is a great misfortune. Many decision-making problems in healthcare, finance and natural sciences can be modelled as bandit problems. In many of these applications, principled algorithms with strong performance guarantees would be very much appreciated. This survey provides an overview of PAC-Bayes performance bounds for bandit problems and an experimental comparison of these bounds. Our experimental comparison has revealed that available PAC-Bayes upper bounds on the cumulative regret are loose, whereas available PAC-Bayes lower bounds on the expected reward can be surprisingly tight. We found that an offline contextual bandit algorithm that learns a policy by optimising a PAC-Bayes bound was able to learn randomised neural network polices with competitive expected reward and non-vacuous performance guarantees.

我们观察到，给定两个（兼容的）函数类别$ \ MATHCAL {f} $和$ \ MATHCAL {h} $，具有较小的容量，按其均匀覆盖的数字测量，组成类$ \ Mathcal {H} \ Circ \ Mathcal {f} $可能会变得非常大，甚至无限。然后，我们证明，在用$ \ Mathcal {h} $构成$ \ Mathcal {f} $的输出中，添加少量高斯噪声可以有效地控制$ \ Mathcal {H} \ Circ \ Mathcal { F} $，提供模块化设计的一般配方。为了证明我们的结果，我们定义了均匀覆盖随机函数数量的新概念，相对于总变异和瓦斯坦斯坦距离。我们将结果实例化，以实现多层Sigmoid神经​​网络。 MNIST数据集的初步经验结果表明，在现有统一界限上改善所需的噪声量在数值上可以忽略不计（即，元素的I.I.D. I.I.D.高斯噪声，具有标准偏差$ 10^{ - 240} $）。源代码可从https://github.com/fathollahpour/composition_noise获得。

通过定义和上限，通过定义和上限，分析了贝叶斯学习的最佳成绩性能，通过限定了最小的过度风险（MER）：通过从数据学习和最低预期损失可以实现的最低预期损失之间的差距认识到了。 MER的定义提供了一种原则状的方式来定义贝叶斯学习中的不同概念的不确定性，包括炼膜不确定性和最小的认知不确定性。提出了用于衍生MER的上限的两种方法。第一方法，通常适用于具有参数生成模型的贝叶斯学习，通过在模型参数之间的条件互信息和所观察到的数据预测的量之间的条件相互信息。它允许我们量化MER衰减随着更多数据可用而衰减为零的速率。在可实现的模型中，该方法还将MER与生成函数类的丰富性涉及，特别是二进制分类中的VC维度。具有参数预测模型的第二种方法，特别适用于贝叶斯学习，将MER与来自数据的模型参数的最小估计误差相关联。它明确地说明了模型参数估计中的不确定性如何转化为MER和最终预测不确定性。我们还将MER的定义和分析扩展到具有多个模型系列的设置以及使用非参数模型的设置。沿着讨论，我们在贝叶斯学习中的MER与频繁学习的过度风险之间建立了一些比较。

我们使用对单个的，相同的$ d $维状态的相同副本进行的测量来研究量子断层扫描和阴影断层扫描的问题。我们首先因Haah等人而重新审视已知的下限。 （2017年）在痕量距离上具有准确性$ \ epsilon $的量子断层扫描，当测量选择与先前观察到的结果无关（即它们是非适应性的）时。我们简要地证明了这一结果。当学习者使用具有恒定结果数量的测量值时，这会导致更强的下限。特别是，这严格确定了民间传说的最佳性``Pauli phymography''算法的样本复杂性。我们还得出了$ \ omega（r^2 d/\ epsilon^2）$和$ \ omega（r^2 d/\ epsilon^2）的新颖界限（ R^2 d^2/\ epsilon^2）$用于学习排名$ r $状态，分别使用任意和恒定的结果测量，在非适应性情况下。除了样本复杂性，对于学习量子的实际意义，是一种实际意义的资源状态是算法使用的不同测量值的数量。我们将下限扩展到学习者从固定的$ \ exp（o（d））$测量的情况下进行自适应测量的情况。这特别意味着适应性。没有使用可有效实现的单拷贝测量结果给我们任何优势。在目标是预测给定的可观察到给定序列的期望值的情况下，我们还获得了类似的界限，该任务被称为阴影层析成像。在适应性的情况下单拷贝测量可通过多项式大小的电路实现，我们证明了基于计算给定可观察物的样本平均值的直接策略是最佳的。

我们推出了可实现的机器学习模型的贝叶斯风险和泛化误差的信息 - 理论下限。特别地，我们采用了一个分析，其中模型参数的速率失真函数在训练样本和模型参数之间界定了所需的互信息，以便向贝叶斯风险约束学习模型。对于可实现的模型，我们表明，速率失真函数和相互信息承认的表达式，方便分析。对于在其参数中（大致）较低的LipsChitz的模型，我们将从下面的速率失真函数绑定，而对于VC类，相互信息以高于$ d_ \ mathrm {vc} \ log（n）$。当这些条件匹配时，贝叶斯相对于零一个损耗尺度的风险不足于$ \ oomega（d_ \ mathrm {vc} / n）$，它与已知的外界和最小界限匹配对数因子。我们还考虑标签噪声的影响，在训练和/或测试样本损坏时提供下限。

In this paper we derive a PAC-Bayesian-Like error bound for a class of stochastic dynamical systems with inputs, namely, for linear time-invariant stochastic state-space models (stochastic LTI systems for short). This class of systems is widely used in control engineering and econometrics, in particular, they represent a special case of recurrent neural networks. In this paper we 1) formalize the learning problem for stochastic LTI systems with inputs, 2) derive a PAC-Bayesian-Like error bound for such systems, 3) discuss various consequences of this error bound.

我们探索了一个新的强盗实验模型，其中潜在的非组织序列会影响武器的性能。上下文 - 统一算法可能会混淆，而那些执行正确的推理面部信息延迟的算法。我们的主要见解是，我们称之为Deconfounst Thompson采样的算法在适应性和健壮性之间取得了微妙的平衡。它的适应性在易于固定实例中带来了最佳效率，但是在硬性非平稳性方面显示出令人惊讶的弹性，这会导致其他自适应算法失败。

收购数据是机器学习的许多应用中的一项艰巨任务，只有一个人希望并且预期人口风险在单调上汇率增加（更好的性能）。事实证明，甚至对于最小化经验风险的最大限度的算法，甚至不令人惊讶的情况。在训练中的风险和不稳定的非单调行为表现出并出现在双重血统描述中的流行深度学习范式中。这些问题突出了目前对学习算法和泛化的理解缺乏了解。因此，追求这种行为的表征是至关重要的，这是至关重要的。在本文中，我们在弱假设下获得了一致和风险的单调算法，从而解决了一个打开问题Viering等。 2019关于如何避免风险曲线的非单调行为。我们进一步表明，风险单调性不一定以更糟糕的风险率的价格出现。为实现这一目标，我们推出了持有某些非I.I.D的独立利益的新经验伯恩斯坦的浓度不等式。鞅差异序列等进程。

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

了解现代机器学习设置中的概括一直是统计学习理论的主要挑战之一。在这种情况下，近年来见证了各种泛化范围的发展，表明了不同的复杂性概念，例如数据样本和算法输出之间的相互信息，假设空间的可压缩性以及假设空间的分形维度。尽管这些界限从不同角度照亮了手头的问题，但它们建议的复杂性概念似乎似乎无关，从而限制了它们的高级影响。在这项研究中，我们通过速率理论的镜头证明了新的概括界定，并明确地将相互信息，可压缩性和分形维度的概念联系起来。我们的方法包括（i）通过使用源编码概念来定义可压缩性的广义概念，（ii）表明“压缩错误率”可以与预期和高概率相关。我们表明，在“无损压缩”设置中，我们恢复并改善了现有的基于信息的界限，而“有损压缩”方案使我们能够将概括与速率延伸维度联系起来，这是分形维度的特定概念。我们的结果为概括带来了更统一的观点，并打开了几个未来的研究方向。

To date, no "information-theoretic" frameworks for reasoning about generalization error have been shown to establish minimax rates for gradient descent in the setting of stochastic convex optimization. In this work, we consider the prospect of establishing such rates via several existing information-theoretic frameworks: input-output mutual information bounds, conditional mutual information bounds and variants, PAC-Bayes bounds, and recent conditional variants thereof. We prove that none of these bounds are able to establish minimax rates. We then consider a common tactic employed in studying gradient methods, whereby the final iterate is corrupted by Gaussian noise, producing a noisy "surrogate" algorithm. We prove that minimax rates cannot be established via the analysis of such surrogates. Our results suggest that new ideas are required to analyze gradient descent using information-theoretic techniques.

Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Rényi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."

我们研究了$ \ Mathcal {r} $的结构和统计属性 - 规范最小化由特定目标函数标记的数据集的内侧插值。$ \ MATHCAL {R} $ - 标准是两层神经网络的电感偏差的基础，最近引入了捕获网络权重大小的功能效果，与网络宽度无关。我们发现，即使有适合数据的脊函数，这些插值也是本质上的多元功能，而且$ \ Mathcal {r} $ - 规范归纳偏见不足以实现某些学习问题的统计上最佳概括。总的来说，这些结果为与实际神经网络训练有关的感应偏见提供了新的启示。