Gittins index strategy offers near-UCB regret guarantees for multi-armed bandits.
problem Optimizing decisions in multi-armed bandit problems with limited time.
method Analysis of Gittins index strategy with finite-time bounds and experimental validation.
result Regret guarantees comparable to UCB algorithm with finite-time bounds.
The paper analyzes deep neural networks using control theory to set a time limit for their convergence.
problem Understanding the finite-time convergence of deep neural networks.
method Lyapunov based analysis of the loss function, control theory framework, finite-time control of non-linear systems.
result A priori guarantees of finite-time convergence for deep neural networks are provided.
Algorithm estimates human decision-making in high-dimensional states with finite-time guarantees.
problem Estimating optimal policies and measures of fit in dynamic decision models with high-dimensional state spaces.
method Single-loop estimation algorithm with stochastic gradient steps for reward maximization.
result Algorithm converges to a stationary solution with finite-time guarantees and approximates maximum likelihood sublinearly.
New continuous-time optimization algorithms converge in finite time to local minima.
problem Finding local minima in optimization problems.
method Discontinuous dynamical systems with finite-time convergence via Lyapunov-based differential inequality.
result Finite-time convergence to strict local minima with provable settling time.
Simulated annealing is a popular method for approaching the solution of a global optimization problem. Existing results on its performance apply to discrete combinatorial optimization where the optimization variables can assume only a finite set of possible values. We introduce a new general formulation of simulated an…
First-order method solves stochastic bilevel optimization with linear constraints.
problem Stochastic bilevel optimization with linear constraints and noise.
method Developed a novel framework using gradient-based techniques and smoothed penalty functions.
result Achieved finite-time convergence guarantees for (δ,ε)-Goldstein stationary points. Meta-learning control algorithm with finite-time guarantees for unknown systems.
problem Online control of unknown linear systems with constraints.
method Provable regret guarantees for an iterative control algorithm.
result Regret bounds of O(T3/4) for controller cost and constraint violation. Paper analyzes finite-time guarantees for preference-based RL.
problem Understanding finite-time guarantees for preference-based RL.
method Combines dueling bandits and policy search to navigate state space.
result Identifies best policy up to accuracy ε with high probability.
Novel algorithm reduces computational burden in IRL with finite-time guarantees.
problem Efficiently recover reward function and optimal policy from expert behavior.
method Single-loop algorithm that maximizes likelihood after each policy improvement step.
result Algorithm provably converges to a stationary solution with finite-time guarantees.
This work achieves finite-time stabilization of uncertain LQ systems using random feedbacks.
problem Stabilizing linear systems with unknown dynamics in finite time.
method Random linear feedbacks to achieve finite-time stabilization.
result High probability guarantees for finite time stabilization of LQ systems.
New algorithm minimizes regret in stochastic bandits.
problem Minimizing cumulative regret in stochastic bandits.
method Introduces anytime OCUCB algorithm with strong regret guarantees.
result Upper and lower bounds nearly match for new algorithm.
The paper analyzes NPG in finite-horizon MDPs and provides convergence guarantees.
problem Finite-horizon Markov Decision Processes with known dynamics and transition kernels.
method Exact analysis of Natural Policy Gradient (NPG) with constant and increasing step sizes.
result NPG converges sublinearly with a rate of O(H^2/t) and linearly with a rate of O((1-1/θρ)^t).
SGLD helps escape local minima in non-convex learning problems.
problem Non-convex optimization in machine learning.
method Stochastic Gradient Langevin Dynamics with Gaussian noise.
result Finite-time guarantees for SGLD to find approximate minimizers.
We consider a discrete-time financial market model with finite time horizon and give conditions which guarantee the existence of an optimal strategy for the problem of maximizing expected terminal utility. Equivalent martingale measures are constructed using optimal strategies.
New algorithms for risk-averse bandits minimize regret in finite time.
problem Minimizing regret in finite time for bandit problems.
method Proposes two algorithms for selecting the most probable arm with a good risk-return trade-off.
result Upper bound for the minimum number of experiments before commitment to guarantee a bound on regret.
Paper analyzes finite-time convergence of double Q-learning.
problem Overestimation issue in Q-learning.
method Finite-time analysis of double Q-learning.
result Convergence to ε-accurate neighborhood in finite iterations.
RANDPOL uses randomized networks for efficient reinforcement learning in continuous state and action MDPs.
problem Efficient reinforcement learning in environments with continuous state and action spaces.
method RANDPOL uses randomized function approximation to represent policy and value functions, providing finite time guarantees and improved numerical performance.
result RANDPOL achieves better numerical performance and provides finite time guarantees compared to deep neural network based algorithms.
Researchers analyze TD learning with linear approximations for efficiency.
problem Challenges in analyzing the statistical efficiency of TD learning.
method Finite time analysis using linear function approximation and stochastic gradient descent techniques.
result Simple and explicit finite time analysis of TD learning with linear function approximation.
Study verifies Joyce's conjectures for circle-invariant Lagrangian surfaces.
problem Verifying Joyce's conjectures for specific Lagrangian surfaces.
method Continuation of Lagrangian mean curvature flow through finite time neck pinches.
result Flow converges to a chain of special Lagrangians, verifying conjectures.
This work analyzes actor-critic methods for faster convergence.
problem Finite-time analysis and sample complexity of two-time-scale actor-critic methods.
method Non-asymptotic analysis under non-i.i.d. setting, proving convergence to first-order stationary point.
result Actor-critic method finds a first-order stationary point with ildeO(ε−2.5) sample complexity. Study analyzes FLMC for non-convex optimization with finite-time bounds.
problem Non-convex optimization challenges in machine learning.
method Fractional Langevin Monte Carlo (FLMC) with α-stable noise.
result Finite-time bounds for expected suboptimality of FLMC.
Single-timescale analysis improves convergence in multi-sequence stochastic approximation.
problem Finite-time convergence of nonlinear stochastic approximation with multiple coupled sequences.
method Smoothness property of fixed points and analysis of fine-grained single-timescale SA.
result Improved iteration complexity for achieving ε-accuracy in multi-sequence single-timescale SA.
The paper provides guarantees for feedback control with sensor errors.
problem Certifying performance and safety in feedback control systems with sensor errors.
method Solving a supervised learning problem to characterize sensor errors and providing uniform error bounds.
result Finite-time convergence rate on sub-optimality of using a regressor in closed-loop for waypoint tracking.
This work analyzes Q-learning with adaptive stepsizes for finite-time convergence.
problem Finite-time convergence analysis for average-reward Q-learning with adaptive stepsizes. method Adaptive stepsizes as local clocks, time-inhomogeneous Markovian reformulation, almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities.
result Convergence rates of ildeO(1/k) for mean-square and pointwise mean-square convergence. Study finite time singularities in Ricci flow with bounded scalar curvature.
problem Understanding finite time singularities in Ricci flow with bounded scalar curvature.
method Analyzing blow-up sequences of locally Type I singularities.
result Every blow-up sequence of a locally Type I singularity has a specific property.
Finite-time degeneration of harmonic map flows on surfaces is proven under specific conditions.
problem Finite-time degeneration of harmonic map flows on surfaces.
method Proving finite-time degeneration under specific conditions of image stretching rate.
result Sharp conditions for finite-time degeneration of harmonic map flows are established.
New framework for Bayesian inference using neural Schrödinger-Föllmer flows.
problem Approximate Bayesian inference in large datasets.
method Stochastic control, Schrödinger bridges, SDE-based models.
result Advocates stochastic control as a finite time and low variance alternative to SGLD.
This paper investigates the problem of maximizing expected terminal utility in a (generically incomplete) discrete-time financial market model with finite time horizon. In contrast to the standard setting, a possibly non-concave utility function U is considered, with domain of definition R. Simple conditio…
Finite-time blow-up in Yang-Mills flow for small energy initial connections.
problem Finite-time blow-up of Yang-Mills flow solutions.
method Analyzing the Yang-Mills flow on Riemannian and Kähler manifolds.
result Finite-time blow-up occurs for small energy initial connections.
This paper improves SGMs by using a predictor-corrector scheme to converge faster.
problem Theoretical and practical limitations of existing SGMs when T1o∞. method Integrates a predictor-corrector scheme after the forward process to converge in finite time.
result Convergence guarantees for SGMs require only a fixed finite time T1. Estimates for VPMCF show ancient MCF solutions and finite-time behavior.
problem Volume Preserving Mean Curvature Flow (VPMCF) behavior and singularities.
method Nonlocal estimates and blowup analysis.
result Ancient solutions to MCF and finite-time behavior of VPMCF.
The paper analyzes the InfoNCE loss under different temperature schedules using Langevin dynamics.
problem Understanding the dynamics of InfoNCE loss under fixed versus annealed temperature schedules.
method Modeling embedding evolution under Langevin dynamics on a compact Riemannian manifold, with theoretical guarantees for convergence.
result Slow logarithmic inverse-temperature schedules ensure convergence to globally optimal representations, while faster schedules risk suboptimal minima.
Study optimal adaptive allocation for multi-armed bandits with Markovian rewards.
problem Optimal adaptive allocation for multi-armed bandits with Markovian rewards.
method Round-robin Kullback-Leibler upper confidence bounds for optimal adaptive allocation.
result Logarithmic dependence of regret on time horizon, asymptotically optimal.
New algorithm for nonstationary multi-armed bandits with optimal performance.
problem Nonstationary multi-armed bandits with changing model parameters over time.
method Adaptive Resetting Bandit (ADR-bandit) algorithm using adaptive windowing techniques.
result ADR-bandit achieves nearly optimal performance in both abrupt and gradual changes.
We show that if on a compact Kahler threefold there is a solution of the Kahler-Ricci flow which encounters a finite time collapsing singularity, then the manifold admits a Fano fibration. Furthermore, if there is finite time extinction then the manifold is Fano and the initial class is a positive multiple of the first…
Last-iterate guarantees for learning in co-coercive games under noisy feedback.
problem Learning in co-coercive games with noisy feedback.
method Vanilla stochastic gradient descent with a new noise model.
result Last-iterate bound of order O(log(t)/t1/3) for co-coercive games. No finite-time singularities in Yang-Mills flow in 4D.
problem Finite-time singularities in Yang-Mills flow.
method Weighted energy identity and sharp decay estimates.
result Long-time existence of Yang-Mills flow in 4D.
Unified analysis of stochastic iterative algorithms using Lyapunov functions.
problem Analyzing convergence of stochastic iterative algorithms for fixed-point equations.
method Lyapunov-based techniques for finite-time analysis of stochastic approximation algorithms.
result Unified mean-square convergence guarantees for various algorithms.
We give concentration bounds for martingales that are uniform over finite times and extend classical Hoeffding and Bernstein inequalities. We also demonstrate our concentration bounds to be optimal with a matching anti-concentration inequality, proved using the same method. Together these constitute a finite-time versi…
New algorithm learns Koopman operator online, with complexity control and convergence guarantees.
problem Online learning of Koopman operator for general nonlinear systems.
method Sparse online learning via stochastic approximation, RKHS action, CME operator.
result Provably convergent algorithm with finite-time guarantees in mis-specified setting.
NSGLD improves SGLD for non-convex optimization problems.
problem Optimizing non-convex objectives efficiently.
method Introducing non-reversible SGLD by adding an anti-symmetric matrix to the drift term of the Langevin diffusion.
result NSGLD converges faster to the same stationary distribution with non-asymptotic guarantees.
Study shows Whitney sphere collapses to a point in finite time.
problem Understanding the evolution of Whitney sphere under mean curvature flow.
method Investigated equivariant Lagrangian spheres in \(\mathbb{C}^n\) using mean curvature flow.
result Equivariant Lagrangian spheres collapse to a point in finite time and converge to a plane with multiplicity two.
Study of deep neural networks using finite-time Lyapunov exponents.
problem Understanding the geometric structures in input space formed by deep neural networks.
method Analogy with dynamical systems, computing finite-time Lyapunov exponents.
result Ridges of large positive exponents divide input space into regions associated with different classes.
This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits t…
This paper provides guarantees for DFM models using KL divergence.
problem Ensuring generative models match target distributions efficiently.
method Using KL divergence and Brownian motion bridge for generative models.
result Non-asymptotic guarantees for DFM models under specific conditions.
Study on SA with heavy-tailed and LRD noise, establishing finite-time bounds.
problem Analyzing stochastic approximation under heavy-tailed and LRD noise.
method Noise-averaging argument to regularize impact of non-classical noise.
result Established first finite-time moment bounds for SA under heavy-tailed and LRD noise.
Study on fake stationary Volterra Heston model for non-stationary processes.
problem Non-stationary nature of true Volterra equations.
method Weak notion of stationarity (fake stationary regime) for inhomogeneous affine Stochastic Volterra equations.
result Existence of limiting distributions in the long run, which may depend on initial state.
In this note we study finite-time singularities in the Chern-Ricci flow. We show that finite-time singularities are characterized by the blow-up of the scalar curvature of the Chern connection.