Variance Reduction

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, up 67% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 61

All topics

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization
Oct 1, 2026Jiayi Song, Zi XuConvex Optimization Lower Bounds
Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China
Sufficiently Reduced Distributional Regression
Sep 24, 2026Alexander Henzi, Tiange Liu, Xinwei ShenDimensionality Reduction Exponential Family
Tsinghua University, Department of Statistics and Data Science · University of Washington
Revisiting Distributed Sign-Based Variance Reduction
Sep 16, 2026Wei Jiang, Zechao Li, Lijun ZhangDecentralized Optimization Variance Reduction
School of Computer Science and Engineering, Nanjing University of Science and Technology, China · National Key Laboratory for Novel Software Technology,Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
Same Flow, Different Paths: Variance Reduction in Flow Matching
Sep 15, 2026Alexander TyurinConditional Flow Matching Variance Reduction
AXXX, Moscow, Russia · Applied AI Institute, Moscow, Russia
Solving Finite-sum Coupled Compositional Optimization via Multi-block-Single-probe Estimator
Sep 14, 2026Wei Jiang, Sifan Yang, Yibo Wang +2Stochastic Optimization Variance Reduction
School of Computer Science and Engineering, Nanjing University of Science and Technology, China · 2State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
When Local Variance Optimality Is Not Enough: RoPE-Aligned Q/K Rotations for Dynamic 4-Bit Quantisation
Aug 13, 2026Shuhan Wang, Yilin Luo, Nan Xu +1Post-Training Quantization Rotary Position Embedding
Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization
Aug 12, 2026TaeHo Yoon, Nicolas LoizouStochastic Approximation Variance Reduction
Department of Applied Mathematics and Statistics & Mathematical Institute for Data Science, Johns Hopkins University
Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size
Aug 12, 2026Chenhan Jin, Shengze Xu, Binghui Xie +4Proximal Operators Stochastic Gradient Descent
1The Chinese University of Hong Kong · University of Utah · 3Beijing Normal-Hong Kong Baptist University +1
Arm2Air: Cross-Embodiment Skeleton Transfer for 3D Relay Formation
Jul 30, 2026Dohun Lee, Kyeonghyun Yoo, Seokmin Kim +3Obstacle Avoidance Cross-Embodiment Transfer
Department of Electrical and Electronic Engineering, Korea University, Seoul, Republic of Korea
Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
Jul 26, 2026Heyang Zhao, Tianyuan Jin, Weixin Wang +3Stochastic Multi-Armed Bandits Variance Reduction
Department of Computer Science, University of California, Los Angeles · Department of Electrical and Computer Engineering, National University of Singapore · Department of Biostatistics & Bioinformatics, Duke University +2
On the Convergence of Stochastic Low-Rank Adaptation
Jul 24, 2026Ru Wang, Chengchang Liu, John C. S. LuiLow-Rank Adaptation Framework Multi-Lora
The Chinese University of Hong Kong · Westlake University
Online Variance Reduction for Domain Adaptation on Streaming Data
Jul 22, 2026Andrea NapoliVariance Reduction Domain Adaptation
Department of Electronics and Computer Science University of Southampton, UK
Variance-reduced Domain Adaptation using Paired Sampling
Jul 22, 2026Andrea NapoliDomain Adaptation Variance Reduction
Department of Electronics and Computer Science University of Southampton, UK
Accelerating A/B-Tests with Counterfactual Estimation: Reducing Variance through Policy Overlap
Jul 16, 2026Olivier JeunenVariance Reduction Heterogeneous Treatment Effects
Independent Researcher Antwerp, Belgium
Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite
Jul 11, 2026Yushi Hirose, Hiroo Irobe, Takafumi KanamoriSemi-Supervised Learning Empirical Risk Minimization
Department of Mathematical and Computing Science, Institute of Science Tokyo · 2RIKEN Center for Advanced Intelligence Project
Solving Stochastic Fixed-Point Equations with High Probability
Jul 10, 2026Jelena DiakonikolasFixed-Point Iteration Stochastic Approximation
Department of Computer Sciences University of Wisconsin-Madison
Variance Reduction on the Camera Axis: Multi-View Score Distillation for 3D
Jun 29, 2026Marian Lupascu, Mihai Sorin Stupariu, Ionut MironicaScore-Based Diffusion Model Multi-View
Department of Computer Science, University of Bucharest, Romania · Adobe Research
Variance Reduction for Stochastic Gradient Generalized Non-reversible Langevin Monte Carlo Algorithms
Jun 27, 2026Bingye Ni, Xiaoyu Wang, Yingli Wang +1Langevin Dynamics Variance Reduction
FinTech Thrust, Hong Kong University of Science and Technology (Guangzhou), Guangzhou, Guangdong, People's Republic of China · School of Mathematical Science, Fudan University, Shanghai, People's Republic of China · Department of Mathematics, Florida State University, Tallahassee, Florida, United States of America
Stochastic Gradient Optimization with Model-Assisted Sampling
Jun 25, 2026Jonne Pohjankukka, Jukka HeikkonenStochastic Gradient Descent Variance Reduction
University of Turku, Department of Computing
Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
Jun 21, 2026Shengchao Zhao, Yongchao LiuFederated Learning Fedavg
School of Mathematics, China University of Mining and Technology, Xuzhou, China · School of Mathematical Sciences, Dalian University of Technology, Dalian, China
On the Variance of Temporal Difference Learning and its Reduction Using Control Variates
Jun 18, 2026Hsiao-Ru Pan, Bernhard SchölkopfTemporal Difference Variance Reduction
Max Planck Institute for Intelligent Systems, Tübingen · ELLIS Institute Tübingen · ETH Zürich
A Risk Decomposition Framework for Pre-Hoc Fine-Tuning Prediction
Jun 16, 2026Yuxiang Luo, Chen Wang, Nan TangContinual Fine-Tuning Model Fine-Tuning
The Hong Kong University of Science and Technology (Guangzhou).
Decoupling Inference from State Updates in Low-Latency Feature Engines via Probabilistic Thinning
Jun 15, 2026Augusto Peres, Iker Perez, Pedro Valdeira +4Streaming Persistence
Feedzai
Variance Reduction for Non-Log-Concave Sampling with Applications to Inverse Problems
Jun 15, 2026M. Berk Sahin, Ahmet Ege Tanriverdi, Behzad Sharif +1Log-Concave Distributions Variance Reduction
School of Electrical and Computer Engineering, Purdue University, West Lafayette, Indiana, USA · School of Electrical and Computer Engineering, University of Southern California, California, USA · School of Biomedical Engineering, Purdue University, West Lafayette, Indiana, USA
Learning the generating functional for variance reduction in lattice QCD
Jun 14, 2026Ryan Abbott, Yang Fu, Daniel C. Hackett +3Effective Field Theory Variance Reduction
1Physics Department, Columbia University, New York, NY 10027, USA · Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA · 3The NSF AI Institute for Artificial Intelligence and Fundamental Interactions +3
SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums
Jun 14, 2026Igor Sokolov, Laurent Condat, Peter RichtárikVariance Reduction Stochastic Gradient Descent
*Center of Excellence for Generative AI, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia. · KAUST
The Risk Shadow of Principal Component Analysis: When 99.9999% Variance Preservation Causes Catastrophic Decision Errors
Jun 12, 2026Hamidou TembinePrincipal Component Analysis Long-Tailed Distribution
Department of EECS, School of Engineering, UQTR, Canada. Learning and Game Theory Laboratory (LnG Lab), TIMADIE.
Effective Reinforcement Learning for Agentic Search by Recycling Zero-Variance Queries During Training
Jun 9, 2026João Coelho, João Magalhães, Bruno Martins +1Offline Reinforcement Learning Agentic Search
Language Technologies Institute, Carnegie Mellon University, United States · Instituto Superior Técnico and INESC-ID, University of Lisbon, Portugal · NOVA LINCS, NOVA School of Science and Technology, Portugal
Pointwise Complexity for Gaussian Fields: Upper Envelopes, Algorithmic Lower Bounds, and Separation
Jun 6, 2026Yunbei XuGaussian Process Gaussian Primitives
National University of Singapore
X4Val: Learning Neural Surrogates for Variance-Reduced Policy Evaluation
Jun 3, 2026Rachel Luo, Michael Watson, Apoorva Sharma +6Variance Reduction Autonomous Driving
NVIDIA Research, Santa Clara, CA, USA · Harvard University, Cambridge, MA, USA · Stanford University, Stanford, CA, USA
Variance Reduction for Heavy-Tailed Monetization Metrics in Ranking Experiments via Post-Stratification
Jun 2, 2026Neeti Pokharna, Olivier Jeunen, Yatharth Saraf +1Click-Through Rate Prediction Variance Reduction
ShareChat · Bengaluru, Karnataka, India · Aampe +3
Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee
May 31, 2026Shion TakenoBayesian Optimization Variance Reduction
1Nagoya University
Variance-sensitive Thompson sampling for generalised linear bandits, revisited
May 29, 2026Tom Perneczky, Marc Abeille, David JanzThompson Sampling Variance Reduction
University of Oxford · Criteo AI Lab
Riemannian Stochastic Optimization for Sufficient Dimension Reduction
May 29, 2026Thibault Pautrel, François PortierDimensionality Reduction Riemannian Optimization
Laboratoire des Signaux et Systèmes (L2S), CentraleSupélec, Université Paris-Saclay, Gif-sur-Yvette, France · ENSAI, CREST, Bruz, France
Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens
May 29, 2026Junbin Qiu, Zhaowei Hong, Renzhe Xu +1Hessian Zeroth-Order
Hong Kong University of Science and Technology (Guangzhou) · Shanghai University of Finance and Economics
Zeroth-Order Non-Log-Concave Sampling with Variance Reduction and Applications to Inverse Problems
May 28, 2026M. Berk Sahin, Behzad Sharif, Abolfazl HashemiLog-Concave Distributions Variance Reduction
Elmore School of Electrical and Computer Engineering, Purdue University, West Lafayette, USA · Weldon School of Biomedical Engineering, Purdue University, West Lafayette, USA
Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
May 27, 2026Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1Markov Decision Processes Optimal Policies
Chung-Ang University · Seoul National University · Columbia University
Refined Analysis of Entropy-Regularized Actor-Critic
May 23, 2026Safwan Labbi, Paul Mangold, Daniil Tiapkin +1Entropy Regularized Reinforcement Learning Soft Actor-Critic
CMAP, CNRS, École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France · Université Paris-Saclay, CNRS, LMO, 91405, Orsay, France · Google DeepMind +2
Variance Reduction for Expectations with Diffusion Teachers
May 20, 2026Jesse Bettencourt, Xindi Wu, Matan Atzmon +2Variance Reduction Variance
1NVIDIA · University of Toronto · 3Princeton University
Multi-Head Attention as Ensemble Nadaraya-Watson Estimation: Variance Reduction, Decorrelation, and Optimal Head Diversity
May 18, 2026Ernest FokouéMulti-Head Attention Intrinsic Dimensionality
School of Mathematics and Statistics, College of Science Rochester Institute of Technology Rochester, New York 14623, USA
New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions
May 18, 2026Xinzhe Yuan, William de Vazelhes, Bin Gu +1Variance Reduction Adaptive Thresholding
Harbin Institute of Technology · IASM, Harbin Institute of Technology · Mohamed bin Zayed University of Artificial Intelligence +2
Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation
May 14, 2026Zhankun Luo, Antesh Upadhyay, M. Berk Sahin +3Variance Reduction Stochastic Optimization
School of Electrical and Computer Engineering and Purdue University West Lafayette, IN 47907 · Department of Computer Science Purdue University West Lafayette, IN 47907
State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives
May 13, 2026Hoang-Son Tran, Pranav Gupta, Rémi Bardenet +1Determinantal Point Process Subsampling
Department of Mathematics National University of Singapore · Univ. Lille, CNRS, Centrale Lille UMR 9189 – CRIStAL
On Variance Reduction in Learning Mean Flows
May 10, 2026Juanwu Lu, Ziran WangLatent Flow Velocity Field
Purdue University
Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
May 9, 2026Zhirayr Tovmasyan, Artavazd Maranjyan, Peter RichtárikVariance Reduction Stochastic Gradient Descent
KAUST
DARTS: Targeting Prognostic Covariates in Budget-Constrained Sequential Experiments
May 7, 2026Kateryna Husar, Alexander VolfovskyCovariate Balancing Bayesian Experimental Design
Department of Statistical Science Duke University Durham, NC 27705
ORTHOBO: Orthogonal Bayesian Hyperparameter Optimization
May 7, 2026Maresa Schröder, Pascal Janetzky, Michael Klar +1Variance Reduction Monte Carlo
LMU Munich · Munich Center for Machine Learning · Bosch Center for Artificial Intelligence
Accelerating LMO-Based Optimization via Implicit Gradient Transport
May 7, 2026Won-Jun Jang, Si-Hyeon LeeAdaptive Optimizers Gradient
School of Electrical Engineering · Korea Advanced Institute of Science and Technology (KAIST) · Daejeon, South Korea
Order Matters: Improving Domain Adaptation by Reordering Data
May 6, 2026Andrea Napoli, Paul WhiteDomain Adaptation Order Matters
University of Southampton, UK
Rethinking the Rank Threshold for LoRA Fine-Tuning
May 5, 2026Juneyoung ParkModel Fine-Tuning Cross-Entropy Losses
OptAI Inc.
Taming Noise-Induced Prototype Degradation for Privacy-Preserving Personalized Federated Fine-Tuning
Apr 30, 2026Yuhua Wang, Qinnan Zhang, Xiaodong Li +6Federated Learning Model Fine-Tuning
School of Artificial Intelligence, Beihang University · School of Statistics, Renmin University of China · School of Computer Science and Engineering, Beihang University
An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to $Φ$ -Regret Minimization
Apr 21, 2026Gabriele Farina, Juan Carlos PerdomoVariance Reduction Monotone Variational Inequalities
MIT EECS · New York University
Similarity-based Portfolio Construction for Black-box Optimization
Apr 20, 2026Catalin-Viorel Dinu, Diederick Vermetten, Carola DoerrBlack-Box Optimization Algorithm Selection
Sorbonne Université, CNRS, LIP6
Softmax gradient policy for variance minimization and risk-averse multi armed bandits
Mar 31, 2026Gabriel TuriniciStochastic Multi-Armed Bandits Variance Reduction
CEREMADE, Université Paris Dauphine - PSL, CNRS, Paris, France
Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions
Mar 16, 2026Quoc Tran-Dinh, Nghia Nguyen-TrungVariance Reduction Solver Iterations
Department of Statistics and Operations Research The University of North Carolina at Chapel Hill 318 Hanes Hall, UNC-Chapel Hill, NC 27599-3260.
The Optimal Token Baseline: Variance Reduction for Long-Horizon LLM-RL
Feb 6, 2026Yingru Li, Jiawei Xu, Ziniu Li +10Large Language Model Reinforcement Learning Variance Reduction
The Chinese University of Hong Kong, Shenzhen · Fudan University · Hong Kong University of Science and Technology +4
Correcting Boundary Bias and Observation Independence in Bayesian Experimental Design
Feb 2, 2026Sanna Jarl, Jens Sjölund, Jonathan J. S. Scragg +1Bayesian Experimental Design Gaussian Process
Department of Material Science & Engineering Uppsala University RISE · Department of Information Technology Uppsala University · RISE
It's all In the (Exponential) Family: An Equivalence between Maximum Likelihood Estimation and Control Variates for Sketching Algorithms
Jan 29, 2026Keegan Kang, Kerong Wang, Ding Zhang +3Maximum Likelihood Variance Reduction
Department of Mathematics and Statistics, Bucknell University, USA · School of Data Science, University of Virginia, USA · Department of CSE, IIT Hyderabad, India +2
Time-Varying Bayesian Optimization Without a Metronome
Jan 31, 2025Anthony Bardou, Patrick ThiranMulti-Objective Bayesian Optimization Algorithms Bayesian Optimization
IC EPFL Lausanne, Switzerland
Variance Reduction for Independent Metropolis
Jun 25, 2024Siran Liu, Petros Dellaportas, Michalis K. TitsiasVariance Reduction Variance
Department of Statistical Science, University College London, UK. · Department of Statistics, Athens University of Economics and Business, Greece. · Google DeepMind, UK.

