Can a Watershed transform, the classical tool of morphological segmentation, be placed at the end of a deep network and trained through? The Power Watershed (PW) is the limit of the seeded Random Walker (RW) as p grows to infinity with edge weights raised to the power p. At every finite p the RW solves a sparse positive-definite linear system and is exactly differentiable with respect to the edge weights and the unaries through one adjoint solve; its multi-label form costs one right-hand side per label, and its limit is the PW. We study this family as the last layer of a segmentation network, the watershed layer (WS layer). A conditioning study measures how the solve, the gradient and the distance to the limit evolve with p, and the implicit gradient is checked against unrolling. On synthetic data with correct edge costs the WS layer transforms a soft prediction into an exact boundary. On nuclei segmentation (PanNuke), a binary WS layer is level with a thresholded U-Net. With the instances as labels, the WS layer turns the U-Net into an instance segmenter whose number of labels is set per image by the markers rather than by the output layout, and the network is trained through that partition: instance F1 score rises from 0.656 to 0.795 over a U-Net with connected components, level with the same network followed by a tuned marker watershed. At the training temperature the partition is a watershed of the learned costs, and the finite temperature lets the solve hedge, discounting weak markers and sharing contested pixels. The hedging puts the WS layer 0.015--0.020 F1 ahead of the baseline when trained on a tenth of the data, at the price of having to deploy the finite-p solve rather than its exact limit at inference. Code and the full experimental record are released.
Boao Kong, Xu Huang, Yuqi Xu, Yixuan Liang, Bin Wang, Kun Yuan
Pipeline-parallel distributed optimization is essential for large-scale machine learning but is challenged by significant communication overhead from transmitting high-dimensional activations and gradients between workers. Existing approaches often depend on impractical unbiased gradient assumptions or incur sample-size memory overhead. This paper introduces Clapping, a Communication compression algorithm with LAzy samPling for Pipeline-parallel learnING. Clapping adopts a lazy sampling strategy that reuses data samples across steps, breaking sample-wise memory barrier and supporting convergence in few-epoch or online regimes. Clapping comprises two variants including Clapping-FC and Clapping-FU, both of which achieve convergence without unbiased assumption for compressed gradient, effectively addressing compression error propagation in multi-worker settings. Numerical experiments validate the performance of Clapping across different tasks.
Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when $γ=1$. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.
Underdamped Langevin dynamics (ULD) is a widely-used sampler for Gibbs distributions $π\propto e^{-V}$, and is often empirically effective in high dimensions. However, existing non-asymptotic convergence guarantees for discretized ULD typically scale polynomially with the ambient dimension $d$, leading to vacuous bounds when $d$ is large. The main known dimension-free result concerns the randomized midpoint discretization in Wasserstein-2 distance (Liu et al.,2023), while dimension-independent guarantees for ULD discretizations in KL divergence have remained open. We close this gap by proving the first dimension-free KL divergence bounds for discretized ULD. Our analysis refines the KL local error framework (Altschuler et al., 2025) to a dimension-free setting and yields bounds that depend on $\mathrm{tr}(\mathbf{H})$, where $\mathbf{H}$ upper bounds the Hessian of $V$, rather than on $d$. As a consequence, we obtain improved iteration complexity for underdamped Langevin Monte Carlo relative to overdamped Langevin methods in regimes where $\mathrm{tr}(\mathbf{H})\ll d$.
Gromov--Wasserstein optimal transport (GWOT) aligns metric measure spaces by matching their within-domain relational structures, but large-scale GWOT remains challenging because its objective is nonconvex and projection onto the transport polytope is often solved only approximately in practice. This leads to a gap between practical projected-gradient implementations and convergence theory, which typically assumes exact projections. For squared-loss GWOT, we propose an inexact projected-gradient framework with a verifiable feasibility-residual-based inexact condition for the projection subproblem. This condition is directly computable and avoids unknown quantities such as the exact projection point. Under this implementable condition, we prove subsequential convergence to stationary points and, with a mild tolerance-decay condition, convergence of the whole sequence. The resulting method retains the simplicity and sparsity of projected-gradient schemes while providing rigorous convergence guarantees, turning projected-gradient methods into a principled and scalable approach for GWOT with provable reliability.
Fast inference and strict constraint satisfaction are essential for learning-based decision-making. Existing methods often rely on constraint-specific projections or feasible-set parameterizations, while iterative repair can be costly. We introduce Convex-SKM-Net, a convex constraint-satisfaction layer that forms linearization halfspaces from residual and (sub)gradient oracles without constraint-specific inequality projectors. It applies fixed-depth dual projected-gradient descent (dual PGD) to minimum-displacement block problems using GPU-friendly matrix operations. We jointly learn the predictor and a positive-definite mobility, adapting the correction geometry to improve objective quality. We prove convergence of the outer iterates at fixed dual depth and linear convergence in distance under Slater's condition and bounded subgradients. All our test outputs on three second-order-cone model-predictive control (SOC-MPC) horizons and six power-system convex relaxations satisfy a $10^{-3}$ feasibility tolerance. Comparisons with the latest constraint-satisfaction methods show inference speedups of up to $144.3\times$ on SOC-MPC and $7.7\times$ on a convex quadratically constrained quadratic programming (QCQP) benchmark with joint training. On QCQP, the mean objective gap is $0.012\%$, with full test feasibility at $10^{-4}$. Learning mobility reduces the five-seed affine-task mean gap by $22.4\%$ and improves gaps in matched power-system comparisons.
Benders decomposition and column generation solve large optimization problems by passing cuts, columns, and dual values between a master problem and subproblems, and are hard to implement correctly. Large language models now automate parts of algorithm design, which points toward agents that build decomposition solvers for new problems. As a first step toward such agents, we study how well current coding agents design and implement these two algorithms, and how they fail. We introduce DecompGym, 81 instances from nine problem families (five Benders, four column generation), in which an agent writes a solver for a prescribed method. Each solver must meet three criteria: execution within a 60-second time limit; numerical feasibility together with a method audit, in which an LLM judge reads the solver's code; and an objective within 1% of the stored optimal objective. We evaluate 12 GPT, Claude, and Gemini models running in coding-agent tools. Over up to ten attempts, we compare independent regeneration with reflection, which first diagnoses the failure. On the first attempt, two models solve every instance and seven solve more than 90%. Most Benders failures (48 of 62) are missing or suboptimal solutions. The most common column-generation failure is a method-audit rejection. Output checks alone would accept 93 of the 108 attempts that fail the method audit. The most common rejection, an optimalif, occurs 96 times, 92 of them in one model.Reflection turns 66% of retries into successes, compared with 39% for regeneration, and it repairs method-audit failures, for which the judge names the defecective gaps. Agents for decomposition therefore need checks on how a solver reaches its answer and feedback that locates the error. The benchmark is available at https://github.com/SIKAI-C/DecompGym.
We continue the study of minimum-time escape of an omnidirectional evader from the forward conic field of view of a Reeds--Shepp pursuer, now for a faster evader, and solve the game for every speed ratio $ν>1$ and every half-angle $0<α<π/2$: the escape time is characterized by explicit characteristics and the selection of roots of a scalar equation, and it is the value of the game in nonanticipative strategies at every state. Above the end $E$ of the evader's dispersal line on the front axis, the evader chases the reversing pursuer along a universal line fed by tributaries. The characteristic from the boundary of the usable part is an involute of a circle of radius $ν$ ending at a cusp, and two explicit thresholds decide whether it reaches the axis before the cusp and whether the jump of the escape time across it ends before the cusp or runs to it; in the latter case primaries fold back next to the barrier. The pursuer's optimal strategy is the relay of the slower case. The evader follows the tributaries and switches once to a primary, or commits in advance to a heading certified by the scalar equation of the primaries. Level-set and semi-Lagrangian computations are compared with the value.
Liang Wu, Honghui Zheng, Bo Yang, Xu Yang, Yilin Mo, Ján Drgoňa
Solving large-scale multiparametric quadratic programs (mpQPs) in real time often requires thousands of iterative optimization updates, creating a major computational bottleneck in model predictive control and learning-enabled systems. This paper proposes TQPNet, a self-supervised neural compression framework that learns to compress long ADMM optimization trajectories into a compact neural warm start followed by a few refinement iterations. We derive a low-dimensional ADMM scheme operating on the primal-dual variables $(x,β)$ and show that its iteration admits an equivalent ReLU-layer representation, termed ADMM(ReLU). Building on this insight, TQPNet combines a multilayer perceptron with ReLU activations (MLP(ReLU)) and a small number of unrolled ADMM(ReLU) refinement layers. The network is trained offline using an optimality-condition-informed residual loss, eliminating the need for solver-generated labels. The proposed residual-based framework enables both self-supervised training and online solution certification through adaptive ADMM(ReLU) refinement. Experiments on large-scale mpQPs and real-time MPC applications demonstrate that TQPNet achieves high accuracy, strong generalization, and substantially faster inference than conventional optimization-based methods.
Ship-to-home fulfillment requires a retailer to select a fulfillment location and carrier before the delivery time is known. These decisions often rely on static transit-time estimates, which cannot represent how delivery-time uncertainty varies across orders and fulfillment options. This paper constructs conformal predictive distributions (CPDs) using Conformal Predictive Systems (CPS) for regression and the cross Venn-Abers predictor (CVAP) for multiclass classification, and uses them in a contextual optimization model for fulfillment decisions. The model is solved by contextual sample-average approximation (C-SAA). The regret of each fulfillment decision, its expected cost above that of the best decision, is bounded by forecast error, scenario-evaluation error, and the candidate-generation gap. The forecast term depends on how well calibration residuals or class probabilities represent the current order. On more than five million proprietary order records, CVAP raises exact-day accuracy from 49.5% for the rule-based estimate to 64.1%. Paired with a decision rule that selects a quantile weighting late errors more heavily, the split CPS (SCPS) gives a point estimate that raises late-delivery detection from 3.8% to 79.4%. Residual-based CPS distributions also meet or slightly exceed nominal interval-coverage targets. In decision experiments with a JD.com simulator over six test dates, C-SAA with CVAP lowers mean total cost by 7.1% and C-SAA with the Mondrian CPS (MCPS) lowers it by 6.7%, relative to C-SAA with the original nonconformal forecast. Both cut the late-delivery rate from 5.7% to below 4.0%.
We present GPU-accelerated Bregman Douglas--Rachford splitting algorithm (BDRS) for discrete optimal transport problem in three input formats: an explicit cost matrix, a point cloud with a ground cost between them, and a separable cost on a regular grid. For each input format, we propose hardware-aware designs of mathematically equivalent representations for the BDRS iterations to enhance numerical stability and empirical runtime. We benchmark the three proposed implementations against eight GPU baseline solvers from the literature on the same device. We demonstrate that our implementations of BDRS achieve state-of-the-art performance on their respective input formats. To the best of our knowledge, this is the first cross-solver study of GPU DOT solvers with a unified measure of optimality.
Rounded capacity cuts (RCCs) are among the most effective cuts for capacitated vehicle-routing relaxations, but exact separation is computationally prohibitive at scale. Existing heuristic and neural separators can be fast, but often fail to produce sufficiently many effective cuts within practical separation budgets. We introduce SAG-Sep, a separator that scores node membership in RCC-inducing subsets across vehicle-count levels from a fractional LP solution in a single encoder forward pass, avoiding the iterative predict-and-coarsen inference used by NeuralSEP-style separators. SAG-Sep encodes the LP solution as a Sparse Augmented Graph (SAG), adding flow-informed multi-hop edges that expose long-range routing structure without densifying attention. Beyond LP-aware sparse encoding, we observe that high-value exact RCCs are typically nested, organizing into onion-like subset families, and SAG-Sep's node scores track subset nesting depth. This motivates Onion-Sweep (OS), a training-free decoder that ranks customers by their scores, evaluates the RCC violation of every prefix of the ranking in one vectorized pass, and emits the most violated prefix of each replica together with a cross-replica family of nested proposals, converting independent node scores into structurally coordinated RCC candidates without a tuned threshold or probing band. On the NeuralSEP benchmark with N=1000 customer instances, SAG-Sep with OS reduces the average root gap by 17.7% relative to the strongest NeuralSEP baseline, while the single-pass SAG-Sep separator achieves a roughly 30-fold per-iteration neural separation speedup. Our findings suggest that LP-aware sparse encoding and the nested structure of high-value cuts are structural patterns worth leveraging in neural separation more broadly.
We study online Wasserstein distributionally robust optimization (DRO), where the ambiguity set is a Wasserstein ball centered at the empirical distribution and evolves with each observation. We formulate each round as a zero-sum game and develop an online distributional best-response algorithm that requires only one projected subgradient step per iteration. Combining regret analysis with measure concentration, we establish explicit, instance-dependent, and high-probability convergence rates to the optimal offline DRO value.
Weight decay and explicit weight-norm constraints improve optimizer performance in language model pretraining, yet a unified understanding of why such control helps and how much is needed remains incomplete. We analyze norm control in Muon over the entire training trajectory using the \emph{accumulated effective learning rate}, $C_T=\sum_{t<T}η_t/\|W_t\|_F$, where $η_t$ is the nominal learning rate and $η_t/\|W_t\|_F$ is the effective learning rate relative to the weight norm. For bounded update directions, accumulation over any training interval bounds relative weight displacement. We show that vanilla Muon can accumulate only logarithmically, potentially limiting exploration and helping explain its slower empirical progress, whereas MuonW and MuonH guarantee at least linear accumulation under the stated conditions. Going beyond bounded-norm control, we show that sufficiently slow norm growth guarantees faster accumulation than the logarithmic worst case, opening up less restrictive optimizer designs. Based on this insight, we propose MuonGS, which uses Gram--Schmidt (GS) projection to remove the radial component of each Muon update without fixing the weight norm. With bounded update directions and a constant nominal learning rate, we prove that the weight norm grows at most proportionally to $\sqrt{t}$ after $t$ steps. Consequently, MuonGS guarantees $C_T=Ω(\sqrt{T})$, with accumulation sustained even in later training. Further, for smooth scale-invariant objectives we establish its $O(T^{-1/2})$ stationarity guarantee. In pretraining experiments with 160M- and 400M-parameter dense models as well as a 135M active- and 1B total- parameter MoE model, MuonGS achieves lower validation perplexity than MuonH at long training horizons. In particular, for the dense model it achieves an estimated token-equivalent speedup up to about $15\%$ at matched validation loss to MuonH.
Ali Ghasemzadeh, Erfan Babakhani, Armin Khosravi, Pariya Ghasemzadeh, Yong-Hong Kuo, Seyedali Mirjalili, Amir H. Gandomi
Many real-world optimization tasks are governed not only by what should be optimized, but also by what is allowed: a solution must first satisfy physical, operational, safety, budgetary, or structural requirements before its objective value becomes meaningful. Yet benchmark design for constrained continuous optimization often treats these restrictions as fixed properties of predefined test instances. Existing generators and benchmark suites provide essential foundations for reproducible comparison, but they either focus primarily on configurable objective landscapes or expose constraint properties within limited, predefined regimes, making it difficult to ask targeted questions about constraint-induced difficulty: whether an optimizer struggles because feasible regions are small, boundaries are restrictive, variables are tightly coupled, or constraint information is poorly scaled. We introduce GNBG-C, a Generalized Numerical Benchmark Generator for Constrained Continuous Optimization. The central idea is to treat the feasible region itself as a configurable object rather than as an inseparable attachment to a fixed test function. By generating controlled constraint regimes around the known GNBG global minimizer, the generator enables systematic studies in which feasibility pressure can be varied while preserving that point as a global minimizer of the constrained problem. This allows researchers to examine how optimizers discover feasibility, handle constraint pressure, and improve objective quality under diverse and controllable feasibility conditions. GNBG-C therefore provides a flexible and auditable framework for probing the strengths and weaknesses of constrained continuous optimizers under targeted forms of feasibility-side difficulty.
We build on EndoWake, an endogenous wake model that links the wind speed at every grid cell to its upwind neighbors by linear constraints, so that wake field, siting decisions and project constraints share one mixed-integer model. Its four parameters are calibrated once on the single wake of a Reynolds-averaged Navier-Stokes (RANS) simulation, and a graphics processing unit (GPU) scores over a million layouts per second per wind direction. At Lillgrund, we compare searches guided by EndoWake and by PyWake under a RANS judge that no search calls: the fidelity of a wake model is not the quality of the layouts optimized under it. Two diagnostics separate a quadrature error between the sampled wind directions from a surrogate bias localized off each wake edge, not reported before to our knowledge; at random directions, five paired starts detect no difference between the pipelines. The main result puts the speed to use: EndoWake ranks the moves of a local search on the GPU, and PyWake confirms every accepted move. On twenty unseen starts, with one GPU and thirty CPU processes, screen-and-confirm reaches similar mean gains to a search on PyWake alone, 7.9 times faster at one wind speed and 14.9 times faster on the annual energy (3.0 and 4.7 with a proof of local optimality charged to the timed search); on a second site it keeps its speed, and its local optima fall slightly short of those of PyWake alone. Code and data are deposited on Zenodo.
Zhenyu Wang, Molei Liu, Jing Lei, Francis Bach, Zijian Guo
When synthesizing multi-source high-dimensional data, a key objective is to extract low-dimensional representations that effectively approximate the original features across different sources. Such representations facilitate the discovery of transferable structures and help mitigate systematic biases such as batch effects. We introduce Stable Principal Component Analysis (StablePCA), a distributionally robust framework for constructing stable latent representations by maximizing the worst-case explained variance over multiple sources. A primary challenge in extending classical PCA to the multi-source setting lies in the nonconvex rank constraint, which renders the StablePCA formulation a nonconvex optimization problem. To overcome this challenge, we conduct a convex relaxation of StablePCA and develop an efficient Mirror-Prox algorithm to solve the relaxed problem, with global convergence guarantees. Since the relaxed problem generally differs from the original formulation, we further introduce a data-dependent certificate to assess how well the algorithm solves the original nonconvex problem and establish the condition under which the relaxation is tight. Finally, we explore alternative distributionally robust formulations of multi-source PCA based on different loss functions.
We present sparse dictionary differentiable predictive control (SD-DPC), a framework for learning sparse, interpretable feedback policies for nonlinear systems from data. A prediction model is first identified by rollout-based sparse identification of nonlinear dynamics (SINDy), building on gradient-based and multistep formulations. The policy is then parameterized as a sparse combination of dictionary functions and trained by differentiating a constrained finite-horizon predictive-control objective through this model, so that its terms are selected by closed-loop performance rather than by imitating a previously trained controller. The result is an explicit feedback law with only a handful of terms. Across three benchmark control problems, SD-DPC satisfies the constraints in almost all test scenarios, outperforms a policy distilled onto the same terms by up to an order of magnitude, and requires orders of magnitude less memory and online computation than an optimization benchmark, while admitting explicit sensitivity bounds.
Elliot Paquette, Noah Marshall, Lucas Benigni, Guangyuan Wang, Atish Agarwala, Courtney Paquette
Muon and related spectral optimizers have recently demonstrated strong empirical performance as scalable stochastic methods, often outperforming Adam. Yet their behavior remains poorly understood. We analyze stochastic Muon, which orthogonalizes an exponential moving average of minibatch gradients, on a high-dimensional matrix-valued least squares problem, and we compare it with stochastic SignSGD, a simple baseline comparable to Adam. We derive explicit deterministic dynamics that provide a tractable framework for studying learning behavior. We show that Muon has non-linear sensitivity to the effective batch $B_{\rm eff}=B(1+β)/(1-β)$. With exact whitening and small $B_{\rm eff}$ Muon fails to resolve smaller eigenmodes, slowing down convergence. Momentum and finite Newton--Shulz iterations can act as a ridge which lessen this effect. This behavior is in contrast with SignSGD which has no transition, leading to different optimal learning rates, but with matching convergence rate up to a constant factor in the isotropic setting. For anisotropic data, large batch setting Muon performs a square-root preconditioning with respect to the data covariance spectrum while SignSGD provides no preconditioning for generic covariances. We analyze time to target loss in a power law covariance model and derive a phase diagram in the data exponent $α$ and target exponent $ζ$. Muon is favored for steep covariance spectra with rich targets ($α>2$, $ζ<α+1$), SignSGD is favored for flat spectra ($α<1$), and in other regions the winner depends on how the target loss scales with dimension. Our results shed light on why replacing Adam with Muon is not trivial even from a pure optimization perspective.
We study over-the-air computation of functions, such as empirical variance, formed by combining two separately postprocessed sums of locally transformed observations. We consider continuous encoders subject to pointwise peak-power constraints over a single use of a complex multiple-access channel. With four or more transmitters, we identify conditions under which exact noiseless recovery forces every continuous encoder collection into a common affine structure that preserves both sums, reducing infinite-dimensional encoder design to selecting a finite set of coefficients. To quantify resilience against channel noise, we introduce a robustness score that measures the separation of noiseless received aggregates relative to variations in the desired function value. Within this characterized encoder family, we formulate robustness maximization as an exact convex semi-infinite program, eliminating rank constraints without a relaxation gap, and construct a decoder that attains the minimum uniform noise-amplification constant. For several function classes, including empirical variance, we derive closed-form robustness-optimal encoders and scores. Under mild regularity conditions, we also establish sharp limits on the Gaussian mean squared error at high signal-to-noise ratios and show how using the input distribution reduces average error at the expense of uniform robustness.
Classical pooled-testing rules choose pool sizes to reduce the number of tests. In practice, however, samples arrive over time, pools take time to form, testing capacity is finite, and positive pools create bursts of follow-up work. These operational features can make the test-efficient pool size far from the delay-efficient one. We formulate pooled testing with stochastic arrivals and finite testing capacity as a queueing system, and derive exact performance representations and asymptotic scaling laws for fixed-batch Dorfman testing and a dynamic two-threshold policy. The analysis reveals three distinct design regimes. When test usage is the main concern, the classical Dorfman rule is recovered and the optimal pool size scales with the inverse square root of prevalence. When delay accumulated while the laboratory is busy testing another batch matters, positive pools create service-time variability that grows more rapidly with pool size than the mean retesting burden, and the optimal scale shifts to the inverse cube root of prevalence. When waiting to assemble a pool is itself costly, the optimal fixed pool size remains bounded even as prevalence becomes very small. Under severe capacity scarcity, congestion remains relevant at the classical Dorfman scale: the square-root law survives, but with a capacity-dependent constant. Dynamic pooling separates two operational decisions that fixed pool sizes conflate. A lower threshold determines when routine testing should begin, while an upper threshold limits pooling when backlog is high. The lower threshold follows the cube-root scale, whereas the upper threshold primarily acts as congestion control. The results show how prevalence, capacity, and delay jointly determine pooling decisions and explain why operationally optimal pools can be much smaller than those suggested by test-efficiency calculations alone.
The Low Order-Value Optimization (LOVO) problem involves minimizing the minimum among a finite number of function values within a feasible set. LOVO has several practical applications such as robust parameter estimation, protein alignment, portfolio optimization, among others. In this work, we are interested in the constrained nonlinear optimization LOVO problem of minimizing the minimum between a finite number of function values subject to a nonempty closed convex set where each function is a black-box and continuously differentiable, but the derivatives are not available. We develop the first derivative-free trust-region algorithm for constrained LOVO problems with convergence to weakly critical points. Under suitable conditions, we establish the global convergence of the algorithm and also its worst-case iteration complexity analysis. An initial open-source implementation using only linear interpolation models is developed. Extensive numerical experiments and comparison with existing alternatives show the properties and the efficiency of the proposed approach when solving LOVO problems.
Robust optimization models that allow decisions to adapt to newly revealed information remain computationally challenging and are often limited to two decision stages or are addressed heuristically or via approximation schemes. This challenge is further amplified when uncertainty sets depend on earlier decisions. Conventional approaches to such problems often require problem-specific reformulations and tailored algorithms, highlighting the need for an exact model-and-run approach. We address this gap by presenting an algorithmic framework for solving multistage robust discrete linear optimization problems. This exact approach adapts and integrates ideas from game-tree search, quantified conflict-driven clause learning, and integer linear programming to explore the minimax tree and is implemented in the open-source solver Yasol. The solver supports discrete decision variables across multiple stages, discrete uncertainty sets with polyhedral or decision-dependent structure, and mixed-integer recourse in the final stage. It can be used as a standalone executable or through a C++ library interface, allowing it to serve as a reference solver for exact methods in multistage robust discrete linear optimization. In an extensive computational study, we demonstrate the capabilities of our solver. The results show competitive performance against a reference approach from the literature for a protection-interdiction problem, as well as strong performance on bilevel benchmark instances. For a multistage cutting-stock problem, we demonstrate the substantial loss in solution quality that can arise from neglecting the multistage structure and show that our solver significantly outperforms decision-rule approximations in terms of computational efficiency while certifying the true multistage optimum.
Mohammad Al-Jarrah, Michele Martino, Marcus Yim, Bamdad Hosseini, Amirhossein Taghvaei
We present Conditional Wasserstein Autoencoders (CWAEs), a framework for conditional simulation that exploits low-dimensional structure in both the conditioned and the conditioning variables. The key idea is to modify a Wasserstein autoencoder to use a (block-) triangular decoder and impose an appropriate independence assumption on the latent variables. We show that the resulting model gives an autoencoder that can exploit low-dimensional structure while simultaneously the decoder can be used for conditional simulation. We explore various theoretical properties of CWAEs, including their connections to conditional optimal transport (OT) problems. We also present alternative formulations that lead to three architectural variants forming the foundation of our algorithms. We present a series of numerical experiments that demonstrate that our different CWAE variants achieve substantial reductions in approximation error relative to the low-rank ensemble Kalman filter (LREnKF), particularly in problems where the support of the conditional measures is truly low-dimensional.
High-frequency control problems are often studied through time discretization, but refining the timestep $δ$ increases the discrete horizon $H=T/δ$ and can make standard finite-horizon regret guarantees deteriorate even when the physical horizon $T$ is fixed. We study episodic value-based reinforcement learning for Euler discretizations of controlled diffusions. The performance is measured as the cumulative regret over $K$ episodes relative to the optimal policy of the corresponding Euler model. Under stability and regularity conditions on value function gradients, Bellman residual derivatives, and fitted critics, we prove an $\mathcal{O}(\log K)$ regret bound with constants uniform in $δ$. For dynamics with drift linear in unknown parameters and unknown constant diffusion covariance, we verify localized versions of these conditions for a constrained, model-based controlled-diffusion fitted-$Q$ algorithm (CD-FQ) and obtain high-probability $\mathcal{O}(\log K\log\log K)$ regret for fixed and finite $T$, again with constants uniform in $δ$.
Jia-Nan Wang, Zixun Huang, Kairui Li, Zilin Wang, Lei Wu
We study when and how momentum improves large-batch training in the one-pass regime, using power-law kernel regression as a tractable setting. We first characterize stochastic stability through the \emph{critical learning rate}, defined as the largest learning rate for stable training, and obtain $η_{\mathrm{SGD}}^{\mathrm{crit}}\eqsim 1$, $η_{\mathrm{Polyak}}^{\mathrm{crit}}\eqsim \min\{1,B(1-β)\}$, and $η_{\mathrm{Nesterov}}^{\mathrm{crit}}\eqsim \min\{1,B^q(1-β)\}$, where $B$ is the batch size, $β\in[0,1)$ is the momentum factor, and \(q>1\) is the capacity exponent governing spectral decay. Within the stable region, we derive scaling laws for the full risk dynamics, capturing the progression from an early transient through power-law decay to a noise floor. We then optimize the final-step risk under a fixed data budget, obtaining a three-regime phase diagram that reveals how the benefits of momentum change with batch size. Notably, Polyak enlarges the critical batch size, the largest batch size preserving the optimal small-batch data-scaling exponent, thereby allowing fewer sequential updates without sacrificing data efficiency. In contrast, Nesterov improves the optimal data-scaling exponent in the large-batch regime through look-ahead-induced suppression of noise amplification. Experiments on PLK regression quantitatively support the theoretical scaling predictions, while neural-network experiments provide qualitative evidence for the predicted batch-size dependence and stability behavior.
Mateo Díaz, Nicolás García Trillos, Daniel López-Castaño, Congwei Yang
Dimension-reduction methods such as PCA identify a subspace capturing most of the variation in the data, but not a distinguished basis within it. Selecting a basis in which the samples are sparsely represented is a recurring task in unsupervised learning, addressed by methods in factor analysis, dictionary learning, and subspace clustering. We pose this task as Wasserstein approximation of the data distribution by measures supported on the axes of an orthogonal frame, which, in turn, reduces to a nonsmooth optimization problem over the orthogonal group $\mathrm{O}(d)$. We show that, under mild assumptions, both empirical risk minimizers and a locally initialized stochastic gradient method recover the population-optimal frame at the near-parametric rate $\widetilde{O}_d(n^{-1/2})$, where $n$ is the sample size. The main difficulty is that, although the population objective is smooth, the empirical objective is not-this mismatch precludes standard covering arguments. We overcome this issue by replacing Lipschitz continuity of the empirical gradient with a coarsely Lipschitz bound, a tool that may be of independent interest. Numerical experiments support our theoretical findings.
Yifan Zhao, Qianyang Zhao, Xinyu Guan, kai wei, Yuming Deng
Chunking is a fundamental preprocessing step in retrieval-augmented generation (RAG), yet most existing chunkers rely primarily on heuristics. We introduce the Question--Evidence-Supervised Chunker (QESChunker), to our knowledge the first method for constructing static chunk indices from question--evidence supervision. QESChunker constructs document-specific chunk indices by optimizing over human-annotated or LLM-generated question--evidence pairs, without access to held-out test queries. We formulate non-overlapping and overlapping index construction through a unified question--evidence utility-maximization objective, turning chunking into a supervised combinatorial optimization problem. Under the non-overlap constraint, the objective decomposes over chunks and can be optimized exactly in polynomial time by dynamic programming. When overlap is allowed, the objective becomes monotone submodular; exact optimization is NP-hard, but our greedy achieves a $(1-1/\sqrt{e})$-approximation. Across two self-constructed and three public datasets, both variants outperform existing chunking methods in complete-evidence recall in nearly all evaluated settings, under the same overlap regime and a fixed hybrid retriever. These results recast chunking as supervised, budget-aware index construction for evidence retrieval.
Derivative-free optimization (DFO) addresses problems where derivatives are unavailable or costly to obtain. This setting often arises in simulation-based and experimental applications, where evaluating the black-box objective can itself be costly. Thus, it remains a central challenge in DFO to effectively exploit accumulated observations to select informative evaluation points under a limited budget. In this light, we introduce the NextEval solver, an agent-based DFO solver, which integrates the capabilities of a large language model (LLM) to guide the sequential selection of evaluation points. Specifically, we establish a system that combines an LLM agent with a numerical environment. The environment provides tools for analyzing past evaluations and executing numerical methods, while maintaining a shared evaluation history and method-specific state to support continuation across method switches. Using observations and tool feedback, the LLM agent selects tools, configures their parameters, and allocates the evaluation budget, while numerical methods compute and evaluate candidate points. Building on this system, we also introduce NextEval Bench, a benchmark protocol for comparing agent configurations on shared DFO tasks using the same numerical tools under matched evaluation budgets and information constraints. Numerical results on low-dimensional DFO problems demonstrate that the NextEval solver outperforms the state-of-the-art DFO baselines in function-evaluation efficiency.
Mingyuan Xu, Zongqi Xia, Tianxi Cai, Doudou Zhou, Nian Si
Learning a common policy from multiple source environments requires accounting for cross-source heterogeneity, and the offline setting introduces an additional challenge of limited data coverage. We formulate this problem as a distributionally robust Markov decision process under a shared linear MDP representation with source-specific transition and reward components. The uncertainty set is constructed through feature-wise mixtures of these components, yielding a $d$-rectangular structure that captures cross-source heterogeneity and admits a robust Bellman recursion. Building on this formulation, we develop Group-Robust Pessimistic Value Iteration (GR-PEVI), an offline policy-learning algorithm that combines feature-wise worst-case aggregation with a data-dependent pessimism penalty. Under a robust partial coverage condition, we establish finite-sample suboptimality guarantees for GR-PEVI and extend the analysis to clustered sources, characterizing the trade-off between the statistical gain from pooling similar sources and the approximation error induced by within-cluster heterogeneity. Simulation studies demonstrate the effectiveness of GR-PEVI, with empirical behavior consistent with the theoretical analysis. We apply GR-PEVI to a multi-source electronic health record study of multiple sclerosis treatment decisions to illustrate its use in a clinical setting.