Papers

We design adaptive overlapping temporal decomposition (AOTD), a parallel sequential quadratic programming (SQP) method for long-horizon nonlinear optimal control problems (OCPs). As designed, AOTD is the first overlapping temporal decomposition (OTD) algorithm that adapts the overlap size online, eliminating the need to fix a suitable overlap a priori. Specifically, at each iteration, it partitions the long horizon into overlapping nonlinear subproblems, performs one SQP step on each in parallel, and adaptively selects both the overlap size and the accuracy to which the resulting local KKT systems are solved. Two conditions govern the accepted step: an adaptive residual condition bounding the distance from the concatenated inexact direction to the exact Newton direction of the full problem, and a descent condition on the adaptive penalty parameters that certifies descent for a carefully chosen exact augmented Lagrangian. The residual condition is solver independent and accommodates both deterministic iterative solvers and randomized sketching solvers. Under standard regularity assumptions, we prove that the KKT residual converges to zero from any initialization and establish a local linear rate for sequences converging to a strict local minimizer. We validate AOTD on a power-system frequency regulation OCP and a Burgers PDE OCP, attaining a reduction in estimated FLOPs of approximately $2.5\times$ to the best fixed-overlap variant while converging across multiple horizon lengths with a single parameter setting.

In these notes, we view control as a dynamically constrained sampling problem on the state-space of a control system. With this viewpoint, we extend methods from generative modeling, such as flow matching, normalizing flows and denoising diffusions to control problems. Concepts such as controllability, optimal control and trajectory planning play an important role in guiding the extension and understanding well-posedeness of the corresponding algorithms, with application to steering systems to target states or distributions and sampling from reachable sets. The notes are intended as an accessible introduction for readers with a background in control theory and robotics.

We study episodic continuous-time control with an unknown vector control gain, scalar state, quadratic action cost, and smooth convex terminal cost. In the scalar Gaussian experiment, let $\Delta(H)$ denote the minimax improvement over zero control and set $\delta=\sqrt2H^2-1$. We prove the critical law $$ \Delta(H)\asymp \delta^4\sqrt{\log(1/\delta)} \qquad (\delta\downarrow0), $$ with a matching lower and upper bound. The lower bound follows from a uniform deficit–energy inequality valid for fully adaptive controls with unbounded amplitudes, while a moving soft-threshold feedback attains the rate. For local parameters $\theta=N^{-1/4}h$, $|h|\le H$, we show that the normalized minimax regret over $N$ episodes is within $O(N^{-1/2})$ of a fixed-horizon Gaussian sequential control problem, without an additional dimension factor. The terminal task enters the limit only through $c_g=\operatorname{Var}(g(Z))$. The Gaussian problem exhibits an exact no-learning phase transition: $$ C_d^T(H)=TH^2/2 \iff H^4T\le d^2/2, $$ yielding the asymptotic task boundary $c_gH^4=d^2/2$.

Muon is emerging as a promising alternative to AdamW for large-scale neural network training, yet theoretical understanding of its practical implementation remains incomplete, as existing analyses often simplify or omit two key components: (i) practical Newton–Schulz iterations with empirically tuned polynomial coefficients $(3.4445,-4.7750,2.0315)$; and (ii) decoupled weight decay for regularization. In this paper, we provide an optimization interpretation and establish convergence for practical Muon, jointly accounting for both components. Specifically, we interpret practical Muon as right-preconditioned optimization of the original loss with a dynamic weighted $\ell_2$ regularizer that vanishes as stationarity is approached, so that the optimization target remains the original objective. We then establish, to our best knowledge, the first convergence guarantee for practical Muon in the stochastic nonconvex setting, with an $\mathcal{O}(T^{-1/4})$ convergence rate in terms of the expected Frobenius norm of the gradient, improving the dimension dependence of the best known AdamW's convergence rate by a factor of $\sqrt{d}$, where $T$ is the iteration horizon and $d$ is the parameter dimension. Experiments further support the theoretical convergence results.

