Papers

We study acceleration of stochastic first-order methods for monotone Lipschitz inclusions with a fixed number of oracle queries per iteration, measured by the expected squared residual. Existing methods either have suboptimal oracle complexity, require an increasing number of oracle queries per iteration, or both. Under same-sample oracle access and mean-square Lipschitz stochastic noise, we develop variance-reduced anchored forward-backward (VRAF), an anytime composite method that makes two oracle queries per iteration. VRAF attains the first log-free $O(1/\epsilon)$ complexity under these oracle assumptions and hence the optimal $O(\sigma^2/\epsilon)$ variance dependence. This, however, leaves open whether the optimal $O(1/\sqrt{\epsilon})$ deterministic term can also be attained. We establish an impossibility result by extending the lower bound of Foster et al. (2019) to stochastic oracles permitting repeated queries to sampled stochastic operators, showing that $O(LD/\sqrt{\epsilon}+\sigma^2/\epsilon)$ oracle complexity is unattainable in general. We therefore develop recentered regularized stochastic extragradient (RRSEG), which attains the near-optimal oracle complexity previously achievable only with an increasing number of queries per iteration, while using a fixed number of queries.

We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central parameter for tractability: bounded treewidth yields polynomial-time solvability. Motivated by this fact, we investigate whether treewidth plays a similar role when the binary domain is replaced by the unit hypercube. We show that the situation is strikingly different. If the interaction graph is a forest, we give a strongly polynomial-time algorithm based on dynamic programming and a structural analysis of the resulting univariate value functions, which are shown to be concave and piecewise quadratic with linearly many pieces. However, the problem becomes strongly NP-hard already when the interaction graph has treewidth two. We then identify substantially more general polynomial-time solvable classes whose interaction graphs may have unbounded treewidth. Our approach exploits the fact that there exists an optimal solution in which every variable with a nonpositive coefficient for its square term is binary-valued, thereby separating the problem into a combinatorial part and a genuinely continuous part. We show that tractability can be recovered by controlling the complexity of these two parts and their interaction, rather than the treewidth of the entire interaction graph.

For probability measures on $\mathbb{R}^d$ supported in fixed compact sets, we prove that quadratic optimal transport plans are quantitatively stable in Wasserstein distance under perturbation of both marginal measures, assuming that one of the initial measures satisfies an upper Ahlfors regularity condition with exponent strictly greater than $d-1$. Under the same assumption, we also prove novel quantitative stability results for optimal transport maps. Furthermore, we prove a coercivity theorem which states that any probability measure on the product space must be quantitatively close to the set of optimal plans, if it has similar marginals and a similar transport cost to the optimal value. Finally, we prove a quantitative uniqueness theorem which acts as a quantitative counterpart to Brenier's theorem. The Wasserstein diameter of the set of optimal plans is controlled by the distance of one marginal measure to a regular measure for which uniqueness holds. In this way, "almost uniqueness" of optimal plans is quantified by the source measure being "almost regular". Examples are provided which prove that the exponents of all estimates are sharp.

We prove that $(G\circ G^{-1})^{-1}$ is entrywise nonnegative for every real symmetric positive definite matrix $G$ of order at most six, resolving the inverse relative gain array conjecture of Jeffrey Uhlmann. The proof combines an explicit sum-of-squares identity on $\Lambda^2\mathbb R^4$ with two bordering arguments. More generally, we establish an equivalence between a biquadratic inequality, a quadratic positivity property, and inverse relative gain array nonnegativity in three consecutive dimensions. As consequences, we characterize the fixed space and averaging properties of the inverse interaction operator and prove a reverse Schur–Horn majorization inequality for matrices diagonalized by real symmetric positive definite matrices. A rational example of order seven shows that both dimension bounds are sharp.

Soft Actor-Critic (SAC) is widely used for entropy-regularised reinforcement learning with continuous action spaces, and practical implementations perform only a few actor steps towards an evolving target. In this work, we prove convergence guarantees when the target policy arises from policy mirror descent and compare it with the classical Gibbs target. We derive sufficient conditions for the strong convexity and smoothness of the actor objective, characterised by the curvature of the $Q$-function estimate through the Legendre differential operator, and establish an $\mathcal{O}\!\left(N^{-\frac{1}{5}}\right)$ best-iterate finite-time convergence rate up to actor and critic approximation errors. Moreover, the mirror-descent step size $\lambda$ directly controls the target drift and hence actor tracking error, whereas the analogous Gibbs bound contains a non-vanishing tracking term.

