Papers

Policy-gradient methods are central to modern reinforcement learning, including LLM post-training. When they struggle, the usual suspects are exploration, credit assignment and action-sampling noise. Classification has none of them. A classifier is a policy whose expected reward, its expected accuracy, is the probability it assigns to the correct label, and because that label is known, the policy gradient is exact and smooth. Yet exact policy gradient loses to cross-entropy, even on expected accuracy. The exact gradient is myopic: it values an update only by what it buys now, but each update also sets where the next one starts, so an update's value depends on how much learning remains. Viewed this way, cross-entropy is patient accuracy, the total error an example would pay if its log-odds rose at unit speed forever, while exact policy gradient is the zero-horizon limit. Truncating this total at the learning that remains yields the horizon loss, a one-line change that moves from cross-entropy toward exact policy gradient as training runs out. In a simple allocation model, it provably escapes the trap that catches each endpoint. On MNIST and on ImageNet with ResNet-50, ResNet-101 and ViT-S/16, the horizon loss improves top-1 accuracy over cross-entropy at a flat learning rate, and the gain grows with label noise.

Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within $\mathcal{O}(1/\varepsilon^p)$ iterations to an $\varepsilon$-optimal policy, where the exponent $p$ depends on problem data. For single-period MDPs, such a policy is obtained within $\mathcal{O}(\log(1/\varepsilon))$ iterations.

We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon>0$ in nonconvex–strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge1$, F$^2$SA-$p$ achieves $\widetilde O(p\epsilon^{-4-2/p})$ (Chen et al., 2026), but necessity of the exponent $4+2/p$ was open. We prove matching upper and lower bounds $\Theta_p(\epsilon^{-4-2/p})$ under fixed nondegenerate regularity budgets, with constants allowed to depend on $p$. The lower bound holds for unrestricted randomized algorithms under a fixed sample budget, allows dimension to grow with accuracy, and preserves global unbiasedness and all prescribed lower-variable smoothness bounds, even with a scalar lower variable and exact upper gradients. We further characterize the minimax fixed-budget complexity under $L_j=M\Lambda^j(j!)^\beta$ for $j\ge3$: $Q_{p,\beta}^*(\epsilon)=\Theta\left(\epsilon^{-4}\left[\inf_{1\le r\le p,,r\in\mathbb N} r^\beta\epsilon^{-1/r}\right]^2\right)$, for $p\in\mathbb N\cup{\infty}$, with constants independent of $p$. At infinite order, this gives $\Theta(\epsilon^{-4})$ for $\beta=0$ and $\Theta(\epsilon^{-4}\log^2(1/\epsilon))$ for $\beta=1$. A gradient-difference method with weighted independent batches attains these bounds uniformly in order. Thus quantitative smoothness yields precise gains, whereas qualitative analyticity alone still permits $\Theta(\epsilon^{-6})$ complexity.

We characterize the optimal accuracy dependence for smooth nonconvex–strongly-convex bilevel optimization with stochastic first-order oracles. For globally unbiased fresh-gradient observations with bounded variance, we prove an $\Omega(\epsilon^{-6})$ lower bound matching the accuracy exponent of existing upper bounds. We consider globally Lipschitz gradients, a bounded upper gradient in the lower variable, and Lipschitz lower Hessian blocks, with target $\mathbb{E}|\nabla F(\widehat{x})|\le\epsilon$. Let $L$ be the common first-order scale, $\mu$ the lower strong-convexity modulus, $\rho$ the lower Hessian-variation budget, $\kappa=L/\mu$, and $\chi=1+\rho/\mu$. For $\rho\gtrsim\mu$, $\chi\lesssim\kappa$, sufficiently high accuracy, and sufficiently large dimension, we establish $\Omega\left(L\kappa^2\Delta\epsilon^{-2}+L^3\chi^2\kappa^8\sigma_g^2\Delta\epsilon^{-6}\right)$, where $\Delta$ is the initial gap budget and $\sigma_g^2$ is the lower-gradient variance budget. The bound holds over full Euclidean spaces against arbitrary randomized adaptive algorithms, even when every sample is the gradient of a scalar function. In the common-scale regime $\rho=\Theta(L)$, the leading stochastic term has condition-number dependence $\kappa^{10}$, compared with the achievable $\kappa^{11}$ dependence. The proof embeds a sequential hard objective into an exact lower response while preserving global regularity and finite gap. A multiscale decomposition limits the gradient signal carrying each new direction, yielding the required sample complexity. We complement this lower bound with a frozen-linear-tilt estimator whose bias is proportional to lower Hessian variation. Its analysis makes this structural dependence explicit and yields matching leading rates in the specified curvature-controlled and small-gap regimes.

