theory->optimization

Optimization problems are fundamental across science and industry, including planning, scheduling, and resource allocation. While LLMs show promise in automating optimization, they struggle to bridge the gap between real-world requirements and both mathematical formulations and effective heuristic designs. Furthermore, the field lacks a unified framework that spans problem formulation and heuristic discovery for NP-hard settings. To address these challenges, we propose OptMaster, a unified framework that spans optimization from formulation to heuristic discovery, structuring the process as a Directed Acyclic Graph (DAG) where each node represents a candidate solution. The DAG architecture enables cross-branch knowledge transfer when search progress stagnates. Within each node, we further replace textual self-reflection with independently generated verification code, grounding the evaluation in deterministic computation to suppress hallucinations. OptMaster achieves competitive performance across two optimization paradigms. In Formulation Intelligence, OptMaster achieves state-of-the-art accuracy across the three most challenging benchmarks in the field. In Heuristic Discovery, OptMaster surpasses the best known solutions on Circle Packing ($n=26, 32$) and achieves a cut of 9,590 on Gset70 with significantly reduced time and search budgets.

As Large Language Models (LLMs) more deeply integrate into human life across various regions, aligning them with pluralistic cultures is crucial for improving user engagement and mitigating cultural conflicts. For this purpose, recently, different culture-specific corpora have been carefully curated, either synthesized or manually annotated. Nevertheless, inspired by culture theories, we identify two key challenges faced by these datasets: (1) Representativeness: These corpora fail to fully capture the target culture's core characteristics, causing insufficient cultural coverage with redundancy; (2) Distinctiveness: They struggle to distinguish the unique nuances of a given culture from shared patterns across other relevant ones, hindering precise cultural modelling. To handle these challenges, we introduce CAReDiO, a novel data optimization framework, which alternatively refines culture-sensitive questions and responses according to information-theoretic objectives in an in-context optimization manner, enhancing the cultural informativeness and distinguishability of constructed data. Extensive experiments on 15 distinct cultures demonstrate that CAReDiO can create high-quality data with richer cultural information and enable efficient alignment of small open-source or large proprietary LLMs with as few as 200 training samples, consistently outperforming previous datasets in both multi-choice and open-ended cultural benchmarks.

Many machine learning techniques rely on approximating a loss function's curvature, but this is notoriously hard to do at the scale of modern deep networks. Surprisingly, no previous work has exploited the curvature constraints that arise from well known weight-space symmetries in loss landscapes. By analytically averaging over group actions that leave the loss invariant, we construct structured Hessian approximations from single gradients that can be tractably estimated, stored, and inverted. The choice of user-specified symmetry group directly governs the trade-off between approximation accuracy and computational cost. Moreover, our framework provides a unifying theoretical lens for viewing existing methods; in particular, a specific choice of symmetry group recovers Shampoo/Muon-like curvature estimates. We validate our method on a range of network architectures, and deploy it to second-order optimization benchmarks, including a small language model. Our curvature estimation framework might find applications in other machine learning problems such as uncertainty estimation, continual learning, compression/pruning, training data attribution, and more.

We present a theoretical analysis of stochastic optimization methods in terms of their sensitivity with respect to the step size. We identify a key quantity that, for each method, describes how the performance degrades as the step size becomes too large. For convex problems, we show that this quantity directly impacts the suboptimality bound of the method. Most importantly, our analysis provides direct *theoretical* evidence that adaptive step size methods, such as SPS or NGN, are more robust than SGD. This allows us to quantify the advantage of these adaptive methods beyond empirical evaluation. Finally, we show through experiments that our theoretical bound qualitatively mirrors the actual performance as a function of the step size, even for non-convex problems.

Physics-Informed Neural Networks (PINNs) often train slowly or fail to converge on challenging partial differential equations (PDEs), a behavior recently linked to severely ill-conditioned loss landscapes inherited from the underlying differential operator. We study PINNs augmented with a pointwise data-fidelity term, added at a few points in the domain to the standard residual and boundary losses. We show that this supervision term acts as an operator-level preconditioner: for suitable weights, our comparison bounds guarantee a substantially smaller condition number than under the standard PINN loss, independently of how the pointwise labels are obtained. For a broad class of PDEs admitting a Feynman-Kac (FK) representation, we generate such labels by Monte Carlo averages of the FK functional, resulting in what we call "FK-PINNs", and using the excess risk decomposition approach, we derive non-asymptotic $L^2(\Omega)$-error bounds for FK-PINNs with $\tanh$ activation trained by finitely many steps of gradient descent. Along the way, we establish pseudo-dimension bounds for first- and second-order derivatives of $\tanh$ neural networks, which are of independent interest and, to the best of our knowledge, new. Numerical experiments on Poisson, Schrödinger, mean exit time, and committor problems corroborate the theory, and show that FK-PINNs can successfully solve PDEs for which standard PINNs exhibit severe failure modes.

