Coded computation techniques provide robustness against straggling servers in distributed computing, with the following limitations: First, they increase decoding complexity. Second, they ignore computations carried out by straggling servers; and they are typically designed to recover the full gradient, and thus, canno…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “Gradient computation”
A new method computes gradients without backpropagation.
problem Optimization of machine learning models.
method Forward mode automatic differentiation to compute gradients.
result Forward gradient is an unbiased estimate of the gradient, eliminating the need for backpropagation.
Regularizes persistent homology gradients for neural network integration.
problem Ill-posed inverse problem in computing gradients of persistent homology.
method Regularization through a grouping term to define gradients for larger entities.
result Ensures gradients are defined with respect to larger entities, not individual points.
This technical report describes an efficient technique for computing the norm of the gradient of the loss function for a neural network with respect to its parameters. This gradient norm can be computed efficiently for every example.
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.
GA method reduces gradient staleness in cloud computing.
problem Gradient staleness in asynchronous SGD methods.
method Gap-Aware (GA) method that penalizes stale gradients linearly to the Gap.
result GA outperforms existing methods in final test accuracy.
Enhances SGLD for log-concave posteriors with asynchronous computation.
problem Sampling log-concave posterior distributions efficiently.
method Integrates asynchronous computation into SGLD with delayed gradients.
result Convergence in measure is not significantly affected by delayed gradient information.
Efficiently computes per-example gradients in CNNs for differential privacy.
problem Computing per-example gradients in CNNs for differential privacy.
method Comparison of existing strategies and introduction of a new per-example gradient calculation method.
result The new method is advantageous depending on model architecture and training.
RAD estimates gradients with less memory, faster than small batch sizes.
problem Training deep models with stochastic gradient descent requires exact gradients, but they are not needed.
method Developed a framework for randomized automatic differentiation (RAD) to compute unbiased gradient estimates with reduced memory.
result RAD converges in fewer iterations than using a small batch size for feedforward networks and similar number for recurrent networks.
New method efficiently computes gradients for stochastic differential equations.
problem Computing gradients for stochastic differential equations efficiently.
method Generalized adjoint sensitivity method to stochastic differential equations.
result Time-efficient and memory-efficient computation of gradients with high-order solvers.
This work improves SGD convergence by adaptively adjusting batch sizes.
problem High variance in gradient estimates with small batch sizes.
method Adaptive batch size adjustment based on model training loss.
result Adaptive batch size method requires fewer model updates with same computation.
Tuning hyperparameters of learning algorithms is hard because gradients are usually unavailable. We compute exact gradients of cross-validation performance with respect to all hyperparameters by chaining derivatives backwards through the entire training procedure. These gradients allow us to optimize thousands of hyper…
Improved bounds for proximal gradient algorithms with computational errors.
problem Analyzing convergence of proximal gradient algorithms with inaccuracies.
method Deriving new tighter deterministic and probabilistic bounds for convex composite problems.
result Probabilistic bounds are more robust and accurate for algorithm verification and performance guarantees.
Gradient codes use block designs to resist adversarial stragglers in distributed computing.
problem Mitigating slow machines (stragglers) in distributed gradient-based methods.
method Gradient coding based on balanced incomplete block designs (BIBDs) to resist adversarial selection of stragglers.
result Adversarial stragglers have no advantage over random selection, and codes based on symmetric BIBDs maximize the adversarial threshold.
A method predicts GNS of transformer layers using normalization layer norms.
problem Estimating gradient noise scale with minimal variance.
method Simultaneously compute per-example gradient norms and parameter gradients.
result Total GNS is predicted well by normalization layer GNS.
Gradient codes adapt to varying straggler counts in distributed learning.
problem Mitigating slow worker nodes (stragglers) in distributed machine learning.
method Proposes a flexible gradient coding scheme that concatenates codes for different straggler tolerances, adapting to actual straggler counts.
result Significantly lower latency compared to fixed-tolerance gradient codes.
RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments c…
Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the invol…
We introduce a new, high-throughput, synchronous, distributed, data-parallel, stochastic-gradient-descent learning algorithm. This algorithm uses amortized inference in a compute-cluster-specific, deep, generative, dynamical model to perform joint posterior predictive inference of the mini-batch gradient computation ti…
A new method for efficient computation of Knowledge Gradient in Bayesian optimization.
problem Efficient computation of the Knowledge Gradient for Bayesian optimization.
method One-shot Hybrid KG, a new approach combining previous ideas.
result The new method is cheap to compute and preserves theoretical properties of previous methods.
This study reveals efficient finite-difference computation for gradient regularization in deep learning.
problem Improving generalization performance in deep learning through gradient regularization.
method Analyzes and reveals a specific finite-difference computation that reduces computational cost and improves generalization performance.
result Finite-difference computation strengthens the implicit bias towards rich regimes and enhances generalization performance.
The Cheap Gradient Principle (Griewank 2008) --- the computational cost of computing the gradient of a scalar-valued function is nearly the same (often within a factor of ) as that of simply computing the function itself --- is of central importance in optimization; it allows us to quickly obtain (high dimensional) …
Paper extends knowledge gradient for preferential BO, overcoming computational challenges.
problem Extending knowledge gradient to preferential BO with pairwise comparisons.
method Derive exact and analytical knowledge gradient for preferential BO.
result Exact knowledge gradient outperforms existing acquisition functions on benchmark problems.
Storchastic improves stochastic AD for complex models in RL and VI.
problem Handling intractable expectations in RL and VI.
method Introduces Storchastic, a framework for AD of stochastic computation graphs with various gradient estimation methods.
result Provable unbiasedness and variance reduction for higher-order gradients.
Stochastic variational inference (SVI) lets us scale up Bayesian computation to massive data. It uses stochastic optimization to fit a variational distribution, following easy-to-compute noisy natural gradients. As with most traditional stochastic optimization methods, SVI takes precautions to use unbiased stochastic g…
Gradient descent algorithms on manifolds solve control and mean computation problems.
problem Control and mean computation on positive definite Hermitian matrices.
method Riemannian and natural gradient algorithms applied to geodesic distance.
result Efficient algorithms for control and mean computation demonstrated.
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradie…
Optimizes CNNs by directing gradients along output channels.
problem Improving generalization error in CNNs.
method Output-channel directed re-weighted L2 or Sobolev metrics.
result Improves generalization error by optimizing gradients.
New cross-validation methods for Gaussian process regression with efficient gradient computation.
problem Estimating parameters of Gaussian process covariance functions.
method Derive new cross-validation criteria and efficient adjoint computation of gradients.
result Efficient method for evaluating cross-validation criteria and their gradients.
A new method for stochastic optimization using virtual gradients.
problem Stochastic optimization challenges in computational efficiency and memory usage.
method Inspired by dynamic programming, SVGD uses a computational graph and automatic differentiation for efficient optimization.
result Experimental results show SVGD outperforms other methods on multiple datasets and network models.
We provide the first experimental results on non-synthetic datasets for the quasi-diagonal Riemannian gradient descents for neural networks introduced in [Ollivier, 2015]. These include the MNIST, SVHN, and FACE datasets as well as a previously unpublished electroencephalogram dataset. The quasi-diagonal Riemannian alg…
A large class of machine learning techniques requires the solution of optimization problems involving spectral functions of parametric matrices, e.g. log-determinant and nuclear norm. Unfortunately, computing the gradient of a spectral function is generally of cubic complexity, as such gradient descent methods are rath…
This paper investigates asymptotic behaviors of gradient descent algorithms (particularly accelerated gradient descent and stochastic gradient descent) in the context of stochastic optimization arising in statistics and machine learning where objective functions are estimated from available data. We show that these alg…
Paper introduces MNNs for efficient neural network training.
problem Training large-scale sparse neural networks efficiently.
method Formal derivation of MNN architecture with forward-only gradient propagation.
result MNNs can efficiently compute gradients without backward computation.
Develops implicit MAML for efficient few-shot learning.
problem Efficient few-shot learning with limited data.
method Implicit differentiation for inner loop optimization.
result Agrees with inner loop optimizer choice and handles many gradient steps.
Unbiased Gradient Estimation in Unrolled Computation Graphs with Persistent Evolution Strategiescs.LG
PES method reduces bias in gradient estimation for unrolled graphs.
problem High variance and bias in gradient estimation for unrolled computation graphs.
method Divide graph into unrolls, apply ES update, accumulate correction terms.
result PES provides unbiased, low-variance gradient estimates.
A method for estimating the median of gradients in stochastic optimization.
problem Robust gradient estimation in stochastic optimization for various applications.
method Stochastic Proximal Point Method for median gradient estimation.
result The proposed method can converge even under heavy-tailed, state-dependent noise.
Distributed algorithms are often beset by the straggler effect, where the slowest compute nodes in the system dictate the overall running time. Coding-theoretic techniques have been recently proposed to mitigate stragglers via algorithmic redundancy. Prior work in coded computation and gradient coding has mainly focuse…
SVRG reduces gradient evaluations for policy evaluation in reinforcement learning.
problem Policy evaluation in reinforcement learning with high computational costs.
method Two variants of SVRG for policy evaluation that reduce gradient calculations.
result Significant reduction in the number of gradient evaluations while preserving linear convergence speed.
A new metric GNQ audits LLMs for privacy risks during training.
problem Auditing LLMs for privacy risks during training is computationally hard.
method Gradient Uniqueness (GNQ) metric derived from gradient descent, BS-Ghost GNQ for efficiency.
result GNQ successfully predicts sequence extractability and reveals risk heterogeneity.
Recently the so-called Atiyah conjecture about l^2-Betti numbers has been disproved. The counterexamples were found using a specific method of computing the spectral measure of a matrix over a complex group ring. We show that in many situations the same method allows to compute homology gradients, i.e. generalizations …
New method improves accuracy in computing implied volatility.
problem Computing implied volatility from the Black-Scholes model.
method Adaptive gradient descent optimizers for numerical computation.
result More accurate results compared to close form approximation and Newton-Raphson method.
New algorithms improve Langevin Monte Carlo efficiency.
problem High computational cost of classical Langevin Monte Carlo.
method Integrates ensemble feature into LMC, constraining gradient approximations.
result Constrained Ensemble Langevin Monte Carlo reduces gradient computation.
Stochastic gradient descent procedures have gained popularity for parameter estimation from large data sets. However, their statistical properties are not well understood, in theory. And in practice, avoiding numerical instability requires careful tuning of key parameters. Here, we introduce implicit stochastic gradien…
We propose Kernel Hamiltonian Monte Carlo (KMC), a gradient-free adaptive MCMC algorithm based on Hamiltonian Monte Carlo (HMC). On target densities where classical HMC is not an option due to intractable gradients, KMC adaptively learns the target's gradient structure by fitting an exponential family model in a Reprod…
Proposes a method to balance tasks in multitask learning with a single gradient step update.
problem Balancing tasks in multitask learning to avoid imbalance.
method Gradient-based meta-learning to balance tasks at the gradient level, training shared and task-specific layers separately.
result Achieves state-of-the-art performance on various multitask computer vision problems.
Gradient boosting with randomized trees reduces discontinuities and complexity.
problem Discontinuities in regression functions due to sparse training data.
method Gradient boosting machine with partially randomized decision trees.
result Improves robustness and computational efficiency of gradient boosting.
A new measure helps compute suboptimality in entropy-regularized methods.
problem Computing suboptimality in entropy-regularized variational objectives when unnormalised densities are unavailable.
method Introduced 'kernel gradient discrepancy' (KGD) to compute suboptimality explicitly.
result KGD characterizes kernel Stein discrepancy (KSD) in the standard Bayesian context and measures variational gradient size.