This is a very first draft of a manuscript about existence of solutions of differential inclusions involving chattering.

Why are some dynamic lot-sizing problems polynomial? We address this question by introducing Grid Theory, a structural framework based on cumulative production and the additive structure of production bounds. For a general single-item dynamic lot-sizing model with lower and upper production bounds, there exists an optimal extreme solution in which, within each regeneration interval, all but at most one production quantity lie on a boundary value. This induces additive grids, and the Main Grid Theorem establishes that an optimal cumulative production trajectory can be restricted to these discrete sets. Although the resulting grids may be exponentially large, we introduce the notion of additive dimension to capture production-bound profiles whose boundary sums admit a low-dimensional representation. We show that bounded additive dimension yields a polynomially constructible grid envelope and a polynomial time grid-based dynamic programming algorithm. The framework extends to separable concave costs and establishes polynomial solvability of several families, including constant capacities, minimum order quantities, a fixed number of capacity levels, fixed-degree polynomial capacities, periodic capacities, and piecewise polynomial capacities. In particular, polynomiality may hold even when the number of distinct capacity values grows with the planning horizon. Grid Theory thus identifies additive structure, rather than the number of distinct resource values, as a sufficient mechanism for polynomial solvability.

Decision making under uncertainty requires balancing the value of additional information against the cost of delaying the decision until that information becomes available. This challenge is especially prevalent for embodied decisions such as those faced by animals moving between food sources and robots selecting navigation targets, where movement through space shapes both the quality of information and the cost of acting. We consider a version of this problem, where the decision is on choosing among rewards of uncertain value, and those rewards can only be attained through changing the decision maker's state sufficiently. Our focus is on interactions between reward learning and state evolution, restated as a deterministic optimal control problem with two terminal alternatives, one with a known reward and the other learned gradually through noisy observations. We demonstrate that delayed reward attainment is often optimal in a variety of systems, especially so when the alternatives are initially difficult to distinguish and the cost of waiting is relatively low. For a subset of problems, we also derive sufficient conditions that allow shortening the planning horizon a priori, guaranteeing that further observations would not affect the value function. Finally, when observation quality depends on the state, we show that it is often optimal for a controller to evolve the state strategically toward more informative sensing locations before making a decision, in line with the behavior broadly observed in biological and engineered systems.

We study gradient-type dynamics for weak stochastic control through the laws of controlled diffusions on path space. Although the objective is generally nonconvex in the drift, a uniformly convex running cost induces a strictly convex functional of the corresponding path law and hence a natural Bregman geometry. We construct the associated implicit proximal scheme and prove its well-posedness and convergence to a continuous-time mirror flow. When the mirror cost coincides with the running cost and the law-dependent potential is linear, the flow becomes affine in centered entropy coordinates. This yields a variational construction of the resulting Newton flow, uniform stability estimates, and exponential convergence to the optimizer. For a general uniformly convex mirror cost and a nonlinear convex potential of the law, we construct the natural-gradient flow globally in learning time using BMO estimates for quadratic BSDEs, and establish quantitative convergence and a first-order discretization error. We further analyze interacting finite-particle approximations, proving exponential convergence to the finite-particle optimum and an O(1/N) normalized discrepancy from the mean-field optimum. In the Markovian setting, reflection coupling yields uniform spatial regularity and exponential convergence of the feedback controls on Rd, including for nonquadratic state-dependent Hamiltonians.

