📐 优化/理论¶

🧠 NeurIPS2025 · 共 54 篇

A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization: 针对下层问题带耦合线性约束的双层优化问题，提出单循环一阶算法 SFLCB，通过罚函数 + 增广拉格朗日重构消除 Hessian 依赖，将迭代复杂度从 \(O(\epsilon^{-3}\log(\epsilon^{-1}))\) 改进至 \(O(\epsilon^{-3})\)。
A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning: 提出首个针对基于采样的测试时缩放方法的理论框架，将推理误差分解为估计误差和模型误差，揭示了Self-Consistency收敛慢、Perplexity模型误差大的局限，并提出RPC方法融合两者优势，在7个基准上以50%的采样成本达到同等推理性能。
A Unified Approach to Submodular Maximization Under Noise: 本文提出一个统一的元算法框架，可以将任何满足"鲁棒性"条件的精确子模最大化算法作为黑盒，自动转换为在持久噪声值预言机下保持近似比的算法，首次覆盖了非单调子模函数的拟阵约束和无约束情形。
A Unified Stability Analysis of SAM vs SGD: Role of Data Coherence and Emergence of Simplicity Bias: 通过线性稳定性分析框架，证明了"平坦极小值⇒好泛化"和"SGD偏好简单函数"是同一枚硬币的两面——数据一致性(coherence)同时控制着两者，且SAM通过更严格的稳定性条件进一步放大了简单性偏好。
Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimization: 首次为随机层次化优化（极小极大和双层优化）提供自适应且sharp的收敛保证，通过动量归一化技术和新型自适应参数选择，在无需事先知道噪声大小的情况下实现最优收敛率Õ(1/√T + √σ̄/T^{1/4})。
An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds: AdaRHD 是首个无需预知问题参数（强凸常数、Lipschitz 界、流形曲率）的黎曼双层优化自适应算法——通过逆累计梯度范数策略自适应选择步长，在三阶段框架中逐步求解下层问题/线性系统/上层更新，收敛速率 \(O(1/\epsilon)\) 匹配非自适应方法，对初始步长选择鲁棒性远超 RHGD。
Asymptotically Stable Quaternionic Hopfield Structured Neural Network with Supervised Projection-based Manifold Learning: 提出四元数值监督学习 Hopfield 结构神经网络 (QSHNN)，通过周期性投影策略保持权重矩阵的四元数结构一致性，并基于 Lyapunov 理论证明了不动点的存在唯一性和渐近稳定性，轨迹曲率有界保证机器人路径规划的平滑性。
Auto-Compressing Networks: Auto-Compressing Networks（ACN）用长程前向连接（所有层输出直接汇聚到最终输出）替代短残差连接，使得梯度的 Direct Gradient 成分远强于 Forward Gradient，隐式地将信息压缩到早期层——ViT 仅需 6 层达到标准 12 层性能，BERT 节省 75% 层数，还额外获得噪声鲁棒性（+6.4%）和持续学习抗遗忘（-18%）。
AutoOpt: A Dataset and a Unified Framework for Automating Optimization Problem Solving: AutoOpt 构建了首个优化问题图像到代码的端到端框架——11554 张优化公式图像（手写+印刷）的 AutoOpt-11k 数据集 + M1 混合编码器（ResNet+Swin→mBART）图像转 LaTeX（BLEU 96.70）+ M2 DeepSeek-Coder LaTeX 转 PYOMO + M3 双层分解求解器，框架级成功率 94.20%。
Better NTK Conditioning: A Free Lunch from ReLU Nonlinear Activation in Wide Neural Networks: 证明 ReLU 激活函数对宽神经网络有一个此前未被注意的"免费"益处：(a) 在模型梯度特征空间中产生更好的数据分离（相似输入的角度在梯度空间中被放大），(b) 由此导致 NTK 矩阵条件数严格减小（相比线性网络）。深度进一步放大此效应——在无限宽然后无限深的极限下，所有数据对在梯度空间中等角分离（~75.5°），NTK 条件数收敛到仅依赖数据量 \(n\) 的固定值 \((n+4)/3\)。
Brain-like Variational Inference: 提出 FOND 框架（Free energy Online Natural-gradient Dynamics），从自由能最小化的第一原理推导出脉冲神经网络推断动力学，并实现 iPVAE（迭代泊松 VAE），在重建-稀疏性权衡、生物合理性和 OOD 泛化上优于标准 VAE 和预测编码模型。
Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets: 提出 CoGS 框架，证明二层二次激活网络在 Abelian 群乘法推理任务上的权重空间具有半环代数结构，损失函数中的 Sum Potential 是环同态映射，由此可从仅满足部分损失的局部解通过环加法和环乘法代数地组合出全局最优解，约 95% 的梯度下降解与理论构造精确匹配。
Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets: 揭示两层二次激活网络在 Abelian 群推理任务上训练时权重空间具有半环代数结构，提出 CoGS 框架通过环运算将部分解组合为全局最优解，约 95% 梯度下降解与理论构造精确匹配。
Contribution of Task-Irrelevant Stimuli to Drift of Neural Representations: 理论证明在线学习中任务无关刺激的统计特性（方差和维度）是表示漂移的重要驱动因素，在 Oja 规则、Similarity Matching、自编码器和监督两层网络中均观察到漂移率 \(D \propto \lambda_\perp^2 (n-m)\)，且学习噪声诱导的漂移具有各向异性几何特征，与高斯突触噪声的各向同性漂移定性不同。
Covariances for Free: Exploiting Mean Distributions for Training-free Federated Learning: 提出 FedCOF，仅利用客户端上传的类均值（class means）即可在服务器端无偏估计类协方差矩阵，从而在零训练、极低通信开销的条件下初始化全局分类器，性能媲美甚至超越需要传输二阶统计量的 Fed3R。
DartQuant: Efficient Rotational Distribution Calibration for LLM Quantization: DartQuant 提出基于分布校准的旋转矩阵优化方法，通过 Whip 损失将激活值分布推向均匀分布以减少量化误差，并用 QR-Orth 替代昂贵的流形优化器，在 70B 模型上实现 47× 加速和 10× 内存节省，首次在单张 3090 GPU 上完成大模型旋转校准。
Deep Taxonomic Networks for Unsupervised Hierarchical Prototype Discovery: Deep Taxonomic Networks 提出一种基于完全二叉树混合高斯先验的深度潜变量模型，通过变分推断自动从无标签数据中发现层次化分类体系和各级原型聚类，无需预设类别数量，并在多个数据集上大幅超越 TreeVAE 等基线。
Do Neural Networks Need Gradient Descent to Generalize? A Theoretical Study: 本文在矩阵分解（神经网络理论的经典测试平台）上证明了 Guess & Check（随机抽参数直到拟合训练集）的泛化能力随宽度增加而退化（首次证明存在 G&C 可证明劣于梯度下降的典范情况），但随深度增加而改善，揭示了宽度和深度对泛化的截然不同作用。
Doubly Robust Alignment for Large Language Models: DRPO 借鉴因果推断中的双重稳健估计方法，提出一种偏好优化算法，当偏好模型或参考策略任一正确指定时即可保持一致性，在理论和实验上均优于 PPO/DPO 及其变体。
DynaAct: Large Language Model Reasoning with Dynamic Action Spaces: DynaAct 将 LLM 推理中的动作空间构建建模为子集选择问题，通过兼顾效用和多样性的子模函数在每步动态构建紧凑动作空间，在 6 个基准上显著优于 rStar、RAP 等方法，MATH-500 上比 rStar 高 6.8%。
Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives: 提出 MA-SPL 和 MA-MPL 两个多智能体在线协调算法，通过"基于策略的连续扩展"技术突破次模性限制，首次在次模和弱次模目标函数上均实现最优 \((1 - c/e)\) 近似比，支持时变目标和仅局部反馈的实际约束。
Efficient Adaptive Federated Optimization: FedAda2/FedAda2++ 提出在联邦学习中实现高效的服务器-客户端联合自适应优化：客户端本地预条件器从零初始化（无需服务器传输），并可选地用 SM3 等内存高效优化器压缩本地统计量，在理论上保持与完整联合自适应相同的 \(O(T^{-1/2})\) 收敛率，实测通信成本与 FedAvg 一致。
Efficient Federated Learning against Byzantine Attacks and Data Heterogeneity via Aggregating Normalized Gradients: 提出 Fed-NGA 算法，通过对客户端上传的梯度做归一化后加权平均来实现聚合，以 \(\mathcal{O}(pM)\) 的极低时间复杂度同时抵御 Byzantine 攻击与数据异质性，并在非凸损失函数下首次证明了特定温和条件下的零最优性间隙收敛。
Emergence and Scaling Laws in SGD Learning of Shallow Neural Networks: 本文对浅层神经网络在线 SGD 学习加法模型（多个单指标函数叠加）的过程进行了精确分析，证明了每个教师神经元的学习呈现尖锐相变（emergence），而大量相变曲线的叠加自然产生平滑的幂律 scaling law。
Escaping Saddle Points without Lipschitz Smoothness: The Power of Nonlinear Preconditioning: 本文提出统一的充分条件连接 \((L_0,L_1)\)-光滑性与各向异性光滑性两种广义光滑框架，证明非线性预条件梯度法（含梯度裁剪）在此放松条件下保持鞍点规避性质，并给出扰动变体以多项对数维数依赖达到二阶稳定点。
Evaluating LLMs for Combinatorial Optimization: One-Phase and Two-Phase Heuristics for 2D Bin-Packing: 本文提出一个结合 LLM 与进化算法的系统性评估框架，用于评估 LLM 在 2D 装箱问题上生成和优化启发式算法的能力，GPT-4o 在 2 轮迭代内即达到最优解，将平均箱数从 16 降至 15，空间利用率从 0.76-0.78 提升至 0.83。
Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable: 本文引入随机矩阵和时变图作为建模工具，将联邦学习的客户端参与和本地更新过程统一为矩阵乘法形式，并提出 FOCUS 算法（基于 push-pull 策略），在任意客户端参与和数据异构下首次实现精确收敛与线性收敛速率。
Exploring Landscapes for Better Minima along Valleys: 本文提出优化器适配器"E"，通过在梯度更新中加入梯度差分的指数移动平均 \(\mathbf{a}_k = \text{EMA}(\mathbf{g}_k - \mathbf{g}_{k-1})\) 使优化器能在到达局部极小值后继续沿损失景观的"山谷"探索更低更平坦的极小值，适配后的 ALTO 在大批量训练中平均提升 2.5% 测试准确率。
Extragradient Method for \((L_0, L_1)\)-Lipschitz Root-finding Problems: 本文在 \(\alpha\)-对称 \((L_0,L_1)\)-Lipschitz 条件下（放松经典 \(L\)-Lipschitz 假设）为 extragradient (EG) 方法提出自适应步长策略 \(\gamma_k = 1/(c_0 + c_1\|F(x_k)\|^\alpha)\)，建立了强单调（线性收敛）、单调（次线性收敛）和 weak Minty（局部收敛）三类根问题的首个完整收敛保证。
FedRTS: Federated Robust Pruning via Combinatorial Thompson Sampling: 将联邦动态剪枝重新建模为组合多臂赌博机(CMAB)问题，提出基于 Thompson Sampling 的拓扑调整机制 TSAdj，通过概率性决策替代确定性决策来获得更鲁棒的稀疏模型拓扑，同时显著降低通信开销。
Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds: 提出 Riemannian Online to NonConvex (RO2NC) 算法及其零阶版本 ZO-RO2NC，首次为黎曼流形上完全非光滑非凸随机优化建立了 \(O(\delta^{-1}\epsilon^{-3})\) 的有限时间样本复杂度保证，匹配欧几里德最优结果。
From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications: 提出 A2L (Average to Last-iterate) 黑箱规约，对效用函数关于自身策略和对手联合策略均线性的博弈，能将任意非耦合学习动力学的平均迭代转换为新动力学的末迭代，由此在多人零和多矩阵博弈中取得 \(O(\log d / T)\) 梯度反馈和 \(\tilde{O}(d^{1/5}T^{-1/5})\) bandit 反馈的 SOTA last-iterate 收敛率。
From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD: 系统刻画了在学习高斯单指标模型时，学习率如何在"information exponent 主导"和"generative exponent 主导"两个样本复杂度体制之间引发相变，并提出了一种新的逐层交替 SGD 算法，无需复用样本即可突破 CSQ 下界。
From Linear to Nonlinear: Provable Weak-to-Strong Generalization through Feature Learning: 本文首次在非线性特征学习设定（线性 CNN → 两层 ReLU CNN）下严格分析了 weak-to-strong 泛化现象，揭示了数据匮乏和数据丰富两种机制下的不同行为：前者通过良性过拟合实现泛化（或因有害过拟合失败），后者通过早停的标签纠正实现泛化（但过训练会退化）。
Functional Scaling Laws in Kernel Regression: Loss Dynamics and Learning Rate Schedules: 在幂律核回归模型中建立了 Functional Scaling Law (FSL)，通过引入"内在时间"概念统一刻画任意学习率调度下的完整 loss 轨迹，并推导出常数/指数衰减/WSD 三种调度在数据受限和计算受限条件下的显式 scaling 关系，理论解释了 WSD 优于纯衰减的经验现象。
Generalization or Hallucination? Understanding Out-of-Context Reasoning in Transformers: 本文论证 LLM 的泛化能力和幻觉产生源于同一机制——脱语境推理（OCR），并在单层注意力模型上理论证明：分解参数化 \((W_O, W_V)\) 因梯度下降的核范数隐式偏差而能执行 OCR，而合并参数化 \(W_{OV}\) 因 Frobenius 范数偏差而不能，且 OCR 是样本高效的（仅需 \(m_{\text{train}}>0\)）。
Gradient Descent As Loss Landscape Navigation A Normative Framework For Deriving: 提出统一框架将各种学习规则（momentum、Adam、自然梯度等）推导为损失景观上的最优导航策略，不同度量和目标自然导出不同的优化器。
Implicit Bias of Spectral Descent and Muon on Multiclass Separable Data: 本文首次完整刻画了归一化最速下降（NSD）和归一化动量最速下降（NMD）在多分类线性可分数据上的隐式偏差：这些算法以 \(\mathcal{O}(1/\sqrt{t})\) 的速率收敛到相应 \(p\)-范数的最大 margin 解，涵盖 Spectral Descent（谱范数）和 Muon 作为特例，并扩展至 Adam（max-范数 margin）。
Improving the Straight-Through Estimator with Zeroth-Order Information: 本文提出 FOGZO（First-Order-Guided Zeroth-Order Gradient Descent），将 STE 梯度作为偏置源注入零阶梯度估计中，在保留 STE 的计算效率的同时利用零阶信息纠正 STE 的偶发错误方向，仅多 2 次前向传播即在 DeiT、ResNet、LLaMA 上实现 1-22 点的精度/困惑度改善。
In Search of Adam's Secret Sauce: 本文通过训练 1500+ 语言模型的大规模实验发现：(1) Signum 虽能缩小 96% 的 SGD-Adam 差距，但仍比 Adam 慢 25%；(2) 设 \(\beta_1 = \beta_2\) 是 Adam 的近最优简化；(3) 在 \(\beta_1 = \beta_2 = \beta\) 下 Adam 可被重新解读为基于在线高斯变分推断估计梯度均值和方差的信噪比自适应 Signum。
Isotropic Noise in Stochastic and Quantum Convex Optimization: 本文引入各向同性随机梯度预言机（ISGO）概念——噪声在每个方向上都以高概率有界——并设计随机切平面算法达到 \(\tilde{O}(R^2\sigma_I^2/\epsilon^2 + d)\) 的查询复杂度，较 SGD 在某些参数区间改进 \(d\) 倍，作为推论获得了 sub-exponential 噪声下的新 SOTA 复杂度，并通过量子各向同性化子程序改进了量子随机凸优化的维度依赖。
Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization: 提出在再生核希尔伯特空间（RKHS）中将对抗扰动从输入空间转移到特征空间的新范式，使内层最大化可精确求解，并通过迭代加权核岭回归高效优化，同时自适应正则化无需调参即可匹配交叉验证性能。
Large Language Bayes: 将 LLM 和概率编程语言（PPL/Stan）数学地"胶合"成联合分布 \(p(z,x,m|t) = p(m|t)_{\text{LLM}} \cdot p(z,x|m)_{\text{PPL}}\)，用户只需提供非形式化的问题描述和数据，系统自动从 LLM 采样候选形式模型、做贝叶斯推断、通过边际似然加权平均，无需用户编写概率模型。
Large Stepsizes Accelerate Gradient Descent for Regularized Logistic Regression: 证明了在线性可分数据上对 \(\ell_2\) 正则化逻辑回归使用大步长 GD（进入 Edge of Stability 区间），可将步复杂度从经典的 \(\widetilde{O}(\kappa)\) 加速到 \(\widetilde{O}(\sqrt{\kappa})\)，在小正则化下匹配 Nesterov 动量的加速率。
Layer-wise Update Aggregation with Recycling for Communication-Efficient Federated Learning: 提出 FedLUAR：基于梯度-权重比的层级优先级度量选择低优先级层复用上一轮梯度（而非丢弃），在仅 17% 通信开销下保持与 FedAvg 几乎相同的精度。
Learning at the Speed of Physics: Equilibrium Propagation on Oscillator Ising Machines: 首次将 Equilibrium Propagation（EP）完整映射到振荡器 Ising Machine（OIM）硬件上，利用 GHz 物理动力学实现无反向传播的局部学习，在 MNIST/Fashion-MNIST 上达到 97.2%/88.0% 精度，并展示在参数量化和噪声下的鲁棒性。
Learning from Interval Targets: 研究仅有区间标签（上下界）的回归问题，建立了基于假设类平滑性的非渐进泛化界（不依赖小 ambiguity degree 假设），并提出 minmax 学习框架利用平滑约束限制最坏情况标签，在 18 个真实数据集上显著优于无约束方法。
Learning Orthogonal Multi-Index Models A Fine-Grained Information Exponent Analy: 证明正交多索引模型 \(f_*(\mathbf{x}) = \sum_{k=1}^P \phi(\mathbf{v}_k^* \cdot \mathbf{x})\) 可通过两阶段在线 SGD 以 \(\tilde{O}(dP^{L-1})\) 样本复杂度学习（\(L\) 为链接函数最低高阶 Hermite 阶），远优于仅用最低阶信息的 \(\tilde{O}(Pd^{L-1})\)——关键在于先用 2 阶项恢复子空间，再用 \(L\) 阶项恢复方向，联合利用不同阶的 Hermite 分量。
Memory-Augmented Potential Field Theory: A Framework for Adaptive Control in Non-Convex Domains: 提出记忆增强势场理论（MAPFT），在随机最优控制中维护一个动态记忆模块来检测并编码状态空间的拓扑特征（局部最小值、低梯度区等），通过动态修改价值函数景观实现非凸环境下的自适应控制，在 Humanoid-v4 等任务上比最优 RL 方法（SAC）提升 27% 累积奖励，且局部最优逃逸率从 ~30% 提升到 ~72%。
MESS+: Dynamically Learned Inference-Time LLM Routing in Model Zoos with Service Level Guarantees: MESS+是首个成本最优的LLM路由框架，通过在线学习请求满足度预测和虚拟队列约束，动态选择模型同时保证SLA合规，相比现有方法实现平均2倍成本节省。
Online Two-Stage Submodular Maximization: 首次提出在线两阶段子模最大化（O2SSM）问题，针对加权阈值势函数（WTP）设计了 RAOCO 算法，通过分数松弛+随机管道舍入实现多项式时间运行下的次线性 \((1-1/e)^2\)-regret 保证，同时改进了离线问题的近似比。
Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality: 提出乐观在线到批量（O2B）转换框架，将乐观性从在线算法中释放到转换机制本身，使简单的在线梯度下降就能实现 \(O(T^{-2})\) 加速收敛率，并首次通过 O2B 转换实现强凸光滑目标的最优收敛，同时达到对光滑性的通用性。
Understanding the Generalization of Stochastic Gradient Adam in Learning Neural Networks: 首次理论分析 mini-batch Adam 的泛化行为，证明大 batch Adam/AdamW 即使带 weight decay 也收敛到高测试误差的解，而小 batch 版本通过随机梯度的隐式正则化 + weight decay 的显式正则化可实现近零测试误差，且 Adam 的有效 weight decay 上界严格小于 AdamW。
Unveiling the Power of Multiple Gossip Steps: A Stability-Based Generalization Analysis in Decentralized Training: 本文首次从算法稳定性角度分析去中心化 SGD（DSGD）中多步 Gossip 通信（MGS）的泛化效果，证明 MGS 以指数速率减少优化误差从而收紧泛化界，但即使 Gossip 步数趋于无穷也无法完全弥合与中心化训练的泛化差距。