论文检索

General Machine Learning · Representation Learning

Yahya Sattar, Sunmook Choi, Leo Maynard-Zhang, Yassir Jedra, Maryam Fazel, Sarah Dean

Auto-regressive models have emerged as powerful tools for sequential data, from language to video. Understanding how and why these models learn latent representations remains an open theoretical question. In this work, we demonstrate that when trained by empirical risk minimization on data from partially observed linear dynamical systems, two-layer linear auto-regressive models naturally learn to approximate Kalman filtering. In particular, we show that the learned hidden representation coincides, up to a similarity transformation, with the state estimates produced by the optimal (Kalman) filter, even though the model has no explicit knowledge of the underlying dynamics or state. The result follows from three main insights. First, we establish that the Kalman filter is well approximated by an auto-regressive model with bounded truncation error. Second, we show that despite non-convexity, the two-layer optimization landscape is benign, i.e., all stationary points are either strictly saddle or global minima. Finally, as our main contributions, we provide finite-sample guarantees on prediction error, parameter estimation error, and latent state recovery. Numerical simulations support the theoretical results and demonstrate that auto-regressive models automatically represent latent state estimates.

Probabilistic Methods · Monte Carlo and Sampling Methods

Zonghao Chen, Toni Karvonen, Heishiro Kanagawa, Francois-Xavier Briol, Chris J Oates

Approximation of a target probability distribution using a finite set of points is a problem of fundamental importance in numerical integration. Several authors have proposed to select points by minimising a maximum mean discrepancy (MMD), but the non-convexity of this objective typically precludes global minimisation. Instead, we consider the concept of \emph{stationary points of the MMD} which, in contrast to points globally minimising the MMD, can be accurately computed. Our main contributions are two-fold and theoretical in nature. We first prove the (perhaps surprising) result that, for integrands in the associated reproducing kernel Hilbert space, the numerical integration error of stationary MMD points vanishes \emph{faster} than the MMD. Motivated by this \emph{super-convergence} property, we consider MMD gradient flows as a practical strategy for computing stationary points of the MMD. We then prove that MMD gradient flow can indeed compute stationary MMD points, based on a refined convergence analysis that establishes a novel non-asymptotic finite-particle error bound.

Optimization · Non-Convex

Chenyu Gao, Zhexian Yang, Ziping Zhao

Estimating statistical parameters from quantized data has received significant attention in recent years, as recovering information from quantized measurements has numerous applications across signal processing, communications, and data analysis. In this work, we focus on maximum likelihood (ML) estimation of statistical parameters from quantized samples. Directly solving the ML problem is challenging, as the likelihood function involves multiple integrals that are difficult to evaluate. To address this challenge, we propose an expectation-conditional-maximization (ECM) algorithm under a general distributional framework. Our approach generalizes the quantization model to multi-bit settings and allows the underlying signal to follow any distribution within the normal mean-variance mixture family. By designing suitable surrogate functions, the ECM algorithm ensures that all model parameters can be updated in closed form at each iteration. Leveraging the ECM framework, we provide convergence guarantees, and under specific distributional assumptions, we further derive bounds on the convergence rate and the statistical error. Extensive experiments demonstrate the effectiveness of our method in recovering statistical parameters from quantized data.

Optimization · Stochastic

Maria-Eleni Sfyraki, Jun-Kun Wang

Stochastic Frank-Wolfe is a classical optimization method for solving constrained optimization problems. On the other hand, recent optimizers such as Lion and Muon have gained quite significant popularity in deep learning. In this work, building on recent initiatives, we provide a unifying perspective by interpreting these seemingly disparate methods through the lens of Stochastic Frank-Wolfe. Specifically, we show that Lion and Muon with weight decay can be viewed as special instances of a Stochastic Frank-Wolfe, and we establish their convergence guarantees in terms of the Frank-Wolfe gap, a standard stationarity measure in non-convex optimization for Frank-Wolfe methods. We further find that convergence to this gap implies convergence to a KKT point of the original problem under a norm constraint for Lion and Muon. Moreover, motivated by recent empirical findings that stochastic gradients in modern machine learning tasks often exhibit heavy-tailed distributions, we extend Stochastic Frank-Wolfe to settings with heavy-tailed noise by developing two robust variants with strong theoretical guarantees that hold for general compact convex sets without the need for a large batch size, filling the gap in the literature on Stochastic Frank-Wolfe for non-convex optimization. Our contributions in the later part of this work, in turn, yield new variants of Lion and Muon, that better accommodate heavy-tailed gradient noise, thereby enhancing their practical scope.

