538 citations · 2.3k across the 54 of their papers we have counts for
10 papers · 1 filter
Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm
Amrutha Varshini Ramesh, Aaron Mishkin, Mark Schmidt +3
We consider minimizing a smooth function subject to a summation constraint over its variables. By exploiting a connection between the greedy 2-coordinate update for this problem an…
Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking
Frederik Kunstner, Victor S. Portella, Mark Schmidt +1
The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically opti…
Don't be so Monotone: Relaxing Stochastic Line Search in Over-Parameterized Models
Leonardo Galli, Holger Rauhut, Mark Schmidt
Recent works have shown that line search methods can speed up Stochastic Gradient Descent (SGD) and Adam in modern over-parameterized settings. However, existing line searches may…
Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence
Julie Nutini, Issam Laradji, Mark Schmidt
Block coordinate descent (BCD) methods are widely used for large-scale numerical optimization because of their cheap iteration costs, low memory requirements, amenability to parall…
"Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?
Julie Nutini, Mark Schmidt, Warren Hare
Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or L1-regularization. Under suitable nondegeneracy…
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection
Julie Nutini, Mark Schmidt, Issam H. Laradji +2
There has been significant recent work on the theory and application of randomized coordinate descent algorithms, beginning with the work of Nesterov [SIAM J. Optim., 22(2), 2012],…
Convex Optimization for Big Data
Volkan Cevher, Stephen Becker, Mark Schmidt
This article reviews recent advances in convex optimization algorithms for Big Data, which aim to reduce the computational, storage, and communications bottlenecks. We provide an o…
Minimizing Finite Sums with the Stochastic Average Gradient
Mark Schmidt, Nicolas Le Roux, Francis Bach
We propose the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method'…
Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
Mark Schmidt, Nicolas Le Roux
We consider optimizing a function smooth convex function that is the average of a set of differentiable functions , under the assumption considered by Solodov [1998] and T…
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
Nicolas Le Roux, Mark Schmidt, Francis Bach
We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods…