数学系

搜索

在

达可研讨会

×

模态的标题

模式内容

请订阅这如果你愿意，我们会通过电子邮件通知你。而且你可以订阅到iCal/ics日历。

2023年春季学期

日期/时间 演讲者 标题 位置
＊2023年1月27日
12:20-13:00		 Pranav Nuti
斯坦福大学，美国斯坦福
事件详细信息

达可研讨会

标题 在线选择问题以及拉姆齐定理如何解决纸牌游戏
演讲者,归属 Pranav Nuti，斯坦福大学，美国斯坦福
日期、时间 2023年1月27日，12:20-13:00
位置 HG19.2 G
摘要 在一个基本的在线选择问题中，我们一个接一个地观察一个数字序列，我们必须做出一个不可撤销的决定，从这些数字中选择一个。秘书问题和先知问题都属于这种类型，但它们在几个维度上有所不同:数字出现的顺序，在观察数字之前我们有多少关于数字的信息，以及我们希望最大化的目标。在这些维度上，几个介于秘书和先知问题之间的模型已经被研究过了。在这次演讲中，我将稍微介绍一下这些不同的模型，然后解释我们如何使用拉姆齐定理(用于超图)来获得这样一个模型的最优结果。这个模型可以解释为一个简单的纸牌游戏。
在线选择问题以及拉姆齐定理如何解决纸牌游戏read_more
HG19.2 G
2023年2月21日
14:15-16:00		 Martin Kassabov教授
美国康奈尔大学
事件详细信息

达可研讨会

标题 具有性质(T)和无限多交替群商的多项式环的驯服自同构群
演讲者,归属 Martin Kassabov教授，美国康奈尔大学
日期、时间 2023年2月21日14:15-16:00
位置 HG19.1 G
摘要 我们构造具有性质(T)和无限个交替群商的群的新族。其中一个由Aut(Fp[x1，…，xn])的子群组成，由一组合适的驯服自同构生成。有限商是利用Aut(F_p[x1，…，x_n])在F_p的有限扩展上的n维仿射空间上的自然作用构造的。因此，我们得到了具有性质(T)和无限多交替群商的Gromov双曲群的显式表示。我们的构造还对任意奇素数p的p^7−1次交替群给出了一个明确的4次展开式Cayley图族。
具有性质(T)和无限多交替群商的多项式环的驯服自同构群read_more
HG19.1 G
＊2023年2月24日
16:15-17:15		 Amir Ali Ahmadi教授
普林斯顿大学，美国普林斯顿
事件详细信息

达可研讨会

标题 多项式优化中求局部极小值的复杂性
演讲者,归属 Amir Ali Ahmadi教授，普林斯顿大学，美国普林斯顿
日期、时间 2023年2月24日16:15-17:15
位置 HG19.2 G
摘要 我们考虑多元多项式的(i)临界点，(ii)二阶点，(iii)局部极小值和(iv)严格局部极小值的概念。对于每一种类型的点，作为多项式次的函数，我们研究确定(1)给定点是否属于那种类型，以及(2)多项式是否具有那种类型的点的复杂性。我们的研究结果描述了这两个问题的复杂性，这些问题都是先前文献所遗留下来的。我们的主要贡献揭示了这些问题中的许多问题对于三次多项式是可以处理的。相比之下，我们表明，除非P=NP，否则不可能有多项式时间算法在欧几里得距离$c^n$(对于任何常数$c\geq 0$)内找到一个点的局部最小值的$n$二次多项式在多形体上。这个结果($c=0$)回答了Pardalos和Vavasis的一个问题，这个问题出现在1992年复杂性理论数值优化的七个开放问题的列表中。基于与Jeffrey Zhang (CMU)的共同工作。
多项式优化中求局部极小值的复杂性read_more
HG19.2 G
＊2023年3月9日
14:15-16:00		 Friedrich Eisenbrand教授
EPF洛桑
事件详细信息

达可研讨会

