  


``RelativeContinuity'' for NonLipschitz NonSmooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent
Haihao Lu(haihaomit.edu) Abstract: The usual approach to developing and analyzing firstorder methods for nonsmooth (stochastic or deterministic) convex optimization assumes that the objective function is uniformly Lipschitz continuous with parameter $M_f$. However, in many settings the nondifferentiable convex function $f(\cdot)$ is not uniformly Lipschitz continuous  for example (i) the classical support vector machine (SVM) problem, (ii) the problem of minimizing the maximum of convex quadratic functions, and even (iii) the univariate setting with $f(x) := \max\{0, x\} + x^2$. Herein we develop a notion of ``relative continuity'' that is determined relative to a userspecified ``reference function'' $h(\cdot)$ (that should be computationally tractable for algorithms), and we show that many nondifferentiable convex functions are relatively continuous with respect to a correspondingly fairlysimple reference function $h(\cdot)$. We also similarly develop a notion of ``relative stochastic continuity'' for the stochastic setting. We analysis two standard algorithms  the (deterministic) mirror descent algorithm and the stochastic mirror descent algorithm  for solving optimization problems in these two new settings, and we develop for the first time computational guarantees for instances where the objective function is not uniformly Lipschitz continuous. This paper is a companion paper for nondifferentiable convex optimization to the recent paper by Lu, Freund, and Nesterov, which developed similar sorts of results for differentiable convex optimization. Keywords: largescale optimization, stochastic firstorder methods, nonLipschitz nonsmooth optimization, mirror descent Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: MIT Operations Research Center Working Paper Download: [PDF] Entry Submitted: 10/12/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  