Papers

We study average-reward weakly-coupled Markov decision processes (WCMDPs), where a WCMDP consists of $N$ smaller MDPs, called arms, that share multiple per-step budget constraints. We consider the setting where the arms have identical model parameters, multiple actions, and state- and action-dependent costs. For restless bandits (RBs), a well-studied special case of WCMDPs, prior work has developed policies that achieve an $O(1/\sqrt{N})$ optimality gap under general conditions, and has further identified conditions under which policies can achieve a better-than-$1/\sqrt{N}$ optimality gap. However, for general WCMDPs, no prior result achieves an optimality gap better than $1/\sqrt{N}$. In this paper, we identify conditions analogous to those for RBs under which a better-than-$1/\sqrt{N}$ optimality gap is achievable, and design a policy that attains an $O(1/N)$ optimality gap. Notably, unlike prior approaches based on generalizing priority orderings, our policy is not priority-based but rather is designed to induce locally linear mean-field dynamics.

We study the deterministic query complexity of finding approximate Goldstein stationary points of globally Lipschitz functions that may be nonsmooth and nonconvex. Under prescribed bounds on the Lipschitz constant and on the difference between the initial function value and the infimum, we prove a lower bound on the worst-case number of oracle calls that is exponential in the dimension at fixed sufficiently small accuracy parameters. The result holds for a local oracle and gives explicit dependence on the accuracy parameters. A complementary deterministic algorithm using only function values gives an exponential upper bound, establishing the exponential order in the dimension in this regime. For a coarser stationarity requirement, we also give a deterministic first-order algorithm with a dimension-free query bound. Thus, the dimension dependence differs between the two accuracy regimes.

We propose a continuous-time algorithm for zeroth-order global optimization of smooth functions on compact manifolds that synthesizes Riemannian gradient dynamics using only objective measurements, without evaluating gradients. The algorithm is formulated as an ordinary differential equation driven by piecewise-smooth McShane-type approximations of the Wiener process, with a geometric compensation term that depends only on the actuation frame and not on the objective function. Our main result establishes infinite-horizon practical probabilistic guarantees for fixed approximation parameters. To this end, we show that the algorithm's trajectories approximate, in the mean-square sense, a Riemannian Langevin diffusion whose unique invariant Gibbs measure concentrates on the set of global minimizers. We exploit this approximation to establish finite-horizon probabilistic convergence guarantees and directly analyze the algorithm's long-time behavior to obtain the infinite-horizon result.

We study generalized learning dynamics in multi-agent systems whose joint state evolves on a manifold and whose agents act through state-dependent, potentially nonholonomic vector fields. Under a bundle-splitting condition, we show that these dynamics admit an intrinsic representation as projected Riemannian gradients, giving rise to a class of nonholonomic gradient play dynamics. We characterize the local stability of its equilibria through an intrinsic linearization that explicitly captures the effects of the Riemannian connection and the nonholonomy of the actuation frame. The framework recovers classical gradient play on Euclidean spaces and manifolds as special cases while accommodating nonholonomic actuation. We then develop a geometric theory of deception under asymmetric information, whereby an agent exploits privileged knowledge of other agents' learning rules to manipulate the emerging equilibrium. We show that deception effectively tilts the Riemannian geometry perceived by the oblivious agents, distorting their projected gradient directions. We establish persistence of exponentially stable equilibria over an open set of deception parameters and derive an explicit first-order characterization of the resulting equilibrium displacement. Analytical and numerical examples illustrate the framework and its implications for equilibrium manipulation in games.

We give an explicit solution to the five expert prediction with expert advice partial differential equation (PDE) in the finite-time horizon setting. The solution formula establishes that the adversary's rank strategy $(1,0,1,0,0)$ is globally optimal, and the COMB strategy $(1,0,1,0,1)$ is optimal exactly on the set where $x_1=x_2$ and $x_3=x_4$. The formula is derived from the solution of the geometric-stopping problem given in our companion paper through the transform principle of Bayraktar, Ekren and Zhang, which links the two problems by a Laplace transform. Inverting the transform term by term expresses the solution through a series of Gaussian and complementary error function kernels. The optimality of $(1,0,1,0,0)$ is reduced to the signs of $41$ one-variable Gaussian series, which are certified with computer assistance by Poisson summation, first-mode domination and interval arithmetic on $1616$ rational cells. The proofs of our main theorems, certificates included, are also formalized in the Lean proof assistant.