标题 从近似到精确整数规划
演讲者,归属 Friedrich Eisenbrand教授，EPF洛桑
日期、时间 2023年3月9日14:15-16:00
位置 HG19.2 G
摘要 在这次演讲中，我们将展示如何使用近似整数规划的oracle来精确地求解整数程序。该方法基于凸优化技术。它为一般整数规划提供了最广为人知的复杂度边界，并以相等形式为整数程序提供了新的复杂度结果，在这种形式中，域由维度上的多项式限定。与丹尼尔·达杜什和托马斯·罗斯沃斯合作
从近似到精确整数规划read_more
HG19.2 G
＊2023年3月14日
10:40-11:20		 Vasilis Livanov
伊利诺伊大学香槟分校，美国
事件详细信息

达可研讨会

标题 成本最小化的最优停车问题
演讲者,归属 Vasilis Livanov，伊利诺伊大学香槟分校，美国
日期、时间 2023年3月14日，10:40-11:20
位置 HGF 26.5
摘要 最优停止理论的一个经典结果是，如果一个人知道这些值来自于分布，并想要选择最大值，那么他应该在什么时候停止并从一个逐个呈现的观测值序列中接受一个值。问题是，如果一个值被拒绝，它就永远不能再次被选择。这种结合了在线决策和随机不确定性的设置被称为预言不等式。在过去的十年中，有两个非常令人兴奋的发现，将拍卖理论和在线组合优化与预言不等式类型问题联系起来。在这次演讲中，我们将介绍预言不等式和在线组合优化的一些标准思想和结果。然后，我们在一个新的方向上提出了第一个结果，即研究最小化的先知不等式，一个与最大化情况不同的设置，它产生丰富的和定性的不同结果。
成本最小化的最优停车问题read_more
HGF 26.5
2023年3月21日
14:15-15:05		 伊曼纽尔Pilliat
Université法国蒙彼利埃
事件详细信息

达可研讨会

标题 众包问题中的最优排列估计
演讲者,归属 伊曼纽尔Pilliat，Université法国蒙彼利埃
日期、时间 2023年3月21日14:15-15:05
位置 HG19.1 G
摘要 受众包应用程序的激励，我们考虑了一个模型，其中我们有来自二元等压nxd矩阵的部分观测，其行上有一个未知的排列\pi^*。针对置换\pi^*的恢复和未知矩阵的估计这两个孪生问题，我们介绍了一个多项式时间过程，对这两个问题实现了最小最大风险，这对于所有可能的n, d和所有采样工作。在此过程中，我们建立了在某些情况下，恢复排列\pi^*要比估计矩阵简单得多。
众包问题中的最优排列估计read_more
HG19.1 G
＊2023年3月28日
14:45-15:45		 塔蒂阿娜Brailovskaya
普林斯顿大学，美国普林斯顿
事件详细信息

达可研讨会

标题 普遍性和矩阵浓度不等式
演讲者,归属 塔蒂阿娜Brailovskaya，普林斯顿大学，美国普林斯顿
日期、时间 2023年3月28日14:45-15:45
位置 HG19.1 G
摘要 随机矩阵经常出现在许多不同的领域-物理，计算机科学，应用和纯数学。通常情况下，感兴趣的随机矩阵将具有非平凡的结构-相关的条目，具有潜在的不同的均值和方差(例如稀疏Wigner矩阵，对应于随机图的邻接矩阵，样本协方差矩阵)。然而，目前对这种复杂随机矩阵的理解仍然缺乏。在这次演讲中，我将讨论关于具有a.s.有界算子范数的独立随机矩阵和谱的最新结果。特别地，我将证明在一些相当普遍的条件下，这样的和将表现出以下的普遍性现象-它们的频谱将接近具有相同均值和协方差的高斯随机矩阵。不需要事先有随机矩阵理论的背景-基本的概率论和线性代数知识就足够了。(与拉蒙·范亨德尔合作)预印链接:https://web.math.princeton.edu/~rvan/tuniv220113.pdf
普遍性和矩阵浓度不等式read_more
HG19.1 G
2023年4月18日
14:15-15:05		 Courtney Paquette教授
加拿大麦吉尔
事件详细信息

达可研讨会

