Projected semi-stochastic gradient descent method with mini-batch scheme under weak strong convexity assumption

DOI10.1007/978-3-319-66616-7_7MaRDI QIDQ1695084zbMATH OpenOpenAlexFDO

Authors Jie Liu, M. Takáč

Publication date 6 February 2018

Full work available at URL https://arxiv.org/abs/1612.05356

zbMATH Keywords

stochastic gradientvariance reductionlinear convergencesupport vector machine (SVM)weak strong convexity

Mathematics Subject Classification ID

Stochastic programming (90C15) Existence of optimal solutions to problems involving randomness (49J55) Optimal stochastic control (93E20) Duality theory (optimization) (49N15)

Abstract: We propose a projected semi-stochastic gradient descent method with mini-batch for improving both the theoretical complexity and practical performance of the general stochastic gradient descent method (SGD). We are able to prove linear convergence under weak strong convexity assumption. This requires no strong convexity assumption for minimizing the sum of smooth convex functions subject to a compact polyhedral set, which remains popular across machine learning community. Our PS2GD preserves the low-cost per iteration and high optimization accuracy via stochastic gradient variance-reduced technique, and admits a simple parallel implementation with mini-batches. Moreover, PS2GD is also applicable to dual problem of SVM with hinge loss.

Recommendations

• Semi-stochastic coordinate descent
• A proximal stochastic gradient method with progressive variance reduction
• Asymptotic estimates for \(r\)-Whitney numbers of the second kind
• Stochastic model-based minimization of weakly convex functions
• Improved SVRG for finite sum structure optimization with application to binary classification

Cited in

(2)

• Sign stochastic gradient descents without bounded gradient assumption for the finite sum minimization
• A framework of convergence analysis of mini-batch stochastic projected gradient methods

This page was built for publication: Projected semi-stochastic gradient descent method with mini-batch scheme under weak strong convexity assumption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1695084)