We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Base…
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,695 papers · 148 categories
Trend · papers per month
48 results for “biased gradient descent”
A number of optimization approaches have been proposed for optimizing nonconvex objectives (e.g. deep learning models), such as batch gradient descent, stochastic gradient descent and stochastic variance reduced gradient descent. Theory shows these optimization methods can converge by using an unbiased gradient estimat…
Study reveals biases in gradient descent for GLNs, improving neural network performance.
problem Understanding and improving the inductive biases of deep neural networks.
method Derive infinite-time training limit of gated linear networks and generalize to other networks.
result Theoretical framework captures key inductive biases of ReLU networks.
A new biased gradient descent method for conditional stochastic optimization.
problem Challenges in constructing unbiased gradient estimators for conditional stochastic optimization.
method Proposes a biased stochastic gradient descent (BSGD) algorithm and analyzes its sample complexities.
result Establishes sample complexities of BSGD for various objectives and shows that BSpiderBoost matches the lower bound complexity.
New biased compression methods lead to faster convergence in distributed learning.
problem Improving convergence rates in distributed learning with biased compression.
method Study of three classes of biased compression operators in distributed learning.
result Biased compressors can lead to linear convergence rates in both single node and distributed settings.
Gradient descent with biased rounding errors converges faster under certain conditions.
problem Stagnation or negative impact of rounding errors in neural network training with low precision.
method Analysis of gradient descent with stochastic fixed-point rounding errors under the Polyak-Lojasiewicz inequality.
result Biased rounding errors can improve convergence rates, especially when the Polyak-Lojasiewicz inequality holds.
Implicit biases in multitask and continual learning from a backward error analysis perspectivestat.ML
The study analyzes implicit biases in neural networks using backward error analysis.
problem Analyzing implicit biases in multitask and continual learning settings.
method Backward error analysis to compute implicit training biases, deriving modified losses with three terms.
result The conflict term, measuring gradient alignment, is a new quantity in continual learning.
New oracles improve stochastic optimization with noisy or biased measurements.
problem Optimizing functions with noisy or biased measurements.
method Introduced biased gradient oracles for stochastic optimization, analyzed RSG and SGD algorithms with these oracles.
result Derived non-asymptotic bounds for convergence rates of algorithms with biased gradient oracles.
Derives equations for deep learning biases and weights, showing data complexity reduction.
problem Understanding interpretability in supervised learning.
method Gradient flow equations and dynamical truncation of training data.
result Data complexity reduction at an exponential rate with training.
Gradient descent implicitly regularizes neural networks by penalizing large loss gradients.
problem How to optimize deep neural networks without explicit regularization.
method Backward error analysis to calculate implicit gradient regularization and demonstrate its effectiveness empirically.
result Implicit gradient regularization biases gradient descent toward flat minima, improving model robustness and test errors.
Studied SGD convergence under weak conditions.
problem Convergence of SGD in nonconvex optimization.
method Analyzed biased nonconvex SGD under mild conditions.
result Provided convergence rates and complexities.
Large learning rates lead to various implicit biases in nonconvex optimization.
problem Understanding the conditions under which large learning rates yield edge of stability, balancing, and catapult phenomena.
method Developed a global convergence theory for nonconvex functions without globally Lipschitz continuous gradient, focusing on functions with good regularity.
result These implicit biases are more likely to occur in functions with good regularity, and large learning rates favor flatter regions.
Natural gradient descent avoids the magic of model parametrization, leading to different optimization outcomes.
problem Understanding the impact of model parametrization on optimization and generalization in deep learning.
method Characterization of natural gradient flow in deep linear networks and nonlinear neural networks.
result Natural gradient descent fails to generalize in some cases, while gradient descent with the right architecture performs well.
Gradient descent with large steps leads to chaotic parameter space and unpredictable outcomes.
problem Understanding the behavior of gradient descent with large step sizes in matrix factorization.
method Analyzing the fractal structure of the parameter space and deriving critical step sizes for convergence.
result Gradient descent with large steps exhibits chaotic behavior and sensitivity to initialization, creating a fractal boundary between converging and diverging minimizers.
Proposes Coherent Gradients to explain and reduce overfitting in neural networks.
problem Why neural networks generalize well despite fitting random data.
method Hypothesis about gradient dynamics and a modification to gradient descent.
result Supports hypothesis with heuristic arguments and perturbative experiments.
This paper analyzes SGD with biased gradients for deep learning models.
problem Analyzing SGD with biased gradients for deep learning models.
method Non-asymptotic analysis of SGD with adaptive steps for non-convex smooth functions.
result Adagrad, RMSProp, and AMSGRAD converge to critical points at a similar rate to unbiased case.
The paper analyzes time-dependent streaming data with biased gradient estimates and proposes improved stochastic optimization methods.
problem Stochastic optimization in a streaming setting with time-dependent and biased gradient estimates.
method Analysis of several first-order methods including SGD, mini-batch SGD, and time-varying mini-batch SGD, along with their Polyak-Ruppert averages.
result Time-varying mini-batch SGD methods can break long- and short-range dependence structures, and biased SGD methods can achieve comparable performance to their unbiased counterparts.
Gradient descent, when applied to the task of logistic regression, outputs iterates which are biased to follow a unique ray defined by the data. The direction of this ray is the maximum margin predictor of a maximal linearly separable subset of the data; the gradient descent iterates converge to this ray in direction a…
Gradient descent biases towards stable rank networks for nearly-orthogonal data.
problem Understanding implicit bias in non-smooth neural networks trained by gradient descent.
method Analysis of two-layer ReLU and leaky ReLU networks trained by gradient descent on nearly-orthogonal data.
result Gradient descent biases towards networks with stable rank and uniform margin for nearly-orthogonal data.
Feature Averaging: An Implicit Bias of Gradient Descent Leading to Non-Robustness in Neural Networkscs.LG
Gradient descent biases neural networks to use an average of features, leading to non-robustness.
problem Non-robustness in neural networks due to feature averaging.
method Theoretical analysis and experiments on binary classification tasks.
result Gradient descent trains networks to rely on an average of features, making them vulnerable to adversarial attacks.
Markov Chain Score Ascent: A Unifying Framework of Variational Inference with Markovian Gradientscs.LG
New framework improves variational inference with Markov chain methods.
problem Challenges of minimizing KL divergence with stochastic gradient descent.
method Markov chain score ascent (MCSA) methods, including parallel MCSA (pMCSA).
result Improved theoretical and empirical performance of MCSA methods.
New method improves online covariance estimation for SGD.
problem Improving online covariance estimation for SGD.
method Proposes a de-biased covariance estimator that eliminates second-order derivatives.
result Achieves a convergence rate of , outperforming existing methods.
A new scheme reduces global search cost by a square root factor.
problem Challenges in finding global minimum of cost functions.
method Gradient descent combined with a biased crossover of two good solutions.
result Quadratic speedup of global search efficiency.
We introduce a novel and efficient algorithm called the stochastic approximate gradient descent (SAGD), as an alternative to the stochastic gradient descent for cases where unbiased stochastic gradients cannot be trivially obtained. Traditional methods for such problems rely on general-purpose sampling techniques such …
Gradient descent implicitly favors group sparsity in neural networks.
problem Understanding implicit regularization in neural networks for structured sparsity.
method Novel neural reparameterization for diagonally grouped linear networks.
result Gradient descent without explicit regularization biases towards group sparsity.
We prove that two-layer (Leaky)ReLU networks initialized by e.g. the widely used method proposed by He et al. (2015) and trained using gradient descent on a least-squares loss are not universally consistent. Specifically, we describe a large class of one-dimensional data-generating distributions for which, with high pr…
This study investigates how gradient-based methods bias neural networks trained on high-dimensional data.
problem The implicit biases of gradient-based optimization algorithms in neural networks trained on high-dimensional data.
method Investigation of gradient flow and gradient descent in two-layer fully-connected neural networks with leaky ReLU activations.
result Gradient flow and gradient descent lead to neural networks with low-rank solutions and linear decision boundaries.
Neural nets learn simple distributions first, then more complex ones.
problem Understanding how neural networks generalize from simple to complex functions.
method Stochastic gradient descent training, synthetic data, CIFAR10, ImageNet pre-training.
result Neural networks initially use lower-order statistics, then higher-order ones.
New approach uses 'growth' and 'harvesting' concepts to improve deep learning models.
problem Current deep learning models lack transparency and high convergence rates.
method Reconsider neural networks as single-species population dynamics with balanced growth and harvesting rates.
result SGD with balanced growth and harvesting rates outperforms adaptive methods in all three requirements.
RS-PINN uses randomized smoothing to speed up high-dimensional PDE simulations without sacrificing accuracy.
problem High computational cost and bias in PINNs for high-dimensional PDEs.
method Introduces Gaussian noise for stochastic smoothing of PINNs, enabling Monte Carlo derivative approximation.
result Proposes bias correction techniques and a hybrid method to optimize the bias-variance trade-off.
The paper improves sparse Gaussian processes by optimizing predictive loss.
problem Optimizing predictive loss in sparse Gaussian processes.
method Direct loss minimization (DLM) for log-loss and square loss, with product sampling (uPS) and biased Monte Carlo (bMC) for non-conjugate cases.
result DLM shows significant performance improvement in both log-loss and square loss cases.
Gradient descent with geometrically adapted metrics drives cost to global minimum at uniform rate.
problem Minimizing cost in deep learning networks.
method Adapting gradient descent to output layer metric in deep learning.
result Uniform exponential convergence to global minimum in cost.
The natural gradient allows for more efficient gradient descent by removing dependencies and biases inherent in a function's parameterization. Several papers present the topic thoroughly and precisely. It remains a very difficult idea to get your head around however. The intent of this note is to provide simple intuiti…
Paper formalizes and analyzes a new bound for variational inference.
problem Lack of theoretical guarantees in variational algorithms.
method Introduces VR-IWAE bound, a generalization of IWAE.
result VR-IWAE bound leads to unbiased gradient estimators.
Energy-entropy competition and the effectiveness of stochastic gradient descent in machine learningcs.LG
Finding parameters that minimise a loss function is at the core of many machine learning methods. The Stochastic Gradient Descent algorithm is widely used and delivers state of the art results for many problems. Nonetheless, Stochastic Gradient Descent typically cannot find the global minimum, thus its empirical effect…
Distributed descent-based methods are an essential toolset to solving optimization problems in multi-agent system scenarios. Here the agents seek to optimize a global objective function through mutual cooperation. Oftentimes, cooperation is achieved over a wireless communication network that is prone to delays and erro…
The current interpretation of stochastic gradient descent (SGD) as a stochastic process lacks generality in that its numerical scheme restricts continuous-time dynamics as well as the loss function and the distribution of gradient noise. We introduce a simplified scheme with milder conditions that flexibly interprets S…
New method for unbiased regression reduces excess risk.
problem Least squares regression with optimal solution and Hessian matrix.
method Averaged stochastic gradient descent with time-average estimator.
result Unbiased estimator with O(1/k) expected excess risk.
Batch normalization biases linear models towards uniform margins, improving performance in binary classification.
problem Understanding the implicit bias of batch normalization in linear models and neural networks.
method Analyzing gradient descent convergence on linear models and two-layer CNNs with batch normalization.
result Gradient descent with batch normalization in linear models converges to a uniform margin classifier with an exponential convergence rate.
Study on dropout in neural networks using percolation theory.
problem Understanding dropout's effect on neural network training.
method Investigates percolation models mimicking dropout in neural networks.
result Dropout can cause a breakdown in neural networks.
DD algorithm tracks test error from train error without validation data.
problem Systematic generalization gap between train and test errors in modern model training.
method Decoupled descent (DD) algorithm that cancels data reuse biases via approximate message passing.
result DD algorithm rigorously demonstrates zero-cost validation and 100% data utilization.
This work bounds the run-time of nonconvex optimization with early stopping.
problem Bounding the expected run-time of nonconvex optimization with early stopping.
method Derives conditions for well-defined early stopping based on validation function norms and bounds the expected number of iterations and gradient evaluations.
result Guarantees the validity of early stopping and provides bounds on the expected run-time for various optimization algorithms.
We study the problem of learning-to-learn: inferring a learning algorithm that works well on tasks sampled from an unknown distribution. As class of algorithms we consider Stochastic Gradient Descent on the true risk regularized by the square euclidean distance to a bias vector. We present an average excess risk bound …
Stochastic gradient descent (SGD), which dates back to the 1950s, is one of the most popular and effective approaches for performing stochastic optimization. Research on SGD resurged recently in machine learning for optimizing convex loss functions and training nonconvex deep neural networks. The theory assumes that on…
Analyze SGD with biased gradients, improving convergence rates and accuracy.
problem Analyzing the convergence of SGD with biased gradients.
method Derive convergence results for smooth non-convex functions and quantify the impact of bias magnitude.
result Improved rates under the Polyak-Lojasiewicz condition and insights into how bias magnitude affects accuracy and convergence.
Paper proposes an unbiased optimization method for Bayesian experimental design.
problem Maximizing expected information gain in Bayesian experimental design.
method Randomized multilevel Monte Carlo (MLMC) method combined with stochastic gradient descent.
result An unbiased estimator for the gradient of expected information gain.
Study on how initialization scale affects neural network training regimes.
problem Understanding the transition between kernel and rich regimes in overparametrized models.
method Analysis of simple depth-D models and empirical testing on complex models.
result Scale of initialization controls transition between kernel and rich regimes.
New method identifies parameters of wider shallow neural networks with biases.
problem Identifying parameters of wide shallow neural networks with biases from finite samples.
method Two-step pipeline: direction of weights via second order information, signs via algebraic evaluations, biases via gradient descent.
result Constructive methods and theoretical guarantees of finite sample identification for wider shallow networks with biases.