Optimization · Large Scale, Parallel and Distributed

Yijiang Li, Emon Dey, Zilinghan Li, Krishnan Raghavan, Ravi Madduri, Kibaek Kim

Federated learning~(FL) across multiple HPC facilities faces stochastic \emph{admission delays} from batch schedulers that dominate wall-clock time. Synchronous FL suffers from severe stragglers, while asynchronous FL accumulates stale updates when queues spike. We propose \fedqueue{}, a queue-aware FL protocol that incorporates scheduler delays directly into training and aggregation, which (i) predicts per-facility queue delays online to budget local work, (ii) applies cutoff-based admission that buffers late arrivals to bound staleness, and (iii) performs staleness-aware aggregation to stabilize heterogeneous local workloads. We prove the convergence for non-convex objectives at rate $\mathcal{O}(1/\sqrt{R})$ under bounded staleness, and show that the admission controls yield bounded staleness with high probability under queue-prediction error. Real-world cross-facility deployment of \fedqueue{} shows 20.5\% improvement over baseline algorithms. Controlled queue simulations demonstrate robust improvement over the baselines; in particular, about 34\% reduction in time to reach a target accuracy level under high queue variance and non-IID partitions.

Optimization · Non-Convex

Artem Riabinin, Egor Shulgin, Kaja Gruntkowska, Peter Richtarik

Recent developments in deep learning optimization have brought about radically new algorithms based on the Linear Minimization Oracle (LMO) framework, such as Muon and Scion. After over a decade of Adam's dominance, these LMO-based methods are emerging as viable replacements, offering several practical advantages such as improved memory efficiency, better hyperparameter transferability, and most importantly, superior empirical performance on large-scale tasks, including LLM training. However, a significant gap remains between their practical use and our current theoretical understanding: prior analyses (1) overlook the layer-wise LMO application of these optimizers in practice, and (2) rely on an unrealistic smoothness assumption, leading to impractically small stepsizes. To address both, we propose a new LMO-based framework called Gluon, capturing prior theoretically analyzed methods as special cases, and introduce a new refined generalized smoothness model that captures the layer-wise geometry of neural networks, matches the layer-wise practical implementation of Muon and Scion, and leads to state-of-the-art convergence guarantees. Our experiments with NanoGPT and CNN confirm that our assumption holds along the optimization trajectory, ultimately closing the gap between theory and practice.

Optimization · Non-Convex

Egor Shulgin, Tamaz Gadaev, Sarit Khirirat, Peter Richtarik

MARS has recently emerged as a state-of-the-art optimizer, consistently outperforming AdamW in large language model (LLM) training. It modifies the momentum-based variance reduction (MVR) update by introducing a multiplicative coefficient $\gamma$, which scales the momentum correction term. However, the existing theory of Yuan et al. (2025) does not explain why this modification improves the convergence of MARS over MVR. In this paper, we provide a rigorous theoretical explanation for the superiority of MARS over MVR. We introduce the novel similarity condition, called **$\gamma$-similarity**, which generalizes standard similarity and smoothness assumptions for analyzing stochastic algorithms. Under this condition, we derive gradient complexity guarantees for MARS, which explicitly depend on $\gamma$ and a $\gamma$-similarity constant $\delta_\gamma$. We prove that by appropriately tuning $\gamma \in [0,1]$, MARS achieves strictly lower complexity than MVR. Finally, experiments on GPT pretraining corroborate our theoretical findings, demonstrating that MARS with an optimal choice of $\gamma$ improves token efficiency over MVR, and yields substantial gains compared to AdamW.

Applications · Robotics

Zhicheng Fan, Zitong Wu, Zhaoxing Fan, Xiao Zhang, Biao Hou, Bo Ren

