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.
Recurrent Neural Networks (RNNs) are powerful models for sequential data that have the potential to learn long-term dependencies. However, they are computationally expensive to train and difficult to parallelize. Recent work has shown that normalizing intermediate representations of neural networks can significantly im…
Estimates stationary distribution from batch transitions without access to the underlying process.
problem Estimating stationary distribution from batch transitions without access to the underlying process.
method Proposes a consistent estimator based on a correction ratio function and variational power method (VPM).
result VPM provides significantly better estimates across various problems.
Improved robustness in optimization methods using second-order information.
problem Scalability and sensitivity to mini-batch size in optimization methods.
method Mini-Batch Stochastic Variance-Reduced Newton (extttMb−SVRN) algorithm incorporating partial second-order information. result Achieves a fast linear convergence rate independent of mini-batch size for large data sizes.
In statistical learning for real-world large-scale data problems, one must often resort to "streaming" algorithms which operate sequentially on small batches of data. In this work, we present an analysis of the information-theoretic limits of mini-batch inference in the context of generalized linear models and low-rank…
We introduce a novel apprenticeship learning algorithm to learn an expert's underlying reward structure in off-policy model-free \emph{batch} settings. Unlike existing methods that require a dynamics model or additional data acquisition for on-policy evaluation, our algorithm requires only the batch data of observed ex…
This paper unifies three regularization methods in batch reinforcement learning.
problem Learning overly-complex models in batch reinforcement learning.
method Unified weighted average transition matrix framework for three regularization methods.
result Empirical evaluation confirms intuitions about regularization methods' performance.
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.
Mini-batch SGD with momentum is a fundamental algorithm for learning large predictive models. In this paper we develop a new analytic framework to analyze noise-averaged properties of mini-batch SGD for linear models at constant learning rates, momenta and sizes of batches. Our key idea is to consider the dynamics of t…
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.
A new algorithm learns policies from batch data in hierarchical RL.
problem Learning policies from fixed batches of data without full exploration.
method Modeling RL as a two-player game with a leader-follower structure, proposing StackelbergLearner.
result StackelbergLearner achieves competitive performance in batch RL and real-world datasets.
We tackle the Multi-task Batch Reinforcement Learning problem. Given multiple datasets collected from different tasks, we train a multi-task policy to perform well in unseen tasks sampled from the same distribution. The task identities of the unseen tasks are not provided. To perform well, the policy must infer the tas…
New batched Langevin Thompson Sampling reduces communication costs for sequential decision making.
problem Efficiently learning unknown reward distributions and transition dynamics in batched settings.
method Langevin Thompson Sampling with logarithmic communication costs.
result Order-optimal regret guarantees for stochastic MABs and RL.
The existence of a phase transition with diverging susceptibility in batch Minority Games (MGs) is the mark of informationally efficient regimes and is linked to the specifics of the agents' learning rules. Here we study how the standard scenario is affected in a mixed population game in which agents with the `optimal'…
Traditional model-based reinforcement learning approaches learn a model of the environment dynamics without explicitly considering how it will be used by the agent. In the presence of misspecified model classes, this can lead to poor estimates, as some relevant available information is ignored. In this paper, we introd…
Learning with noisy labels, which aims to reduce expensive labors on accurate annotations, has become imperative in the Big Data era. Previous noise transition based method has achieved promising results and presented a theoretical guarantee on performance in the case of class-conditional noise. However, this type of a…
Study uses Bayesian Optimization to analyze noise effects in materials research.
problem Optimizing materials with many variables and experimental noise.
method Batch Bayesian Optimization with synthetic data analysis.
result Noise sensitivity varies by problem landscape, impacting optimization outcomes.
New analysis of Muon and SignSGD on matrix-valued least squares problems.
problem Understanding the behavior of Muon and SignSGD on matrix-valued least squares problems.
method Derive explicit deterministic dynamics to study learning behavior of Muon and SignSGD.
result Muon and SignSGD exhibit different optimal learning rates and convergence characteristics based on batch size and data covariance.
A new method for learning policies from demonstrations without reinforcement.
problem Learning policies from demonstrations without access to reinforcement signals.
method Energy-based distribution matching (EDM) to learn policy parameters and state marginals.
result EDM yields consistent performance gains over existing algorithms for strictly batch imitation learning.
New learning rate approach reveals phase transitions in SGD performance.
problem Understanding feature learning dynamics in neural networks.
method Characterizing the relationship between learning rate(s) and sample complexity for gradient-based algorithms.
result Phase transition from information exponent to generative exponent regime with different learning rates.
We study the dynamics of the batch minority game, with random external information, using generating functional techniques a la De Dominicis. The relevant control parameter in this model is the ratio α=p/N of the number p of possible values for the external information over the number N of trading agents. In the …
We study the dynamics of a version of the batch minority game, with random external information and with different types of inhomogeneous decision noise (additive and multiplicative), using generating functional techniques à la De Dominicis. The control parameters in this model are the ratio α=p/N of the number p o…
We present a novel spectral learning algorithm for simultaneous localization and mapping (SLAM) from range data with known correspondences. This algorithm is an instance of a general spectral system identification framework, from which it inherits several desirable properties, including statistical consistency and no l…
Theoretical study explains grokking in neural networks.
problem Understanding the abrupt transition from fitting to generalizing in neural networks.
method Characterized a shell-core topological configuration of the solution space induced by Adam's optimization dynamics.
result Derived grokking scaling laws for learning rate, batch size, and regularization coefficient.
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.
Determining the appropriate batch size for mini-batch gradient descent is always time consuming as it often relies on grid search. This paper considers a resizable mini-batch gradient descent (RMGD) algorithm based on a multi-armed bandit for achieving best performance in grid search by selecting an appropriate batch s…
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.
Flow Matching for count data improves sample quality and efficiency.
problem Mapping between count distributions across batches or time points in high-dimensional count data.
method count-FM, a flow-matching framework based on a continuous-time birth-death process with local unit jumps.
result count-FM achieves better sample quality than representative baselines while using fewer parameters.
BatchGFN uses generative flow networks for efficient batch active learning.
problem Efficiently selecting informative batches for active learning.
method Generative flow networks to sample batches proportional to a batch reward.
result Constructs highly informative batches with a single forward pass per point.
Adaptive batch sizes improve active learning efficiency and flexibility.
problem Fixed batch sizes in active learning are inefficient due to dynamic cost-speed trade-offs.
method Probabilistic Numerics framework that adaptively changes batch sizes based on integration error and precision objectives.
result Significant enhancement in learning efficiency and flexibility across various applications.
CBN improves batch normalization for small mini-batch sizes.
problem Reduced effectiveness of Batch Normalization in small mini-batch sizes.
method CBN uses statistics from multiple recent iterations, compensating for network weight changes via Taylor polynomials.
result CBN outperforms original batch normalization and direct iteration statistics in object detection and image classification.
Opt-BBAI identifies the best arm with minimal batches and pulls, optimizing both sample and batch complexity.
problem Batched best arm identification (BBAI) problem, aiming to minimize policy switches and resource usage.
method Proposed Opt-BBAI algorithm, achieving near-optimal sample and batch complexity in non-asymptotic settings.
result First algorithm to achieve near-optimal sample and batch complexity in non-asymptotic settings.
Batch Normalization (BN) uses mini-batch statistics to normalize the activations during training, introducing dependence between mini-batch elements. This dependency can hurt the performance if the mini-batch size is too small, or if the elements are correlated. Several alternatives, such as Batch Renormalization and G…
A new method designs batches for Bayesian optimization more efficiently.
problem Efficiently designing batches for Bayesian optimization to reduce total time.
method Minimal Terminal Variance (MTV) acquisition function, optimizing I-optimality criterion.
result MTV designs batches more efficiently than other methods, as shown by numerical experiments.
Training deep neural networks with Stochastic Gradient Descent, or its variants, requires careful choice of both learning rate and batch size. While smaller batch sizes generally converge in fewer training epochs, larger batch sizes offer more parallelism and hence better computational efficiency. We have developed a n…
Riemannian stochastic gradient descent converges faster with increasing batch size.
problem Improving convergence rate of Riemannian stochastic gradient descent.
method Theoretical analysis and numerical investigation of increasing batch size effects.
result Riemannian stochastic gradient descent converges faster with increasing batch size.
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.
New findings show mini-batch SGD operates in a 'Edge of Stochastic Stability' regime.
problem Understanding the stability and convergence of mini-batch SGD.
method Analyzing the mini-batch Hessian and its directional curvature.
result Mini-batch SGD operates in a different stability regime (Edge of Stochastic Stability) compared to full-batch GD.
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.
A new scaling law predicts optimal batch size for training models.
problem Finding the optimal batch size for training models efficiently.
method Proposed a three-term scaling law that considers model size, training data, training steps, and batch size.
result The three-term law accurately recovers the optimal batch size and can be robustly fit with fewer training runs.
E4 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.
ABS dynamically adjusts batch size based on policy stability, improving RL performance.
problem Diminishing returns with large batch sizes in RL due to non-stationary data.
method Adaptive Batch Scaling (ABS) with Behavioral Divergence metric.
result Larger batch sizes can improve RL performance, contrary to conventional wisdom.
SNGM improves large-batch training accuracy.
problem Improving generalization in large-batch training.
method Stochastic Normalized Gradient Descent with Momentum.
result SNGM achieves better test accuracy than MSGD and other large-batch methods.
Maximizes Rényi entropy for efficient exploration in reward-free RL.
problem Challenges of exploration in reward-free reinforcement learning.
method Maximizes Rényi entropy over state-action space in exploration phase; uses batch RL for planning phase.
result Effective and sample-efficient exploration leading to superior policies.
Batched Neural Bandits reduces policy updates in sequential decision-making.
problem Sequential decision-making with batched policy changes.
method BatchNeuralUCB algorithm combining neural networks and optimism.
result Achieves similar regret as fully sequential version with fewer policy updates.
Large batch sizes reduce gradient variance in DP-SGD, improving privacy.
problem Understanding why large batch sizes work in DP-SGD.
method Decomposed total gradient variance into subsampling and noise-induced variances, proving batch size independence in the limit.
result Large batch sizes reduce effective total gradient variance, improving privacy in DP-SGD.
Large-batch SGD is important for scaling training of deep neural networks. However, without fine-tuning hyperparameter schedules, the generalization of the model may be hampered. We propose to use batch augmentation: replicating instances of samples within the same batch with different data augmentations. Batch augment…
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.