Black-box Optimization (BO) is a powerful framework for optimizing expensive objective functions or unknown functions with a limited number of evaluations. A central step of standard BO such as Bayesian optimization is the optimization of a surrogate-based acquisition criterion, which is commonly performed using nonlinear optimization or heuristic search. Therefore, conventional black-box optimization generally does not guarantee global optimality in candidate selection. In this study, we propose Integer Linear Programming-based Black-box Optimization (ILP-BO), a quasi-Bayesian optimization framework that transforms kernel-based surrogate optimization over discrete domains into an Integer Linear Programming (ILP) problem. The key idea is to represent nonlinear kernel functions exactly on finite discrete distance levels by introducing binary one-hot auxiliary variables. This transformation converts the nonlinear surrogate into a linear objective with linear constraints and binary variables. To incorporate exploration while preserving the linear structure, we further introduce a Hamming-distance margin that excludes neighborhoods around previously observed points. We derive the proposed formulation for several standard kernels and obtain an analytical upper bound on the Hamming-distance threshold based on the measure in the binary search space. The resulting candidate-selection problem can be solved by integer programming solvers with certificates of optimality. Thus, our methodology has the potential to serve as a highly transparent black-box optimization framework. Experiments on synthetic and discrete optimization benchmarks show that ILP-BO achieves competitive optimization performance compared with practical Bayesian optimization methods.

Plug-and-Play (PnP) methods replace proximal operators with learned denoisers, which produce state-of-the-art reconstruction quality, but sacrifice the variational interpretation and convergence guarantees of proximal methods. Learned Proximal Networks (LPNs) address this problem by designing the denoiser architecture so that it is exactly the proximal operator of a regularizer. In this work, we clarify the theoretical foundations of LPNs and extend the framework to a broader class of activation functions. We then study two practical mechanisms for controlling the learned prior: (i) averaging the LPN with the identity, a common heuristic in PnP methods, and (ii) directly scaling the implicit regularizer induced by the proximal operator. In particular, we characterize the regularizer induced by averaging and develop a convergent method for evaluating the scaled proximal operator.

Policy gradient methods for the linear quadratic regulator optimize feedback gains using a cost over an infinite horizon. When this cost is evaluated at one fixed initial state, it need not diverge near every part of the stability boundary. We study whether the Euclidean gradient flow can reach this boundary in finite optimization time. For controllable planar systems with one input and positive definite quadratic weights, an exact representation of the cost yields a necessary and sufficient condition for the existence of such a collision. The condition reduces to a scalar root calculation and includes the critical case, where a double direction root attracts an open set of stabilizing gains. For a triangular family, the criterion gives an explicit algebraic parameter region, and every trajectory either converges to the Riccati gain or collides with the stability boundary. A sharp threshold for compact cost sublevels provides a convergence certificate. Along every colliding trajectory, the stability margin and the smallest eigenvalue of the accumulated state Gramian vanish linearly, although the Gramian remains positive definite before collision. Numerical experiments examine the dependence on initialization, slow passage near a critical direction, and the effect of adding excitation in a second state direction.

We study stochastic fixed-point iterations $x_{n+1}=\theta_nx_0+(1-\theta_n)\widehat T(x_n)$ for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule $\theta_n=c_n/(n+2)$ whose density $c_n\in(0,1]$ does not oscillate between scales is either polynomially suboptimal on contractions or super-polynomially slow on rotations; for constant densities $\theta_n=c/(n+2)$ the tradeoff is exact, with $\norm{x_n}\asymp\Gamma(c+1)(n\varphi)^{-c}$ on rotations by angle $\varphi$ ($\varphi\to0$, $n\varphi\to\infty$) and, for the classical schedule, $\norm{x_n}=\frac{2|\sin(n\varphi/2)|}{n\varphi}+O(\frac1n)$. The dichotomy fails exactly under lacunary anchor concentration: an explicit $\gamma$-oblivious schedule, one per target accuracy, is simultaneously contraction-optimal and rotation-polynomial with exponent $1/\alpha_0$, $\alpha_0=\log_2(3/2)$, and, for each fixed target accuracy, the matching lower bound holds for Lebesgue-a.e.\ angle. For stochastic contractions, the minimax rate is $\Theta(\sigma^2\eps^{-2}(1-\gamma)^{-2})$ on affine maps, and within the anchored class $\Theta(\sigma^2\eps^{-2}(1-\gamma)^{-2}+(1-\gamma)^{-1}\ln(D/\eps))$ for known modulus via geometric batching; without a certified modulus bound no sound distance certificate exists, and a certified ceiling is the exact boundary. For nonexpansive maps we prove $O(K\sigma^2D^2\eps^{-4})$ in every $2$-uniformly smooth Banach space and the Hilbert rate $\tilde\Theta(\sigma^2\eps^{-2}+D\eps^{-1})$ by reduction to monotone inclusions. Numerical experiments are consistent with every scaling prediction.