Conventional dynamic SLAM approaches typically treat dynamic objects as outliers based on pre-defined categories, creating perceptual blind spots that limit the comprehensive environmental perception required for embodied agents. Although integrating Gaussian Splatting into SLAM enables holistic scene representation, it introduces an optimization paradox: without categorical priors, flexible dynamic primitives rapidly overfit static residuals. This phenomenon undermines the self-supervised error signals necessary for distinguishing motion. In response, we present De4D-SLAM, a novel framework designed for decoupled 4D reconstruction from monocular video. Our approach features a Gradient-Isolated Decoupling strategy, which leverages static reconstruction residuals to supervise a Spatially-Aware Kolmogorov-Arnold Network (SA-KAN), ensuring robust, category-agnostic motion segmentation. Additionally, we propose a Flow-Induced Initialization prior to stabilize the non-convex optimization of 4D Gaussian primitives using dense optical flow. Extensive evaluations on the TUM and Bonn benchmarks demonstrate that De4D-SLAM achieves state-of-the-art performance in both tracking and dynamic reconstruction, successfully reconciling the tension between robust localization and high-fidelity 4D mapping.

Deep Learning · Large Language Models

Ziqing Wen, Jiahuan Wang, ping luo, Dongsheng Li, Tao Sun

Large language models (LLMs) have demonstrated remarkable performance due to their large parameter counts and extensive training data. However, their scale leads to significant memory bottlenecks during training, especially when using memory-intensive optimizers like Adam. Existing memory-efficient approaches often rely on techniques such as singular value decomposition (SVD), projections, or weight freezing, which can introduce substantial computational overhead, require additional memory for projections, or degrade model performance. In this paper, we propose Folded Optimizer with Approximate Moment (FOAM), a method that compresses optimizer states by computing block-wise gradient means and incorporates a residual correction to recover lost information. Theoretically, FOAM achieves convergence rates equivalent to vanilla Adam under standard non-convex optimization settings. Empirically, FOAM eliminates up to 90\% of the memory overhead of optimizer states and accelerates convergence. Furthermore, FOAM is compatible with other memory-efficient optimizers, delivering performance and throughput that match or surpass both full-rank and existing memory-efficient baselines.

Optimization · Non-Convex

Huan Li, Yiming Dong, Zhouchen Lin

This paper studies the AdamW-style Shampoo optimizer, an effective implementation of the classical Shampoo that notably won the external tuning track of the AlgoPerf neural network training algorithm competition. Our analysis unifies one-sided and two-sided preconditioning and establishes the convergence rate $\frac{1}{K}\sum_{k=1}^KE[|||\nabla f(X_k)|||]\leq O(\frac{\sqrt{m+n}C}{K^{1/4}})$ measured by nuclear norm (denoted as $|||\cdot|||$ to display correctly in OpenReview), where $K$ represents the iteration number, $(m,n)$ denotes the size of matrix parameters, and $C$ matches the constant in the optimal convergence rate of SGD. Theoretically, we have $||\nabla f(X)||\leq|||\nabla f(X)|||\leq\sqrt{\min(m,n)}||\nabla f(X)||$ (denote $||\cdot||$ as the Frobenius norm to display correctly in OpenReview), supporting that our convergence rate can be considered to be analogous to the optimal $\frac{1}{K}\sum_{k=1}^K E[||\nabla f(X_k)||]\leq O(\frac{C}{K^{1/4}})$ convergence rate of SGD in the ideal case of $|||\nabla f(X)|||= \Theta(\sqrt{\min(m,n)})||\nabla f(X)||$ and balanced $m$ and $n$.

Optimization · Large Scale, Parallel and Distributed

Aleksandar Armacki, Ali Sayed

Convergence in high-probability (HP) has attracted increasing interest, due to implying exponentially decaying tail bounds and strong guarantees for individual runs of an algorithm. While many works study HP guarantees in centralized settings, much less is understood in the decentralized setup, where existing works require strong assumptions, like uniformly bounded gradients, or asymptotically vanishing noise. This results in a significant gap between the assumptions used to establish convergence in the HP and the mean-squared error (MSE) sense, and is also contrary to centralized settings, where it is known that $\mathtt{SGD}$ converges in HP under the same conditions on the cost function as needed for MSE convergence. Motivated by these observations, we study the HP convergence of Decentralized $\mathtt{SGD}$ ($\mathtt{DSGD}$) in the presence of light-tailed noise, providing several strong results. First, we show that $\mathtt{DSGD}$ converges in HP under the same conditions on the cost as in the MSE sense, removing the restrictive assumptions used in prior works. Second, our sharp analysis yields order-optimal rates for both non-convex and strongly convex costs. Third, we establish a linear speed-up in the number of users, leading to matching, or strictly better transient times than those obtained from MSE results, further underlining the tightness of our analysis. To the best of our knowledge, this is the first work that shows $\mathtt{DSGD}$ achieves a linear speed-up in the HP sense. Our relaxed assumptions and sharp rates stem from several technical results of independent interest, including a result on the variance-reduction effect of decentralized methods in the HP sense, as well as a novel bound on the MGF of strongly convex costs, which is of interest even in centralized settings. Finally, we provide experiments that validate our theory.

Social Aspects · Privacy

Difei Xu, Youming Tao, Meng Ding, Chenglin Fan, Di Wang

We provide the first study of the problem of finding differentially private (DP) second-order stationary points (SOSP) in stochastic (non-convex) minimax optimization. Existing literature either focuses only on first-order stationary points for minimax problems or on SOSP for classical stochastic minimization problems. This work provides, for the first time, a unified and detailed treatment of both empirical and population risks. Specifically, we propose a purely first-order method that combines a nested gradient descent--ascent scheme with SPIDER-style variance reduction and Gaussian perturbations to ensure privacy. A key technical device is a block-wise ($q$-period) analysis that controls the accumulation of stochastic variance and privacy noise without summing over the full iteration horizon, yielding a unified treatment of both empirical-risk and population formulations. Under standard smoothness, Hessian-Lipschitzness, and strong concavity assumptions, we establish high-probability guarantees for reaching an $(\alpha,\sqrt{\rho_\Phi \alpha})$-approximate second-order stationary point with $\alpha = \mathcal{O}( (\frac{\sqrt{d}}{n\varepsilon})^{2/3})$ for empirical risk objectives and $\mathcal{O}(\frac{1}{n^{1/3}} + (\frac{\sqrt{d}}{n\varepsilon})^{1/2})$ for population objectives, matching the best known rates for private first-order stationarity.

Shervin Khalafi, Alejandro Ribeiro, Dongsheng Ding

Unlearning in diffusion models aims to remove undesirable data or concepts while preserving the utility of pretrained models---two fundamentally conflicting objectives. We propose a principled constrained optimization framework that formulates unlearning as minimizing the deviation from a pretrained model, subject to explicit separation constraints from the unlearning distributions. Specifically, we formulate three constrained optimization problems based on reverse and forward KL divergences, and likelihood constraints. The first two generalize existing approaches for concept and data unlearning, while the third offers a novel and natural formulation for unlearning. Despite the non-convexity of the KL constraints, we establish strong duality for all three problems, enabling us to explicitly characterize their optimal solutions as unlearning targets and develop primal–dual algorithms for each formulation. Experimental results demonstrate that our KL-constrained approach achieves superior retaining-unlearning trade-offs compared to weight-based baselines for concept and data unlearning, and that our likelihood-based approach matches unlearning effectiveness while better preserving retained concepts compared to baselines.

Social Aspects · Privacy

Yiting Hu, Lingjie Duan, Qian Zhang

Machine unlearning aims to eliminate the influence of specific data from trained models to safeguard privacy. However, this presents a significant challenge in the context of continual learning (CL), where models update sequentially on dynamic datasets. A major limitation is that current certified unlearning algorithms fail to account for the complex, cumulative model evolution inherent to CL framework. In this work, we establish the first theoretical foundation bridging CL and machine unlearning. We formulate the CL's unlearning objective as the minimization of post-unlearning excess risk, which decomposes into CL excess risk and unlearning loss, characterizing the fundamental trade-off between preserving historical knowledge and targeted forgetting. Under mild assumptions, we first establish an upper bound for the CL excess risk in non-convex models. We then adapt two certified unlearning approaches, gradient-based and Hessian-based, to the CL framework. Our analysis reveals that while the gradient-based approach is less effective than the Hessian-based method in minimizing unlearning loss, it offers the distinct advantage of nearly zero storage overhead for enabling unlearning. This insight inspire us for a combination strategy to minimize storage costs while maintaining post-unlearning performance. Experimental results further validate our theoretical findings.

