Stochastic Gradient Optimization Techniques

Últimos artículos

• Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds

  Sifan Yang, Wenhao Yang, Wei Jiang, Lijun Zhang · 9 de enero de 2026

  We investigate distributed online convex optimization with compressed communication, where $n$ learners connected by a network collaboratively minimize a sequence of global loss functions using only local information and compressed data from neighbors. Prior work has established regret bounds of $O(…

• Predictable Gradient Manifolds in Deep Learning: Temporal Path-Length and Intrinsic Rank as a Complexity Regime

  Anherutowa Calvo · 9 de enero de 2026

  Deep learning optimization exhibits structure that is not captured by worst-case gradient bounds. Empirically, gradients along training trajectories are often temporally predictable and evolve within a low-dimensional subspace. In this work we formalize this observation through a measurable framewor…

• Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization

  Zhen Qin, Zhishuai Liu, Pan Xu · 9 de enero de 2026

  signSGD is popular in nonconvex optimization due to its communication efficiency. Yet, existing analyses typically assume data are sampled with replacement in each iteration, contradicting a common practical implementation where data are randomly reshuffled and sequentially fed into the algorithm. T…

• NC2C: Automated Convexification of Generic Non-Convex Optimization Problems

  Xinyue Peng, Yanming Liu, Yihan Cang, Yuwei Zhang, Xinyi Wang, Songhang Deng, Jiannan Cao · 9 de enero de 2026

  Non-convex optimization problems are pervasive across mathematical programming, engineering design, and scientific computing, often posing intractable challenges for traditional solvers due to their complex objective functions and constrained landscapes. To address the inefficiency of manual convexi…

• Learning Shrinks the Hard Tail: Training-Dependent Inference Scaling in a Solvable Linear Model

  Noam Levi · 8 de enero de 2026

  We analyze neural scaling laws in a solvable model of last-layer fine-tuning where targets have intrinsic, instance-heterogeneous difficulty. In our Latent Instance Difficulty (LID) model, each input's target variance is governed by a latent ``precision'' drawn from a heavy-tailed distribution. Whil…

• Provably Convergent Decentralized Optimization over Directed Graphs under Generalized Smoothness

  Yanan Bo, Yongqiang Wang · 8 de enero de 2026

  Decentralized optimization has become a fundamental tool for large-scale learning systems; however, most existing methods rely on the classical Lipschitz smoothness assumption, which is often violated in problems with rapidly varying gradients. Motivated by this limitation, we study decentralized op…

• Architecture independent generalization bounds for overparametrized deep ReLU networks

  Anandatheertha Bapu, Thomas Chen, Chun-Kai Kevin Chien, Patricia Mu\~noz Ewald, Andrew G. Moore · 8 de enero de 2026

  We prove that overparametrized neural networks are able to generalize with a test error that is independent of the level of overparametrization, and independent of the Vapnik-Chervonenkis (VC) dimension. We prove explicit bounds that only depend on the metric geometry of the test and training sets, …

• Provable Acceleration of Distributed Optimization with Local Updates

  Zuang Wang, Yongqiang Wang · 8 de enero de 2026

  In conventional distributed optimization, each agent performs a single local update between two communication rounds with its neighbors to synchronize solutions. Inspired by the success of using multiple local updates in federated learning, incorporating local updates into distributed optimization h…

• Convergence of Decentralized Stochastic Subgradient-based Methods for Nonsmooth Nonconvex functions

  Siyuan Zhang, Nachuan Xiao, Xin Liu · 7 de enero de 2026

  In this paper, we focus on the decentralized stochastic subgradient-based methods in minimizing nonsmooth nonconvex functions without Clarke regularity, especially in the decentralized training of nonsmooth neural networks. We propose a general framework that unifies various decentralized subgradien…

• Polynomial Convergence of Riemannian Diffusion Models

  Xingyu Xu, Ziyi Zhang, Yorie Nakahira, Guannan Qu, Yuejie Chi · 7 de enero de 2026

  Diffusion models have demonstrated remarkable empirical success in the recent years and are considered one of the state-of-the-art generative models in modern AI. These models consist of a forward process, which gradually diffuses the data distribution to a noise distribution spanning the whole spac…

• On the Convergence Behavior of Preconditioned Gradient Descent Toward the Rich Learning Regime

  Shuai Jiang, Alexey Voronin, Eric Cyr, Ben Southworth · 7 de enero de 2026

  Spectral bias, the tendency of neural networks to learn low frequencies first, can be both a blessing and a curse. While it enhances the generalization capabilities by suppressing high-frequency noise, it can be a limitation in scientific tasks that require capturing fine-scale structures. The delay…

• MAST: Model-Agnostic Sparsified Training

  Yury Demidovich, Grigory Malinovsky, Egor Shulgin, Peter Richt\'arik · 7 de enero de 2026

  We introduce a novel optimization problem formulation that departs from the conventional way of minimizing machine learning model loss as a black-box function. Unlike traditional formulations, the proposed approach explicitly incorporates an initially pre-trained model and random sketch operators, a…

• First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data

  Artavazd Maranjyan · 7 de enero de 2026

  Artificial intelligence has advanced rapidly through large neural networks trained on massive datasets using thousands of GPUs or TPUs. Such training can occupy entire data centers for weeks and requires enormous computational and energy resources. Yet the optimization algorithms behind these runs h…

• The Homogeneity Trap: Spectral Collapse in Doubly-Stochastic Deep Networks

  Yizhi Liu · 6 de enero de 2026

  Doubly-stochastic matrices (DSM) are increasingly utilized in structure-preserving deep architectures -- such as Optimal Transport layers and Sinkhorn-based attention -- to enforce numerical stability and probabilistic interpretability. In this work, we identify a critical spectral degradation pheno…

• Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity

  Boris Prokhorov, Semyon Chebykin, Alexander Gasnikov, Aleksandr Beznosikov · 6 de enero de 2026

  This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such problems in strongly convex smooth and non-smooth settings with both one-point and two-point feedback oracles. Using a ran…

• SGD with Dependent Data: Optimal Estimation, Regret, and Inference

  Yinan Shen, Yichen Zhang, Wen-Xin Zhou · 6 de enero de 2026

  This work investigates the performance of the final iterate produced by stochastic gradient descent (SGD) under temporally dependent data. We consider two complementary sources of dependence: $(i)$ martingale-type dependence in both the covariate and noise processes, which accommodates non-stationar…

• Sobolev Approximation of Deep ReLU Network in Log-weighted Barron Space

  Changhoon Song, Seungchan Ko, Youngjoon Hong · 6 de enero de 2026

  Universal approximation theorems show that neural networks can approximate any continuous function; however, the number of parameters may grow exponentially with the ambient dimension, so these results do not fully explain the practical success of deep models on high-dimensional data. Barron space t…

• A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory

  Itay Safran · 6 de enero de 2026

  We consider the problem of exact computation of the maximum function over $d$ real inputs using ReLU neural networks. We prove a depth hierarchy, wherein width $\Omega\big(d^{1+\frac{1}{2^{k-2}-1}}\big)$ is necessary to represent the maximum for any depth $3\le k\le \log_2(\log_2(d))$. This is the f…

• Leveraging Flatness to Improve Information-Theoretic Generalization Bounds for SGD

  Ze Peng, Jian Zhang, Yisen Wang, Lei Qi, Yinghuan Shi, Yang Gao · 6 de enero de 2026

  Information-theoretic (IT) generalization bounds have been used to study the generalization of learning algorithms. These bounds are intrinsically data- and algorithm-dependent so that one can exploit the properties of data and algorithm to derive tighter bounds. However, we observe that although th…

• Multi-Subspace Multi-Modal Modeling for Diffusion Models: Estimation, Convergence and Mixture of Experts

  Ruofeng Yang, Yongcan Li, Bo Jiang, Cheng Chen, Shuai Li · 6 de enero de 2026

  Recently, diffusion models have achieved a great performance with a small dataset of size $n$ and a fast optimization process. However, the estimation error of diffusion models suffers from the curse of dimensionality $n^{-1/D}$ with the data dimension $D$. Since images are usually a union of low-di…

• Learning with Monotone Adversarial Corruptions

  Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty · 6 de enero de 2026

  We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon looking at a "clean" i.i.d. dataset, inserts additional "corrupted" points of their choice into…

• FANoS: Friction-Adaptive Nos\'e--Hoover Symplectic Momentum for Stiff Objectives

  Nalin Dhiman · 6 de enero de 2026

  We study a physics-inspired optimizer, \emph{FANoS} (Friction-Adaptive Nos\'e--Hoover Symplectic momentum), which combines (i) a momentum update written as a discretized second-order dynamical system, (ii) a Nos\'e--Hoover-like thermostat variable that adapts a scalar friction coefficient using kine…

• Game of Coding: Coding Theory in the Presence of Rational Adversaries, Motivated by Decentralized Machine Learning

  Hanzaleh Akbari Nodehi, Viveck R. Cadambe, Mohammad Ali Maddah-Ali · 6 de enero de 2026

  Coding theory plays a crucial role in enabling reliable communication, storage, and computation. Classical approaches assume a worst-case adversarial model and ensure error correction and data recovery only when the number of honest nodes exceeds the number of adversarial ones by some margin. Howeve…

• Fibonacci-Driven Recursive Ensembles: Algorithms, Convergence, and Learning Dynamics

  Ernest Fokou\'e · 6 de enero de 2026

  This paper develops the algorithmic and dynamical foundations of recursive ensemble learning driven by Fibonacci-type update flows. In contrast with classical boosting Freund and Schapire (1997); Friedman (2001), where the ensemble evolves through first-order additive updates, we study second-order…

• Categorical Reparameterization with Denoising Diffusion models

  Samson Gourevitch, Alain Durmus, Eric Moulines, Jimmy Olsson, Yazid Janati · 5 de enero de 2026

  Gradient-based optimization with categorical variables typically relies on score-function estimators, which are unbiased but noisy, or on continuous relaxations that replace the discrete distribution with a smooth surrogate admitting a pathwise (reparameterized) gradient, at the cost of optimizing a…