📐 优化/理论¶

🧪 ICML2025 · 55 篇论文解读

A Generalization Result for Convergence in Learning-to-Optimize: 提出一个概率框架，将 PAC-Bayesian 泛化理论与变分分析中的 Kurdyka-Łojasiewicz (KL) 收敛定理相结合，首次在不限制学习算法设计的前提下，以高概率证明了学习型优化算法收敛到临界点。
A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization: 本文提出 ALEXR 算法——一种高效的单循环原始-对偶块坐标随机算法，用于求解凸有限和耦合复合优化（cFCCO）问题，在光滑和非光滑条件下均达到近最优收敛速率，并通过推导下界证明了算法的最优性。
A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation: 以f-NCE为基础提出alpha-CentNCE和f-CondNCE两个估计器家族，统一了MLE、MC-MLE、GlobalGISO、pseudo-likelihood、ISO等学习非归一化分布的方法，纠正了CondNCE与score matching的误导性联系，并为有界指数族首次建立有限样本收敛保证。
Adjustment for Confounding using Pre-Trained Representations: 本文研究如何利用预训练神经网络的隐表示来调整非表格数据（如图像、文本）中的混杂因素，形式化了表示充分性条件，证明了稀疏性/可加性假设在可逆线性变换（ILT）下不成立，并基于低内在维度和层次组合模型建立了深度网络的收敛速率理论，从而保证 DML 框架下 ATE 估计的有效推断。
AdvPrompter: Fast Adaptive Adversarial Prompting for LLMs: 提出 AdvPrompter——用一个 LLM（AdvPrompter）在秒级速度内为目标 LLM 生成人类可读的对抗提示后缀，通过交替优化算法训练，在 AdvBench 和 HarmBench 上实现高攻击成功率，且可迁移到闭源黑盒 LLM，同时展示了用生成的对抗后缀进行对抗训练以增强目标 LLM 鲁棒性的策略。
Autoformulation of Mathematical Optimization Models Using LLMs: 本文提出一种利用大语言模型结合蒙特卡洛树搜索（MCTS）自动将自然语言描述的优化问题转化为可求解器求解的数学规划模型的方法，通过符号剪枝和 LLM 价值评估显著提升了搜索效率。
Benefits of Early Stopping in Gradient Descent for Overparameterized Logistic Regression: 在过参数化逻辑回归中，理论证明了早停梯度下降（early-stopped GD）相比渐近 GD 具有统计优势：早停 GD 是校准且一致的，而渐近 GD 的 logistic risk 趋于无穷且校准误差不消失；同时建立了早停与 \(\ell_2\) 正则化之间的定量联系。
Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs: 提出 History-Driven Target (HDT) 框架，通过修改目标分布（而非转移核）将自排斥机制嵌入任意 MCMC 采样器，在保持 O(1/α) 方差缩减的同时解决了 SRRW 的计算开销大、仅限可逆链、内存占用高三大问题。
Can Transformers Learn Full Bayesian Inference In Context?: 证明 Transformer 可以在上下文中执行完整的贝叶斯推断——通过在合成数据上预训练一个编码器-解码器架构（TabPFN 编码器 + 扩散 Transformer 解码器），模型在部署时无需参数更新即可为 GLM、混合高斯模型等统计模型生成与 HMC 质量媲美的后验样本。
Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed: 证明了 AdaGrad/Adam 在重尾噪声下的高概率收敛可能很差（依赖置信水平的多项式），并证明梯度裁剪可以修复这个问题——Clip-AdaGrad-Norm 和 Clip-Adam-Norm 在重尾噪声下实现了对置信水平的对数多项式依赖的高概率收敛界，扩展到延迟步长版本。
Compelling ReLU Networks to Exhibit Exponentially Many Linear Regions at Initialization and During Training: 提出一种基于非对称三角波的 ReLU 网络重参数化方法，使深度为 \(d\) 的 4 神经元宽网络在初始化时即产生 \(2^d\) 个线性区域，并在预训练中保持该指数级表达能力，在一维函数逼近任务上将误差降低了 3 个数量级。
Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability: 证明了 Local GD 在分布式逻辑回归问题上可以使用任意正步长 \(\eta > 0\) 收敛，且通过允许初始不稳定阶段的非单调目标下降，可实现比现有凸优化最坏情况下界更快的 \(\widetilde{\mathcal{O}}(M/(\gamma^5 R^2))\) 收敛速率。
Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization: 提出 NBO 框架，利用双层优化中超梯度的内在结构（下层问题求解与 Hessian 逆向量积共享同一 Hessian），通过非精确 Newton 方法高效融合曲率信息来逼近超梯度，在确定性场景下将梯度计算复杂度相比 SOTA 改善了 \(\kappa \log \kappa\) 倍。
Emergence in Non-Neural Models: Grokking Modular Arithmetic via Average Gradient Outer Product: 本文证明 grokking（延迟泛化）现象并非神经网络或梯度下降特有，而是源于任务相关特征的逐步学习——利用非神经网络的 Recursive Feature Machines (RFM) 在核机器上复现了模算术的 grokking，揭示分块循环（block-circulant）特征矩阵是泛化的核心。
FedSWA: Improving Generalization in Federated Learning with Highly Heterogeneous Data via Momentum-Based Stochastic Controlled Weight Averaging: 针对高数据异质性下 FedSAM 泛化失败的问题，提出 FedSWA（周期学习率 + EMA 聚合）和 FedMoSWA（动量方差缩减控制变量），在理论和实验上均证明优于 FedSAM 及其变体，在 CIFAR-100 Dirichlet-0.1 上比 FedSAM 高出 21.8% 准确率。
Flexible Tails for Normalizing Flows: 提出 Tail Transform Flow (TTF)，在 normalizing flow 的最后一层添加基于互补误差函数的非 Lipschitz 变换，将高斯尾部转换为可调权重的重尾分布，避免了使用重尾基分布导致的神经网络优化困难问题。
FSL-SAGE: Accelerating Federated Split Learning via Smashed Activation Gradient Estimation: 本文提出 FSL-SAGE，一种联邦分裂学习算法，通过辅助模型估计服务端梯度反馈，在保持与 FedAvg 相当的 \(O(1/\sqrt{T})\) 收敛速率的同时，大幅降低通信开销和客户端内存需求。
GCAL: Adapting Graph Models to Evolving Domain Shifts: 提出 Graph Continual Adaptive Learning (GCAL)，通过"适应+生成记忆"双层优化策略，在图模型面对持续演变的 OOD 图序列时，利用信息最大化进行无监督域适应，同时基于信息瓶颈理论设计变分记忆图生成模块来压缩历史图知识，有效缓解灾难性遗忘。
Generalization and Robustness of the Tilted Empirical Risk: 本文为负倾斜参数(γ<0)下的 Tilted Empirical Risk (TER) 提供了系统性的泛化误差上下界和鲁棒性保证，在损失函数无界但具有有界 (1+ε) 阶矩条件下，通过均匀方法和信息论方法建立了 \(O(n^{-\epsilon/(1+\epsilon)})\) 的收敛速率，并给出了数据驱动的倾斜参数选择方案。
Global Convergence and Rich Feature Learning in \(L\)-Layer Infinite-Width Neural Networks under \(\mu\)P Parametrization: 证明了在 \(\mu\)P (Maximal Update Parametrization) 下，\(L\) 层无限宽 MLP 用 SGD 训练时，各层特征在整个训练过程中保持线性独立且发生实质性演化，从而保证训练收敛点必为全局最小值——首次同时解决"丰富特征学习"和"全局收敛"两个理论目标。
Grokking at the Edge of Linear Separability: 在最简单的逻辑回归二分类任务中揭示了 grokking（延迟泛化）的根本原因：当数据维度与样本数之比 \(\lambda = d/N\) 接近临界点 \(\lambda_c = 1/2\) 时，训练动力学会在过拟合解附近停留任意长时间后才收敛到泛化解，类似于物理学中的"临界减速"现象。
How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias: 从理论上刻画了一层 Transformer 学习 "even pairs" 和 "parity check" 两类正则语言识别任务时的两阶段训练动力学，证明了线性层在梯度下降下隐式收敛到最大间隔超平面，并揭示了 CoT 在解决 parity 问题中的关键作用。
Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization: 首次证明 Random Reshuffle（RR）和 Single Shuffle（SS）在非光滑（强）凸有限和优化中的 last-iterate 收敛率严格优于 Proximal GD，RR 达到 \(\tilde{O}(GD_\star / (n^{1/4}\sqrt{K}))\)，近似匹配下界 \(\Omega(1/(n^{1/4}\sqrt{K}))\)。
Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization: 在差分隐私约束下研究非光滑非凸（NSNC）随机优化，通过改进梯度估计器的有效灵敏度，将已知最优样本复杂度降低了 \(\Omega(\sqrt{d})\) 倍，并首次证明 Goldstein 稳定性可从经验损失泛化到总体损失。
In-Context Linear Regression Demystified: Training Dynamics and Mechanistic Interpretability of Multi-Head Softmax Attention: 本文通过理论分析和大量实验揭示了多头 softmax attention 在线性回归 ICL 任务上训练后涌现出优雅的注意力模式（KQ 对角均匀、OV 仅关注最后一项且零和），进而证明这些结构使模型近似实现了去偏梯度下降预测器，接近贝叶斯最优。
Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems: 系统研究了增量梯度下降（IGD）在小 epoch 体制（\(K \lesssim \kappa\)）下的收敛行为，证明 IGD 在此体制下比有放回 SGD 慢至少 \(n\) 倍，且当分量函数非凸时收敛速度急剧恶化至指数级慢。
Integer Programming for Generalized Causal Bootstrap Designs: 提出基于整数规划（IP）数值求解最不利 copula 的方法，将因果 bootstrap 的设计不确定性量化从"完全随机化 + 均值差估计量"推广到任意已知概率分配与线性/二次处理估计量，并证明渐近有效性。
Interior-Point Vanishing Problem in Semidefinite Relaxations for Neural Network Verification: 本文首次识别了SDP松弛用于深度神经网络验证时的"内点消失"(interior-point vanishing)问题——随着网络深度增加，SDP问题丧失严格可行性导致数值不稳定和求解失败——并提出五种缓解方法，其中B-Remove（移除层边界约束）最有效，解决了88%原本无法求解的问题。
Layer-wise Quantization for Quantized Optimistic Dual Averaging: 通过层级量化（为不同层分配不同量化方案）和乐观对偶平均算法(QODA)，在单调变分不等式上达到竞争性收敛率，在WGAN分布式训练中实现150%端到端加速。
Learning Mixtures of Experts with EM: A Mirror Descent Perspective: 本文从镜像下降的视角严格分析了 EM 算法训练混合专家（MoE）模型的收敛性，证明 EM 等价于以 KL 散度为正则项的投影镜像下降，并给出了局部线性收敛的条件，在合成数据和真实数据上验证 EM 优于梯度下降。
Learning to Plan & Reason for Evaluation with Thinking-LLM-as-a-Judge: 提出 EvalPlanner，通过将 LLM-as-a-Judge 的推理过程解耦为"评估计划生成"和"计划执行"两个阶段，并在自训练循环中用 DPO 迭代优化计划与执行的偏好对，在 RewardBench 上以仅 22K 合成偏好对达到 93.9 的生成式奖励模型新 SOTA。
MetaAgent: Automatically Constructing Multi-Agent Systems Based on Finite State Machines: 提出 MetaAgent，一个基于有限状态机（FSM）的框架，给定任务描述即可自动设计多智能体系统，无需外部训练数据，支持工具调用和状态回溯，在文本任务、ML 任务和软件开发任务上超越现有自动设计方法并逼近人工设计系统性能。
Nearly Optimal Sample Complexity for Learning with Label Proportions: 本文研究从标签比例学习（LLP）的样本复杂度，在平方损失下给出了近最优的样本复杂度上下界，并设计了基于 ERM 和 SGD 的算法，在关于 bag size 的依赖关系上显著改进了现有结果。
Nonparametric Teaching for Graph Property Learners: 提出 GraNT 范式，将非参数教学理论拓展到图属性学习场景，通过贪心选择"预测偏差最大"的图样本子集来加速 GCN 训练，在保持泛化性能的同时将训练时间缩减 30%–47%。
On Understanding Attention-Based In-Context Learning for Categorical Data: 将 Transformer 的 in-context learning (ICL) 从实值输出推广到分类数据（categorical outcomes），证明一种交替使用 self-attention 和 cross-attention 的架构可以精确实现多步函数梯度下降（functional GD），并在理论上证明该 GD 参数构型是注意力模型损失函数的驻点。
Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees: 针对带有额外支撑保持约束的稀疏优化问题，提出两步投影IHT算法（先硬阈值再投影凸集），在RSC/RSS条件下给出全局目标值保证（无系统误差），揭示稀疏度松弛与次优性间的新trade-off。
POPri: Private Federated Learning using Preference-Optimized Synthetic Data: 将差分隐私联邦学习中的合成数据生成问题重新建模为 LLM 策略优化（DPO）问题，利用客户端 DP 反馈构建偏好对来微调 LLM，比传统 Private Evolution 提升更大——在 ε=1 下将隐私-性能差距缩小 58%。
Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent: 本文首次理论证明了在正定二次函数的坐标下降中，随机排列坐标下降（RPCD）的收缩率严格优于均匀随机坐标下降（RCD），从而解决了一个长期悬而未决的理论问题。
Provable In-Context Vector Arithmetic via Retrieving Task Concepts: 本文从优化理论角度证明：带残差连接和层归一化的非线性 Transformer 经梯度下降在 QA 数据上训练后，能通过向量加法（task vector + query）完成事实召回型 ICL 任务，且在 ICL 数据上训练反而会导致低层特征的有害记忆。
Quantum Optimization via Gradient-Based Hamiltonian Descent: 将梯度信息融入量子哈密顿下降 (QHD) 框架，提出 gradient-based QHD，在凸和非凸优化中均实现了比原始 QHD 及经典方法（NAG、SGDM）快至少一个数量级的收敛速度和更高的全局最优命中概率。
Random Feature Representation Boosting: 提出 RFRBoost，利用梯度表示提升（gradient representation boosting）理论构建深层残差随机特征神经网络，在 MSE 损失下获得封闭解，在一般损失下化归为二次约束最小二乘问题，在表格数据上显著超越单层 RFNN 与端到端训练的 MLP ResNet。
Revisiting Unbiased Implicit Variational Inference: 重新审视被认为"不实用"的无偏隐式变分推断（UIVI），用重要性采样替代其内部 MCMC 循环，并通过最小化期望前向 KL 散度无偏地学习最优提议分布，在标准 SIVI 基准上达到或超越 SOTA。
SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming: 提出 SDP-CROWN，将半定规划（SDP）松弛的紧致性融入线性界传播框架，每层仅增加一个参数 λ，便可在 ℓ₂ 扰动下将验证松弛度最多收紧 √n 倍，同时保持与 α-CROWN 同级的可扩展性。
Sparse Causal Discovery with Generative Intervention for Unsupervised Graph Domain Adaptation: 提出 SLOGAN 框架，通过稀疏因果图构建与信息瓶颈解耦因果/虚假特征，结合跨域虚假特征交换的生成式干预机制和类别自适应伪标签动态校准，实现无监督图域自适应中稳定的因果特征迁移。
Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances: 本文为 Kernel Max-Sliced (KMS) Wasserstein 距离提供了尖锐的有限样本统计保证（无维度依赖、收敛速率 \(n^{-1/(2p)}\)）和计算保证（证明精确计算是 NP-hard 后提出高效的半定松弛 SDR 及一阶算法），并在高维两样本检验、人体活动检测和生成建模上验证了优越性能。
Subspace Optimization for Large Language Models with Convergence Guarantees: 本文揭示了 GaLore（子空间优化算法）在随机设定下不总是收敛，并提出了 GoLore（梯度随机低秩投影）——一种可证明收敛的变体，即使在标准 batch 大小下也能保证收敛。
Synonymous Variational Inference for Perceptual Image Compression: 基于语义信息论中的同义性视角，提出同义变分推断 (SVI) 方法，从理论上证明感知图像压缩的优化方向是率-失真-感知三元权衡，并设计渐进式同义图像压缩 (SIC) 编解码器，单模型即可覆盖多码率多感知质量级别。
The Butterfly Effect: Neural Network Training Trajectories Are Highly Sensitive to Initial Conditions: 通过"产卵-扰动"实验范式，系统研究神经网络训练轨迹对初始条件的敏感性，发现训练初期极微小的扰动（甚至单个权重）就能导致完全不同的收敛结果——即"蝴蝶效应"，且这种不稳定性与训练噪声无关，随训练进展迅速消减。
The Panaceas for Improving Low-Rank Decomposition in Communication-Efficient Federated Learning: 针对联邦学习中低秩分解的三个核心问题（分解什么、怎么分解、怎么聚合），分别提出 MUD（模型更新分解）、BKD（分块 Kronecker 分解）和 AAD（聚合感知分解）三种互补技术，在保持低通信开销的同时实现更快收敛和更高精度。
Tilted Sharpness-Aware Minimization: 提出 Tilted SAM (TSAM)，利用指数倾斜 (exponential tilting) 将 SAM 的 min-max 目标平滑化为对邻域内多个局部解按损失值加权的软优化，理论上更平滑、更偏好平坦极小值，实验在图像和文本任务上一致优于 SAM 及其变体。
Training Dynamics of In-Context Learning in Linear Attention: 本文完整刻画了多头线性注意力在梯度流训练中获取 ICL 能力的动态过程：merged KQ 参数化呈现单次突变式 loss 下降，而 separate KQ 参数化则展现 saddle-to-saddle 逐步学习主成分回归的阶梯式训练动态。
Transformative or Conservative? Conservation Laws for ResNets and Transformers: 系统推导并证明了卷积 ResNet 和 Transformer 等现代架构在梯度流训练动态下的守恒律，揭示残差连接不改变守恒律、块级守恒律等价于孤立块的守恒律，并证明离散 SGD 下守恒误差为 \(O(\text{step-size}^2)\)。
Understanding Sharpness Dynamics in NN Training with a Minimalist Example: The Effects of Dataset Difficulty, Depth, Stochasticity, and More: 提出用"每层单神经元的深度线性网络"作为极简模型，系统性地研究 progressive sharpening 和 edge of stability 现象，引入 dataset difficulty \(Q\) 概念并推导了 sharpness 在全局最优处的上下界，理论分析了数据规模、网络深度、batch size 和学习率对 sharpness 动态的影响机制。
Understanding the Statistical Accuracy-Communication Trade-off in Personalized Federated Learning with Minimax Guarantees: 本文首次定量刻画了个性化联邦学习中个性化程度 \(\lambda\) 如何同时影响统计精度和通信效率，建立了 minimax 最优统计速率，并提出 FedCLUP 算法实现了统计-通信的最优权衡。
Widening the Network Mitigates the Impact of Data Heterogeneity on FedAvg: 从 NTK 理论出发，证明 FedAvg 中数据异质性导致的模型发散上界为 \(\mathcal{O}(n^{-1/2})\)（\(n\) 为网络宽度），在无穷宽极限下全局和局部模型均线性化，FedAvg 在相同迭代次数下等价于集中式梯度下降，泛化性能一致。