Augustinos Saravanos, Oswin So, H M Sabbir Ahmad, Chuchu Fan

We introduce *FlowOptimizer*, a deep unfolded, flow-based framework for learned iterative optimization. Motivated by the expressiveness of flow models, we represent each optimization iteration via a velocity field that operates on a population of candidate solutions, i.e., a set of parallel iterates, conditioned on contextual information including their objective values and gradients, as well as population-level statistics. The velocity field is initially trained in a simulation-free manner by matching displacements from source populations to improved target ones obtained through sampling the objective. Subsequently, we unfold this velocity field as the internal iteration of an optimization sequence, and fine-tune it in an end-to-end manner by directly optimizing objective values over a targeted class of problems. Notably, FlowOptimizer is a self-supervised framework whose training relies solely on objective evaluations without requiring knowledge of solutions. We evaluate our approach on a series of tasks from standard non-convex optimization benchmarks to real-world problems from supply chain, robotics and power grid applications. FlowOptimizer consistently outperforms well-established sampling-based/gradient-based traditional optimization and learning-to-optimize methods, often by orders of magnitude in terms of solution quality. We further highlight its ability to be trained on low-dimensional problems and successfully generalize to substantially higher-dimensional $(\times 10)$ ones.

Applications · Computer Vision

Meisheng Zhang, Shizhao Sun, Yang Zhao, Ziyuan Liu, Zhijun Gao, Jiang Bian

Autonomous 3D indoor scene synthesis breaks down in non-convex rooms with tightly coupled spatial constraints. Data-driven generators lack topological priors for long-horizon planning, while iterative agents fragment semantics and become geometrically brittle. We present \textbf{ZoneMaestro}, a unified framework that shifts the paradigm from object-centric synthesis to Zone-Graph Orchestration. By internalizing a novel zone-based logic, ZoneMaestro translates high-level semantic intent into functional zones and topological constraints, enabling robust adaptation to diverse architectural forms. To support this, we construct \textit{Zone-Scene-10K}, a large-scale dataset enriched with explicit Zone-Graph annotations. We further introduce an \textit{Alternating Alignment Strategy} that cycles between reasoning internalization and Zone-Aware Group Relative Policy Optimization (\textit{Z-GRPO}), effectively reconciling the tension between semantic richness and geometric validity without relying on external physics engines. To rigorously evaluate spatial intelligence beyond convex primitives, we formally define the task of \textbf{Intricate Spatial Orchestration} and release SCALE, a stress-test benchmark for irregular indoor scenarios with complex, dense spatial relations. Extensive experiments demonstrate that ZoneMaestro resolves the density-safety dichotomy, significantly outperforming state-of-the-art baselines in both structural coherence and intent adherence.

Optimization · Non-Convex

Chenghao Liu, Enming Liang, Minghua Chen

We study optimization over non-convex constraint sets that are homeomorphic to a ball, encompassing important problem classes such as star-shaped sets that frequently arise in machine learning and engineering applications. We propose Hom-PGD$^+$, a learning-based and projection-efficient first-order method that efficiently solves such problems without requiring expensive projection or optimization oracles. Our approach leverages an invertible neural network (INN) to learn the homeomorphism between the non-convex constraint set and a unit ball, transforming the original problem into an equivalent ball-constrained optimization where projections admit closed-form solutions. We establish that Hom-PGD$^+$ achieves an $\mathcal{O}(\epsilon^{-2})$ convergence rate to an ($\epsilon + \mathcal{O}(\sqrt{\epsilon_{\rm inn}})$)-approximate stationary solution, where $\epsilon_{\rm inn}$ denotes the homeomorphism learning error. This rate significantly improves upon existing methods for optimization over non-convex sets, while maintaining a per-iteration complexity of only $\mathcal{O}(W)$ for $W$ INN parameters. Experiments on chance-constrained optimization problems in power systems demonstrate that Hom-PGD$^+$ achieves convergence rates comparable to state-of-the-art methods while delivering speedups of up to one order of magnitude.

