Overview

Gradient descent is a family of methods that repeatedly adjusts parameters in the direction that lowers an objective, making it a basic tool for training neural networks and fitting models such as logistic regression. Common approaches include full-batch and stochastic gradient descent, momentum and Nesterov acceleration, adaptive optimizers such as Adam, and geometry-aware variants such as natural, preconditioned, projected, or mirror descent. Theory and applications span deep-network training, matrix recovery, differential privacy, and decentralized or federated learning, with evaluations often measuring convergence, prediction quality, communication, memory, or privacy cost. A central tension is that larger or adaptive steps can speed training but also cause oscillations or instability, while the geometry, noise, and stopping time can change both which solution is reached and how well it generalizes.

Latest papers

122 papers4 papers in the last four weeks, down 79% on the four weeks before. 0.0% of all new papers.

Jun 7, 2024

Gradient Descent on Logistic Regression with Non-Separable Data and Large Step Sizes

We study gradient descent (GD) dynamics on logistic regression problems with large, constant step sizes. For linearly-separable data, it is known that GD converges to the minimizer with arbitrarily large step sizes, a property which no longer holds when the problem is not separable. In fact, the behaviour can be much more complex -- a sequence of period-doubling bifurcations begins at the critical step size 2/λ2/λ, where λλ is the largest eigenvalue of the Hessian at the solution. Using a smaller-than-critical step size guarantees convergence if initialized nearby the solution: but does this suffice globally? In one dimension, we show that a step size less than 1/λ1/λ suffices for global convergence. However, for all step sizes between 1/λ1/λ and the critical step size 2/λ2/λ, one can construct a dataset such that GD converges to a stable cycle. In higher dimensions, this is actually possible even for step sizes less than 1/λ1/λ. Our results show that although local convergence is guaranteed for all step sizes less than the critical step size, global convergence is not, and GD may instead converge to a cycle depending on the initialization.
Jan 26, 2022

Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant

Training logistic regression over encrypted data has emerged as a prominent approach to addressing security concerns in recent years. In this paper, we introduce an efficient gradient variant, termed the quadratic gradient, which is specifically designed for privacy-preserving logistic regression while remaining equally effective in plaintext optimization. By incorporating this quadratic gradient, we enhance Nesterov's Accelerated Gradient (NAG), Adaptive Gradient (AdaGrad), and Adam algorithms. We evaluate these enhanced algorithms across various datasets, with experimental results demonstrating state-of-the-art convergence rates that significantly outperform traditional first-order gradient methods. Furthermore, we apply the enhanced NAG method to implement homomorphic logistic regression training, achieving comparable performance within only four iterations. The proposed quadratic-gradient approach offers a unified framework that synergizes the advantages of first-order gradient methods and second-order Newton-type methods, suggesting broad applicability to diverse numerical optimization tasks.