Skip to main content
Search

# Stochastic Gradient Descent

4 related articles

Subscribe to updates
  1. arXiv

    Constrained optimization stops sampling constraints uniformly: keeping recently violated ones cuts iterate error by two orders of magnitude on synthetic problems

    For stochastic-gradient optimization with very many inequality constraints, an adaptive constraint-sampling method stops drawing each step's constraint uniformly from all constraints and instead maintains an "important set" of recently violated constraints, sampling from that set or from all constraints with fixed probabilities. On 100-dimensional synthetic convex problems it lowers the final Euclidean distance of the iterates to the constrained minimizer by about two orders of magnitude on average for ABSGD, Projection-SGD and Huber-penalty SGD, and by one to two orders for APDSG; in Dubins Car control-barrier-function synthesis it lowers maximum constraint violation by half an order to one order of magnitude.

  2. arXiv

    Gradient descent's implicit bias is no longer set by initialization alone: step size tilts the limit toward a perturbed weighted L1 minimizer

    The training limit of deep linear diagonal networks had been characterized only for gradient flow, the continuous version with vanishing step size, where the implicit bias is fixed entirely by initialization. This analysis rewrites discrete gradient descent and stochastic gradient descent themselves as perturbed mirror gradient descent, proves convergence of the iterates for any number of layers, and characterizes the limit as a convex minimization problem parameterized by a perturbed initialization. The perturbation shrinks linearly with step size, so the limit corresponds to weighted L1 minimization whose weights depend on initialization, step size and the whole iterate trajectory.

  3. arXiv

    SGD convergence rates can be transferred: one Lyapunov calculation on a diffusion, then carried back window by window

    Finite-time convergence bounds for stochastic gradient algorithms can be transferred from Lyapunov estimates for an associated stochastic differential equation, recovering known rates for strongly convex SGD and stochastic Heavy Ball.

  4. Hasegawa and Ohzeki compare Ising and QUBO encodings under fixed model, sampler, and step size, finding QUBO has lower Fisher spectral entropy and slower SGD convergence while natural gradient descent makes the encodings converge alike

    Under a controlled protocol that fixes the Boltzmann machine model, simulated-annealing sampler, and learning-rate design, the study compares Ising ({−1,+1}) and QUBO ({0,1}) variable encodings, exploits the identity that the Fisher information matrix equals the covariance of sufficient statistics to visualize empirical moments, and finds that QUBO induces larger cross terms between first- and second-order statistics, creating more small-eigenvalue directions and lowering spectral entropy, which explains slower convergence under stochastic gradient descent, whereas natural gradient descent, which rescales updates by the Fisher information matrix metric, achieves similar convergence across encodings due to reparameterization invariance.

You’re all caught up