This paper studies convex optimization when the gradient cannot be evaluated exactly, but only approximated by a hierarchy of algorithms whose compute grows like $\delta^{-\gamma}$ in the accuracy $\delta$. When $\gamma>2$, falling into the Harder-Than-Monte-Carlo (HTMC) regime, the price of accuracy outruns the variance reduction that Monte Carlo would buy and we show that minimizing a loss function costs no more, up to a factor depending only on $\gamma$, than a single evaluation of its gradient at the accuracy the problem demands. A randomized multilevel oracle replaces the deterministic approximation of accuracy $\delta$ by an unbiased estimator of it, whose variance $\sigma^2$ becomes a second, independently priced dial: the cost of one call drops from $\delta^{-\gamma}$ to $\delta^{2-\gamma}\sigma^{-2}$. Plain inexact gradient descent driven by that oracle reaches loss $\varepsilon$ at expected compute $\Theta(\varepsilon^{-\gamma})$ in the convex case, against $\Theta(\varepsilon^{-(\gamma+1)})$ for the same method run at a fixed accuracy: randomization buys a full power of $\varepsilon$. Under $\mu$-strong convexity the exponent halves, to $\varepsilon^{-\gamma/2}$, because the iterates settle at a noise floor and the bias budget relaxes accordingly. Both bounds are independent of the step size, and hence of the smoothness constant, and we show that the cost is a functional of the underlying gradient flow rather than of any discretization of it.

We study the uniform null-controllability, in the vanishing viscosity limit, of the transport–diffusion equation $u_t + M u_x = \varepsilon u_{xx}$ on $[0,L]$ with a Dirichlet boundary control at $x=0$. Our results concern the uniform null-controllability time $T_{\mathrm{unif}}$, defined as the infimum of the times for which the null-controllability cost remains bounded as $\varepsilon \to 0$. We determine this time exactly for both signs of the transport velocity: $T_{\mathrm{unif}} = 2 L / M$ in the positive-speed case $M>0$, and $T_{\mathrm{unif}} = (2 + 2 \sqrt{2}) L / |M|$ in the negative-speed case $M<0$. The positive-speed result disproves the conjecture $T_{\mathrm{unif}}=L/M$ suggested by Coron and Guerrero. For negative speed, the conjectured threshold had already been disproved by Lissy. Our result determines the exact threshold. We establish the lower bounds by constructing adjoint solutions that violate uniform observability below the respective thresholds. In the positive-speed case, the construction exploits the asymptotic structure of the Blaschke products and model spaces associated with the exponential family generated by the adjoint spectrum. The same model-space structure is used to reduce the upper-bound problems for both signs of $M$ to infinite-time observability inequalities, which are proved through a representation of the boundary-to-interior map and estimates of its Hilbert–Schmidt norm.

We study nonsmooth convex-concave saddle-point problems over compact convex sets, assuming access to stochastic subgradients of the payoff function. We develop single-loop projection-free algorithms that use linear minimization oracles over the primal and dual domains. Unlike prior projection-free approaches that rely on smoothing, our methods are purely subgradient-based and handle nonsmoothness directly. This design makes the framework modular: when a linear minimization oracle is not used over a specific domain, the corresponding update can be replaced by a standard projection oracle without changing the single-loop structure. Thus, our framework covers both fully projection-free and hybrid oracle configurations. We prove anytime strong saddle gap guarantees under standard unbiased stochastic oracle assumptions with bounded variance. Our algorithms achieve an $O(\epsilon^{-2})$ iteration complexity, matching projected stochastic subgradient methods. We also provide matching lower bounds for the corresponding oracle models, establishing minimax optimality. Our results show that, for nonsmooth stochastic minimax problems, the computational advantages of linear minimization oracles need not come at the expense of statistical or oracle efficiency.