Inverse game theory seeks to learn agents' unknown objectives from observed equilibrium behavior. Existing residual-based approaches can lead to non-convex problems and need not ensure strong monotonicity of the learned game, limiting reliable equilibrium prediction. We develop a tractable convex framework for learning static and dynamic non-cooperative games using first-order and Nikaido-Isoda (NI) loss. Specialized operator parameterizations, including a Helmholtz–Hodge decomposition in a reproducing kernel Hilbert space (RKHS), enforce strong monotonicity for quadratic, nonparametric, non-quadratic, and linear-quadratic dynamic games. We establish finite-sample out-of-sample prediction guarantees, using Rademacher complexity to match existing bounds for the non-quadratic setting. For noisy sequential data, we develop a robust receding-horizon learning scheme whose adaptive regularization admits a maximum a posteriori (MAP) interpretation and is computed using randomized trace estimation. Numerical experiments, including a stylized autonomous-vehicle collision-avoidance application, demonstrate predictive accuracy and robustness to measurement noise.

We study a constrained basis-selection problem for an ordered block matrix $B=[ B_1\mid\cdots\mid B_n ].$ The successive tail matrices determine a nested family of column spaces, and we consider bases of representatives which are compatible with this induced flag. Our main linear-algebraic result shows that, among bases of representatives, compatibility with the entire flag is characterized by the intrinsic block quotas $r_k=w_k-w_{k+1}$, where $w_k$ is the rank of the $k$-th tail matrix. We then show that the same structure arises naturally in finite-horizon linear control. For the reachability matrix $[A^{N-1}G\mid \cdots\mid G]$, requiring every actuator to be used exactly once turns an actuator schedule into a representative system. Preservation of the complete reachability profile is then equivalent to compatibility with the tail-space flag. This correspondence leads to an exact depth-first search with a future-rank pruning criterion. For an explicit structured family and a fixed search ordering, the baseline search visits $3\cdot2^m+m-2$ nodes before the first solution, whereas future-rank pruning reduces this number to $3m+1$. Exact-arithmetic experiments reproduce these formulas for all tested instances.

We study the allocation of a force of a fixed size across independent battlefields against a known distribution of opposing forces. Formulating battlefield outcomes through loss and survival functions allows us to establish allocation results without assuming a specific system of combat equations. For convex enemy loss functions, an optimal allocation exists with at most one partially saturated battlefield. We prove NP-hardness for every prescribed family of strictly convex, strictly increasing loss functions satisfying an endpoint normalization, and give an exact pseudopolynomial algorithm for the special case when the total force size and saturation thresholds are integers. We also derive allocation rules for maximizing successful engagements, maximizing own survivors, and maximizing the ratio of enemy losses to own losses. Applications include a power-law family containing the classical Lanchester, guerrilla, and mixed combat models, as well as models with implicitly defined outcomes.

Low-rank approximation can require additional matrix–vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across \(W\) paths, a concentration bound exploiting shared residual energy yields a \(\sqrt{\log(W+1)}\) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders \(N^{1/3}\) and \(N^{2/3}\) for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/

Existing convergence analyses of Muon either assume exact orthogonalization or analyze classical Newton–Schulz polynomials, and guarantee only stationarity, so it is unresolved what Muon's five tuned Newton–Schulz steps preserve and whether that suffices to reach a prescribed neural-network training loss. We establish a finite-time training guarantee that accounts for both momentum accumulation before orthogonalization and the tuned finite-step update. For full-batch training of a sufficiently wide two-layer ReLU network with fixed random output weights and a positive-definite limiting neural tangent kernel, we prove that Muon reaches any target empirical squared loss $\varepsilon>0$ with high probability over initialization. For every momentum parameter $\mu\in[0,1)$, a target-dependent constant learning rate proportional to $(1-\mu)\sqrt{\varepsilon}$ yields a hitting-time bound of $O((1-\mu)^{-1}\varepsilon^{-1/2})$, with other problem parameters fixed. The sufficient width is independent of both target accuracy and momentum. The analysis shows that the tuned Newton–Schulz map preserves alignment with the momentum buffer while bounding the update's spectral norm. Control of gradient variation near initialization transfers this alignment to the current gradient, ensuring descent until the target is reached without requiring exact orthogonalization. Numerical experiments support these mechanisms at widths below the sufficient theoretical threshold: gradient-update alignment remains above the analytical reference, and all 30 runs across six widths and five student initializations on a fixed teacher-student dataset reach the target loss while maintaining kernel positivity.