On-policy distillation (OPD) trains a student on its own generated responses using dense, token-level supervision from a stronger teacher. Vanilla OPD treats all teacher signals equally, assuming that the teacher's supervision is equally important for every token. However, teacher signals at different tokens may have very different effects on the student's performance: some correct important reasoning errors, while others have little effect on the final answer. Motivated by this observation, we introduce Dr. OPD (OPD Done Right), which defines the optimal weighted OPD to maximize the student's performance. We formulate Dr. OPD as a bilevel optimization problem in which the student learns from weighted teacher supervision, while the weights are selected to maximize the expected reward of the resulting student. To solve Dr. OPD, we develop an efficient iterative solver that updates the token weights and student policy alternatively. At each round, it updates weights in closed form and then takes one gradient step on the resulting weighted OPD objective. Under regularity conditions, we show that this weighted update achieves a higher expected reward than a vanilla OPD update. Empirically, across strong-to-weak and same-size distillation on math and code, Dr. OPD consistently outperforms all evaluated baselines. In particular, in the strong-to-weak distillation setting, Dr. OPD improves average math performance by $9.7$ points over vanilla OPD, and enables the smaller student to surpass its larger teacher.

We propose a single-level reformulation (SLR) for the pessimistic bilevel optimization problem that does not rely on complementarity conditions or optimal value functions. For this reason, we refer to it as a true single-level reformulation (tSLR). A remarkable consequence is that this reformulation can satisfy the classical linear independence constraint qualification, despite the fact that even the weaker Mangasarian-Fromovitz constraint qualification is known to systematically fail for standard single-level reformulations of both optimistic and pessimistic bilevel programs. We leverage on these constraint qualifications to construct new necessary optimality conditions for pessimistic bilevel optimization. The reformulation also has a striking limitation: under the assumptions of our analysis, the classical second-order sufficient condition fails at every Karush-Kuhn-Tucker point of the problem. Nevertheless, preliminary numerical experiments demonstrate that algorithms based on the proposed tSLR can outperform existing approaches for pessimistic bilevel optimization. Overall, the proposed framework suggests that pessimistic bilevel programs may be considerably more tractable than previously believed and need not be inherently more difficult to solve than their optimistic counterparts.

The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut–Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.

We study the optimization landscape of low-tubal-rank tensor sensing through a balanced factorization. Under a tubal restricted isometry condition, we establish a quantitative strict-saddle landscape with no spurious local minima for arbitrary Fourier multi-rank profiles. We further show that the local geometry depends on the Fourier-slice ranks rather than the tubal rank alone. Uniform ranks yield quadratic growth transverse to the solution orbit, whereas nonuniform ranks produce quartically flat directions through hidden frequency-wise overparameterization, even when the factor width equals the exact tubal rank. Numerical experiments illustrate the global optimization behavior and the contrasting local geometries.

This paper addresses the stabilization of switched affine systems under dwell-time constraints around a desired operating point that is not a common equilibrium of the subsystems. Since asymptotic stabilization is generally unattainable in this setting, the objective is to ensure that trajectories converge to and remain within a prescribed region containing the desired operating point. The main contribution is the development of Lyapunov-based tools that accommodate target regions more general than those induced by quadratic Lyapunov functions. In particular, we establish a constructive Lyapunov characterization for a broad family of weighted $p$-norm functions, which generalizes the classical quadratic Lyapunov equivalence and underpins the proposed hybrid-control and dwell-time developments. Focusing on the case in which the desired region is a polytope, and building on existing Lyapunov-based methods, we develop a constructive two-step method that starts from a polytopic Lyapunov certificate for the average system and yields a smooth weighted $p$-norm Lyapunov function for all sufficiently large $p$. We prove that this extension guarantees practical asymptotic stability of the desired operating point and yields a Lyapunov-certified invariant region under minimum dwell-time switching. Numerical examples illustrate the effectiveness of the proposed method.

