Provable Guarantees

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, with none the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 40

All topics

Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning
Sep 28, 2026Hanbin Zhou, Shangzhe Li, Alexander Braverman +1Entropy Regularized Reinforcement Learning Regularization
HKUST(GZ) · UNC Chapel Hill · Cornell University
Exploring Solver-Level Warmstarting for Neural Network Verification
Sep 22, 2026Annelot Bosman, Minghao Liu, Marta Kwiatkowska +2Neural Network Verification Neural Solvers
Leiden Institute of Advanced Computer Science, Leiden · University of Oxford, United Kingdom · Chair for AI Methodology, RWTH Aachen University, Germany +1
Human-LLM Deliberation as Interactive Proof: Conditions for Verifiability Without Transparency
Sep 21, 2026Baotong Zhang, Dean Foster, João SedocLarge Language Model Reliability Provable Guarantees
Stern School of Business New York University New York, NY, USA · Amazon New York, NY, USA
Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounders
Sep 16, 2026Weijian Yu, Jean HonorioLinear Structural Equation Models Latent Confounders
CIS, The University of Melbourne
Provable Guarantees for Spectral Structured Prediction
Sep 16, 2026Violet Zheng, Jean HonorioGraph Edge Sparsification Provable Guarantees
CIS, The University of Melbourne
Predictive Varanus: Combining CSP Conformance Monitoring with Predictive LTL Runtime Verification
Sep 15, 2026Angelo Ferrando, Matt Luckcuck, Pedro RibeiroRuntime Enforcement Linear Temporal Logics
Department of Physics, Informatics and Mathematics, University of Modena and Reggio Emilia, Italy · School of Computer Science, University of Nottingham, UK · Department of Computer Science, University of York, UK
Sparse Data Augmentation for Optimization with Provable Guarantees
Sep 8, 2026Behrooz Tahmasebi, Melanie WeberConvex Optimization Data Augmentation
Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA.
Differential 6-DOF Pose Estimation with Provable First-Order Immunity to Camera Calibration Errors
Aug 5, 2026Yueqiang Zhang, Liang Deng, Yi Zhang +5Category-Level Object Pose Estimation Extrinsic Calibration
State Key Laboratory of Radio Frequency Heterogeneous Integration, the Key Laboratory of Optoelectronic Devices and Systems of Ministry of Education and Guangdong Province, the Shenzhen Key Laboratory of Intelligent Optical Measurement and Detection, and the College of Physics and Optoelectronic Engineering, Shenzhen University, Shenzhen 518060, China · School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen 510275, China
The Order Is the Guarantee: Verifier-Budgeted Code Deletion with Static-First Learned Proposals
Aug 5, 2026Ruitong Li, Binjie Guo, Aisheng Mo +4Code Quality Verification Framework
University of Hong Kong · Zhejiang University · Dalian University of Technology +1
Trustworthy Machine Learning through the Lens of Combinatorial Optimization: Survey and Research Perspectives
Jul 8, 2026Thibaut Vidal, Julien FerryTrustworthy Artificial Intelligence Provable Guarantees
CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains, Department of Mathematics and Industrial Engineering, Polytechnique Montreal, Montreal, Canada
Untrusted Content Masking for Web Agents with Security Guarantees
Jul 6, 2026Kristina Nikolić, Egor Zverev, Javier Rando +3Untrusted Content Web Agents
ISTA · Anthropic
PRISM3D: Probabilistic Refinement and Robust Initialization for Physically Consistent Scene Modeling under Extreme Motion Blur
Jul 4, 2026Gopi Raju Matta, Reddypalli Trisha, Vemunuri Divya Madhuri +1Structure-From-Motion 3D Reconstruction
Computational Imaging Lab, Dept. of Electrical Engineering, IIT Madras
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Jul 4, 2026Marek Eliáš, Fabrizio Grandoni, Adam Polak +1Salesman Problem Approximation Algorithms
Maestro Order: A Model-Agnostic Orchestration Harness
Jun 22, 2026Hidayet AksuOrchestration Probabilistic Model Checking
Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficiently
Jun 22, 2026Stanley Wei, Juno KimLarge Reasoning Models Reinforcement Learning With Verifiable Reward
1Princeton University · University of California, Berkeley.
VeriBound: PAC-Bayesian Generalization Bounds for Process Reward Models Trained with Formal Verification Tools
Jun 17, 2026Amirul Rahman, Mohammed Sabih AlsharariReinforcement Learning With Verifiable Reward Process Reward Model
University of Malaya
Provably Safe, Yet Scalable Reinforcement Learning
Jun 12, 2026Kai S. Yun, Zeyang Li, Navid AzizanProvable Guarantees Certificates
MIT
SPEA2 $^+$ : Improved Density Estimation in SPEA2 with Provable Runtime Guarantees
Jun 10, 2026Duc-Cuong Dang, Andre Opris, Dirk SudholtEvolutionary Optimization Multi-Objective Optimization
University of Passau, Passau, Germany
Hedging on the Frontier: Learning New Tasks with Few Samples
May 29, 2026Tobias Wegel, Federico Di Gennaro, Geelon So +1Learnability Monotonicity
Department of Computer Science, ETH Zurich · Department of Computer Science and Engineering, UC San Diego
On the Stability and Realizability of Recurrent Polynomial Surrogate Ternary Logic Gate Networks
May 23, 2026Sai Sandeep Damera, Ryan Matheu, Aniruddh G. Puranic +2Differentiable Logic Gate Networks Recurrent Neural Networks
University of Maryland, College Park, USA
Less Effort, Shorter Proofs: Reinforcement Learning for Security Protocol Analysis in Tamarin
May 22, 2026Matthias Cosler, Cas Cremers, Bernd Finkbeiner +2Provable Guarantees Reinforcement Learning With Verifiable Reward
CISPA Helmholtz Center for Information Security, Saarbrücken, Germany · Technical University of Munich, Munich, Germany
Safety, Liveness, and Fairness in Quantitative Argumentation Dialogues
May 22, 2026Arunavo Ganguly, Julian Alfredo Mendez, Timotheus KampikArgumentation Frameworks Provable Guarantees
Department of Computing Science, Umeå University, Umeå, Sweden.
Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
May 17, 2026Shaddin Dughmi, Mahdi Haghifam, Yusuf Hakan KalayciInference-Time Reinforcement Learning With Verifiable Reward
University of Southern California · Data Science Institute at the University of Chicago · Northwestern University +2
Stress-Testing Neural Network Verifiers with Provably Robust Instances
May 16, 2026David Troxell, Yulia Alexandr, Sofia Hunt +2Neural Network Verification Verification Framework
Department of Statistics & Data Science, University of California, Los Angeles · Department of Mathematics, University of California, Los Angeles · Max Planck Institute for Mathematics in the Sciences, Leipzig
Probabilistic Verification of Recurrent Neural Networks for Single and Multi-Agent Reinforcement Learning
May 14, 2026Luca Marzari, Enrico MarchesiniReinforcement Learning With Verifiable Reward Neural Policies
1TU Wien, Vienna, Austria · 2Massachusetts Institute of Technology, Cambridge (MA), USA
Monitoring Data-aware Temporal Properties (Extended Version)
May 14, 2026Alessandro Gianola, Marco Montali, Sarah WinklerLinear Temporal Logics Runtime Enforcement
INESC-ID/Instituto Superior T´ecnico, Universidade de Lisboa, Portugal · Free University of Bozen-Bolzano, Italy
A Hierarchical Language Model with Predictable Scaling Laws and Provable Benefits of Reasoning
May 13, 2026Jason Gaitonde, Frederic Koehler, Elchanan Mossel +2Autoregressive Language Models Autoregressive Model
Duke University · University of Chicago · Massachusetts Institute of Technology +1
Vision-Based Runtime Monitoring under Varying Specifications using Semantic Latent Representations
May 13, 2026Bardh Hoxha, Oliver Schön, Hideki Okamoto +2Runtime Enforcement Partial Observability
Toyota NA R&D · ETH Zürich
Robust Probabilistic Shielding for Safe Offline Reinforcement Learning
May 11, 2026Maris F. L. Galesloot, Thomas Rhemrev, Nils JansenOffline Reinforcement Learning Probabilistic Safety
Radboud University · Nijmegen, The Netherlands · Ruhr University & Radboud University +1
MAGIQ: A Post-Quantum Multi-Agentic AI Governance System with Provable Security
May 7, 2026Sepideh Avizheh, Tushin Mallick, Alina Oprea +2Post-Quantum Cryptography Diffie-Hellman
University of Calgary Calgary, Alberta, Canada · Northeastern University Boston, MA, USA
Dataset Watermarking for Closed LLMs with Provable Detection
May 7, 2026Pengrun Huang, Kamalika Chaudhuri, Yu-Xiang WangLarge Language Model Watermarks Watermarks
Preprint. Under review.
Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics
May 2, 2026Zijie ZhouLarge Language Model Serving LLM Inference Optimization
Department of Industrial Engineering and Decision Analytics, HKUST
Probabilistic Verification of Neural Networks via Efficient Probabilistic Hull Generation
Apr 23, 2026Jingyang Li, Xin Chen, Hongfei Fu +1Neural Network Verification Probabilistic Safety
Shanghai Jiao Tong University, Shanghai 200240, China · University of New Mexico, Albuquerque, NM 87106, USA
Towards Certified Malware Detection: Provable Guarantees Against Evasion Attacks
Apr 22, 2026Nandakrishna Giri, Asmitha K. A., Serena Nicolazzo +2Malware Evasion
Department of Computer Applications, Cochin University of Science and Technology, India · Department of Electrical, Computer and Biomedical Engineering, University of Pavia, Via Adolfo Ferrata 5, 27100, Pavia, Italy
An intuitive rearranging of the Yates covariance decomposition for probabilistic verification of forecasts with the Brier score
Mar 4, 2026Bruno Hebling VieiraProbabilistic Forecasting Forecast
Methods of Plasticity Research, Department of Psychology, University of Zurich, Zurich, Switzerland · Methods of Plasticity Research, Department of Psychology, University of Zurich, Zurich,2026 Switzerland
Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance
Nov 30, 2025Robin Yadav, Shuo Xie, Tianhao Wang +1Stochastic Gradient Descent Signsgd
Toyota Technological Institute at Chicago · University of British Columbia · University of California, San Diego
A Provably-Correct and Robust Convex Model for Smooth Separable NMF
Nov 10, 2025Junjun Pan, Valentin Leplat, Michael Ng +1Nonnegative Matrix Factorization Support Vector Machines
Department of Mathematics, Hong Kong Baptist University, Hong Kong. · Institute of Data Science and Artificial Intelligence, Faculty of Computer Science and Engineering, Innopolis University. · Department of Mathematics and Operational Research, Université de Mons, Rue de Houdain 9, 7000 Mons, Belgium.
Re:Form -- Reducing Human Annotations in Scalable Formal Software Verification with RL in LLMs: A Preliminary Study on Dafny
Jul 22, 2025Chuanhao Yan, Fengdi Che, Xuhan Huang +12Formal Verification Human Annotations
Shanghai AI Lab · Tsinghua University · University of Alberta +5
Reliable learning in challenging environments
Apr 6, 2023Maria-Florina Balcan, Steve Hanneke, Rattana Pukdee +1Learnability Provable Guarantees
Carnegie Mellon University · Purdue University
Propheticus: Machine Learning Framework for the Development of Predictive Models for Reliable and Secure Software
Sep 6, 2018João R. Campos, Marco Vieira, Ernesto CostaEarly Failure Prediction Software
DEI/CISUC, University of Coimbra, Portugal

