106 citations · 499 across the 45 of their papers we have counts for
26 papers · 1 filter
DIGing--SGLD: Decentralized and Scalable Langevin Sampling over Time--Varying Networks
Waheed U. Bajwa, Mert Gurbuzbalaban, Mustafa Ali Kutbay +2
Sampling from a target distribution induced by training data is central to Bayesian learning, with Stochastic Gradient Langevin Dynamics (SGLD) serving as a key tool for scalable p…
Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds
Mert Gürbüzbalaban, Yasa Syed, Necdet Serhat Aybat
We study trade-offs between convergence rate and robustness to gradient errors in the context of first-order methods. Our focus is on generalized momentum methods (GMMs)--a broad c…
Robustly Stable Accelerated Momentum Methods With A Near-Optimal L2 Gain and Performance
Mert Gurbuzbalaban
We consider the problem of minimizing a strongly convex smooth function where the gradients are subject to additive worst-case deterministic errors that are square-summable. We stu…
Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima
Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. Bajwa
This paper considers the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that…
High Probability and Risk-Averse Guarantees for a Stochastic Accelerated Primal-Dual Method
Yassine Laguel, Necdet Serhat Aybat, Mert Gürbüzbalaban
We consider stochastic strongly-convex-strongly-concave (SCSC) saddle point (SP) problems which frequently arise in applications ranging from distributionally robust learning to ga…
SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problems
Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban
We propose a new stochastic method SAPD+ for solving nonconvex-concave minimax problems of the form , where are closed convex and $…
Entropic Risk-Averse Generalized Momentum Methods
Bugra Can, Mert Gürbüzbalaban
In the context of first-order algorithms subject to random gradient noise, we study the trade-offs between the convergence rate (which quantifies how fast the initial conditions ar…
A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm
Bugra Can, Mert Gurbuzbalaban, Necdet Serhat Aybat
In this work, we consider strongly convex strongly concave (SCSC) saddle point (SP) problems where is -smooth,…
Robust Accelerated Primal-Dual Methods for Computing Saddle Points
Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban
We consider strongly-convex-strongly-concave saddle point problems assuming we have access to unbiased stochastic estimates of the gradients. We propose a stochastic accelerated pr…
L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
Bugra Can, Saeed Soori, Maryam Mehri Dehnavi +1
This work proposes a distributed algorithm for solving empirical risk minimization problems, called L-DQN, under the master/worker communication model. L-DQN is a distributed limit…
Boundary Conditions for Linear Exit Time Gradient Trajectories Around Saddle Points: Analysis and Algorithm
Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. Bajwa
Gradient-related first-order methods have become the workhorse of large-scale numerical optimization problems. Many of these problems involve nonconvex objective functions with mul…
IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
Yossi Arjevani, Joan Bruna, Bugra Can +3
We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of ap…
A Stochastic Subgradient Method for Distributionally Robust Non-Convex Learning
Mert Gürbüzbalaban, Andrzej Ruszczyński, Landi Zhu
We consider a distributionally robust formulation of stochastic optimization problems arising in statistical learning, where robustness is with respect to uncertainty in the underl…
The Heavy-Tail Phenomenon in SGD
Mert Gurbuzbalaban, Umut Şimşekli, Lingjiong Zhu
In recent years, various notions of capacity and complexity have been proposed for characterizing the generalization properties of stochastic gradient descent (SGD) in deep learnin…
Randomized Gossiping with Effective Resistance Weights: Performance Guarantees and Applications
Bugra Can, Saeed Soori, Necdet Serhat Aybat +2
The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced when a unit current is injected at one node and extra…
A Universally Optimal Multistage Accelerated Stochastic Gradient Method
Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban +1
We study the problem of minimizing a strongly convex, smooth function when we have noisy estimates of its gradient. We propose a novel multistage accelerated algorithm that is univ…
Breaking Reversibility Accelerates Langevin Dynamics for Global Non-Convex Optimization
Xuefeng Gao, Mert Gurbuzbalaban, Lingjiong Zhu
Langevin dynamics (LD) has been proven to be a powerful technique for optimizing a non-convex objective as an efficient algorithm to find local minima while eventually visiting a g…
Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
Xuefeng Gao, Mert Gürbüzbalaban, Lingjiong Zhu
Stochastic gradient Hamiltonian Monte Carlo (SGHMC) is a variant of stochastic gradient with momentum where a controlled and properly scaled Gaussian noise is added to the stochast…
Robust Accelerated Gradient Methods for Smooth Strongly Convex Functions
Necdet Serhat Aybat, Alireza Fallah, Mert Gurbuzbalaban +1
We study the trade-offs between convergence rate and robustness to gradient errors in designing a first-order algorithm. We focus on gradient descent (GD) and accelerated gradient…
Decentralized Computation of Effective Resistances and Acceleration of Consensus Algorithms
Necdet Serhat Aybat, Mert Gurbuzbalaban
The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the f…
Approximating the Real Structured Stability Radius with Frobenius Norm Bounded Perturbations
Nicola Guglielmi, Mert Gurbuzbalaban, Tim Mitchell +1
We propose a fast method to approximate the real stability radius of a linear dynamical system with output feedback, where the perturbations are restricted to be real valued and bo…
Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate
Aryan Mokhtari, Mert Gürbüzbalaban, Alejandro Ribeiro
Recently, there has been growing interest in developing optimization methods for solving large-scale machine learning problems. Most of these problems boil down to the problem of m…
Convergence Rate of Incremental Gradient and Newton Methods
Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo Parrilo
The incremental gradient method is a prominent algorithm for minimizing a finite sum of smooth convex functions, used in many contexts including large-scale data processing applica…
Why Random Reshuffling Beats Stochastic Gradient Descent
Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo Parrilo
We analyze the convergence rate of the random reshuffling (RR) method, which is a randomized first-order incremental algorithm for minimizing a finite sum of convex component funct…