We derive the sub-Riemannian geodesics of the affine-additive group using the Pontryagin Maximum Principle (PMP) and compute the associated cut times. We then proceed to construct the Carnot-Carathéodory sphere of the affine-additive group as well as the flask surface; the latter is the analogue of the Pansu sphere (bubble set) in the first Heisenberg group.

Contraction analysis of dynamical systems turns a global convergence problem into a local one. If the variational system is stable in a uniform sense, then all trajectories of the original system converge toward each other. This paper develops a stochastic analogue for continuous-time stochastic systems, where convergence is measured by Wasserstein distance between probability laws. The key step is to employ mean-square differentiation to construct stochastic variational dynamics. Its uniform $L_2$ stability can then be integrated along curves of initial conditions, yielding Wasserstein contraction of the associated probability laws. This yields criteria formulated in terms of differential Lyapunov functions, and on manifolds, it leads to intrinsic Riemannian formulations. A distinctive feature of the stochastic setting is that the coupling of the noises becomes a design freedom. To exploit this freedom, we introduce an orthogonal differential coupling that extends the framework beyond synchronous coupling. The resulting criterion explicitly exposes how the curvature of the state space enters the contraction mechanism and, in the orthonormal-frame case, recovers the classical Ricci-curvature structure. Finally, we apply the framework to stochastic control on a compact manifold. By introducing stochastic control input, we overcome a deterministic obstruction to global stabilization. That is, a system that cannot be globally stabilized through smooth time-invariant deterministic feedback is rendered globally contracting in $W_2$, and its steady state distribution can be made arbitrarily concentrated around a prescribed target equilibrium.

We develop a Newton–Kleinman iteration for linear-quadratic optimal control of infinite-dimensional systems with possibly unbounded control and observation operators. In this setting, the classical algebraic Riccati equation need not be meaningful and therefore cannot serve as the basis of the iteration. We instead linearize a Lur'e identity formulated directly on the system-node domain. Starting from any stabilizing feedback, the resulting iteration is well defined, preserves stability, and yields a monotonically decreasing sequence of cost operators. A resolvent-based normalization makes the construction applicable to unbounded control. Under finite-cost detectability and for a finite-dimensional input space, the iterates converge strongly to the optimal value operator, independently of the fixed normalization parameter. In finite dimensions, the natural zero-state normalization recovers exactly the classical Newton–Kleinman iteration. The formulation leads to a low-rank numerical realization based on shifted system solves and inversions on the input space. We illustrate the method on a linearized cylinder wake with boundary traction control and unbounded observation, using one Newton–Kleinman update per adaptively refined spatial mesh, and on a damped linear elasticity problem with boundary traction control and boundary displacement observation.

This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per $m$ iterations. Under this setting, we show a lower bound of $\Omega(m+ m^{1/7} \epsilon^{-2/7})$ on the number of total iterations to find an $\epsilon$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} \epsilon^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} \epsilon^{-2/7})$ and is tight up to logarithmic factors.

We give an exact counterexample to the eight-point angular-energy conjecture stated by Mouchet in 2005 and published in 2006. The conjecture specifies both a radical value for the global maximum and a square antiprism with unit-side horizontal squares separated by $h_0=\sqrt{1+2\sqrt{2}}/2$. We prove that the same family at the rational separation $489/500$ has a strictly larger angular sum. The proof reduces the sum of all $168$ angle cosines to a one-variable formula, factors its derivative, and certifies its sign using rational inequalities. We also characterize the unique maximizing separation within this family. All comparisons needed for the counterexample are exact. The result disproves the exact stated conjecture.

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining linear-relaxation solves with a local-search procedure designed for efficient batched execution on GPUs. In addition, instead of relying on a single heuristic for iterative variable fixing, we leverage GPU batching capabilities to generate and explore multiple subproblems in parallel. PaNGEA leverages GPU capabilities in two ways. First, on 283 MIPcc26 and MIPLIB instances, implementing a single-node primal heuristic on the GPU reduces the average gap integral by 8-18% relative to its CPU counterpart. Second, generating and exploring multiple nodes in parallel further reduces the average gap integral by 12-19%.