This paper addresses discrete-time non-Gaussian distribution steering in deterministic nonlinear systems. Distribution steering is a problem in which a control policy is designed over a distribution of trajectories rather than optimizing a single trajectory. The challenge with nonlinear systems is that even initially Gaussian distributions evolve into non-Gaussian distributions, often precluding a closed-form representation of the probability density. A method called statistical moment steering applies a cubature-based method to approximate non-Gaussian distributions for an approximate solution to this problem. This paper provides theoretical support and details how it can be solved with sequential convex optimization. A coupled, nonlinear, second-order ordinary differential equation describing a two-dimensional oscillator is provided as a numerical example.

We study decentralized optimization with cross-coupled mixed affine constraints, where local and shared variables interact through two affine channels. We show that the intrinsic difficulty of combining separately well-conditioned channels is governed by their Friedrichs angle. This geometry induces a cross-coupling factor that cannot be removed by channelwise preconditioning and governs the additional affine-oracle and communication complexity. We develop an accelerated decentralized method with matching minimax guarantees in the smooth strongly convex regime and extend the framework to smooth and nonsmooth convex objectives. Experiments confirm the predicted dependence on cross-channel geometry and network conditioning.

We propose RIAG-R, a Riemannian Inertial Adaptive Gradient method with gradient-triggered Restart, for optimization on Riemannian manifolds. RIAG-R combines three ingredients: an AdaGrad-type adaptive step-size that requires no knowledge of the Lipschitz constant; inertial extrapolation in the tangent space via the exponential map to accelerate convergence; and a restart rule, costing only one extra inner product per iteration, that detects and corrects the momentum-saturation pathology induced by manifold curvature. We establish a per-iteration descent inequality, an optimal $O(\varepsilon^{-2})$-iteration complexity, a convergence result for cluster points of the generated sequence, and a linear convergence rate under the Riemannian Polyak-Łojasiewicz inequality. Numerical experiments on four representative matrix manifold optimization problems including sphere, Stiefel, symmetric positive-definite, and Grassmann manifolds demonstrate that RIAG-R consistently outperforms non-inertial and restart-free inertial baselines, confirming that adaptive restart is essential to realizing the benefits of momentum on curved spaces.

Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an $O(1/T)$ ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon $T$: the uniform averages of the AltGDA iterates satisfy an $O(1/T)$ duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an $O(1/T)$ rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.

Since Zhang et al. \cite{Zhang2025} introduced the first purely primal methods for monotone variational inequalities subject to convex functional constraints, the field has lacked a complete understanding of the complexity limits of this oracle class. We develop a theory that resolves the critical gaps left by their pioneering framework. Our Optimal Primal Constrained Gradient Method (OPCGM) establishes convergence rates and lower bounds for algorithms restricted to local linear constraint approximations. For strongly monotone operators, we prove that a refined primal gradient method achieves the optimal $\mathcal{O}(1/T)$ rate for both optimality gap and constraint violation, eliminating the suboptimal exponent present in prior work. For Lipschitz monotone operators, we propose a primal extragradient variant that achieves the optimal $\mathcal{O}(1/\epsilon)$ gap complexity using only quadratic programming oracles, at the cost of a constant asymptotic feasibility violation for the averaged iterate; we prove that the first half-step is necessarily infeasible for the natural class of constant-stepsize primal extragradient methods on smooth convex constraints with positive curvature. We establish lower complexity bounds for primal methods restricted to local linear approximations, proving $\Omega(1/\epsilon^2)$ for Lipschitz monotone variational inequalities with Lipschitz constant scaling as $\Theta(1/\epsilon)$, and $\Omega(1/\epsilon)$ for standard Lipschitz monotone variational inequalities. We design a single-loop primal method that achieves an $\mathcal{O}(1/\sqrt{T})$ gap rate with only a domain-radius estimate, at the cost of a problem-dependent asymptotic feasibility constant that we prove is unavoidable. For strongly monotone problems, we prove that the last iterate converges at the optimal $\mathcal{O}(1/T)$ rate.