标题 DACO-FDS:大型随机算法:批量饱和，步长临界，泛化性能和精确动力学(第一部分)
演讲者,归属 Courtney Paquette教授，加拿大麦吉尔
日期、时间 2023年4月18日14:15-15:05
位置 HG19.1 G
摘要 在这次演讲中，我们将提出一个框架，用于分析随机优化算法的动态(例如，随机梯度下降(SGD)和动量(SGD+M))，当样本数量和维度都很大时。为了分析，我们将引入一个随机微分方程，称为齐次SGD。我们证明了均匀化SGD是SGD的高维等价物——对于任何二次统计量(例如，具有二次损失的总体风险)，当样本数量n和特征数量d多项式相关时，SGD迭代下的统计量收敛到均匀化SGD下的统计量。通过分析齐次化SGD，给出了SGD训练动态和泛化性能的精确非渐近高维表达式，并给出了Volterra积分方程的解。该分析是针对满足一组可解析条件的数据矩阵和目标向量制定的，这些条件可以大致看作是数据的样本侧奇异向量的弱离域形式。通过分析这些限制动态，我们可以深入了解学习率、动量参数和批量大小选择。例如，我们确定了一个稳定性测量，隐式条件调节比(ICR)，它调节SGD+M加速算法的能力。当批大小超过该ICR时，SGD+M以$O(1/ \kappa)$的速率线性收敛，匹配最优的全批动量(特别是表现与全批一样好，但大小的一小部分)。相比之下，对于小于ICR的批处理大小，SGD+M的速率就像单批SGD速率的倍数。我们给出了明确的学习率和动量参数的选择，以实现这种性能的黑森谱。 Finally we show this model matches performances on real data sets.
DACO-FDS:大型随机算法:批量饱和，步长临界，泛化性能和精确动力学(第一部分)read_more
HG19.1 G
2023年4月18日
15:10-16:00		 Elliot Paquette教授
加拿大麦吉尔
事件详细信息

达可研讨会

标题 DACO-FDS:大型随机算法:批量饱和，步长临界，泛化性能和精确动力学(第二部分)
演讲者,归属 Elliot Paquette教授，加拿大麦吉尔
日期、时间 2023年4月18日15:10-16:00
位置 HG19.1 G
摘要 在这次演讲中，我们将提出一个框架，用于分析随机优化算法的动态(例如，随机梯度下降(SGD)和动量(SGD+M))，当样本数量和维度都很大时。为了分析，我们将引入一个随机微分方程，称为齐次SGD。我们证明了均匀化SGD是SGD的高维等价物——对于任何二次统计量(例如，具有二次损失的总体风险)，当样本数量n和特征数量d多项式相关时，SGD迭代下的统计量收敛到均匀化SGD下的统计量。通过分析齐次化SGD，给出了SGD训练动态和泛化性能的精确非渐近高维表达式，并给出了Volterra积分方程的解。该分析是针对满足一组可解析条件的数据矩阵和目标向量制定的，这些条件可以大致看作是数据的样本侧奇异向量的弱离域形式。通过分析这些限制动态，我们可以深入了解学习率、动量参数和批量大小选择。例如，我们确定了一个稳定性测量，隐式条件调节比(ICR)，它调节SGD+M加速算法的能力。当批大小超过该ICR时，SGD+M以$O(1/ \kappa)$的速率线性收敛，匹配最优的全批动量(特别是表现与全批一样好，但大小的一小部分)。相比之下，对于小于ICR的批处理大小，SGD+M的速率就像单批SGD速率的倍数。我们给出了明确的学习率和动量参数的选择，以实现这种性能的黑森谱。 Finally we show this model matches performances on real data sets.
DACO-FDS:大型随机算法:批量饱和，步长临界，泛化性能和精确动力学(第二部分)read_more
HG19.1 G

笔记:强调事件标记下一个发生的事件和标有星号(＊)表示时间及/或地点与通常的时间及/或地点不同。

存档:FS 23HS 22FS 22HS 21FS 21HS 20FS 20

您的浏览器中已禁用JavaScript