Oct 1, 2026, math.OCJ/K move · Enter open · S save

Lower Bounds for Stochastic First-Order Algorithms with Variance Reduction in Nonconvex--Concave Minimax Optimization

Jiayi Song, Zi Xu

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Convex Optimization Lower Bounds Variance Reduction Stochastic Approximation Smoothness

Open paper AskPDF arXiv

We establish complexity lower bounds for stochastic first-order algorithms in nonconvex--concave minimax optimization, allowing algorithms to use variance reduction. Our main contribution is a lower bound for a zero-respecting algorithm class that permits variance reduction, extending beyond the algorithmic restrictions imposed by some existing lower bounds. We consider objectives with an

L

-Lipschitz continuous joint gradient, a compact convex dual domain of Euclidean radius at most

D_Y

, and a primal value function, defined by maximizing the objective over the dual variable, with initial suboptimality at most

Δ

. The target accuracy

\varepsilon

is measured by the gradient norm of the Moreau envelope of the constrained primal value function with parameter

1/(2L)

. Under an unbiased stochastic first-order oracle with variance at most

σ^2

and mean-square smoothness, we prove the lower bound

Ω\!\left(L^2D_YΔ\varepsilon^{-3}+L^3D_Y^2Δσ^2\varepsilon^{-6}\right)

. This result quantifies the dependence on accuracy, dual-domain radius, and oracle noise even when variance reduction is allowed. We also establish complementary lower bounds for nonconvex--strongly-concave minimax optimization. With dual strong-concavity parameter

μ>0

and condition number

κ:=L/μ

, we obtain

Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+LΔκσ^2\varepsilon^{-4}\right)

under the bounded-variance oracle model. Under the additional mean-square smoothness condition with constant

\bar L

, we obtain

Ω\!\left(LΔ\sqrtκ\,\varepsilon^{-2}+Δ\bar Lσκ^{3/2}\varepsilon^{-3}\right)

. Together, these results identify complexity barriers across the concave and strongly concave regimes, with the main nonconvex--concave bound remaining valid for algorithms that use variance reduction.

Momentum

Related topics

Latest papers 61