模型不合时宜的元学习(MAML)目前是少量元学习的主要方法之一。尽管它具有有效性,但由于先天的二聚体问题结构,MAML的优化可能具有挑战性。具体而言,MAML的损失格局比其经验风险最小化的对应物更为复杂,可能的鞍点和局部最小化可能更复杂。为了应对这一挑战,我们利用了最近发明的清晰度最小化的最小化,并开发出一种清晰感的MAML方法,我们称其为Sharp MAML。我们从经验上证明,Sharp-MAML及其计算有效的变体可以胜过流行的现有MAML基准(例如,Mini-Imagenet上的$+12 \%$ $精度)。我们通过收敛速率分析和尖锐MAML的概括结合进行了经验研究。据我们所知,这是在双层学习背景下对清晰度感知最小化的第一个经验和理论研究。该代码可在https://github.com/mominabbass/sharp-maml上找到。
translated by 谷歌翻译
清晰度感知最小化(SAM)是一种最近的训练方法,它依赖于最严重的重量扰动,可显着改善各种环境中的概括。我们认为,基于pac-bayes概括结合的SAM成功的现有理由,而收敛到平面最小值的想法是不完整的。此外,没有解释说在SAM中使用$ m $ sharpness的成功,这对于概括而言至关重要。为了更好地理解SAM的这一方面,我们理论上分析了其对角线性网络的隐式偏差。我们证明,SAM总是选择一种比标准梯度下降更好的解决方案,用于某些类别的问题,并且通过使用$ m $ -sharpness可以放大这种效果。我们进一步研究了隐性偏见在非线性网络上的特性,在经验上,我们表明使用SAM进行微调的标准模型可以导致显着的概括改进。最后,当与随机梯度一起使用时,我们为非凸目标提供了SAM的收敛结果。我们从经验上说明了深层网络的这些结果,并讨论了它们与SAM的概括行为的关系。我们的实验代码可在https://github.com/tml-epfl/understanding-sam上获得。
translated by 谷歌翻译
In today's heavily overparameterized models, the value of the training loss provides few guarantees on model generalization ability. Indeed, optimizing only the training loss value, as is commonly done, can easily lead to suboptimal model quality. Motivated by prior work connecting the geometry of the loss landscape and generalization, we introduce a novel, effective procedure for instead simultaneously minimizing loss value and loss sharpness. In particular, our procedure, Sharpness-Aware Minimization (SAM), seeks parameters that lie in neighborhoods having uniformly low loss; this formulation results in a minmax optimization problem on which gradient descent can be performed efficiently. We present empirical results showing that SAM improves model generalization across a variety of benchmark datasets (e.g., CIFAR-{10, 100}, Ima-geNet, finetuning tasks) and models, yielding novel state-of-the-art performance for several. Additionally, we find that SAM natively provides robustness to label noise on par with that provided by state-of-the-art procedures that specifically target learning with noisy labels. We open source our code at https: //github.com/google-research/sam. * Work done as part of the Google AI Residency program.
translated by 谷歌翻译
在本文中,我们考虑基于移动普通(SEMA)的广泛使用但不完全了解随机估计器,其仅需要{\ bf是一般无偏的随机oracle}。我们展示了Sema在一系列随机非凸优化问题上的力量。特别是,我们分析了基于SEMA的SEMA的{\ BF差异递归性能的各种随机方法(现有或新提出),即三个非凸优化,即标准随机非凸起最小化,随机非凸强烈凹入最小最大优化,随机均方优化。我们的贡献包括:(i)对于标准随机非凸起最小化,我们向亚当风格方法(包括ADAM,AMSGRAD,Adabound等)提供了一个简单而直观的融合证明,随着越来越大的“势头” “一阶时刻的参数,它给出了一种替代但更自然的方式来保证亚当融合; (ii)对于随机非凸强度凹入的最小值优化,我们介绍了一种基于移动平均估计器的单环原始 - 双随机动量和自适应方法,并确定其Oracle复杂性$ O(1 / \ epsilon ^ 4)$不使用大型批量大小,解决文献中的差距; (iii)对于随机双脚优化,我们介绍了一种基于移动平均估计器的单环随机方法,并确定其Oracle复杂性$ \ widetilde o(1 / \ epsilon ^ 4)$,而无需计算Hessian矩阵的SVD,改善最先进的结果。对于所有这些问题,我们还建立了使用随机梯度估计器的差异递减结果。
translated by 谷歌翻译
我们分析了一类养生问题,其中高级问题在于平滑的目标函数的最小化和下层问题是找到平滑收缩图的固定点。这种类型的问题包括元学习,平衡模型,超参数优化和数据中毒对抗性攻击的实例。最近的几项作品提出了算法,这些算法温暖了较低级别的问题,即他们使用先前的下级近似解决方案作为低级求解器的凝视点。这种温暖的启动程序使人们可以在随机和确定性设置中提高样品复杂性,在某些情况下可以实现订单的最佳样品复杂性。但是,存在一些情况,例如元学习和平衡模型,其中温暖的启动程序不适合或无效。在这项工作中,我们表明没有温暖的启动,仍然可以实现订单的最佳或近乎最佳的样品复杂性。特别是,我们提出了一种简单的方法,该方法在下层下使用随机固定点迭代,并在上层处预测不精确的梯度下降,该梯度下降到达$ \ epsilon $ -Stationary Point,使用$ O(\ Epsilon^{-2) })$和$ \ tilde {o}(\ epsilon^{ - 1})$样本分别用于随机和确定性设置。最后,与使用温暖启动的方法相比,我们的方法产生了更简单的分析,不需要研究上层和下层迭代之间的耦合相互作用
translated by 谷歌翻译
域泛化(DG)方法旨在通过仅使用来自源域的训练数据来实现未经证明的目标域的概括性。虽然已经提出了各种DG方法,但最近的一项研究表明,在一个公平的评估方案下,称为域底,简单的经验风险最小化(ERM)方法可与以前的方法相当。不幸的是,简单地解决了ERM在复杂的非凸损函数上,可以通过寻求尖锐的最小值来容易地导致次优化的普遍性。在本文中,我们理论上表明发现扁平最小值导致较小的域泛化差距。我们还提出了一种简单而有效的方法,名为随机重量平均(纵向),找到扁平的最小值。瑞郎发现更漂亮的最小值,并且由于通过密集和过度感知的随机重量采样策略而遭受的过度装备不足。瑞士瑞士展示了五个DG基准测试,即PACS,VLC,OfficeHome,Terraincognita和Domainnet的最先进的表演,符合域名准确度的一致和大幅度+ 1.6%。我们还与常规的泛化方法(如数据增强和一致性正则化方法)进行比较,以验证显着的性能改进是通过寻求扁平的最小值,而不是更好的域概括性。最后但并非最不重要的是,瑞士剧本适应现有的DG方法而无需修改;施联和现有DG方法的组合进一步提高了DG性能。源代码可在https://github.com/khanrc/swad提供。
translated by 谷歌翻译
FEDPROX算法是一种简单但功能强大的分布式近端优化方法,广泛用于联合学习(FL)而不是异质数据。尽管在实践中看到了它的知名度和杰出的成功,但对FEDPROX的理论理解在很大程度上是不足的:FedProx的吸引人的融合行为迄今在某些非标准和不切实际的地方功能的差异假设下的特征是,结果的优化仅限于优化的限制。问题。为了解决这些缺陷,我们通过算法稳定性的镜头开发了FedProx及其Minibatch随机扩展的新型局部差异不变理论。结果,我们有助于得出对FedProx的几个新的和更深入的见解,以实现联合优化的非凸面,包括:1)收敛确保独立于局部差异类型条件; 2)融合保证非平滑FL问题; 3)关于Minibatch的尺寸和采样设备的数量,线性加速。我们的理论首次揭示了局部差异和平稳性对于FedProx获得有利的复杂性界限并不是必备的。据报道,一系列基准FL数据集的初步实验结果证明了小型匹配以提高FEDPROX的样品效率的好处。
translated by 谷歌翻译
模型 - 不可知的元学习(MAML),一种流行的基于梯度的元学习框架,假设每个任务或实例对元学习​​者的贡献相等。因此,在几次拍摄学习中,它无法解决基本和新颖类之间的域转移。在这项工作中,我们提出了一种新颖的鲁棒元学习算法,巢式MAML,它学会为训练任务或实例分配权重。我们将权重用为超参数,并使用嵌套双级优化方法中设置的一小组验证任务迭代优化它们(与MAML中的标准双级优化相比)。然后,我们在元培训阶段应用NestedMaml,涉及(1)从不同于元测试任务分发的分布中采样的多个任务,或(2)具有嘈杂标签的某些数据样本。对综合和现实世界数据集的广泛实验表明,巢式米姆有效地减轻了“不需要的”任务或情况的影响,从而实现了最先进的强大的元学习方法的显着改善。
translated by 谷歌翻译
最近,模型 - 不可知的元学习(MAML)已经获得了巨大的关注。然而,MAML的随机优化仍然不成熟。 MAML的现有算法利用“剧集”思想,通过对每个迭代的每个采样任务进行采样和一些数据点来更新元模型。但是,它们不一定能够以恒定的小批量大小保证收敛,或者需要在每次迭代时处理大量任务,这对于持续学习或跨设备联合学习不可行,其中仅提供少量任务每次迭代或每轮。本文通过(i)提出了与消失收敛误差的有效的基于内存的随机算法提出了基于存储的基于存储器的随机算法,这只需要采样恒定数量的任务和恒定数量的每次迭代数据样本; (ii)提出基于通信的分布式内存基于存储器的MAML算法,用于跨设备(带客户端采样)和跨筒仓(无客户采样)设置中的个性化联合学习。理论结果显着改善了MAML的优化理论,实证结果也证实了理论。
translated by 谷歌翻译
模型不足的元学习(MAML)已越来越流行,对于可以通过一个或几个随机梯度下降步骤迅速适应新任务的训练模型。但是,与标准的非自适应学习(NAL)相比,MAML目标更难优化,并且几乎没有理解MAML在各种情况下的溶液的快速适应性方面的改善。我们通过线性回归设置进行分析解决此问题,该设置由简单而艰难的任务组成,其中硬度与梯度下降在任务上收敛的速率有关。具体而言,我们证明,为了使MAML比NAL获得可观的收益,(i)任务之间的硬度必须有一定的差异,并且(ii)艰苦任务的最佳解决方案必须与中心远离远离中心。简单任务最佳解决方案的中心。我们还提供数值和分析结果,表明这些见解适用于两层神经网络。最后,我们提供了很少的图像分类实验,可以支持我们何时使用MAML的见解,并强调培训MAML对实践中的艰巨任务的重要性。
translated by 谷歌翻译
近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加,我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始,显示一般非凸面问题无法在合理的时间内有效地解决。然后,我们提供了一个问题列表,可以通过利用问题的结构来有效地找到全球最小化器,因为可能的问题。处理非凸性的另一种方法是放宽目标,从找到全局最小,以找到静止点或局部最小值。对于该设置,我们首先为确定性一阶方法的收敛速率提出了已知结果,然后是最佳随机和随机梯度方案的一般理论分析,以及随机第一阶方法的概述。之后,我们讨论了非常一般的非凸面问题,例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能,这仍然允许获得一阶的理论融合保证方法。然后,我们考虑更高阶和零序/衍生物的方法及其收敛速率,以获得非凸优化问题。
translated by 谷歌翻译
在本文中,我们研究了模型 - 不可知的元学习(MAML)算法的泛化特性,用于监督学习问题。我们专注于我们培训MAML模型超过$ M $任务的设置,每个都有$ n $数据点,并从两个视角表征其泛化错误:首先,我们假设测试时间的新任务是其中之一培训任务,我们表明,对于强烈凸的客观函数,预期的多余人口损失是由$ {\ mathcal {o}}(1 / mn)$的界限。其次,我们考虑MAML算法的概念任务的泛化,并表明产生的泛化误差取决于新任务的底层分布与培训过程中观察到的任务之间的总变化距离。我们的校对技术依赖于算法稳定性与算法的泛化界之间的连接。特别是,我们为元学习算法提出了一种新的稳定性定义,这使我们能够捕获每项任务的任务数量的任务数量的角色$ N $对MAML的泛化误差。
translated by 谷歌翻译
NDCG是标准化的折扣累积增益,是信息检索和机器学习中广泛使用的排名指标。但是,仍然缺乏最大化NDCG的有效且可证明的随机方法,尤其是对于深层模型。在本文中,我们提出了一种优化NDCG及其最高$ K $变体的原则方法。首先,我们制定了一个新颖的组成优化问题,以优化NDCG替代物,以及一个新型的双层构图优化问题,用于优化顶部$ K $ NDCG代理。然后,我们开发有效的随机算法,并为非凸目标提供可证明的收敛保证。与现有的NDCG优化方法不同,我们的算法量表的均量复杂性与迷你批量大小,而不是总项目的数量。为了提高深度学习的有效性,我们通过使用初始热身和停止梯度操作员进一步提出实用策略。多个数据集的实验结果表明,我们的方法在NDCG方面优于先前的排名方法。据我们所知,这是首次提出随机算法以优化具有可证明的收敛保证的NDCG。我们提出的方法在https://libauc.org/的libauc库中实现。
translated by 谷歌翻译
随机一阶方法是训练大规模机器学习模型的标准。随机行为可能导致算法的特定运行导​​致高度次优的目标值,而通常证明理论保证是出于目标值的期望。因此,从理论上保证算法具有很高的可能性,这一点至关重要。非平滑随机凸优化的现有方法具有复杂的界限,其依赖性对置信度或对数为负功率,但在额外的假设下是高斯(轻尾)噪声分布的额外假设,这些噪声分布在实践中可能不存在。在我们的论文中,我们解决了这个问题,并得出了第一个高概率收敛的结果,并以对数依赖性对非平滑凸的随机优化问题的置信度依赖,并带有非Sub-Gaussian(重尾)噪声。为了得出我们的结果,我们建议针对两种随机方法进行梯度剪辑的新步骤规则。此外,我们的分析适用于使用H \“较旧连续梯度的通用平滑目标,对于这两种方法,我们都为强烈凸出问题提供了扩展。最后,我们的结果暗示我们认为的第一种(加速)方法也具有最佳的迭代。在所有制度中,Oracle的复杂性,第二个机制在非平滑设置中都是最佳的。
translated by 谷歌翻译
联邦学习(FL)是一种越来越受欢迎的机器学习范式,其中多个节点在隐私,通信和多个异质性约束下尝试协同学习。联邦学习中的持续存在问题是,不清楚优化目标应该:监督学习的标准平均风险最小化在处理联合学习的几个主要限制方面是不充分的,例如沟通适应性和个性化控制。我们在联合学习的框架中识别几个关键的Desiderata,并介绍了一个新的框架,Flix,考虑到联合学习所带来的独特挑战。 Flix具有标准的有限和形式,使从业者能够利用分布式优化的现有(潜在非本地)方法的巨大财富。通过不需要任何通信的智能初始化,Flix不需要使用本地步骤,但仍然可以通过本地方法执行不一致的正则化。我们提供了几种用于在通信约束下有效解决FLIX制剂的算法。最后,我们通过广泛的实验证实了我们的理论结果。
translated by 谷歌翻译
标准梯度下降(GDA) - 型算法只能在非凸极小优化中找到固定点,这比局部minimax点比局部最佳。在这项工作中,我们开发了GDA型算法,这些算法在非convex-rong-concave minimax优化中全球收敛到局部minimax点。我们首先观察到局部最小点等效于某个包膜函数的二阶固定点。然后,受到经典立方正则化算法的启发,我们提出了Cubic-GDA(一种用于查找局部最小值点的立方体规范化的GDA算法),并通过利用其内在潜在功能来提供全面的收敛分析。具体而言,我们以sublinear收敛速率建立了立方GDA与局部最小点的全球收敛。我们进一步分析了在局部梯度显性型非凸几何形状的整个频谱中立方GDA的渐近收敛速率,比标准GDA更快地建立秩序的渐近收敛速率。此外,我们提出了用于大规模最小优化的立方GDA的随机变体,并在随机子采样下表征其样品复杂性。
translated by 谷歌翻译
最近,随机梯度下降(SGD)及其变体已成为机器学习(ML)问题大规模优化的主要方法。已经提出了各种策略来调整步骤尺寸,从自适应步骤大小到启发式方法,以更改每次迭代中的步骤大小。此外,动力已被广泛用于ML任务以加速训练过程。然而,我们对它们的理论理解存在差距。在这项工作中,我们开始通过为一些启发式优化方法提供正式保证并提出改进的算法来缩小这一差距。首先,我们分析了凸面和非凸口设置的Adagrad(延迟Adagrad)步骤大小的广义版本,这表明这些步骤尺寸允许算法自动适应随机梯度的噪声水平。我们首次显示延迟Adagrad的足够条件,以确保梯度几乎融合到零。此外,我们对延迟的Adagrad及其在非凸面设置中的动量变体进行了高概率分析。其次,我们用指数级和余弦的步骤分析了SGD,在经验上取得了成功,但缺乏理论支持。我们在平滑和非凸的设置中为它们提供了最初的收敛保证,有或没有polyak-{\ l} ojasiewicz(pl)条件。我们还显示了它们在PL条件下适应噪声的良好特性。第三,我们研究动量方法的最后迭代。我们证明了SGD的最后一个迭代的凸设置中的第一个下限,并以恒定的动量。此外,我们研究了一类跟随基于领先的领导者的动量算法,并随着动量和收缩的更新而增加。我们表明,他们的最后一个迭代具有最佳的收敛性,用于无约束的凸随机优化问题。
translated by 谷歌翻译
Bilevel优化是在机器学习的许多领域中最小化涉及另一个功能的价值函数的问题。在大规模的经验风险最小化设置中,样品数量很大,开发随机方法至关重要,而随机方法只能一次使用一些样品进行进展。但是,计算值函数的梯度涉及求解线性系统,这使得很难得出无偏的随机估计。为了克服这个问题,我们引入了一个新颖的框架,其中内部问题的解决方案,线性系统的解和主要变量同时发展。这些方向是作为总和写成的,使其直接得出无偏估计。我们方法的简单性使我们能够开发全球差异算法,其中所有变量的动力学都会降低差异。我们证明,萨巴(Saba)是我们框架中著名的传奇算法的改编,具有$ o(\ frac1t)$收敛速度,并且在polyak-lojasciewicz的假设下实现了线性收敛。这是验证这些属性之一的双光线优化的第一种随机算法。数值实验验证了我们方法的实用性。
translated by 谷歌翻译
与SGD相比,Adam等自适应梯度方法允许对现代深层网络(尤其是大型语言模型)进行强有力的培训。但是,适应性的使用不仅是为了额外的记忆,而且还提出了一个基本问题:SGD等非自适应方法可以享受类似的好处吗?在本文中,我们通过提议通过以下一般配方提议实现健壮和记忆效率的培训来为这个问题提供肯定的答案:(1)修改体系结构并使IT规模不变,即参数规模不影响。网络的输出,(2)使用SGD和重量衰减的训练,以及(3)剪辑全局梯度标准与重量标准成比例成正比,乘以$ \ sqrt {\ tfrac {\ tfrac {2 \ lambda} {\ eta}} {\ eta}}} $, $ \ eta $是学习率,而$ \ lambda $是权重腐烂。我们表明,这种一般方法是通过证明其收敛性仅取决于初始化和损失的规模来重新恢复参数和丢失的强大,而标准SGD甚至可能不会收敛许多初始化。在我们的食谱之后,我们设计了一个名为Sibert的Bert版本的比例不变版本,该版本仅由Vanilla SGD进行训练时,可以实现与Bert在下游任务中受过自适应方法训练的BERT相当的性能。
translated by 谷歌翻译
标准联合优化方法成功地适用于单层结构的随机问题。然而,许多当代的ML问题 - 包括对抗性鲁棒性,超参数调整和参与者 - 批判性 - 属于嵌套的双层编程,这些编程包含微型型和组成优化。在这项工作中,我们提出了\ fedblo:一种联合交替的随机梯度方法来解决一般的嵌套问题。我们在存在异质数据的情况下为\ fedblo建立了可证明的收敛速率,并引入了二聚体,最小值和组成优化的变化。\ fedblo引入了多种创新,包括联邦高级计算和降低方差,以解决内部级别的异质性。我们通过有关超参数\&超代理学习和最小值优化的实验来补充我们的理论,以证明我们方法在实践中的好处。代码可在https://github.com/ucr-optml/fednest上找到。
translated by 谷歌翻译