SDCA without Duality, Regularization, and Individual Convexity

By Shai Shalev-Shwartz. 2016

108 citations recorded by the source corpus.

Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. We describe variants of SDCA that do not require explicit regularization and do not rely on duality. We prove linear convergence rates even if individual loss functions are non-convex, as long as the expected loss is strongly convex.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

AIDE: Fast and Communication Efficient Distributed Optimization (2016, background): “This is to be expected, as the acceleration of the fast stochastic methods changes κ in convergence rates to √ Nκ [18].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “Recent works [86, 20] interpret the SDCA method in primal-only setting, shedding light onto why this method works as a SGD method with a version of variance reduction property.”
SGD: General Analysis and Improved Rates (2019, background): “In the last experiment (Section 6.3) we focus on the problem of principal component analysis (PCA) which by construction can be seen as a problem with a strongly convex objective f but with non-convex functions f i (Allen-Zhu & Yuan, 2016; Garber & Hazan, 2015; Shalev-Shwartz, 2016).”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, methodology): “Variance reduced methods (Roux et al., 2012; Johnson & Zhang, 2013; Shalev-Shwartz & Zhang, 2013; Defazio et al., 2014; Qu et al., 2015; Shalev-Shwartz, 2016; Qu et al., 2016; Csiba & Richt ´ arik, 2015; Csiba et al., 2015; Nguyen et al., 2017; Gower et al., 2018; Zhou, 2018) admit linear…”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “1)) and then followed by many others (Zhang et al., 2013; Mahdavi et al., 2013; Johnson and Zhang, 2013; Shalev-Shwartz and Zhang, 2013; Shalev-Shwartz, 2016; Shalev-Shwartz and Zhang, 2012; Xiao and Zhang, 2014; Defazio et al., 2014; Mairal, 2015; Allen-Zhu and Yuan, 2016).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “Recent works [160, 38] interpret the SDCA method in primal-only setting, shedding light onto why this method works as a SGD method with a version of variance reduction property.”
Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving (2016, background): “High variance of the gradient has a detrimental effect on the convergence rate of SGD [22, 29, 16, 28, 24] and given the nature of our problem domain, with extremely low-probability corner cases, the effect of an extremely high variance could bring about bad policy solutions.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, background): “The first “nonconvex use” of variance reduction is by ShalevShwartz [43], who assumes that each fi(x) is nonconvex but their average f(x) is still convex.”
Stochastic quasi-gradient methods: variance reduction via Jacobian sketching (2018, background): “This resulted in primal variants of SDCA such as dual-free SDCA [31].”
Supervised Learning Under Distributed Features (2018, background): “The same difﬁculties mentioned above for the dual methods will again arise if coordinate descent solutions are implemented in the dual domain [23], [32], [33].”
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop (2019, methodology): “Alternative variance-reduced method include MISO (Mairal, 2015), FINITO (Defazio et al., 2014b), SDCA (Shalev-Shwartz, 2016), dfSDCA (Csiba & Richt´arik, 2015), AdaSDCA (Csiba et al., 2015), QUARTZ (Qu et al., 2015), SBFGS (Gower et al., 2016), SDNA (Qu et al., 2016), SARAH (Nguyen et al., 2017) and”
Neon2: Finding Local Minima via First-Order Oracles (2017, methodology): “(8)Shalev-Shwartz [29] first discovered that one can apply SVRG to minimize sum-of-nonconvex functions.”