On-device research index

arXiv research

A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.

168,742 papers · 148 categories

Trend · papers per month

count % of corpus

48 results for “batch information lower bound”

The Conditional Regret-Capacity Theorem for Batch Universal Predictioncs.IT

The paper derives a new theorem for predicting batches of data.

problem Finding lower bounds on minimal batch regret.

method Derives a conditional version of the regret-capacity theorem.

result Reveals a connection between conditional Rényi divergence and conditional Sibson's mutual information.

regret-capacity theorem batch universal prediction Rényi information measures binary memoryless sources

2025-08-14abs ↗pdf ↗

The Batch Complexity of Bandit Pure Explorationcs.LG

The study analyzes batched methods for early stopping in stochastic multi-armed bandits.

problem Early stopping in stochastic multi-armed bandits with fixed confidence.

method Instance-dependent lower bounds and a general batched algorithm with upper bounds.

result Upper and lower bounds on the number of batches and sample complexity.

batched methods stochastic multi-armed bandits pure exploration lower bounds upper bounds

2025-02-03abs ↗pdf ↗

There and Back Again: Unraveling the Variational Auto-Encodercs.LG

VAEs can use constant posterior variances under certain conditions, simplifying model training.

problem Learning variances in VAEs is challenging and unnecessary under certain conditions.

method Proof of non-trivial solutions with constant posterior variances, simplified ELBO formulation, and new sampling method.

result ELBO can be simplified and optimized without learning variances, improving model performance.

variational auto-encoder ELBO posterior variance smoothness batch information lower bound

2019-12-21abs ↗pdf ↗

Gaussian Process Bandit Optimization with Few Batchesstat.ML

A batched Gaussian Process bandit optimization method achieves near-optimal regret bounds.

problem Black-box optimization with limited function evaluations.

method Batched Gaussian Process bandit optimization algorithm.

result Achieves near-optimal cumulative regret bound of

O^\ast(\sqrt{Tγ_T})

using

O(\log\log T)

batches.

Gaussian Process Bandit Optimization Cumulative Regret Batched Algorithms Kernel Methods

2021-10-15abs ↗pdf ↗

Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycs.LG

New research shows many batch selection methods for training work just as well as full batch training.

problem Finding optimal batch selection methods for training.

method Analysis of mini-batch Gradient Descent (GD) and Stochastic GD (SGD) with various batch selection rules.

result All mini-batch schedules, including deterministic ones, generalize optimally for smooth Lipschitz-convex/nonconvex/strongly-convex loss functions.

mini-batch GD stochastic GD batch selection generalization error convex optimization

2023-05-03abs ↗pdf ↗

Batched Kernelized Bandits: Refinements and Extensionsstat.ML

The paper refines and extends batched kernelized bandits, improving regret bounds and introducing a robust setting.

problem Optimizing black-box functions with noisy batches in Reproducing Kernel Hilbert Space.

method Refined and extended existing regret bounds, including adaptive batch sizes and robust optimization.

result Improved regret bounds for batched kernelized bandits, showing optimal number of batches and adaptive batch sizes.

batched kernelized bandits regret bounds adaptive batches robust optimization Reproducing Kernel Hilbert Space

2026-03-13abs ↗pdf ↗

Batched Stochastic Bandit for Nondegenerate Functionsstat.ML

GN algorithm solves batched bandit for nondegenerate functions near-optimally.

problem Batched bandit learning for nondegenerate functions.

method Introduces Geometric Narrowing (GN) algorithm with a

\widetilde{\mathcal{O}} ( A_{+}^d \sqrt{T} )

regret bound and

\mathcal{O} (\log \log T)

batches.

result GN achieves near optimal regret with minimal number of batches.

batched bandit nondegenerate functions Geometric Narrowing regret bound minimal batches

2024-05-09abs ↗pdf ↗

Sequential Batch Learning in Finite-Action Linear Contextual Banditscs.LG

Study batch learning in linear bandits with context, achieving near-optimal performance.

problem Sequential batch learning in linear contextual bandits with finite actions.

method Established regret bounds and provided algorithms for two settings: arbitrary contexts and i.i.d. contexts.

result Regret upper bound nearly matches lower bound, showing polynomial and logarithmic batch requirements.

Sequential Batch Learning Linear Contextual Bandits Regret Analysis Finite Action Sets Regret Lower Bounds

2020-04-14abs ↗pdf ↗

Distributionally Ambiguous Optimization Techniques for Batch Bayesian Optimizationstat.ML

