Online learning of smooth functions on $\mathbb{R}$

• URL: http://arxiv.org/abs/2604.03525v1
• Date: Sat, 04 Apr 2026 00:08:22 GMT
• Title: Online learning of smooth functions on $\mathbb{R}$
• Abstract summary: We study adversarial online learning of real-valued functions on $mathbbR$.<n>For every $p$-loss $sum_tge 1|hat y_t-f(x_t)|p$, an adversary can force infinite loss.
• Score: 46.81931064034358
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study adversarial online learning of real-valued functions on $\mathbb{R}$. In each round the learner is queried at $x_t\in\mathbb{R}$, predicts $\hat y_t$, and then observes the true value $f(x_t)$; performance is measured by cumulative $p$-loss $\sum_{t\ge 1}|\hat y_t-f(x_t)|^p$. For the class \[ \mathcal{G}_q=\Bigl\{f:\mathbb{R}\to\mathbb{R}\ \text{absolutely continuous}:\ \int_{\mathbb{R}}|f'(x)|^q\,dx\le 1\Bigr\}, \] we show that the standard model becomes ill-posed on $\mathbb{R}$: for every $p\ge 1$ and $q>1$, an adversary can force infinite loss. Motivated by this obstruction, we analyze three modified learning scenarios that limit the influence of queries that are far from previously observed inputs. In Scenario 1 the adversary must choose each new query within distance $1$ of some past query. In Scenario 2 the adversary may query anywhere, but the learner is penalized only on rounds whose query lies within distance $1$ of a past query. In Scenario 3 the loss in round $t$ is multiplied by a weight $g(\min_{j<t}|x_t-x_j|)$. We obtain sharp characterizations for Scenarios 1-2 in several regimes. For Scenario 3 we identify a clean threshold phenomenon: if $g$ decays too slowly, then the adversary can force infinite weighted loss. In contrast, for rapidly decaying weights such as $g(z)=e^{-cz}$ we obtain finite and sharp guarantees in the quadratic case $p=q=2$. Finally, we study a natural multivariable slice generalization $\mathcal{G}_{q,d}$ of $\mathcal{G}_q$ on $\mathbb{R}^d$ and show a sharp dichotomy: while the one-dimensional case admits finite opt-values in certain regimes, for every $d\ge 2$ the slice class $\mathcal{G}_{q,d}$ is too permissive, and even under Scenarios 1-3 an adversary can force infinite loss.

Related papers

• Exact Risk Ratios for Weighted Data Selection in Linear Regression [0.0]
  Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed the following open problem.<n>A selector sees a finite dataset $D subseteq mathbbRd times mathbbR$, picks at most $n$ examples together with nonnegative weights, and hands the weighted least squares objective to the minimum-norm ERM.<n>We give explicit counterexamples showing that several shorter routes fail, and constructive sign-time selection algorithms for all proved cases.
  arXiv  Detail & Related papers  (2026-08-28T07:19:17Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs [25.375074054942434]
  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
  arXiv  Detail & Related papers  (2026-07-22T15:15:28Z)
• High-Dimensional Calibration from Swap Regret [40.9736612423411]
  We study the online calibration of multi-dimensional forecasts over an arbitrary convex set $mathcalP subset mathbbRd$.<n>We show that if it is possible to guarantee $O(sqrtrho T)$ worst-case regret after $T$ rounds, it is possible to obtain $epsilon$-calibrated forecasts after $T = exp(logd/epsilon2).
  arXiv  Detail & Related papers  (2025-05-27T17:31:47Z)
• Worst-case Error Bounds for Online Learning of Smooth Functions [0.0]
  We investigate worst-case error for the online learning of real functions that have certain smoothness constraints.<n>We prove for all $p, q ge 2$ and $eta ge 1$ that $operatornameopttextnf_p, eta (mathcalF_q)$ is finite.<n>We also define a noisy model for the online learning of smooth functions, where the learner may receive incorrect feedback up to $eta ge 1$ times.
  arXiv  Detail & Related papers  (2025-02-23T00:43:10Z)
• Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
  We show that when $rho$ is concentrated near an $mtext-d$ set we may interpret this as a manifold learning problem with noisy data.<n>We quantify $nu$'s performance in approximating $rho$ via the Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$, and constrain the complexity by requiring $mathrmsupp nu$ to be coverable by an $f : mathbbRm
  arXiv  Detail & Related papers  (2024-09-25T01:30:16Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  In this work we aim to characterize the smallest achievable error $epsilon=epsilon(eta)$ by the learner in the presence of such an adversary. Remarkably, we show that the upper bound can be attained by a deterministic learner.
  arXiv  Detail & Related papers  (2022-10-06T06:49:48Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  tightest statistical query (SQ) lower bounds for learnining halfspaces in the presence of Massart noise. We show that for arbitrary $eta in [0,1/2]$ every SQ algorithm achieving misclassification error better than $eta$ requires queries of superpolynomial accuracy.
  arXiv  Detail & Related papers  (2022-01-24T17:33:19Z)
• A note on the price of bandit feedback for mistake-bounded online learning [0.0]
  The standard model and the bandit model are generalizations of the mistake-bound model to online multiclass classification. In both models the learner guesses a classification in each round, but in the standard model the learner recieves the correct classification after each guess. We show that this lemma is false precisely when $s$ and $t$ are multiples of each other mod $p$.
  arXiv  Detail & Related papers  (2021-01-18T06:00:30Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  We study learning in contextual bandits with the help of loss predictors. We show that the optimal regret is $mathcalO(minsqrtT, sqrtmathcalETfrac13)$ when $mathcalE$ is known.
  arXiv  Detail & Related papers  (2020-03-04T07:36: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.