arXane › Mathematics › Mathematics
Wednesday, 4 November 2026: 19 new papers, 16 cross-lists and 20 replacements in Optimization and Control (math.OC), in arXiv's order, with full abstracts. The same papers as arXiv's own listing, set as a newspaper; every title links to arXiv.
The paper considers a nonsmooth semi-infinite optimization problem in which the constraints are reformulated through a value function. Stationary points of the cutting surface approximations are studied, showing that stationarity is preserved in the limit under boundedness of the associated sequence of multipliers. Building on these results, an algorithm that combines the cutting surface approximations with a penalty scheme is devised, together with some proximal variants. An exact penalty result is established under suitable global conditions, and numerical results are reported to compare the methods with existing exact penalty and cutting surface algorithms.
In this paper, we investigate a class of decoupled infinite-horizon forward--backward stochastic differential equations (FBSDEs) with time-dependent coefficients and jumps. Under suitable time-integrability conditions on the coefficient growth and stochastic Lipschitz moduli, we establish an $L^p$ theory ($p\ge 2$) for these systems, including well-posedness, moment estimates, conditional stability, and tail estimates, without imposing dissipativity of the forward dynamics or monotonicity of the backward generator in its value variable. In particular, the forward state converges in $L^p$ and almost surely to a limiting random variable $X_\infty$, while the backward solution converges to the generally nonzero terminal value $\Phi(X_\infty)$. Within this framework, we study infinite-horizon two-player zero-sum stochastic recursive differential games. We prove that the lower and upper value functions are deterministic and establish the dynamic programming principle (DPP) using backward stochastic semigroups and nonanticipative strategies. Both value functions converge locally uniformly to $\Phi$ as the initial time tends to infinity and are characterized as viscosity solutions of the corresponding non-autonomous, nonlocal Hamilton--Jacobi--Bellman--Isaacs (HJBI) equations. Under an additional integrable Lyapunov-barrier condition, we establish a comparison principle for continuous viscosity subsolutions and supersolutions of uniform linear growth, provided that at least one is uniformly Lipschitz in space. This yields uniqueness for both HJBI equations in the linear-growth class. Finally, we establish a weaker, contact-wise Isaacs criterion ensuring that the lower and upper value functions coincide and hence that the game has a value.
We study the minimization of the average of $n$ convex $(L_0,L_1)$-smooth functions: the Hessian norm of each function is bounded by an affine function of its gradient norm. We assume known upper bounds $R$ on the distance from the starting point to a minimizer and $\delta$ on the difference between the minimum of the average and the average of the infima of the components. We derive upper and lower bounds on the oracle complexity of reaching accuracy $\varepsilon$ in function value in expectation. Up to logarithmic factors, both bounds are of order $n(1+(L_1R)^{2/3}) +\sqrt{\frac{n(L_0+L_1^2\delta)R^2}{\varepsilon}+n(L_1R)^2}$. The upper bound is attained by the proposed method YETI. The method combines ideas of accelerated proximal methods and variance reduction methods with a heuristic for choosing additional points. The number of oracle calls made by the heuristic is bounded, which preserves the upper bound on the total number of queries needed to reach the target accuracy. In the experiments, YETI is compared with first-order methods on synthetic problems and Poisson regression problems. We also examine the stopping criterion and the effect of the heuristic separately. The lower bound is obtained by an explicit construction of families of instances that are hard for any first-order method.
We study the optimal design of investment subsidies across heterogeneous monopolistic markets subject to a common expected discounted budget. Each producer faces a regular one-dimensional demand diffusion and chooses irreversible capacity expansion through a singular stochastic control problem. The regulator values weighted consumer surplus, producer profits, and an additional benefit from installed capacity, while accounting for the excess cost of raising public funds. We characterize producers' optimal investment responses through free boundaries and reformulate the regulator's stochastic optimization problem as a deterministic optimization over investment boundaries. An integral representation then recovers the optimal subsidy schedules that implement the resulting capacity policies. Under mild conditions on the diffusions, we establish existence of optimal schedules and uniqueness of the induced investment policies. Finally, we characterize the subsidy schedule and provide numerical illustrations.
We study how risk aversion changes learning and the value of data in the classical newsvendor problem. We evaluate data-driven policies through the Conditional Value-at-Risk (CVaR) of realized loss on the combined draw of an i.i.d.\ historical sample and an independent future demand from the same distribution. We measure worst-case regret over demand distributions on a bounded interval relative to an oracle that knows the distribution. We show that, for every fixed positive risk level, Sample Average Approximation (SAA) can retain regret bounded away from zero as the sample size \(n\) grows, even at a fixed demand distribution, and characterize its asymptotic worst-case regret. We trace this failure to persistent variability in the learned order, which contributes to tail risk under this combined-risk evaluation. We establish that risk aversion also slows the minimax learning rate over all data-driven policies from \(\Theta(n^{-1/2})\) under expectation to \(\Theta(n^{-1/4})\). We construct policies that average nearby order statistics and attain this optimal rate. For finite samples, we reduce worst-case analysis for mixtures of convex combinations of order statistics to Bernoulli demand on the endpoints of the interval. We use this reduction to formulate a linear program for computing minimax policies within this class to any accuracy. In numerical experiments, we find that minimizing this objective alone can leave substantial average CVaR regret when each learned order is evaluated over future demand alone. We therefore develop a two-stage linear program that minimizes the worst-case value of this average regret while allowing a prescribed increase in the original objective. This yields improvements across a broad range of scenarios. Our results show that risk aversion changes both the rate at which data improve decisions and the policies needed to realize that improvement.
In this paper, we propose a variance-reduced stochastic quasi-Newton sequential quadratic constrained quadratic programming method (VR-QN-SQCQP) for finite-sum nonlinear optimization with equality and inequality constraints. Exact nonlinear-constraint Hessians are replaced entirely by safeguarded symmetric rank-one (SR1) curvature models built from first-order constraint gradients, while PAGE estimates the objective gradient and an exact \(L_1\) merit function provides globalization. Under explicit regularity, boundedness, relative QCQP-accuracy, and step-length assumptions, the analysis establishes almost-sure subsequential convergence to Karush--Kuhn--Tucker (KKT) points and, under stronger uniform step-length and error-control conditions, an expected \(O(\varepsilon^{-2})\) outer-iteration bound for the squared KKT residual. A conditional local stability result also compares learned-curvature directions with their exact-Hessian counterparts. Numerical experiments compare VR-QN-SQCQP against Exact-SQCQP-PAGE on Sparse PCA using 253,680 CDC BRFSS 2015 observations and on a dense nonlinear benchmark. Over ten seeds, both methods converge in all Sparse PCA runs, while on the dense benchmark the proposed method converges in 10/10 runs versus 9/10 for the exact-Hessian variant. The proposed method performs zero exact constraint-Hessian evaluations and reduces median curvature-construction time on the dense benchmark from 0.1230 s to 0.0111 s. Overall runtime benefits remain problem-dependent.
We study how to compute valid dual bounds for mixed-integer linear programs (MILPs) with finite variable bounds under data perturbations. In an offline-online setting, a nominal instance is solved once and its information is reused to evaluate perturbations. We develop a framework for linear programs under simultaneous perturbations to the objective coefficients, right-hand side, and constraint matrix. Our construction is based on a bounded Lagrangian dual evaluated at nominal optimal dual multipliers. We prove that its gap to the perturbed LP optimal value grows at most linearly with perturbation magnitude under suitable conditions. We extend this construction to MILPs by reusing the nominal branch-and-bound tree and node-level dual information, generalizing the sensitivity analysis framework of Schrage and Wolsey (1985) to all problem data. To strengthen the dual bounds, we adapt their subtree-selection dynamic program. The online computations support GPU acceleration and highly parallel evaluation of dual bounds, which can also certify optimal variable fixings and accelerate reoptimization. Experiments on generalized independent set, combinatorial auction, capacitated facility location, and unit commitment instances produce tight dual bounds at low computational cost. For single-parameter ``what-if'' perturbations, gaps are typically a small fraction of a percent, with GPU evaluation times below a millisecond per perturbation. Relative to the time Gurobi needs to obtain bounds of the same quality, GPU evaluation is approximately 2,000--240,000 times faster for single-parameter perturbations and 120--50,000 times faster for multi-parameter perturbations. Using exact perturbed optima as supplied primal cutoffs, variable fixing accelerates exact reoptimization by up to a factor of 10 for generalized independent set instances, with little or no improvement for unit commitment.
We consider deterministic composite federated optimization, in which distributed smooth client objectives are combined with a shared, possibly nonsmooth, regularizer. We propose Relative-Error Composite FedDyn (REC-FedDyn), an inexact method that supports partial participation, with one server-side proximal evaluation per communication round. REC-FedDyn employs a directly testable relative-error criterion that allows each client to independently control the accuracy of its local subproblem, without a server-side acceptance test. We establish almost-sure iterate convergence for strongly convex and convex problems, almost-sure asymptotic stationarity for nonconvex problems, and communication and parallel gradient-evaluation complexity bounds, all under partial participation and without assuming bounded data heterogeneity. Experiments on image inpainting, fMRI prediction, and neural-network classification with structured regularization demonstrate efficiency and robustness across levels of data heterogeneity and client participation.
We study decentralized minimization of a smooth network average that is globally quasar-convex with respect to a fixed minimizer; the node functions may be nonconvex and need not share a minimizer. A unit-rate Poisson clock drives an exactly simulable continuized process: between events the state follows a closed-form accelerated flow, and each event uses one oracle vector. One master theorem covers oracles with a predictable bias and a state-dependent variance and keeps the inverse-quadratic term $\mathcal{O}(LR_0^2/(\gamma^2T^2))$; one selected-row lemma supplies the oracle moments of three network implementations. CQA-Net keeps a common state, mixes local rows for finitely many rounds, and disseminates one uniformly selected row; its oracle is unbiased at every mixing depth, so incomplete averaging affects only the variance. A walking token removes dissemination, the shared clock, and the shared root, and an importance weight keeps it unbiased on fixed graphs. D-CQA keeps local states and mixes them; under bounded heterogeneity it needs $\widetilde{\mathcal{O}}(\sqrt{\chi}\sqrt{L}R_0/(\gamma\theta\sqrt{\varepsilon}))$ communication rounds and no dissemination. Changing graphs enter through certified operator norms. Experiments on a certified nonconvex regression on static and changing graphs compare the three implementations.
Large language model (LLM) inference, the process by which a pre-trained model receives an input prompt and generates output tokens sequentially, has become increasingly important with the widespread deployment of LLM-based applications. As inference workloads continue to scale, GPU memory has emerged as a critical bottleneck: the long input prompts and generation sequences common in agentic and reasoning workloads lead to substantial key-value (KV) cache usage. In this paper, we study the resulting online scheduling problem from a queueing perspective. Requests arrive stochastically with heterogeneous prompt and output lengths, undergo prefill and autoregressive decode, and compete for a finite KV-cache capacity. Unlike classical queueing models, the duration of a processing step depends on both prefill computation and KV-cache I/O, so service capacity is jointly determined by computation, memory access, and memory occupancy. We develop a fluid model that reduces the system to a multiclass single-server queue with effective service rates capturing computation, memory access, and memory capacity. This fluid analysis yields a $c\mu$ priority rule, where the effective service rate $\mu$ is jointly determined by computational speed, memory bandwidth, and memory capacity. We prove that this rule minimizes cumulative holding cost in the fluid model and, for a finite workload, also minimizes completion time and maximizes full-run output-token throughput. We then construct a feasible scheduling policy for the original finite system and prove that its scaled dynamics converge to the optimal fluid policy. Finally, experiments on a real LLM serving engine using an NVIDIA H800 show that practical implementations of the proposed priority rule substantially reduce average latency while maintaining high throughput relative to existing scheduling policies.
This manuscript studies a constraint dissolving method for solving optimization problems with general constraints, comprising an abstract constraint G(x) \in C and a potentially nonconvex geometric constraint x \in D, which, to the best of our knowledge, is the first constraint dissolving type method applicable to this general setting. More specifically, we introduce an auxiliary variable s to decouple G(x) \in C into G(x) = s and s \in C, and construct the constraint dissolving mapping acting jointly on both variables. We then propose a penalty-based constraint dissolving method, in which the penalty parameter is updated adaptively according to the feasibility error. Under mild conditions, every accumulation point is Mordukhovich-stationary. By a specific choice of the constraint dissolving mapping, every accumulation point is guaranteed to be feasible, which stands in contrast to standard penalty-type methods in nonconvex settings. Numerical experiments on Rosenbrock, portfolio, and MAXCUT problems demonstrate the effectiveness of the proposed method against the augmented Lagrangian and the penalty decomposition methods.
Problem definition: We study dynamic inventory control for battery-swapping stations that combine central replenishment with automatic local recovery. Central replenishment improves immediate battery availability but reduces the depleted-battery pool available for subsequent recovery, creating an intertemporal trade-off. Managing this trade-off is particularly challenging when historical demand data are limited and future demand is uncertain and temporally dependent. Methodology/results: We develop a time-consistent distributionally robust dynamic program under martingale demand ambiguity, using the latest observed demand as the next conditional mean without requiring a fully specified demand distribution. We establish an optimal order-up-to policy for every finite horizon and identify two critical recovery rates governing replenishment decisions. Under a regular penalty condition, we derive explicit finite-horizon policies and worst-case demand distributions, showing that sufficiently strong automatic recovery makes central replenishment unnecessary in nonterminal periods. Extensions to submartingale and supermartingale demand reveal contrasting behaviors, including eventual full-capacity replenishment under upward ambiguity and recovery-induced positive replenishment under downward ambiguity. Managerial implications: Numerical experiments demonstrate that the robust policy is particularly competitive when demand is highly dispersed and historical information is limited, whereas its advantage diminishes when demand becomes more predictable or the conditional-mean assumption becomes less reliable. Our findings also reveal that greater reliance on local recovery may compromise service availability, highlighting the importance of jointly considering demand information, recovery capability, and service requirements when making replenishment decisions.
In this paper, we formulate a two-player zero-sum game under dynamic constraints defined in terms of a hybrid inclusion. The game consists of a min-max problem involving a cost functional that depends on the actions and corresponding (potentially non-unique) solutions, defined as functions of hybrid time and, hence, can flow or jump. We present sufficient conditions given in terms of Hamilton-Jacobi-Isaacs-like equations to establish a bound and to exactly evaluate the worst-case cost under the optimal strategy. Under additional conditions, we show that the proposed optimal state-feedback laws render a set of interest pre-asymptotically stable for the resulting hybrid closed-loop system. The results are illustrated in an application with sporadic jumps and linear quadratic hybrid dynamics.
Stochastic variance-reduced gradient (SVRG) uses a full gradient at a snapshot point to correct inexpensive component gradients. This fourth expository note on variance reduction explains that control variate and gives a self-contained proof of linear convergence for the classical strongly convex finite-sum setting. Each component is assumed convex and smooth, while only their average must be strongly convex. A second-moment bound links the estimator to the objective gaps at the current iterate and the snapshot. Summing a distance recursion over an epoch then yields a geometric decrease and an oracle complexity of order $(n+L/\mu)\log(1/\tau)$ for objective accuracy $\tau$, with the initial gap fixed. The result uses a random snapshot update and counts all full-gradient computations. No new algorithm or rate is claimed.
Practitioners of linear programming widely believe that reformulating a linear program (LP) offers little benefit to interior-point methods: their iteration counts are famously insensitive to the formulation, so the payoff of reformulation beyond automatic presolve and customized linear solve is modest. This paper presents evidence that the same is not true of first-order solvers built on the primal-dual hybrid gradient method (PDHG), such as PDLP. Unlike interior-point methods, PDHG-type methods have per-iteration costs governed by the matrix representation of the formulation and iteration counts governed by its geometry, and both change under equivalent reformulations. We describe a general reformulation recipe: constraints drawn from a catalogue of projection-friendly polyhedra can be absorbed into the projection step of PDHG. We analyze what absorption does to the four constants that govern restarted PDHG: the coupling norm, the termination certificate, the distance scale, and the sharpness modulus. We perform the reformulation on two case studies. On the LP relaxation of quadratic unconstrained binary optimization (QUBO), absorption makes any step size below $1$ admissible on every instance, and yields a fully explicit linear rate. On the LP relaxation of the joint replenishment problem (JRP), whose optimum certifies a $2$-approximation for an NP-hard inventory problem, absorption improves the coupling norm and eliminates every matrix-vector product. Both reformulations run on GPUs with custom kernels in place of sparse matrix-vector products. We benchmark both against the GPU LP solver cuPDLPx applied to the original formulations. By solve time, the reformulated solvers are $6.4$-$9.6\times$ faster on QUBO and $6.1$-$28.9\times$ faster on the JRP. They take $1.7$-$4.3\times$ and $13.6$-$52.3\times$ fewer iterations respectively.
This paper introduces the Location-Routing Problem with Delivery Preferences, a last-mile delivery problem with service flexibility that integrates collection-point activation and routing decisions while accounting for customer choice. The company determines which collection points to activate, which customers to offer home delivery, and the corresponding delivery route. Customers subsequently decide whether to accept the proposed home-delivery service or collect their parcels from an activated collection point according to ranked preferences over delivery time intervals and collection points. This hierarchical interaction is modeled through a bilevel optimization framework, which can be formulated as a mixed-integer bilevel program that incorporates compensation mechanisms for service inconvenience. Two equivalent single-level reformulations that exploit the structure of the customers' problems are developed. In addition, a two-phase heuristic is proposed to generate feasible solutions that can be used as warm starts for the formulations. The computational experiments run to compare the performance of the formulations, show that the warm-start strategy becomes particularly effective as the instance size increases. The comparison with a benchmark model that ignores customer preferences indicates that explicitly accounting for customer choice alters the resulting location-routing configuration while improving customer preference satisfaction at a small increase in the company's overall cost. These findings highlight the importance of jointly considering operational efficiency, service flexibility, and customer autonomy in last-mile delivery planning.
This work considers stepsize schedules for gradient descent on smooth strongly convex objectives. We develop a curvature-dependent concatenation framework for constructing stepsize schedules of arbitrary length with sharp worst-case guarantees. Within this framework, we introduce two families of schedules for the function-value gap and gradient norm of the last iterate, respectively. For each fixed condition number $\kappa=L/\mu>1$, both families attain iteration complexity $\Theta(\kappa^\rho\log(1/\epsilon))$ for sufficiently small $\epsilon$, where $\rho=\log_{\sqrt2+1}2\approx0.7864$. This complexity is optimal up to a subpolynomial factor in $\kappa$ among predetermined nonnegative stepsize schedules. The framework also recovers the strongly convex silver schedule at power-of-two iteration budgets and applies to smooth convex and smooth weakly convex functions.
Efficient preconditioning plays an important role in large-scale first-order optimization. In this paper, we propose an adaptive accelerated optimistic dual averaging ($\text{A}^2$ODA) method for unconstrained convex optimization that adopts low-cost preconditioning based on $p$-norm geometry for $p\in[2,\infty]$. The method is line-search-free and employs a new stepsize selection technique based on an aggregated affine lower model. Its update structure is simple and unified across $p\in[2,\infty]$, with the case $p>2$ requiring no more elaborate updates than the Euclidean case $p=2$. Under a generalized local smoothness condition, we derive a convergence bound that separates the effects of constant and gap-dependent curvature, with the latter potentially yielding faster-decaying terms. In the special case of local smoothness, this bound recovers a nearly optimal convergence rate.
Minimum shipment quota regulations ensure that socially critical commodities are not excluded from capacity-constrained freight markets by profit-driven allocation. Existing models of such regulation are deterministic and static, assuming perfect market knowledge and instantaneous convergence to a rational equilibrium. This paper relaxes both assumptions through a framework combining adaptive robust optimization, multi-objective optimization, and evolutionary game theory. A robust optimization model first characterizes the regulator's quota-setting problem under uncertain commodity availability, trading social welfare against enforcement cost to generate a Pareto frontier of quota policies. This frontier then defines the regulator's strategy space in a three-population evolutionary game in which the regulator, suppliers, and carrier co-evolve under replicator dynamics, so that the prevailing policy emerges from the interaction of the three players. The framework is calibrated to a Canadian rail freight case study that covers crude oil, corn, barley, and oat. Quota regulation raises social welfare from 65.0 to 288.2 million CAD, at an enforcement cost of about 2% of the gain. Two findings carry particular policy weight: capacity shortfalls fall entirely on unprotected commodities the carrier ships voluntarily, sparing both the highest-margin and the protected products; and a fall in transport cost can end the regulation while the exclusion it was designed to correct persists, because the margin observable before bidding diverges from the margin prevailing once suppliers adapt.
Computing a Karush-Kuhn-Tucker (KKT) point of a quadratic polynomial over the unit hypercube is known to be $CLS$-complete, when the coefficients of the polynomial are encoded in binary. We prove that the problem remains $CLS$-complete even when the coefficients are encoded in unary. This is the first problem proven to remain $CLS$-hard when the input is given in unary.
Max-Pressure (MP) has emerged as a widely studied decentralized traffic signal control framework, thanks to its desirable theoretical properties and strong control performance. Early research on MP focused on improving control performance by exploring different variables of the traffic state for the definition of pressure. Subsequent studies expanded MP to incorporate the complexity of real-world transportation systems and emerging technologies. This paper provides a comprehensive review of these developments. The review first introduces the theoretical foundations of MP and examines early developments in movement weight definition. It then synthesizes major extensions for multimodal and multiscale network control, followed by recent developments in connected and automated vehicle (CAV) environments and the integration of MP with artificial intelligence (AI) and data-driven methods. Beyond summarizing existing approaches, this review examines their underlying assumptions, data requirements, implementation considerations, and practical limitations. Based on this comprehensive review, key research gaps and future directions are identified, including remaining limitations in the theoretical foundations of MP and the underexplored integration of autonomous vehicle control with the MP framework. Overall, this review provides a structured perspective on the evolution and current state of MP control and highlights opportunities for developing more proactive, robust, and practically deployable MP-based traffic control methods.
Capacity expansion models often dramatically simplify the physics of how power flows through a transmission network in order to preserve computational tractability. However, with the rapid growth of electrification, large loads, renewables, and storage, increased realism in planning future grids is imperative. We extend the open-source capacity expansion model GenX with AC optimal power flow physics, and analyze generation, storage, and transmission investment decisions for 20-zone, hourly models of Germany and Texas. We compare our results against those using two common approximations, the transport model and DC optimal power flow. We find that total costs and emissions largely agree across all formulations. However, we find substantial differences in outputs related to transmission, generation siting, storage, and reactive-power support between the approximate formulations and the true AC physics formulation. We identify where AC physics changes planning decisions and discuss how to potentially capture these effects without the full computational cost.
The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an $\ell_p$ ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for $p = 1$ and multi-player polymatrix games for $p = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 2$, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for $p=2$, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.
Motivated by the expressive power of neural ordinary differential equations in flow-based generative modeling, we study the approximation of probability measures by pushforwards generated by parameterized families of Lipschitz vector fields. For Wasserstein distances, we establish a quantitative relationship between finite-sample point interpolation and distributional approximation, and derive universality criteria based on $L^p$-approximation of transport maps. In particular, affine-invariant families containing a non-affine vector field are universal from compactly supported absolutely continuous base measures. For total variation, we show that coordinate-wise dynamics are insufficient in dimensions $d\geq 2$ and establish sufficient conditions based on one-dimensional Sobolev approximation and shear-type mixing. We further examine the role of point interpolation, establishing when different regimes relate to one another and when approximate interpolation can be made exact.
Data-driven algorithms are ubiquitous across industries, and there is an extensive literature on analyzing their \emph{average} performance. The risk profile of such algorithms, while critical, is much less understood. This paper quantifies the risk of data-driven policies and isolates its sources. We evaluate a policy through the conditional value-at-risk (CVaR) of its loss over the training sample, any policy randomization, and the future outcome, at a fixed unknown distribution. Regret against an oracle that knows the distribution decomposes into expected post-sample regret (PS), the average outcome-only CVaR gap of the selected action, and a sample-risk premium (SR), the additional tail risk omitted by averaging those evaluations. The analogous premium vanishes under expected loss. We characterize when the premium vanishes and how large it is relative to post-sample regret. For losses with a continuous density near the tail cutoff, we identify conditions under which both components decay at the same rate, yet the limiting ratio of the premium to post-sample regret can reach the thousands. When a probability mass at the cutoff moves with the action, the premium can decay more slowly and dominate post-sample regret. We establish conditions under which sample average approximation learns the oracle action at rate $n^{-1/2}$ in both settings, but its combined-risk regret is of order $n^{-1}$ in the first and $n^{-1/2}$ in the second. In finite-sample numerical examples of SAA in both settings, the premium accounts for approximately $74\%$--$97\%$ of regret.
Funnels, time-varying invariant sets around nominal trajectories, certify that a closed-loop system tracks its plan, and can be composed into verified motion plans. Their computation by sum-of-squares (SOS) programming is well established in formulation but not in practice: the result depends on implementation choices such as the initial guess, Lyapunov function normalization, and termination rule, which the literature documents only briefly. This paper presents a self-contained treatment of SOS-based funnel computation, implemented in the open-source package computeSOSFunnels. We propose a minimum-volume formulation with inlet and outlet constraints under which funnels with coinciding nominal endpoints compose by construction. Numerical experiments on a unicycle, with timing studies on a cart-pole and a 12-state quadrotor, characterize the pipeline: infeasible initial guesses are partly decidable before solving, the certificate shows no violations among 39,000 boundary samples per funnel under the true dynamics, and constructing the semidefinite program, not solving it, dominates computation time.
We consider a two-well problem within geometrically linear elasticity, on a bounded Lipschitz set in dimension $n\ge 2$. We assume that the two wells are compatible through a symmetrized rank-one connection and that the displacement matches their average on the boundary, and we include a regularization based on the total surface energy. We show that there are two distinct regimes, with the energy scaling differently in terms of the surface-energy coefficient $\eps$: it is proportional to $\eps^{2/3}$ if there are two distinct compatible twin-normal directions, and to $\eps^{4/5}$ if there is only one. This matches previous findings in rectangles and other special geometries, mostly in two dimensions, and the lower bounds obtained by a Fourier method by Rai\c{t}\u{a}, R\"uland, Tissot and Tribuzio (2024). Our results are obtained by explicit constructions, which contain a self-similar refinement of oscillations close to the boundary, and by a short real-space proof of the matching lower bounds.
We propose a Multi-technology AdopTion-opinion co-Evolution (MATE) model to describe the diffusion of $m \geq 2$ competing alternatives within a networked population whose opinions evolve under social influence and the feedback generated by adoption. Communities interact through two layers: a physical network governing exposure to adoption, and a social network shaping opinion evolution through social imitation. Individuals can adopt a technology, eventually becoming dissatisfied at a rate reflecting the quality of the technology, and switch to an alternative at a rate driven by their opinion of that alternative. For an arbitrary number of competing technologies $m \geq 2$, we characterize the equilibria and establish the existence of an adoption-diffused equilibrium in which all technologies coexist. For $m > 2$, the equilibrium configuration depends on the broader competitive environment: unlike the two-technology case, within-community relative adoption generally depends also on equilibrium opinions and on the other alternatives. Finally, we formulate finite-horizon opinion-shaping control problems, derive necessary optimality conditions via the discrete-time Pontryagin maximum principle, and compute numerical extremals using a forward-backward sweep method.
The classical model-based optimal design criteria (D-, T-, L-, C-, and A-optimality) are usually motivated via the Cram\'er--Rao bound as optimizing scalar functions of the Fisher information matrix (FIM). This paper offers a complementary reading in which each criterion appears asymptotically as $N \to \infty$ as the leading-order term of an expected dissimilarity between prior and posterior, with the FIM entering through the Bernstein--von Mises limit. The Kullback--Leibler (KL) divergence of the posterior relative to the prior recovers D-optimality (classically known); a reverse KL of the prior relative to the posterior recovers T-optimality (here defined as maximization of the trace of the FIM, following one common convention) and its weighted-trace generalization; and a first-order approximation of the squared 2-Wasserstein distance recovers L-, C- and A-optimality. The five criteria emerge as instances of a common Bayesian-geometric template, indexed by three choices: the dissimilarity, the prior parametrization, and the approximation scheme used to evaluate it (e.g.\ Taylor expansions of the matrix square root). For the weighted criteria, the Gaussian prior covariance encodes the criterion's weight matrix, so any choice of weights corresponds to a specific prior in the family. The T-, L-, C-, and A-optimality derivations appear novel to the best of my knowledge. A sixth criterion, E-optimality, is recovered not as an independent expected-dissimilarity limit but as a min-max robustification of C-optimality against uncertainty in the modeler's prior direction. The framework is extended to distinguish between a designer's prior over unknown parameters at design time and a modeler's prior used for posterior inference, recovering the classical expected information gain objective as a special case.
Integral quadratic constraints (IQCs) and scaled relative graphs (SRGs) are two prominent frameworks for analyzing feedback systems. Although both frameworks are rooted in the same graph separation principle, a general characterization of their relationship has remained unavailable. This paper establishes conditions under which the IQC- and SRG frameworks are equivalent. To this end, we introduce two new classes of systems, termed disjunctive and conjunctive systems, which are respectively characterized by unions and intersections of quadratic input-output constraints. Under structural assumptions, we prove equivalence between the IQC and SRG frameworks for these system classes. By exploiting this equivalence, we develop novel IQC- and SRG-based converse stability results for linear and nonlinear systems. Our results accommodate multiple quadratic constraints, extending well-known converse results in robust control beyond the single-constraint setting.
We present an algorithm for approximating a given matrix polynomial of degree $d$ by a matrix polynomial of prescribed rank and degree at most $d$. The method builds on recent advances in the theory of generic eigenstructures and factorizations of matrix polynomials with bounded rank and degree. We also give a specialized treatment of the case of matrix pencils (degree one matrix polynomials), motivated by its particular theoretical and practical importance. Lastly, numerical experiments are reported to assess the performance of the proposed approach and to compare it with existing methods.
Matrix factorization provides a simple model for studying the training dynamics of neural networks. Recent studies of gradient flow under small initialization have analyzed how trajectories escape from a neighborhood of the origin and approach their first nonzero stationary point. In this paper, we study continuous-time dynamics that applies a finite number of Newton-Schulz iterations to the normalized matrix gradient (Muon). We show that the number of Newton-Schulz steps can change the rank selected during the early stages of training and allow the resulting trajectory to bypass the first nonzero stationary point approached by gradient flow. Under an additional residual-inertia condition, we prove that bypass occurs for all sufficiently large finite Newton-Schulz depths and provide an explicit sufficient threshold. We also construct an example in which the bypass threshold is four.
Risk and reliability analysis are fundamental to the design, assessment, and operation of safety-critical complex systems; however, their integration into next-generation computational tools is constrained by the cost of uncertainty quantification with expensive computational models. The computational challenge is particularly prohibitive for tail-sensitive quantities, such as probabilities of failure, conditional values-at-risk, and buffered probabilities of failure, where accurate estimation can require a large number of model evaluations. Multifidelity methods provide a framework for addressing this computational bottleneck by combining information from models of varying accuracy and cost while retaining the predictive accuracy of the high-fidelity model. This review summarizes the state of the art in methods that enable scalable risk and reliability analysis using multifidelity control variates, multifidelity importance sampling, and multifidelity active learning.
We study the superhedging of American claims with an irregular optional payoff process $\xi$ over the full set $\mathcal{M}(X)$ of equivalent local martingale measures of a locally bounded market. We show that a process which is a strong optional supermartingale of class (D) under every $Q\in\mathcal{M}(X)$, with no bound from either side, decomposes as $S=S_0+\int H\,dX-A-C_-$, with a common integrand $H$, a right-continuous increasing process $A$ and a purely discontinuous increasing process $C$ given explicitly by the right jumps of $S$. For the robust Snell envelope this yields the superhedging duality $p_0(\xi)=\sup_{Q}\sup_{\tau}E^Q[\xi_\tau]$ with an explicit optimal strategy and no regularity of $\xi$ in time. Unbounded payoffs are covered when $\{\xi_\tau\}$ is uniformly integrable jointly over measures and stopping times, or when $|\xi|$ is dominated by a traded uniformly integrable martingale. For payoffs bounded below, the price is attained by wealth bounded below by a constant. For payoffs unbounded below this can fail, already in a complete market, and the price is attained once the constant bound is replaced by $-M$, with $M$ a traded martingale dominating $|\xi|$. In an incomplete Brownian market we study the associated reflected BSDE with an optional obstacle and a Lipschitz driver depending on the value. We prove existence and uniqueness of the minimal supersolution, a representation at stopping times, comparison and an equivalent dynamic minimality condition, for bounded data and for data dominated by a traded martingale. For a European-type obstacle, the Skorokhod conditions on the total regulator hold for some supersolution if and only if the terminal claim is attainable by a bounded wealth process; so in an incomplete market some data admit no supersolution satisfying them, while the right-jump regulator always satisfies its contact condition.
Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.