We propose a novel, theoretically-grounded, acquisition function for Batch Bayesian optimization informed by insights from distributionally ambiguous optimization. Our acquisition function is a lower bound on the well-known Expected Improvement function, which requires evaluation of a Gaussian Expectation over a multiv…

2017-07-13abs ↗pdf ↗

Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Banditsstat.ML

Study dynamic batch learning in high-dimensional sparse linear bandits.

problem Dynamic batch learning in high-dimensional sparse linear contextual bandits under batch constraints.

method Characterized fundamental learning limits via regret lower bound and provided matching upper bound.

result Prescribed an optimal scheme for dynamic batch learning in high-dimensional sparse linear contextual bandits.

dynamic batch learning high-dimensional sparse linear bandits regret lower bound upper bound optimal scheme

2020-08-27abs ↗pdf ↗

Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycs.LG

Paper establishes lower bounds and optimal algorithms for deployment-efficient RL.

problem Deployment efficiency in reinforcement learning.

method Optimization with constraints, lower bounds, algorithms.

result Established optimal algorithms for deployment-efficient RL.

reinforcement learning deployment efficiency information theory lower bounds optimization

2022-02-14abs ↗pdf ↗

Efficient List-Decodable Regression using Batchescs.LG

Polynomial-time algorithm for list-decodable linear regression with batches.

problem Efficiently decoding linear regression with a fraction of adversarial data.

method Polynomial time algorithm using batches of i.i.d. samples.

result Returns a list of size O(1/α^2) with one item close to true parameter.

list-decodable regression batches polynomial time adversarial data i.i.d. samples

2022-11-23abs ↗pdf ↗

Active clustering with bandit feedbackstat.ML

New algorithm reduces clustering cost in bandit feedback.

problem Discovering hidden groupings in stochastic bandit feedback.

method ACB algorithm for active clustering with non-asymptotic lower bound.

result ACB algorithm's budget matches lower bound in most regimes.

active clustering stochastic bandit non-asymptotic lower bound computation-information gap

2024-06-17abs ↗pdf ↗

Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcs.LG

Sparse feature selection improves batch RL efficiency.

problem High-dimensional batch RL with many features.

method Sparse linear function approximation, Lasso, group Lasso, fitted Q-evaluation, fitted Q-iteration.

result Sparse feature selection makes batch RL more sample efficient.

batch reinforcement learning sparse feature selection sample efficiency finite-sample error bound post model selection estimator

2020-11-08abs ↗pdf ↗

Adversarial Combinatorial Bandits with Switching Costsstat.ML

New algorithms tackle adversarial combinatorial bandits with switching costs.

problem Adversarial combinatorial bandits with switching costs.

method Design algorithms operating in batches to restrict switches, proving lower bounds and achieving upper bounds on regret.

result Achieved upper bounds on regret for both bandit and semi-bandit feedback settings.

Adversarial bandits Switching costs Regret bounds Batched algorithms

2024-04-02abs ↗pdf ↗

Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Banditscs.LG

New constraints on space and adaptivity in bandits force more batches and memory use.

problem Simultaneous space and adaptivity constraints in stochastic bandits.

method Proved lower bounds and constructed an algorithm with near-minimax regret.

result Near-minimax regret requires more batches and memory than previously thought.

stochastic bandits space constraints adaptivity constraints near-minimax regret information bottleneck

2026-03-14abs ↗pdf ↗

The Sample Complexity of Multicalibrationcs.LG

Study shows sample complexity for multicalibration is Θ(ε^-3) with polylogarithmic factors.

problem Minimizing Expected Calibration Error (ECE) for predictors with respect to a family of groups.

method Proved necessary and sufficient sample complexity of Θ(ε^-3) for multicalibration, using online-to-batch reduction and lower bounds.

result Sample complexity of multicalibration is Θ(ε^-3) with polylogarithmic factors, distinguishing it from marginal calibration.

Sample Complexity Multicalibration Expected Calibration Error Online-to-Batch Reduction Lower Bounds

2026-04-23abs ↗pdf ↗

DARTS: Targeting Prognostic Covariates in Budget-Constrained Sequential Experimentsstat.ML

DARTS optimizes covariate selection in trials with limited data.

problem Limited budget for high-dimensional pretreatment data.

method Dynamic Adaptive Rerandomization via Thompson Sampling (DARTS).

result DARTS efficiently concentrates budget on informative features.

covariate selection sequential optimization Thompson sampling causal inference budget-constrained

2026-05-07abs ↗pdf ↗

Batched Dueling Banditscs.LG

New algorithms for batched dueling bandits with improved regret bounds.

problem Batched dueling bandits with noisy pairwise comparisons.