Taxi-based mobile sensing has emerged as a cost-efficient paradigm for large-scale urban environmental monitoring. In practice, both passive and active sensing strategies are adopted by ride-hailing platforms. Passive sensing, conducted during passenger-serving trips, is constrained by stochastic and spatially imbalanced ride demand, leading to limited and uneven coverage. Active sensing, executed by vacant taxis, provides greater control over sensing operations but incurs additional operational costs, and is thus typically treated as a supplementary strategy. To address the inefficiencies of the conventional "passive-first, active-second" paradigm, which may delay the monitoring of critical Points of Interest (POIs) and increase system-wide costs, we propose a Distributionally Robust Optimization (DRO)-based framework for active mobile sensing. First, we develop an enhanced A*-based drive-by sensing routing policy that integrates vehicle-task matching while capturing both global routing efficiency and local sensing opportunities. Second, we formulate the active sensing problem as a DRO model that explicitly accounts for uncertainty in ride demand through an ambiguity set of probability distributions, enabling robust decision-making for vacant taxi routing and vehicle-task matching. The proposed framework is evaluated on both static and dynamic mobile sensing settings using real-world data. Computational results demonstrate that our approach achieves better performance in terms of sensing coverage, operational cost, and robustness compared to benchmark strategies, highlighting the value of integrating distributional robustness into taxi-based sensing operations.

We study the stochastic first-order oracle complexity of finding $\epsilon$-stationary points of the primal function in smooth nonconvex-strongly-concave minimax optimization. For sufficiently small $\epsilon$, we establish lower bounds of $\Omega(\kappa L\Delta\sigma^2\epsilon^{-4})$ under the bounded-variance assumption and $\Omega(\kappa^{3/2}\bar L\Delta\sigma\epsilon^{-3})$ under the additional assumption of averaged smoothness. Here, $L$ and $\bar L$ denote the smoothness and averaged-smoothness constants, respectively, $\Delta$ is the initial primal gap, $\sigma^2$ bounds the oracle variance, and $\kappa=L/\mu$ or $\bar L/\mu$ in the respective settings, where $\mu$ is the strong-concavity parameter. Our bounded-variance lower bound improves the dependence on the condition number from $\kappa^{1/3}$ in previous lower bounds to $\kappa$, while our averaged-smoothness lower bound is the first of its kind. In both settings, the resulting lower bounds match existing upper bounds in their dependence on $\kappa$ and $\epsilon$. Our proofs are based on a unified quadratic lifting construction that transfers a hardness instance for stochastic nonconvex minimization to unconstrained minimax optimization while preserving the required variance and smoothness properties.

We study a non-stationary queueing system with multiple parallel servers and a finite buffer capacity, over a finite planning horizon. Motivated by an operation that is central to an EV (electric vehicle) battery-swapping station – how to best manage the charging of batteries swapped off from EVs, we develop a continuous-time MDP (Markov decision process) approach to the problem. The main technical challenge is to allow both the arrival rate and the service-cost rate to be functions of time with jumps at discrete time points, key features of the EV swapping station's operation. We derive an exact and explicit threshold structure that characterizes the optimal control policy. Moreover, we give conditions under which the thresholds are monotone over time, and with respect to key system parameters such as service and buffer capacities. Extensive numerical experiments are carried out to supplement as well as validate the theoretical results, and also to illustrate the robustness of the threshold structure in practical implementations.

Successive weaving segments (SWSs) on urban expressways are bottlenecks prone to recurrent congestion and collisions, requiring fine-grained active traffic management (ATM). Existing approaches struggle to balance the adaptive performance of data-driven optimization with the resilience and transferability of model-based control. We propose a hybrid framework to coordinate lane-level variable speed limits (VSLs) and ramp metering across SWSs. First, we reconstruct L-METANET, a lane-level macroscopic traffic flow model that captures free and forced lane changes. Second, we combine XGBoost-SHAP with a random-parameters binary logit (RPBL) model to derive analytical equations for merging and diverging collision risks and formulate system cost and reward functions. Third, we develop MPC-STMAPPO, a hierarchical controller integrating model predictive control (MPC) and multi-agent reinforcement learning (MARL). Its upper MPC layer uses L-METANET for long-horizon rolling optimization and generates baseline commands; its lower spatiotemporal MAPPO (ST-MAPPO) layer, enhanced with Mamba cells and graph attention, produces residual actions for short-horizon adjustment. Real-world experiments on the 18-km Eastern Expressway in Changchun, China, show that L-METANET accurately reproduces lane-changing-induced flow redistribution and capacity drops, with state evolution aligned with ground truth. XGBoost-SHAP-RPBL achieves AUCs above 0.80 in most tasks, outperforming conventional logit models. MPC-STMAPPO converges faster and performs better across multiple metrics than MPC- and MARL-based baselines. Under randomly fluctuating demand, it also significantly outperforms pure MARL in generalization, demonstrating strong potential for industrial deployment.

