Efficient Kirszbraun extension with applications to regression
成果类型：
Article
署名作者：
Zaichyk, Hananel; Biess, Armin; Kontorovich, Aryeh; Makarychev, Yury
署名单位：
Ben-Gurion University of the Negev; Toyota Technological Institute - Chicago
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-023-02023-6
发表日期：
2024
页码：
617-642
关键词：
摘要：
We introduce a framework for performing vector-valued regression in finite-dimensional Hilbert spaces. Using Lipschitz smoothness as our regularizer, we leverage Kirszbraun's extension theorem for off-data prediction. We analyze the statistical and computational aspects of this method-to our knowledge, its first application to supervised learning. We decompose this task into two stages: training (which corresponds operationally to smoothing/regularization) and prediction (which is achieved via Kirszbraun extension). Both are solved algorithmically via a novel multiplicative weight updates (MWU) scheme, which, for our problem formulation, achieves significant runtime speedups over generic interior point methods. Our empirical results indicate a dramatic advantage over standard off-the-shelf solvers in our regression setting.