We study second-order convex optimization under generalized Hessian smoothness, where the local Hessian Lipschitz constant may grow linearly with the gradient norm. For inexact Hessians, we develop adaptive algorithms, including an accelerated Monteiro-Svaiter-type method whose complexity matches the lower bound for second-order methods with $\delta$-inexact Hessians in the classical Lipschitz-Hessian setting. Our methods are parameter-free in the sense that they require no problem-specific parameters as input, including the Hessian inexactness level $\delta$ and smoothness constants. Instead, their backtracking adapts a single regularization parameter that jointly captures Hessian inexactness and local Hessian smoothness. The resulting rates split into two regimes. Far from the solution, the gradient-dependent smoothness term yields geometric convergence. Near the solution, the rate is governed by the ordinary Hessian smoothness and the inexactness level $\delta$, recovering the classical Lipschitz-Hessian guarantees.

Minimax optimization is a fundamental framework in machine learning, robust optimization, and game theory, yet finding first-order stationary points of general nonconvex-nonconcave minimax problems remains challenging without additional structural assumptions. Existing guarantees often rely on global PL- or KL-type conditions that connect max-player stationarity to global inner optimality, or on Minty-type conditions that impose a global relation on the game gradient field relative to a reference solution; local KL variants relax the former requirement but typically require initialization and tracking within a near-optimal region. Such conditions may be difficult to satisfy in many applications. In contrast, we develop a first-order method that finds an $\epsilon$-stationary point within $\widetilde{O}(\epsilon^{-2})$ first-order iterations under a local inverse-Lipschitz regularity condition around approximate max-player stationary points, together with a compactness condition on a penalty sublevel set. Our condition places no optimality requirement on stationary points of the inner maximization problem: they need not be globally, or even locally, maximizing. We further provide sufficient conditions for the required regularity. In the unconstrained setting, it follows from uniform nonsingularity of the maximization-variable Hessian near stationary points; for constrained upper Moreau envelopes, it follows from standard KKT regularity conditions. These results establish first-order complexity guarantees for classes of nonconvex-nonconcave minimax problems not covered by the above PL-, KL-, or Minty-type frameworks.

Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample comparison of clipped and unclipped Polyak-Ruppert averaged SGD under finite conditional $p$-th moments, $p\ge2$. Our main result gives explicit accuracy and confidence conditions under which, for $p>2$, the Gaussian term dominates the unclipped deviation bound, so clipping need not improve its leading order. By balancing clipping bias and concentration, we obtain a bound in which the heavy-tail correction depends logarithmically rather than polynomially on the inverse failure probability. At $p=2$, this improves the confidence dependence of the leading bound. We establish sharpness of the unclipped heavy-tail term through an exact one-dimensional quadratic recursion and extend the comparison to projected convex SGD. We also prove concrete costs of clipping: every fixed finite threshold increases asymptotic variance on a scalar Gaussian quadratic, while whole-gradient clipping can shift the limiting point under asymmetric noise.

For planar convex bodies $A_0,A_1,A_2$ satisfying $\frac12(A_0+A_2)\subseteq A_1$, we prove that the union of the three slices $\{i\}\times A_i\subseteq\mathbb{R}^3$, $i=0,1,2$, contains a point such that every closed halfspace containing it captures at least $2/9$ of their total area. This establishes the three-slice case of Oertel's mixed-integer centerpoint conjecture in $\mathbb{Z}\times\mathbb{R}^2$ with the best possible constant.

Lebesgue's universal covering problem asks for the minimum area convex planar region capable of containing a congruent copy of every planar set of diameter at most one. In this paper, we develop an exact dual formulation of this problem through a minimum diameter analogue of Bellman's lost-in-a-forest problem. For a compact convex forest $F$, we define the critical escape diameter $D(F)$ as the minimum diameter of a closed path whose trace cannot be placed, under any rigid motion, entirely in the interior of $F$. We prove attainment of this minimum and establish a diameter cover/escape duality showing that the normalized body $D(F)^{-1}F$ is a Lebesgue universal cover. Consequently, the Lebesgue universal covering constant admits the exact representation \[ \mathcal L=\inf_F\frac{\operatorname{Area}(F)}{D(F)^2}, \] where the infimum ranges over compact convex planar bodies with nonempty interior. By reversing the rigid motion, we further characterize escape as intersection of a fixed path with every oppositely transformed boundary of $F$, and derive equivalent continuous curve, convex body, and support function optimization formulations. To make the infinite dimensional problem computationally tractable while retaining rigorous control of approximation error, we discretize the compact configuration space by an $\eta_m$-net and formulate the resulting problem as a minimum diameter traveling salesman problem with neighborhoods; for polygonal forests, an exact mixed-integer second-order cone formulation is obtained. We prove the quantitative certification, which yields convergent, rigorously certified universal cover bounds. The framework replaces finite tests of prescribed constant width shapes by a unified optimization over the full configuration space and extends naturally to other congruent and translative universal cover problems.

