Error bounds and convergence analysis of feasible descent methods: a general approach

By Zhi-Quan Tom Luo, Paul Tseng. 1993

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

Hybrid Deterministic-Stochastic Methods for Data Fitting (2011, background): “Gradient descent with a decreasing sequence of errors in the gradient measurement was previously analyzed by Luo and Tseng [18], and they present analogous weak and strong linear convergence results depending on the sequence of bounds on the noise.”
Coordinate descent algorithms (2015, background): “…Rheinboldt [40, Section 14.6] included a comprehensive discussion of “univariate relaxation,” and such optimization specialists as Luo and Tseng [30,31], Tseng [55], and Bertsekas and Tsitsiklis [5] made important contributions to understanding the convergence properties of these methods in the…”
Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems (2020, background): “…[2016], PL condition is weaker, or not stronger, than other well-known conditions that guarantee linear convergence for gradient descent, such as error bounds (EB) [Luo and Tseng, 1993], weak strong convexity (WSC) [Necoara et al., 2018] and restricted secant inequality (RSI) [Zhang and Yin, 2013].”
A coordinate gradient descent method for nonsmooth separable minimization (2008, methodology): “Under C3, a similar argument using [28, Theorem 4.1] (also see [ 29, Theorem 2.1 ]) proves (44).”
Incrementally Updated Gradient Methods for Constrained and Regularized Optimization (2013, background): “Assumption 6.1(b) holds automatically if f is convex or f is quadratic and P is polyhedral; see [20, 30] for further discussions.”
On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization (2013, methodology): “Once we have such a bound, a routine application of the powerful analysis framework developed by Luo and Tseng [10] will yield the desired linear convergence result.”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, unknown): “O C ]”
Improvements on Twin Support Vector Machines (2011, methodology): “Furthermore, it has been proved that this algorithm converges linearly to a solution [15].”
Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets (1998, methodology): “Luo and Tseng [43] establish linear convergence of the Gauss{Seidel scheme using their generalresult.”
Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, methodology): “We extend the well known framework of Feasible Descent Methods (FDM) (Luo and Tseng 1993) to randomized and randomized coordinate FDM and show that the SCDM algorithm fits into our new proposed framework.”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “Under the EB condition, asymptotic linear and even superlinear convergence can be established for various methods, including interior point, gradient projection, proximal minimization, coordinate minimization, and coordinate gradient methods – even if X̄ is unbounded; see [12, 49, 80, 81, 139, 144, ”
The Physical Systems Behind Optimization Algorithms (2016, background): “These conditions have been shown to hold for many optimization problems in machine learning and faster convergence rates have been established (e.g. Luo and Tseng (1993); Liu and Wright (2015); Necoara et al. (2015); Zhang and Yin (2013); Liu and Wright (2015); Gong and Ye (2014); Karimi et al.…”
Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling (2020, background): “For some τ > 0 and all x ∈ R d , we have This kind of error bound is standard in the literature on variational inequalities for deriving last iterate convergence rates [see e.g., 7, 19, 20, 37, 38].”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, background): “…[Leventhal and Lewis, 2010], for boosting algorithms [R¨atsch et al., 2001], and for scenarios without strong-convexity under general error bounds [Luo and Tseng, 1993]. where each g i and f ij are diﬀerentiable and G = { V, E } is a graph where the number of vertices | V | is the same as the…”
Some recent advances in projection-type methods for variational inequalities (2003, methodology): “Solodov and Svaiter [100,101] and Tseng [114] combined the PPA with extragradient algorithms.”
Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization (2009, background): “X is locally in the order of the norm of the residual at x ;s ee [27, 35, 36 ] and references therein.”
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods (2016, methodology): “More recent techniques, originally highlighted in the work of Luo and Tseng [17], postulate that the step length at each iteration of the algorithm linearly bounds the error.”