Papers

Consider the problems of computing $\ell_p$-Lewis weights, Kelly portfolios, D-optimal designs, general equilibria in Fisher markets, and optimal error exponents for channel coding in information theory. All of them can be formulated as optimization problems over the probability simplex, but except for the last one, the associated objective functions are neither Lipschitz continuous nor smooth, rendering existing first-order optimization algorithms and their guarantees not directly applicable. Nevertheless, first-order algorithms for solving these problems do exist in the literature and, perhaps surprisingly, look very similar, even though their interpretations, derivations, and analyses mostly appear unrelated. In this paper, we develop a framework unifying these results that captures their common problem structure through log-homogeneity and a novel second-order condition on the objective function, and identifies their common algorithmic pattern as multiplicative gradient methods. The framework recovers known algorithms and their optimization error guarantees for computing Kelly portfolios, D-optimal designs, optimal error exponents for channel coding in classical communication, $\ell_p$-Lewis weights with $p < 2$, and general equilibria in Fisher markets. To illustrate the insights provided by the framework, we further show that multiplicative gradient methods yield state-of-the-art performance guarantees for computing $\ell_p$-Lewis weights with $p > 2$ and optimal error exponents in classical-quantum communication. Both results are novel to the best of our knowledge.

In this paper we deal with the celebrated Gamow liquid drop model, namely, for $m>0$, $N\geq 2$ and $\alpha\in (0,N)$, we study the problem \[ \min\Big\{P(\Omega)+ V_\alpha(\Omega) : \Omega\subset \mathbb{R}^N,\;|\Omega|=m\Big\}\,, \] and focus mostly on the nonexistence of minimizers for large masses. First we show that any possible minimizer in the asymptotic regime must satisfy an optimal thickness property. Eventually, in the simplified setting of sets made up as a tiling of cubes, we show that nonexistence occurs for large masses for the whole range of parameters $N\geq 2$ and $\alpha\in (0,N)$.

We study the query complexity of finding an an $\varepsilon$-stationary points of a one-dimensional non-convex function whose $p$-th derivative is $\beta_p$-Hölder continuous. We determine the optimal complexity for deterministic and randomized algorithms and for oracles that return only derivatives, only function values, or full local information. Randomness provably helps when only derivatives are available, function values help in all cases, and higher-order derivatives never do. Together with known results in higher dimensions, this shows how these benefits depend on the dimension. Our deterministic lower bound also implies that the optimal accuracy exponents of objective-function-free adaptive regularization of order $p$ (OFFAR$p$) in every dimension $d\ge1$ and of deterministic gradient-only trapping in dimension $d=2$.

We establish a functional-analytic framework that justifies the LaSalle convergence argument outlined in [van der Schaft, 2026] on port-Hamiltonian primal-dual gradient dynamics for finite-horizon optimal control of linear systems. In addition to strict convexity of the running cost as in \cite{vanderSchaft2026PDGJuly}, our analysis requires global Lipschitz continuity of the cost gradient. This ensures that the nonlinear gradient operator is well-defined and Lipschitz on the entire underlying space. We establish global well-posedness of the optimizer dynamics: every initial value determines a unique global mild solution, and the associated solution operators form a contraction semigroup. Similar to [Gernandtand Schaller, 2025], this is proved using tools from maximal monotone operator theory. Assuming existence of an optimal solution, we combine a dissipation inequality with an infinite-dimensional LaSalle invariance principle to prove strong convergence of every trajectory with a relatively compact positive orbit to the unique optimal state, control, and costate. Moreover, we present a sufficient condition for compactness through uniform control regularity and show that convergence holds for all initial states. Finally, we present an example with a strictly but not strongly convex running cost for which every mild solution converges strongly to the unique equilibrium, while no global exponential estimate uniformly over initial values can be obtained.

We study the exponential map on the group of real two-by-two matrices with determinant one, endowed with a left-invariant Riemannian metric. Using the Euler-Poincaré equation and its linearization, we determine the conjugate and Maxwell times and identify a domain on which the exponential map is a global diffeomorphism onto the complement of the Maxwell stratum. This provides an alternative proof that the first Maxwell time coincides with the cut time. We obtain an explicit matrix description of the cut locus and characterize the globally minimizing geodesics. Furthermore, we analyze the first Maxwell-time function, determine its unique global minimum, and show that the injectivity radius is $\frac{\pi \sqrt{14}}{4}$. Finally, we characterize the intersection of the cut and conjugate loci and prove that every geodesic is equi-optimal.

