Stochastic Optimization for Non-convex Inf-Projection Problems
Preprint
Abstract
In this paper, we study a family of non-convex and possibly non-smooth inf-projection minimization problems, where the target objective function is equal to minimization of a joint function over another variable. This problem include difference of convex (DC) functions and a family of bi-convex functions as special cases. We develop stochastic algorithms and establish their first-order convergence for finding a (nearly) stationary solution of the target non-convex function under different conditions of the component functions. To the best of our knowledge, this is the first work that comprehensively studies stochastic optimization of non-convex inf-projection minimization problems with provable convergence guarantee. Our algorithms enable efficient stochastic optimization of a family of non-decomposable DC functions and a family of bi-convex functions. To demonstrate the power of the proposed algorithms we consider an important application in variance-based regularization. Experiments verify the effectiveness of our inf-projection based formulation and the proposed stochastic algorithm in comparison with previous stochastic algorithms based on the min-max formulation for achieving the same effect.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex ProblemsSIAM Journal on Optimization, 2019
- Stochastic Model-Based Minimization of Weakly Convex FunctionsSIAM Journal on Optimization, 2019
- A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processingIEEE Signal Processing Magazine, 2015
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimizationMathematical Programming, 2014
- Universal gradient methods for convex optimization problemsMathematical Programming, 2014
- Proximal alternating linearized minimization for nonconvex and nonsmooth problemsMathematical Programming, 2013
- A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and CompletionSIAM Journal on Imaging Sciences, 2013
- On the equivalence of weak learnability and linear separability: new relaxations and efficient boosting algorithmsMachine Learning, 2010
- Biconvex sets and optimization with biconvex functions: a survey and extensionsMathematical Methods of Operations Research, 2007