2013/04/02 by Lijun Zhang, Tianbao Yang, Zhang, Lijun +5
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1304.0740
openalex publication_date 2013/04/02 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Traditional algorithms for stochastic optimization require projecting the\nsolution at each iteration into a given domain to ensure its feasibility. When\nfacing complex domains, such as positive semi-definite cones, the projection\noperation can be expensive, leading to a high computational cost per iteration.\nIn this paper, we present a novel algorithm that aims to reduce the number of\nprojections for stochastic optimization. The proposed algorithm combines the\nstrength of several recent developments in stochastic optimization, including\nmini-batch, extra-gradient, and epoch gradient descent, in order to effectively\nexplore the smoothness and strong convexity. We show, both in expectation and\nwith a high probability, that when the objective function is both smooth and\nstrongly convex, the proposed algorithm achieves the optimal O(1/T) rate of\nconvergence with only O(\log T) projections. Our empirical study verifies the\ntheoretical result.\n