Reinforcement Learning · Everything Else

Xiaoyuan Cheng, Wenxuan Yuan, Boyang Li, Yuanchao Xu, Yiming Yang, Hao Liang, Bei Peng, Robert Loftin, Zhuo Sun, Yukun Hu

Diffusion policy sampling enables reinforcement learning (RL) to represent multimodal action distributions beyond suboptimal unimodal Gaussian policies. However, existing diffusion-based RL methods primarily focus on offline setting for reward maximization, with limited consideration of safety in online settings. To address this gap, we propose Augmented Lagrangian-Guided Diffusion (ALGD), a novel algorithm for off-policy safe RL. By revisiting optimization theory and energy-based modeling, we show that the instability of primal–dual methods arises from the non-convex Lagrangian landscape. In diffusion-based safe RL, the Lagrangian can be interpreted as an energy function guiding the denoising dynamics; counter-intuitively, direct usage destabilizes both policy generation and training. ALGD resolves this issue by introducing an augmented Lagrangian that locally convexifies the energy landscape, yielding a stabilized policy generation and training, without altering the distribution of optimal policy. Theoretical analysis and extensive experiments demonstrate that ALGD is both theoretically grounded and empirically effective, achieving strong and stable performance across diverse environments.

Optimization · Non-Convex

Zuqi Zhang, Chenghe Sun, Xiangyi Chu, Wei-Han Yu, Ka-Fai Un, Rui Martins, Pui-In Mak, Jiawei Xu

Adaptive rounding techniques in Post-Training Quantization (PTQ) enable the efficient deployment of Large Language Models (LLMs) with low resource and data dependencies. While learning-based rounding methods are accurate yet costly, compensation-based approaches offer a highly efficient alternative. However, synergizing these two to realize their full potential is hindered by spatiotemporal misalignment in the decoupled paradigm. Key challenges include temporal parameter conflict, the invalidation of the initial Round-to-Nearest (RTN) assumption, and spatially-inconsistent optimization objectives. This paper introduces STLA, a novel rounding-optimized PTQ framework that achieves both fast and accurate LLM quantization. STLA resolves temporal inconsistency through cluster-wise integrated rounding optimization, which collocates the learning and compensation phases. STLA achieves spatial alignment through a unified global objective derived from the Schur Complement, enabling the solver to look ahead and align local rounding decisions with the optimal future compensation of remaining weights. Furthermore, we propose a Hessian-guided clustering strategy that exploits both diagonal and off-diagonal information to maximize intra-cluster error cancellation. Extensive experiments demonstrate that STLA establishes a new state-of-the-art for low-bit PTQ while maintaining high computational efficiency. The code is available at https://anonymous.4open.science/r/STLA.

Optimization · Non-Convex

Christopher Harker, Aditya Bhaskara

The DeepWalk algorithm has been widely used for learning node embeddings in graphs. Combined with the idea of _negative sampling_, the DeepWalk algorithm has been shown to be implementable at scale, easily handling graphs with millions of nodes. However, theoretical guarantees on the resulting embeddings are much less understood. Recent results have studied the minimizers of the objective and have shown interesting guarantees for certain graph classes. However, the optimization _trajectory_, i.e., what happens when we start at a random initialization and run gradient descent, remains poorly understood. This is especially true for the implementation of DeepWalk using Skip-gram with negative sampling (SGNS), since the variance of the stochastic updates turns out to be very large. In this work, we make progress on this question. We show that for "small norm" initialization, under a spectral gap assumption on the graph, the DeepWalk embeddings align with the column space of a fixed low-rank matrix. For graphs generated from Stochastic Block Models with certain separation conditions, our results imply that the DeepWalk embeddings recover cluster structure. To the best of our knowledge, our results give the first analysis of the optimization trajectory of DeepWalk with negative sampling on non-trivial graph classes.