在这个简短的说明中,我们考虑解决最小 - 最大零和游戏的问题。已经在凸凹方案中广泛研究了该问题,其中可以有效地计算全局解。最近,当玩家的一个目标是凹的或(弱的)凹陷时,也有发现用于找到游戏的一阶静止点的发展。这项工作侧重于非凸非凹方式,其中一个参与者的目标满足Polyak - {\ L} ojasiewicz(PL)条件。对于这样的游戏,weshow一个简单的多步梯度下降 - 上升算法在$ \ widetilde {\ mathcal {O}}中找到$ \ varepsilon $ - 问题的第一阶固定点(\ varepsilon ^ { - 2 })$ iterations。
translated by 谷歌翻译
过去的工作已经表明,有些令人惊讶的是,过度参数化可以帮助神经网络中的泛化。为了解释这一现象,我们采用基于保证金的观点。我们建立:1)对于多层前馈网络,弱正则化交叉熵损失的全局最小值具有所有网络中的最大归一化裕度,2)因此,增加过度参数化改善了归一化裕度和广义误差界限用于双层网络。特别是,无限大小的神经网络享有最佳的泛化保证。典型的无限特征方法是核方法;我们将神经netmargin与内核方法进行比较,并构建自然实例,其中kernelmethods具有更弱的泛化保证。我们凭经验验证了这两种方法之间的差距。最后,这种无限神经元观点对于分析优化也很有成效。我们证明了无限大小网络上的扰动梯度流在多项式时间内找到了一个全局优化器。
translated by 谷歌翻译
廉价梯度原理(Griewank 2008)---计算标量值函数梯度的计算成本几乎相同(通常在5美元左右),就像简单计算函数本身一样 - 在中心的重要性优化;它允许我们快速获得(高维)标量损失函数的梯度,这些函数随后用于基于黑盒子梯度的优化程序。目前的状态在计算子衍生物方面明显不同:广泛使用的MLlibraries,包括TensorFlow和PyTorch,即使在简单的例子中也没有正确计算(广义)子衍生物。这项工作考虑了问题:是否有廉价的次级原则?我们的主要结果表明,在我们的非光滑函数库(标准非线性规划)的某些限制下,可证明正确的广义子衍生物可以计算成本计算成本,该计算成本在计算成本的$ 6 $(无维度)因子内。标量函数本身。
translated by 谷歌翻译
我们研究了梯度下降对学习多层齐次函数所施加的隐式正则化,包括具有线性,ReLU或Leaky ReLU激活的前馈全连通和卷积深度神经网络。我们严格证明梯度流(即有限步长内的梯度下降)有效地强制执行不同层次的平方之间的差异在没有任何明确的规则化的情况下保持不变。该结果意味着如果权重最初很小,则梯度流自动平衡所有层的大小。利用adiscretization参数,我们分析了具有正步长的梯度下降,得到了非凸低阶非对称矩阵分解问题,没有任何正则化。受我们对梯度流的研究结果的启发,我们证明了步长为$ \ eta_t = O \ left(t ^ { - \ left(\ frac12 + \ delta \ right)} \ right)$($ 0 <\ delta \ le \)的梯度下降frac12 $)自动平衡两个低秩因子并收敛到有界全局最优。此外,对于秩为1美元的非对称矩阵分解,我们给出了更精细的分析,显示梯度下降,恒定步长在全球线性速率下收敛到全局最小值。我们认为,在学习同质模型时检验一阶算法所假设的不变性的想法可以作为研究深度模型学习优化的基本构件。
translated by 谷歌翻译
我们提供了关于过度参数化在学习神经网络中有效的原因的新理论见解。对于具有二次激活和$ n $训练数据点的$ k $隐藏节点浅网络,我们只要$ k \ ge \ sqrt {2n} $显示,过度参数化使本地搜索算法能够找到\ emph {global}一般情况下,尽管参数的数量可能超过样本量,但使用Rademacher复杂度理论,我们表明,如果数据是从常规分布中采样的,那么解决方案也可以很好地推广。高斯。为了证明$ k \ ge \ sqrt {2n} $,损失函数有benignlandscape属性,我们采用平滑分析的想法,这可能有其他应用于研究神经网络的损失表面。
translated by 谷歌翻译
我们考虑学习具有非重叠卷积层和ReLU激活的单隐层神经网络的问题,即$ f(\ mathbf {Z},\ mathbf {w},\ mathbf {a})= \ sum_j a_j \ sigma(\ mathbf {w} ^ T \ mathbf {Z} _j)$,其中卷积权重$ \ mathbf {w} $和输出权重$ \ mathbf {a} $是要学习的参数。当标签是具有固定权重$(\ mathbf {w} ^ *,\ mathbf {a} ^ *)$的相同架构的教师网络的输出时,我们用高斯输入$ \ mathbf {Z} $证明,有一个有害的局部最小化器。令人惊讶的是,在存在虚假局部最小化的情况下,随机初始化权重的权重归一化的梯度下降仍然可以证明恢复具有恒定概率的真实参数,可以通过多次重启来提升到1美元的概率。 Wealso表明,在恒定的概率下,相同的程序也可以归结为虚假的局部最小值,表明局部最小值在梯度下降的动力学中起着重要的作用。此外,水平分析表明梯度下降动力学有两个阶段:它开始缓慢,但在几次迭代后收敛得更快。
translated by 谷歌翻译
The stochastic gradient descent (SGD) algorithm has been widely used in statistical estimation for large-scale data due to its computational and memory efficiency. While most existing works focus on the convergence of the objective function or the error of the obtained solution, we investigate the problem of statistical inference of true model parameters based on SGD when the population loss function is strongly convex and satisfies certain smoothness conditions. Our main contributions are twofold. First, in the fixed dimension setup, we propose two consistent estimators of the asymptotic covariance of the average iterate from SGD: (1) a plug-in estimator, and (2) a batch-means estimator, which is computationally more efficient and only uses the iterates from SGD. Both proposed estimators allow us to construct asymptotically exact confidence intervals and hypothesis tests. Second, for high-dimensional linear regression, using a variant of the SGD algorithm, we construct a debiased estimator of each regression coefficient that is asymptotically normal. This gives a one-pass algorithm for computing both the sparse regression coefficients and confidence intervals, which is computationally attractive and applicable to online data. MSC 2010 subject classifications: Primary 62J10, 62M02; secondary 60K35 The batch-means estimator is a "weighted" sample covariance matrix that treats each batch-means as a sample. The idea of batch-means estimator can be traced to Markov Chain Monte Carlo (MCMC), where the batch-means method with equal batch size (see, e.g., Glynn and Iglehart (1990); Glynn and Whitt (1991); Damerdji (1991); Geyer (1992); Fishman (1996); Jones et al. (2006); Flegal and Jones (2010)) is widely used for variance estimation in a time-homogeneous Markov chain. The SGD iterates in (2) indeed form a Markov chain, as x i only depends on x i−1. However, since the step size sequence η i is a diminishing sequence, it is a time-inhomogenous Markov chain. Moreover, the asymptotic behavior of SGD and MCMC are fundamentally different: while the former converges to the optimum, the latter travels ergodically inside the state space. As a consequence of these important differences, previous literature on batch-means methods is not applicable to our analysis. To address this challenge, our new batch-means method constructs batches of increasing sizes. The sizes of batches are chosen to ensure that the correlation decays appropriately among far-apart batches, so that far-apart batch-means can be roughly treated as independent. In Theorem 4.3, we prove that the proposed batch-means method is a consistent estimator of the asymptotic covariance. Further , we believe this new batch-means algorithm with increasing batch sizes is of independent interest since it can be used to estimate the covariance structure of other time-inhomogeneous Markov chains. As both the plug-in and the batch-means estimator provide asymptoti-cally exact confidence intervals, each of the
translated by 谷歌翻译
矩阵完成是一个基本的机器学习问题,具有广泛的应用,特别是在协同过滤和推荐系统中。简单的非凸优化算法在实践中是流行和有效的。尽管最近在证明各种非凸算法方面取得了很好的进展,但仍然不清楚为什么随机或任意初始化在实践中就足够了。我们证明了\ textit {positive semidefinite}矩阵完成的常用非凸目标函数具有nospurious局部最小值 - 所有局部最小值也必须是全局的。因此,诸如(随机)梯度下降的许多流行优化算法可以在多项式时间中使用\ textit {任意}初始化来提供正半定矩阵完成。当观察到的条目包含噪声时,结果可以推广到设置。我们认为,我们的主要证明策略可用于理解涉及部分或嘈杂观测的其他问题的几何特性。
translated by 谷歌翻译
我们提出MonoPSR,一种单眼三维物体检测方法,可以利用孢子和形状重建。首先,利用apinhole相机模型的基本关系,使用来自成熟2D物体检测器的检测来生成场景中每个对象的3D提议。这些建议的3D位置证明是非常准确的,这大大降低了恢复最终3D边界框检测的难度。同时,在物体中心坐标系中预测点云以学习局部尺度和形状信息。然而,关键的挑战是如何利用形状信息来指导3D定位。因此,我们设计总损失,包括新颖的投影对准损失,以联合优化神经网络中的这些任务,以提高3D定位精度。我们在KITTI基准测试中验证了我们的方法,我们在已发布的单眼方法中设置了新的最先进的结果,包括更硬的行人和骑车人,同时保持高效的运行时间。
translated by 谷歌翻译
全身控制(WBC)是一种通用的面向任务的控制方法,用于对类人机器人中的机器人操纵行为进行反馈控制。 WBC和基于模型的步行控制器的组合已广泛用于各种类人机器人中。然而,到目前为止,WBC方法尚未用于无支撑的被动 - 踝动态运动。因此,在本文中,我们设计了一种新的WBC,称为全身运动控制器(WBLC),可以在无支撑的被动式踝式机器人上实现实验动态行走。 WBLC的一个关键方面是放宽接触约束,使得控制命令在切换脚触点时产生减少的抖动。为了实现稳健的动态运动,我们对称为时间 - 速度反转(TVR)规划器的动态步行算法进行了不确定性的深入分析。不确定性研究是基础,它允许我们改进机器人的控制算法和机械结构,以满足容忍的不确定性。此外,我们进行了广泛的实验:1)不支持的动态平衡(即在地方步进)与六自由度(DoF)两足动物,水星; 2)与水星无支撑的双向行走; 3)用水星走过一个不规则的滑溜溜; 4)使用我们新设计的10-DoFviscoelastic液冷两足动物DRACO进行就地行走。总的来说,这项工作的主要贡献在于:a)使用WBLC控制器和TVR规划器实现无支撑动态运动的各种模式,b)进行不确定性分析以改善水星的机械结构和控制器,以及c设计全身控制策略,减少行走时的运动混乱。
translated by 谷歌翻译