Incremental Gradient Algorithms with Stepsizes Bounded Away from Zero

By M. Solodov. 1998

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

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, neutral): “Other related work has used the strong growth condition to prove convergence rates for incremental gradient methods [34, 38].”
Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition (2013, neutral): “Under condition (5), Solodov [1998] and Tseng [1998] have analyzed convergence properties of deterministic incremental gradient methods.”
On the linear convergence of the projected stochastic gradient method with constant step-size (2017, methodology): “h σ = 2Ei k [k∇fi k (x∗)k2]. In the general case of fi. The condition (3.1) is satisﬁed when (∀i ∈ {1,...,n})(∀x ∈ C) k∇fi(x)k2 ≤ Mk∇f(x)k2. (3.5) 4 Conclusions The strong growth condition is used in [14] where the incremental gradient method converges with a suﬃciently small constant step size and ”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “Convergence of IG methods has been long studied under various conditions (Zhi-Quan & Paul, 1994; Mangasari-any & Solodovy, 1994; Bertsekas, 1996; Solodov, 1998; Tseng, 1998), however IG’s convergence rate has been characterized only more recently (see (Bertsekas, 2015b) for a survey).”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “Indeed, up until the recent work of Bach andMoulines [3], convergence of the basic SGmethod with a constant step size had only been shown for the strongly-convex quadratic case (with averaging of the iterates) [47], or under extremely strong assumptions about the relationship between the functions f”
On the Convergence Rate of Incremental Aggregated Gradient Algorithms (2015, methodology): “1) even if it is applied to smooth and strongly convex component functions [4], unless a restrictive “gradient growth condition” holds [27].”
Stochastic Structured Prediction under Bandit Feedback (2016, methodology): “The models use a standard set of dense and lexicalized sparse features, including an out-of and an in(3)For constant learning rates, [21] show even faster convergence in the search phase of strongly-convex stochastic optimization.”
Sliced and Radon Wasserstein Barycenters of Measures (2014, unknown): “For a convex energy, this property is known to imply convergence of stochastic gradient descent with a fixed step size, see [31].”
Designing games for distributed optimization (2011, methodology): “g, subgradient methods [21]–[26], consensus based methods [1], [2], [27], or two-step consensus based approaches [9], [28], is predicated on the structure of the system level objective.”
Better Theory for SGD in the Nonconvex World (2020, methodology): “Like maximal growth, variants of this condition have also been used in convergence results for incremental gradient methods (Solodov, 1998).”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “,m} and stepsize αk > 0 either constant or adjusted dynamically; see [15, 68, 77, 85, 91, 128, 137] and references therein.”
Incremental Stochastic Subgradient Algorithms for Convex Optimization (2008, methodology): “The incremental method was originally proposed by Kibardin [11] and has been extensively studied more recently in [4, 7, 17, 20, 33].”