2021/10/31 by Kaan Gökcesu, Kaan Gokcesu, Gokcesu, Kaan +3
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #Computational Complexity (cs.CC) #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #cs.CC #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2111.00468
arxiv created 2021/10/31 · openalex publication_date 2021/10/31 · arxiv updated 2021/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate the calibration of estimations to increase performance with an optimal monotone transform on the estimator outputs. We start by studying the traditional square error setting with its weighted variant and show that the optimal monotone transform is in the form of a unique staircase function. We further show that this staircase behavior is preserved for general strictly convex loss functions. Their optimal monotone transforms are also unique, i.e., there exist a single staircase transform that achieves the minimum loss. We propose a linear time and space algorithm that can find such optimal transforms for specific loss settings. Our algorithm has an online implementation where the optimal transform for the samples observed so far are found in linear space and amortized time when the samples arrive in an ordered fashion. We also extend our results to cases where the functions are not trivial to individually optimize and propose an anytime algorithm, which has linear space and pseudo-linearithmic time complexity.