We study the exact Euclidean ball-proximal point method for proper, closed, convex functions, where each iteration minimizes the objective over a ball centered at the current point. Retaining the objective gap in the decrease of squared distance yields sharper bounds on objective values, stationarity, and the symmetric Bregman distance to a minimizer. For constant radius $t>0$ and initial distance $D_0>0$ to the solution set, the objective gap after $K$ iterations is at most its initial value multiplied by $\exp(-2K^2t^2/D_0^2)$. We characterize convergence for arbitrary positive radius sequences. If their sum diverges, the method reaches a minimizer in finitely many iterations whenever one exists; otherwise, the objective values converge to the infimum and the iterates escape every bounded set. If the radii are summable, the iterates converge to a possibly nonoptimal point. Self-contraction gives finite trajectory length for bounded iterates and a constant-radius termination bound $O_d(1+D_0/t)$, whose implicit constant depends only on the dimension. A polyhedral family shows that the dimension-independent quadratic bound remains asymptotically sharp. We also identify a minimum successful geometric decay factor and analyze adaptive radius rules based on subgradients or objective gaps, epigraph reformulation, and relaxed updates. Together, these results strengthen the foundations and convergence guarantees of the method without assuming smoothness or strong convexity.

This paper studies stochastic algorithms for minimizing paraconvex functions, a function class that generalizes weakly convex functions and includes, for instance, Hölder smooth functions and compositions of convex functions with Hölder smooth maps. We first establish the convergence of the stochastic subgradient method and the stochastic proximal subgradient method for unconstrained and composite paraconvex optimization, respectively. The analysis is then extended to a broad family of algorithms that access the objective through stochastic models satisfying certain approximation-quality and continuity assumptions. The main principle that underlies the convergence analysis is that the algorithms under consideration can be interpreted as perturbed descent methods on the generalized Moreau envelope of the original paraconvex problem.

We study the loss of observability for a class of strongly coupled parabolic systems as the coupling parameter tends to zero. The system is observed through a fixed matrix $B$ on a measurable subset of space-time with positive measure. Under the Kalman rank condition, we determine the exact blow-up rates of the optimal observability cost. Different components of the state, as well as different combinations of them, may have different blow-up rates, and these rates are determined by the algebraic structure of the pair $(B,K)$. The full-state observability cost is determined by the largest of these rates. We also show that the worst-case minimum $L^\infty$-norm of null controls has the same asymptotic behavior.

Long contexts are central to modern transformer systems, but most expressivity results choose a different network for each fixed sequence length. We study whether one masked transformer can approximate causal token-to-token maps uniformly over sequences of arbitrary length sampling a fixed normalized horizon. To relate sampling resolutions, we model tokens by $\alpha$-Hölder sequences or, more generally, a common modulus of continuity. Our notion of continuity across resolutions characterizes the causal families admitting uniform approximation on these compact input classes by a single transformer with length-independent parameters. The result extends to the infinite-length mean-field limit, where tokens form continuous curves and masked attention becomes a causal time integral. For bounded regression with target maps satisfying a $\beta$-smooth stability condition defined using regular test functions, quantitative approximation yields a generalization bound: exact empirical risk minimization over suitably sized bounded-weight transformers gives root mean-square prediction error $O((\log\log N/\log N)^{\beta/(d+2)})$ from $N$ iid labeled sequences. The bound holds at fixed confidence on the same sampling distribution, with $d$ the token dimension and no maximum-length factor. Finally, experiments on physical time series support the Hölder-regular token model at observed scales, with dataset-dependent fitted exponents, whereas text input embeddings provide a contrasting case. Native and dense sampling, shuffled controls, and refinement checks delimit this empirical regularity regime.

