The paper studies batch decompositions of random datasets with probabilistic similarity constraints.
problem Understanding how to optimally split large datasets into batches for better model learning.
method Assumes independent data points from a space, defines similarity, and uses probabilistic and martingale methods to find bounds on batch sizes.
result Demonstrates an inherent tradeoff between relaxing similarity constraints and batch size, and provides bounds for maximum similarity subsets.
Unified framework for solving linear systems with improved convergence rates.
problem Efficiently solving linear systems with randomized batch-sampling methods.
method Developed a unified randomized batch-sampling Kaczmarz framework with concentration inequalities for analysis.
result Derived new expected linear convergence rate bounds that are tighter and more reflective of empirical behavior.
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.
Ensembles of randomized decision trees, usually referred to as random forests, are widely used for classification and regression tasks in machine learning and statistics. Random forests achieve competitive predictive performance and are computationally efficient to train and test, making them excellent candidates for r…
Study shows how mini-batch GD with random reshuffling affects least squares regression dynamics.
problem Analyzing the error dynamics of mini-batch GD with random reshuffling for least squares regression.
method Represented training and generalization errors through a sample cross-covariance matrix Z, compared with sample covariance matrix of original features X, and used linear scaling rule for analysis.
result Mini-batch GD with random reshuffling exhibits subtle step-size dependence not detectable by gradient flow analysis, converging to a limit dependent on the step size.
In this paper we study a family of variance reduction methods with randomized batch size---at each step, the algorithm first randomly chooses the batch size and then selects a batch of samples to conduct a variance-reduced stochastic update. We give the linear convergence rate for this framework for composite functions…
New insights into learning rates and batch sizes for neural networks using random matrix theory.
problem Understanding how batch size affects learning rates in neural networks.
method Random matrix theory applied to spiked, field-dependent random matrices.
result Analytical expressions for maximal learning rates as a function of batch size.
Proposes reducing random error in stochastic optimization by variance regularization.
problem Random error accumulation in stochastic optimization algorithms.
method Regularizes learning-rate based on mini-batch variances.
result Speeds up convergence and stabilizes stochastic optimization.
iMondrian forest combines isolation forest and Mondrian forest for better anomaly detection.
problem Anomaly detection in batch and online settings.
method Hybrid of isolation forest and Mondrian forest, using depth in Mondrian forest structure.
result iMondrian forest outperforms existing methods in batch and online settings.
New hyperparameter ensembles boost neural network performance and uncertainty.
problem Improving neural network robustness and uncertainty quantification.
method Designing ensembles over both weights and hyperparameters, stratified across random initializations.
result Hyper-deep and hyper-batch ensembles outperform deep and batch ensembles on various architectures.
In this work we investigate the reasons why Batch Normalization (BN) improves the generalization performance of deep networks. We argue that one major reason, distinguishing it from data-independent normalization methods, is randomness of batch statistics. This randomness appears in the parameters rather than in activa…
Partition functions arise in a variety of settings, including conditional random fields, logistic regression, and latent gaussian models. In this paper, we consider semistochastic quadratic bound (SQB) methods for maximum likelihood inference based on partition function optimization. Batch methods based on the quadrati…
A new method for efficient sampling from probability measures.
problem Efficiently sampling from complex probability distributions.
method RBM-SVGD, a stochastic version of SVGD using Random Batch Method.
result Reduces computational cost, especially for long-range kernels.
Batch normalization prevents rank collapse in deep networks, improving training stability.
problem Rank collapse in randomly initialized deep networks with increasing depth.
method Investigates spectral instabilities in random matrices and uses batch normalization to avoid rank collapse.
result Batch normalization prevents rank collapse in both linear and ReLU networks, improving training stability.
The paper parallelizes MCMC using random forests for big data Bayesian computation.
problem Efficiently computing Bayesian models in large datasets.
method Embed random forests into divide-and-conquer MCMC framework, using scaled subposteriors as proposal distributions.
result The approach works well across various model types, including misspecified models.
Extends batch active learning to non-differentiable models.
problem Efficiently training machine learning models on large, initially unlabelled datasets.
method Black-box batch active learning for regression tasks that relies solely on model predictions.
result Achieves strong performance on regression datasets compared to white-box approaches for deep learning models.
Sources of variability in experimentally derived data include measurement error in addition to the physical phenomena of interest. This measurement error is a combination of systematic components, originating from the measuring instrument, and random measurement errors. Several novel biological technologies, such as ma…
A new method for graph neural networks speeds up inference and training.
problem Challenges in constructing mini-batches for large graphs in graph neural networks.
method Theoretical model of batch construction via maximizing influence score of nodes on outputs.
result Accelerates inference by up to 130x compared to previous methods.
Batch normalization makes deep neural networks' representations increasingly orthogonal.
problem Orthogonality of deep neural network representations.
method Random linear transformations in successive batch-normalizations.
result Orthogonality of representations improves SGD performance.
SGD batch size affects autoencoder global minima sparsity and sharpness.
problem Investigating how batch size impacts autoencoder learning.
method Non-convex autoencoder training with SGD, varying batch sizes.
result SGD batch size influences global minimum sparsity and sharpness.
Sketching and stochastic gradient methods are arguably the most common techniques to derive efficient large scale learning algorithms. In this paper, we investigate their application in the context of nonparametric statistical learning. More precisely, we study the estimator defined by stochastic gradient with mini bat…
Bayesian batch active learning approximates model parameters efficiently.
problem High label acquisition cost for large-scale supervised models.
method Sparse subset approximation using Bayesian active learning.
result Efficient active learning at scale with diverse batches.
New sparsity operator reduces variance reduction methods' computational cost.
problem Reduce computational cost of variance reduction methods.
method Introduce random-top-k operator to estimate gradient sparsity and reduce operations per update.
result Our algorithm consistently outperforms SpiderBoost in various tasks.
Batch normalization in the last layer reduces sharpness in wide neural networks.
problem Pathological sharpness in wide neural networks.
method Quantifying the geometry of the parameter space using Fisher information matrix and analyzing deep neural networks with random initialization.
result Batch normalization in the last layer significantly decreases pathological sharpness under specific conditions.
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.
Background: Deep learning models are typically trained using stochastic gradient descent or one of its variants. These methods update the weights using their gradient, estimated from a small fraction of the training data. It has been observed that when using large batch sizes there is a persistent degradation in genera…
New SGDA method speeds up nonconvex minimax optimization.
problem Improving convergence of nonconvex minimax optimization.
method SGDA with random reshuffling for nonconvex-PŁ objectives.
result Convergence rates faster than with-replacement SGDA.
New SARAH variant MB-SARAH-RBB accelerates mini-batch optimization.
problem Improving the performance of SARAH in mini-batch settings.
method Introduced MB-SARAH-RBB, a variant of SARAH using RBB step size calculation.
result MB-SARAH-RBB converges linearly for strongly convex objectives and outperforms existing methods.
A new inference method using regression and batched discrepancies.
problem Simulating parameters from simulator outputs.
method Regression-based projection and batched discrepancy weighting.
result Method produces a self-normalized pseudo-posterior.
Unified approach for first-order methods with Markovian noise in stochastic optimization and variational inequalities.
problem Stochastic optimization problems with Markovian noise.
method Unified theoretical analysis of first-order gradient methods using randomized batching and multilevel Monte Carlo.
result Optimal (linear) dependence on the mixing time of the noise sequence, eliminating previous limiting assumptions.
New method reduces variance in complex probabilistic model optimization.
problem High variance in stochastic optimisation of complex models.
method Use recognition network to approximate optimal control variate for each mini-batch.
result Sub-optimal variance reduction is improved with new approach.
GNC smooths loss function for large-batch SGD, improving generalization.
problem Extremely large-batch SGD leads to poor generalization and converges to sharp minima.
method Gradient noise convolution (GNC) smooths loss function by convolving gradient noise with the loss function.
result GNC achieves state-of-the-art generalization performance for large-scale deep neural networks.
We introduce the Mondrian kernel, a fast random feature approximation to the Laplace kernel. It is suitable for both batch and online learning, and admits a fast kernel-width-selection procedure as the random features can be re-used efficiently for all kernel widths. The features are constructed by sampling trees via a…
Meta-algorithm for efficient reinforcement learning from human preferences.
problem Learning from human preference comparisons in Markov decision processes.
method Randomized exploration and experimental design for batch comparison queries.
result Meta-algorithm achieves both regret and last-iterate guarantees with minimal preference queries.
New algorithm learns from distributed, heterogeneous data without shuffling.
problem Efficiently learning from distributed, heterogeneous data in exascale simulations.
method Block-random gradient descent algorithm for distributed, heterogeneous data.
result Algorithm enables in situ learning without pre-shuffling data.
New study shows non-adaptive trials can be outperformed by adaptive designs in treatment selection.
problem Determining the best allocation of resources in clinical trials.
method Analysis of batched arm elimination designs and comparison with completely randomized trials.
result Simple adaptive designs universally and strictly dominate non-adaptive completely randomized trials for at least three treatment arms.
Batch normalization improves deep networks by aligning their decision boundaries with data.
problem Improving the performance and generalization of deep networks.
method Theoretical analysis of batch normalization as a function approximation technique for continuous piecewise affine splines.
result Batch normalization adapts the geometry of a deep network's partition to match the data, improving learning and generalization.
Deep Neural Networks (DNNs) thrive in recent years in which Batch Normalization (BN) plays an indispensable role. However, it has been observed that BN is costly due to the reduction operations. In this paper, we propose alleviating this problem through sampling only a small fraction of data for normalization at each i…
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.
New method for constructing confidence intervals for time series data.
problem Constructing confidence intervals for statistical functionals from time series data.
method Proposes a general purpose confidence interval procedure based on overlapping batches of time series data.
result Large overlapping batches yield confidence intervals of higher quality than generic methods.
BN helps learn fragile features, which can improve adversarial robustness.
problem The role of batch normalization in adversarial training and its impact on robustness.
method Investigated the expressiveness of BN in learning robust features compared to random features.
result Adversarially fine-tuning BN layers can result in non-trivial adversarial robustness.
This paper introduces sample-averaged Q-learning for better RL performance.
problem Improving reinforcement learning algorithms by managing uncertainty.
method Integrates statistical inference into Q-learning through sample averaging and functional central limit theorem.
result Establishes a unified theoretical foundation for sample-averaged Q-learning.
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.
This work analyzes how curriculum learning improves deep network training.
problem Training deep networks with non-uniform sampling of mini-batches.
method Two methods to address curriculum learning: transfer learning and bootstrapping. Different pacing functions to guide mini-batch sampling.
result Curriculum learning leads to faster learning and better final performance.
The study analyzes how stochastic recursive algorithms converge to Markov chains.
problem Understanding convergence of stochastic recursive algorithms to Markov chains.
method Analyzes iterated random operators and contraction operators over Polish spaces.
result The distribution of random sequences converges to the invariant distribution of the Markov chain.
Estimates metric tensor on neuromanifolds using Fisher information and random methods.
problem Computing the metric tensor on high-dimensional neuromanifolds efficiently and accurately.
method Deterministic bounds and unbiased random estimators based on Hutchinson's trace method.
result An efficient random estimator with bounded standard deviation.
New framework improves fraud prediction with incremental data balancing for massive data streams.
problem Class imbalance problem in massive imbalanced data streams.
method Incremental data balancing framework using Racing Algorithm for automated balancing and Random Forest for classification.
result Better results than Batch mode on European Credit Card dataset.
Adaptive Langevin dynamics reduces bias in Bayesian inference with mini-batching.
problem Bias in posterior sampling due to mini-batching in Bayesian inference.
method Adaptive Langevin dynamics with dynamical friction to correct noise.
result Quantified bias in posterior distribution due to mini-batching.