This paper studies online convex optimization against comparators that switch $k$ times among only $m$ distinct points, generalizing the classic experts tracking problem to continuous domains. While discretizing the domain and applying the Bousquet–Warmuth long-term-memory algorithm yields information-theoretic regret $\widetilde O(md+k)$, this is computationally inefficient. The authors prove that, under the hypergraphic planted-clique conjecture, no polynomial-time algorithm can achieve $\widetilde O(k^a d^b)$ regret whenever the exponents violate $\theta a + b < \theta + 1/2$, establishing a fundamental computational barrier for exp-concave losses even when $m=2$.

This paper studies the nonconvex optimisation landscape of finite-particle maximum mean discrepancy (MMD) quantisation, where a target probability measure is approximated by a weighted atomic measure. For the one-dimensional Gaussian kernel, the authors prove that beyond explicit particle thresholds every local minimum has arbitrarily small MMD and every high-MMD stationary point is unstable under unweighted gradient flow. These are the first finite-particle overparameterisation guarantees for weighted MMD, though the analysis is currently limited to one dimension.

This paper resolves the open problem of optimal dimension dependence for dynamic regret in exp-concave online learning. The authors propose SparseGauss, a proper full-information learner that achieves a $\widetilde{O}(d^{1/3}T^{1/3}P_T^{2/3})$ rate via sparse Gaussian histories and square-root KL movement control. A matching lower bound on a Euclidean ball establishes minimax optimality, up to logarithms, when $T \gtrsim d^2$.

Momentum is a pillar of modern optimization, yet its benefits in reinforcement learning with verifiable rewards (RLVR) remain unclear. This paper studies a KL-regularized bandit formulation of RLVR and proves that, with exact policy gradients, larger EMA coefficients strictly accelerate convergence within a safe overshoot-free range. Its central insight is that stochastic sampling obscures this gain unless the coefficient scales with the learning rate so that $\eta/(1-\beta)$ stays constant, a principle validated in bandits and in LLM post-training on Qwen models.

Random reshuffling (RR) is the de facto standard for training machine learning models, yet theory has long lagged practice for last-iterate convergence. Existing guarantees required stepsizes as small as $1/(nL)$, while averaged-iterate analyses allowed $1/L$. Chen and Zhang close this gap for smooth convex objectives, proving that the last iterate of RR-SGD converges with stepsizes up to $1/(L(1+\log(nK)))$---removing the explicit $1/n$ barrier at the cost of only logarithmic factors. The result matters because practitioners return the final parameter, not an average, and large constant stepsizes are common in deep learning.

The paper tackles sampling from Gibbs distributions on matrix spaces with potentials that are neither convex nor globally gradient-Lipschitz. Its core idea is to replace the quadratic kinetic energy of underdamped Langevin dynamics with a non-quadratic, relativistic-like energy $K_\delta(p)=\delta^{-1}\operatorname{Tr}[(I_n+\delta pp^\top)^{1/2}-I_n]$, whose gradient tames momentum singular values smoothly. By carefully coupling a momentum-dependent diffusion matrix $M_\delta(p)$ and its divergence correction $\Gamma_\delta(p)$, the authors preserve the exact target Gibbs measure, recover regularised Muon in the zero-temperature limit, and prove exponential convergence of the diffusion plus uniform-in-time moment bounds for an explicit Euler-Maruyama scheme.

Robust Markov decision processes with polyhedral uncertainty lack exact convex representations because the natural robust Bellman inequalities become bilinear or union-of-polyhedra constraints. This paper shows how to encode a finite sequence of robust policy-iteration steps into a single exact LP whose optimal face recovers the robust optimal value and all optimal stationary randomized policies. At fixed discount, the LP has polynomial dimension and encoding length, and the authors use this representation together with a unified complexity analysis to prove strongly polynomial bounds for several standard uncertainty sets—including $\ell_1$, weighted $\ell_1$, interval, and Wasserstein—that previously lacked such guarantees.

Contextual linear optimization faces a discontinuity: small prediction errors can flip the LP solution to a different vertex, making regret non-differentiable pointwise. This paper proves that, after averaging over the data distribution, the population regret is locally quadratic with curvature concentrated on the walls of the normal fan. The authors derive the exact curvature measure $K_0$, provide a tractable single-projection approximation $\mathsf{K}_{\lambda,s}$, and apply it to scenario generation, showing a $30.8\%$ regret reduction on a battery arbitrage task.

TACO attacks the memory bottleneck of full-parameter LLM fine-tuning by replacing dense AdamW states with a geometry-induced sparse update. The core idea is to use a dimension-normalized $\ell_1 \to \ell_1$ operator norm, whose exact steepest-descent direction is a ternary, column-wise one-sparse matrix. By retaining only a tiny FP8 heavy-hitter history per column, TACO slashes persistent optimizer state by over $170\times$ and peak memory by nearly $3\times$, enabling 30–32B parameter models to fine-tune on a single 80 GB GPU.