{Let \(K\subseteq\mathbb R_+^E\) be a closed convex cone and \(P=K\cap[0,1]^E\). For a linear objective with positive optimum, we study the intersection of the coordinate supports of all optimal solutions.} We prove that this common support is a transversal of a natural clutter associated with the positive directions of the cone and introduce a decreasing hierarchy of bottleneck families that stabilizes after at most \(|E|-1\) levels. In the polyhedral setting, the first level consists exactly of the sets carrying feasible upper-bound dual multipliers, while every set carrying an optimal multiplier belongs to the stabilized family. {The breadth of the join-semilattice generated under union by the zero sets of the nonzero vertices gives an objective-independent upper bound on the universal stabilization depth;} this bound is exact for simplicial truncations. Every possible depth occurs, and the \(|E|-1\) bound is sharp. Membership in the second level is co-NP-complete and fixed-parameter tractable in the size of the candidate bottleneck. Under upper-box-integrality and the integer decomposition property, the hierarchy collapses at level two, and its stabilized members are exactly the carriers of optimal upper-bound multipliers. When \(P\) is integral, the common optimal support is the union of the supports of all optimal dual solutions. Applications include bipartite matchings, maximum-order cycle subdigraphs, binary circulations, balanced hypergraph matchings, interval hypergraphs, and maximum-weight closures.

We study the Delay Constrained Routing (DCR) problem arising in IP computer networks to support high bandwidth applications. The goal is to route IP packets, from source to destination, subject to quality of service constraints – in particular, bounding the worst case delay – while minimizing the total allocated bandwidth in the network. DCR can be formulated as a Mixed-Integer Second-Order Cone Program, and solved using standard solvers; while generally efficient, this hinges on off-the-shelf tools and does not scale to large instances. We devise a solver-free bespoke approach that uses nested Benders-Lagrange, namely, a double decomposition approach that exploits the special structure of the problem. In particular, we use a nonconvex nonlinear formulation of the problem, that results in a nonconvex Benders value function whose optimization we tackle with a bespoke Spatial Branch-and-Bound approach using custom piecewise-convex cuts. We show that our approach provides very tight upper and lower bounds in competitive running times w.r.t. previous state-of-the-art approaches.

Greedy box splitting reads gradient signs at the centre and retains one smaller box. Its summable travel budget makes an incorrect exclusion irreversible. We determine when this geometry is safe. Halving is minimax optimal in the sign-vector oracle model on a coordinatewise sign-consistent class that need not be convex. A dimensionless sign defect yields a sharp scalar envelope, attained by one smooth convex potential; a three-dimensional trajectory ends farther from the target than its initial radius. For quadratics, universal convergence with aspect $w$ and contraction beta holds exactly when the weighted absolute row defect is at most $(2 \beta - 1)$. Perron weights minimise this defect. Adaptive half-sizes avoid initial enlargement and, under persistent error, converge to an exact capped fixed-point limit. For binary comparisons, an independent probe fraction $q$ permits universal localisation on common-target monotone sections exactly when $(q \leq 2 \beta - 1)$; coupled probes give the sharp threshold $2/3$. Matching information bounds distinguish comparisons from sign-vector queries. Error bands give finite-time guarantees and sharp residual floors. Extensions and reproducible experiments identify the assumptions and costs of freezing, smoothing, voting, multistart and random-matrix certificates.

