Fetching the paper…
Reading the bibliography…
This work provides test error bounds for iterative fixed point methods on linear predictors -- specifically, stochastic and batch mirror descent (MD), and stochastic temporal difference learning (TD) -- with two core contributions: (a) a single proof technique which gives high probability guarantees despite the absence of projections, regularization, or any equivalents, even when optima have large or infinite norm, for quadratically-bounded losses (e.g., providing unified treatment of squared and logistic losses); (b) locally-adapted rates which depend not on global problem structure (such as condition numbers and maximum margins), but rather on properties of low norm predictors which may suffer some small excess test error.
A stochastic approximation method
H. Robbins and S. Monro · 1951
Earlier work this paper cites.
On convergence proofs on perceptrons
Albert B.J. Novikoff · 1962
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
A. S. Nemirovski and D. B. Yudin · 1983
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
Richard S Sutton · 1988
Earlier work this paper cites.
Boosting the margin: A new explanation for the effectiveness of voting methods
Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee · 1997
Earlier work this paper cites.
Fundamentals of Convex Analysis
Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal · 2001
Earlier work this paper cites.
Solving large scale linear prediction problems using stochastic gradient descent algorithms
Tong Zhang · 2004
Earlier work this paper cites.
Boosting with early stopping: Convergence and consistency
Tong Zhang and Bin Yu · 2005
Earlier work this paper cites.
On the complexity of linear prediction: Risk bounds, margin bounds, and regularization
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari · 2008
Earlier work this paper cites.
Optimal Transport: Old and New
Cèdric Villani · 2008
Earlier work this paper cites.
Large-scale machine learning with stochastic gradient descent
Léon Bottou · 2010
Earlier work this paper cites.
254a notes 1: Concentration of measure, Jan 2010
Terence Tao · 2010
Earlier work this paper cites.
Ergodic mirror descent
John C Duchi, Alekh Agarwal, Mikael Johansson, and Michael I Jordan · 2012
Earlier work this paper cites.
Markov chains and stochastic stability
Sean P Meyn and Richard L Tweedie · 2012
Earlier work this paper cites.
Making gradient descent optimal for strongly convex stochastic optimization
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan · 2012
Earlier work this paper cites.
Margins, shrinkage, and boosting
Matus Telgarsky · 2013
Earlier work this paper cites.
Moment-based uniform deviation bounds for k k -means and friends
Matus Telgarsky and Sanjoy Dasgupta · 2013
Cited alongside, same era.
Taming the monster: A fast and simple algorithm for contextual bandits
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire · 2014
Cited alongside, same era.
Adam: A method for stochastic optimization
Diederik P Kingma and Jimmy Ba · 2014
Cited alongside, same era.
In search of the real inductive bias: On the role of implicit regularization in deep learning
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro · 2014
Cited alongside, same era.
Understanding Machine Learning: From Theory to Algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Cited alongside, same era.
Tight analyses for non-smooth stochastic gradient descent
Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa · 2019
Later among the works it cites.
Gradient descent maximizes the margin of homogeneous neural networks
Kaifeng Lyu and Jian Li · 2019
Later among the works it cites.
Algorithms of robust stochastic optimization based on mirror descent method
Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky · 2019
Later among the works it cites.
Finite-sample analysis for SARSA with linear function approximation
Shaofeng Zou, Tengyu Xu, and Yingbin Liang · 2019
Later among the works it cites.
Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss
Lenaic Chizat and Francis Bach · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Train faster, generalize better: Stability of stochastic gradient descent
Moritz Hardt, Ben Recht, and Yoram Singer · 2016
Cited alongside, same era.
Apc 550 lecture notes: Probability in high dimensions, Dec 2016
Ramon van Handel · 2016
Cited alongside, same era.
Foundations of data science, 2017
Avrim Blum, John Hopcroft, and Ravindran Kannan · 2017
Cited alongside, same era.
The implicit bias of gradient descent on separable data
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro · 2017
Cited alongside, same era.
Understanding deep learning requires rethinking generalization
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals · 2017
Cited alongside, same era.
A finite time analysis of temporal difference learning with linear function approximation
Jalaj Bhandari, Daniel Russo, and Raghav Singal · 2018
Cited alongside, same era.
Later among the works it cites.
High probability guarantees for stochastic convex optimization
Damek Davis and Dmitriy Drusvyatskiy · 2020
Later among the works it cites.
Stochastic optimization with heavy-tailed noise via accelerated gradient clipping
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov · 2020
Later among the works it cites.
Directional convergence and alignment in deep learning
Ziwei Ji and Matus Telgarsky · 2020
Later among the works it cites.
Bandit Algorithms
Tor Lattimore and Csaba Szepesvári · 2020
Later among the works it cites.
A high probability analysis of adaptive sgd with momentum
Xiaoyu Li and Francesco Orabona · 2020
Later among the works it cites.
The statistical complexity of early-stopped mirror descent
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini · 2020
Later among the works it cites.
Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate
Jingfeng Wu, Difan Zou, Vladimir Braverman, and Quanquan Gu · 2020
Later among the works it cites.
Gradient methods never overfit on separable data
Ohad Shamir · 2021
Later among the works it cites.
Actor-critic is implicitly biased towards high entropy optimal policies
Yuzheng Hu, Ziwei Ji, and Matus Telgarsky · 2022
Closest in time.
Polylogarithm — Wikipedia, the free encyclopedia
Wikipedia contributors · 2022
Closest in time.
Beyond sub-gaussian noises: Sharp concentration analysis for stochastic gradient descent
Wanrong Zhu, Zhipeng Lou, and Wei Biao Wu · 2022
Closest in time.