method Developed algorithms for two settings: Condorcet winner and strong stochastic transitivity.

result Regret bounds match sequential bounds using only a logarithmic number of batches.

dueling bandits batched regret Condorcet winner stochastic transitivity

2022-02-22abs ↗pdf ↗

Low-Precision Streaming PCAcs.LG

Low-precision streaming PCA estimates the leading eigenvector with limited precision.

problem Estimating the leading eigenvector in a streaming setting with limited precision.

method Oja's algorithm with linear and nonlinear stochastic quantization.

result A batched version of the quantized variants achieves the lower bound on quantization error up to logarithmic factors.

streaming PCA low precision quantization eigenvector estimation Oja's algorithm

2025-10-25abs ↗pdf ↗

GIBBON: General-purpose Information-Based Bayesian OptimisatioNcs.LG

GIBBON unifies Bayesian optimization for various problem types.

problem Bayesian optimization across noisy, multi-fidelity, and batch optimisations.

method Novel approximation of information gain for a single framework.

result Significantly lower computational overhead compared to existing approaches.

Bayesian optimization max-value entropy search information gain batch optimization noisy optimization

2021-02-05abs ↗pdf ↗

The Impact of Batch Learning in Stochastic Banditscs.LG

We analyze how batch learning impacts bandit problems.

problem Impact of batch learning in stochastic bandits.

method Policy-agnostic regret analysis, upper and lower bounds demonstration.

result The impact of batch learning can be measured in terms of online behavior.

batched bandits regret analysis stochastic bandits batch learning

2021-11-03abs ↗pdf ↗

Batched Stochastic Linear Bandits with 1-Bit Communication Constraintsstat.ML

New algorithm tackles batched stochastic linear bandits with 1-bit communication constraints.

problem Stochastic linear bandits with 1-bit communication constraints.

method Phased-elimination algorithms based on G-optimal designs and 1-bit mean estimation.

result Achieves near-optimal regret bounds for broad scaling regimes.

stochastic linear bandits batched 1-bit communication minimax regret G-optimal designs

2026-05-29abs ↗pdf ↗

Batched Multi-armed Bandits Problemstat.ML

In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the re…

2019-04-03abs ↗pdf ↗

Mini-batch Estimation for Deep Cox Models: Statistical Foundations and Practical Guidancestat.ML

New statistical properties for mini-batch Cox-NN optimization.

problem Optimizing deep Cox neural networks using mini-batches.

method Developed mini-batch maximum partial-likelihood estimator (mb-MPLE) for Cox-NN.

result mb-MPLE is consistent and achieves optimal convergence rate.

Cox-NN mini-batch stochastic gradient descent partial-likelihood statistical properties

2024-08-05abs ↗pdf ↗

Batched Nonparametric Contextual Banditsmath.ST

Study nonparametric contextual bandits with batched updates, achieving optimal regret.

problem Optimal regret in nonparametric contextual bandits with batch constraints.

method Dynamic binning of covariate space, optimal regret achieved.

result Achieves optimal regret (up to logarithmic factors) for nonparametric contextual bandits.

contextual bandits nonparametric batched updates optimal regret

2024-02-27abs ↗pdf ↗

Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Boundscs.LG

We design a new algorithm for batch active learning with deep neural network models. Our algorithm, Batch Active learning by Diverse Gradient Embeddings (BADGE), samples groups of points that are disparate and high-magnitude when represented in a hallucinated gradient space, a strategy designed to incorporate both pred…

2019-06-09abs ↗pdf ↗

Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspectivestat.ML

Study mini-batch SGD noise and its limits, proving complexity guarantees.

problem Analyzing the noise in mini-batch SGD and its impact on optimization.

method Examined the conditional covariance and diffusion limits of SGD under different sampling designs.

result Proved mean-square upper bounds and Fisher van Trees lower bounds for SGD, linking them to effective dimension and condition number.

stochastic gradient descent mini-batch sampling design oracle complexity functional CLT

2026-03-02abs ↗pdf ↗

Uncertainty Estimation via Stochastic Batch Normalizationstat.ML

In this work, we investigate Batch Normalization technique and propose its probabilistic interpretation. We propose a probabilistic model and show that Batch Normalization maximazes the lower bound of its marginalized log-likelihood. Then, according to the new probabilistic model, we design an algorithm which acts cons…

2018-02-13abs ↗pdf ↗

On Batch Normalisation for Approximate Bayesian Inferencecs.LG

Batch normalisation doesn't affect variational inference but fails for larger batch sizes.

