Stochastic Gradient Optimization Techniques

Derniers papiers

• Local Duality for Sparse Support Vector Machines

  Penghe Zhang, Naihua Xiu, Houduo Qi · 29 janvier 2026

  Due to the rise of cardinality minimization in optimization, sparse support vector machines (SSVMs) have attracted much attention lately and show certain empirical advantages over convex SVMs. A common way to derive an SSVM is to add a cardinality function such as $\ell_0$-norm to the dual problem o…

• Deep-ICE: the first globally optimal algorithm for minimizing 0-1 loss in two-layer ReLU and maxout networks

  Xi He, Yi Miao, Max A. Little · 29 janvier 2026

  This paper introduces the first globally optimal algorithm for the empirical risk minimization problem of two-layer maxout and ReLU networks, i.e., minimizing the number of misclassifications. The algorithm has a worst-case time complexity of $O\left(N^{DK+1}\right)$, where $K$ denotes the number of…

• Membership Privacy Risks of Sharpness Aware Minimization

  Young In Kim, Andrea Agiollo, Pratiksha Agrawal, Johannes O. Royset, Rajiv Khanna · 29 janvier 2026

  Optimization algorithms that seek flatter minima, such as Sharpness-Aware Minimization (SAM), are credited with improved generalization and robustness to noise. We ask whether such gains impact membership privacy. Surprisingly, we find that SAM is more prone to Membership Inference Attacks (MIA) tha…

• Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise

  Gaku Omiya, Pierre-Louis Poirion, Akiko Takeda · 29 janvier 2026

  Randomized subspace methods reduce per-iteration cost; however, in nonconvex optimization, most analyses are expectation-based, and high-probability bounds remain scarce even under sub-Gaussian noise. We first prove that randomized subspace SGD (RS-SGD) admits a high-probability convergence bound un…

• Certificate-Guided Pruning for Stochastic Lipschitz Optimization

  Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma · 29 janvier 2026

  We study black-box optimization of Lipschitz functions under noisy evaluations. Existing adaptive discretization methods implicitly avoid suboptimal regions but do not provide explicit certificates of optimality or measurable progress guarantees. We introduce \textbf{Certificate-Guided Pruning (CGP)…

• Hyperparameter Transfer with Mixture-of-Expert Layers

  Tianze Jiang, Blake Bordelon, Cengiz Pehlevan, Boris Hanin · 29 janvier 2026

  Mixture-of-Experts (MoE) layers have emerged as an important tool in scaling up modern neural networks by decoupling total trainable parameters from activated parameters in the forward pass for each token. However, sparse MoEs add complexity to training due to (i) new trainable parameters (router we…

• Fractal and Regular Geometry of Deep Neural Networks

  Simmaco Di Lillo, Domenico Marinucci, Michele Salvi, Stefano Vigogna · 29 janvier 2026

  We study the geometric properties of random neural networks by investigating the boundary volumes of their excursion sets for different activation functions, as the depth increases. More specifically, we show that, for activations which are not very regular (e.g., the Heaviside step function), the b…

• Robust Distributed Learning under Resource Constraints: Decentralized Quantile Estimation via (Asynchronous) ADMM

  Anna van Elst, Igor Colin, Stephan Cl\'emen\c{c}on · 29 janvier 2026

  Specifications for decentralized learning on resource-constrained edge devices require algorithms that are communication-efficient, robust to data corruption, and lightweight in memory usage. While state-of-the-art gossip-based methods satisfy the first requirement, achieving robustness remains chal…

• Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes

  Abhishek Chakraborty, Angelia Nedi\'c · 29 janvier 2026

  We consider minimizing an objective function subject to constraints defined by the intersection of lower-level sets of convex functions. We study two cases: (i) strongly convex and Lipschitz-smooth objective function and (ii) convex but possibly nonsmooth objective function. To deal with the constra…

• Minimax Rates for Hyperbolic Hierarchical Learning

  Divit Rawal, Sriram Vishwanath · 29 janvier 2026

  We prove an exponential separation in sample complexity between Euclidean and hyperbolic representations for learning on hierarchical data under standard Lipschitz regularization. For depth-$R$ hierarchies with branching factor $m$, we first establish a geometric obstruction for Euclidean space: any…

• Sharpness of Minima in Deep Matrix Factorization

  Anil Kamber, Rahul Parhi · 29 janvier 2026

  Understanding the geometry of the loss landscape near a minimum is key to explaining the implicit bias of gradient-based methods in non-convex optimization problems such as deep neural network training and deep matrix factorization. A central quantity to characterize this geometry is the maximum eig…

• To Grok Grokking: Provable Grokking in Ridge Regression

  Mingyue Xu, Gal Vardi, Itay Safran · 28 janvier 2026

  We study grokking, the onset of generalization long after overfitting, in a classical ridge regression setting. We prove end-to-end grokking results for learning over-parameterized linear regression models using gradient descent with weight decay. Specifically, we prove that the following stages occ…

• Collaborative Compressors in Distributed Mean Estimation with Limited Communication Budget

  Harsh Vardhan, Arya Mazumdar · 28 janvier 2026

  Distributed high dimensional mean estimation is a common aggregation routine used often in distributed optimization methods. Most of these applications call for a communication-constrained setting where vectors, whose mean is to be estimated, have to be compressed before sharing. One could independe…

• Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining

  Yunwei Ren, Yatin Dandi, Florent Krzakala, Jason D. Lee · 28 janvier 2026

  The empirical success of deep learning is often attributed to deep networks' ability to exploit hierarchical structure in data, constructing increasingly complex features across layers. Yet despite substantial progress in deep learning theory, most optimization results sill focus on networks with on…

• Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise

  Yidong Wu, Luo Luo · 28 janvier 2026

  This paper considers the problem of asynchronous stochastic nonconvex optimization with heavy-tailed gradient noise and arbitrarily heterogeneous computation times across workers. We propose an asynchronous normalized stochastic gradient descent algorithm with momentum. The analysis show that our me…

• Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts

  TrungKhang Tran, TrungTin Nguyen, Gersende Fort, Tung Doan, Hien Duy Nguyen, Binh T. Nguyen, Florence Forbes, Christopher Drovandi · 28 janvier 2026

  Processing high-volume, streaming data is increasingly common in modern statistics and machine learning, where batch-mode algorithms are often impractical because they require repeated passes over the full dataset. This has motivated incremental stochastic estimation methods, including the increment…

• Accelerated Multiple Wasserstein Gradient Flows for Multi-objective Distributional Optimization

  Dai Hai Nguyen, Duc Dung Nguyen, Atsuyoshi Nakamura, Hiroshi Mamitsuka · 28 janvier 2026

  We study multi-objective optimization over probability distributions in Wasserstein space. Recently, Nguyen et al. (2025) introduced Multiple Wasserstein Gradient Descent (MWGraD) algorithm, which exploits the geometric structure of Wasserstein space to jointly optimize multiple objectives. Building…

• Stability and Generalization of Nonconvex Optimization with Heavy-Tailed Noise

  Hongxu Chen, Ke Wei, Xiaoming Yuan, Luo Luo · 28 janvier 2026

  The empirical evidence indicates that stochastic optimization with heavy-tailed gradient noise is more appropriate to characterize the training of machine learning models than that with standard bounded gradient variance noise. Most existing works on this phenomenon focus on the convergence of optim…

• High-Rate Quantized Matrix Multiplication: Theory and Practice

  Or Ordentlich, Yury Polyanskiy · 27 janvier 2026

  This work investigates the problem of quantized matrix multiplication (MatMul), which has become crucial for the efficient deployment of large language models (LLMs). We consider two settings: 1) Generic MatMul, where both matrices must be quantized (weight+activation quantization); and 2) weight-on…