Sep 28, 2026, cs.LGJ/K move · Enter open · S save

Provable Benefits of Regularization: Fast Rates for Adversarial Imitation Learning

Hanbin Zhou, Shangzhe Li, Alexander Braverman, Weitong Zhang

HKUST(GZ) · UNC Chapel Hill · Cornell University

Entropy Regularized Reinforcement Learning Regularization Provable Guarantees

Open paper AskPDF arXiv

We study adversarial imitation learning (AIL), in which an agent learns to imitate expert demonstrations by optimizing a policy against an adversarial reward that distinguishes expert and learner behavior. Historically, reward regularization and entropy-based policy regularization are key components of empirically successful methods such as GAIL and LS-IQ, yet their finite-sample benefits remain underexplored. We establish fast rates for jointly regularized AIL in finite-horizon Markov decision processes with general function approximation. Our model-free algorithm, Dually Regularized AIL, combines KL policy regularization with a quadratic reward penalty weighted by expert and learner occupancies. With K online episodes and N expert trajectories, we prove a

\widetilde{O}\left(\frac{1}{K}+\frac{1}{N}\right)

bound on the regularized imitation gap for fixed regularization parameters. Our analysis combines an online mirror descent construction for general convex reward classes to control estimation error from finite expert data and stochastic learner feedback, with a sharp analysis of optimistic KL-regularized policy learning. To the best of our knowledge, Dually Regularized AIL is the first algorithm to simultaneously achieve

\widetilde{O}\left(\frac{1}ε\right)

sample complexity in both expert demonstrations and online interactions for this regularized AIL objective, even with stochastic experts. These results provide a rigorous characterization of the complementary statistical benefits of reward and policy regularization in AIL.

Momentum

Related topics

Latest papers 40