Chance-constrained programs (CCPs) optimize decisions under uncertainty by limiting the probability of constraint violation. Despite advances in traditional and learning-based approaches, optimizing non-convex or non-smooth objectives and adapting to different objectives under fixed chance constraints remain challenging. In this paper, we propose a Derivative-free Diffusion-based framework that Disentangles constraint modeling from objective optimization, termed \textbf{D$^3$Opt}. We learn the chance-feasible structure once, independently of any particular objective, by training a risk-conditioned diffusion model solely on constraint-filtered decisions and freezing it as a reusable prior for post-specified objectives. At inference time, we propose an annealed, particle-based Feynman–Kac correction along the frozen reverse diffusion process to optimize post-specified objectives using only function evaluations. This enables derivative-free optimization of non-convex and non-smooth objectives without objective-specific retraining. We prove that the correction preserves feasibility when this property holds for the frozen prior, and derive an optimization-error bound separating learned-prior coverage, finite-particle approximation, and finite-temperature effects. Experiments on linear Gaussian CCPs, objective-transfer tasks, and chance-constrained economic dispatch demonstrate effective optimization across smooth and non-smooth objectives, including non-convex cases, and objective generalization under fixed chance constraints without retraining.

We study a forward-backward McKean-Vlasov system with jumps and one-way coupling: the forward equation is independent of the backward variables, whereas the BSDE depends on the forward state and its law. A source generated by a maximal monotone operator is evaluated along the forward state and then accumulated in the backward equation. The operator is the subdifferential of a convex potential evaluated at the state translated by a function of the control, plus a term depending on the law of the state, so the control shifts the discontinuity interface of its minimal-norm selection. We establish modelwise well-posedness and strong stability, with estimates uniform over the model family. We then study the Yosida approximation: strong convergence, Minty-type strong-weak closedness when the state, its law, and the control (hence the moving interface) vary, and uniform convergence under an integrability condition. For an asymmetric loss-aversion prototype, a quantitative occupation estimate for a layer around the interface yields an explicit Yosida convergence rate. When the continuous martingale part is nondegenerate and the interface moves absolutely continuously, the occupation time is linear in the layer width. The same rate controls the backward components and the cumulative source.

A nonfatal propulsion fault can invalidate the nominal ascent trajectory while leaving sufficient vehicle capability to reach the original orbit or a degraded target. Deterministic replanning can restore nominal feasibility, but residual uncertainty in the identified propulsion capability may still lead to path-constraint violations and terminal injection dispersion. This paper develops a fast chance-constrained stochastic ascent trajectory replanner that explicitly accounts for persistent propulsion uncertainty. The uncertainty model combines persistent random uncertainties shared across the prediction horizon with interval-wise independent disturbances. For a fixed nominal trajectory, system level synthesis is used to parameterize the closed-loop responses. A Cholesky-based transformation of the system responses converts the resulting cross-time correlated feedback design problem into column-wise affine recursions that share a common Riccati recursion. A task-oriented terminal weight is further derived from the minimum-energy post-injection orbital correction in phase-free modified equinoctial elements, thereby relating terminal covariance shaping directly to correction demand. The stochastic replanning problem is solved by alternating deterministic trajectory replanning and feedback controller design, with covariance-based chance-constraint backoffs coupling the two updates. Nonlinear Monte Carlo simulations demonstrate reduced equivalent correction demand, effective chance-constraint satisfaction, and fast online replanning over a range of uncertainty levels and fault conditions.

Direct approaches to discrete parabolic Carleman estimates often rely on weighted identities tailored to the discrete operator. We prove an abstract transfer theorem that derives such estimates for fully discrete backward Euler schemes with conforming spatial reconstructions from a continuous Carleman inequality together with suitable weighted approximation and compatibility properties. For a class of time-independent positive self-adjoint operators, the key construction assigns to each discrete state a shifted continuous auxiliary problem whose discrete solution is exactly the prescribed state. Weighted space-time error estimates, uniform over the full discrete load space, then transfer the inequality while preserving the residual and observation terms of the original scheme. This separates the PDE-specific Carleman analysis from the numerical verification required for each discretization. We verify the hypotheses for the heat equation discretized by consistent-mass $P_1$ finite elements on locally graded meshes in two and three dimensions and by standard Cartesian finite differences in any fixed dimension. For the heat equation, the transferred estimate is valid for Carleman parameters up to the scale $\min\{h^{-4/5},(\delta t)^{-2/5}\}$. For bounded real-valued space-time potentials, the resulting estimates yield relaxed observability and approximate null controls with uniformly bounded cost and exponentially small terminal errors under independent spatial and temporal refinement; weak accumulation points of the reconstructed controls are continuous null controls.

