Publications

74 works in optimization, machine learning, and applied probability. Search by title, co-author, or venue; filter by topic, year, or type; expand summaries where available; and copy BibTeX for any entry.

Type

TopicYear

74 items — 34 journal articles, 29 conference papers, 11 preprints.

2026

Found. Comput. Math.Journal

Accelerated gradient methods for nonconvex optimization: escape trajectories from strict saddle points and convergence to local minima

Rishabh Dixit, Mert Gürbüzbalaban, Waheed U. Bajwa

Foundations of Computational Mathematics, 2026.

DOI arXiv:2307.07030

Momentum methods are known to escape saddle points of non-convex functions, but how, and how fast? The paper analyzes the trajectories of a family of accelerated gradient methods near strict saddle points, characterizes the time they take to leave as a function of the local geometry, and shows that the methods converge to local minima — with an explicit account of the role the momentum parameter plays in both.

@article{dixit2026escape,
  title   = {Accelerated gradient methods for nonconvex optimization: escape trajectories from strict saddle points and convergence to local minima},
  author  = {Rishabh Dixit and Mert Gürbüzbalaban and Waheed U. Bajwa},
  year    = {2026},
  journal = {Foundations of Computational Mathematics},
  doi     = {10.1007/s10208-026-09745-x},
}

J. Nonlinear Var. Anal.Journal · selected

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

Journal of Nonlinear and Variational Analysis (special issue), 2026.

arXiv:2509.13628

Studies accelerated methods when gradient estimates are biased as well as noisy. Computes the risk-sensitive index of generalized momentum methods via a Riccati-equation reduction, characterizes when it blows up, and derives a large deviation principle whose rate function is the convex conjugate of that index — turning rare-event behavior of the running suboptimality into a designable quantity, with finite-time high-probability guarantees beyond quadratics.

@article{gurbuzbalaban2026biased,
  title   = {Accelerated gradient methods with biased gradient estimates: risk sensitivity, high-probability guarantees, and large deviation bounds},
  author  = {Mert Gürbüzbalaban and Yasa Syed and Necdet Serhat Aybat},
  year    = {2026},
  journal = {Journal of Nonlinear and Variational Analysis (special issue)},
  note    = {arXiv:2509.13628},
}

J. Nonlinear Var. Anal.Journal

An accelerated primal–dual algorithm with backtracking for decentralized constrained optimization

Qiushui Xu, Necdet Serhat Aybat, Mert Gürbüzbalaban

Journal of Nonlinear and Variational Analysis (special issue in honor of Yurii Nesterov), 10(3), pp. 555–596, 2026.

Paper

A primal–dual method for constrained problems whose data are spread over a network of agents, each holding its own objective and constraints and communicating only with neighbors. The method is accelerated, and a backtracking rule lets it find usable stepsizes on the fly instead of requiring the problem’s Lipschitz constants in advance, with convergence rates for the resulting decentralized iteration.

