OlogT Projections for Stochastic Optimization of Smooth and Strongly Convex FunctionsReport as inadecuate



 OlogT Projections for Stochastic Optimization of Smooth and Strongly Convex Functions


OlogT Projections for Stochastic Optimization of Smooth and Strongly Convex Functions - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: OlogT Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
Traditional algorithms for stochastic optimization require projecting the solution at each iteration into a given domain to ensure its feasibility. When facing complex domains, such as positive semi-definite cones, the projection operation can be expensive, leading to a high computational cost per iteration. In this paper, we present a novel algorithm that aims to reduce the number of projections for stochastic optimization. The proposed algorithm combines the strength of several recent developments in stochastic optimization, including mini-batch, extra-gradient, and epoch gradient descent, in order to effectively explore the smoothness and strong convexity. We show, both in expectation and with a high probability, that when the objective function is both smooth and strongly convex, the proposed algorithm achieves the optimal $O1-T$ rate of convergence with only $O\log T$ projections. Our empirical study verifies the theoretical result.



Author: Lijun Zhang; Tianbao Yang; Rong Jin; Xiaofei He

Source: https://archive.org/







Related documents