# Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity

arXiv: https://arxiv.org/abs/1606.03841 · HTML: https://mlsanity.com/paper/1606.03841/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2016.

## Built on by (most cited first, 5 of 5)

- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [DC-LA: Difference-of-Convex Langevin Algorithm](https://mlsanity.com/paper/2601.22932/) (2026)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Learning Multi-Attribute Differential Graphs with Non-Convex Penalties](https://mlsanity.com/paper/2505.09748/) (2025)
- [Generalized Low-Rank Matrix Completion Model with Overlapping Group Error Representation](https://mlsanity.com/paper/2407.08517/) (2024)

## Abstract (arXiv)

The use of convex regularizers allows for easy optimization, though they often produce biased estimation and inferior prediction performance. Recently, nonconvex regularizers have attracted a lot of attention and outperformed convex ones. However, the resultant optimization problem is much harder. In this paper, for a large class of nonconvex regularizers, we propose to move the nonconvexity from the regularizer to the loss. The nonconvex regularizer is then transformed to a familiar convex regularizer, while the resultant loss function can still be guaranteed to be smooth. Learning with the convexified regularizer can be performed by existing efficient algorithms originally designed for convex regularizers (such as the proximal algorithm, Frank-Wolfe algorithm, alternating direction method of multipliers and stochastic gradient descent). Extensions are made when the convexified regularizer does not have closed-form proximal step, and when the loss function is nonconvex, nonsmooth. Extensive experiments on a variety of machine learning application scenarios show that optimizing the transformed problem is much faster than running the state-of-the-art on the original problem.