Closed-loop planning accounts for future observation-dependent actions but can be expensive to repeat at deployment. Bellman-gradient (BG) refinement differentiates conditional rollouts through an existing actor, corrects the current action, and stores the result in an executable policy. A backward sweep reuses deployed future feedback; full-horizon rollouts in an identified Gaussian belief model need no learned value critic. A nonlinear error recursion links quadratic continuation error, local correction, and policy storage. A controlled non-LQG example exhibits second-order policy accuracy with consistent storage, while ideal affine LQG admits exact backward recovery. In nonquadratic thrust, BG reduces actor cost by 2.47-3.20% and remains within 0.13-0.53% of the tested feedback MPC; original policies execute in 5-6 microseconds in a seed-0 native audit. With matched storage, BG attains competitive plant costs at about one ninth (arm) and one sixtieth (docking) of feedback-teacher-plus-student construction time on one GPU, excluding shared learning and node preparation. Richer common maps substantially narrow some student-BG gaps. These results expose the roles of learned feedback, local correction, and storage in executable control.

Formalizing research-level stochastic optimization in Lean requires both an algorithm model and domain theory connecting foundational libraries to convergence proofs. Revising a model to restore provability can change the mathematical claim. We introduce ProofLoom, a fully automated LLM-agent system for Proof-Obligation-Driven Theory Construction. Given a published algorithm, target theorem, and source proof, ProofLoom autonomously constructs the Lean model and supporting theory. Open proof obligations drive the development of definitions, interfaces, lemmas, and proof plans. Signature contracts record evidence and obligations for model revisions; an independent Judge rejects unsupported assumptions and weakened conclusions. Planner expands the published argument into intermediate claims, and Audit checks whether the Lean proof follows it. Across tasks, SOptLib accumulates verified mathematics and construction experience: reusable results are extracted, generalized, and verified, while modeling decisions and failed proof routes are recorded. Later tasks retrieve these results and records and contribute new developments, forming a cycle of construction, accumulation, and reuse. On fifteen textbook and research-paper tasks, ProofLoom obtains mean human ratings of 6.3/7 and 6.4/7, compared with 4.9/7 and 5.0/7 for the strongest of six baselines. Across 33 developments, it produces 490,693 lines of algorithm-local Lean code with no sorry. The formalizations also expose 28 incorrect formulas, proof gaps, and algorithm-analysis mismatches in published sources across 22 developments, each with checked evidence.

Exponential stabilization is investigated for a hetero-dimensional parabolic system in which a one-dimensional shoreline subsystem, subject to a constant input delay, is bidirectionally coupled with unactuated two-dimensional bathymetric dynamics. A spectral decomposition separates the finite-dimensional critical shoreline modes from the exponentially stable residual dynamics. State feedback is designed on the critical subspace and lifted to the full shoreline space. An auxiliary transport equation represents the delay, while a predictor removes the explicit input delay from the nominal predictor dynamics. Exponential stability of the full coupled system is established by combining shoreline stabilization and bathymetric coercivity using weighted input–output estimates and a small-gain condition on the hetero-dimensional interaction. Numerical simulations show that uncompensated delayed feedback can strongly amplify both shoreline and bathymetric responses, whereas predictor compensation restores decay of the critical shoreline dynamics and prevents delay-induced amplification from propagating to the unactuated bathymetric subsystem.

Completely positive functions are an extension of completely positive matrices. They are known to characterize maximal spherical codes and maximum-density distance-avoiding subsets of $\mathbb{R}^n$ and certain compact metric spaces. This thesis expands this framework to related classes of problems in finite measure spaces and to the sphere-packing problem. For the latter, this is sharpened to show that the optimal sphere-packing density can be approximated using Schwartz functions. Converging hierarchies of semidefinite programming bounds on the size of optimal spherical codes are known, based on approximations of completely positive functions and the Lovász theta number of a graph. This thesis extends these hierarchies to distance-avoiding sets and similar problems and to the sphere-packing problem, and proves their convergence to the maximum density. For distance-avoiding sets, additional hierarchies, such as the moment hierarchy, are introduced and shown to be stronger than the completely positive hierarchy, hence they also converge. Related hierarchies for compact packing problems are also investigate. These bounds are implemented for Witsenhausen's problem, which asks for the maximum fraction $\alpha_n$ of the $n$-dimensional unit sphere that is coverable by a set avoiding orthogonal pairs; and for the $t$-almost-equiangular-set problem: finding the maximum size $\alpha(n,t)$ of a subset of the $n$-dimensional unit sphere in which every triple contains a pair with inner product $t \in [-1,1)$. An analytic solution to this bound yields an enumeration of optimal constructions for $n = 2$ and $3$ when $t \geq 0$.

Data-driven model predictive control based on Koopman operator theory is a promising approach for constrained control of nonlinear systems with unknown dynamics. This paper proposes a robust model predictive control framework for such systems using bilinear Koopman realizations with state- and input-dependent proportional approximation-error bounds that vanish at the target equilibrium. Since prediction in lifted coordinates with a finite-dimensional Koopman realization need not remain on the manifold of valid lifted states, multi-step prediction may leave the region where one-step error certificates apply. We avoid this difficulty by reprojecting each predicted lifted state onto the original state coordinates and lifting it again, yielding an error-aware discrete-time control-affine predictor in the original state space without assuming invariance of the Koopman dictionary. For this predictor, we develop a homothetic tube construction based on a discrete-time robust control contraction metric whose radius explicitly accounts for the proportional approximation error bounds. The tube tightening handles arbitrary continuously differentiable nonlinear constraints, and the resulting model predictive control problem includes terminal ingredients and a tube-radius penalty that exploits the vanishing uncertainty near the target. We prove robust satisfaction of the original nonlinear constraints, recursive feasibility, and exponential stability of the sampled true closed-loop system with high probability over the training data without requiring a globally optimal solution to the model predictive control problem. Numerical examples, including nonlinear obstacle-avoidance constraints, demonstrate robust stabilization and higher performance of the proposed approach compared to existing Koopman-based model predictive control methods in terms of smaller closed-loop cost and flexibility.

We study finite-time concentration and convergence rates for projected two-time-scale stochastic approximation driven by a controlled Markov chain. The averaged fast map is contractive, while the slow iterate is projected onto a compact convex polyhedron. The associated projected ordinary differential equation may have a discontinuous vector field at the boundary, preventing a direct application of standard analyses based on Lipschitz vector fields. Using the Skorokhod map, we establish explicit high-probability bounds for tracking the moving fast equilibrium and the projected slow dynamics. These bounds separate martingale fluctuations, Markov-noise residuals, and the bias due to time-scale separation. A Lipschitz Lyapunov function satisfying a uniform decrease condition over fixed time intervals yields almost-sure convergence, with explicit last-iterate rates when the decrease admits a power lower bound. Under uniform Lyapunov contraction, polynomial step sizes yield joint fast-tracking and slow Lyapunov-error exponents arbitrarily close to $1/3$. Under the additional assumption that the reduced slow update map is a Euclidean contraction, logarithmically separated step sizes improve the joint rate to $O(n^{-1/2}\log n)$ almost surely, including for boundary equilibria. The same rate holds under a distinct geometric condition involving a strictly attracting face of a box and a fast equilibrium that is constant on that face. An actor-critic application achieves an almost-sure value-gap rate of $O(n^{-1}\log n)$ relative to the optimum within the constrained policy class. Further applications include projected TD(0) and projected stochastic gradient descent. We also extend the analysis to projection of the fast recursion under Euclidean contractivity.

We study Bregman proximal gradient (BPG) algorithms under relative smoothness for convex, relatively strongly convex, and nonconvex objectives. Existing accelerated BPG algorithms for convex objectives typically require additional assumptions on Bregman divergences, most notably triangle-scaling conditions, which can lead to slower convergence rates. We propose a family of geometry-accelerated BPG algorithms that exploit Bregman geometry in both proximal-gradient and mirror-space updates, without imposing additional geometric conditions such as triangle-scaling conditions. Our methods adapt the stepsizes and mirror-space updates through local backtracking and computable acceptance criteria, without a global relative-smoothness constant as input. We derive convergence bounds in terms of the parameters accepted during the iterations. These bounds yield an $\O(k^{-2})$ rate for convex objectives and a linear rate for relatively strongly convex objectives when the geometry-acceleration parameters remain uniformly bounded. For nonconvex objectives, we establish an $\O(k^{-1})$ rate for a stationarity measure without requiring a lower Bregman bound or a full-domain Bregman divergence. Numerical experiments on inverse problems, entropy-regularized least squares, D-optimal design, and nonnegative matrix factorization demonstrate faster practical convergence than established Bregman baselines.