@article{xu2026backtracking,
  title   = {An accelerated primal–dual algorithm with backtracking for decentralized constrained optimization},
  author  = {Qiushui Xu and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2026},
  journal = {Journal of Nonlinear and Variational Analysis (special issue in honor of Yurii Nesterov)},
  volume  = {10(3)},
  pages   = {555--596},
  url     = {https://jnva.biemdas.com/issues/JNVA2026-3-4.pdf},
}

Math. Program.Journal

Mean-semideviation-based distributionally robust learning with weakly convex losses: convergence rates and finite-sample guarantees

Landi Zhu, Mert Gürbüzbalaban, Andrzej Ruszczyński

Mathematical Programming, 215(1), pp. 237–267, 2026.

DOI

Establishes convergence rates and finite-sample guarantees for distributionally robust learning formulated with mean–semideviation risk, for the broad class of weakly convex losses.

@article{zhu2026semideviation,
  title   = {Mean-semideviation-based distributionally robust learning with weakly convex losses: convergence rates and finite-sample guarantees},
  author  = {Landi Zhu and Mert Gürbüzbalaban and Andrzej Ruszczyński},
  year    = {2026},
  journal = {Mathematical Programming},
  volume  = {215(1)},
  pages   = {237--267},
  doi     = {10.1007/s10107-025-02218-z},
}

Trans. Mach. Learn. Res.Journal

RESIST: resilient decentralized learning using consensus gradient descent

Cheng Fang, Rishabh Dixit, Waheed U. Bajwa, Mert Gürbüzbalaban

Transactions on Machine Learning Research, 2026. Featured certification.

arXiv:2502.07977 OpenReview

Decentralized learning is vulnerable to man-in-the-middle attacks that alter the messages agents exchange. RESIST combines multi-step consensus gradient descent with robust-statistics screening of neighbors’ messages and converges exactly to the empirical risk minimizer — linearly for strongly convex and Polyak–Łojasiewicz problems, sublinearly for smooth non-convex ones — as long as the fraction of compromised links stays below the screening rule’s breakdown point.

@article{fang2025resist,
  title   = {RESIST: resilient decentralized learning using consensus gradient descent},
  author  = {Cheng Fang and Rishabh Dixit and Waheed U. Bajwa and Mert Gürbüzbalaban},
  year    = {2026},
  journal = {Transactions on Machine Learning Research},
  note    = {arXiv:2502.07977},
}

2025

arXivPreprint

Algorithmic stability of stochastic gradient descent with momentum under heavy-tailed noise

Thanh Dang, Melih Barsbey, A K. M. Rokonuzzaman Sonet, Mert Gürbüzbalaban, Umut Şimşekli, Lingjiong Zhu

arXiv preprint, 2025.

arXiv:2502.00885

Algorithmic stability — how much a trained model changes when one training example is replaced — controls generalization, and under heavy-tailed gradient noise it depends on the tail index. The paper extends this analysis from plain SGD to SGD with momentum, quantifying how the momentum parameter and the heaviness of the tails together govern stability and hence generalization.

@misc{dang2025stability,
  title   = {Algorithmic stability of stochastic gradient descent with momentum under heavy-tailed noise},
  author  = {Thanh Dang and Melih Barsbey and A K. M. Rokonuzzaman Sonet and Mert Gürbüzbalaban and Umut Şimşekli and Lingjiong Zhu},
  year    = {2025},
  howpublished = {arXiv preprint arXiv:2502.00885},
}

arXivPreprint

Anchored Langevin algorithms

Mert Gürbüzbalaban, Hoang M. Nguyen, Xicheng Zhang, Lingjiong Zhu

arXiv preprint, 2025.

arXiv:2509.19455

Standard Langevin samplers struggle with non-differentiable potentials (as in L1-regularized models) and explore heavy-tailed targets slowly, because the gradient vanishes far from the mode. Anchoring the sampler to a smooth reference potential, with a multiplicative correction that preserves the target, gives non-asymptotic guarantees without the bias of smoothing — and, with a logarithmic anchor, exponential convergence on heavy-tailed targets where standard Langevin algorithms are only sub-exponential.

@misc{gurbuzbalaban2025anchored,
  title   = {Anchored Langevin algorithms},
  author  = {Mert Gürbüzbalaban and Hoang M. Nguyen and Xicheng Zhang and Lingjiong Zhu},
  year    = {2025},
  howpublished = {arXiv preprint arXiv:2509.19455},
}

arXivPreprint

DIGing-SGLD: decentralized and scalable Langevin sampling over time-varying networks

Waheed U. Bajwa, Mert Gürbüzbalaban, Mustafa Ali Kutbay, Lingjiong Zhu, Muhammad Zulqarnain

arXiv preprint, 2025.

arXiv:2511.12836

Agents holding different parts of the data want to sample from the joint posterior without pooling it, over a network whose links change over time — a setting in which earlier decentralized Langevin methods drift away from the target. DIGing-SGLD adds gradient tracking, so each agent follows an estimate of the network-average gradient; this removes the network-induced bias and yields the first finite-time Wasserstein guarantees for time-varying networks, matching centralized rates.

@misc{bajwa2025diging,
  title   = {DIGing-SGLD: decentralized and scalable Langevin sampling over time-varying networks},
  author  = {Waheed U. Bajwa and Mert Gürbüzbalaban and Mustafa Ali Kutbay and Lingjiong Zhu and Muhammad Zulqarnain},
  year    = {2025},
  howpublished = {arXiv preprint arXiv:2511.12836},
}

Optim. Methods Softw.Journal · selected

Entropic risk-averse generalized momentum methods

Bugra Can, Mert Gürbüzbalaban

Optimization Methods and Software, 40(6), pp. 1535–1583, 2025.

DOI Code Note Playground

Builds a unified convergence and risk analysis for the generalized momentum family (covering gradient descent, heavy ball, and Nesterov acceleration) under stochastic gradient errors, bounding the entropic risk and entropic value-at-risk of suboptimality. The bounds support risk-averse parameter selection (RA-GMM): choosing step and momentum on the rate–risk Pareto frontier rather than for expected performance alone.

@article{can2025entropic,
  title   = {Entropic risk-averse generalized momentum methods},
  author  = {Bugra Can and Mert Gürbüzbalaban},
  year    = {2025},
  journal = {Optimization Methods and Software},
  volume  = {40(6)},
  pages   = {1535--1583},
  doi     = {10.1080/10556788.2025.2549356},
}

IISE Trans.Journal

Heavy-tail phenomenon in decentralized SGD

Mert Gürbüzbalaban, Yuanhan Hu, Umut Şimşekli, Kun Yuan, Lingjiong Zhu

IISE Transactions, 57(7), pp. 788–802, 2025.

arXiv:2205.06689 Code

Extends the heavy-tail theory of SGD to the decentralized setting, showing how network communication interacts with multiplicative gradient noise to shape the tail behavior of the iterates.

@article{gurbuzbalaban2025decentralizedheavytail,
  title   = {Heavy-tail phenomenon in decentralized SGD},
  author  = {Mert Gürbüzbalaban and Yuanhan Hu and Umut Şimşekli and Kun Yuan and Lingjiong Zhu},
  year    = {2025},
  journal = {IISE Transactions},
  volume  = {57(7)},
  pages   = {788--802},
  note    = {arXiv:2205.06689},
}

arXivPreprint

High-order Langevin Monte Carlo algorithms

Thanh Dang, Mert Gürbüzbalaban, Mohammad Rafiqul Islam, Nian Yao, Lingjiong Zhu

arXiv preprint, 2025.

arXiv:2508.17545

Underdamped (second-order) Langevin dynamics sample faster than overdamped ones; this paper goes further and discretizes P-th order Langevin dynamics for any P ≥ 3, combining splitting with accurate integration of the exactly solvable parts. The resulting samplers come with Wasserstein convergence guarantees for smooth log-concave targets, with a dependence on dimension and accuracy that improves as the order grows.

@misc{dang2025highorder,
  title   = {High-order Langevin Monte Carlo algorithms},
  author  = {Thanh Dang and Mert Gürbüzbalaban and Mohammad Rafiqul Islam and Nian Yao and Lingjiong Zhu},
  year    = {2025},
  howpublished = {arXiv preprint arXiv:2508.17545},
}

arXivPreprint

Rényi differential privacy for heavy-tailed SDEs via fractional Poincaré inequalities

Benjamin Dupuis, Mert Gürbüzbalaban, Umut Şimşekli, Jian Wang, Sinan Yıldırım, Lingjiong Zhu

arXiv preprint, 2025.

arXiv:2511.15634

Injecting heavy-tailed rather than Gaussian noise into gradient-based training changes its privacy properties. Working with the heavy-tailed stochastic differential equations that describe such algorithms in continuous time, the paper derives Rényi differential-privacy guarantees through fractional Poincaré inequalities, extending privacy analysis beyond the Gaussian mechanism.

@misc{dupuis2025renyi,
  title   = {Rényi differential privacy for heavy-tailed SDEs via fractional Poincaré inequalities},
  author  = {Benjamin Dupuis and Mert Gürbüzbalaban and Umut Şimşekli and Jian Wang and Sinan Yıldırım and Lingjiong Zhu},
  year    = {2025},
  howpublished = {arXiv preprint arXiv:2511.15634},
}

Math. Oper. Res.Journal · selected

Robustly stable accelerated momentum methods with a near-optimal L₂ gain and H∞ performance

Mert Gürbüzbalaban

Mathematics of Operations Research, 2025. Dedicated to Michael L. Overton.

DOI Note Playground

Treats first-order algorithms as feedback dynamical systems subject to worst-case, finite-energy gradient errors and computes their H∞ norm in closed form on quadratics — together with the explicit worst-case noise achieving it (a decaying cosine). Introduces robustly stable variants (RS-GD, RS-HB) with near-optimal L₂ gain, quantifies real stability radii of momentum methods, and extends the guarantees beyond quadratics through matrix-inequality certificates.

@article{gurbuzbalaban2025hinf,
  title   = {Robustly stable accelerated momentum methods with a near-optimal {$L_2$} gain and {$H_\infty$} performance},
  author  = {Mert Gürbüzbalaban},
  year    = {2025},
  journal = {Mathematics of Operations Research},
  doi     = {10.1287/moor.2023.0321},
}

2024

arXivPreprint

A stochastic GDA method with backtracking for solving nonconvex (strongly) concave minimax problems

Qiushui Xu, Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

arXiv preprint, 2024.

arXiv:2403.07806

Gradient descent-ascent for minimax problems that are non-convex in the minimizing variable and concave or strongly concave in the maximizing one, with stochastic gradients and a backtracking rule that adapts the stepsizes to the local smoothness instead of requiring it to be known; the paper establishes oracle-complexity guarantees for the resulting method.

@misc{xu2024gda,
  title   = {A stochastic GDA method with backtracking for solving nonconvex (strongly) concave minimax problems},
  author  = {Qiushui Xu and Xuan Zhang and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2024},
  howpublished = {arXiv preprint arXiv:2403.07806},
}

arXivPreprint

Differential privacy of noisy (S)GD under heavy-tailed perturbations

Umut Şimşekli, Mert Gürbüzbalaban, Sinan Yıldırım, Lingjiong Zhu

arXiv preprint, 2024.

arXiv:2403.02051

Differential privacy is usually obtained by adding Gaussian noise to gradients; this paper asks what happens when the noise is heavy-tailed instead, as it naturally is in SGD. It establishes differential-privacy guarantees for noisy (stochastic) gradient descent under heavy-tailed perturbations and works out the resulting privacy–utility trade-off.

@misc{simsekli2024dp,
  title   = {Differential privacy of noisy (S)GD under heavy-tailed perturbations},
  author  = {Umut Şimşekli and Mert Gürbüzbalaban and Sinan Yıldırım and Lingjiong Zhu},
  year    = {2024},
  howpublished = {arXiv preprint arXiv:2403.02051},
}

arXivPreprint

Generalized EXTRA stochastic gradient Langevin dynamics

Mert Gürbüzbalaban, Mohammad Rafiqul Islam, Xiaoyu Wang, Lingjiong Zhu

arXiv preprint, 2024.

arXiv:2412.01993

Decentralized stochastic gradient Langevin dynamics lets agents sample a posterior over a network without sharing data, but network effects bias the samples, most visibly with full-batch gradients. Borrowing the EXTRA correction from decentralized optimization removes that bias: the method converges to the target posterior in 2-Wasserstein distance under strong convexity and smoothness, and outperforms plain decentralized SGLD when communication is constrained.

@misc{gurbuzbalaban2024extra,
  title   = {Generalized EXTRA stochastic gradient Langevin dynamics},
  author  = {Mert Gürbüzbalaban and Mohammad Rafiqul Islam and Xiaoyu Wang and Lingjiong Zhu},
  year    = {2024},
  howpublished = {arXiv preprint arXiv:2412.01993},
}

J. Mach. Learn. Res.Journal

High probability and risk-averse guarantees for a stochastic accelerated primal-dual method

Yassine Laguel, Necdet Serhat Aybat, Mert Gürbüzbalaban

Journal of Machine Learning Research, 25(421), pp. 1–56, 2024.

Paper Note Playground

Stochastic accelerated primal–dual methods are usually analyzed in expectation; this paper gives high-probability bounds on the distance to the saddle point, together with risk-averse (entropic value-at-risk) guarantees that control the tail of the error distribution. The analysis covers strongly convex–strongly concave problems with light-tailed gradient noise and shows how the step-sizes trade off speed against the size of the tails.

@article{laguel2024sapd,
  title   = {High probability and risk-averse guarantees for a stochastic accelerated primal-dual method},
  author  = {Yassine Laguel and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2024},
  journal = {Journal of Machine Learning Research},
  volume  = {25(421)},
  pages   = {1--56},
  url     = {https://jmlr.org/papers/v25/23-0864.html},
}

NeurIPSConference

High-probability complexity bounds for stochastic non-convex minimax optimization

Yassine Laguel, Yasa Syed, Necdet Serhat Aybat, Mert Gürbüzbalaban

Advances in Neural Information Processing Systems (NeurIPS), 2024.

Paper

For stochastic non-convex minimax problems — the structure behind adversarial training and distributionally robust learning — the paper establishes complexity bounds that hold with high probability rather than only in expectation. The guarantees are for computing approximate stationary points with a stochastic accelerated primal–dual method, so that a single run, not just the average run, comes with a performance certificate.

@inproceedings{laguel2024minimax,
  title   = {High-probability complexity bounds for stochastic non-convex minimax optimization},
  author  = {Yassine Laguel and Yasa Syed and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2024},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {http://papers.nips.cc/paper_files/paper/2024/hash/fec946957ce1af51a61e8f2d851ac98f-Abstract-Conference.html},
}

J. Mach. Learn. Res.Journal

Penalized overdamped and underdamped Langevin Monte Carlo algorithms for constrained sampling

Mert Gürbüzbalaban, Yuanhan Hu, Lingjiong Zhu

Journal of Machine Learning Research, 25(263), pp. 1–67, 2024.

Paper Code

Develops penalty-based overdamped and underdamped Langevin Monte Carlo methods for sampling from distributions supported on constraint sets, with non-asymptotic performance guarantees.

@article{gurbuzbalaban2024constrained,
  title   = {Penalized overdamped and underdamped Langevin Monte Carlo algorithms for constrained sampling},
  author  = {Mert Gürbüzbalaban and Yuanhan Hu and Lingjiong Zhu},
  year    = {2024},
  journal = {Journal of Machine Learning Research},
  volume  = {25(263)},
  pages   = {1--67},
  url     = {https://jmlr.org/papers/v25/22-1443.html},
}

SIAM J. Optim.Journal

Robust accelerated primal-dual methods for computing saddle points

Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

SIAM Journal on Optimization, 34(1), pp. 1097–1130, 2024.

DOI Note Playground

Accelerated primal–dual methods solve saddle-point problems quickly but, like momentum methods, amplify gradient errors. For strongly convex–strongly concave problems the paper quantifies that amplification as a robustness measure, computes it for the accelerated primal–dual family, and shows how to choose parameters on the speed–robustness frontier — the saddle-point counterpart of the trade-off for momentum methods.

@article{zhang2024rapd,
  title   = {Robust accelerated primal-dual methods for computing saddle points},
  author  = {Xuan Zhang and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2024},
  journal = {SIAM Journal on Optimization},
  volume  = {34(1)},
  pages   = {1097--1130},
  doi     = {10.1137/21M1462775},
}

2023

arXivPreprint

A variance-reduced stochastic accelerated primal–dual algorithm

Bugra Can, Mert Gürbüzbalaban, Necdet Serhat Aybat

arXiv preprint, 2023.

arXiv:2202.09688

Combines the stochastic accelerated primal–dual method with variance reduction for strongly-convex–strongly-concave saddle-point problems of finite-sum form, so that the noise of stochastic gradients no longer caps the accuracy: the method converges linearly to the saddle point, with a rate that reflects both the acceleration and the variance reduction.

@misc{can2023vrsapd,
  title   = {A variance-reduced stochastic accelerated primal–dual algorithm},
  author  = {Bugra Can and Mert Gürbüzbalaban and Necdet Serhat Aybat},
  year    = {2023},
  howpublished = {arXiv preprint arXiv:2202.09688},
}

ICMLConference

Algorithmic stability of heavy-tailed SGD with general loss functions

Anant Raj, Lingjiong Zhu, Mert Gürbüzbalaban, Umut Şimşekli

International Conference on Machine Learning (ICML), pp. 28578–28597, 2023.

Paper arXiv:2301.11885

Extends the heavy-tailed stability analysis from least squares to general, non-convex loss functions by modeling SGD with a heavy-tailed stochastic differential equation. It derives algorithmic-stability bounds in terms of the tail index and the loss geometry, giving generalization bounds that depend on the tails rather than only on the number of iterations.

@inproceedings{raj2023general,
  title   = {Algorithmic stability of heavy-tailed SGD with general loss functions},
  author  = {Anant Raj and Lingjiong Zhu and Mert Gürbüzbalaban and Umut Şimşekli},
  year    = {2023},
  booktitle = {International Conference on Machine Learning (ICML)},
  pages   = {28578--28597},
  url     = {https://proceedings.mlr.press/v202/raj23a.html},
  note    = {arXiv:2301.11885},
}

ALTConference

Algorithmic stability of heavy-tailed stochastic gradient descent on least squares

Anant Raj, Melih Barsbey, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Şimşekli

Algorithmic Learning Theory (ALT), pp. 1292–1342, 2023.

Paper arXiv:2206.01274

On least-squares problems SGD’s iterates can become heavy-tailed, and here everything is explicit enough to compute how that affects algorithmic stability. The paper derives stability bounds as a function of the tail index of the iterates and, since stability governs generalization, links the tail behavior of SGD directly to how well it generalizes.

@inproceedings{raj2023leastsquares,
  title   = {Algorithmic stability of heavy-tailed stochastic gradient descent on least squares},
  author  = {Anant Raj and Melih Barsbey and Mert Gürbüzbalaban and Lingjiong Zhu and Umut Şimşekli},
  year    = {2023},
  booktitle = {Algorithmic Learning Theory (ALT)},
  pages   = {1292--1342},
  url     = {https://proceedings.mlr.press/v201/raj23a.html},
  note    = {arXiv:2206.01274},
}

IEEE Trans. Inf. TheoryJournal

Boundary conditions for linear exit time gradient trajectories around saddle points: analysis and algorithm

Rishabh Dixit, Mert Gürbüzbalaban, Waheed U. Bajwa

IEEE Transactions on Information Theory, 69(4), pp. 2556–2602, 2023.

DOI

Gradient descent can linger for a long time near saddle points of non-convex losses. The paper characterizes the initial conditions — boundary conditions — under which gradient trajectories leave a saddle neighborhood in linear time, and uses that analysis to design a method with linear exit-time guarantees.

@article{dixit2023saddle,
  title   = {Boundary conditions for linear exit time gradient trajectories around saddle points: analysis and algorithm},
  author  = {Rishabh Dixit and Mert Gürbüzbalaban and Waheed U. Bajwa},
  year    = {2023},
  journal = {IEEE Transactions on Information Theory},
  volume  = {69(4)},
  pages   = {2556--2602},
  doi     = {10.1109/TIT.2022.3213607},
}

Trans. Mach. Learn. Res.Journal

Cyclic and randomized stepsizes invoke heavier tails in SGD than constant stepsize

Mert Gürbüzbalaban, Yuanhan Hu, Umut Şimşekli, Lingjiong Zhu

Transactions on Machine Learning Research, 2023.

arXiv:2302.05516 Code OpenReview

A constant step-size already makes SGD’s iterates heavy-tailed; this paper shows that cyclic and randomized step-size schedules make them heavier still, with an explicit characterization of the tail index on quadratic problems. The schedule itself, not only the step-size-to-batch-size ratio, therefore shapes the tail behavior — and hence the solutions SGD tends to find.

@article{gurbuzbalaban2023cyclic,
  title   = {Cyclic and randomized stepsizes invoke heavier tails in SGD than constant stepsize},
  author  = {Mert Gürbüzbalaban and Yuanhan Hu and Umut Şimşekli and Lingjiong Zhu},
  year    = {2023},
  journal = {Transactions on Machine Learning Research},
  note    = {arXiv:2302.05516},
}

Inf. InferenceJournal

Exit time analysis for approximations of gradient descent trajectories around saddle points

Rishabh Dixit, Mert Gürbüzbalaban, Waheed U. Bajwa

Information and Inference: A Journal of the IMA, 12(2), pp. 714–786, 2023.

Paper arXiv:2006.01106

How long does gradient descent linger near a saddle point before it leaves? The paper approximates the trajectory of gradient descent around a strict saddle, derives the exit time of the approximation together with bounds on how far the true trajectory can stray from it, and turns the analysis into estimates of the time gradient descent spends in the neighborhood of saddle points on non-convex problems.

@article{dixit2023exittime,
  title   = {Exit time analysis for approximations of gradient descent trajectories around saddle points},
  author  = {Rishabh Dixit and Mert Gürbüzbalaban and Waheed U. Bajwa},
  year    = {2023},
  journal = {Information and Inference: A Journal of the IMA},
  volume  = {12(2)},
  pages   = {714--786},
  url     = {https://academic.oup.com/imaiai/article-abstract/12/2/714/6835006},
  note    = {arXiv:2006.01106},
}

arXivPreprint

Non-convex optimization via non-reversible stochastic gradient Langevin dynamics

Yuanhan Hu, Xiaoyu Wang, Xuefeng Gao, Mert Gürbüzbalaban, Lingjiong Zhu

arXiv preprint, 2023.

arXiv:2004.02823

Takes the non-reversible Langevin idea to the stochastic-gradient setting: a non-reversible drift added to stochastic gradient Langevin dynamics leaves the target distribution unchanged while speeding up both sampling and non-convex optimization, and the paper quantifies the improvement in the convergence guarantees and the generalization bounds of the solutions found.

@misc{hu2023nonreversible,
  title   = {Non-convex optimization via non-reversible stochastic gradient Langevin dynamics},
  author  = {Yuanhan Hu and Xiaoyu Wang and Xuefeng Gao and Mert Gürbüzbalaban and Lingjiong Zhu},
  year    = {2023},
  howpublished = {arXiv preprint arXiv:2004.02823},
}

NeurIPSConference

Uniform-in-time Wasserstein stability bounds for (noisy) stochastic gradient descent

Lingjiong Zhu, Mert Gürbüzbalaban, Anant Raj, Umut Şimşekli

Advances in Neural Information Processing Systems (NeurIPS), 2023.

Paper arXiv:2305.12056

Stability bounds for SGD usually degrade as training runs longer; this paper proves Wasserstein stability bounds for (noisy) SGD that are uniform in time, so they do not grow with the number of iterations. The key is to view the iterates as a Markov chain and exploit its contraction properties, which yields time-uniform generalization bounds in convex and non-convex settings.

@inproceedings{zhu2023wasserstein,
  title   = {Uniform-in-time Wasserstein stability bounds for (noisy) stochastic gradient descent},
  author  = {Lingjiong Zhu and Mert Gürbüzbalaban and Anant Raj and Umut Şimşekli},
  year    = {2023},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {http://papers.nips.cc/paper_files/paper/2023/hash/05d6b5b6901fb57d2c287e1d3ce6d63c-Abstract-Conference.html},
  note    = {arXiv:2305.12056},
}

2022

J. Optim. Theory Appl.Journal

A stochastic subgradient method for distributionally robust non-convex and non-smooth learning

Mert Gürbüzbalaban, Andrzej Ruszczyński, Landi Zhu

Journal of Optimization Theory and Applications, 194(3), pp. 1014–1041, 2022.

DOI arXiv:2006.04873

Formulates statistical learning robust to perturbations of the data distribution using mean–semideviation risk, and develops a stochastic subgradient method for generalized-differentiable losses that may be non-convex and non-smooth — the first with rigorous convergence guarantees in this setting — achieving any desired robustness level at little extra cost over population risk minimization.

@article{gurbuzbalaban2022subgradient,
  title   = {A stochastic subgradient method for distributionally robust non-convex and non-smooth learning},
  author  = {Mert Gürbüzbalaban and Andrzej Ruszczyński and Landi Zhu},
  year    = {2022},
  journal = {Journal of Optimization Theory and Applications},
  volume  = {194(3)},
  pages   = {1014--1041},
  doi     = {10.1007/s10957-022-02063-6},
}

SIAM J. Optim.Journal

Differentially private accelerated optimization algorithms

Nurdan Kuru, Ş. İlker Birbil, Mert Gürbüzbalaban, Sinan Yıldırım

SIAM Journal on Optimization, 32(2), pp. 795–821, 2022.

DOI arXiv:2008.01989

Differentially private versions of the accelerated first-order methods. A smoothing approach keeps the privacy noise injected into heavy-ball iterations from accumulating, and a noise-dividing mechanism does the same for Nesterov’s method and its multistage variant; dynamical-systems analysis gives convergence rates for both, showing that acceleration survives the privacy constraint and improves the utility achievable at a given privacy budget.

@article{kuru2022dp,
  title   = {Differentially private accelerated optimization algorithms},
  author  = {Nurdan Kuru and Ş. İlker Birbil and Mert Gürbüzbalaban and Sinan Yıldırım},
  year    = {2022},
  journal = {SIAM Journal on Optimization},
  volume  = {32(2)},
  pages   = {795--821},
  doi     = {10.1137/20M1355847},
}

Oper. Res.Journal · selected

Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration

Xuefeng Gao, Mert Gürbüzbalaban, Lingjiong Zhu

Operations Research, 70(5), pp. 2931–2947, 2022.

DOI arXiv:1809.04618

Provides non-asymptotic global convergence guarantees for stochastic gradient Hamiltonian Monte Carlo on non-convex problems, quantifying when and how momentum accelerates Langevin-based optimization.

@article{gao2022sghmc,
  title   = {Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration},
  author  = {Xuefeng Gao and Mert Gürbüzbalaban and Lingjiong Zhu},
  year    = {2022},
  journal = {Operations Research},
  volume  = {70(5)},
  pages   = {2931--2947},
  doi     = {10.1287/opre.2021.2162},
}

SCConference

HyLo: a hybrid low-rank natural gradient descent method

Baorun Mu, Saeed Soori, Bugra Can, Mert Gürbüzbalaban, Maryam Mehri Dehnavi

International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2022.

DOI

A practical natural-gradient method for training large networks on many GPUs. HyLo keeps two Khatri–Rao-based low-rank approximations of the Fisher information — one more accurate, one cheaper — and a gradient-based rule for switching between them, so the curvature information that makes natural gradient converge in fewer iterations no longer costs more time than it saves. It converges 1.4–2.1× faster than the state-of-the-art distributed implementation of KFAC, with up to 350× less computation and 10.7× less communication on ResNet-50.

@inproceedings{mu2022hylo,
  title   = {HyLo: a hybrid low-rank natural gradient descent method},
  author  = {Baorun Mu and Saeed Soori and Bugra Can and Mert Gürbüzbalaban and Maryam Mehri Dehnavi},
  year    = {2022},
  booktitle = {International Conference for High Performance Computing, Networking, Storage and Analysis (SC)},
  doi     = {10.1109/SC41404.2022.00052},
}

IEEE Trans. Control Netw. Syst.Journal

Randomized gossiping with effective resistance weights: performance guarantees and applications

Bugra Can, Saeed Soori, Necdet Serhat Aybat, Maryam Mehri Dehnavi, Mert Gürbüzbalaban

IEEE Transactions on Control of Network Systems, 9(2), pp. 524–536, 2022.

DOI Code

Asks how to pick which pair of neighbors should average their values in randomized gossip. Choosing edges with probability proportional to their effective resistance — a quantity that measures how much an edge matters for connectivity — comes with convergence-rate guarantees that improve on uniform gossip, markedly so on poorly connected graphs, and the scheme plugs into decentralized optimization algorithms whose communication step is gossip.

@article{can2022gossiping,
  title   = {Randomized gossiping with effective resistance weights: performance guarantees and applications},
  author  = {Bugra Can and Saeed Soori and Necdet Serhat Aybat and Maryam Mehri Dehnavi and Mert Gürbüzbalaban},
  year    = {2022},
  journal = {IEEE Transactions on Control of Network Systems},
  volume  = {9(2)},
  pages   = {524--536},
  doi     = {10.1109/TCNS.2022.3161201},
}

J. Mach. Learn. Res.Journal

Robust distributed accelerated stochastic gradient methods for multi-agent networks

Alireza Fallah, Mert Gürbüzbalaban, Asuman Ozdaglar, Umut Şimşekli, Lingjiong Zhu

Journal of Machine Learning Research, 23(220), pp. 1–96, 2022.

arXiv:1910.08701

Takes the speed–robustness analysis of accelerated methods to networks. Agents hold local strongly convex objectives, exchange information only with neighbors, and see noisy gradients; the paper proposes distributed accelerated stochastic gradient methods, works out how fast they converge and how much gradient noise they amplify as a function of stepsize, momentum, and the network’s connectivity, and shows how to choose the parameters to sit on the resulting trade-off.

@article{fallah2022multiagent,
  title   = {Robust distributed accelerated stochastic gradient methods for multi-agent networks},
  author  = {Alireza Fallah and Mert Gürbüzbalaban and Asuman Ozdaglar and Umut Şimşekli and Lingjiong Zhu},
  year    = {2022},
  journal = {Journal of Machine Learning Research},
  volume  = {23(220)},
  pages   = {1--96},
  note    = {arXiv:1910.08701},
}

NeurIPSConference

SAPD+: an accelerated stochastic method for nonconvex-concave minimax problems

Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

Advances in Neural Information Processing Systems (NeurIPS), 2022.

Paper Note Playground

Extends the stochastic accelerated primal–dual method beyond the convex–concave case. SAPD+ wraps SAPD inside an inexact proximal-point scheme for weakly-convex–strongly-concave and weakly-convex–merely-concave minimax problems, with oracle-complexity bounds that match or improve the best known ones and a variance-reduced variant; the method handles the non-convex minimax problems that arise in robust and adversarial learning. Recent work showed that SAPD+ is an optimal method: its dependence on the condition number cannot be improved in the stochastic nonconvex–strongly-concave setting.

@inproceedings{zhang2022sapdplus,
  title   = {SAPD+: an accelerated stochastic method for nonconvex-concave minimax problems},
  author  = {Xuan Zhang and Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2022},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {http://papers.nips.cc/paper_files/paper/2022/hash/880d8999c07a8efc9bbbeb0c38f50765-Abstract-Conference.html},
}

2021

ICMLConference

Asymmetric heavy tails and implicit bias in Gaussian noise injections

Alexander Camuto, Xiaoyu Wang, Lingjiong Zhu, Chris Holmes, Mert Gürbüzbalaban, Umut Şimşekli

International Conference on Machine Learning (ICML), PMLR 139, pp. 1249–1260, 2021.

arXiv:2102.07006

Explains a side effect of adding Gaussian noise to activations during training. The gradient noise this induces is heavy-tailed and, more unusually, asymmetric, which gives SGD an implicit bias that can degrade generalization; modeling the dynamics with asymmetric α-stable processes identifies the cause, and correcting for the asymmetry recovers the regularization benefit that the noise injection was meant to provide.

@inproceedings{camuto2021asymmetric,
  title   = {Asymmetric heavy tails and implicit bias in Gaussian noise injections},
  author  = {Alexander Camuto and Xiaoyu Wang and Lingjiong Zhu and Chris Holmes and Mert Gürbüzbalaban and Umut Şimşekli},
  year    = {2021},
  booktitle = {International Conference on Machine Learning (ICML)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {139},
  pages   = {1249--1260},
  note    = {arXiv:2102.07006},
}

NeurIPSConference

Convergence rates of stochastic gradient descent under infinite noise variance

Hongjian Wang, Mert Gürbüzbalaban, Lingjiong Zhu, Umut Şimşekli, Murat A. Erdogdu

Advances in Neural Information Processing Systems (NeurIPS), 34, pp. 18866–18877, 2021.

arXiv:2102.10346

Provides convergence guarantees for SGD when gradient noise is so heavy-tailed that its variance is infinite: under a p-positive definiteness condition on the Hessian, plain SGD still converges to the global optimum of strongly convex problems, with rates in the p-th moment — no gradient clipping or robustification needed.

@inproceedings{wang2021infinite,
  title   = {Convergence rates of stochastic gradient descent under infinite noise variance},
  author  = {Hongjian Wang and Mert Gürbüzbalaban and Lingjiong Zhu and Umut Şimşekli and Murat A. Erdogdu},
  year    = {2021},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume  = {34},
  pages   = {18866--18877},
  note    = {arXiv:2102.10346},
}

J. Mach. Learn. Res.Journal · selected

Decentralized stochastic gradient Langevin dynamics and Hamiltonian Monte Carlo

Mert Gürbüzbalaban, Xuefeng Gao, Yuanhan Hu, Lingjiong Zhu

Journal of Machine Learning Research, 22(239), pp. 1–69, 2021.

arXiv:2007.00590 Code

Introduces decentralized versions of stochastic gradient Langevin dynamics and Hamiltonian Monte Carlo for Bayesian learning over networks of agents, with non-asymptotic guarantees on sampling accuracy.

@article{gurbuzbalaban2021decentralizedlangevin,
  title   = {Decentralized stochastic gradient Langevin dynamics and Hamiltonian Monte Carlo},
  author  = {Mert Gürbüzbalaban and Xuefeng Gao and Yuanhan Hu and Lingjiong Zhu},
  year    = {2021},
  journal = {Journal of Machine Learning Research},
  volume  = {22(239)},
  pages   = {1--69},
  note    = {arXiv:2007.00590},
}

NeurIPSConference

Fractal structure and generalization properties of stochastic optimization algorithms

Alexander Camuto, George Deligiannidis, Murat A. Erdogdu, Mert Gürbüzbalaban, Umut Şimşekli, Lingjiong Zhu

Advances in Neural Information Processing Systems (NeurIPS), 34, pp. 18774–18788, 2021. Gürbüzbalaban and Şimşekli are corresponding authors

arXiv:2106.04881

Asks what controls how well a stochastic optimizer generalizes, and answers with geometry: the iterates of an algorithm such as SGD accumulate on a set that is typically a fractal, and the paper bounds the generalization error by the Hausdorff dimension of that set rather than by the number of parameters. For algorithms driven by heavy-tailed noise the dimension is tied to the tail index — heavier tails, lower dimension, better generalization — and the dimension can be estimated numerically and tracks the generalization gap in experiments.

@inproceedings{camuto2021fractal,
  title   = {Fractal structure and generalization properties of stochastic optimization algorithms},
  author  = {Alexander Camuto and George Deligiannidis and Murat A. Erdogdu and Mert Gürbüzbalaban and Umut Şimşekli and Lingjiong Zhu},
  year    = {2021},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume  = {34},
  pages   = {18774--18788},
  note    = {arXiv:2106.04881},
}

AISTATSConference

Fractional moment-preserving initialization schemes for training deep neural networks

Mert Gürbüzbalaban, Yuanhan Hu

International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 130, pp. 2233–2241, 2021.

arXiv:2005.11878 Code

Standard initialization schemes keep the variance of activations constant across layers — which assumes the variance exists. When signals are heavy-tailed it may not, and the paper proposes initializations that preserve fractional moments of order below two instead, generalizing the Xavier and He schemes to the heavy-tailed regime, with experiments showing the difference in training deep networks.

@inproceedings{gurbuzbalaban2021init,
  title   = {Fractional moment-preserving initialization schemes for training deep neural networks},
  author  = {Mert Gürbüzbalaban and Yuanhan Hu},
  year    = {2021},
  booktitle = {International Conference on Artificial Intelligence and Statistics (AISTATS)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {130},
  pages   = {2233--2241},
  note    = {arXiv:2005.11878},
}

CDCConference

L-DQN: an asynchronous limited-memory distributed quasi-Newton method

Bugra Can, Saeed Soori, Maryam Mehri Dehnavi, Mert Gürbüzbalaban

IEEE Conference on Decision and Control (CDC), 2021.

DOI arXiv:2108.09365

A quasi-Newton method for a primary–worker system in which workers hold their own data and update asynchronously. L-DQN keeps limited-memory curvature information so that each update is cheap and the primary node never waits for the slowest worker, and the analysis shows the method still converges linearly despite the asynchrony, with experiments on large-scale problems.

@inproceedings{can2021ldqn,
  title   = {L-DQN: an asynchronous limited-memory distributed quasi-Newton method},
  author  = {Bugra Can and Saeed Soori and Maryam Mehri Dehnavi and Mert Gürbüzbalaban},
  year    = {2021},
  booktitle = {IEEE Conference on Decision and Control (CDC)},
  doi     = {10.1109/CDC45484.2021.9682985},
}

ICMLConference · selected

The heavy-tail phenomenon in SGD

Mert Gürbüzbalaban, Umut Şimşekli, Lingjiong Zhu

International Conference on Machine Learning (ICML), PMLR 139, pp. 3964–3975, 2021.

arXiv:2006.04740 Note Playground

Shows that SGD can produce heavy-tailed, power-law iterate fluctuations even from light-tailed data: multiplicative gradient noise drives a Kesten-type random recursion whose stationary law has a tail index controlled by the stepsize-to-batch-size ratio — connecting algorithm hyperparameters to the tail behavior, and thereby the generalization properties, of the learned solutions.

@inproceedings{gurbuzbalaban2021heavytail,
  title   = {The heavy-tail phenomenon in SGD},
  author  = {Mert Gürbüzbalaban and Umut Şimşekli and Lingjiong Zhu},
  year    = {2021},
  booktitle = {International Conference on Machine Learning (ICML)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {139},
  pages   = {3964--3975},
  note    = {arXiv:2006.04740},
}

Math. Program.Journal · selected

Why random reshuffling beats stochastic gradient descent

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

Mathematical Programming, 186, pp. 49–84, 2021.

DOI Code Note Playground

Resolves a long-standing open question about without-replacement sampling: random reshuffling — the sampling scheme practitioners actually use — provably converges faster than i.i.d. sampling for SGD, with rate Θ(1/k^2s) over epochs against the Ω(1/k) barrier of with-replacement sampling.

@article{gurbuzbalaban2021reshuffling,
  title   = {Why random reshuffling beats stochastic gradient descent},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo},
  year    = {2021},
  journal = {Mathematical Programming},
  volume  = {186},
  pages   = {49--84},
  doi     = {10.1007/s10107-019-01440-w},
}

2020

IPDPSConference

ASYNC: a cloud engine with asynchrony and history for distributed machine learning

Saeed Soori, Bugra Can, Mert Gürbüzbalaban, Maryam Mehri Dehnavi

IEEE International Parallel & Distributed Processing Symposium (IPDPS), pp. 429–439, 2020.

DOI

A cloud computing engine for distributed machine-learning algorithms that are asynchronous or that depend on the history of past updates — the two features that make such algorithms fast and that standard frameworks handle badly. ASYNC is built on Spark, exposes the bookkeeping the algorithms need, and is demonstrated on asynchronous gradient and quasi-Newton methods.

@inproceedings{soori2020async,
  title   = {ASYNC: a cloud engine with asynchrony and history for distributed machine learning},
  author  = {Saeed Soori and Bugra Can and Mert Gürbüzbalaban and Maryam Mehri Dehnavi},
  year    = {2020},
  booktitle = {IEEE International Parallel & Distributed Processing Symposium (IPDPS)},
  pages   = {429--439},
  doi     = {10.1109/IPDPS47924.2020.00052},
}

NeurIPSConference

Breaking reversibility accelerates Langevin dynamics for non-convex optimization

Xuefeng Gao, Mert Gürbüzbalaban, Lingjiong Zhu

Advances in Neural Information Processing Systems (NeurIPS), 33, pp. 17850–17862, 2020.

Paper arXiv:1812.07725

Langevin dynamics explores a non-convex landscape by adding noise to gradient descent, and the usual version is reversible in time. Adding a carefully chosen non-reversible drift leaves the stationary distribution unchanged but speeds up both convergence to it and escape from local minima, and the paper quantifies the resulting gains for non-convex optimization and for the generalization of the solutions found.

@inproceedings{gao2020reversibility,
  title   = {Breaking reversibility accelerates Langevin dynamics for non-convex optimization},
  author  = {Xuefeng Gao and Mert Gürbüzbalaban and Lingjiong Zhu},
  year    = {2020},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume  = {33},
  pages   = {17850--17862},
  url     = {https://proceedings.neurips.cc/paper/2020/hash/cebd648f9146a6345d604ab093b02c73-Abstract.html},
  note    = {arXiv:1812.07725},
}

AISTATSConference

DAve-QN: a distributed averaged quasi-Newton method with local superlinear convergence rate

Saeed Soori, Konstantin Mishchenko, Aryan Mokhtari, Maryam Mehri Dehnavi, Mert Gürbüzbalaban

International Conference on Artificial Intelligence and Statistics (AISTATS), PMLR 108, pp. 1965–1976, 2020.

Paper

A distributed quasi-Newton method in which each worker maintains its own curvature estimate and the primary node keeps an average, so that no single node has to handle the full problem. DAve-QN converges locally at a superlinear rate — the hallmark of quasi-Newton methods — even though information arrives from workers with delays, and the experiments compare it with first-order distributed methods.

@inproceedings{soori2020daveqn,
  title   = {DAve-QN: a distributed averaged quasi-Newton method with local superlinear convergence rate},
  author  = {Saeed Soori and Konstantin Mishchenko and Aryan Mokhtari and Maryam Mehri Dehnavi and Mert Gürbüzbalaban},
  year    = {2020},
  booktitle = {International Conference on Artificial Intelligence and Statistics (AISTATS)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {108},
  pages   = {1965--1976},
  url     = {http://proceedings.mlr.press/v108/soori20a.html},
}

ICMLConference

Fractional underdamped Langevin dynamics: retargeting SGD with momentum under heavy-tailed gradient noise

Umut Şimşekli, Lingjiong Zhu, Yee Whye Teh, Mert Gürbüzbalaban

International Conference on Machine Learning (ICML), PMLR 119, pp. 8970–8980, 2020.

Paper arXiv:2002.05685

When the gradient noise is heavy-tailed, SGD with momentum no longer samples from the distribution one would expect; it is attracted to a different, heavier-tailed one. Fractional underdamped Langevin dynamics is a modification of the momentum iteration whose invariant measure is the intended Gibbs distribution despite α-stable noise, derived with fractional calculus and tested on deep networks.

@inproceedings{simsekli2020fractional,
  title   = {Fractional underdamped Langevin dynamics: retargeting SGD with momentum under heavy-tailed gradient noise},
  author  = {Umut Şimşekli and Lingjiong Zhu and Yee Whye Teh and Mert Gürbüzbalaban},
  year    = {2020},
  booktitle = {International Conference on Machine Learning (ICML)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {119},
  pages   = {8970--8980},
  url     = {http://proceedings.mlr.press/v119/simsekli20a.html},
  note    = {arXiv:2002.05685},
}

NeurIPSConference

IDEAL: inexact decentralized accelerated augmented Lagrangian method

Yossi Arjevani, Joan Bruna, Bugra Can, Mert Gürbüzbalaban, Stefanie Jegelka, Hongzhou Lin

Advances in Neural Information Processing Systems (NeurIPS), 33, pp. 20648–20659, 2020.

Paper arXiv:2006.06733

A framework for decentralized optimization that reduces the problem to an augmented Lagrangian solved inexactly with any inner solver. With an accelerated inner method, IDEAL attains optimal communication complexity in the condition number and the network’s spectral gap for smooth strongly convex problems, unifying and improving on several earlier decentralized accelerated methods.

@inproceedings{arjevani2020ideal,
  title   = {IDEAL: inexact decentralized accelerated augmented Lagrangian method},
  author  = {Yossi Arjevani and Joan Bruna and Bugra Can and Mert Gürbüzbalaban and Stefanie Jegelka and Hongzhou Lin},
  year    = {2020},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume  = {33},
  pages   = {20648--20659},
  url     = {https://proceedings.neurips.cc/paper/2020/hash/ed77eab0b8ff85d0a6a8365df1846978-Abstract.html},
  note    = {arXiv:2006.06733},
}

Math. Program.Journal

Randomness and permutations in coordinate descent methods

Mert Gürbüzbalaban, Asuman Ozdaglar, Nuri Denizcan Vanli, Stephen J. Wright

Mathematical Programming, 181, pp. 349–376, 2020.

DOI Note Playground

Does the order in which coordinate descent visits the coordinates matter? For a family of quadratic problems the paper gives exact convergence rates for the random-permutations order and shows it can beat both the fixed cyclic order and independent random sampling, while the cyclic order can beat random sampling on others — the picture is more subtle than the worst-case bounds suggest.

@article{gurbuzbalaban2020permutations,
  title   = {Randomness and permutations in coordinate descent methods},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Nuri Denizcan Vanli and Stephen J. Wright},
  year    = {2020},
  journal = {Mathematical Programming},
  volume  = {181},
  pages   = {349--376},
  doi     = {10.1007/s10107-019-01438-4},
}

SIAM J. Optim.Journal · selected

Robust accelerated gradient methods for smooth strongly convex functions

Necdet Serhat Aybat, Alireza Fallah, Mert Gürbüzbalaban, Asuman Ozdaglar

SIAM Journal on Optimization, 30(1), pp. 717–751, 2020.

DOI arXiv:1805.10579 Note Playground

Analyzes accelerated gradient methods under inexact gradients through a robustness measure (asymptotic noise amplification), proves a Heisenberg-like trade-off — the product of speed and robustness is bounded below — and designs parameters on the resulting Pareto frontier, obtaining methods that retain acceleration while controlling noise amplification.

@article{aybat2020robust,
  title   = {Robust accelerated gradient methods for smooth strongly convex functions},
  author  = {Necdet Serhat Aybat and Alireza Fallah and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2020},
  journal = {SIAM Journal on Optimization},
  volume  = {30(1)},
  pages   = {717--751},
  doi     = {10.1137/19M1244925},
}

2019

ICMLConference · selected

A tail-index analysis of stochastic gradient noise in deep neural networks

Umut Şimşekli, Levent Sagun, Mert Gürbüzbalaban

International Conference on Machine Learning (ICML), PMLR 97, pp. 5827–5837, 2019. Best Paper Honorable Mention, ICML 2019.

Paper arXiv:1901.06053 Note Playground

Challenges the Gaussian picture of stochastic gradient noise: empirically, the noise in deep network training is heavy-tailed and better modeled by α-stable laws, which reframes SGD as a discretization of a Lévy-driven differential equation — with consequences for how the algorithm explores the loss landscape and escapes local minima.

@inproceedings{simsekli2019tailindex,
  title   = {A tail-index analysis of stochastic gradient noise in deep neural networks},
  author  = {Umut Şimşekli and Levent Sagun and Mert Gürbüzbalaban},
  year    = {2019},
  booktitle = {International Conference on Machine Learning (ICML)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {97},
  pages   = {5827--5837},
  url     = {http://proceedings.mlr.press/v97/simsekli19a.html},
  note    = {arXiv:1901.06053},
}

NeurIPSConference

A universally optimal multistage accelerated stochastic gradient method

Necdet Serhat Aybat, Alireza Fallah, Mert Gürbüzbalaban, Asuman Ozdaglar

Advances in Neural Information Processing Systems (NeurIPS), 32, pp. 8523–8534, 2019.

Paper arXiv:1901.08022

An accelerated stochastic gradient method for strongly convex problems that is optimal in both of the terms that matter — the deterministic part of the error, which decays at the accelerated rate, and the noise part, which decays at the optimal statistical rate — without knowing the noise level in advance. The method proceeds in stages, each with its own stepsize and momentum, and achieves this universally over the noise.

@inproceedings{aybat2019multistage,
  title   = {A universally optimal multistage accelerated stochastic gradient method},
  author  = {Necdet Serhat Aybat and Alireza Fallah and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2019},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  volume  = {32},
  pages   = {8523--8534},
  url     = {https://proceedings.neurips.cc/paper/2019/hash/d630553e32ae21fb1a6df39c702d2c5c-Abstract.html},
  note    = {arXiv:1901.08022},
}

ICMLConference · selected

Accelerated linear convergence of stochastic momentum methods in Wasserstein distances

Bugra Can, Mert Gürbüzbalaban, Lingjiong Zhu

International Conference on Machine Learning (ICML), PMLR 97, pp. 891–901, 2019.

Paper arXiv:1901.07445

Shows that with persistent gradient noise, momentum methods converge in distribution: the iterates contract linearly, at the accelerated rate, to a unique stationary law in the 1-Wasserstein distance — the analytical foundation for measuring and designing the stationary "noise cloud" of accelerated methods.

@inproceedings{can2019wasserstein,
  title   = {Accelerated linear convergence of stochastic momentum methods in Wasserstein distances},
  author  = {Bugra Can and Mert Gürbüzbalaban and Lingjiong Zhu},
  year    = {2019},
  booktitle = {International Conference on Machine Learning (ICML)},
  series  = {Proceedings of Machine Learning Research},
  volume  = {97},
  pages   = {891--901},
  url     = {http://proceedings.mlr.press/v97/can19a.html},
  note    = {arXiv:1901.07445},
}

SIAM J. Optim.Journal

Convergence rate of incremental gradient and incremental Newton methods

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

SIAM Journal on Optimization, 29(4), pp. 2542–2565, 2019.

DOI Note Playground

Pins down how fast the incremental gradient method — a fixed pass over the component functions with a diminishing stepsize — converges on strongly convex problems: with stepsize proportional to 1/k^s the rate is of order 1/k^s in the distance to the optimum, with the 1/k rate attainable when the constant is chosen correctly, and the incremental Newton method achieves the 1/k rate without that tuning.

@article{gurbuzbalaban2019incremental,
  title   = {Convergence rate of incremental gradient and incremental Newton methods},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo},
  year    = {2019},
  journal = {SIAM Journal on Optimization},
  volume  = {29(4)},
  pages   = {2542--2565},
  doi     = {10.1137/17M1147846},
}

NeurIPSConference

First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise

Thanh Huy Nguyen, Umut Şimşekli, Mert Gürbüzbalaban, Gaël Richard

Advances in Neural Information Processing Systems (NeurIPS), 2019.

Paper arXiv:1906.09069 Note Playground

Models SGD under heavy-tailed gradient noise as a stochastic differential equation driven by an α-stable Lévy process and analyzes how long it takes to leave a basin of the loss. The exit time depends polynomially on the width of the basin rather than exponentially on its depth, so heavy-tailed SGD leaves narrow minima quickly and settles in wide ones; the analysis also controls the gap between the SDE and the discrete SGD iteration.

@inproceedings{nguyen2019exittime,
  title   = {First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise},
  author  = {Thanh Huy Nguyen and Umut Şimşekli and Mert Gürbüzbalaban and Gaël Richard},
  year    = {2019},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {https://proceedings.neurips.cc/paper/2019/hash/a97da629b098b75c294dffdc3e463904-Abstract.html},
  note    = {arXiv:1906.09069},
}

arXivPreprint

On the heavy-tailed theory of stochastic gradient descent for deep neural networks

Umut Şimşekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, Levent Sagun

arXiv preprint, 2019. Şimşekli and Gürbüzbalaban contributed equally

arXiv:1912.00018

The long-form account of the heavy-tailed view of SGD, combining and extending the ICML 2019 tail-index measurements and the NeurIPS 2019 exit-time analysis: the gradient noise of SGD in deep networks has heavy, infinite-variance tails; the right continuous-time model is therefore a Lévy-driven stochastic differential equation rather than a diffusion; and in that model the time SGD takes to leave a basin depends on the basin’s width rather than its depth, which explains the preference for wide minima.

@misc{simsekli2019heavytailedtheory,
  title   = {On the heavy-tailed theory of stochastic gradient descent for deep neural networks},
  author  = {Umut Şimşekli and Mert Gürbüzbalaban and Thanh Huy Nguyen and Gaël Richard and Levent Sagun},
  year    = {2019},
  howpublished = {arXiv preprint arXiv:1912.00018},
}

2018

SIAM J. Optim.Journal

Global convergence rate of proximal incremental aggregated gradient methods

Nuri Denizcan Vanli, Mert Gürbüzbalaban, Asuman Ozdaglar

SIAM Journal on Optimization, 28(2), pp. 1282–1300, 2018.

DOI

Linear convergence for the proximal incremental aggregated gradient method, which minimizes a sum of smooth components plus a nonsmooth regularizer using one new component gradient per step and stale gradients for the rest. The rate is global, holds under strong convexity, and depends explicitly on how stale the aggregated gradients are allowed to be.

@article{vanli2018piag,
  title   = {Global convergence rate of proximal incremental aggregated gradient methods},
  author  = {Nuri Denizcan Vanli and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2018},
  journal = {SIAM Journal on Optimization},
  volume  = {28(2)},
  pages   = {1282--1300},
  doi     = {10.1137/16M1094415},
}

ICPPConference

Reducing communication in proximal Newton methods for sparse least squares problems

Saeed Soori, Aditya Devarakonda, Zachary Blanco, James Demmel, Mert Gürbüzbalaban, Maryam Mehri Dehnavi

International Conference on Parallel Processing (ICPP), 2018.

DOI

Proximal Newton methods for sparse least-squares problems spend most of their time communicating when run on a distributed-memory machine. Reformulating the inner iterations so that several steps’ worth of information is exchanged at once reduces the number of communication rounds by a tunable factor, and the resulting method is faster on large problems without changing what it computes.

@inproceedings{soori2018communication,
  title   = {Reducing communication in proximal Newton methods for sparse least squares problems},
  author  = {Saeed Soori and Aditya Devarakonda and Zachary Blanco and James Demmel and Mert Gürbüzbalaban and Maryam Mehri Dehnavi},
  year    = {2018},
  booktitle = {International Conference on Parallel Processing (ICPP)},
  doi     = {10.1145/3225058.3225131},
}

SIAM J. Optim.Journal

Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate

Aryan Mokhtari, Mert Gürbüzbalaban, Alejandro Ribeiro

SIAM Journal on Optimization, 28(2), pp. 1420–1447, 2018.

DOI arXiv:1611.00347

An incremental method that provably beats full gradient descent. DIAG aggregates both the gradients and the iterates of the component functions in a fixed cyclic order, converges linearly, and does so at a rate that is strictly better than gradient descent’s for the same amount of gradient computation — the first such guarantee for a cyclic incremental method.

@article{mokhtari2018cyclic,
  title   = {Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate},
  author  = {Aryan Mokhtari and Mert Gürbüzbalaban and Alejandro Ribeiro},
  year    = {2018},
  journal = {SIAM Journal on Optimization},
  volume  = {28(2)},
  pages   = {1420--1447},
  doi     = {10.1137/16M1101702},
}

2017

ICASSPConference

A double incremental aggregated gradient method with linear convergence rate for large-scale optimization

Aryan Mokhtari, Mert Gürbüzbalaban, Alejandro Ribeiro

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4696–4700, 2017.

DOI

The conference version of the double incremental aggregated gradient method: an incremental method that aggregates both gradients and iterates over a fixed cycle through the component functions and converges linearly on strongly convex finite sums, with a rate that improves on gradient descent’s.

@inproceedings{mokhtari2017diag,
  title   = {A double incremental aggregated gradient method with linear convergence rate for large-scale optimization},
  author  = {Aryan Mokhtari and Mert Gürbüzbalaban and Alejandro Ribeiro},
  year    = {2017},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  pages   = {4696--4700},
  doi     = {10.1109/ICASSP.2017.7953047},
}

SIAM J. Matrix Anal. Appl.Journal

Approximating the real structured stability radius with Frobenius-norm bounded perturbations

Nicola Guglielmi, Mert Gürbüzbalaban, Tim Mitchell, Michael L. Overton

SIAM Journal on Matrix Analysis and Applications, 38(4), pp. 1323–1353, 2017.

DOI

The real structured stability radius measures how large a real, structured perturbation a dynamical system can tolerate before losing stability. The paper shows the worst perturbations in the Frobenius norm can be taken to have rank at most two and builds an iterative method around that fact, which approximates the radius efficiently where the general problem is intractable.

@article{guglielmi2017radius,
  title   = {Approximating the real structured stability radius with Frobenius-norm bounded perturbations},
  author  = {Nicola Guglielmi and Mert Gürbüzbalaban and Tim Mitchell and Michael L. Overton},
  year    = {2017},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  volume  = {38(4)},
  pages   = {1323--1353},
  doi     = {10.1137/16M1110169},
}

GlobalSIPConference

Decentralized computation of effective resistances and acceleration of consensus algorithms

Necdet Serhat Aybat, Mert Gürbüzbalaban

IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 538–542, 2017.

DOI

Effective resistances say how important each link of a network is, and knowing them lets consensus algorithms weight their averaging steps to converge faster. The paper gives a decentralized way to compute them, with each node using only information from its neighbors, and uses the result to accelerate consensus.

@inproceedings{aybat2017resistance,
  title   = {Decentralized computation of effective resistances and acceleration of consensus algorithms},
  author  = {Necdet Serhat Aybat and Mert Gürbüzbalaban},
  year    = {2017},
  booktitle = {IEEE Global Conference on Signal and Information Processing (GlobalSIP)},
  pages   = {538--542},
  doi     = {10.1109/GlobalSIP.2017.8308701},
}

SIAM J. Optim.Journal · selected

On the convergence rate of incremental aggregated gradient algorithms

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

SIAM Journal on Optimization, 27(2), pp. 1035–1048, 2017.

DOI

Establishes the first linear convergence rate guarantees for incremental aggregated gradient methods — the deterministic-order counterparts of SAG-type algorithms — with explicit dependence on the problem conditioning and the delay in gradient information.

@article{gurbuzbalaban2017iag,
  title   = {On the convergence rate of incremental aggregated gradient algorithms},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo},
  year    = {2017},
  journal = {SIAM Journal on Optimization},
  volume  = {27(2)},
  pages   = {1035--1048},
  doi     = {10.1137/15M1049695},
}

Math. Program.Journal

Polynomial root radius optimization with affine constraints

Julie Eaton, Sara Grundel, Mert Gürbüzbalaban, Michael L. Overton

Mathematical Programming, 165(2), pp. 509–528, 2017.

DOI

Minimize the largest root modulus of a polynomial whose coefficients must satisfy a set of affine constraints — the problem behind stabilizing a discrete-time system with a controller of fixed structure. The optimal polynomial turns out to have very few distinct root moduli, which makes a non-convex, nonsmooth problem solvable in closed form in cases that matter for control.

@article{eaton2017rootradius,
  title   = {Polynomial root radius optimization with affine constraints},
  author  = {Julie Eaton and Sara Grundel and Mert Gürbüzbalaban and Michael L. Overton},
  year    = {2017},
  journal = {Mathematical Programming},
  volume  = {165(2)},
  pages   = {509--528},
  doi     = {10.1007/s10107-016-1092-5},
}

NeurIPSConference

When cyclic coordinate descent outperforms randomized coordinate descent

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo, Nuri Denizcan Vanli

Advances in Neural Information Processing Systems (NeurIPS), 2017. Spotlight presentation.

Paper

Random coordinate selection is usually assumed to be safer than a fixed cyclic order, because worst-case bounds say the cyclic order can be far slower. This paper exhibits a natural class of problems on which the opposite holds: the cyclic order converges provably faster than random selection, and the gap can grow with the dimension.

@inproceedings{gurbuzbalaban2017ccd,
  title   = {When cyclic coordinate descent outperforms randomized coordinate descent},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo and Nuri Denizcan Vanli},
  year    = {2017},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  url     = {https://proceedings.neurips.cc/paper/2017/hash/0e7c7d6c41c76b9ee6445ae01cc0181d-Abstract.html},
}

2016

OPT@NeurIPSConference

A simple proof for the iteration complexity of the proximal gradient algorithm

Nuri Denizcan Vanli, Mert Gürbüzbalaban, Asuman Ozdaglar

OPT 2016: NeurIPS Workshop on Optimization for Machine Learning, 2016.

A short, self-contained proof that the proximal gradient method converges at the rate O(1/k) in function value for composite convex problems — a smooth term plus a nonsmooth regularizer handled through its proximal map — built on one elementary inequality rather than the usual machinery, so the argument fits in a page and is easy to teach.

@inproceedings{vanli2016simpleproof,
  title   = {A simple proof for the iteration complexity of the proximal gradient algorithm},
  author  = {Nuri Denizcan Vanli and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2016},
  booktitle = {OPT 2016: NeurIPS Workshop on Optimization for Machine Learning},
}

CDCConference

Global convergence rate of incremental aggregated gradient methods for nonsmooth problems

Nuri Denizcan Vanli, Mert Gürbüzbalaban, Asuman Ozdaglar

IEEE Conference on Decision and Control (CDC), pp. 173–178, 2016.

DOI

Extends the linear convergence of incremental aggregated gradient methods to problems with a nonsmooth regularizer, where each step uses one fresh component gradient, stale gradients for the rest, and a proximal step for the regularizer; the rate is explicit in the staleness and the condition number.

@inproceedings{vanli2016nonsmooth,
  title   = {Global convergence rate of incremental aggregated gradient methods for nonsmooth problems},
  author  = {Nuri Denizcan Vanli and Mert Gürbüzbalaban and Asuman Ozdaglar},
  year    = {2016},
  booktitle = {IEEE Conference on Decision and Control (CDC)},
  pages   = {173--178},
  doi     = {10.1109/CDC.2016.7798265},
}

2015

Math. Program.Journal

A globally convergent incremental Newton method

Mert Gürbüzbalaban, Asuman Ozdaglar, Pablo A. Parrilo

Mathematical Programming, 151(1), pp. 283–313, 2015.

DOI

An incremental Newton method that processes the component functions one at a time with second-order information and, unlike earlier incremental Newton schemes, is proved to converge from any starting point. With a constant stepsize it converges linearly on strongly convex problems, and with diminishing stepsizes it converges at an explicit sublinear rate.

@article{gurbuzbalaban2015newton,
  title   = {A globally convergent incremental Newton method},
  author  = {Mert Gürbüzbalaban and Asuman Ozdaglar and Pablo A. Parrilo},
  year    = {2015},
  journal = {Mathematical Programming},
  volume  = {151(1)},
  pages   = {283--313},
  doi     = {10.1007/s10107-015-0897-y},
}

ROCONDConference

Polynomial stabilization with bounds on the controller coefficients

Julie Eaton, Sara Grundel, Mert Gürbüzbalaban, Michael L. Overton

IFAC Symposium on Robust Control Design (ROCOND), 2015.

DOI

Stabilizing a discrete-time polynomial family when the controller’s coefficients must stay within given bounds — a root-radius optimization with box constraints. The paper characterizes when the problem is feasible and gives explicit solutions in low-dimensional cases, connecting a hard nonsmooth optimization problem to a classical control question.

@inproceedings{eaton2015stabilization,
  title   = {Polynomial stabilization with bounds on the controller coefficients},
  author  = {Julie Eaton and Sara Grundel and Mert Gürbüzbalaban and Michael L. Overton},
  year    = {2015},
  booktitle = {IFAC Symposium on Robust Control Design (ROCOND)},
  doi     = {10.1016/j.ifacol.2015.09.487},
}

2013

SIAM J. Matrix Anal. Appl.Journal · selected

Fast approximation of the H∞ norm via optimization over spectral value sets

Nicola Guglielmi, Mert Gürbüzbalaban, Michael L. Overton

SIAM Journal on Matrix Analysis and Applications, 34(2), pp. 709–737, 2013.

DOI

Develops fast algorithms for approximating the H∞ norm of large-scale dynamical systems by optimizing over spectral value sets — scalable alternatives to the classical Boyd–Balakrishnan bisection, and the computational root of the later control-theoretic analysis of optimization algorithms.

@article{guglielmi2013hinf,
  title   = {Fast approximation of the {$H_\infty$} norm via optimization over spectral value sets},
  author  = {Nicola Guglielmi and Mert Gürbüzbalaban and Michael L. Overton},
  year    = {2013},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  volume  = {34(2)},
  pages   = {709--737},
  doi     = {10.1137/120875752},
}

2012

IEEE Trans. Autom. ControlJournal

Explicit solutions for root optimization of a polynomial family with one affine constraint

Vincent D. Blondel, Mert Gürbüzbalaban, Alexandre Megretski, Michael L. Overton

IEEE Transactions on Automatic Control, 57(12), pp. 3078–3089, 2012.

DOI

Among all monic polynomials whose coefficients satisfy a single affine constraint, which one has the smallest root radius, or the smallest root abscissa? The answer is explicit: the optimal polynomial has all of its roots at one point, and the paper gives that point, which settles the simplest version of the fixed-order stabilization problem in control.

@article{blondel2012root,
  title   = {Explicit solutions for root optimization of a polynomial family with one affine constraint},
  author  = {Vincent D. Blondel and Mert Gürbüzbalaban and Alexandre Megretski and Michael L. Overton},
  year    = {2012},
  journal = {IEEE Transactions on Automatic Control},
  volume  = {57(12)},
  pages   = {3078--3089},
  doi     = {10.1109/TAC.2012.2202069},
}

Nonlinear Anal.Journal

On Nesterov's nonsmooth Chebyshev–Rosenbrock functions

Mert Gürbüzbalaban, Michael L. Overton

Nonlinear Analysis: Theory, Methods & Applications, 75(3), pp. 1282–1289, 2012. Invited paper, special issue on optimization.

Paper

Nesterov’s nonsmooth Chebyshev–Rosenbrock functions are a famous stress test for nonsmooth optimization methods. The paper explains why they are so hard: the first variant has exponentially many Clarke stationary points of which only one is a minimizer, so a method that converges to Clarke stationary points can stop almost anywhere, and the second variant is analyzed in the same spirit.

@article{gurbuzbalaban2012nesterov,
  title   = {On Nesterov's nonsmooth Chebyshev–Rosenbrock functions},
  author  = {Mert Gürbüzbalaban and Michael L. Overton},
  year    = {2012},
  journal = {Nonlinear Analysis: Theory, Methods & Applications},
  volume  = {75(3)},
  pages   = {1282--1289},
  url     = {https://www.sciencedirect.com/science/article/pii/S0362546X1100544X},
}

SIAM J. Optim.Journal

Some regularity results for the pseudospectral abscissa and pseudospectral radius of a matrix

Mert Gürbüzbalaban, Michael L. Overton

SIAM Journal on Optimization, 22(2), pp. 281–285, 2012.

DOI

The pseudospectral abscissa and radius measure the robust stability of a matrix, and optimizing them requires knowing how regular they are as functions of the matrix. The paper proves they are locally Lipschitz and, more strongly, regular in the sense of nonsmooth analysis near the relevant points, which is what the convergence theory of nonsmooth optimization methods needs.

@article{gurbuzbalaban2012pseudospectral,
  title   = {Some regularity results for the pseudospectral abscissa and pseudospectral radius of a matrix},
  author  = {Mert Gürbüzbalaban and Michael L. Overton},
  year    = {2012},
  journal = {SIAM Journal on Optimization},
  volume  = {22(2)},
  pages   = {281--285},
  doi     = {10.1137/110822840},
}

2010

CDCConference

Explicit solutions for root optimization of a polynomial family

Vincent D. Blondel, Mert Gürbüzbalaban, Alexandre Megretski, Michael L. Overton

IEEE Conference on Decision and Control (CDC), pp. 485–488, 2010.

DOI

The conference version of the root-optimization result: for monic polynomials with one affine constraint on the coefficients, the polynomial with the smallest root radius has a single repeated root, which can be computed explicitly.

@inproceedings{blondel2010root,
  title   = {Explicit solutions for root optimization of a polynomial family},
  author  = {Vincent D. Blondel and Mert Gürbüzbalaban and Alexandre Megretski and Michael L. Overton},
  year    = {2010},
  booktitle = {IEEE Conference on Decision and Control (CDC)},
  pages   = {485--488},
  doi     = {10.1109/CDC.2010.5718074},
}

This archive covers the journal articles, principal conference papers, and current preprints; the CV is the complete record. Author order follows the published papers — alphabetical in mathematics venues, contribution-ordered in some engineering and machine-learning venues.