538 citations · 2.3k across the 54 of their papers we have counts for
28 papers · 1 filter
BiSLS/SPS: Auto-tune Step Sizes for Stable Bi-level Optimization
Chen Fan, Gaspard Choné-Ducasse, Mark Schmidt +1
The popularity of bi-level optimization (BO) in deep learning has spurred a growing interest in studying gradient-based BO algorithms. However, existing algorithms involve two coup…
Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington +1
The success of the Adam optimizer on a wide array of architectures has made it the default in settings where stochastic gradient descent (SGD) performs poorly. However, our theoret…
Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-Łojasiewicz Condition
Chen Fan, Christos Thrampoulidis, Mark Schmidt
Modern machine learning models are often over-parameterized and as a result they can interpolate the training data. Under such a scenario, we study the convergence properties of a…
Target-based Surrogates for Stochastic Optimization
Jonathan Wilder Lavington, Sharan Vaswani, Reza Babanezhad +2
We consider minimizing functions for which it is expensive to compute the (possibly stochastic) gradient. Such functions are prevalent in reinforcement learning, imitation learning…
Improved Policy Optimization for Online Imitation Learning
Jonathan Wilder Lavington, Sharan Vaswani, Mark Schmidt
We consider online imitation learning (OIL), where the task is to find a policy that imitates the behavior of an expert via active interaction with the environment. We aim to bridg…
SVRG Meets AdaGrad: Painless Variance Reduction
Benjamin Dubois-Taine, Sharan Vaswani, Reza Babanezhad +2
Variance reduction (VR) methods for finite-sum minimization typically require the knowledge of problem-dependent constants that are often unknown and difficult to estimate. To addr…
Robust Asymmetric Learning in POMDPs
Andrew Warrington, J. Wilder Lavington, Adam Ścibior +2
Policies for partially observed Markov decision processes can be efficiently learned by imitating policies for the corresponding fully observed Markov decision processes. Unfortuna…
Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent
Frederik Kunstner, Raunak Kumar, Mark Schmidt
Expectation maximization (EM) is the default algorithm for fitting probabilistic models with missing or latent variables, yet we lack a full understanding of its non-asymptotic con…
Variance-Reduced Methods for Machine Learning
Robert M. Gower, Mark Schmidt, Francis Bach +1
Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last 8 years hav…
Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses
Yihan Zhou, Victor S. Portella, Mark Schmidt +1
In online convex optimization (OCO), Lipschitz continuity of the functions is commonly assumed in order to obtain sublinear regret. Moreover, many algorithms have only logarithmic…
Adaptive Gradient Methods Converge Faster with Over-Parameterization (but you should do a line-search)
Sharan Vaswani, Issam Laradji, Frederik Kunstner +3
Adaptive gradient methods are typically used for training over-parameterized models. To better understand their behaviour, we study a simplistic setting -- smooth, convex losses wi…
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
Si Yi Meng, Sharan Vaswani, Issam Laradji +2
We consider stochastic second-order methods for minimizing smooth and strongly-convex functions under an interpolation condition satisfied by over-parameterized models. Under this…
Efficient Deep Gaussian Process Models for Variable-Sized Input
Issam H. Laradji, Mark Schmidt, Vladimir Pavlovic +1
Deep Gaussian processes (DGP) have appealing Bayesian properties, can handle variable-sized data, and learn deep features. Their limitation is that they do not scale well with the…
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates
Sharan Vaswani, Aaron Mishkin, Issam Laradji +3
Recent works have shown that stochastic gradient descent (SGD) achieves the fast convergence rates of full-batch gradient descent for over-parameterized models satisfying certain i…
Distributed Maximization of Submodular plus Diversity Functions for Multi-label Feature Selection on Huge Datasets
Mehrdad Ghadiri, Mark Schmidt
There are many problems in machine learning and data mining which are equivalent to selecting a non-redundant, high "quality" set of objects. Recommender systems, feature selection…
SLANG: Fast Structured Covariance Approximations for Bayesian Deep Learning with Natural Gradient
Aaron Mishkin, Frederik Kunstner, Didrik Nielsen +2
Uncertainty estimation in large deep-learning models is a computationally challenging task, where it is difficult to form even a Gaussian approximation to the posterior distributio…
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
Sharan Vaswani, Francis Bach, Mark Schmidt
Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that…
Combining Bayesian Optimization and Lipschitz Optimization
Mohamed Osama Ahmed, Sharan Vaswani, Mark Schmidt
Bayesian optimization and Lipschitz optimization have developed alternative techniques for optimizing black-box functions. They each exploit a different form of prior about the fun…
A Less Biased Evaluation of Out-of-distribution Sample Detectors
Alireza Shafaei, Mark Schmidt, James J. Little
In the real world, a learning system could receive an input that is unlike anything it has seen during training. Unfortunately, out-of-distribution samples can lead to unpredictabl…
New Insights into Bootstrapping for Bandits
Sharan Vaswani, Branislav Kveton, Zheng Wen +3
We investigate the use of bootstrapping in the bandit setting. We first show that the commonly used non-parametric bootstrapping (NPB) procedure can be provably inefficient and est…
Horde of Bandits using Gaussian Markov Random Fields
Sharan Vaswani, Mark Schmidt, Laks V. S. Lakshmanan
The gang of bandits (GOB) model \cite{cesa2013gang} is a recent contextual bandits framework that shares information between a set of bandit problems, related by a known (possibly…
Online Learning Rate Adaptation with Hypergradient Descent
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio +2
We introduce a general method for improving the convergence rate of gradient-based optimizers that is easy to implement and works well in practice. We demonstrate the effectiveness…
Model-Independent Online Learning for Influence Maximization
Sharan Vaswani, Branislav Kveton, Zheng Wen +3
We consider influence maximization (IM) in social networks, which is the problem of maximizing the number of users that become aware of a product by selecting a set of "seed" users…
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
Hamed Karimi, Julie Nutini, Mark Schmidt
In 1963, Polyak proposed a simple condition that is sufficient to show a global linear convergence rate for gradient descent. This condition is a special case of the Łojasiewicz in…