Efficient Online Proportional Sampling with Applications to Smoothed Online Learning

• URL: http://arxiv.org/abs/2607.10963v1
• Date: Mon, 13 Jul 2026 00:16:17 GMT
• Title: Efficient Online Proportional Sampling with Applications to Smoothed Online Learning
• Abstract summary: We study the problem of efficient online proportional sampling from a high-dimensional domain under a $$-smoothed adversary.<n>This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design)<n>We prove a tight $O(sqrtT)$ bound on the depth of our data structure, and an $O(log T)$ bound under a random-order adversary.
• Score: 17.03942758909167
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of efficient online proportional sampling from a high-dimensional domain under a $σ$-smoothed adversary, where the sampling distribution is induced by a dynamically evolving weight function defined over a sequence of piecewise-structured partitions. This setting captures a broad range of applications, including principal-agent games (e.g., pricing and contract design), and algorithm configuration and parameter tuning. The central challenge is maintaining an efficient data structure as the induced partition grows increasingly complex over time -- naively, the number of subregions can grow as $O(t^d)$ by round $t$ in $d$ dimensions. We design a data structure that supports efficient updates and proportional sampling while avoiding the cost of explicitly maintaining this exponential growth, where the discontinuities are structured from axis-parallel hyperplanes. Under a $σ$-smoothed adaptive adversary, we prove a tight $O(\sqrt{σT})$ bound on the depth of our data structure, and an $O(\log T)$ bound under a random-order adversary -- to our knowledge, the first such results for this class of problems. We apply this framework to online learning with piecewise-structured rewards, obtaining efficient no-regret algorithms under both full-information and bandit feedback, with provable sublinear regret guarantees.

Related papers

• Denoising growth complexity: Data geometry and certified schedules for diffusion sampling [14.877292137182422]
  We show how the $mathsfDGC$ increments lead to a simple and explicit bound on the KL error of an Euler scheme applied to the innovations representation.<n>We derive KL sampling guarantees for optimized stepsize schedules, both in a simpler single-block setting and in a more refined $K$-block setting.
  arXiv  Detail & Related papers  (2026-07-28T21:26:16Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  We propose textbfLighter-X, an efficient and modular framework that can be seamlessly integrated with existing GNN-based recommender architectures.<n>Our approach substantially reduces both parameter size and computational complexity while preserving the theoretical guarantees and empirical performance of the base models.<n>Experiments demonstrate that Lighter-X achieves comparable performance to baseline models with significantly fewer parameters.
  arXiv  Detail & Related papers  (2025-10-11T08:33:08Z)
• Online Learning of Whittle Indices for Restless Bandits with Non-Stationary Transition Kernels [24.314013749328677]
  We study optimal resource allocation in restless multi-armed bandits (RMABs) under unknown and non-stationary dynamics.<n>We propose a Sliding-Window Online Whittle (SW-Whittle) policy that remains computationally efficient while adapting to time-varying kernels.<n>Our algorithm consistently outperforms baselines, achieving the lowest cumulative regret across a range of non-stationary environments.
  arXiv  Detail & Related papers  (2025-06-22T22:04:52Z)
• Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration [6.287267171078442]
  We propose variance-aware algorithms that leverage neural networks to approximate nonlinear utility functions.<n>We establish theoretical guarantees showing that our algorithms achieve sublinear cumulative average regret of order $bigollt(d sqrtsum_t=1T sigma_t2 + sqrtdTrt),$ for sufficiently wide neural networks.
  arXiv  Detail & Related papers  (2025-06-02T01:58:48Z)
• Gaussian Ensemble Belief Propagation for Efficient Inference in High-Dimensional Systems [3.6773638205393198]
  Efficient inference in high-dimensional models is a central challenge in machine learning.<n>We introduce the Gaussian Ensemble Belief Propagation (GEnBP) algorithm.<n>We show that GEnBP outperforms existing belief methods in terms of accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2024-02-13T03:31:36Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  We present efficient methods for optimizing dynamic regret and adaptive regret.<n>The proposed algorithms require only one gradient query and one function evaluation at each round.<n>We also study an even stronger measure, namely "interval dynamic regret", and reduce the number of projections per round from $O(log2 T)$ to $1$.
  arXiv  Detail & Related papers  (2023-09-16T07:30:12Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Linearly-scalable learning of smooth low-dimensional patterns with permutation-aided entropic dimension reduction [0.0]
  In many data science applications, the objective is to extract appropriately-ordered smooth low-dimensional data patterns from high-dimensional data sets. We show that when selecting the Euclidean smoothness as a pattern quality criterium, both of these problems can be efficiently solved numerically.
  arXiv  Detail & Related papers  (2023-06-17T08:03:24Z)
• Generalization Bounds for Stochastic Gradient Descent via Localized $\varepsilon$-Covers [16.618918548497223]
  We propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific clustering measured by the bounds number. We derive these results in various contexts and improve the known state-of-the-art label rates.
  arXiv  Detail & Related papers  (2022-09-19T12:11:07Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  We introduce novel online algorithms that can exploit smoothness and replace the dependence on $T$ in dynamic regret with problem-dependent quantities. Our results are adaptive to the intrinsic difficulty of the problem, since the bounds are tighter than existing results for easy problems and safeguard the same rate in the worst case.
  arXiv  Detail & Related papers  (2021-12-29T02:42:59Z)
• Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks [42.43493635899849]
  We establish theoretical guarantees of convolutional residual networks (ConvResNet) in terms of function approximation and statistical estimation for binary classification. Our results demonstrate that ConvResNets are adaptive to low-dimensional structures of data sets.
  arXiv  Detail & Related papers  (2021-09-07T02:58:11Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• $P^2$ Net: Augmented Parallel-Pyramid Net for Attention Guided Pose Estimation [69.25492391672064]
  We propose an augmented Parallel-Pyramid Net with feature refinement by dilated bottleneck and attention module. A parallel-pyramid structure is followed to compensate the information loss introduced by the network. Our method achieves the best performance on the challenging MSCOCO and MPII datasets.
  arXiv  Detail & Related papers  (2020-10-26T02:10:12Z)

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.