Fix a target accuracy $\varepsilon$, a gradient-noise level $s$, and a horizon $N$. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., $\mathcal{E}_N = -\log \sup_{f,P} \mathbb{P}_P(f(x_A) - f_\star \ge \varepsilon)$, with the noise law $P$ known only to be sub-Gaussian. We single out a uniformly averaged schedule which is harmonic (of the form $h_k = R^2/(\varepsilon (N+m-k))$) and prove, via an optimized exponential supermartingale argument, that it attains the optimal exponent $\mathcal{E}_N^\star = \varepsilon^2 N (1+o(1))/(2R^2 s^2)$. Optimality is certified by a matching impossibility result: under Gaussian noise, a gradient-masking change of measure caps the exponent of every algorithm at the same leading order. In a small-noise limit, our setting degenerates into the adversarial-error model of Gösgens and van Parys (2025) for subgradient methods.

Learning how to replenish inventory and estimating the cost of doing so require different information. We establish information-theoretic lower bounds for offline multistage inventory control with independent bounded demand. For fixed additive error in total expected cost, policy learning requires cubically many scalar observations in the horizon in the worst case, even under full observation and adaptive sample allocation. This matches the known empirical-risk upper order. Stationarity permits a quadratic policy-learning guarantee, yet valuation with inherited stock can remain cubically difficult even when the optimal policy is known. Censoring sharpens this distinction: optimal decisions can be learnable while absolute costs remain unidentified. We give a carrysafe coverage condition under which truncation preserves inventory transitions and policy gaps exactly. Combining this reduction with a matching lower bound yields the sharp censored-learning rate, with raw sample requirements inversely proportional to the usable fraction of sales logs. The same qualified observations can check coverage and fit the policy under a joint error guarantee. The results isolate information limits for decisions and valuation under an explicit conditionally independent logging protocol.

Generating optimization instances that are both feasible and computationally challenging is crucial for benchmarking solvers and training learning-based optimization algorithms. Existing non-LLM generators rely on seed instances or parameter tuning, resulting in high test-time computational cost, while existing LLM generators lack explicit hardness measures. Recent reinforcement learning methods with verifier feedback evaluate only binary correctness, which is misaligned with generating challenging problems. We note that an optimization solver reports the cost of solving at several stages of its pipeline, and leverage this to design a reward that scores both the solvability and the hardness of generated problems, measured by branch-and-bound nodes and post-cut relaxation gaps. Our key idea is a challenger-solver asymmetric self-play approach, where an LLM challenger generates progressively harder instances and the solver verifies feasibility and hardness, so no seed or training MILP instances are required. We fine-tune Gemma-4-12B and Qwen3.5-4B with GRPO and a size curriculum into OptiScribe-12B and OptiScribe-4B, which generate feasible yet challenging MILP problems from natural language instructions. On capacitated facility location and max-cut, OptiScribe-12B raises median SCIP search nodes by 1.7-5x and post-cut gaps by 1.1-1.7x over its base model and improves the feasibility rate on facility location by 9-19 points, while OptiScribe-4B raises median nodes by up to 15.6x. The problems cover a wider difficulty range than public benchmarks of the same size, follow instructions on density and difficulty, and can tune solver settings for families that public libraries lack. These results indicate that optimization-specific rewards, used in self-play mode, can teach LLMs to generate high-difficulty optimization benchmarks. We will release our code and models publicly on acceptance.

This paper introduces a hybrid joint-selective optimization (HJSO) framework for large-scale numerical problems in which a small subset of trainable quantities is of primary interest. We partition the full parameter vector into a high-dimensional remaining block and a low-dimensional block of parameters of interest (POIs), perform joint first-order optimization over the full parameter set, and then freeze the remaining variables while applying a reduced-space Levenberg-Marquardt (LM) refinement to the POIs. The method is designed for settings in which the POIs are low-dimensional but strongly influence the quality of the computed solution, while the full parameter space remains too large for full-space second-order methods. The framework is evaluated on three representative problems: a matrix eigenvalue problem, an inverse Bratu problem solved with a physics-informed neural network, and a 100-dimensional nonlinear Black-Scholes problem solved with the DeepBSDE method. In each test, HJSO reaches prescribed POI-error thresholds faster than the corresponding joint first-order baseline and improves the final POI accuracy for the reported solver configurations. The contribution is therefore not a universal optimizer, but a practical reduced-space strategy for problems with known low-dimensional parameters of interest and expensive high-dimensional training variables.

