广义线性模型（GLM）形成了一类广泛的回归和分类模型，其中预测是输入变量的线性组合的函数。对于高维度的统计推断，事实证明，诱导正规化的稀疏性在提供统计保证时很有用。但是，解决最终的优化问题可能具有挑战性：即使对于流行的迭代算法，例如协调下降，也需要在大量变量上循环。为了减轻这种情况，称为筛选规则和工作集的技术可以通过逐步删除变量或解决增长的较小问题的序列来减少手头优化问题的大小。对于这两种技术，都可以鉴定出大量变量，这要归功于凸双重性论点。在本文中，我们表明，GLM的双重迭代在标志识别后表现出矢量自回归（VAR）行为，当使用近端梯度下降或环状坐标下降解决原始问题时。利用这种规律性，可以构建双重点，以提供最佳的最佳证书，增强筛选规则的性能并帮助设计竞争性的工作集算法。
translated by 谷歌翻译
找到模型的最佳超参数可以作为双重优化问题，通常使用零级技术解决。在这项工作中，当内部优化问题是凸但不平滑时，我们研究一阶方法。我们表明，近端梯度下降和近端坐标下降序列序列的前向模式分化，雅各比人会收敛到精确的雅各布式。使用隐式差异化，我们表明可以利用内部问题的非平滑度来加快计算。最后，当内部优化问题大约解决时，我们对高度降低的误差提供了限制。关于回归和分类问题的结果揭示了高参数优化的计算益处，尤其是在需要多个超参数时。
translated by 谷歌翻译
路径跟踪算法经常用于复合优化问题，其中一系列具有不同正则化超参数的子问题，顺序解决。通过将以前的解决方案重用为初始化，在数值上观察到更好的收敛速度。这使得它成为加速机器学习中优化算法的执行的相当有用的启发式。我们提出了路径跟踪算法的原始双重分析，并探索了如何设计其超参数，以及确定每个子问题的解决方案应该如何解决，以保证目标问题的线性收敛速度。此外，考虑用稀疏诱导惩罚的优化，我们分析了关于正则化参数的活动集的变化。然后可以自适应地校准后者以精细地确定沿解决方案路径选择的特征的数量。这导致简单的启发式校准主动集方法的超级参数，以降低他们的复杂性并提高他们的执行时间。
translated by 谷歌翻译
Sparsity promoting regularizers are widely used to impose low-complexity structure (e.g. l1-norm for sparsity) to the regression coefficients of supervised learning. In the realm of deterministic optimization, the sequence generated by iterative algorithms (such as proximal gradient descent) exhibit "finite activity identification", namely, they can identify the low-complexity structure in a finite number of iterations. However, most online algorithms (such as proximal stochastic gradient descent) do not have the property owing to the vanishing step-size and non-vanishing variance. In this paper, by combining with a screening rule, we show how to eliminate useless features of the iterates generated by online algorithms, and thereby enforce finite activity identification. One consequence is that when combined with any convergent online algorithm, sparsity properties imposed by the regularizer can be exploited for computational gains. Numerically, significant acceleration can be obtained.
translated by 谷歌翻译
一类非平滑实践优化问题可以写成，以最大程度地减少平滑且部分平滑的功能。我们考虑了这种结构化问题，这些问题也取决于参数矢量，并研究了将其解决方案映射相对于参数的问题，该参数在灵敏度分析和参数学习选择材料问题中具有很大的应用。我们表明，在部分平滑度和其他温和假设下，近端分裂算法产生的序列的自动分化（AD）会收敛于溶液映射的衍生物。对于一种自动分化的变体，我们称定点自动分化（FPAD），我们纠正了反向模式AD的内存开销问题，此外，理论上提供了更快的收敛。我们从数值上说明了套索和组套索问题的AD和FPAD的收敛性和收敛速率，并通过学习正则化项来证明FPAD在原型实用图像deoise问题上的工作。
translated by 谷歌翻译
Iterative regularization is a classic idea in regularization theory, that has recently become popular in machine learning. On the one hand, it allows to design efficient algorithms controlling at the same time numerical and statistical accuracy. On the other hand it allows to shed light on the learning curves observed while training neural networks. In this paper, we focus on iterative regularization in the context of classification. After contrasting this setting with that of regression and inverse problems, we develop an iterative regularization approach based on the use of the hinge loss function. More precisely we consider a diagonal approach for a family of algorithms for which we prove convergence as well as rates of convergence. Our approach compares favorably with other alternatives, as confirmed also in numerical simulations.
translated by 谷歌翻译
广义自我符合是许多重要学习问题的目标功能中存在的关键属性。我们建立了一个简单的Frank-Wolfe变体的收敛速率，该变体使用开环步数策略$ \ gamma_t = 2/（t+2）$，获得了$ \ Mathcal {o}（1/t）$收敛率对于这类功能，就原始差距和弗兰克 - 沃尔夫差距而言，$ t $是迭代计数。这避免了使用二阶信息或估计以前工作的局部平滑度参数的需求。我们还显示了各种常见病例的收敛速率的提高，例如，当所考虑的可行区域均匀地凸或多面体时。
translated by 谷歌翻译
最近有兴趣的兴趣在教师学生环境中的各种普遍性线性估计问题中的渐近重建性能研究，特别是对于I.I.D标准正常矩阵的案例。在这里，我们超越这些矩阵，并证明了具有具有任意界限频谱的旋转不变数据矩阵的凸遍的线性模型的重建性能的分析公式，严格地确认使用来自统计物理的副本衍生的猜想。该公式包括许多问题，例如压缩感测或稀疏物流分类。通过利用消息通过算法和迭代的统计特性来实现证明，允许表征估计器的渐近实证分布。我们的证据是基于构建Oracle多层向量近似消息传递算法的会聚序列的构建，其中通过检查等效动态系统的稳定性来完成收敛分析。我们说明了我们对主流学习方法的数值示例的要求，例如稀疏的逻辑回归和线性支持矢量分类器，显示中等大小模拟和渐近预测之间的良好一致性。
translated by 谷歌翻译
最佳子集选择被认为是许多稀疏学习问题的“黄金标准”。已经提出了各种优化技术来攻击这一非凸和NP障碍问题。在本文中，我们研究了$ \ ell_0 $登记的问题的双重形式。基于原始和双重问题结构已经开发了一种有效的原始偶对偶方法。通过利用双重范围估计以及增量策略，我们的算法可能会减少冗余计算并改善最佳子集选择的解决方案。关于合成和现实世界数据集的理论分析和实验验证了拟议溶液的效率和统计特性。
translated by 谷歌翻译
数值验证是机器学习研究的核心，因为它允许评估新方法的实际影响，并确认理论和实践之间的一致性。然而，该领域的快速发展构成了一些挑战：研究人员面临着大量的方法来比较，有限的透明度和最佳实践的共识以及乏味的重新实施工作。结果，验证通常是非常部分的，这可能会导致错误的结论，从而减慢研究的进展。我们提出了Benchopt，这是一个协作框架，旨在在跨编程语言和硬件体系结构的机器学习中自动化，复制和发布优化基准。 Benchopt通过提供用于运行，共享和扩展实验的现成工具来简化社区的基准测试。为了展示其广泛的可用性，我们在三个标准学习任务上展示基准：$ \ ell_2 $ regulaine的逻辑回归，套索和RESNET18用于图像分类的培训。这些基准强调了关键的实际发现，这些发现对这些问题的最新问题更加细微，这表明在实际评估中，魔鬼在细节上。我们希望Benchopt能在社区中促进合作工作，从而改善研究结果的可重复性。
translated by 谷歌翻译
在本文中，我们制定了一种简单而有效的筛选策略，以提高涉及noncovex $ \ ell_ {q，p} $正则化的结构化优化方面的计算效率。基于迭代重新加权的$ \ ell_1 $（irl1）框架，所提出的筛选规则就像一个预处理模块一样工作，该模块可能在启动子问题求解器之前可能会删除不活动的组，从而减少总计计算时间。这主要是通过在每次迭代过程中启发双重子问题信息来实现的。此外，我们证明我们的筛选规则可以消除IRL1方法有限数量的迭代中的所有不活动变量。数值实验说明了与几种最新算法相比，我们的筛选规则策略的效率。
translated by 谷歌翻译
我们开发了快速算法和可靠软件，以凸出具有Relu激活功能的两层神经网络的凸优化。我们的工作利用了标准的重量罚款训练问题作为一组组-YELL_1 $调查的数据本地模型的凸重新印度，其中局部由多面体锥体约束强制执行。在零规范化的特殊情况下，我们表明此问题完全等同于凸“ Gated Relu”网络的不受约束的优化。对于非零正则化的问题，我们表明凸面式relu模型获得了RELU训练问题的数据依赖性近似范围。为了优化凸的重新制定，我们开发了一种加速的近端梯度方法和实用的增强拉格朗日求解器。我们表明，这些方法比针对非凸问题（例如SGD）和超越商业内部点求解器的标准训练启发式方法要快。在实验上，我们验证了我们的理论结果，探索组-ELL_1 $正则化路径，并对神经网络进行比例凸的优化，以在MNIST和CIFAR-10上进行图像分类。
translated by 谷歌翻译
稀疏性损失最小化问题在包括机器学习，数据挖掘和现代统计的各个领域中起着重要作用。近端梯度下降法和坐标下降法是解决最小化问题的最流行方法。尽管现有方法可以实现隐式模型识别，但在有限数量的迭代中，也就是支持集合识别，但在高维情况下，这些方法仍然遭受巨大的计算成本和内存负担。原因是这些方法中的支持集识别是隐式的，因此无法明确识别实践中的低复杂性结构，即，它们无法通过降低尺寸丢弃相关特征的无用系数，以实现算法加速。为了应对这一挑战，我们提出了一种新颖的加速双随机梯度下降（ADSGD）方法，用于稀疏性损失最小化问题，这可以通过在优化过程中消除无效系数来减少块迭代次数的数量，并最终实现更快的显式模型识别和改进的模型识别和改进和改进的模型识别和改进速度算法效率。从理论上讲，我们首先证明ADSGD可以达到线性收敛速率并降低总体计算复杂性。更重要的是，我们证明ADSGD可以实现显式模型识别的线性速率。从数值上讲，基准数据集上的实验结果证实了我们提出的方法的效率。
translated by 谷歌翻译
预处理一直是优化和机器学习方面的主食技术。它通常会减少其应用于矩阵的条件数，从而加快优化算法的收敛性。尽管实践中有许多流行的预处理技术，但大多数人缺乏降低病数的理论保证。在本文中，我们研究了最佳对角线预处理的问题，以分别或同时分别或同时缩放其行或列来实现任何全级矩阵的条件数量的最大降低。我们首先将问题重新将问题重新制定为一个准凸出问题，并提供了一种基线一分配算法，该算法在实践中易于实现，其中每次迭代都包含SDP可行性问题。然后，我们建议使用$ o（\ log（\ frac {1} {\ epsilon}）））$迭代复杂度提出多项式时间潜在的降低算法，其中每个迭代均由基于Nesterov-todd方向的牛顿更新组成。我们的算法基于该问题的表述，该问题是von Neumann最佳生长问题的广义版本。接下来，我们专注于单方面的最佳对角线预处理问题，并证明它们可以作为标准双SDP问题配方，我们应用了有效的定制求解器并研究我们最佳的对角线预处理的经验性能。我们在大型矩阵上进行的广泛实验表明，与基于启发式的预处理相比，最佳对角线预处理在减少条件数方面的实际吸引力。
translated by 谷歌翻译
目前的论文研究了最小化损失$ f（\ boldsymbol {x}）$的问题，而在s $ \ boldsymbol {d} \ boldsymbol {x} \的约束，其中$ s $是一个关闭的集合，凸面或非，$ \ boldsymbol {d} $是熔化参数的矩阵。融合约束可以捕获平滑度，稀疏或更一般的约束模式。为了解决这个通用的问题，我们将Beltrami-Courant罚球方法与近距离原则相结合。后者是通过最小化惩罚目标的推动$ f（\ boldsymbol {x}）+ \ frac {\ rho} {2} \ text {dist}（\ boldsymbol {d} \ boldsymbol {x}，s）^ 2 $涉及大型调整常量$ \ rho $和$ \ boldsymbol {d} \ boldsymbol {x} $的平方欧几里德距离$ s $。通过最小化大多数代理函数$ f（\ boldsymbol {x}，从当前迭代$ \ boldsymbol {x} _n $构建相应的近距离算法的下一个迭代$ \ boldsymbol {x} _ {n + 1} $。 ）+ \ frac {\ rho} {2} \ | \ boldsymbol {d} \ boldsymbol {x} - \ mathcal {p} _ {s}（\ boldsymbol {d} \ boldsymbol {x} _n）\ | ^ 2 $。对于固定$ \ rho $和subanalytic损失$ f（\ boldsymbol {x}）$和子质约束设置$ s $，我们证明了汇聚点。在更强大的假设下，我们提供了收敛速率并展示线性本地收敛性。我们还构造了一个最陡的下降（SD）变型，以避免昂贵的线性系统解决。为了基准我们的算法，我们比较乘法器（ADMM）的交替方向方法。我们广泛的数值测试包括在度量投影，凸回归，凸聚类，总变化图像去噪和矩阵的投影到良好状态数的问题。这些实验表明了我们在高维问题上最陡的速度和可接受的准确性。
translated by 谷歌翻译
现代技术正在生成越来越多的数据。利用这些数据需要既有统计学上的声音又有效率的方法。通常，统计和计算方面会分别处理。在本文中，我们提出了一种在正规化估计的背景下纠缠这两个方面的方法。将我们的方法应用于稀疏和小组的回归，我们表明它可以在统计和计算上对标准管道进行改进。
translated by 谷歌翻译
我们在高维批处理设置中提出了统计上健壮和计算高效的线性学习方法，其中功能$ d $的数量可能超过样本量$ n $。在通用学习环境中，我们采用两种算法，具体取决于所考虑的损失函数是否为梯度lipschitz。然后，我们将我们的框架实例化，包括几种应用程序，包括香草稀疏，群 - 帕克斯和低升级矩阵恢复。对于每种应用，这导致了有效而强大的学习算法，这些算法在重尾分布和异常值的存在下达到了近乎最佳的估计率。对于香草$ S $ -SPARSITY，我们能够以重型尾巴和$ \ eta $ - 腐败的计算成本与非企业类似物相当的计算成本达到$ s \ log（d）/n $速率。我们通过开放源代码$ \ mathtt {python} $库提供了有效的算法实现文献中提出的最新方法。
translated by 谷歌翻译
我们提出了一个基于预测校正范式的统一框架，用于在原始和双空间中的预测校正范式。在此框架中，以固定的间隔进行了连续变化的优化问题，并且每个问题都通过原始或双重校正步骤近似解决。通过预测步骤的输出，该解决方案方法是温暖启动的，该步骤的输出可以使用过去的信息解决未来问题的近似。在不同的假设集中研究并比较了预测方法。该框架涵盖的算法的示例是梯度方法的时变版本，分裂方法和著名的乘数交替方向方法（ADMM）。
translated by 谷歌翻译
我们提出了一种新颖的随机弗兰克 - 沃尔夫（又名条件梯度）算法，用于使用广义的线性预测/结构进行约束的平滑有限和最小化。这类问题包括稀疏，低级别或其他结构化约束的经验风险最小化。提出的方法易于实现，不需要阶梯尺寸调整，并且具有独立于数据集大小的恒定触电成本。此外，作为该方法的副产品，我们获得了Frank-Wolfe间隙的随机估计器，可以用作停止标准。根据设置，提出的方法匹配或改进了随机Frank-Wolfe算法的最佳计算保证。几个数据集上的基准强调了不同的策略，其中所提出的方法比相关方法表现出更快的经验收敛性。最后，我们在开源软件包中提供了所有考虑的方法的实现。
translated by 谷歌翻译
我们研究了估计多元高斯分布中的精度矩阵的问题，其中所有部分相关性都是非负面的，也称为多变量完全阳性的顺序阳性（$ \ mathrm {mtp} _2 $）。近年来，这种模型得到了重大关注，主要是由于有趣的性质，例如，无论底层尺寸如何，最大似然估计值都存在于两个观察。我们将此问题作为加权$ \ ell_1 $ -norm正常化高斯的最大似然估计下$ \ mathrm {mtp} _2 $约束。在此方向上，我们提出了一种新颖的预计牛顿样算法，该算法包含精心设计的近似牛顿方向，这导致我们具有与一阶方法相同的计算和内存成本的算法。我们证明提出的预计牛顿样算法会聚到问题的最小值。从理论和实验中，我们进一步展示了我们使用加权$ \ ell_1 $ -norm的制剂的最小化器能够正确地恢复基础精密矩阵的支持，而无需在$ \ ell_1 $ -norm中存在不连贯状态方法。涉及合成和实世界数据的实验表明，我们所提出的算法从计算时间透视比最先进的方法显着更有效。最后，我们在金融时序数据中应用我们的方法，这些数据对于显示积极依赖性，在那里我们在学习金融网络上的模块间值方面观察到显着性能。
translated by 谷歌翻译