problem Failure of Monte Carlo Batch Normalisation (MCBN) for capturing epistemic uncertainty in larger batch sizes.

method Investigated MCBN as an approximate inference technique for Bayesian neural networks, showing its limitations and providing insights for improvement.

result For larger batch sizes, MCBN fails to capture epistemic uncertainty, requiring the batch size to be a variational parameter.

batch normalisation variational inference Bayesian neural networks epistemic uncertainty MC Dropout

2020-12-24abs ↗pdf ↗

Optimal Batched Linear Banditscs.LG

E $^4$ algorithm optimizes batched linear bandits with minimal regret and batches.

problem Optimizing batched linear bandits for minimal regret.

method Explore-Estimate-Eliminate-Exploit framework with optimal exploration rate.

result Achieves minimax and asymptotic optimality in regret and batch complexity.

batched linear bandits Explore-Estimate-Eliminate-Exploit minimax optimality asymptotic optimality regret minimization

2024-06-06abs ↗pdf ↗

Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regressioncs.LG

Batching stabilizes risk in high-dimensional linear regression models.

problem Stability and risk behavior in high-dimensional overparameterized linear regression.

method Minimum-norm overparameterized linear regression model with batch-partitioning.

result Optimal batch size is inversely proportional to noise level and overparametrization ratio, leading to stable risk behavior.

batch-partitioning overparameterized linear regression minimum-norm risk stability

2023-06-14abs ↗pdf ↗

Empirical study towards understanding line search approximations for training neural networksstat.ML

Choosing appropriate step sizes is critical for reducing the computational cost of training large-scale neural network models. Mini-batch sub-sampling (MBSS) is often employed for computational tractability. However, MBSS introduces a sampling error, that can manifest as a bias or variance in a line search. This is bec…

2019-09-15abs ↗pdf ↗

Cost-Sensitive Approach to Batch Size Adaptation for Gradient Descentcs.LG

In this paper, we propose a novel approach to automatically determine the batch size in stochastic gradient descent methods. The choice of the batch size induces a trade-off between the accuracy of the gradient estimate and the cost in terms of samples of each update. We propose to determine the batch size by optimizin…

2017-12-09abs ↗pdf ↗

Robust Estimation of Discrete Distributions under Local Differential Privacymath.ST

New method estimates discrete distributions while protecting privacy.

problem Estimating discrete distributions with local differential privacy.

method Combining robust learning and local differential privacy.

result Minimax estimation rate of

ε\sqrt{d/α^2 k}+\sqrt{d^2/α^2 kn}

under privacy constraint.

Privacy Estimation Differential Privacy Discrete Distributions Robust Learning

2022-02-14abs ↗pdf ↗

Reinforcement Learning with Multi-Step Lookahead Information Via Adaptive Batchingcs.LG

New algorithm learns optimal policy with multi-step lookahead information.

problem Learning optimal policy in reinforcement learning with multi-step lookahead information is NP-hard.

method Adaptive batching policies that process lookahead in state-dependent chunks.

result Order-optimal regret bounds up to a constant factor of lookahead horizon.

Reinforcement Learning Multi-step Lookahead Adaptive Batching Optimal Policy Regret Minimization

2026-01-15abs ↗pdf ↗

An Internal Covariate Shift Bounding Algorithm for Deep Neural Networks by Unitizing Layers' Outputscs.LG

This paper analyzes and improves the effectiveness of BN techniques in controlling Internal Covariate Shift.

problem The effectiveness of BN techniques in reducing Internal Covariate Shift (ICS) is limited, especially for high-dimensional outputs and noise.

method The paper introduces a measure for ICS using the Earth Mover (EM) distance, derives bounds for this measure, and proposes a unitization algorithm to further bound ICS.

result The unitization algorithm effectively bounds ICS, especially for low-dimensional outputs and small noise, and can be tuned to control ICS.

Internal Covariate Shift Batch Normalization Earth Mover Distance Deep Neural Networks Unitization Algorithm

2020-01-09abs ↗pdf ↗

Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescs.LG

DPP-BBO diversifies batched Bayesian optimization using DPPs.

problem Efficiently proposing diverse and informative batches in batched Bayesian optimization.

method Introducing DPP-Batch Bayesian Optimization (DPP-BBO) with DPP-Thompson Sampling (DPP-TS).

result Novel Bayesian simple regret bounds for DPP-TS show improved performance over classical methods.

Bayesian Optimization DPP Thompson Sampling Batched Optimization Determinantal Point Processes

2021-10-22abs ↗pdf ↗

Information-Theoretic Bayes Risk Lower Bounds for Realizable Modelscs.LG