Classical Inverse Optimal Transport (IOT) typically infers a cost function from a single observed transport plan, which may be sensitive to noise and observational biases in practice. To address this limitation, we propose the Multi-Observation Inverse Optimal Transport (M-IOT) framework, which learns a universal cost function from multiple transport plans. We reformulate the resulting bilevel optimization problem into a tractable single-level convex program and characterize the existence and geometric structure of the optimal solution set. Moreover, we propose a Block Coordinate Descent with Anderson-type Extrapolation (BCDwAE) algorithm and establish its Q-linear convergence. Extensive experiments on synthetic data, urban mobility flows, and e-commerce recommendations demonstrate that M-IOT reduces recovery error compared to single-observation baselines and extracts robust structural patterns from noisy multi-view data.

This paper continues our work on the convergence rates of moment-SOS hierarchies via approximation of truncated moment sequences. We extend the method developed for the Schmüdgen-type hierarchy to the Putinar-type, Krivine–Stengle-type, extended-Handelman-type, and Hol-Scherer-type hierarchies. The main idea is to lift a pseudo-moment sequence to a simple set, approximate it by a moment sequence, and project the atoms of a representing measure onto the original feasible set. The Łojasiewicz inequality then converts the error in the defining constraints into an error in the moments. With the Łojasiewicz exponent $0<L\leq 1$, we obtain the convergence rates $\mathrm{O}((\log_2 r)^{3L/2}/r^{L})$ for the Putinar-type hierarchy and $\mathrm{O}(1/r^{L/2})$ for the normalized Krivine–Stengle-type and extended-Handelman-type hierarchies. In the matrix setting, we utilize a Chebyshev-type kernel on $[-1,1]^n$ to derive the rate $\mathrm{O}((\log_2 r)^{3L/2}/r^{L})$ for the Hol-Scherer-type hierarchy. Together with our preceding work, the results provide a universal method for studying convergence rates of different types of moment-SOS hierarchies.

Permanent air-quality networks are expensive to install and maintain, yet many decisions depend on one future regional exposure rather than the complete pollution field. We introduce Target-Aware Permanent Sampling (TAPS), a graph-diffusion framework for selecting permanent locations observed repeatedly over time, that can reduce unnecessary sensor installations, maintenance, and cost while preserving the information needed for future air-quality decisions, subject to validation with the estimator that will use the network. We formulate the permanent space-time sampling problem and show that, in the noiseless model, recovery of one prescribed target can require less information than full-state identification, for which we give an explicit lower bound on the permanent-location count. We also derive a greedy rule whose marginal gain factors into raw target response and a finite-update correction. We evaluate TAPS on regulatory air-quality networks in California, Canada, and England. In each case the prescribed regional target becomes numerically recoverable at permanent-location budgets well below those required to identify the retained state, and TAPS attains lower regularized target risk than target-weight, geometric, and design-based placements. A blind prospective study further shows that the criterion can be applied before candidate sites have any ground-monitor history, using exogenous environmental covariates alone.

The semidefinite linear complementarity problem associated with the multiplicative map $M_A:\mathbb{S}^n\to\mathbb{S}^n$ defined by $M_A(X)=AXA^T$, is considered, in the case when $A\in\mathbb{R}^{n\times n}$ has rank one. A linear map is said to have the $Q_0$-property if every feasible instance of the associated complementarity problem admits a complementary solution. We prove two sharp, complementary results. When $A=xy^T$ with $x,y\in\mathbb{R}^n$ linearly independent, we construct a matrix $Q\in\mathbb{S}^n$ for which the associated semidefinite complementarity problem is feasible, but possesses no complementary solution; proving that $M_A$ does not have the $Q_0$-property. Conversely, when $A=uu^T$ for some nonzero $u\in\mathbb{R}^n$, we prove that $M_A$ has the $Q_0$-property. These two results provide a complete characterization of the $Q_0$-property within the family of rank-one multiplicative maps.

