在本文中，我们制定了一种简单而有效的筛选策略，以提高涉及noncovex $ \ ell_ {q，p} $正则化的结构化优化方面的计算效率。基于迭代重新加权的$ \ ell_1 $（irl1）框架，所提出的筛选规则就像一个预处理模块一样工作，该模块可能在启动子问题求解器之前可能会删除不活动的组，从而减少总计计算时间。这主要是通过在每次迭代过程中启发双重子问题信息来实现的。此外，我们证明我们的筛选规则可以消除IRL1方法有限数量的迭代中的所有不活动变量。数值实验说明了与几种最新算法相比，我们的筛选规则策略的效率。

路径跟踪算法经常用于复合优化问题，其中一系列具有不同正则化超参数的子问题，顺序解决。通过将以前的解决方案重用为初始化，在数值上观察到更好的收敛速度。这使得它成为加速机器学习中优化算法的执行的相当有用的启发式。我们提出了路径跟踪算法的原始双重分析，并探索了如何设计其超参数，以及确定每个子问题的解决方案应该如何解决，以保证目标问题的线性收敛速度。此外，考虑用稀疏诱导惩罚的优化，我们分析了关于正则化参数的活动集的变化。然后可以自适应地校准后者以精细地确定沿解决方案路径选择的特征的数量。这导致简单的启发式校准主动集方法的超级参数，以降低他们的复杂性并提高他们的执行时间。

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.

广义线性模型（GLM）形成了一类广泛的回归和分类模型，其中预测是输入变量的线性组合的函数。对于高维度的统计推断，事实证明，诱导正规化的稀疏性在提供统计保证时很有用。但是，解决最终的优化问题可能具有挑战性：即使对于流行的迭代算法，例如协调下降，也需要在大量变量上循环。为了减轻这种情况，称为筛选规则和工作集的技术可以通过逐步删除变量或解决增长的较小问题的序列来减少手头优化问题的大小。对于这两种技术，都可以鉴定出大量变量，这要归功于凸双重性论点。在本文中，我们表明，GLM的双重迭代在标志识别后表现出矢量自回归（VAR）行为，当使用近端梯度下降或环状坐标下降解决原始问题时。利用这种规律性，可以构建双重点，以提供最佳的最佳证书，增强筛选规则的性能并帮助设计竞争性的工作集算法。

稀疏性损失最小化问题在包括机器学习，数据挖掘和现代统计的各个领域中起着重要作用。近端梯度下降法和坐标下降法是解决最小化问题的最流行方法。尽管现有方法可以实现隐式模型识别，但在有限数量的迭代中，也就是支持集合识别，但在高维情况下，这些方法仍然遭受巨大的计算成本和内存负担。原因是这些方法中的支持集识别是隐式的，因此无法明确识别实践中的低复杂性结构，即，它们无法通过降低尺寸丢弃相关特征的无用系数，以实现算法加速。为了应对这一挑战，我们提出了一种新颖的加速双随机梯度下降（ADSGD）方法，用于稀疏性损失最小化问题，这可以通过在优化过程中消除无效系数来减少块迭代次数的数量，并最终实现更快的显式模型识别和改进的模型识别和改进和改进的模型识别和改进速度算法效率。从理论上讲，我们首先证明ADSGD可以达到线性收敛速率并降低总体计算复杂性。更重要的是，我们证明ADSGD可以实现显式模型识别的线性速率。从数值上讲，基准数据集上的实验结果证实了我们提出的方法的效率。

稀疏条件随机场（CRF）是一种强大的计算机视觉和结构预测的自然语言处理技术。然而，在大规模应用中解决稀疏CRF仍然具有挑战性。在本文中，我们提出了一种新的安全动态筛选方法，该方法利用准确的双重最佳估计来识别和去除训练过程中的无关功能。因此，问题大小可以连续减小，从不牺牲最终学习模型的任何准确性，以计算成本很大地节省。据我们所知，这是第一种筛选方法，介绍了双重最佳估计技术 - 通过仔细探索和利用强大的凸起和双重问题的复杂结构 - 在静态筛选方法中动态筛选。通过这种方式，我们可以吸收静态和动态筛选方法的优点，避免其缺点。我们的估计比基于二元间隙开发的估计更准确，这有助于更强大的筛选规则。此外，我们的方法也是稀疏CRFS甚至结构预测模型中的第一筛选方法。合成和现实世界数据集的实验结果表明，我们的方法获得的加速是显着的。

最佳子集选择被认为是许多稀疏学习问题的“黄金标准”。已经提出了各种优化技术来攻击这一非凸和NP障碍问题。在本文中，我们研究了$ \ ell_0 $登记的问题的双重形式。基于原始和双重问题结构已经开发了一种有效的原始偶对偶方法。通过利用双重范围估计以及增量策略，我们的算法可能会减少冗余计算并改善最佳子集选择的解决方案。关于合成和现实世界数据集的理论分析和实验验证了拟议溶液的效率和统计特性。

