We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.
translated by 谷歌翻译
我们研究随机梯度下降(SGD)在多大程度上被理解为“常规”学习规则,该规则通过获得良好的培训数据来实现概括性能。我们考虑基本的随机凸优化框架,其中(一通道,无需替代)SGD在经典上是众所周知的,可以最大程度地降低人口风险,以$ o(1/\ sqrt n)$ $ O(1/\ sqrt n)$,并且出人意料地证明,存在问题实例SGD解决方案既表现出$ \ omega(1)$的经验风险和概括差距。因此,事实证明,从任何意义上讲,SGD在算法上都不是稳定的,并且其概括能力不能通过均匀的收敛性或任何其他当前已知的概括性结合技术来解释(除了其经典分析外)。然后,我们继续分析与替代SGD密切相关的相关性,为此我们表明不会发生类似现象,并证明其人口风险实际上确实以最佳速度融合。最后,我们在没有替换SGD的背景下解释了我们的主要结果,用于有限的和凸优化问题,并得出多上类别制度的上限和下限,从而在先前已知的结果上有了显着改善。
translated by 谷歌翻译
最近,随机梯度下降(SGD)及其变体已成为机器学习(ML)问题大规模优化的主要方法。已经提出了各种策略来调整步骤尺寸,从自适应步骤大小到启发式方法,以更改每次迭代中的步骤大小。此外,动力已被广泛用于ML任务以加速训练过程。然而,我们对它们的理论理解存在差距。在这项工作中,我们开始通过为一些启发式优化方法提供正式保证并提出改进的算法来缩小这一差距。首先,我们分析了凸面和非凸口设置的Adagrad(延迟Adagrad)步骤大小的广义版本,这表明这些步骤尺寸允许算法自动适应随机梯度的噪声水平。我们首次显示延迟Adagrad的足够条件,以确保梯度几乎融合到零。此外,我们对延迟的Adagrad及其在非凸面设置中的动量变体进行了高概率分析。其次,我们用指数级和余弦的步骤分析了SGD,在经验上取得了成功,但缺乏理论支持。我们在平滑和非凸的设置中为它们提供了最初的收敛保证,有或没有polyak-{\ l} ojasiewicz(pl)条件。我们还显示了它们在PL条件下适应噪声的良好特性。第三,我们研究动量方法的最后迭代。我们证明了SGD的最后一个迭代的凸设置中的第一个下限,并以恒定的动量。此外,我们研究了一类跟随基于领先的领导者的动量算法,并随着动量和收缩的更新而增加。我们表明,他们的最后一个迭代具有最佳的收敛性,用于无约束的凸随机优化问题。
translated by 谷歌翻译
We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoercive -- and more generally Lipschitz-monotone -- setup, our algorithm attains $\epsilon$ norm of the operator with $\mathcal{O}(\frac{1}{\epsilon^3})$ stochastic operator evaluations, which significantly improves over state of the art $\mathcal{O}(\frac{1}{\epsilon^4})$ stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how to couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with ${\mathcal{O}}(\frac{\log(1/\epsilon)}{\epsilon^2})$ stochastic operator evaluations under additional sharpness or strong monotonicity assumptions.
translated by 谷歌翻译
近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加,我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始,显示一般非凸面问题无法在合理的时间内有效地解决。然后,我们提供了一个问题列表,可以通过利用问题的结构来有效地找到全球最小化器,因为可能的问题。处理非凸性的另一种方法是放宽目标,从找到全局最小,以找到静止点或局部最小值。对于该设置,我们首先为确定性一阶方法的收敛速率提出了已知结果,然后是最佳随机和随机梯度方案的一般理论分析,以及随机第一阶方法的概述。之后,我们讨论了非常一般的非凸面问题,例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能,这仍然允许获得一阶的理论融合保证方法。然后,我们考虑更高阶和零序/衍生物的方法及其收敛速率,以获得非凸优化问题。
translated by 谷歌翻译
我们考虑非凸凹minimax问题,$ \ min _ {\ mathbf {x}} \ mathcal {y}} f(\ mathbf {x},\ mathbf {y})$, $ f $在$ \ mathbf {x} $ on $ \ mathbf {y} $和$ \ mathcal {y} $中的$ \ \ mathbf {y} $。解决此问题的最受欢迎的算法之一是庆祝的梯度下降上升(GDA)算法,已广泛用于机器学习,控制理论和经济学。尽管凸凹设置的广泛收敛结果,但具有相等步骤的GDA可以收敛以限制循环甚至在一般设置中发散。在本文中,我们介绍了两次尺度GDA的复杂性结果,以解决非膨胀凹入的最小问题,表明该算法可以找到函数$ \ phi(\ cdot)的静止点:= \ max _ {\ mathbf {Y} \ In \ Mathcal {Y}} F(\ CDOT,\ MATHBF {Y})高效。据我们所知,这是对这一环境中的两次尺度GDA的第一个非因对药分析,阐明了其在培训生成对抗网络(GANS)和其他实际应用中的优越实际表现。
translated by 谷歌翻译
最近,在学习没有更换SGD的收敛率的情况下,有很多兴趣,并证明它在最坏情况下比更换SGD更快。然而,已知的下限忽略了问题的几何形状,包括其条件号,而上限明确取决于它。也许令人惊讶的是,我们证明,当考虑条件号时,没有替换SGD \ EMPH {没有}在最坏情况下,除非是时期的数量(通过数据来说)大于条件号。由于机器学习和其他领域的许多问题都没有条件并涉及大型数据集,这表明没有替换不一定改善用于现实迭代预算的更换采样。我们通过提供具有紧密(最多日志因子)的新下限和上限来展示这一点,用于致通二次术语的二次问题,精确地量化了对问题参数的依赖性。
translated by 谷歌翻译
加速的近端算法(APPA),也称为“催化剂”,是从凸优化到近似近端计算(即正则最小化)的确定还原。这种减少在概念上是优雅的,可以保证强大的收敛速度。但是,这些速率具有多余的对数项,因此需要计算每个近端点至高精度。在这项工作中,我们提出了一个新颖的放松误差标准,用于加速近端点(recapp),以消除对高精度子问题解决方案的需求。我们将recapp应用于两个规范问题:有限的和最大结构的最小化。对于有限和问题,我们匹配了以前通过精心设计的问题特异性算法获得的最著名的复杂性。为了最大程度地减少$ \ max_y f(x,y)$,其中$ f $以$ x $为$ x $,而在$ y $中强烈concave,我们改进了受对数因素限制的最著名的(基于催化剂)。
translated by 谷歌翻译
我们提出了一种基于优化的基于优化的框架,用于计算差异私有M估算器以及构建差分私立置信区的新方法。首先,我们表明稳健的统计数据可以与嘈杂的梯度下降或嘈杂的牛顿方法结合使用,以便分别获得具有全局线性或二次收敛的最佳私人估算。我们在局部强大的凸起和自我协调下建立当地和全球融合保障,表明我们的私人估算变为对非私人M估计的几乎最佳附近的高概率。其次,我们通过构建我们私有M估计的渐近方差的差异私有估算来解决参数化推断的问题。这自然导致近​​似枢轴统计,用于构建置信区并进行假设检测。我们展示了偏置校正的有效性,以提高模拟中的小样本实证性能。我们说明了我们在若干数值例子中的方法的好处。
translated by 谷歌翻译
我们提供了新的基于梯度的方法,以便有效解决广泛的病态化优化问题。我们考虑最小化函数$ f:\ mathbb {r} ^ d \ lightarrow \ mathbb {r} $的问题,它是隐含的可分解的,作为$ m $未知的非交互方式的总和,强烈的凸起功能并提供方法这解决了这个问题,这些问题是缩放(最快的对数因子)作为组件的条件数量的平方根的乘积。这种复杂性绑定(我们证明几乎是最佳的)可以几乎指出的是加速梯度方法的几乎是指数的,这将作为$ F $的条件数量的平方根。此外,我们提供了求解该多尺度优化问题的随机异标变体的有效方法。而不是学习$ F $的分解(这将是过度昂贵的),而是我们的方法应用一个清洁递归“大步小步”交错标准方法。由此产生的算法使用$ \ tilde {\ mathcal {o}}(d m)$空间,在数字上稳定,并打开门以更细粒度的了解凸优化超出条件号的复杂性。
translated by 谷歌翻译
We introduce a new tool for stochastic convex optimization (SCO): a Reweighted Stochastic Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. Combining ReSQue with recent advances in ball oracle acceleration [CJJJLST20, ACJJS21], we develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings. For a SCO objective constrained to the unit ball in $\mathbb{R}^d$, we obtain the following results (up to polylogarithmic factors). We give a parallel algorithm obtaining optimization error $\epsilon_{\text{opt}}$ with $d^{1/3}\epsilon_{\text{opt}}^{-2/3}$ gradient oracle query depth and $d^{1/3}\epsilon_{\text{opt}}^{-2/3} + \epsilon_{\text{opt}}^{-2}$ gradient queries in total, assuming access to a bounded-variance stochastic gradient estimator. For $\epsilon_{\text{opt}} \in [d^{-1}, d^{-1/4}]$, our algorithm matches the state-of-the-art oracle depth of [BJLLS19] while maintaining the optimal total work of stochastic gradient descent. We give an $(\epsilon_{\text{dp}}, \delta)$-differentially private algorithm which, given $n$ samples of Lipschitz loss functions, obtains near-optimal optimization error and makes $\min(n, n^2\epsilon_{\text{dp}}^2 d^{-1}) + \min(n^{4/3}\epsilon_{\text{dp}}^{1/3}, (nd)^{2/3}\epsilon_{\text{dp}}^{-1})$ queries to the gradients of these functions. In the regime $d \le n \epsilon_{\text{dp}}^{2}$, where privacy comes at no cost in terms of the optimal loss up to constants, our algorithm uses $n + (nd)^{2/3}\epsilon_{\text{dp}}^{-1}$ queries and improves recent advancements of [KLL21, AFKT21]. In the moderately low-dimensional setting $d \le \sqrt n \epsilon_{\text{dp}}^{3/2}$, our query complexity is near-linear.
translated by 谷歌翻译
This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the wellknown convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free.Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.
translated by 谷歌翻译
We show that parametric models trained by a stochastic gradient method (SGM) with few iterations have vanishing generalization error. We prove our results by arguing that SGM is algorithmically stable in the sense of Bousquet and Elisseeff. Our analysis only employs elementary tools from convex and continuous optimization. We derive stability bounds for both convex and non-convex optimization under standard Lipschitz and smoothness assumptions.Applying our results to the convex case, we provide new insights for why multiple epochs of stochastic gradient methods generalize well in practice. In the non-convex case, we give a new interpretation of common practices in neural networks, and formally show that popular techniques for training large deep models are indeed stability-promoting. Our findings conceptually underscore the importance of reducing training time beyond its obvious benefit.
translated by 谷歌翻译
最近对基于置换的SGD的接地结果进行了证实了广泛观察到的现象:随机排列提供更快的收敛性,而不是更换采样。但是,是随机的最佳状态吗?我们表明这一点在很大程度上取决于我们正在优化的功能,并且最佳和随机排放之间的收敛差距可能因指数而异。我们首先表明,对于具有光滑的第二衍生物的1维强凸功能,与随机相比,存在令人指导的收敛性的排列。但是,对于一般强凸的功能,随机排列是最佳的。最后,我们表明,对于二次,强凸的功能,与随机相比,存在易于构建的置换,从而导致加速会聚。我们的研究结果表明,最佳排列的一般收敛性表征不能捕获各个函数类的细微差别,并且可能错误地表明一个人不能比随机更好。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们研究了具有有限和结构的平滑非凸化优化问题的随机重新洗脱(RR)方法。虽然该方法在诸如神经网络的训练之类的实践中广泛利用,但其会聚行为仅在几个有限的环境中被理解。在本文中,在众所周知的Kurdyka-LojasiewiCz(KL)不等式下,我们建立了具有适当递减步长尺寸的RR的强极限点收敛结果,即,RR产生的整个迭代序列是会聚并会聚到单个静止点几乎肯定的感觉。 In addition, we derive the corresponding rate of convergence, depending on the KL exponent and the suitably selected diminishing step sizes.当KL指数在$ [0,\ FRAC12] $以$ [0,\ FRAC12] $时,收敛率以$ \ mathcal {o}(t ^ { - 1})$的速率计算,以$ t $ counting迭代号。当KL指数属于$(\ FRAC12,1)$时,我们的派生收敛速率是FORM $ \ MATHCAL {O}(T ^ { - Q})$,$ Q \ IN(0,1)$取决于在KL指数上。基于标准的KL不等式的收敛分析框架仅适用于具有某种阶段性的算法。我们对基于KL不等式的步长尺寸减少的非下降RR方法进行了新的收敛性分析,这概括了标准KL框架。我们总结了我们在非正式分析框架中的主要步骤和核心思想,这些框架是独立的兴趣。作为本框架的直接应用,我们还建立了类似的强极限点收敛结果,为重组的近端点法。
translated by 谷歌翻译
我们的目标是使随机梯度$ \ sigma^2 $在随机梯度和(ii)问题依赖性常数中自适应(i)自适应。当最大程度地减少条件编号$ \ kappa $的平滑,强大的功能时,我们证明,$ t $ t $ toerations sgd的$ t $ toerations sgd具有指数降低的阶跃尺寸和对平滑度的知识可以实现$ \ tilde {o} \ left(\ exp) \ left(\ frac {-t} {\ kappa} \ right) + \ frac {\ sigma^2} {t} \ right)$ rate,而又不知道$ \ sigma^2 $。为了适应平滑度,我们使用随机线路搜索(SLS)并显示(通过上下距离),其SGD的SGD与SLS以所需的速率收敛,但仅针对溶液的邻域。另一方面,我们证明具有平滑度的离线估计值的SGD会收敛到最小化器。但是,其速率与估计误差成正比的速度减慢。接下来,我们证明具有Nesterov加速度和指数步骤尺寸(称为ASGD)的SGD可以实现接近最佳的$ \ tilde {o} \ left(\ exp \ left(\ frac {-t} {-t} {\ sqrt {\ sqrt {\ sqrt { \ kappa}}} \ right) + \ frac {\ sigma^2} {t} \ right)$ rate,而无需$ \ sigma^2 $。当与平滑度和强频率的离线估计值一起使用时,ASGD仍会收敛到溶液,尽管速度较慢。我们从经验上证明了指数级尺寸的有效性以及新型SLS的变体。
translated by 谷歌翻译
零顺序(ZO)优化广泛用于处理具有挑战性的任务,例如基于查询的黑匣子对抗攻击和加强学习。已经提出了各种尝试,以基于有限差异将先前信息集成到梯度估计过程中,具有有前途的经验结果。然而,它们的收敛性质不太了解。本文试图通过分析具有各种梯度估计的贪婪下降框架下的先前引导的ZO算法的收敛来填补这种差距。我们为先前引导的随机梯度(PRGF)算法提供了收敛保障。此外,为了进一步加速贪婪的下降方法,我们提出了一种新的加速随机搜索(ARS)算法,其将先前信息与收敛分析一起结合在一起。最后,我们的理论结果是通过关于几个数值基准以及对抗性攻击的实验确认。
translated by 谷歌翻译
在本文中,我们提出了一种称为ANITA的新型加速梯度方法,用于解决基本的有限和优化问题。具体而言,我们同时考虑一般凸面和强烈凸面设置:i)对于一般凸有限的和有限的问题,Anita改善了Varag给定的先前最新结果(Lan等,2019)。特别是,对于大规模问题或收敛错误不是很小,即$ n \ geq \ frac {1} {\ epsilon^2} $,Anita获得\ emph {first} optimal restion $ o(n )$,匹配Woodworth and Srebro(2016)提供的下限$ \ Omega(N)$,而先前的结果为$ O(N \ log \ frac {1} {\ epsilon})$ 。 ii)对于强烈凸有限的问题,我们还表明,Anita可以实现最佳收敛速率$ o \ big(((n+\ sqrt {\ frac {\ frac {nl} {\ mu}} {\ mu}})\ log \ log \ frac {1} {1} {1} {1} { \ epsilon} \ big)$匹配下限$ \ omega \ big(((n+\ sqrt {\ frac {nl} {nl} {\ mu}})\ log \ frac {1} {\ epsilon} {\ epsilon} \ big) Lan and Zhou(2015)。此外,与以前的加速算法(如Varag(Lan等,2019)和Katyusha(Allen-Zhu,2017年),Anita享有更简单的无环算法结构。此外,我们提供了一种新颖的\ emph {动态多阶段收敛分析},这是将先前结果提高到最佳速率的关键技术。我们认为,针对基本有限和有限问题的新理论率和新颖的收敛分析将直接导致许多其他相关问题(例如分布式/联合/联合/分散的优化问题)的关键改进(例如,Li和Richt \'Arik,2021年,2021年)。最后,数值实验表明,Anita收敛的速度比以前的最先进的Varag(Lan等,2019)更快,从而验证了我们的理论结果并证实了Anita的实践优势。
translated by 谷歌翻译
用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升(SGDA)和最近引入的随机共识优化(SCO)[Mescheder等,2017]。已知SGDA可以收敛到特定类别的游戏的静止点,但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题,但其收敛保证仅限于其确定性变体。在这项工作中,我们介绍了预期的共同胁迫条件,解释了它的好处,并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证,以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时,当它们使用恒定的步长时,我们提出了富有识别的步骤化切换规则,以保证对确切解决方案的融合。此外,我们的收敛保证在任意抽样范式下担保,因此,我们对迷你匹配的复杂性进行了解。
translated by 谷歌翻译