This work is concerned with the numerical computation of Gross-Pitaevskii ground states using the tensor train (TT) format. We regard the problem as the minimization of the Gross-Pitaevskii energy functional under a unit mass constraint, and propose a first-order Riemannian optimization scheme that preserves both the mass constraint and the low-rank representation throughout the optimization, by operating on the manifold of unit-norm functions of fixed TT-rank. On this manifold, we derive the energy-adaptive Riemannian gradient and show how to compute it efficiently in the TT format. Spatial discretization is performed using a spectral method with numerical integration, which allows the required computations to be carried out efficiently while preserving the low-rank format. The method is shown to substantially reduce computational time compared to full-rank computations, while maintaining accuracy for both single- and multicomponent Gross-Pitaevskii equations.

We study how actuator rank and control horizon jointly determine worst-case control performance for finite-dimensional linear systems under a fixed total actuator-gain budget. The design variable is the input covariance $X=BB^\top$. Scalar actuators give rank-one matrices $X=bb^\top$; dropping the rank constraint yields their convex hull and a semidefinite benchmark. We identify regimes in which low-rank designs necessarily fall short and others in which they attain the benchmark. At small time, the relaxed maximizer is unique and full rank. If $A$ is cyclic, then, for every $k

We study when logarithmic regret is attainable in structured adaptive linear-quadratic regulation. The state and input matrices depend affinely on a common unknown parameter. We consider neighborhoods of a known nominal model that is stabilizable and observable through the output associated with the state cost, with radii proportional to the inverse fourth root of the horizon. The key condition is controller identifiability, which requires the optimal gain derivative to vanish in every parameter direction that leaves the closed-loop dynamics unchanged under nominal optimal feedback. Under suitable regularity conditions on the noise density, this condition at the nominal parameter yields logarithmic local minimax regret when the gain derivative there is nonzero. Failure of the condition yields square-root local minimax regret. If the nominal gain derivative vanishes, local minimax regret remains bounded. We prove that controller identifiability is equivalent to the optimal gain remaining unchanged under sufficiently small invisible perturbations of the nominal model. Motivated by this invariance, we construct a certainty-equivalent policy that estimates only the visible parameter component and attains the logarithmic upper bound under controller identifiability. The policy requires neither the horizon nor the noise law, and its guarantee holds for independent, identically distributed noise with zero mean and finite positive definite covariance.

Saddle-point problems play an important role in modern machine learning, including robust optimization and algorithmic fairness. We investigate structured convex–concave minimax problems where the primal variable lies in a high-dimensional, unconstrained space $\mathbb{R}^d$, while the dual variable is confined to a constrained, low-dimensional space $\mathbb{R}^J$, with $J\ll d$. Although existing theoretical frameworks establish that an accelerated rate of $\mathcal{O}(L/T^2)$ is possible, solving the associated subproblems efficiently can become a computational bottleneck in high dimensions. To address this, we introduce a decoupling technique. By restricting second-order updates to the low-dimensional dual space and employing first-order methods in the high-dimensional primal space, our framework combines Newton methods with Nesterov acceleration. For simplex-constrained dual variables and regularizers compatible with a self-concordant barrier, the resulting algorithm achieves a convergence rate of $\mathcal{O}(L/T^2)$ in primal objective suboptimality after $T$ outer iterations, without strong dual concavity. The additional linear-algebra cost per outer iteration is $\widetilde{\mathcal{O}}(dJ^2+J^{3.5})$, alongside one evaluation of the component losses and their Jacobian.

