Efficiency of minimizing compositions of convex functions and smooth maps

2016/04/30 by Dmitriy Drusvyatskiy, Drusvyatskiy, Dmitriy, Courtney Paquette +1 · 18 citations
Computer Science · Engineering · Mathematics · #90C06 #90C25 #90C30 #97N60 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #math.OC #msc:90C06 #msc:90C25 #msc:90C30 #msc:97N60

paper · pdf · doi:10.48550/arxiv.1605.00125

openalex publication_date 2016/04/30 · arxiv created 2017/08/14 · arxiv updated 2017/08/16 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the subproblems are solved exactly, the method has efficiency O(ε^-2), akin to gradient descent for smooth minimization. We show that when the subproblems can only be solved by first-order methods, a simple combination of smoothing, the prox-linear method, and a fast-gradient scheme yields an algorithm with complexity \widetildeO(ε^-3). The technique readily extends to minimizing an average of m composite functions, with complexity \widetildeO(m/ε²+√(m)/ε³) in expectation. We round off the paper with an inertial prox-linear method that automatically accelerates in presence of convexity.

Cited by

• A Proximal Method for Composite Optimization with Smooth and Convex Components
• A Smooth Approximation Framework for Weakly Convex Optimization
• Verification of Sequential Convex Programming for Parametric Non-convex Optimization
• Distributed Stochastic Proximal Algorithm on Riemannian Submanifolds for Weakly-convex Functions
• Optimization Outperforms Unscented Techniques for Nonlinear Smoothing
• A √(2)-accelerated FISTA for composite strongly convex problems
• An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization
• Some New Insights from Highly Optimized Polyhedral Passages
• Sequential Convex Programming for 6-DoF Powered Descent Guidance with Continuous-Time Compound State-Triggered Constraints
• A New Inexact Manifold Proximal Linear Algorithm with Adaptive Stopping Criteria
• Sequential Convex Programming with Filtering-Based Warm-Starting for Continuous-Time Multiagent Quadrotor Trajectory Optimization
• Can SGD Handle Heavy-Tailed Noise?
• Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises
• Beyond Scores: Proximal Diffusion Models
• Efficient Methods for Min-Max Optimization with Dual-Linear Coupling
• A Proximal Variable Smoothing for Minimization of Nonlinearly Composite Nonsmooth Function -- Finite-Max Minimization and MIMO Applications
• Distributed Stochastic Optimization for Non-Smooth and Weakly Convex Problems under Heavy-Tailed Noise
• Optimal Deterministic Oracle Complexity for Weakly Convex Optimization
• Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints

Related

• Tight Complexity Bounds for Optimizing Composite Objectives
• Smoothing technique for nonsmooth composite minimization with linear operator
• Proximal methods for minimizing the sum of a convex function and a composite function
• A Note on Complexity for Two Classes of Structured Non-Smooth Non-Convex Compositional Optimization
• On Optimal Universal First-Order Methods for Minimizing Heterogeneous Sums