Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs

• URL: http://arxiv.org/abs/2607.20258v1
• Date: Wed, 22 Jul 2026 15:15:28 GMT
• Title: Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs
• Abstract summary: We study regret for learning CDF-related objectives of the form [ g(x)cdotmathbbP_XsimmathcalD(Xle x), ] over $[0,1]2$, where $g$ is a known Lipschitz function and $mathcalD$ is an unknown distribution.<n>We design an algorithm achieving regret $widetildemathcalO(T7/10)$, improving over the previous best-known bound of $widetildemath
• Score: 25.375074054942434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study regret minimization for learning CDF-related objectives of the form \[ g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x), \] over $[0,1]^2$, where $g$ is a known Lipschitz function and $\mathcal{D}$ is an unknown distribution. At each round $t$, the learner selects a point $x_t$ and observes the binary feedback $\mathbb{I}(X_t\le x_t)$, where $X_t\sim\mathcal{D}$. We design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{7/10})$, improving over the previous best-known bound of $\widetilde{\mathcal{O}}(T^{3/4})$ and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the $Ω(T^{2/3})$ lower bound. As an application, our techniques yield the same $\widetilde{\mathcal{O}}(T^{7/10})$ regret bound for profit maximization in repeated bilateral trade with fixed prices.

Related papers

• Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
  We study oracle fixed-point equations $mathbfT(mathbfx) = mathbfx$ over normed spaces.<n>We introduce VR-GHAL, a variance-reduced gradual Halpern method for quadratically smoothable Banach spaces.
  arXiv  Detail & Related papers  (2026-07-10T04:59:20Z)
• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  We develop a unified framework certified Top-$k$ attention truncation that quantifies error at both the distribution and output levels.<n>We show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$.
  arXiv  Detail & Related papers  (2025-12-08T15:36:41Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  We show that the Monotonic Value Omega (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land mathttVar_maxtextc$.
  arXiv  Detail & Related papers  (2025-06-06T20:33:57Z)
• Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [38.551072383777594]
  We study the problem of learning a single neuron with respect to the $L2$ loss in the presence of adversarial distribution shifts. A new algorithm is developed to approximate the vector vector squared loss with respect to the worst distribution that is in the $chi2$divergence to the $mathcalp_0$.
  arXiv  Detail & Related papers  (2024-11-11T03:43:52Z)
• A class of ternary codes with few weights [0.0]
  In this paper, we investigate a ternary code $mathcalC$ of length $n$, defined by $mathcalC$ := (textTr) := (textTr(dx), dots, dots, d_n$. Using recent results on explicit evaluations of exponential sums, we determine the Weil bound, and techniques, we show that the dual code of $mathcalC$ is optimal with respect to the Hamming bound.
  arXiv  Detail & Related papers  (2024-10-05T16:15:50Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets. Two types of structural assumptions lead to better pseudo-regret bounds.
  arXiv  Detail & Related papers  (2021-03-10T07:33:03Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)

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.