在本文中，我们研究了一类二聚体优化问题，也称为简单的双重优化，在其中，我们将光滑的目标函数最小化，而不是另一个凸的约束优化问题的最佳解决方案集。已经开发了几种解决此类问题的迭代方法。 las，它们的收敛保证并不令人满意，因为它们要么渐近，要么渐近，要么是收敛速度缓慢且最佳的。为了解决这个问题，在本文中，我们介绍了Frank-Wolfe（FW）方法的概括，以解决考虑的问题。我们方法的主要思想是通过切割平面在局部近似低级问题的解决方案集，然后运行FW型更新以减少上层目标。当上层目标是凸面时，我们表明我们的方法需要$ {\ mathcal {o}}（\ max \ {1/\ epsilon_f，1/\ epsilon_g \}）$迭代才能找到$ \ \ \ \ \ \ epsilon_f $ - 最佳目标目标和$ \ epsilon_g $ - 最佳目标目标。此外，当高级目标是非convex时，我们的方法需要$ {\ MATHCAL {o}}（\ max \ {1/\ epsilon_f^2,1/（\ epsilon_f \ epsilon_g}）查找$（\ epsilon_f，\ epsilon_g）$ - 最佳解决方案。我们进一步证明了在“较低级别问题的老年人错误约束假设”下的更强的融合保证。据我们所知，我们的方法实现了所考虑的二聚体问题的最著名的迭代复杂性。我们还向数值实验提出了数值实验。与最先进的方法相比，展示了我们方法的出色性能。

Convex function constrained optimization has received growing research interests lately. For a special convex problem which has strongly convex function constraints, we develop a new accelerated primal-dual first-order method that obtains an $\Ocal(1/\sqrt{\vep})$ complexity bound, improving the $\Ocal(1/{\vep})$ result for the state-of-the-art first-order methods. The key ingredient to our development is some novel techniques to progressively estimate the strong convexity of the Lagrangian function, which enables adaptive step-size selection and faster convergence performance. In addition, we show that the complexity is further improvable in terms of the dependence on some problem parameter, via a restart scheme that calls the accelerated method repeatedly. As an application, we consider sparsity-inducing constrained optimization which has a separable convex objective and a strongly convex loss constraint. In addition to achieving fast convergence, we show that the restarted method can effectively identify the sparsity pattern (active-set) of the optimal solution in finite steps. To the best of our knowledge, this is the first active-set identification result for sparsity-inducing constrained optimization.

异常值广泛发生在大数据应用中，可能严重影响统计估计和推理。在本文中，引入了抗强估计的框架，以强制任意给出的损耗函数。它与修剪方法密切连接，并且包括所有样本的显式外围参数，这反过来促进计算，理论和参数调整。为了解决非凸起和非体性的问题，我们开发可扩展的算法，以实现轻松和保证快速收敛。特别地，提出了一种新的技术来缓解对起始点的要求，使得在常规数据集上，可以大大减少数据重采样的数量。基于组合的统计和计算处理，我们能够超越M估计来执行非因思分析。所获得的抗性估算器虽然不一定全局甚至是局部最佳的，但在低维度和高维度中享有最小的速率最优性。回归，分类和神经网络的实验表明，在总异常值发生的情况下提出了拟议方法的优异性能。

基于梯度的高参数调整的优化方法可确保理论收敛到固定解决方案时，对于固定的上层变量值，双光线程序的下层级别强烈凸（LLSC）和平滑（LLS）。对于在许多机器学习算法中调整超参数引起的双重程序，不满足这种情况。在这项工作中，我们开发了一种基于不精确度（VF-IDCA）的基于依次收敛函数函数算法。我们表明，该算法从一系列的超级参数调整应用程序中实现了无LLSC和LLS假设的固定解决方案。我们的广泛实验证实了我们的理论发现，并表明，当应用于调子超参数时，提出的VF-IDCA会产生较高的性能。

我们提出了一个基于一般学习的框架，用于解决非平滑和非凸图像重建问题。我们将正则函数建模为$ l_ {2,1} $ norm的组成，并将平滑但非convex功能映射参数化为深卷积神经网络。我们通过利用Nesterov的平滑技术和残留学习的概念来开发一种可证明的趋同的下降型算法来解决非平滑非概念最小化问题，并学习网络参数，以使算法的输出与培训数据中的参考匹配。我们的方法用途广泛，因为人们可以将各种现代网络结构用于正规化，而所得网络继承了算法的保证收敛性。我们还表明，所提出的网络是参数有效的，其性能与实践中各种图像重建问题中的最新方法相比有利。