Optimal first-order methods on non-Euclidean domains such as the $\ell_1$ ball $B_1^n(R)=\{x\in\mathbb R^n:\|x\|_1\le R\}$ pair the prox-function with the norm in which smoothness is measured. When the gradient is $L$-Lipschitz in the Euclidean norm only, the accelerated method with a Euclidean prox-setup reduces the functional gap $f(x_N)-\min_{B_1^n(R)}f$ to $O(LR^2/N^2)$ after $N$ first-order queries (an entropic $\ell_1$ prox-setup replaces $L$ by the $\ell_1\to\ell_\infty$ constant $L_1\le L$, at the cost of a factor $\log n$ and with the same exponent). The lower bound of Guzmán and Nemirovski is of order $LR^2/N^3$, and whether the upper bound can be brought down to that order is a question of A. S. Nemirovski. We show that for this mismatched problem the minimax value of the gap is of order $LR^2/N^3$ up to logarithmic factors, for deterministic and for randomized methods alike, and already in dimension proportional to the number of queries. The upper bound is attained by a Steiner-point level method: every supporting hyperplane seen so far is kept as a level cut, and the next query is made near the Steiner point of the resulting localization polytope. The analysis rests on a single geometric fact: along nested subsets of the ball the Steiner points travel a distance that is polylogarithmic in the dimension, in contrast to $\sqrt n$ for the Euclidean ball. All queries stay feasible, and a randomized selector keeps the internal work polynomial. The same geometry yields optimal rates for nonsmooth objectives, Hölder gradients, higher-order oracles and Lipschitz monotone operators, the last with a matching deterministic lower bound. For convex quadratics, a curvature-learning method attains the optimal rate on every $\ell_p$ ball with $1\le p<2$ and without logarithmic loss. Experiments confirm the predicted $N^{-3}$ behaviour on objectives that are hard for Euclidean methods.

In this paper, we present a multi-period optimization problem arising from the traffic engineering of core IP/MPLS networks, called T-ASR. This problem aims at computing a sequence of segment routing paths that adapt to a multi-period scheduled maintenance, while allowing limited number of path reconfigurations between successive time steps. Rather than focusing solely on minimizing the classical Maximum Link Utilization (MLU) criteria, we introduce a more refined lexicographic objective that minimizes the entire sorted vector of link loads providing a more efficient resource utilization for all the links. We propose a generic approach that decomposes this problem into a sequence of subproblems. To model each subproblem, we introduce two Mixed Integer Linear Programming (MILP) formulations, ALEXA and STELA, resulting in two variants of our approach. Finally, we evaluate and compare the efficiency of both variants on small to medium-sized network instances.

This paper studies the nonconvex optimization landscape of Linear Quadratic Gaussian (LQG) control under direct state-space parameterization. Although the LQG cost may possess suboptimal stationary points, whether it admits suboptimal local minima has remained open. We answer this question negatively: Every local minimum of the full-order LQG cost is globally optimal. More generally, at any controller order, every local minimum corresponding to an uncontrollable or unobservable realization attains the globally optimal LQG cost over all stabilizing policies of arbitrary orders. We further show that any suboptimal policy can be augmented with decoupled stable controller states, so that the augmented policy admits a direction of negative curvature with probability one. Consequently, any suboptimal stationary point in full-order LQG cost can be converted into a strict saddle with probability one. One key proof idea connects the state-space Hessian to a frequency-domain global-optimality condition derived from the Youla parameterization. These results reveal a benign local-minimum landscape despite the presence of suboptimal stationary points.

