Tootfinder

Stochastic gradient descent based variational inference for infinite-dimensional inverse problems
Jiaming Sui, Junxiong Jia, Jinglai Li
https://arxiv.org/abs/2506.08380

Stochastic gradient descent based variational inference for infinite-dimensional inverse problems
This paper introduces two variational inference approaches for infinite-dimensional inverse problems, developed through gradient descent with a constant learning rate. The proposed methods enable efficient approximate sampling from the target posterior distribution using a constant-rate stochastic gradient descent (cSGD) iteration. Specifically, we introduce a randomization strategy that incorporates stochastic gradient noise, allowing the cSGD iteration to be viewed as a discrete-time process.…

Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization
Pierre Vernimmen, Fran\c{c}ois Glineur
https://arxiv.org/abs/2506.09730

Empirical and computer-aided robustness analysis of long-step and accelerated methods in smooth convex optimization
This work assesses both empirically and theoretically, using the performance estimation methodology, how robust different first-order optimization methods are when subject to relative inexactness in their gradient computations. Relative inexactness occurs, for example, when compressing the gradient using fewer bits of information, which happens when dealing with large-scale problems on GPUs. Three major families of methods are analyzed: constant step gradient descent, long-step methods, and acc…

Gradient Similarity Surgery in Multi-Task Deep Learning
Thomas Borsani, Andrea Rosani, Giuseppe Nicosia, Giuseppe Di Fatta
https://arxiv.org/abs/2506.06130

Gradient Similarity Surgery in Multi-Task Deep Learning
The multi-task learning ($MTL$) paradigm aims to simultaneously learn multiple tasks within a single model capturing higher-level, more general hidden patterns that are shared by the tasks. In deep learning, a significant challenge in the backpropagation training process is the design of advanced optimisers to improve the convergence speed and stability of the gradient descent learning rule. In particular, in multi-task deep learning ($MTDL$) the multitude of tasks may generate potentially conf…

This https://arxiv.org/abs/2409.08469 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

