Stochastic Optimization for Non-convex Inf-Projection Problems

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.

References in corpus (7)

• Empirical Bernstein Bounds and Sample Variance Penalization
• Positive-Unlabeled Learning with Non-Negative Risk Estimator
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• Learning with Non-Convex Truncated Losses by SGD
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions