295 papers
This paper establishes that history-dependent policies with sublinear expected regret are robust-optimal for non-rectangular average-reward robust MDPs without requiring rectangularity, and introduces a transient-value framework with an epoch-based policy that achieves constant-order finite-time performance by combining worst-case optimality with online learning.
This paper proposes a robust, data-driven framework for assortment optimization that maximizes worst-case expected revenue under potential customer preference shifts, establishing computational tractability and deriving statistically optimal algorithms with tight sample complexity bounds to ensure reliable generalization.
This paper establishes new convergence rates for the last iterate of stochastic gradient descent and stochastic heavy ball methods in parametric settings with globally convex or non-convex objectives having -Hölder gradients, utilizing discrete Gronwall's inequality to derive improved bounds without relying on the Robbins-Siegmund theorem.
This paper establishes the first global linear convergence guarantees for a dynamic smoothing variant of Iteratively Reweighted Least Squares (IRLS) in robust subspace and affine subspace recovery, extending these theoretical results to nonconvex optimization on Riemannian manifolds and demonstrating their practical utility in low-dimensional neural network training.
This paper proposes a data-driven robust Markov decision process framework for Borel spaces with unknown disturbance distributions, utilizing ambiguity sets defined by distance functions to establish finite-sample performance guarantees, probabilistic convergence rates, and out-of-distribution bounds that empirical MDPs fail to provide.
This paper introduces a family of mean-normalized matrix operator norms to derive width-independent smoothness bounds for deep neural networks, leading to the development of MOGA, a row/column-normalized optimizer that enables stable hyperparameter transfer across model widths and outperforms Muon in speed while maintaining competitive performance.
This paper introduces OptEMA, a novel adaptive Exponential Moving Average optimizer that achieves nearly optimal convergence rates in both stochastic and zero-noise regimes without requiring prior knowledge of Lipschitz constants or manual hyperparameter tuning.
This paper proposes a rigorous optimal control framework that models Transformer training as a lifted Markov decision process on probability measures, establishing the existence of globally optimal policies and providing a quantized, gradient-free training alternative that respects key architectural constraints like input independence and positional encoding.
This paper proposes a Velocity Verlet-based optimization algorithm for Variational Quantum Eigensolvers that leverages an inertial velocity term to efficiently navigate complex energy landscapes, demonstrating superior performance over standard optimizers like L-BFGS-B in achieving chemical accuracy and lower final energies for H and LiH molecules.
This paper develops a game-theoretic framework to analyze the incentives and efficiency losses in informal, privatized transit systems, demonstrating that targeted interventions like centralized routing and cross-subsidization can effectively mitigate performance gaps between decentralized profit-driven operations and optimal system outcomes.
This paper empirically demonstrates that while the runtime of local greedy search for optimizing Sherrington-Kirkpatrick spin glass Hamiltonians is universal across various coupling distributions, the performance of Parisi's local reluctant search is surprisingly non-universal and sensitive to the specific entry distribution, particularly when couplings have discrete support.
This paper introduces a unified Davis-Wielandt shell framework for the graphical stability analysis of MIMO LTI systems, proposing a novel rotated scaled relative graph (-SRG) concept that yields the least conservative closed-loop stability criterion among existing two-dimensional graphical conditions.
This paper establishes robustness bounds for discrete-time stochastic optimal control under Wasserstein model approximation, demonstrating that the performance loss of policies derived from approximate models is controlled by the Wasserstein-1 distance between transition kernels, thereby enabling rigorous sample complexity analysis for empirical model and noise distribution learning where stronger convergence criteria may fail.
This paper presents a geometrically convergent exact solution and a highly parallelizable algorithm for spatial hypercube queueing models with heterogeneous service rates, demonstrating significant computational speedups over traditional solvers and simulations for large-scale emergency service applications.
This paper solves an intertemporal utility maximization problem with a no-borrowing constraint and stochastic excess returns in the Kim-Omberg framework by employing Lagrange duality to transform the primal problem into a dual singular control problem, which is then characterized via an auxiliary two-dimensional optimal stopping problem to derive optimal consumption and portfolio strategies.
This paper introduces calculus rules for computing Kurdyka-Łojasiewicz exponents via rank theorems and Lie group actions, offering a smoothness-free framework to establish linear convergence for diverse algorithms in matrix factorization and neural networks, particularly for nonisolated local minima.
This paper proposes unfolding-free majorization-minimization algorithms for nonnegative CP and Tucker tensor decompositions under -divergences, utilizing tensor contractions and joint update strategies to achieve theoretical convergence guarantees and significant computational speedups over traditional unfolding-based methods.
This paper introduces a stratification framework for nonlinear semidefinite programming that leverages the geometry of nonsmooth KKT systems to establish new regularity conditions and develop a globally convergent Gauss–Newton algorithm with local quadratic convergence.
This paper establishes the tightness of known convergence rates for the Polyak stepsize in gradient descent by constructing worst-case functions, demonstrates its ability to escape worst-case scenarios via floating-point errors, and proves its universality across diverse function classes including those with Hölder smoothness and growth conditions.
This paper establishes the existence, uniqueness, and global regularity of positive classical solutions to quasilinear Hamilton–Jacobi–Bellman equations on bounded convex domains via a constructive weighted monotone iteration scheme, while providing a probabilistic derivation from controlled Itô diffusions and demonstrating applications in stochastic production planning and image restoration.