Lower bounds on Bayes risk for realizable models derived using information theory.

problem Deriving lower bounds on Bayes risk for realizable machine learning models.

method Information-theoretic analysis using rate-distortion theory and mutual information.

result Lower bounds on Bayes risk for realizable models, matching known bounds up to logarithmic factors.

Bayes risk information theory rate-distortion mutual information realizable models

2021-11-08abs ↗pdf ↗

Distributed Contextual Linear Bandits with Minimax Optimal Communication Costcs.LG

A distributed algorithm reduces communication cost in linear bandits to near-optimal levels.

problem Cooperative linear bandit optimization with stochastic contexts.

method DisBE-LUCB algorithm, DecBE-LUCB algorithm, sharing information through a central server or immediate neighbors.

result Communication cost of DisBE-LUCB matches information-theoretic lower bound up to logarithmic factors.

distributed optimization linear bandits contextual bandits minimax optimality communication cost

2022-05-26abs ↗pdf ↗

Optimal

δ

-Correct Best-Arm Selection for Heavy-Tailed Distributionscs.LG

Given a finite set of unknown distributions or arms that can be sampled, we consider the problem of identifying the one with the maximum mean using a $δ$ -correct algorithm (an adaptive, sequential algorithm that restricts the probability of error to a specified $δ$ ) that has minimum sample complexity. Lower bounds for …

2019-08-24abs ↗pdf ↗

Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscs.LG

Efficient RL algorithms for linear function approximation with limited adaptivity constraints.

problem Limited adaptivity in reinforcement learning with linear function approximation.

method Proposed two efficient online RL algorithms for episodic linear Markov decision processes under batch learning and rare policy switch models.

result Achieved efficient regret bounds for both batch learning and rare policy switch models, with substantial reduction in adaptivity.

reinforcement learning linear function approximation adaptivity constraints batch learning rare policy switch

2021-01-06abs ↗pdf ↗

Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problemcs.LG

We consider the combinatorial multi-armed bandit (CMAB) problem, where the reward function is nonlinear. In this setting, the agent chooses a batch of arms on each round and receives feedback from each arm of the batch. The reward that the agent aims to maximize is a function of the selected arms and their expectations…

2019-05-08abs ↗pdf ↗

Parallelizing Thompson Samplingcs.LG

Batch Thompson Sampling reduces exploration-exploitation trade-off in online decision making.

problem Balancing exploration and exploitation in online decision making.

method Introducing a batch Thompson Sampling framework for stochastic multi-arm bandit and linear contextual bandit problems.

result Achieves asymptotic regret bound with

O(\log T)

batch queries, significantly reducing interactions.

Thompson Sampling Online Decision Making Bandit Problems Exploration-Exploitation Exponential Reduction

2021-06-02abs ↗pdf ↗

Information Theoretic Lower Bounds for Feed-Forward Fully-Connected Deep Networksstat.ML

The paper sets information-theoretic lower bounds for neural networks' parameter recovery and excess risk.

problem Establishing sample complexity lower bounds for neural network parameters and excess risk.

method Using information-theoretic tools, the paper proves lower bounds by constructing a generative network.

result Proves information-theoretic lower bounds for exact parameter recovery and positive excess risk.

information theory neural networks sample complexity lower bounds binary classification

2020-07-01abs ↗pdf ↗

Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Datacs.LG

New streaming methods improve convergence rates for optimization problems.

problem Optimizing large-scale, sequential data problems.

method Time-varying mini-batches and Polyak-Ruppert averaging for gradient-based algorithms.

result Time-varying mini-batches and averaging achieve optimal convergence and variance reduction.

streaming data stochastic approximation gradient descent mini-batches convergence rates

2021-09-15abs ↗pdf ↗

A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcs.LG

New RL difficulty shown for discounted settings.

problem Difficulty in reinforcement learning with discounted rewards.

method Adapted Wang et al. (2020) construction to 2-state MDP.

result Learning impossible even with infinite data in discounted setting.

reinforcement learning discounted rewards batch RL MDP

2020-11-02abs ↗pdf ↗

Fisher information lower bounds for samplingstat.ML

The paper sets lower bounds for sampling non-log-concave distributions using Fisher information.

problem Understanding the complexity of sampling non-log-concave distributions.

method Proves two lower bounds using Fisher information in the context of sampling.

result Lower bounds on the complexity of sampling non-log-concave distributions, ruling out high-accuracy algorithms.

Fisher information sampling non-log-concave lower bounds approximate stationarity

2022-10-05abs ↗pdf ↗