We focus on systems of nonlinear equations, where some equations are non-polynomial. Building on the remarkable developments in solving polynomial systems during the recent decades, and on a few extensions to specific examples of the transcendental case, a general framework for finding isolated roots is proposed. The name paxotopy is proposed after (1) Polynomial ApproXimation of the transcendental functions, then (2) solving the approximating polynomial system by the homOTOPY continuation method, and finally (3) the roots of the polynomial systems are used as starting points of a Newton's iteration to arrive at the solutions of the original system. These steps combine the advantages of local and global methods.

Parameter space symmetries and conservation laws play an important role in understanding the loss landscapes and implicit biases of neural networks. Inspired by Noether's theorem in physics, prior works have sought to derive conservation laws under gradient flow from parameter symmetries, but the scope and limitations of this connection remain unclear. We develop a unified geometric framework that clarifies the precise relationship between the two notions, including the conditions under which symmetries correspond to conservation laws. We introduce a notion of compositional identifiability and use it to establish a general inheritance principle for complete characterizations of symmetries and conservation laws in multilayer networks. We apply the framework to multi-head and grouped-query attention, polynomial neural networks, and square deep linear networks.

Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an $\epsilon$-Riemannian critical point within $O(\epsilon^{-3})$ iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

Nonasymptotic convergence rates for optimization problems have been extensively studied across a wide range of settings, with carefully constructed worst-case instances establishing matching lower bounds for many algorithm classes. Recent work has shown, however, that these rates can often be improved in the asymptotic regime, while the corresponding asymptotic lower bounds remain largely unknown. We propose a general technique for converting existing nonasymptotic lower bound constructions into asymptotic lower bounds on Hilbert spaces. This allows us to show that several known asymptotic convergence upper bounds in Hilbert spaces are tight. In particular, we recover tightness of the $o(n^{-2})$ suboptimality guarantee for accelerated gradient descent on smooth convex functions \cite{attouch2016rate}, as well as the $o(n^{-1/2})$ suboptimality guarantee for gradient descent on smooth nonconvex functions \cite{gratton2025refining}. For stochastic convex optimization, we also develop a method that achieves an $o(n^{-1/2})$ suboptimality guarantee in finite dimensions, and prove a matching one-dimensional lower bound.

We study convex optimization over compact convex sets for twice differentiable objective functions with positive definite Hessians, assuming access to the feasible set through a linear minimization oracle. Existing second-order Frank–Wolfe methods either provide only a local linear rate over general convex sets or achieve global linear and local quadratic convergence only over polytopes. We propose damped Newton Frank–Wolfe methods that approximately solve constrained damped Newton subproblems using Frank–Wolfe or away-step Frank–Wolfe inner iterations. We develop residual backtracking, using a root Newton stepsize as a safe reference, together with a switching rule that eventually takes full steps. Under Hölder smoothness assumptions for $p$th derivatives, we establish global linear convergence and local convergence with Q-order at least $1+\nu$ ($p=2$) and local quadratic convergence ($p=3$). Experiments on matrix sensing and ridge-regularized logistic regression show that the residual-backtracking variant is consistently robust and often achieves the best performance among the tested first- and second-order baselines.

Nonlinear preconditioning makes it possible to adapt gradient updates to the growth of the objective's curvature, but combining its design with suitable stepsize selection is challenging. We propose adaptive dual preconditioned gradient descent (adaptive DPGD), which combines curvature-based preconditioner design with a linesearch-free stepsize rule based on local information. For convex objectives, we establish linear convergence under local strong convexity of the objective. By adapting the stepsize rule, we extend the method to weakly convex objectives and establish asymptotic stationarity without global Lipschitz smoothness. Moreover, our local assumptions give greater freedom in preconditioner design. We exploit this freedom to develop a semiautomatic recipe guided by the objective's curvature, yielding a family of preconditioners that includes those underlying normalized and hyperbolic gradient descent. Experiments on convex and weakly convex problems with real data demonstrate the effectiveness of the preconditioner design and adaptive stepsize selection.