• Gradient Regularized Natural Gradients

  Satya Prakash Dash, Hossein Abdi, Wei Pan, Samuel Kaski, Mingfei Sun · 27 janvier 2026

  Gradient regularization (GR) has been shown to improve the generalizability of trained models. While Natural Gradient Descent has been shown to accelerate optimization in the initial phase of training, little attention has been paid to how the training dynamics of second-order optimizers can benefit…

• Provably Learning Attention with Queries

  Satwik Bhattamishra, Kulin Shah, Michael Hahn, Varun Kanade · 26 janvier 2026

  We study the problem of learning Transformer-based sequence models with black-box access to their outputs. In this setting, a learner may adaptively query the oracle with any sequence of vectors and observe the corresponding real-valued output. We begin with the simplest case, a single-head softmax-…

• Multigrade Neural Network Approximation

  Shijun Zhang, Zuowei Shen, Yuesheng Xu · 26 janvier 2026

  We study multigrade deep learning (MGDL) as a principled framework for structured error refinement in deep neural networks. While the approximation power of neural networks is now relatively well understood, training very deep architectures remains challenging due to highly non-convex and often ill-…

• Learning to Optimize by Differentiable Programming

  Liping Tao, Xindi Tong, Chee Wei Tan · 26 janvier 2026

  Solving massive-scale optimization problems requires scalable first-order methods with low per-iteration cost. This tutorial highlights a shift in optimization: using differentiable programming not only to execute algorithms but to learn how to design them. Modern frameworks such as PyTorch, TensorF…

• Efficient Learning of Stationary Diffusions with Stein-type Discrepancies

  Fabian Bleile, Sarah Lumpp, Mathias Drton · 26 janvier 2026

  Learning a stationary diffusion amounts to estimating the parameters of a stochastic differential equation whose stationary distribution matches a target distribution. We build on the recently introduced kernel deviation from stationarity (KDS), which enforces stationarity by evaluating expectations…

• Kernel-Based Nonparametric Tests For Shape Constraints

  Rohan Sen · 26 janvier 2026

  We propose a kernel-based nonparametric framework for mean-variance optimization that enables inference on economically motivated shape constraints in finance, including positivity, monotonicity, and convexity. Many central hypotheses in financial econometrics are naturally expressed as shape relati…