Convex Optimization For Non-Convex Problems via Column Generation
This work addresses approximation challenges in machine learning, particularly for tensor decomposition, but appears incremental as it adapts existing column generation techniques to non-convex problems.
The paper tackles the problem of approximating complex structured objects using a set of primitive structured objects under cross entropy or L2 loss with L1 regularization, resulting in a convex optimization method applied to produce low-rank approximations for large 3-way tensors.
We apply column generation to approximating complex structured objects via a set of primitive structured objects under either the cross entropy or L2 loss. We use L1 regularization to encourage the use of few structured primitive objects. We attack approximation using convex optimization over an infinite number of variables each corresponding to a primitive structured object that are generated on demand by easy inference in the Lagrangian dual. We apply our approach to producing low rank approximations to large 3-way tensors.