Improved Finite-Particle Convergence Rates for Stein Variational Gradient Descent
We provide finite-particle convergence rates for the Stein Variational Gradient Descent (SVGD) algorithm in the Kernelized Stein Discrepancy ($\mathsf{KSD}$) and Wasserstein-2 metrics. Our key insight is that the time derivative of the relative entropy between the joint density of $N$ particle locations and the $N$-fold product target measure, starting from a regular initial distribution, splits into a dominant `negative part' proportional to $N$ times the expected $\mathsf{KSD}^2$ and a smalle…

Constrained Stein Variational Gradient Descent for Robot Perception, Planning, and Identification
Griffin Tabor, Tucker Hermans
https://arxiv.org/abs/2506.00589

Constrained Stein Variational Gradient Descent for Robot Perception, Planning, and Identification
Many core problems in robotics can be framed as constrained optimization problems. Often on these problems, the robotic system has uncertainty, or it would be advantageous to identify multiple high quality feasible solutions. To enable this, we present two novel frameworks for applying principles of constrained optimization to the new variational inference algorithm Stein variational gradient descent. Our general framework supports multiple types of constrained optimizers and can handle arbitra…

This https://arxiv.org/abs/2503.16398 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp estimates via large deviations
In this paper, we examine the time it takes for stochastic gradient descent (SGD) to reach the global minimum of a general, non-convex loss function. We approach this question through the lens of randomly perturbed dynamical systems and large deviations theory, and we provide a tight characterization of the global convergence time of SGD via matching upper and lower bounds. These bounds are dominated by the most "costly" set of obstacles that the algorithm may need to overcome in order to reach…

This https://arxiv.org/abs/2504.14730 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csIT_…

Optimizing Noise Distributions for Differential Privacy
We propose a unified optimization framework for designing continuous and discrete noise distributions that ensure differential privacy (DP) by minimizing Rényi DP, a variant of DP, under a cost constraint. Rényi DP has the advantage that by considering different values of the Rényi parameter $α$, we can tailor our optimization for any number of compositions. To solve the optimization problem, we reduce it to a finite-dimensional convex formulation and perform preconditioned gradient descent…

This month's newsletter/digest is on it's way to the email box of all the amazing friendly good people who asked for it.
The rest of you bitchy vicious augmentative people in public spats can read it here:
#newsletter #digest

This https://arxiv.org/abs/2503.14353 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_ees…

Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework
The decentralized gradient descent (DGD) algorithm, and its sibling, diffusion, are workhorses in decentralized machine learning, distributed inference and estimation, and multi-agent coordination. We propose a novel, principled framework for the analysis of DGD and diffusion for strongly convex, smooth objectives, and arbitrary undirected topologies, using contraction mappings coupled with a result called the mean Hessian theorem (MHT). The use of these tools yields tight convergence bounds, b…

Stochastic Gradient-Descent Calibration of Pyragas Delayed-Feedback Control for Chaos Suppression in the Sprott Circuit
Adib Kabir, Onil Morshed, Oishi Kabir
https://arxiv.org/abs/2506.06639

Stochastic Gradient-Descent Calibration of Pyragas Delayed-Feedback Control for Chaos Suppression in the Sprott Circuit
This paper investigates chaos control in the Sprott circuit, a minimal electronic system exhibiting complex nonlinear dynamics. Using the third-order nonlinear differential equation from Kaveh Merat paper, we model the circuit and implement delayed feedback control to suppress chaos. Experimental voltage data were extracted from published figures via WebPlotDigitizer. Then we explore two calibration techniques: Minimizing sum of squared errors (SSE), and stochastic gradient descent (SGD) with f…

Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness
Thomas Pethick, Wanyun Xie, Mete Erdogan, Kimon Antonakopoulos, Tony Silveti-Falls, Volkan Cevher
https://arxiv.org/abs/2506.01913

Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness
This work introduces a hybrid non-Euclidean optimization method which generalizes gradient norm clipping by combining steepest descent and conditional gradient approaches. The method achieves the best of both worlds by establishing a descent property under a generalized notion of ($L_0$,$L_1$)-smoothness. Weight decay is incorporated in a principled manner by identifying a connection to the Frank-Wolfe short step. In the stochastic case, we show an order optimal $O(n^{-1/4})$ convergence rate b…

Decentralized Optimization with Amplified Privacy via Efficient Communication
Wei Huo, Changxin Liu, Kemi Ding, Karl Henrik Johansson, Ling Shi
https://arxiv.org/abs/2506.07102

Decentralized Optimization with Amplified Privacy via Efficient Communication
Decentralized optimization is crucial for multi-agent systems, with significant concerns about communication efficiency and privacy. This paper explores the role of efficient communication in decentralized stochastic gradient descent algorithms for enhancing privacy preservation. We develop a novel algorithm that incorporates two key features: random agent activation and sparsified communication. Utilizing differential privacy, we demonstrate that these features reduce noise without sacrificing…

Can Biologically Plausible Temporal Credit Assignment Rules Match BPTT for Neural Similarity? E-prop as an Example
Yuhan Helena Liu, Guangyu Robert Yang, Christopher J. Cueva
https://arxiv.org/abs/2506.06904

Can Biologically Plausible Temporal Credit Assignment Rules Match BPTT for Neural Similarity? E-prop as an Example
Understanding how the brain learns may be informed by studying biologically plausible learning rules. These rules, often approximating gradient descent learning to respect biological constraints such as locality, must meet two critical criteria to be considered an appropriate brain model: (1) good neuroscience task performance and (2) alignment with neural recordings. While extensive research has assessed the first criterion, the second remains underexamined. Employing methods such as Procruste…

Multilevel Stochastic Gradient Descent for Optimal Control Under Uncertainty
Niklas Baumgarten, David Schneiderhan
https://arxiv.org/abs/2506.02647 https:/…

Multilevel Stochastic Gradient Descent for Optimal Control Under Uncertainty
We present a multilevel stochastic gradient descent method for the optimal control of systems governed by partial differential equations under uncertain input data. The gradient descent method used to find the optimal control leverages a parallel multilevel Monte Carlo method as stochastic gradient estimator. As a result, we achieve precise control over the stochastic gradient's bias, introduced by numerical approximation, and its sampling error, arising from the use of incomplete gradients, wh…

Linear Discriminant Analysis with Gradient Optimization on Covariance Inverse
Cencheng Shen, Yuexiao Dong
https://arxiv.org/abs/2506.06845 https://

Linear Discriminant Analysis with Gradient Optimization on Covariance Inverse
Linear discriminant analysis (LDA) is a fundamental method in statistical pattern recognition and classification, achieving Bayes optimality under Gaussian assumptions. However, it is well-known that classical LDA may struggle in high-dimensional settings due to instability in covariance estimation. In this work, we propose LDA with gradient optimization (LDA-GO), a new approach that directly optimizes the inverse covariance matrix via gradient descent. The algorithm parametrizes the inverse co…

This https://arxiv.org/abs/2505.17282 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_csLG_…

Attention with Trained Embeddings Provably Selects Important Tokens
Token embeddings play a crucial role in language modeling but, despite this practical relevance, their theoretical understanding remains limited. Our paper addresses the gap by characterizing the structure of embeddings obtained via gradient descent. Specifically, we consider a one-layer softmax attention model with a linear head for binary classification, i.e., $\texttt{Softmax}( p^\top E_X^\top ) E_X v = \frac{ \sum_{i=1}^T \exp(p^\top E_{x_i}) E_{x_i}^\top v}{\sum_{j=1}^T \exp(p^\top E_{x_{j…

This https://arxiv.org/abs/2502.03701 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

First-ish Order Methods: Hessian-aware Scalings of Gradient Descent
Gradient descent is the primary workhorse for optimizing large-scale problems in machine learning. However, its performance is highly sensitive to the choice of the learning rate. A key limitation of gradient descent is its lack of natural scaling, which often necessitates expensive line searches or heuristic tuning to determine an appropriate step size. In this paper, we address this limitation by incorporating Hessian information to scale the gradient direction. By accounting for the curvatur…

On the Benefits of Accelerated Optimization in Robust and Private Estimation
Laurentiu Andrei Marchis, Po-Ling Loh
https://arxiv.org/abs/2506.03044 https:/…

On the Benefits of Accelerated Optimization in Robust and Private Estimation
We study the advantages of accelerated gradient methods, specifically based on the Frank-Wolfe method and projected gradient descent, for privacy and heavy-tailed robustness. Our approaches are as follows: For the Frank-Wolfe method, our technique is based on a tailored learning rate and a uniform lower bound on the gradient of the $\ell_2$-norm over the constraint set. For accelerating projected gradient descent, we use the popular variant based on Nesterov's momentum, and we optimize our obje…

Multilevel Bregman Proximal Gradient Descent
Yara Elshiaty, Stefania Petra
https://arxiv.org/abs/2506.03950 https://arxiv.org/pdf/250…

Multilevel Bregman Proximal Gradient Descent
We present the Multilevel Bregman Proximal Gradient Descent (ML-BPGD) method, a novel multilevel optimization framework tailored to constrained convex problems with relative Lipschitz smoothness. Our approach extends the classical multilevel optimization framework (MGOPT) to handle Bregman-based geometries and constrained domains. We provide a rigorous analysis of ML BPGD for multiple coarse levels and establish a global linear convergence rate. We demonstrate the effectiveness of ML BPGD in th…

Antenna Q-Factor Topology Optimization with Auxiliary Edge Resistivities
Stepan Bosak, Miloslav Capek, Jiri Matas
https://arxiv.org/abs/2506.00595 https://…

Antenna Q-Factor Topology Optimization with Auxiliary Edge Resistivities
This paper presents a novel bi-level topology optimization strategy within the method-of-moments paradigm. The proposed approach utilizes an auxiliary variables called edge resistivities related to the Rao-Wilton-Glisson method-of-moments basis functions, for a definition of a fast local optimization algorithm. The local algorithm combines automatic differentiation with adaptive gradient descent. A Bayesian optimization scheme is applied on top of the local algorithm to search for an optimum po…

Emergent universal long-range structure in random-organizing systems
Satyam Anand, Guanming Zhang, Stefano Martiniani
https://arxiv.org/abs/2505.22933 http…

Emergent universal long-range structure in random-organizing systems
Self-organization through noisy interactions is ubiquitous across physics, mathematics, and machine learning, yet how long-range structure emerges from local noisy dynamics remains poorly understood. Here, we investigate three paradigmatic random-organizing particle systems drawn from distinct domains: models from soft matter physics (random organization, biased random organization) and machine learning (stochastic gradient descent), each characterized by distinct sources of noise. We discover …

This https://arxiv.org/abs/2502.16492 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions
We study stochastic gradient descent (SGD) with gradient clipping on convex functions under a generalized smoothness assumption called $(L_0,L_1)$-smoothness. Using gradient clipping, we establish a high probability convergence rate that matches the SGD rate in the $L$ smooth case up to polylogarithmic factors and additive terms. We also propose a variation of adaptive SGD with gradient clipping, which achieves the same guarantee. We perform empirical experiments to examine our theory and algor…

A Proximal Variable Smoothing for Minimization of Nonlinearly Composite Nonsmooth Function -- Maxmin Dispersion and MIMO Applications
Keita Kume, Isao Yamada
https://arxiv.org/abs/2506.05974

A Proximal Variable Smoothing for Minimization of Nonlinearly Composite Nonsmooth Function -- Maxmin Dispersion and MIMO Applications
We propose a proximal variable smoothing algorithm for a nonsmooth optimization problem whose cost function is the sum of three functions including a weakly convex composite function. The proposed algorithm has a single-loop structure inspired by a proximal gradient-type method. More precisely, the proposed algorithm consists of two steps: (i) a gradient descent of a time-varying smoothed surrogate function designed partially with the Moreau envelope of the weakly convex function; (ii) an appli…

This https://arxiv.org/abs/2505.08408 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

A three-term Polak-Ribière-Polyak conjugate gradient method for vector optimization
A three-term Polak-Ribière-Polyak conjugate gradient method is first proposed in this paper for solving vector optimization problems. This method can autonomously generate descent directions independent of line search procedures, while retaining the conjugate property. The global convergence of the proposed scheme is established by the generalized Wolfe line search procedure without self-adjusting strategies, regular restarts and convexity assumptions. Finally, numerical experiments illustrati…

This https://arxiv.org/abs/2505.08408 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

A three-term Polak-Ribière-Polyak conjugate gradient method for vector optimization
A three-term Polak-Ribière-Polyak conjugate gradient method is first proposed in this paper for solving vector optimization problems. This method can autonomously generate descent directions independent of line search procedures, while retaining the conjugate property. The global convergence of the proposed scheme is established by the generalized Wolfe line search procedure without self-adjusting strategies, regular restarts and convexity assumptions. Finally, numerical experiments illustrati…

This https://arxiv.org/abs/2401.06738 has been replaced.
initial toot: https://mastoxiv.page/@arXiv_mat…

(Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum
Stochastic heavy ball momentum (SHB) is commonly used to train machine learning models, and often provides empirical improvements over stochastic gradient descent. By primarily focusing on strongly-convex quadratics, we aim to better understand the theoretical advantage of SHB and subsequently improve the method. For strongly-convex quadratics, Kidambi et al. (2018) show that SHB (with a mini-batch of size $1$) cannot attain accelerated convergence, and hence has no theoretical benefit over SGD…