|
Large-scale convex optimization
Advances in randomized numerical linear algebra (randNLA) improve the runtime of a variety of fundamental linear algebraic operations.
The resulting advances in low-rank matrix approximation
have important implications throughout optimization:
many subproblems admit speedups by using low-rank approximations to
data matrices, problem variables, or Hessians.
Our lab has used fast low rank approximations to accelerate
cross-validation,
dynamic optimization,
optimal sensing,
semidefinite programming,
linear systems solvers,
composite optimization,
and conic optimization,
and stochastic optimization.
For example,
we developed a low-rank preconditioner for solving linear systems (NystromPCG)
and used it
to speed up solution times for well-studied statistical learning problems such as LASSO, SVM, logistic regression by an order of magnitude (NysADMM and GeNIOS).
Talks
Software
GeNIOS for composite convex optimization
sketchySGD for stochastic optimization
PROMISE for faster stochastic optimization when the objective is convex
Papers
Stochastic Gradient Methods with Online Scaling
W. Zhang, W. Gao, Y. Ye, and M. Udell
2026
[arxiv][url][bib]
Operator Splitting Methods with Online Scaling
W. Zhang, W. Gao, and M. Udell
2026
[arxiv][url][bib]
GPU-Enabled Large-Scale Optimization Using Randomized Linear Algebra
P. Rathore, Z. Frangella, P. Nobel, X. Hu, and M. Udell
2026
[arxiv][url][code][bib]
Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp
W. Gao, Z. Qu, Y. Ye, and M. Udell
2026
[arxiv][url][bib]
New Results on the Polyak Stepsize: Tight Convergence Analysis and Universal Function Classes
C. He, W. Gao, B. Jiang, M. Udell, and S. Zhang
SIAM Journal on Optimization, 2026
[arxiv][url][bib]
Have ASkotch: A Neat Solution for Large-Scale Kernel Ridge Regression
P. Rathore, Z. Frangella, J. Yang, M. Dereziński, and M. Udell
Journal of Machine Learning Research (JMLR), 2026
[arxiv][url][bib]
Randomized Nyström Preconditioned Interior Point-Proximal Method of Multipliers
Y. Chu, L. Santos, and M. Udell
SIAM Journal on Scientific Computing (SISC), 2026
[arxiv][url][bib]
Scalable Approximate Optimal Diagonal Preconditioning
W. Gao, Z. Qu, M. Udell, and Y. Ye
Computational Optimization and Applications, 2026
[arxiv][url][bib]
On the (linear) convergence of Generalized Newton Inexact ADMM
Z. Frangella, T. Diamandis, B. Stellato, and M. Udell
Transactions on Machine Learning Research (TMLR), 2026
[arxiv][url][bib]
Gradient Methods with Online Scaling Part II. Practical Aspects
Y. Chu, W. Gao, Y. Ye, and M. Udell
Major revision at Mathematical Programming, 2025
[arxiv][url][bib]
Gradient Methods with Online Scaling Part I. Theoretical Foundations
W. Gao, Y. Chu, Y. Ye, and M. Udell
Major revision at Mathematical Programming, 2025
[arxiv][bib]
Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
P. Rathore, Z. Frangella, S. Garg, S. Fazliani, M. Dereziński, and M. Udell
NeurIPS, 2025
[arxiv][url][bib]
Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent
Y. Chu, W. Gao, Y. Ye, and M. Udell
International Conference on Machine Learning (ICML), 2025
[arxiv][url][bib]
SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning
J. Sun, Z. Frangella, and M. Udell
Accepted at SIAM Journal on Mathematics of Data Science (SIMODS), 2025
[arxiv][url][bib]
Gradient Methods with Online Scaling
W. Gao, Y. Chu, Y. Ye, and M. Udell
Conference on Learning Theory (COLT), 2025
[arxiv][url][bib]
When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?
W. Gao, H. Liu, Y. Ye, and M. Udell
Submitted, 2024
[arxiv][url][bib]
PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates
Z. Frangella, P. Rathore, S. Zhao, and M. Udell
JMLR, 2024
[arxiv][url][bib]
SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates
Z. Frangella, P. Rathore, S. Zhao, and M. Udell
SIAM Journal on Mathematics of Data Science (SIMODS), 2024
[arxiv][url][bib]
GeNIOS: an (almost) second-order operator-splitting solver for large-scale convex optimization
T. Diamandis, Z. Frangella, S. Zhao, B. Stellato, and M. Udell
Mathematical Programming Computation, 2023
[arxiv][url][bib]
Randomized Numerical Linear Algebra for Optimization
M. Udell and Z. Frangella
SIAG/OPT Views and News, 2022
[pdf][url][bib][video]
NysADMM: faster composite convex optimization via low-rank approximation
S. Zhao, Z. Frangella, and M. Udell
International Conference on Machine Learning (ICML), 2022
[arxiv][url][bib]
Randomized Nystr\"om Preconditioning
Z. Frangella, J. A. Tropp, and M. Udell
SIAM Journal on Matrix Analysis and Applications, 2022
[arxiv][url][bib]
A Strict Complementarity Approach to Error Bound and Sensitivity of Solution of Conic Programs
L. Ding and M. Udell
Optimization Letters, 2022
[arxiv][pdf][url][bib]
On the simplicity and conditioning of low rank semidefinite programs
L. Ding and M. Udell
SIAM Journal on Optimization (SIOPT), 2021
[arxiv][url][bib]
Scalable Semidefinite Programming
A. Yurtsever, J. Tropp, O. Fercoq, M. Udell, and V. Cevher
SIAM Journal on Mathematics of Data Science (SIMODS), 2021
[arxiv][pdf][url][bib]
Randomized Sketching Algorithms for Low-Memory Dynamic Optimization
R. Muthukumar, D. Kouri, and M. Udell
SIAM Journal on Optimization (SIOPT), 2021
[pdf][url][bib]
An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
L. Ding, A. Yurtsever, V. Cevher, J. Tropp, and M. Udell
SIAM Journal on Optimization (SIOPT), 2021
Winner of 2017 INFORMS Optimization Society student paper prize
[arxiv][pdf][url][slides][bib]
kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles
L. Ding, J. Fan, and M. Udell
In revision at Computational Optimization and Applications, 2020
[arxiv][url][bib]
Frank-Wolfe Style Algorithms for Large Scale Optimization
L. Ding and M. Udell
Large-Scale and Distributed Optimization, 2018
[arxiv][pdf][bib]
Sketchy Decisions: Convex Low-Rank Matrix Optimization with Optimal Storage
A. Yurtsever, M. Udell, J. Tropp, and V. Cevher
International Conference on Artificial Intelligence and Statistics (AISTATS), 2017
Oral Presentation
[arxiv][pdf][url][slides][bib][video]
The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
D. Davis, B. Edmunds, and M. Udell
Advances in Neural Information Processing Systems, 2016
[arxiv][pdf][bib]
|