论文检索

Optimization · Stochastic

Egor Shulgin, Mohamed Awad, Peter Richtarik, Eduard Gorbunov

We study a broad family of momentum *Linear Minimization Oracle* (LMO) methods that includes normalized SGD with momentum, sign-based (Adam-like) directions, and Muon (spectral) updates. Our focus is on subsampling regimes where the classical uniformly-bounded-variance model can be fragile even for finite-sum objectives on unbounded domains. To obtain subsampling-faithful guarantees, we analyze this LMO family under *expected smoothness* (ABC condition), which captures common sampling schemes. We establish a unified nonconvex convergence theory via a new self-bounding closure that handles the history-coupling induced by momentum under ABC. Our bounds recover known bounded-variance results as a special case and simplify in strong-growth regimes. Specializing to $\tau$-nice sampling, we derive explicit batch-size scaling laws, predicting that the optimal momentum must increase with the batch size to maximize sample efficiency. We further identify a theoretical **optimal batch size** that minimizes total sample complexity. Experiments on linear and matrix regression corroborate these predictions, showing a distinct diagonal shift in the optimal momentum-batch landscape that matches our theoretical scaling.

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.

Applications · Chemistry, Physics, and Earth Sciences

Shreshth Malik, Tiarnan Doherty, Panagiotis Tigas, Muhammed Razzak, Stephen Roberts, Aron Walsh, Yarin Gal

Existing benchmarks for computational materials discovery primarily evaluate static predictive tasks or isolated computational sub-tasks. While valuable, these evaluations neglect the inherently iterative and adaptive nature of scientific discovery. We introduce MAterials Discovery Environments (MADE), a novel framework for benchmarking end-to-end autonomous materials discovery pipelines. MADE simulates closed-loop discovery campaigns in which an agent or algorithm proposes, evaluates, and refines candidate materials under a constrained oracle budget, capturing the sequential and resource-limited nature of real discovery workflows. We formalize discovery as a search for thermodynamically stable compounds relative to a given convex hull, and evaluate efficacy and efficiency via comparison to baseline algorithms. The framework is flexible; users can compose discovery agents from interchangeable components such as generative models, filters, and planners, enabling the study of arbitrary workflows ranging from fixed pipelines to fully agentic systems with tool use and adaptive decision making. We demonstrate this by conducting systematic experiments across a family of systems, enabling ablation of components in discovery pipelines, and comparison of how methods scale with system complexity.

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.

Deep Learning · Graph Neural Networks

PARTH VERMA, Parv P Singh, Vipul Garg, Ishita Thakre, N M Anoop Krishnan, Sayan Ranu

Graph Neural Networks (GNNs) have revolutionized Neural Force Fields for atomistic simulations, achieving near-quantum accuracy at reduced cost, yet adapting these models to new chemical systems requires expensive retraining of foundation models. Inspired by model merging in vision and language processing, we introduce GFFMERGE, the first principled framework for closed-form model merging in GNNs. We exploit the linear structure of message-passing layers and formulate merging as a convex embedding-alignment problem with an analytical solution. Through the first systematic benchmarking of model merging for GNNs, we show that existing methods designed for vision and language catastrophically fail on force field regression, while GFFMERGE recovers performance approaching gold standard joint training. Across molecular (MD17, MD22), solid-state (LiPS20), and large-scale graph benchmarks, GFFMERGE and GNNMERGE (its generic GNN counterpart) achieve 5-27$\times$ speedups while enabling modular composition of specialized models. Remarkably, our closed-form solution alone outperforms all baseline methods before fine-tuning and provides superior initialization for faster, data-efficient convergence.

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.

Optimization · Convex

Sharan Vaswani, Yifan Sun, Reza Babanezhad

Recent work has analyzed the convergence of first-order methods under non-uniform smoothness assumptions that better model the loss landscape in machine learning tasks. We generalize this assumption to objectives whose curvature is an affine function of the objective value. This property is satisfied by a broad class of problems, including logistic regression, generalized linear models with a logistic link function, softmax policy gradient in reinforcement learning, and a class of neural networks. Under this assumption and gradient domination conditions, we establish a general convergence rate for the steepest descent method, and deterministic, diagonal variants of RMSProp and Adam. Our results imply that for logistic regression on separable data and the softmax policy gradient objective, sign GD converges linearly and is provably faster than GD. Furthermore, we show that for a class of two-layer neural networks on separable data, RMSProp and Adam can converge at a linear rate with a constant step-size and momentum parameter. Finally, we present a lower bound demonstrating that, under our assumption, RMSProp and Adam are provably faster than AdaGrad, AMSGrad, gradient descent, and heavy-ball momentum.

Theory · Online Learning and Bandits

Lixing Lyu, Jiashuo Jiang, Wang Chi Cheung

We study infinite-horizon discounted Markov decision processes (DMDPs) under a generative model. Motivated by the Algorithms with Advice framework (Mitzenmacher and Vassilvitskii, 2022), we propose a novel framework to investigate how black-box predictions of the transition matrix can enhance sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on DMDPs with $N$ state–action pairs and discount factor $\gamma$. We first provide an impossibility result showing that, in the presence of predictions with unknown accuracy, no sampling policy can compute an $\epsilon$-optimal policy with a sample complexity better than $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, which matches the state-of-the-art minimax sample complexity bound without prediction. In complement, we design an algorithm based on minimax optimization techniques that leverages predictions of the transition matrix without requiring knowledge of the prediction error. Our algorithm achieves a sample complexity bound that depends on the prediction error and is uniformly better than $\tilde{O}((1-\gamma)^{-4} N \epsilon^{-2})$, the previous best result derived from convex optimization methods. In some cases, our bound even improves upon the state-of-the-art $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, despite not having access to the prediction quality.