Multistage Stochastic Programming requires scenario trees that accurately approximate the unknown underlying uncertainty process without violating the non-anticipativity constraint. Most of the existing method for scenario tree generation usually target just one of the two goals at the expense of the other, and just some recent methods try to simultaneously address both. In this paper, we propose to combine two recent distances from Optimal Transport Theory, specifically the ultrametric Gromov-Wasserstein and the Fused Gromov-Wasserstein, into a unique measure to simultaneously deal with the two goals. Our main result is a stability theorem showing that the optimal value of a Multistage Stochastic Programming problem changes by an amount controlled by a Holder-type power of the proposed distance between the true process and its scenario tree approximation, extending Wasserstein-based stability results to control marginal fidelity and non-anticipativity, simultaneously. We propose a block coordinate descent algorithm for the our scenario tree generation based on the proposed distance, and evaluate it on different inventory management test cases.

The bilevel program is an optimization problem in which the constraint involves solutions to a parametric optimization problem. It is well known that the value function reformulation provides an equivalent single-level optimization problem, but it results in a nonsmooth optimization problem that never satisfies the usual constraint qualification, such as the Mangasarian–Fromovitz constraint qualification (MFCQ). In this paper, we study necessary optimality conditions for nonsmooth bilevel programming using tangential subdifferentials. We derive a sequential enhanced tangential Fritz–John type condition for a class of nonsmooth nonlinear programs and then obtain corresponding enhanced tangential Fritz–John and enhanced tangential Karush–Kuhn–Tucker (KKT) systems by taking limits of the sequential condition. We further investigate tangential constraint qualification conditions, including T-quasinormality and a tangential cone–continuity property (T–CCP), and analyze how they guarantee the validity of tangential KKT type conditions. Finally, these results are applied to the value-function reformulation of a bilevel programming problem.

We study the learning dynamics of fine-tuning a policy model on self-generated and reward-weighted data, with particular focus on a generalized version of REINFORCE – referred to as RE(S) – that updates the rollout distribution once every $S \ge 1$ gradient steps. Prior work in bandits and reinforcement learning has developed rich theory for policy gradient methods, and on-policy sampling (i.e., a small $S$, ideally $1$) is often viewed as crucial to their success; yet in prominent application like post-training large language models, reward-guided self-training has proved to be effective even when the rollout distribution is updated infrequently, but theoretical understanding remains limited for the convergence properties of these off-policy methods. To bridge these gaps, we develop a unified theory for RE(S) that covers the full spectrum of $S \ge 1$: it can be interpreted as a stage-wise optimization process, where each stage takes $S$ gradient steps for minimizing the Kullback-Leibler distance to a fixed reward-weighted rollout distribution. For multi-arm bandits with softmax policies, our in-depth analysis and numerical experiments reveal three key findings: (1) for any fixed $S$, RE(S) enjoys global convergence to the optimal policy as the number of rollout distribution updates $B = \lfloor T / S \rfloor \rightarrow \infty$, where $T$ denotes the number of gradient steps; (2) we prove tight two-sided bounds showing that the suboptimality gap of RE(S) achieves an asymptotic $\Theta(1 / T)$ convergence rate, while $S$ only affects the length of a burn-in phase; (3) when initialized at a weak policy with a small optimal-action probability, RE(1) gets trapped around suboptimal policies for a long period, whereas RE(S) with a suitable $S$ avoids the detour and achieves significantly faster convergence to the global optimum, highlighting the benefits of off-policyness in this case.

We study the approximation of finite-energy Sobolev functions by bounded Sobolev functions for integral functionals associated with possibly signed Carathéodory integrands. The approximating sequence is required to converge strongly in the Sobolev space, while the corresponding energy densities converge in \(L^1\). Ordinary truncations may fail because they replace the gradient by zero on the tails, where the integrand need not be integrable. Our main contribution is a general method based on spatially dependent barriers whose gradients can be adapted to the structure of the Lagrangian.

We study the approximation of finite-energy Sobolev functions by bounded Sobolev functions for integral functionals associated with possibly signed Carathéodory integrands. The approximating sequence is required to converge strongly in the Sobolev space, while the corresponding energy densities converge in \(L^1\). Ordinary truncations may fail because they replace the gradient by zero on the tails, where the integrand need not be integrable. Our main contribution is a general method based on spatially dependent barriers whose gradients can be adapted to the structure of the Lagrangian.