arXiv research

Armijo line-search speeds up gradient descent for various functions.

Early stopping improves logistic regression's calibration and consistency in high dimensions.

GD outperforms ridge regression and SGD in linear regression problems.

SGD generalizes better than GD with similar number of iterations.

DP-GD improves CNN training accuracy with privacy, especially with low signal-to-noise ratios.

Accelerates ERM problems with LPI-GD and improved oracle complexity.

GD at EoS edge minimizes logistic loss without monotonic convergence.

GD with large, adaptive stepsizes achieves optimal risk in logistic regression.

New stability bounds for GD in overparameterised shallow nets without NTK assumptions.

CEM-GD combines CEM and gradient descent for efficient model-based RL.

The expectation-maximization (EM) algorithm has been widely used in minimizing the negative log likelihood (also known as cross entropy) of mixture models. However, little is understood about the goodness of the fixed points it converges to. In this paper, we study the regions where one component is missing in two-comp…

Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The server receives all its information about the problem instance from the wo…

This paper discusses a new type of discriminant analysis based on the orthogonal projection of data onto a generalized difference subspace (GDS). In our previous work, we have demonstrated that GDS projection works as the quasi-orthogonalization of class subspaces, which is an effective feature extraction for subspace …

GD with large init shows incremental learning in matrix factorization.

We propose a Generalized Dantzig Selector (GDS) for linear models, in which any norm encoding the parameter structure can be leveraged for estimation. We investigate both computational and statistical aspects of the GDS. Based on conjugate proximal operator, a flexible inexact ADMM framework is designed for solving GDS…

The behavior of the gradient descent (GD) algorithm is analyzed for a deep neural network model with skip-connections. It is proved that in the over-parametrized regime, for a suitable initialization, with high probability GD can find a global minimum exponentially fast. Generalization error estimates along the GD path…

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

Study on GD and SGD over diagonal networks, focusing on stepsizes and regularisation.

Although gradient descent (GD) almost always escapes saddle points asymptotically [Lee et al., 2016], this paper shows that even with fairly natural random initialization schemes and non-pathological functions, GD can be significantly slowed down by saddle points, taking exponential time to escape. On the other hand, g…

Derives EoM for DNNs to describe GD dynamics precisely.

Study robustness of early-stopping GD for linear regression attacks.

New method aggregates GDS analyses of randomly selected interaction models to identify important factors in screening experiments.

Linear Transformer Block combines MLP and linear attention for near-optimal ICL in linear regression.

Momentum improves deep learning generalization by stabilizing noise and learning features.

This paper extends stability and generalization analysis of GD for multi-layer NNs.

We study the convergence of gradient descent (GD) and stochastic gradient descent (SGD) for training $L$-hidden-layer linear residual networks (ResNets). We prove that for training deep residual networks with certain linear transformations at input and output layers, which are fixed throughout training, both GD and SGD…

GD monotonically decreases GFS sharpness in neural networks and scalar models.

GD-VAEs learn dynamics from observations using geometric and topological information.

Large stepsize GD for logistic regression converges faster than expected.

Local Gradient Descent with local steps converges to the centralized model in the interpolation regime.

Analysis of cross-validation for early-stopped gradient descent in high-dimensional regression.

GD learns matrix solutions incrementally, revealing insights into generalization.

We present ErasureHead, a new approach for distributed gradient descent (GD) that mitigates system delays by employing approximate gradient coding. Gradient coded distributed GD uses redundancy to exactly recover the gradient at each iteration from a subset of compute nodes. ErasureHead instead uses approximate gradien…

Gradient descent converges with arbitrary stepsize for separable data under Fenchel-Young losses.

GD-trained shallow ReLU nets learn Lipschitz functions with noise.

GD iterates for non-homogeneous deep nets increase margin and converge in direction.

Gradient Descent (GD) approximators often fail in the solution space with multiple scales of convexities, i.e., in subspace learning and neural network scenarios. To handle that, one solution is to run GD multiple times from different randomized initial states and select the best solution over all experiments. However,…

Differentiable learning via SGD and GD can simulate various learning problems, depending on precision and minibatch size.

Gradient descent near stability threshold shows sharpness oscillations.

Study EM and GD for clustering with penalties for misspecification and high dimensions.

Gradient descent near stability threshold exhibits sharpness oscillations.

Nesterov's accelerated gradient descent (AGD), an instance of the general family of "momentum methods", provably achieves faster convergence rate than gradient descent (GD) in the convex setting. However, whether these methods are superior to GD in the nonconvex setting remains open. This paper studies a simple variant…

Large GD stepsizes improve margins and speed up training for non-homogeneous networks.

GD converges faster to flatter minima than gradient flow in shallow networks.

Gradient Descent with small random initialization solves rank-1 matrix completion efficiently.

Anti-correlated noise improves machine learning model generalization.

The goal of this paper is to characterize function distributions that deep learning can or cannot learn in poly-time. A universality result is proved for SGD-based deep learning and a non-universality result is proved for GD-based deep learning; this also gives a separation between SGD-based deep learning and statistic…

GD with early stopping trains shallow neural nets for nonparametric regression robustly.