2023/06/08 by Andrew Jacobsen, Jacobsen, Andrew, Ashok Cutkosky +1 · 6 citations
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2306.04923
Algorithms for online learning typically require one or more boundedness assumptions: that the domain is bounded, that the losses are Lipschitz, or both. In this paper, we develop a new setting for online learning with unbounded domains and non-Lipschitz losses. For this setting we provide an algorithm which guarantees RT(u)≤ O(G‖u‖√(T)+L‖u‖2√(T)) regret on any problem where the subgradients satisfy ‖gt‖≤ G+L‖wt‖, and show that this bound is unimprovable without further assumptions. We leverage this algorithm to develop new saddle-point optimization algorithms that converge in duality gap in unbounded domains, even in the absence of meaningful curvature. Finally, we provide the first algorithm achieving non-trivial dynamic regret in an unbounded domain for non-Lipschitz losses, as well as a matching lower bound. The regret of our dynamic regret algorithm automatically improves to a novel L* bound when the losses are smooth.