2 citations · 9 across the 14 of their papers we have counts for
13 papers · 1 filter
Tight Convergence Bounds for the Classical Kaczmarz Method
Runbo Yu, Jelena Diakonikolas
The classical method of Kaczmarz, introduced in 1937, is a textbook iterative method for solving linear systems Despite its widespread use, particularly in the context o…
Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities
Yi Wei, Xufeng Cai, Jelena Diakonikolas
Cyclic block coordinate methods are a fundamental class of first-order algorithms, widely used in practice for their simplicity and strong empirical performance. Yet, their theoret…
Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm
Xufeng Cai, Jason M. Altschuler, Jelena Diakonikolas
In 1960, Osborne proposed a simple iterative algorithm for matrix balancing with outstanding numerical performance. Today, it is the default preconditioning procedure before eigenv…
Last Iterate Convergence of Incremental Methods and Applications in Continual Learning
Xufeng Cai, Jelena Diakonikolas
Incremental gradient and incremental proximal methods are a fundamental class of optimization algorithms used for solving finite sum problems, broadly studied in the literature. Ye…
Mirror Duality in Convex Optimization
Jaeyeon Kim, Chanwoo Park, Asuman Ozdaglar +2
While first-order optimization methods are usually designed to efficiently reduce the function value , there has been recent interest in methods efficiently reducing the magn…
Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds
Xufeng Cai, Cheuk Yin Lin, Jelena Diakonikolas
Stochastic gradient descent (SGD) is perhaps the most prevalent optimization method in modern machine learning. Contrary to the empirical practice of sampling from the datasets wit…
Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimization
Cheuk Yin Lin, Chaobing Song, Jelena Diakonikolas
Exploiting partial first-order information in a cyclic way is arguably the most natural strategy to obtain scalable first-order methods. However, despite their wide use in practice…
Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimization
Xufeng Cai, Chaobing Song, Stephen J. Wright +1
Nonconvex optimization is central in solving many machine learning problems, in which block-wise structure is commonly encountered. In this work, we propose cyclic block coordinate…
A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data
Jelena Diakonikolas, Chenghui Li, Swati Padmanabhan +1
Nonnegative (linear) least square problems are a fundamental class of problems that is well-studied in statistical learning and for which solvers have been implemented in many of t…
Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions
Xufeng Cai, Chaobing Song, Cristóbal Guzmán +1
We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel varian…
Coordinate Linear Variance Reduction for Generalized Linear Programming
Chaobing Song, Cheuk Yin Lin, Stephen J. Wright +1
We study a class of generalized linear programs (GLP) in a large-scale setting, which includes simple, possibly nonsmooth convex regularizer and simple convex set constraints. By r…
Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
Chaobing Song, Stephen J. Wright, Jelena Diakonikolas
We study structured nonsmooth convex finite-sum optimization that appears widely in machine learning applications, including support vector machines and least absolute deviation. F…
Cyclic Coordinate Dual Averaging with Extrapolation
Chaobing Song, Jelena Diakonikolas
Cyclic block coordinate methods are a fundamental class of optimization methods widely used in practice and implemented as part of standard software packages for statistical learni…