We study the Sampled-Max Subgradient Method (SMax-SGM) for large convex finite-max problems. Each iteration maximizes over a fresh random subset of the $N$ components and takes one subgradient of the sampled maximizer. The method is therefore stochastic subgradient descent on a sampled-max surrogate. We bound the surrogate error by an average-top-$k$ gap plus the probability of missing all top-$k$ components. A localization argument requires these quantities only on a near-optimal sublevel set. Under a bounded subgradient-moment assumption, this yields $O(\varepsilon^{-2})$ subgradient queries and, when $k$ components remain nearly active in that set, $\widetilde O((N/k)\varepsilon^{-2})$ component-value queries, capped by the full-scan cost. Conversely, a one-dimensional affine construction shows that $\Omega(N/k)$ component-value queries can be necessary even when the average-top-$k$ gap vanishes everywhere and subgradient queries are unlimited. A tensor-grid specialization explains when the subset size can become independent of grid cardinality. Experiments on finite maxima with $2\times10^5$ and $5\times10^6$ components show that, under the reported protocols, SMax-SGM reaches a 5% numerical-reference gap with fewer component-value queries and lower optimizer time than each comparison method that reaches the target.

Over-the-air computation has emerged as a scalable and efficient solution for deploying federated learning algorithms in wireless networks by exploiting waveform superposition for simultaneous model aggregation. Most existing work struggles with heterogeneous fading channels. These approaches either enforce unbiased updates from all devices or allow partial device contributions, requiring careful tuning of the convergence bound to mitigate bias under specific fading models. However, the former significantly amplifies receiver noise due to the weakest channel, whereas the latter is sensitive to fading model mismatch and converges only to a biased objective. To tackle these challenges, we propose FedOAG, which employs algorithmic components to automatically satisfy energy constraints via gradient normalization and evenly mix devices' updates through implicit gossiping. Importantly, FedOAG does not require transmission from all devices, nor does it rely on a specific fading model or knowledge of time-varying statistical channel distributions. We show that FedOAG converges to a stationary point of an unbiased non-convex objective at the best possible rate $O(1/\sqrt{T})$ for any stochastic first-order method. We corroborate our analysis with numerical experiments over dynamic wireless conditions on real-world datasets.

This paper presents a path-following controller for a quadrotor system to guarantee safe maneuvers, in terms of forward path invariance, in the presence of cyber-physical attacks. We assume that an adversarial agent can control any one of the rotors through a false data injection (FDI) type of attack. A feedback controller is designed using transverse feedback linearization which guarantees that the system follows a class of smooth curves under FDI attacks. Our proposed controller is computationally efficient, with a closed-form analytical expression, that not only mitigates the effect of bounded malicious signal but also ensures mission success. We provide theoretical guarantees of forward path invariance under FDI attacks with realistic assumptions and demonstrate the effectiveness of our approach through simulation.

AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal last-iterate rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight $\Omega(\log T/\sqrt T)$ lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that $\log T$ in existing average-iterate upper bounds is unavoidable. Finally, we show that this $\log T$ loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates ${O}(1/\sqrt{T})$.

We study distributionally robust reinforcement learning (DR-RL) in the average-reward setting under weak communication. Our main result provides finite-sample guarantees for estimating the robust optimal average reward and learning a near-optimal policy, covering both SA-rectangular and S-rectangular structures with divergence-based and distance-based uncertainty sets. Specifically, for Kullback–Leibler and $f_k$-divergence balls, we establish explicit radius conditions under which the robust average-reward Bellman equation admits a constant-gain solution, while for total variation and Wasserstein balls, any positive radius suffices without requiring the nominal MDP to be weakly communicating. Our algorithm is prior-knowledge-free and achieves sample complexities of $\widetilde O(|\mathcal{S}||\mathcal{A}|p_{\wedge}^{-1}\operatorname{Span}^{2}(u_{\delta}^{\ast})\epsilon^{-2})$ for estimating the robust optimal average reward and $\widetilde O(|\mathcal{S}||\mathcal{A}|p_{\wedge}^{-2}\operatorname{Span}^{2}(u_{\delta}^{\ast})\epsilon^{-2})$ for learning an $\epsilon$-optimal policy. Here, $p_{\wedge}$ is the smallest positive nominal transition probability and $u_{\delta}^{\ast}$ is a robust optimal bias function. We further provide an almost-tight explicit upper bound on $\operatorname{Span}(u_{\delta}^{\ast})$. Finally, we validate the predicted $n^{-1/2}$ convergence rate through numerical experiments.

