Linear Convergence with Condition Number Independent Access of Full Gradients

By Lijun Zhang, Mehrdad Mahdavi, Rong Jin. 2013

159 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

A Proximal Stochastic Gradient Method with Progressive Variance Reduction (2014, methodology): “A very similar algorithm was proposed by Zhang, Mahdavi, and Jin [34], but with a worse convergence rate analysis.”
Semi-Stochastic Gradient Descent Methods (2013, methodology): “[14], is similar in spirit to SVRG, but achieves a quadratic dependence on the condition number instead of a linear dependence, as is the case with SDCA, SAG, SVRG and with our method.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “The convergence rate of SGD can be further improved with the so-called variance-reduction technique [9, 11, 17, 24, 25, 31, 32, 35, 36].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “The Epoch Mixed Gradient Descent (EMGD) method, [195], is similar in spirit to SVRG, but achieves a quadratic dependence on the condition number instead of a linear dependence, as is the case with SDCA, SAG, SVRG and with our method.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “We ﬁrst recall the main idea of the SVRG method [28, 48], which is an ofﬂine algorithm.”
Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity (2014, background): “To the best of our knowledge, this is the first work that establishest linear convergence rate for the variance-reduced stochastic gradient algorithms on solving both constrained and regularized problems without strong convexity.”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, methodology): “These techniques include importance sampling [4], exploiting neighborhood structure in the training data to share and re-use information about past stochastic gradients [15], incorporating Nesterov’s acceleration techniques [16, 17] or momentum acceleration tricks [18], reducing the number of gradie”
Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives (2015, background): “We show faster convergence results for minimizing such objectives by either directly applying SVRG or modifying it in a novel manner.”
Global convergence of online limited memory BFGS (2014, methodology): “We use the training set to estimate the CTR with a logistic regression as in, e.g., Zhang et al. (2013b).”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, background): “Keywords: coordinate descent; accelerated coordinate descent; arbitrary sampling; complexity analysis”
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy (2016, background): “st of this consequential literature includes Nesterov acceleration [18, 2], stochastic averaging gradient [21, 7], variance reduction [12, 27], dual coordinate methods [24, 25], and hybrid algorithms [28, 13]. When it comes to stochastic second order methods the ﬁrst challenge is that while evaluati”
Projection-Free Adaptive Gradients for Large-Scale Optimization (2020, methodology): “To this end, the Stochastic VarianceReduced Frank-Wolfe algorithm (SVRF) (Hazan and Luo, 2016) integrates variance reduction (Johnson and Zhang, 2013; Zhang et al., 2013) in the estimation of the stochastic gradients to improve the batch-size rate to bt = Θ(t).”
Momentum-Based Variance Reduction in Non-Convex SGD (2019, unknown): “[30], Mahdavi et al.”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, background): “Proposition 5 (Loopless SVRG estimator) .”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, methodology): “Variance reduction (VR) initially emerged as a technique for obtaining fast convergence in large scale optimization problems, for example in the Stochastic Variance Reduction Gradient method (SVRG, [Johnson and Zhang, 2013, Zhang et al., 2013]).”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “In optimization, they were used for ﬁnite-sum minimization by SVRG (Johnson & Zhang, 2013; Zhang et al., 2013a) and then in SAGA (Defazio et al., 2014) to simplify the linearly convergent method SAG (Schmidt et al., 2017).”
Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems (2020, background): “[9], Palaniappan and Bach [34], extend SVRG [20, 51] and SAGA [11] to solving strongly-convex-strongly-concave minimax problem in the finite-sum case, and established a linear convergence.”
Stochastic Gradient Descent with Polyak’s Learning Rate (2019, background): “If variance reduction [JZ13] [ZMJ13] is incorporated, it is reﬂected in the σ 2 term in (6).”