Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements

2021/07/16 by Antonakopoulos, Kimon, Mertikopoulos, Panayotis
#90C15 #90C30 #90C60 #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Primary 90C25 #secondary 68Q25

paper · doi:10.48550/arxiv.2107.08011

Abstract

We propose a new family of adaptive first-order methods for a class of convex minimization problems that may fail to be Lipschitz continuous or smooth in the standard sense. Specifically, motivated by a recent flurry of activity on non-Lipschitz (NoLips) optimization, we consider problems that are continuous or smooth relative to a reference Bregman function - as opposed to a global, ambient norm (Euclidean or otherwise). These conditions encompass a wide range of problems with singular objectives, such as Fisher markets, Poisson tomography, D-design, and the like. In this setting, the application of existing order-optimal adaptive methods - like UnixGrad or AcceleGrad - is not possible, especially in the presence of randomness and uncertainty. The proposed method - which we call adaptive mirror descent (AdaMir) - aims to close this gap by concurrently achieving min-max optimal rates in problems that are relatively continuous or smooth, including stochastic ones.

Related

• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Adaptive algorithms for mirror descent in convex programming problems\n with Lipschitz constraints
• Accelerated Bregman gradient methods for relatively smooth and relatively Lipschitz continuous minimization problems
• On Modification of an Adaptive Stochastic Mirror Descent Algorithm for Convex Optimization Problems with Functional Constraints
• Adaptive Algorithms for Relatively Lipschitz Continuous Convex Optimization Problems