The proximal point algorithm (PPA) stands as a fundamental approach for solving monotone inclusion problems. Notably, several key convex optimization algorithms have been proven to be specific instances of PPA. Given the importance of the PPA, there has been growing interest in developing its accelerated variants. However, for some specific cases, the PPA converges faster than the accelerated PPAs. In this paper, we mainly study an adaptive version of symplectic accelerated PPA, called adaptive symplectic proximal point algorithm (ASPPA). We first prove that the convergence rate of ASPPA with respect to the square norm term is $O(1/k^2)$, which is the same as the convergence rate of some accelerated PPAs. Also, we show that ASPPA exists exponential convergence rate when solving strongly monotone inclusion problem. Our numerical experiments indicate that the performance of ASPPA is very good.

Finite-state interval Markov-chain (IMC) abstractions provide sound verification and performance bounds for continuous-state stochastic systems by enclosing cell-to-cell transition probabilities and costs in intervals. Finite-state Markovian abstractions are generally lossy, as state aggregation often destroys the Markov property. Recently, memory-dependent Markov-chain (MC) abstractions of stochastic systems have been developed to mitigate this by recording recently visited cells. In this paper, we develop the memory-dependent extension of IMC abstractions. Building on the insight that memory narrows the family of state distributions that could occur inside the current cell, we prove that memory tightens the local intervals, at the price of a larger abstraction. We also formulate no-memory IMC abstractions, tightening classic IMC abstraction intervals without enlarging the state space. To characterize spatial refinement relative to memory, we derive two cost-guarantee tightness upper bounds. The bounds depend, respectively, on cell size, and on the worst-case remaining distributional ambiguity after filtering over the remembered past. We then specialize our result to linear-Gaussian systems, for which we derive a closed-form upper bound on this ambiguity. Numerical examples show that the memory-dependent and no-memory constructions can produce tighter expected-cost intervals than comparable partition refined models.

Consensus-based optimization (CBO) is a robust and flexible zero-order, multi-particle class of methods devised to provide provable solutions to high-dimensional global optimization problems, including truly nonconvex and/or nonsmooth cases. The algorithmic framework is grounded in a principled trade-off between stochastic exploration of the search space and deterministic contraction toward a consensus point. This thesis is concerned with three recently established variants of CBO. The $\delta$-CBO method is similar to the classic CBO method, with the difference that the diffusion function is constant. The consensus freezing (CF) scheme can be understood as a piecewise CBO method. The overall time horizon is divided into intervals in which the consensus point is fixed. The consensus hopping (CH) scheme can be understood as a deterministic iterative scheme that jumps at each iteration to a Gaussian distribution centered at the consensus point of the previous distribution. The central contribution of this thesis is the rigorous derivation of propagation of chaos results for all three schemes. For each variant, we establish that the empirical measure of the interacting particle system converges, as the number of particles $N$ approaches infinity, to the solution of the corresponding mean-field equation. Two regimes are treated: first, on a high-probability set on which the empirical measures are uniformly bounded; second, in the unrestricted setting, where moment bounds and a careful treatment of the inter-particle dependence yield convergence without imposing conditioning on favorable events. The propagation of chaos estimates are derived by the coupling method. Together, these results provide quantitative propagation of chaos estimates for all three CBO variants and establish that the particle systems faithfully approximate the idealized mean-field dynamics in the large-particle limit.

