Unified Methods for Exploiting Piecewise Linear Structure in Convex Optimization
We develop methods for rapidly identifying important components of a convex optimization problem for the purpose of achieving fast convergence times. By considering a novel problem formulation—the minimization of a sum of piecewise functions—we describe a principled and general mechanism for exploiting piecewise linear structure in convex optimization. This result leads to a theoretically justified working set algorithm and a novel screening test, which generalize and improve upon many prior results on exploiting structure in convex optimization. In empirical comparisons, we study the scalability of our methods. We find that screening scales surprisingly poorly with the size of the problem, while our working set algorithm convincingly outperforms alternative approaches.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Unified View of Piecewise Linear Neural Network Verification
The success of Deep Learning and its potential use in many safety-critical applications has motivated research on formal verification of Neural Network (NN) models. Despite the reputation of learned NN models to behave a…
A piecewise ellipsoidal reachable set estimation method for continuous bimodal piecewise affine systems
In this work, the issue of estimation of reachable sets in continuous bimodal piecewise affine systems is studied. A new method is proposed, in the framework of ellipsoidal bounding, using piecewise quadratic Lyapunov fu…
The Self-Simplifying Machine: Exploiting the Structure of Piecewise Linear Neural Networks to Create Interpretable Models
Today, it is more important than ever before for users to have trust in the models they use. As Machine Learning models fall under increased regulatory scrutiny and begin to see more applications in high-stakes situation…
Tailored neural networks for learning optimal value functions in MPC
Learning-based predictive control is a promising alternative to optimization-based MPC. However, efficiently learning the optimal control policy, the optimal value function, or the Q-function requires suitable function a…
DAPA: Distribution Aware Piecewise Activation Functions for On-Device Transformer Inference and Training
Non-linear activation functions play a pivotal role in on-device inference and training, as they not only consume substantial hardware resources but also impose a significant impact on system performance and energy effic…