We consider a problem of optimal proportional reinsurance-dividend distribution under a Brownian risk model, where both the drift and volatility coefficients are subject to endogenous regime-switching. Dividend payments are subject to fixed transaction costs. The problem is formulated as a two-dimensional stochastic control problem, and we prove that the value function is the unique viscosity solution of the associated Hamilton-Jacobi-Bellman equation with nonlocal operator. For almost all parameter configurations, we explicitly characterize the optimal strategy that maximizes the expected total discounted dividends net of transaction costs until ruin. The optimal dividend policy is a two-barrier impulsive strategy, while the optimal reinsurance proportion is given in feedback form. Numerical examples are provided to illustrate the optimality results.

We study entropy-regularized linear programs with sparse affine constraints and compare two exact dual representations induced by whether a redundant normalization constraint is retained or eliminated. Eliminating it yields a partially separable sum-exp dual with sparse affine factors but unbounded curvature. Our main result is an accelerated randomized block method whose acceleration preserves sparse data-access cost. The key ingredient is a global entropy-specific Hessian–gap bound that remains valid for signed constraint matrices, admits computable block-overlap refinements, and provides deterministic curvature certificates before sampling. This geometry supports square-root importance sampling and an exact lazy implementation in which sparse arithmetic cost is weighted by local curvature rather than by a worst-block factor. We further introduce a gap-dependent curvature dimension that connects the generalized-smooth regime to the classical effective-rank intuition for coordinate methods. Retaining the normalization constraint yields a log-sum-exp dual with globally bounded higher derivatives, enabling gradient-regularized and cubic-regularized Newton methods. Experiments compare the resulting methods in terms of coordinate epochs, arithmetic operations, and wall-clock time, separating the effects of acceleration, touched-data sparsity, and problem-specific structure.

The current deep learning training paradigm employs end-to-end backpropagation, regardless of the training stage, i.e. pre-training or fine-tuning. However, backpropagating through the entire model is neither biologically plausible nor memory efficient, since learning inside the brain is highly localized. Therefore, we propose LocalProp, a training procedure that locally updates the weights of a model. Our neuro-localized weight updates follow the "pre-training then fine-tuning" paradigm, where the pre-training is based on I-JEPA. After locally updating the weights, a pruning operation is performed, followed by a short final fine-tuning phase. Pruning helps by sending the learning signal from higher blocks to lower blocks. We perform experiments on several datasets, including large-scale benchmarks such as ImageNet, and empirically show that LocalProp reaches good performance at a fraction of GPU peak memory. By varying the number of jointly optimized blocks, we identify gradient-propagation span as a practical control over the accuracy-memory trade-off.

Many learning problems couple a high-dimensional block of parameters with a handful of adversarial or dual variables: worst-group risk over a few groups, or learning under a few constraints. We consider $\min_{x\in X}\max_{y\in Y} f(x,y)$ with $X\subseteq\mathbb{R}^n$, a compact convex set and strongly convex with condition number $\kappa$, and we count the oracle calls for $x$ and for $y$ separately. The textbook approach runs a cutting-plane method in $y$ and solves every inner problem to accuracy $\varepsilon$ with an accelerated method; it needs $O(m\log(1/\varepsilon))$ calls for $y$ but $O(m\sqrt{\kappa}\log^2(1/\varepsilon))$ calls for $x$. We show that the inner problems need not be solved accurately. Our method, certificate transport, keeps a strongly convex lower model of a single slice and uses it as a prior for a short accelerated run on the next slice. By concavity in $y$, every call for $y$ then either cuts the localizer or moves the lower model to a mixture of the two slices with a certified increase of the lower bound. For $m=1$ this gives an $\varepsilon$-saddle point after $O(\sqrt{\kappa}\log(1/\varepsilon))$ calls for $x$, up to an initialization term, and $O(\log(1/\varepsilon))$ calls for $y$; both counts are optimal, even though $f(x,\cdot)$ is only assumed to be concave and Lipschitz. For general $m$, with centers of gravity of the localizer treated as computable, the method needs $O((m+\sqrt{m\kappa})\log(1/\varepsilon))$ calls for $x$ and the optimal $O(m\log(1/\varepsilon))$ calls for $y$. Under strong concavity in $y$, a two-point accelerated method makes the number of calls for $x$ independent of $m$.