Existing cumulative regret guarantees for Bayesian optimization (BO) do not necessarily characterize the quality of the algorithm's final output. This gap is critical under noisy evaluations, where the goal is to return a single high-quality recommendation. To address it, we introduce efficient exploration strategies that can be incorporated into any BO procedure by occasionally replacing the acquisition query with an exploration query. To validate this approach, we bound the Gaussian process posterior standard deviation over the search space via the fill distance of the queries, which measures the largest region left unexplored. We then use this result to derive upper bounds on the inference regret, i.e., the gap between the global optimum and the function value at the algorithm's returned point. Empirically, these exploration strategies improve the final recommendations of existing BO algorithms on synthetic benchmarks, hyperparameter optimization, and a control task.

We study the price of anarchy (PoA) in nonatomic routing games as a function of the full vector of origin–destination demands. We show that the Beckmann value function is continuously differentiable on the positive demand cone, with gradient equal to the equilibrium origin–destination cost vector; hence the PoA is continuously differentiable on the regular demand region. We prove that the nondifferentiability set has Lebesgue measure zero and, when every edge cost is strictly increasing or constant, is covered by countably many codimension-one submanifolds. Under the same cost structure, all equilibrium objects are cellwise as smooth as the edge costs. For affine costs, the exceptional sets become finite unions of lower-dimensional polyhedral cells linked by an exact scaling law, and the maximum of the PoA over a cell closure is attained on the cell boundary, generalizing the one-dimensional endpoint result. The theory is illustrated on the Sioux Falls benchmark network.

We study the convexification of sets defined by box constraints and bilinear inequality constraints in which all bilinear terms share a common variable. For this structured class of nonconvex sets, we provide a complete characterization of the extreme points of the convex hull and derive an explicit description of all facet-defining inequalities, thereby obtaining a full polyhedral description of the convex hull. In addition, we develop a polynomial-time separation algorithm for the facet-defining inequalities and illustrate its effectiveness through examples. These results offer both structural insight into the geometry of the convex hull and algorithmic tools for identifying violated inequalities.

This paper develops a sector-constrained guidance (SCG) law for interception of a maneuvering target while maintaining a prescribed approach geometry. The line of sight is required to remain within a specified angular sector behind the target throughout the engagement, resulting in a state-constrained guidance problem. To enforce this constraint, the directional angle between the target heading and the line of sight is mapped from the prescribed sector to an unconstrained coordinate using a sigmoid diffeomorphism. A guidance law is then designed in the lifted coordinate to generate a desired transverse velocity and corresponding pursuer lead angle. The desired lead angle is tracked through an inner-loop turn-rate controller, which is implemented through the normal-acceleration command of a nonlinear point-mass model. This construction embeds the sector constraint directly into the guidance law and does not require online constrained optimization. Numerical simulations against a maneuvering target show that SCG achieves interception while maintaining the prescribed rear-sector constraint, including when the pursuer normal-acceleration command is subject to actuator saturation. Comparisons with proportional guidance under the same engagement conditions demonstrate that proportional guidance may achieve interception but does not maintain the prescribed directional constraint.

This paper presents a constraint-enforcing control framework for a class of discrete-time strict- feedback nonlinear systems. The objective is to guarantee closed-loop stability while ensuring forward invariance of a prescribed safe set defined by state constraints. The pro- posed approach transforms the constrained control problem into an equivalent unconstrained one through smooth constraint-lifting mappings constructed using strictly increasing sigmoid functions. Controller synthesis is then performed in the lifted coordinates, enabling recursive backstepping design while preserving the admissibility of the constrained states. Conditions on the controller gains are derived to guarantee both asymptotic stability of the closed-loop system and forward invariance of the admissible domain of the lifting functions. The analysis also establishes a conditional deadbeat property for the second backstepping step once the system trajectory enters a region in which the lifting-domain admissibility conditions are satisfied. Numerical simulations of a constrained Roup oscillator demonstrate the effectiveness of the proposed method in enforcing state constraints while tracking a reference command.

We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [KPV13]. Both bounds are tight for polynomial-time algorithms unless NP=RP [KPV13]. The information-theoretic limits for OSW, in contrast, remained open. This prompted researchers to ask for tighter upper bounds [Mehta13] or conjecture the existence of better-competitive (slow) algorithms [Huang23, LTX+23, CHS24, Huang2024, HTW24}. We resolve Mehta's question and refute the subsequent conjectures, proving that the greedy algorithm is in fact tight for both adversarial and i.i.d. arrivals, regardless of computation time. Seemingly contradicting recent $(1-1/e)$-competitive fractional algorithms for OSW [HJP+24,Patton26], we show that this impossibility even holds for fractional algorithms, provided their outputs correspond to marginals that are roundable in hindsight. Conceptually, our proofs can be seen as identifying that a bottleneck for OSW, even under (deterministic) adversarial arrivals, is the inherently random notion of correlation gap [ADSY12].

Households compare their living standard with others' and dislike changing it. We study consumption and investment when felicity depends on consumption relative to a benchmark, the population's geometric average consumption, and cuts in felicity weigh more than increases. Asset returns are exogenous. For finitely many types and arbitrary initial wealth and inherited standards, a mean field equilibrium exists under a weak interaction condition, and for fixed budget multipliers the benchmark is the fixed point of a contraction. In a complete market with common risk, a mean field equilibrium at empirical type frequencies is an exact Nash equilibrium of the finite game, for any preferences over relative consumption. We bound the gain from deviating when plans computed at another composition are used. We compute equilibria in which groups with different wealth, inherited standards, and loss aversion revise spending at different dates. With identical households and common risk, the unique symmetric equilibrium is the policy of a single loss averse household with modified curvature. In a baseline example, ignoring the inherited standard costs up to 17% of wealth, while small errors about the composition of the reference group cost less than 0.5%.

We consider the problem of computing Taylor approximations to the optimal feedback law and value function for infinite-horizon finite-dimensional nonlinear optimal control problem—also known as Al'brekht's method. The scalability of existing Al'brekht-based approaches to computing approximate solutions to the Hamilton-Jacobi-Bellman equation associated with the optimal control problem has been severely limited by computational resources. The computational time issue has been partially mitigated by recent works leveraging tensor-structure to develop efficient numerical methods. However, RAM requirements still have remained a major hindrance to scaling beyond state dimensions of a few hundred or low thousands. We propose an acceleration to compute the expensive higher-order terms in a reduced space, mitigating the curse of dimensionality. A fast and scalable Matlab implementation is provided open-source for general purpose use, with the ability to accommodate arbitrary polynomial nonlinearities in the control-affine state equation, as well as polynomial state-dependence in the cost function, and the ability to handle systems in generalized form with a non-identity mass matrix, such as finite element models. Combined with the exploitation of sparsity and modern low-rank Riccati solvers, this permits computing approximations to polynomial feedback laws based on Al'brekht's method in hundreds of thousands of states.

The set \(P_{n}\) consists of the characteristic vectors of pedigrees, which are combinatorial encodings in one-to-one correspondence with Hamiltonian cycles. For \(n \geq 4\) and \(\tau_{n} = \binom{n}{3}-1\), the Membership Problem for the Pedigree Polytope (M3P) asks whether a given vector \(X \in \mathbb{Q}^{\tau_{n}}\) belongs to \(\mathrm{conv}(P_n)\). This paper gives a complete account, with the full proof statements and machine-verified Lean~4 certificates, of the necessary and sufficient (\NS) condition established in Chapter~5 of Pedigree Polytopes: New Insights on Computational Complexity of Combinatorial Optimisation Problems (Arthanari, 2023): membership of $X$ in $\mathrm{conv}(P_n)$ is characterised by the feasibility, at every stage $k=4,\dots,n-1$, of a recursively constructed layered network, together with, when needed, a multicommodity flow problem $\mathrm{MCF}(k-1)$ achieving its maximum possible flow $z_{\max}$. We present the construction, the \NS{} condition itself, and the proofs of this characterisation, together with the resulting polynomial-time algorithm for M3P. Both directions of the \NS{} condition — sufficiency and necessity (the multicommodity-flow feasibility argument of the book's Chapter~5) — are machine-verified in Lean~4/Mathlib4 with zero unresolved sorrys in either dependency chain. The \NS{} characterisation therefore follows directly from the two machine-checked implications. The complete Lean~4 project is publicly available. A companion introductory article (arXiv:2507.09069) presents the same material for a broader readership, without the Lean~4 verification; the present paper adds full statements, proof sketches, and the complete machine-checked certificates.

The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $\Theta(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.

We study the $p$-Bures-Wasserstein distance $D_p(A,B)=(\mathrm{tr}\,A^p+\mathrm{tr}\,B^p-2\|A^{1/2}B^{1/2}\|_p^p)^{1/2}$ on positive semidefinite matrices; it equals the Bures-Wasserstein distance for $p=1$, and the Hilbert-Schmidt distance for $p=2$. We prove that $D_p$ is a metric for every $1\le p\le2$, by proving a stronger 2014 conjecture of Lin and van den Driessche on $3\times3$ block matrices. Our main tool is a partition inequality for Schatten norms, proved by complex interpolation. We also characterize Fréchet means for $D_p$ by a fixed-point equation and prove geometric convergence of the associated iteration.

We study stationary discrete-time mean-field games with finite state and action spaces under the average-reward criterion, with an entropy-regularized objective and population-dependent dynamics and rewards. Under a minorization condition, the soft Q-operator is a span-seminorm contraction for the full transition kernel, so relative value iteration does not require the minorizing measure. When the Lipschitz constant of the kernel is below the minorization mass and the temperature exceeds an explicit threshold, the equilibrium fixed-point operator is a contraction: an equilibrium exists, its population distribution is unique, and a fixed-point iteration converges to it geometrically. We then learn the equilibrium model-free from a simulator, combining soft Q-learning at a fixed population distribution with an empirical transition kernel. We prove a finite-sample bound for soft Q-learning in the span seminorm, with temperature-independent constants, and derive convergence rates for the learned population distribution and policy. A congestion-aware routing game illustrates the results.

Ordinal optimization selects designs that are good enough rather than optimal when evaluation is expensive and the budget is small. The alignment probability measures the chance that the selected set contains at least a prescribed number of truly good designs. We formulate quantum ordinal optimization as a class of problems that maximize this probability under a fixed oracle budget. We study exact, coherent pairwise comparisons with one selected design as a first instance, with the budget counted in comparison queries. For every classical comparison budget smaller than the number of designs, we prove that a knockout among uniformly sampled designs attains the optimum. The sample is drawn without replacement and contains one more design than the number of comparisons. For a uniformly random order, the selected design's rank has a polynomial probability law. At the same comparison budget, the maximum quantum degree is at most twice the classical maximum, a factor attained whenever there are more than twice as many designs as comparisons, so a quantum algorithm can realize rank laws that no classical algorithm with the same budget can. We determine the exact quantum optimum with one comparison for every number of designs and every good-enough set. For selecting the best of n designs, the optimal success probability with one quantum comparison is approximately 3.30/n for large n, compared with 2/n for one classical comparison. When the best design is sought, one quantum comparison gives a higher alignment probability than two classical comparisons whenever there are more than nine designs.

We study the homogenization of an optimal control problem governed by a Navier-Stokes-Cahn-Hilliard system in a periodically perforated three-dimensional domain. The obstacles are Lipschitz sets of size $\varepsilon^\alpha$, $\alpha>3$, where $\varepsilon$ is the period. The fluid satisfies the no-slip condition on the outer boundary and the free-slip condition on the obstacles, the phase-field equation contains a source term, and the convective term carries a pore-scale Reynolds number that tends to zero as $\varepsilon\to0$. The control is a distributed body force, and the cost functional tracks the velocity in $L^2$ and the order parameter in $H^1$. Since uniqueness of weak solutions of the state system is not known for fixed $\varepsilon$, the control-to-state relation is multivalued, and we pose the microscopic problems over control-state pairs. We prove the existence of microscopic optimal pairs and the sequential $\Gamma$-convergence of the cost functionals to the cost functional of a control problem governed by the unsteady Stokes-Cahn-Hilliard system on the full domain. As a consequence, the optimal values converge, every cluster point of microscopic optimal pairs is optimal for the homogenized problem, and the optimal controls converge strongly along the corresponding subsequences. The $\liminf$ inequality follows from the homogenization of the state system, including the strong convergence of the gradients of the order parameter. Only the recovery sequence requires uniqueness of weak solutions of the homogenized system, which we prove when the outer boundary is of class $C^{2,1}$.

Nonlinear Constrained Optimisation (NCO) requires simultaneous satisfaction of the Karush-Kuhn-Tucker (KKT) conditions. Existing methods enforce these conditions through projections, penalties, barriers, or sequential approximations, potentially introducing computational complexity and convergence difficulties. For nonconvex problems, a KKT point need not be a local optimum. This paper reformulates NCO as stabilisation of a unified KKT sliding residual manifold and develops SM-KKT, a projection-free solver. Stationarity, equality feasibility, and regularised Fischer-Burmeister complementarity are integrated into a unified residual system, with complementarity encoding inequality feasibility, dual feasibility, and complementary slackness. The manifold's zero set is shown to be equivalent to the KKT conditions. The required Jacobian saddle-point inertia is characterised and shown, under stated assumptions, to be equivalent to the simultaneous satisfaction of the Linear Independence Constraint Qualification (LICQ) and Second-Order Sufficient Condition (SOSC). This characterisation establishes local stability of the structured correction algorithm under these conditions and distinguishes nondegenerate locally optimal KKT solutions from points failing second-order optimality. SM-KKT computes structured primal–dual corrections and applies a discrete sliding reaching law to drive the KKT residual into a prescribed boundary layer in finite time. Four nonlinear benchmarks show recovery of reference constrained optima with KKT residuals below $10^{-6}$, earlier boundary-layer reaching, and favourable KKT accuracy compared with projected primal-dual, augmented-Lagrangian, quadratic-penalty, and log-barrier baselines.

We study federated learning from continuously arriving data: each client samples from its own distribution, these distributions drift over time, and the server must track the minimizer of the clients' weighted average loss. Clients are not alike as they collect data at different rates, with different noise, and change at different speeds. The main question is how much history should each one keep? A single shared window must serve every client at once, and so makes a fast-changing client carry the sampling noise of a slow, nearly stationary one. We give each client a memory of its own, sized to that client's noise, arrival rate, and drift, and refresh it by restarted accelerated method that starts from a common point. The tracking error is then bounded by \[ R\left(\sum_m w_m^{3/2}\,\sigma_m\sqrt{\gamma_m/\lambda_m}\right)^{2/3}, \] for clients with weight $w_m$, noise $\sigma_m$, arrival rate $\lambda_m$, and drift rate $\gamma_m$ on a domain of diameter $R$. This is never worse than what any common window can achieve, and strictly better whenever noise and drift are spread unevenly across clients. A lower bound that puts different groups of clients on different drift clocks shows this quantity is the right one. The two bounds agree up to a constant whenever the clients occupy boundedly many refresh scales, and in general differ only by the sixth root of the number of scales. Experiments show the gain comes from the memory rather than from the solver: it persists across accelerated, stochastic-gradient, and one-step methods, and against a separately tuned common-memory baseline.

Non-firm connection products can accelerate grid access while reinforcements are delayed, but their planning value depends on evidence supporting the contractual promise. We develop a one-way evidence-to-access framework for calendarized products. Stage A constructs and fixes directional restriction calendars from public residual-load and day-ahead price-timing signals. Stage B audits the submitted calendar and one bounded common repair, tests joint threshold attainability under the shared annual budget, and applies an aggregation-aware Power Transfer Distribution Factor (PTDF) certificate. Stage C treats the resulting ledger as fixed in queue-aware allocation and intervention planning. In the primary policy-package evaluation, the evidence-supported menu returns the same $2.119$~GW allocation as firm-only access, whereas authorizing the uniformly derated fallback raises awards to $6.442$~GW and reduces backlog from $136.076$ to $113.601$~GW-years; all $4.489$~GW of non-firm awards use the fallback. In a target-free matched control, evidence-routed and state-blind fallback menus attain primary objectives equivalent within EUR~1 and return the same accepted applicants, award years, routes, and intervention portfolio. Thus, in the reported testbed, fallback authorization rather than calendar-specific evidence support drives the access-volume effect.

We completely classify cyclic steepest descent (CSD) on strictly convex quadratics whose Hessian has exactly two distinct eigenvalues. At the beginning of each cycle CSD recomputes an exact steepest-descent stepsize and reuses it for $m$ updates. For every $m\ge2$, write $A=aP+bQ$ with $0<a<b$ and spectral projectors $P,Q$. For nonzero spectral blocks, let $r=\|Pg\|_2/\|Qg\|_2$ at a cycle boundary. The exact projective dynamics is $r^+=r^{1-2m}$. Hence the nonzero equal-norm cone $\|Pg_0\|_2=\|Qg_0\|_2>0$ is precisely the nonterminating exceptional set: there the convergence is $R$-linear with factor $(b-a)/(b+a)$, whereas every other nonterminating initialization is $R$-superlinear and one-eigenspace initializations terminate in one step. The exceptional cone has Lebesgue measure zero, so $R$-superlinear convergence holds almost everywhere in this two-spectrum class. The main results of this paper were obtained through a generative-AI workflow using OpenAI GPT-5.6 Sol, Anthropic Claude Fable 5, and OpenAI GPT-6 Astra. Further details appear in the disclosure at the end of the paper.

Hoffman constants quantify the distance to the solution set of a polyhedral system in terms of its residual; they control error bounds, geometric conditioning, the convergence rate of first-order iterative algorithms, and the stability of regression estimators to target perturbations. Despite their importance, explicit values of Hoffman constants are rarely available due to their computational complexity. In this paper, we derive explicit bounds on the Hoffman constant for a class of structured polyhedral systems arising in sparse regularization. We show that the constants admit a decomposition into spectral, geometric, and interaction components, which together determine their scaling behavior. This framework explains the gap between worst-case dimension-dependent bounds and the favorable conditioning observed empirically in structured problems. As a primary application, we analyze $\ell_1$-regularized least squares, demonstrating that the effective constants depend on low-dimensional active subspaces rather than the ambient dimension. We then extend to the elastic net and adaptive $\ell_1$-regularized formulations, demonstrating how the underlying optimization geometry is altered by the $\ell_2$ penalty and reweighting scheme. Furthermore, we relate our results to classical statistical assumptions and show that the restricted eigenvalue condition bounds only the primal curvature of the active set, leaving the dual interaction geometry unconstrained and is thus insufficient alone for fast theoretical convergence rates. We further show standard $\ell_\infty$ coherence conditions do not yield dimension-independent Euclidean bounds to close this gap. Our theoretical results show that Hoffman constants admit explicit, interpretable forms in structured regression settings and, in practice, provide actionable tools for post-hoc feature pruning and a priori optimal hyperparameter selection.

Recent observations that deep learning models train at the edge of stability have renewed interest in understanding stability properties of classical optimization algorithms. For quadratic objectives, standard gradient descent has a sharp stability threshold: it converges from every initialization when $\eta<2/L$, diverges from almost every initialization when $\eta>2/L$, and diverges from every nonzero initialization when $\eta>2/\mu$. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when $\eta<2/S$, where $S$ is the generalized sharpness, while every nonzero initialization diverges when $\eta>2/\mu$. The behavior in the intermediate regime $2/S<\eta<2/\mu$ is not fully characterized. We show that Hilbertian norms are the only ones for which $2/S$ is an almost-everywhere sharp threshold for every positive-definite quadratic objective. Using linear conjugacy between non-Euclidean and Euclidean gradient descent, we show that for general norms the intermediate regime can contain arbitrarily many edges of stability associated with distinct attracting directions. We identify a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold. When the directions of minimum curvature are finite and nondegenerate, we prove that, sufficiently close to $2/\mu$ from below, only their invariant directions remain convergent. We give smooth two-dimensional constructions with arbitrarily many distinct thresholds, arbitrarily large relative threshold separation and show these properties to be stable.

We develop an adaptive Galerkin neural-network method for computing minimum-$L^2$-norm interior controls for wave equations with spatially varying coefficients. Within the Hilbert Uniqueness Method, adjoint waves are approximated directly in space-time by least-squares Galerkin projections onto trial spaces enriched by neural-network basis functions selected through residual-based training. Linear Galerkin solves determine the adjoint approximations, and a separate linear system reconstructs the control. The least-squares objective provides an indicator for adaptive enrichment and stopping; the experiments use a Ritz-based terminal-data version whose continuous-error interpretation additionally requires an eigenpair consistency estimate. The main difficulty is that adjoint errors perturb this reconstruction system. Assuming observability of the continuous equation, we derive sufficient stability conditions involving a worst-case factor $\sqrt{n}$ multiplying the maximal adjoint error, where $n$ is the number of retained terminal modes. A fully discrete error estimate separates terminal-space truncation, adjoint approximation, and assembly errors, yielding convergence to the minimum-norm control when the truncation error, the $\sqrt{n}$-weighted adjoint error, and the assembly errors tend to zero as $n$ grows. For spectral terminal bases, additional regularity and uniform contraction assumptions yield quantitative convergence rates and show that $O(\log n)$ accepted enrichment steps per mode suffice to balance the neural and truncation errors. Numerical experiments on a nonconvex Cassini oval, a square containing a low-speed lens, and a three-dimensional ball with a graded coefficient illustrate the method.

We study stochastic convex optimization, where each sampled function can be evaluated at two arbitrary points. Our accelerated method chooses step sizes, batch sizes and smoothing radii from function values. A forward difference between smoothing scales controls the radius; we account for changes in the smoothed objective. Under the stated regularity and second-moment assumptions, exact function evaluations give \begin{multline*} \mathbb{E}\bigl[f(x_N)-f(x^\star)\bigr] \le \widetilde{O}\biggl( \frac{\sqrt{d}\,M_2 D}{\sqrt{T}} +\min\biggl( \frac{L D^2}{N^2},\; \frac{d^{1/4} M D}{N}+\frac{\sqrt{d}\,M D^2}{\gamma_{\max} N^2} \biggr)\biggr). \end{multline*} Here $N,T,d,D$ denote the numbers of optimization steps and paired evaluations, the dimension and a feasible-set diameter bound, respectively. Evaluations are available within Euclidean distance $\gamma_{\max}$ of the feasible set. For the population objective $f(x)=\mathbb{E}_{\xi} F(x,\xi)$, $M$ satisfies $|f(x)-f(y)|\le M\|x-y\|_2$, and $M_2$ satisfies $\mathbb{E}_{\xi}\|\nabla F(x,\xi)\|_2^2\le M_2^2$ for sample weak gradients in the interior of the evaluation domain. The method requires no $L,M,M_2$, where $L$ is a Lipschitz constant of $\nabla f$; set $L=+\infty$ without smoothness. The method uses exactly $2T$ values in $3N$ sequential sampling rounds with predetermined batches, or $5N$ with batches chosen from observations. An extension selects a search radius without a supplied distance bound. Fixed radius parameters can leave nonvanishing error; suitable choices depending on the budgets yield convergence.

We study Nesterov's accelerated gradient method with its standard constant parameters for smooth strongly convex optimization. We characterize the exact worst-case asymptotic factor for the squared distance to the minimizer. To this end, we construct candidate worst-case trajectories by combining planar spirals with a common contraction factor that satisfy a self-similarity condition. Each component rotates by a fixed angle at every iteration. The exact factor is the optimal value of a linear optimization problem over probability measures on a fixed disk, with constraints derived from smooth strongly convex interpolation. Every optimal measure has a common contraction factor, which is also the largest factor for which the angular interpolation conditions are feasible. We also show that this worst-case asymptotic rate can be realized by a single function in a finite-dimensional space whose iterates attain this factor. A matching upper bound holds uniformly over all functions in the class and all finite dimensions. Consequently, allowing the function, dimension, and initial point to vary with the iteration horizon does not increase the worst-case asymptotic factor. We also show that the exact factor is $1-4/(3\sqrt\kappa)+o(\kappa^{-1/2})$ as $\kappa\to\infty$, where $\kappa=L/\mu$ is the ratio of the gradient Lipschitz constant to the strong convexity parameter.

Latent recursion repeatedly processes internal representations through the same neural network. Recent work has shown this approach to be effective on structured reasoning tasks such as Sudoku and maze solving. However, whether latent recursion can support neural routing remains unclear. We introduce RELAGRAM (Recursive Latent Graph Model), a novel approach that brings latent recursion to graph combinatorial optimization. RELAGRAM encodes a capacitated vehicle routing problem (CVRP) instance as edge tokens; a compact transformer recurrently updates the latent representations of these tokens. An output head maps the answer state to an edge heatmap, from which an autoregressive decoder constructs a feasible solution. On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. Trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. Together, these results demonstrate that latent recursion is a promising approach to neural routing.

Among connected, planar sets, the ratio between the isoperimetric deficit and the squared barycentric asymmetry is known to be bounded from below by a strictly positive constant (as proved in recent papers by Bianchini-Croce-Henrot and Gambicchia-Pratelli). This opens the natural question whether the infimum is attained at some set. In this paper, we prove that a minimizer for this ratio actually exists, and moreover it is simply connected.