Pan and Yang study stochastic nonconvex–strongly-convex bilevel optimization when only unbiased stochastic gradient estimates are available. They propose MRT-FD, a single-loop algorithm that simultaneously tracks the upper-level variable, lower-level solution, and an auxiliary response variable, using order-$p$ finite differences to reconstruct hypergradient actions from first-order queries. For lower-level objectives with order-$p$ smoothness, the method achieves $\mathcal{O}(\varepsilon^{-4-2/p})$ oracle complexity, and the authors prove a matching $\Omega(\varepsilon^{-4-2/p})$ lower bound, settling the optimal $\varepsilon$-dependence for any fixed finite $p$.

STORM is a single-sample stochastic recursive momentum method that avoids periodic full-gradient checkpoints. Prior analyses required a stronger average smoothness assumption and produced suboptimal or logarithmically degraded rates. This paper shows that the original STORM recursion alone achieves the optimal $O(T^{-1/4})$ nonconvex rate, $O(\sigma R/\sqrt{T})$ convex rate, and $O(\sigma^2/(\lambda T))$ strongly convex rate under standard smoothness, by introducing auxiliary sequences and shifted iterates to cancel the estimator bias.

Understanding when neural-network loss landscapes contain spurious local minima is a foundational problem in deep learning. This paper studies shallow bias-free ReLU networks in a Gaussian teacher-student setting and proves that a learned linear skip connection eliminates all spurious local minima for planar teacher features with positive output weights once the student is at least as wide as the teacher. In contrast, without the skip, spurious minima can persist at every width—a striking separation between architectural bias and overparameterization.

Primal-dual hybrid gradient methods can solve large linear programs on GPUs, but their speed depends on delicately coordinated step sizes, restarts, and acceleration heuristics. GALLOP replaces these hand-tuned rules with a reinforcement learning policy that jointly picks continuous parameters and discrete restart decisions inside a generalized PDHG update. The approach is notable because the learned policy is dimension-agnostic and reportedly generalizes from small training instances to LPs hundreds of times larger without retraining.

Low-budget active learning seeks a tiny labeled subset—a coreset—that still trains an accurate model, which is crucial in medical domains where labeling is expensive. The authors propose using the Sinkhorn divergence, an entropic optimal transport distance, as a coreset quality criterion, and develop a Frank–Wolfe warm-started swap heuristic (FW-Swap) to optimize it. Their framework yields dimension-free generalization guarantees and shows competitive or superior accuracy on vision and EEG benchmarks with very small budgets.

This paper proves worst-case lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, explicitly permitting variance-reduction via same-sample oracle queries. Its main result shows that the stochastic barrier remains $\Omega(L^3 D_Y^2 \Delta \sigma^2 \varepsilon^{-6})$ even with mean-square smoothness. Complementary nonconvex--strongly-concave bounds are also provided. Together the results establish that variance reduction does not improve the fundamental accuracy exponent in the minimax setting.

This paper studies stochastic multi-level compositional optimization, where the objective is a nested composition of $T$ smooth non-convex functions and only stochastic per-layer function and gradient values are available. The core idea is to use momentum-based estimators to track inner function values level-by-level, and then apply the chain rule to build a momentum gradient estimator for the overall objective. It matters because it establishes that the optimal $\mathcal{O}(\epsilon^{-4})$ sample complexity is achievable under standard smoothness assumptions, closing a gap with single-level lower bounds without relying on the stronger average-smoothness conditions common in prior multi-level literature.

This paper tackles deterministic multi-impulse interplanetary rendezvous by embedding classical astrodynamics inside a reinforcement-learning policy. The proposed Reachability Analysis-Informed RL (RARL) framework maps bounded velocity perturbations into a local ellipsoidal waypoint set via the first-order position-from-velocity sensitivity matrix; the policy selects a waypoint, and a Lambert solver reconstructs the dynamically consistent impulsive arc. The core contribution is a physically structured action interface that supports both near-optimal nominal transfers and policy reuse across a family of dispersed departure states.

Standard gradient flow never reaches zero risk in finite time, while naive finite-time modifications drive the weights to the optimum with infinite speed. This paper formulates and solves a regularized least-time problem for the dissipation schedule $u(e)$ that controls the risk clock via $\dot{e}=-u(e)$. By minimizing $\int_0^{e_0}(\frac{\lambda}{2}|u'|^2+1/u)de$ subject to $u(0)=0$, the authors prove the optimal schedule is a cycloid and that it lands with the universal cusp $u^*(e)\sim c e^{2/3}$, placing the dynamics in the finite-time Hölder regime with vanishing weight speed.

This work tackles decentralized learning in multi-player stochastic games where each agent's state transitions depend only on its own state and action, but rewards are arbitrarily coupled. The core idea is to run independent online mirror descent in the dual space of local occupancy measures, using asynchronous dyadic confidence sets to handle unknown transition kernels without synchronized episodes. This matters because the guarantees scale with local state-action dimensions and mixing times rather than the joint product space, offering the first fully online, uncoordinated framework for this setting.

Spacecraft rendezvous and proximity operations currently require specialized engineers to translate high-level mission intent into dynamically feasible trajectories, creating a scalability bottleneck for distributed space systems. This paper introduces OrbitTAMP, a hierarchical task-and-motion planning framework that leverages pretrained LLMs to map natural-language commands into a partial mission specification, then systematically completes unspecified behavior, timing, and waypoint decisions via a domain-specific behavior graph and planning modules. Final trajectory optimization ensures dynamical feasibility and safety, aiming to provide an auditable, scalable language interface for spacecraft operations.