2023/07/26 by Shiliang Zuo, Zuo, Shiliang · 1 citation
Computer Science · Economics, Econometrics and Finance · Social Sciences · #Crime, Illicit Activities, and Governance #FOS: Computer and information sciences #Game Theory and Voting Systems #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.2307.13903
openalex publication_date 2023/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
I study the problem of learning a Lipschitz function with corrupted binary signals. The learner tries to learn a L-Lipschitz function f: [0,1]d → [0, L] that the adversary chooses. There is a total of T rounds. In each round t, the adversary selects a context vector xt in the input space, and the learner makes a guess to the true function value f(xt) and receives a binary signal indicating whether the guess is high or low. In a total of C rounds, the signal may be corrupted, though the value of C is unknown to the learner. The learner's goal is to incur a small cumulative loss. This work introduces the new algorithmic technique agnostic checking as well as new analysis techniques. I design algorithms which: for the symmetric loss, the learner achieves regret L⋅ O(Clog T) with d = 1 and L⋅ Od(Clog T + T(d-1)/d) with d > 1; for the pricing loss, the learner achieves regret L⋅ \widetildeO (Td/(d+1) + C⋅ T1/(d+1)).