预测+优化是一个常见的真实范式,在那里我们必须在解决优化问题之前预测问题参数。然而,培训预测模型的标准通常与下游优化问题的目标不一致。最近,已经提出了集中的预测方法,例如Spo +和直接优化,以填补这种差距。但是,它们不能直接处理许多真实目标所需的$最大$算子的软限制。本文提出了一种用于现实世界线性和半定义负二次编程问题的新型分析微弱的代理目标框架,具有软线和非负面的硬度约束。该框架给出了约束乘法器上的理论界限,并导出了关于预测参数的闭合形式解决方案,从而导出问题中的任何变量的梯度。我们在使用软限制扩展的三个应用程序中评估我们的方法:合成线性规划,产品组合优化和资源供应,表明我们的方法优于传统的双阶段方法和其他集中决定的方法。
translated by 谷歌翻译
将离散域上的功能集成到神经网络中是开发其推理离散对象的能力的关键。但是,离散域是(1)自然不适合基于梯度的优化,并且(2)与依赖于高维矢量空间中表示形式的深度学习体系结构不相容。在这项工作中,我们解决了设置功能的两个困难,这些功能捕获了许多重要的离散问题。首先,我们开发了将设置功能扩展到低维连续域的框架,在该域中,许多扩展是自然定义的。我们的框架包含许多众所周知的扩展,作为特殊情况。其次,为避免不良的低维神经网络瓶颈,我们将低维扩展转换为高维空间中的表示形式,从半际计划进行组合优化的成功中获得了灵感。从经验上讲,我们观察到扩展对无监督的神经组合优化的好处,特别是具有高维其表示。
translated by 谷歌翻译
人工神经网络(ANN)训练景观的非凸起带来了固有的优化困难。虽然传统的背传播随机梯度下降(SGD)算法及其变体在某些情况下是有效的,但它们可以陷入杂散的局部最小值,并且对初始化和普通公共表敏感。最近的工作表明,随着Relu激活的ANN的培训可以重新重整为凸面计划,使希望能够全局优化可解释的ANN。然而,天真地解决凸训练制剂具有指数复杂性,甚至近似启发式需要立方时间。在这项工作中,我们描述了这种近似的质量,并开发了两个有效的算法,这些算法通过全球收敛保证培训。第一算法基于乘法器(ADMM)的交替方向方法。它解决了精确的凸形配方和近似对应物。实现线性全局收敛,并且初始几次迭代通常会产生具有高预测精度的解决方案。求解近似配方时,每次迭代时间复杂度是二次的。基于“采样凸面”理论的第二种算法更简单地实现。它解决了不受约束的凸形制剂,并收敛到大约全球最佳的分类器。当考虑对抗性培训时,ANN训练景观的非凸起加剧了。我们将稳健的凸优化理论应用于凸训练,开发凸起的凸起制剂,培训Anns对抗对抗投入。我们的分析明确地关注一个隐藏层完全连接的ANN,但可以扩展到更复杂的体系结构。
translated by 谷歌翻译
我们通过反馈信息研究了离线和在线上下文优化的问题,而不是观察损失,我们会在事后观察到最佳的动作,而是对目标功能充分了解的甲骨文。我们的目标是最大程度地减少遗憾,这被定义为我们的损失与全知的甲骨所产生的损失之间的区别。在离线设置中,决策者可以从过去段中获得信息,并且需要做出一个决策,而在在线环境中,决策者在每个时期内都会动态地基于一组新的可行动作和上下文功能,以动态进行决策。 。对于离线设置,我们表征了最佳的最小策略,确定可以实现的性能,这是数据引起的信息的基础几何形状的函数。在在线环境中,我们利用这种几何表征来优化累积遗憾。我们开发了一种算法,该算法在时间范围内产生了对数的第一个遗憾。
translated by 谷歌翻译
We describe an algorithm that learns two-layer residual units using rectified linear unit (ReLU) activation: suppose the input $\mathbf{x}$ is from a distribution with support space $\mathbb{R}^d$ and the ground-truth generative model is a residual unit of this type, given by $\mathbf{y} = \boldsymbol{B}^\ast\left[\left(\boldsymbol{A}^\ast\mathbf{x}\right)^+ + \mathbf{x}\right]$, where ground-truth network parameters $\boldsymbol{A}^\ast \in \mathbb{R}^{d\times d}$ represent a full-rank matrix with nonnegative entries and $\boldsymbol{B}^\ast \in \mathbb{R}^{m\times d}$ is full-rank with $m \geq d$ and for $\boldsymbol{c} \in \mathbb{R}^d$, $[\boldsymbol{c}^{+}]_i = \max\{0, c_i\}$. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. Following this objective landscape, learning residual units from finite samples can be formulated using convex optimization of a nonparametric function: for each layer, we first formulate the corresponding empirical risk minimization (ERM) as a positive semi-definite quadratic program (QP), then we show the solution space of the QP can be equivalently determined by a set of linear inequalities, which can then be efficiently solved by linear programming (LP). We further prove the strong statistical consistency of our algorithm, and demonstrate its robustness and sample efficiency through experimental results on synthetic data and a set of benchmark regression datasets.
translated by 谷歌翻译
本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的,我们专注于适合高维优化的方法。我们在二次模型上构建直觉,以确定哪种方法适用于非凸优化,并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础,我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外,最后一章还提供了对更多理论方法的广泛审查,这在实践中并不像惯例。所以在某些情况下,这项工作试图回答这个问题:为什么默认值中包含的默认TensorFlow优化器?
translated by 谷歌翻译
近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加,我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始,显示一般非凸面问题无法在合理的时间内有效地解决。然后,我们提供了一个问题列表,可以通过利用问题的结构来有效地找到全球最小化器,因为可能的问题。处理非凸性的另一种方法是放宽目标,从找到全局最小,以找到静止点或局部最小值。对于该设置,我们首先为确定性一阶方法的收敛速率提出了已知结果,然后是最佳随机和随机梯度方案的一般理论分析,以及随机第一阶方法的概述。之后,我们讨论了非常一般的非凸面问题,例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能,这仍然允许获得一阶的理论融合保证方法。然后,我们考虑更高阶和零序/衍生物的方法及其收敛速率,以获得非凸优化问题。
translated by 谷歌翻译
在确定性优化中,通常假定问题的所有参数都是固定和已知的。但是,实际上,某些参数可能是未知的先验参数,但可以从历史数据中估算。典型的预测 - 优化方法将预测和优化分为两个阶段。最近,端到端的预测到优化已成为有吸引力的替代方法。在这项工作中,我们介绍了PYEPO软件包,这是一个基于Pytorch的端到端预测,然后在Python中进行了优化的库。据我们所知,PYEPO(发音为“带有静音” n“”的“菠萝”)是线性和整数编程的第一个通用工具,具有预测的目标函数系数。它提供了两种基本算法:第一种基于Elmachtoub&Grigas(2021)的开创性工作的凸替代损失函数,第二个基于Vlastelica等人的可区分黑盒求解器方法。 (2019)。 PYEPO提供了一个简单的接口,用于定义新的优化问题,最先进的预测 - 优化训练算法,自定义神经网络体系结构的使用以及端到端方法与端到端方法与与端到端方法的比较两阶段的方法。 PYEPO使我们能够进行一系列全面的实验,以比较沿轴上的多种端到端和两阶段方法,例如预测准确性,决策质量和运行时间,例如最短路径,多个背包和旅行等问题销售人员问题。我们讨论了这些实验中的一些经验见解,这些见解可以指导未来的研究。 PYEPO及其文档可在https://github.com/khalil-research/pyepo上找到。
translated by 谷歌翻译
形状约束,例如非负,单调性,凸度或超模型性,在机器学习和统计的各种应用中都起着关键作用。但是,将此方面的信息以艰苦的方式(例如,在间隔的所有点)纳入预测模型,这是一个众所周知的具有挑战性的问题。我们提出了一个统一和模块化的凸优化框架,依赖于二阶锥(SOC)拧紧,以编码属于矢量值重现的载体内核Hilbert Spaces(VRKHSS)的模型对函数衍生物的硬仿射SDP约束。所提出的方法的模块化性质允许同时处理多个形状约束,并将无限数量的约束限制为有限的许多。我们证明了所提出的方案的收敛及其自适应变体的收敛性,利用VRKHSS的几何特性。由于基于覆盖的拧紧构造,该方法特别适合具有小到中等输入维度的任务。该方法的效率在形状优化,机器人技术和计量经济学的背景下进行了说明。
translated by 谷歌翻译
Outier-bubust估计是一个基本问题,已由统计学家和从业人员进行了广泛的研究。在过去的几年中,整个研究领域的融合都倾向于“算法稳定统计”,该统计数据的重点是开发可拖动的异常体 - 固定技术来解决高维估计问题。尽管存在这种融合,但跨领域的研究工作主要彼此断开。本文桥接了有关可认证的异常抗衡器估计的最新工作,该估计是机器人技术和计算机视觉中的几何感知,并在健壮的统计数据中并行工作。特别是,我们适应并扩展了最新结果对可靠的线性回归(适用于<< 50%异常值的低外壳案例)和列表可解码的回归(适用于>> 50%异常值的高淘汰案例)在机器人和视觉中通常发现的设置,其中(i)变量(例如旋转,姿势)属于非convex域,(ii)测量值是矢量值,并且(iii)未知的异常值是先验的。这里的重点是绩效保证:我们没有提出新算法,而是为投入测量提供条件,在该输入测量值下,保证现代估计算法可以在存在异常值的情况下恢复接近地面真相的估计值。这些条件是我们所谓的“估计合同”。除了现有结果的拟议扩展外,我们认为本文的主要贡献是(i)通过指出共同点和差异来统一平行的研究行,(ii)在介绍先进材料(例如,证明总和证明)中的统一行为。对从业者的可访问和独立的演讲,(iii)指出一些即时的机会和开放问题,以发出异常的几何感知。
translated by 谷歌翻译
In model selection problems for machine learning, the desire for a well-performing model with meaningful structure is typically expressed through a regularized optimization problem. In many scenarios, however, the meaningful structure is specified in some discrete space, leading to difficult nonconvex optimization problems. In this paper, we connect the model selection problem with structure-promoting regularizers to submodular function minimization with continuous and discrete arguments. In particular, we leverage the theory of submodular functions to identify a class of these problems that can be solved exactly and efficiently with an agnostic combination of discrete and continuous optimization routines. We show how simple continuous or discrete constraints can also be handled for certain problem classes and extend these ideas to a robust optimization framework. We also show how some problems outside of this class can be embedded within the class, further extending the class of problems our framework can accommodate. Finally, we numerically validate our theoretical results with several proof-of-concept examples with synthetic and real-world data, comparing against state-of-the-art algorithms.
translated by 谷歌翻译
给定数据点之间的一组差异测量值,确定哪种度量表示与输入测量最“一致”或最能捕获数据相关几何特征的度量是许多机器学习算法的关键步骤。现有方法仅限于特定类型的指标或小问题大小,因为在此类问题中有大量的度量约束。在本文中,我们提供了一种活跃的集合算法,即项目和忘记,该算法使用Bregman的预测,以解决许多(可能是指数)不平等约束的度量约束问题。我们提供了\ textsc {project and Hoses}的理论分析,并证明我们的算法会收敛到全局最佳解决方案,并以指数速率渐近地渐近地衰减了当前迭代的$ L_2 $距离。我们证明,使用我们的方法,我们可以解决三种类型的度量约束问题的大型问题实例:一般体重相关聚类,度量近距离和度量学习;在每种情况下,就CPU时间和问题尺寸而言,超越了艺术方法的表现。
translated by 谷歌翻译
本文介绍了OptNet,该网络架构集成了优化问题(这里,专门以二次程序的形式),作为较大端到端可训练的深网络中的单个层。这些层在隐藏状态之间编码约束和复杂依赖性,传统的卷积和完全连接的层通常无法捕获。我们探索这种架构的基础:我们展示了如何使用敏感性分析,彼得优化和隐式差分的技术如何通过这些层和相对于层参数精确地区分;我们为这些层开发了一种高效的解算器,用于利用基于GPU的基于GPU的批处理在原始 - 双内部点法中解决,并且在求解的顶部几乎没有额外的成本提供了反向衰减梯度;我们突出了这些方法在几个问题中的应用。在一个值得注意的示例中,该方法学习仅在输入和输出游戏中播放Mini-sudoku(4x4),没有关于游戏规则的a-priori信息;这突出了OptNet比其他神经架构更好地学习硬限制的能力。
translated by 谷歌翻译
我们开发了快速算法和可靠软件,以凸出具有Relu激活功能的两层神经网络的凸优化。我们的工作利用了标准的重量罚款训练问题作为一组组-YELL_1 $调查的数据本地模型的凸重新印度,其中局部由多面体锥体约束强制执行。在零规范化的特殊情况下,我们表明此问题完全等同于凸“ Gated Relu”网络的不受约束的优化。对于非零正则化的问题,我们表明凸面式relu模型获得了RELU训练问题的数据依赖性近似范围。为了优化凸的重新制定,我们开发了一种加速的近端梯度方法和实用的增强拉格朗日求解器。我们表明,这些方法比针对非凸问题(例如SGD)和超越商业内部点求解器的标准训练启发式方法要快。在实验上,我们验证了我们的理论结果,探索组-ELL_1 $正则化路径,并对神经网络进行比例凸的优化,以在MNIST和CIFAR-10上进行图像分类。
translated by 谷歌翻译
许多实际优化问题涉及不确定的参数,这些参数具有概率分布,可以使用上下文特征信息来估算。与首先估计不确定参数的分布然后基于估计优化目标的标准方法相反,我们提出了一个\ textIt {集成条件估计 - 优化}(ICEO)框架,该框架估计了随机参数的潜在条件分布同时考虑优化问题的结构。我们将随机参数的条件分布与上下文特征之间的关系直接建模,然后以与下游优化问题对齐的目标估算概率模型。我们表明,我们的ICEO方法在适度的规律性条件下渐近一致,并以概括范围的形式提供有限的性能保证。在计算上,使用ICEO方法执行估计是一种非凸面且通常是非差异的优化问题。我们提出了一种通用方法,用于近似从估计的条件分布到通过可区分函数的最佳决策的潜在非差异映射,这极大地改善了应用于非凸问题的基于梯度的算法的性能。我们还提供了半代理案例中的多项式优化解决方案方法。还进行了数值实验,以显示我们在不同情况下的方法的经验成功,包括数据样本和模型不匹配。
translated by 谷歌翻译
这项工作开发了具有严格效率的新算法,可确保无限的地平线模仿学习(IL)具有线性函数近似而无需限制性相干假设。我们从问题的最小值开始,然后概述如何从优化中利用经典工具,尤其是近端点方法(PPM)和双平滑性,分别用于在线和离线IL。多亏了PPM,我们避免了在以前的文献中出现在线IL的嵌套政策评估和成本更新。特别是,我们通过优化单个凸的优化和在成本和Q函数上的平稳目标来消除常规交替更新。当不确定地解决时,我们将优化错误与恢复策略的次级优势联系起来。作为额外的奖励,通过将PPM重新解释为双重平滑以专家政策为中心,我们还获得了一个离线IL IL算法,该算法在所需的专家轨迹方面享有理论保证。最后,我们实现了线性和神经网络功能近似的令人信服的经验性能。
translated by 谷歌翻译
Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.
translated by 谷歌翻译
机器学习(ML)管道中的组合优化(CO)层是解决数据驱动决策任务的强大工具,但它们面临两个主要挑战。首先,CO问题的解通常是其客观参数的分段常数函数。鉴于通常使用随机梯度下降对ML管道进行训练,因此缺乏斜率信息是非常有害的。其次,标准ML损失在组合设置中不能很好地工作。越来越多的研究通过各种方法解决了这些挑战。不幸的是,缺乏维护良好的实现会减慢采用CO层的速度。在本文的基础上,我们对CO层介绍了一种概率的观点,该观点自然而然地是近似分化和结构化损失的构建。我们从文献中恢复了许多特殊情况的方法,我们也得出了新方法。基于这个统一的观点,我们提出了inferpopt.jl,一个开源的朱莉娅软件包,1)允许将任何具有线性物镜的Co Oracle转换为可区分的层,以及2)定义足够的损失以训练包含此类层的管道。我们的图书馆使用任意优化算法,并且与朱莉娅的ML生态系统完全兼容。我们使用视频游戏地图上的探索问题来证明其能力。
translated by 谷歌翻译
我们证明了由例如He等人提出的广泛使用的方法。(2015年)并使用梯度下降对最小二乘损失进行训练并不普遍。具体而言,我们描述了一大批一维数据生成分布,较高的概率下降只会发现优化景观的局部最小值不好,因为它无法将其偏离偏差远离其初始化,以零移动。。事实证明,在这些情况下,即使目标函数是非线性的,发现的网络也基本执行线性回归。我们进一步提供了数值证据,表明在实际情况下,对于某些多维分布而发生这种情况,并且随机梯度下降表现出相似的行为。我们还提供了有关初始化和优化器的选择如何影响这种行为的经验结果。
translated by 谷歌翻译
成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型,并且通过双下降现象和通过优化景观的结构特性,从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功,但也众所周知,这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下,它们在扰动输入(鲁棒泛化)上的性能也会比良性输入(标准概括)的最佳可达到的性能更糟糕。因此,必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中,我们将通过专注于随机特征回归模型(具有随机第一层权重的两层神经网络)来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度,其中样本量,输入维度和参数的数量彼此成比例地生长,并且当模型发生前列地训练时,可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果,表明对于普遍训练的随机特征模型,高度公正化可能会损害鲁棒泛化。
translated by 谷歌翻译