In this paper, we study the role of the critic in actor-critic for entropy-regularized, finite, discounted environments. We establish that, when the critic is exact, using the latter as a baseline is an actual variance-reduction method. In this case, actor-critic with stochastic gradients matches the sample complexity of deterministic policy gradient, reaching an $\epsilon$-optimal regularized value with $\tilde{O}(\log(1/\epsilon))$ samples. In practice, the critic is learned alongside the actor: the variance of the actor update is then influenced by the critic's variance and bias. Specifically, when the critic has a sufficiently small error, the variance reduction and rapid convergence are preserved. This suggests to learn the critic first, keeping it up to date after each actor update, underscoring the pivotal role of accurate critic estimation in actor-critic methods.

Kolmogorov--Arnold Networks (KANs) have recently emerged as a structured alternative to standard MLPs, yet a principled theory for their training dynamics, generalization, and privacy properties remains limited. In this paper, we analyze gradient descent (GD) for training two-layer KANs and derive general bounds that characterize their training dynamics, generalization, and utility under differential privacy (DP). As a concrete instantiation, we specialize our analysis to logistic loss under an NTK-separable assumption, where we show that polylogarithmic network width suffices for GD to achieve an optimization rate of order $1/T$ and a generalization rate of order $1/n$, with $T$ denoting the number of GD iterations and $n$ the sample size. In the private setting, we characterize the noise required for $(\epsilon,\delta)$-DP and obtain a utility bound of order $\sqrt{d}/(n\epsilon)$ (with $d$ the input dimension), matching the classical lower bound for general convex Lipschitz problems. Our results imply that polylogarithmic width is not only sufficient but also necessary under differential privacy, revealing a qualitative gap between non-private (sufficiency only) and private (necessity also emerges) training regimes. Experiments further illustrate how these theoretical insights can guide practical choices, including network width selection and early stopping.