Optimization · Convex

Abhishek Chakraborty, Angelia Nedich

We consider minimizing an objective function subject to constraints defined by the intersection of lower-level sets of convex functions. We study two cases: (i) strongly convex and Lipschitz-smooth objective function and (ii) convex but possibly nonsmooth objective function. To deal with the constraints that are not easy to project on, we use a randomized feasibility algorithm with Polyak steps and a random number of sampled constraints per iteration, while taking (sub)gradient steps to minimize the objective function. For case (i), we prove linear convergence in expectation of the objective function values to any prescribed tolerance using an adaptive stepsize. For case (ii), we develop a fully problem parameter-free and adaptive stepsize scheme that yields an $O(1/\sqrt{T})$ worst-case rate in expectation. The infeasibility of the iterates decreases geometrically with the number of feasibility updates almost surely, while for the averaged iterates, we establish an expected lower bound on the function values relative to the optimal value that depends on the distribution for the random number of sampled constraints. For certain choices of sample-size growth, optimal rates are achieved. Finally, simulations on a Quadratically Constrained Quadratic Programming (QCQP) problem and Support Vector Machines (SVM) demonstrate the computational efficiency of our algorithm compared to other state-of-the-art methods.

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.

Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma, Jiaxin Song

We study equilibrium pricing in oligopolistic data markets with budget-constrained buyers (e.g., ML companies purchasing data to improve model accuracy) and strategic data sellers. Sellers compete by setting prices for their datasets, giving rise to a pricing game whose pure Nash equilibria correspond to equilibrium prices. While equilibrium prices are guaranteed for rivalrous goods via competitive equilibrium, we show that the non-rivalry of data fundamentally alters this picture: an exact Nash equilibrium need not exist, and in fact no 1.364-approximate equilibrium exists under uniform pricing. We therefore investigate relaxed equilibrium notions. Allowing sellers to use beyond-uniform pricing—specifically, piecewise-linear convex pricing functions—guarantees approximate stability within a constant factor: there exists a pricing profile in which no seller can improve revenue by a factor of two by deviating to any uniform price (a 2-approximate Nash equilibrium). Finally, our simulations demonstrate fast convergence and empirical approximation guarantees that outperform the worst-case bound of 2.

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.

Theory · Learning Theory

Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo

The empirical evidence indicates that stochastic optimization with heavy-tailed gradient noise is more appropriate to characterize the training of machine learning models than that with standard bounded gradient variance noise. Most existing works on this phenomenon focus on the convergence of optimization errors, while the analysis for generalization bounds under the heavy-tailed gradient noise remains limited. In this paper, we develop a general framework for establishing generalization bounds under heavy-tailed noise. Specifically, we introduce a truncation argument to achieve the generalization error bound based on the algorithmic stability under the assumption of bounded $p$th centered moment with $p\in(1,2]$. Building on this framework, we further provide the stability and generalization analysis for several popular stochastic algorithms under heavy-tailed noise, including clipped and normalized stochastic gradient descent, as well as their mini-batch and momentum variants.

Social Aspects · Accountability, Transparency, and Interpretability

Zongxin Liu, Xiaoyong Xue, Sun Weidi, Shengchao Qin, Lijun Zhang

Precise, training-free editing of text-to-image diffusion models requires balancing alignment (faithful attribute manifestation), consistency (preserving non-target content), and quality (artifact-free textures). Sparse autoencoder (SAE) steering offers interpretable, smooth ``slider-like'' control by manipulating SAE feature activations derived from the text encoder; however, existing approaches rely on heuristic feature selection and manual tuning of the steering strength, leading to suboptimal trade-offs among the three objectives. We propose Sparse Relaxed-Lasso Steering (SRLS), which casts steering-vector discovery as a convex sparse recovery problem. Exploiting the affine structure of the SAE decoder, SRLS automatically identifies sparse, generalizable support sets via a Lasso objective, and then debiases the coefficients using support-restricted ridge regression. We further select the optimal steering strength using Bayesian optimization. Experiments across diverse attributes and subjects show that SRLS generally improves over other methods, yielding a better balance among alignment, consistency, and quality.

Theory · Deep Learning

Albert Alcalde, Borjan Geshkovski, Domènec Ruiz-Balet

We analyze the hardmax limit of self-attention dynamics for token embeddings in the zero-temperature regime $(\beta \to +\infty)$ and relate it to finite-$\beta$ behavior. In this limit, the update rule can be viewed as a Frank-Wolfe step for a quadratic objective over the convex hull of the current tokens. When the key-query matrix is negative semidefinite, the dynamics converge with the standard sublinear rate $\mathcal{O}(t^{-1})$ on the quadratic energy, whereas in the positive semidefinite case, extending the hardmax rule to the convex hull induces a Voronoi structure: vertices are stationary, interior points remain in their initial cells, and each token moves along a straight line toward its cell's vertex with exponential convergence under a step-size bounded away from zero. We additionally establish well-posedness of the associated ODE limit in this regime. For finite $\beta$, we model self-attention as a Markov chain and prove *dynamic metastability*: interior tokens reach near-vertex configurations in a constant number of steps and remain trapped for times exponential in $\beta$ with high probability, before eventual collapse to some point within the initial convex hull. Thus, hardmax dynamics accurately approximate the finite-$\beta$ process over exponentially long time horizons.