Preprint
Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints
ArXiv.org
08/05/2019
DOI: 10.48550/arxiv.1908.01871
Abstract
Optimization models with non-convex constraints arise in many tasks in
machine learning, e.g., learning with fairness constraints or Neyman-Pearson
classification with non-convex loss. Although many efficient methods have been
developed with theoretical convergence guarantees for non-convex unconstrained
problems, it remains a challenge to design provably efficient algorithms for
problems with non-convex functional constraints. This paper proposes a class of
subgradient methods for constrained optimization where the objective function
and the constraint functions are weakly convex and nonsmooth. Our methods solve
a sequence of strongly convex subproblems, where a quadratic regularization
term is added to both the objective function and each constraint function. Each
subproblem can be solved by various algorithms for strongly convex
optimization. Under a uniform Slater's condition, we establish the computation
complexities of our methods for finding a nearly stationary point.
Details
- Title: Subtitle
- Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints
- Creators
- Runchao Ma - University of IowaQihang Lin - University of IowaTianbao Yang - University of Iowa
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.1908.01871
- ISSN
- 2331-8422
- Language
- English
- Date posted
- 08/05/2019
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380600302771
Metrics
7 Record Views