Near-optimal Swap Regret Minimization for Convex Losses

• URL: http://arxiv.org/abs/2602.08862v1
• Date: Mon, 09 Feb 2026 16:26:34 GMT
• Title: Near-optimal Swap Regret Minimization for Convex Losses
• Authors: Lunjia Hu, Jon Schneider, Yifan Wu,
• Abstract summary: We give a randomized online algorithm that guarantees near-optimal $widetilde O(sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval.
• Score: 21.006993033547708
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a randomized online algorithm that guarantees near-optimal $\widetilde O(\sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $\widetilde O(T^{2/3})$ and answers an open question of Fishelson et al. [2025b]. In addition, our algorithm is efficient: it runs in $\mathsf{poly}(T)$ time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first $\widetilde O(\sqrt T)$ calibration error guarantee.

Related papers

• Online Conformal Prediction with Efficiency Guarantees [2.0305676256390934]
  We study the problem of conformal prediction in a novel online framework.<n>In our problem, we are given a target miscoverage rate $alpha > 0$, and a time horizon $T$.
  arXiv  Detail & Related papers  (2025-07-03T10:00:50Z)
• Improved Bounds for Swap Multicalibration and Swap Omniprediction [31.959887895880765]
  We show that it is possible to efficiently achieve $O(sqrtT)$ $ell_2$-swap multicalibration error against bounded linear functions.<n>We also establish a $O(varepsilon -3)$ sample complexity of efficiently learning an $varepsilon$-swap omnipredictor for the class of convex and Lipschitz functions.
  arXiv  Detail & Related papers  (2025-05-27T08:29:35Z)
• High dimensional online calibration in polynomial time [17.45683822446751]
  In online (sequential) calibration, a forecaster predicts probability distributions over a finite outcome space $[d]$ over a sequence of $T$ days.<n>Best known algorithms require $exp(d)$ days to achieve non-trivial calibration.<n>We present the firstally calibrated strategy that guarantees non-trivial algorithm calibration after a number of rounds.
  arXiv  Detail & Related papers  (2025-04-12T06:28:05Z)
• Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span [16.49229317664822]
  This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of $widetildemathcalO(dsqrtmathrmsp(v*)T)$ over $T$ time steps.
  arXiv  Detail & Related papers  (2024-10-19T05:45:50Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Oblivious Stochastic Composite Optimization [47.48197617884748]
  We show that our algorithms converge without any prior knowledge on the parameters of the problem.<n>All three algorithms work without prior knowledge of the diameter of the feasible set, the Lipschitz constant or smoothness of the objective function.<n>We extend our framework to relative scale and demonstrate the efficiency and robustness of our methods on large-scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Private Isotonic Regression [54.32252900997422]
  We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
  arXiv  Detail & Related papers  (2022-10-27T05:08:07Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model. The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
  arXiv  Detail & Related papers  (2022-08-11T04:12:50Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  We study the problem of finding a basis $S$ of $M$ such that $det(sum_i in Sv_i v_i v_itop)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning.
  arXiv  Detail & Related papers  (2020-04-16T19:16:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.