We study a widely used Bayesian optimization method, Gaussian process Thompson sampling (GP-TS), under the assumption that the objective function is a sample path from a GP. Compared with the GP upper confidence bound (GP-UCB) with established high-probability and expected regret bounds, most analyses of GP-TS have been limited to expected regret. Moreover, whether the recent analyses of GP-UCB for the lenient regret and the improved cumulative regret upper bound can be applied to GP-TS remains unclear. To fill these gaps, this paper shows several regret bounds: (i) a regret lower bound for GP-TS, which implies that GP-TS suffers from a polynomial dependence on $1/\delta$ with probability $\delta$, (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on $\delta$, (iii) expected lenient regret upper bounds, and (iv) an improved cumulative regret upper bound on the time horizon $T$. Along the way, we provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on $T$.

Transaction cost optimization (TCO) of online portfolio selection is crucial in computing science, due to the significant impact of transaction costs in practical short-term trading. Moreover, sparsity of portfolio vector is often desired to enhance stability and decrease risk. However, there is a lack of models considering transaction costs and sparsity simultaneously in the literature. In this paper, we first propose a $K$-sparse TCO model that minimizes the negative return and transaction costs while keeping the portfolio vector being $K$-sparse. Noting that the model is NP-hard due to the $K$-sparse constraint, we bypass this difficulty by reformulating the sparse model to a nonsmooth difference of convex (DC) optimization problem. We show that both problems are equivalent by proving that the penalty parameter is large enough. Then, to overcome the difficulty caused by the nonsmoothness and the simplex constraint of the model, we develop a proximal subgradient algorithm (PSGA) to solve the DC problem and apply the alternating direction of multipliers (ADMM) to compute the proximity operator of the corresponding function. Furthermore, we establish the global convergence of the entire sequence generated by PSGA through showing the surrogate function satisfies the Kurdyka-Łojasiewicz (KL) property. In addition, by showing the KL exponent of the surrogate function is $1/2$, we establish the R-linear convergence rate of PSGA for any arbitrary initiaal point. Finally, we compare our proposed algorithm with other state-of-the-art strategies on four benchmark real-market data sets, with the numerical results showing that the proposed algorithm achieves lower risk while keeping higher return than classical TCO models.

We study layered models, including feedforward networks, ResNets, and transformers, by limiting each layer to a width of $d = 3$, i.e., $\mathbb{R}^3$ as representation space. This allows us to track how a neural network changes low-dimensional topological invariants through its layers. Just about any topological structure may be simplified or even trivialized by simply increasing dimension; e.g., any knot is equivalent to an unknot in $\mathbb{R}^4$. By restricting to $\mathbb{R}^3$, we not only isolate the effects of activation and depth from that of width, we work in a space that lends itself to easy visualization. We focus on linking number here, deferring other invariants like link groups, Milnor's $\bar{\mu}$-invariants, knot types, ambient cobordisms, to a sequel. We provide full proofs and empirical experiments to justify the following insights: When measured by their power to effect changes in linking numbers, the layer-skipping feature in ResNets is as powerful as the attention mechanism in transformers; both ResNets and transformers are strictly more powerful than feedforward neural networks with monotonic activations, which are in turn more powerful than invertible and flow-based models; but replacing monotonic activation with a nonmonotonic one elevates a feedforward network into the same expressivity class as ResNets and transformers. These results suggest that low-dimensional topology can be a useful tool to guide designs of AI architectures. We also generalize our results from $d = 3$ to arbitrary $d > 3$.

We study the role of batch size in stochastic conditional gradient methods under a $\mu$-Kurdyka–Łojasiewicz ($\mu$-KL) condition. Focusing on momentum-based stochastic Frank–Wolfe–type conditional gradient algorithms (e.g., Scion), we derive a new analysis that explicitly captures the interaction between stepsize, batch size, and stochastic noise. Our study reveals a regime-dependent behavior: increasing the batch size initially improves optimization accuracy, but beyond a critical threshold, the benefits saturate and can eventually degrade performance under a fixed token budget. Notably, the theory predicts the magnitude of the optimal stepsize and aligns well with empirical practices observed in large-scale training. Leveraging these insights, we derive principled guidelines for selecting the batch size and stepsize, and propose an adaptive strategy that increases batch size and sequence length during training while preserving convergence guarantees. Preliminary experiments are consistent with the theoretical predictions and illustrate the emergence of the predicted scaling regimes. Overall, our results provide a theoretical framework for understanding batch-size scaling in stochastic conditional gradient methods and offer guidance for designing efficient training schedules in large-scale optimization.

Designing heuristic algorithms for complex optimization problems is a time-consuming and expert-driven process. Recently, Automated Heuristic Design (AHD) using Large Language Models (LLMs) has shown significant promise for automating algorithm development. However, existing works mainly rely on programs to represent heuristics, which are inherently taskspecific and fail to generalize as effectively as established metaheuristics like tabu search or guided local search. To bridge this gap, we introduce Multi-Task Hierarchical Search (MTHS), an LLM-guided evolutionary method that co-designs general-purpose metaheuristics and task-specific programs. MTHS employs a hierarchical representation and adopts a two-level evolution framework to evolve task-agnostic metaheuristics and task-specific program implementations simultaneously across multiple heuristic design tasks. During this evolution, a knowledge transfer mechanism allows learning from elite programs designed for other tasks. We evaluated MTHS on distinct combinatorial optimization problems, where it outperforms both commonly-used heuristics and existing LLM-driven AHD approaches. Our results demonstrate that the hierarchical representations facilitate effective multi-task AHD, and the evolved metaheuristics exhibit strong generalization to related tasks. Code: https://github.com/FeiLiu36/MTHS.

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 moment-generating function of strongly convex costs, of interest even in centralized settings. Numerical experiments validate our theory.

Deep neural networks with repeated blocks, such as transformers and ResNets, often exhibit structured relationships across layers that emerge during training. Motivated by this observation, we introduce a general paradigm of *Depth-wise Gradient Augmentation*, in which the update applied to a layer may depend on the base optimizer updates computed for other layers. We study an instantiation of this idea, termed *Gradient Smoothing*, which couples optimizer updates across depth and admits a natural interpretation as a structured preconditioning method. Our framework operates directly on block-wise update vectors produced by arbitrary base optimizers (e.g., SGD, Adam, Muon), applying structured depth-wise smoothing operators such as local weighted averaging with minimal computational overhead. We evaluate Gradient Smoothing across a diverse set of architectures and training regimes, including language model pretraining, RL post-training of LLMs on reasoning tasks, diffusion modeling, and image classification with Vision Transformers. Across these settings, Gradient Smoothing consistently improves convergence and generalization performance without modifying model architectures or training objectives. We further show that smoothing promotes more structured representation evolution across depth, suggesting a connection between structured update coupling and the internal organization of learned representations. These results position Gradient Smoothing as a simple and broadly applicable approach for improving training in modern deep networks.

Large language models (LLMs) can generate syntactically valid optimization programs, yet often struggle to reliably choose an effective modeling strategy, leading to incorrect formulations and inefficient solver behavior. We propose **SAGE**, a strategy-aware framework that makes *Modeling Strategy* explicit in both data construction and post-training. SAGE builds a solver-verified multi-strategy dataset and trains a student model with supervised fine-tuning followed by Segment-Weighted GRPO using a composite reward over format compliance, correctness, and solver efficiency. Across eight benchmarks spanning synthetic and real-world settings, SAGE improves average pass@1 from 72.7 to 80.3 over the strongest open-source baseline. With multiple generations, SAGE discovers more distinct correct formulations and improves component-level diversity at pass@16 by 19-29%. At the largest scale, SAGE produces more compact constraint systems with 14.2% fewer constraints than the baseline, consistent with solver-efficient modeling. Overall, these results show that making *Modeling Strategy* explicit improves automated optimization modeling. The code and data are available at https://github.com/rachhhhing/SAGE.

We present improved bounds for estimating discrete probability distributions under the $\ell_{\infty}$ norm. These include minimax bounds in expectation and high-probability tail bounds. We resolve some of the open questions posed in Kontorovich and Painsky (JMLR, 2025) --- including a fully empirical version of the tightest risk bound they presented and identifying the form of the worst-case extremal distribution. Encouraging empirical results are reported as well.

This paper studies second-order methods for nonconvex-strongly-convex bilevel optimization. We propose a novel fully second-order bilevel approximation method (FSBA) that achieves an iteration complexity of $\tilde{\mathcal{O}}(\epsilon^{-1.5})$ for finding the $(\epsilon, \mathcal{O}(\sqrt{\epsilon}))$ second-order stationary point of the hyper-objective function. Our results demonstrate that second-order methods can achieve an accelerated convergence rate than first-order methods in bilevel optimization. To address the heavy computational cost associated with the second-order oracle, we introduce a lazy variant of FSBA, called LFSBA, which reuses second-order information across several iterations. We prove that LFSBA exhibits better computational complexity than FSBA by a factor of $\sqrt{d}$, where $d$ is the dimension of the problem. We also apply a similar idea to nonconvex strongly-concave minimax optimization and propose the lazy minimax cubic-regularized Newton (LMCN) method with better computational complexity compared to existing second-order methods.

End-to-end deep learning has achieved impressive results but often relies on large labeled datasets, exhibits limited generalization to unseen scenarios, and incurs substantial computational cost. Classical optimization methods, in contrast, are more data-efficient and lightweight but frequently suffer from slow convergence. Learned optimizers aim to bridge this gap, yet existing approaches have focused primarily on first-order methods, while learned second-order optimization has received much less attention. We introduce L-SR1, a learned second-order optimizer inspired by the classical Symmetric Rank-One (SR1) method. At its core, L-SR1 employs a Projection-Guided Secant Mechanism (PGSM) that generates positive semi-definite preconditioners and biases meta-training toward the quasi-Newton secant relation. Through controlled analytic benchmarks, we study stability, generalization across problem dimensions, and search direction quality, and further evaluate L-SR1 on Monocular Human Mesh Recovery (HMR), where it outperforms both classical and learned optimization-based baselines. With a compact model and no reliance on task-specific fine-tuning or annotated data, L-SR1 demonstrates strong generalization and can be integrated into a broad range of iterative optimization problems to accelerate convergence and reduce the required number of iterations.

Gated Linear Units (GLU) and their variants are widely adopted in modern open-source large language model architectures and consistently outperform their non-gated counterparts, yet the underlying reasons for this advantage remain unclear. In this work, we study GLU by analyzing two-layer networks in the neural tangent kernel (NTK) regime. Our analysis reveals that the GLU structure reshapes the NTK spectrum, leading to a smaller condition number and a more compact eigenvalue distribution. Building on this finding, we further analyze the resulting training dynamics and show how the reshaped spectrum leads to faster convergence of GLU models, including a characteristic loss-crossing phenomenon observed between GLU and non-GLU models. Finally, we empirically observe that GLU has limited impact in reducing the generalization gap on various models, including ViT and GPT-2, suggesting that its primary benefit lies in accelerating optimization rather than reducing the generalization gap. The code is available at: https://github.com/Zemdalk/GLU-NTK.

We give a very general and simple framework to incorporate predictions on requests for online covering problems in a rigorous and black-box manner. Our framework turns any online algorithm with competitive ratio $\rho(k, \cdot)$ depending on $k$, the number of arriving requests, into an algorithm with competitive ratio of $\rho(\eta, \cdot)$, where $\eta$ is the prediction error. With accurate enough prediction, the resulting competitive ratio breaks through the corresponding worst-case online lower bounds, and smoothly degrades as the prediction error grows. This framework directly applies to a wide range of well-studied online covering problems such as facility location, Steiner problems, set cover, parking permit, etc., and yields improved and novel bounds.