The filtering problem asks to estimate a signal process, the initial state of which is unknown, given its partial and noisy observations. From a probabilistic perspective, the best estimate at each time is the optimal filter, which is the conditional law of the signal given all observations up to the time. The problem of asymptotic stability of the optimal filter, which asks whether the filter initialized with the incorrect initial law converges to the correctly initialized filter, is of fundamental practical and theoretical importance. This paper studies the quantitative asymptotic stability of the optimal filter for signal-observation models with linear drift and additive Brownian noise. When the initial law is additionally assumed to be Gaussian, the optimal filter reduces to the celebrated Kalman-Bucy filter, for which the detectability condition on the signal and observation matrices is the sharp condition ensuring asymptotic stability. In the linear setting where the detectability condition holds but the initial law need not be Gaussian, we make the following contributions by studying the Zakai equation satisfied by the unnormalized filter. First, we study the asymptotic behavior of the deterministic part of the Zakai equation in the general case with nonlinear drift, and place the detectability condition in this context. Second, in the case of linear drift, we characterize the solution of the Zakai equation (hence the optimal filter) by a gauge transformation that separates the finite-dimensional stochastic dynamics from the infinite-dimensional deterministic dynamics. Third, we use this representation to establish asymptotic exponential filter stability in the $\chi^p$-divergence (with respect to a reference optimal filter), the total variation norm, and the $2$-Wasserstein distance.

Dynamic programming for nonstandard infinite-horizon criteria requires more than finite stream values: one-step control substitutions must remain evaluable, and continuation information must propagate recursively. For expected stage-reward streams, we separate domain admissibility, finite-dimensional continuous autonomous realizability, scalar sufficiency, and contextual order consistency. For absolutely summable weighted criteria, we prove that the minimum Euclidean dimension of an exact continuous autonomous continuation state equals the temporal Hankel rank. Thus finite Hankel rank exactly characterizes when temporal nonstationarity can be replaced by finite endogenous state augmentation; the lower bound applies even to nonlinear continuous encoders and already holds in a one-state MDP. For literal Candelpergher Ramanujan summation, the same common-continuation test fails earlier: changing only the current action can leave the evaluation domain. Abel summation provides a contrasting prefix-closed benchmark.

The Beardwood-Halton-Hammersley theorem characterizes the asymptotic length of the optimal Euclidean traveling salesman tour through independent and uniformly distributed random points $X_1,\ldots,X_n$ in the unit square. It states that there exists a universal constant $\beta$ such that the length of the shortest tour is asymptotic to $\beta \sqrt{n}$ almost surely. The best bounds established to date are $0.6277\leq \beta \leq 0.90367$. In this paper, we improve these bounds to $0.6421\leq\beta\leq0.8810$. Using importance sampling, we further show that $0.6536\leq \beta\leq 0.8749$ holds with probability at least $1-2\times 10^{-4}$. Here the probability is taken with respect to the randomness of the sampling procedure.

The Muon optimizer applies spectral orthogonalization to matrix-valued updates and has shown strong performance in large-scale neural network training, yet the mechanisms of this transformation in feature learning remain poorly understood. In this work, we investigate this question through a tractable factual-recall model, where a fact maps each subject-relation pair to an answer, and a linear transformer learns the subject- and relation-dependent information required to recover this mapping. The transformer is optimized with gradient flow (GF), spectral GF, or Sign GF, which are continuous-time limits of gradient descent, Muon, and Adam, respectively. Prior studies (Nichani et al., 2025) have shown that when the number of subjects exceeds the number of relations, GF learns relation-dependent information before subject-dependent information, producing a feature-separation phase during training. We characterize this separation with the learning times when the subject- and relation-dependent components of the prediction reach a target accuracy. With $S$ subjects and $R$ relations, GF has a learning-time ratio of $\widetilde{\Theta}(\sqrt{S/R})$, whereas Spectral GF reduces this ratio to $\widetilde{\Theta}(1)$. In addition, for fixed $S$ and $R$, the subject- and relation-dependent errors decay as $1/(T\log T)$ in training time $T$ under GF, but as $\exp(-\mathrm{poly}(T))$ under spectral GF. Finally, we show that GF and spectral GF are equivariant under orthogonal transformations of the token embeddings, whereas Sign GF is not: Different orthonormal embeddings can potentially produce no feature separation, a large feature-separation phase, or even a reversed learning order. These results provide a mechanistic view of how spectral orthogonalization can fundamentally reshape feature-learning dynamics.