现代统计应用常常涉及最小化可能是非流动和/或非凸起的目标函数。本文侧重于广泛的Bregman-替代算法框架，包括本地线性近似，镜像下降，迭代阈值，DC编程以及许多其他实例。通过广义BREGMAN功能的重新发出使我们能够构建合适的误差测量并在可能高维度下建立非凸起和非凸起和非球形目标的全球收敛速率。对于稀疏的学习问题，在一些规律性条件下，所获得的估算器作为代理人的固定点，尽管不一定是局部最小化者，但享受可明确的统计保障，并且可以证明迭代顺序在所需的情况下接近统计事实准确地快速。本文还研究了如何通过仔细控制步骤和放松参数来设计基于适应性的动力的加速度而不假设凸性或平滑度。

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.

稀疏数据的恢复是机器学习和信号处理中许多应用的核心。虽然可以使用$ \ ell_1 $ -regularization在套索估算器中使用此类问题，但在基础上，通常需要专用算法来解决大型实例的相应高维非平滑优化。迭代地重新重复的最小二乘（IRLS）是一种广泛使用的算法，其出于其优异的数值性能。然而，虽然现有理论能够保证该算法的收敛到最小化器，但它不提供全局收敛速度。在本文中，我们证明了IRLS的变型以全局线性速率收敛到稀疏解决方案，即，如果测量结果满足通常的空空间属性假设，则立即发生线性误差。我们通过数值实验支持我们的理论，表明我们的线性速率捕获了正确的维度依赖性。我们预计我们的理论调查结果将导致IRLS算法的许多其他用例的新见解，例如在低级矩阵恢复中。

Sparse reduced rank regression is an essential statistical learning method. In the contemporary literature, estimation is typically formulated as a nonconvex optimization that often yields to a local optimum in numerical computation. Yet, their theoretical analysis is always centered on the global optimum, resulting in a discrepancy between the statistical guarantee and the numerical computation. In this research, we offer a new algorithm to address the problem and establish an almost optimal rate for the algorithmic solution. We also demonstrate that the algorithm achieves the estimation with a polynomial number of iterations. In addition, we present a generalized information criterion to simultaneously ensure the consistency of support set recovery and rank estimation. Under the proposed criterion, we show that our algorithm can achieve the oracle reduced rank estimation with a significant probability. The numerical studies and an application in the ovarian cancer genetic data demonstrate the effectiveness and scalability of our approach.

我们提出了一种估计具有标称分类数据的高维线性模型的方法。我们的估算器，称为范围，通过使其相应的系数完全相等来融合水平。这是通过对分类变量的系数的阶数统计之间的差异之间的差异来实现这一点，从而聚类系数。我们提供了一种算法，用于精确和有效地计算在具有潜在许多级别的单个变量的情况下的总体上的最小值的全局最小值，并且在多变量情况下在块坐标血管下降过程中使用它。我们表明，利用未知级别融合的Oracle最小二乘解决方案是具有高概率的坐标血缘的极限点，只要真正的级别具有一定的最小分离;已知这些条件在单变量案例中最小。我们展示了在一系列实际和模拟数据集中的范围的有利性能。 R包的R包Catreg实现线性模型的范围，也可以在CRAN上提供逻辑回归的版本。

我们在高维批处理设置中提出了统计上健壮和计算高效的线性学习方法，其中功能$ d $的数量可能超过样本量$ n $。在通用学习环境中，我们采用两种算法，具体取决于所考虑的损失函数是否为梯度lipschitz。然后，我们将我们的框架实例化，包括几种应用程序，包括香草稀疏，群 - 帕克斯和低升级矩阵恢复。对于每种应用，这导致了有效而强大的学习算法，这些算法在重尾分布和异常值的存在下达到了近乎最佳的估计率。对于香草$ S $ -SPARSITY，我们能够以重型尾巴和$ \ eta $ - 腐败的计算成本与非企业类似物相当的计算成本达到$ s \ log（d）/n $速率。我们通过开放源代码$ \ mathtt {python} $库提供了有效的算法实现文献中提出的最新方法。

本文主要侧重于计算向量的欧几里德投影到$ \ ell_ {p} $ ball，其中$ p \ in（0,1）$。这种问题是统计机器学习中的核心构建块和信号处理任务，因为它促进了稀疏性的能力。但是，用于查找投影的有效数值算法仍然不可用，特别是在大规模优化中。为满足这一挑战，我们首先推出了这个问题的一流必备的最优性条件。基于该表征，我们通过求解一系列投影来制定一种用于计算静止点的新颖性方法，以在重新重量$ \ ell_ {1} $ - 球上。这种方法实际上是简单的实现和计算效率。此外，所提出的算法显示在温和条件下唯一会聚，并且具有最坏情况$ O（1 / \ SQRT {k}）$收敛速率。数值实验证明了我们所提出的算法的效率。

现代技术正在生成越来越多的数据。利用这些数据需要既有统计学上的声音又有效率的方法。通常，统计和计算方面会分别处理。在本文中，我们提出了一种在正规化估计的背景下纠缠这两个方面的方法。将我们的方法应用于稀疏和小组的回归，我们表明它可以在统计和计算上对标准管道进行改进。