On variance reduction for stochastic smooth convex optimization with\n multiplicative noise

2017/05/08 by Alejandro Jofré, Jofré, Alejandro, Philip E. Thompson +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1705.02969

openalex publication_date 2017/05/08 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

Abstract

We propose dynamic sampled stochastic approximation (SA) methods for\nstochastic optimization with a heavy-tailed distribution (with finite 2nd\nmoment). The objective is the sum of a smooth convex function with a convex\nregularizer. Typically, it is assumed an oracle with an upper bound \σ²\non its variance (OUBV). Differently, we assume an oracle with\n\multiplicative noise. This rarely addressed setup is more aggressive but\nrealistic, where the variance may not be bounded. Our methods achieve optimal\niteration complexity and (near) optimal oracle complexity. For the smooth\nconvex class, we use an accelerated SA method a la FISTA which achieves, given\ntolerance \ε>0, the optimal iteration complexity of\n\O(\ε^-\(1)/(2)) with a near-optimal oracle complexity of\n\O(\ε^-2)[\ln(\ε^-\(1)/(2))]². This improves\nupon Ghadimi and Lan [\Math. Program., 156:59-99, 2016] where it is\nassumed an OUBV. For the strongly convex class, our method achieves optimal\niteration complexity of \O(\ln(\ε^-1)) and optimal oracle\ncomplexity of \O(\ε^-1). This improves upon Byrd et al.\n[\Math. Program., 134:127-155, 2012] where it is assumed an OUBV. In\nterms of variance, our bounds are local: they depend on variances\n\σ(x^*)² at solutions x^* and the per unit distance multiplicative\nvariance \σ²_L. For the smooth convex class, there exist policies such\nthat our bounds resemble those obtained if it was assumed an OUBV with\n\σ²:=\σ(x^*)². For the strongly convex class such property is\nobtained exactly if the condition number is estimated or in the limit for\nbetter conditioned problems or for larger initial batch sizes. In any case, if\nit is assumed an OUBV, our bounds are thus much sharper since typically\n\max \σ(x^*)²,\σ_L² \≪\σ².\n

Cited by

• Complexity guarantees for risk-neutral generalized Nash equilibrium problems

Related

• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation
• Variance-Reduced Accelerated First-order Methods: Central Limit Theorems and Confidence Statements
• Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
• Can SGD Handle Heavy-Tailed Noise?