A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
We study gapped scale-sensitive dimensions of a function class in both sequential and non-sequential settings. We demonstrate that covering numbers for any uniformly bounded class are controlled above by these gapped dimensions, generalizing the results of \cite{anthony2000function,alon1997scale}. Moreover, we show that the gapped dimensions lead to lower bounds on offset Rademacher averages, thereby strengthening existing approaches for proving lower bounds on rates of convergence in statistical and online learning.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates
This paper studies additive regret in the multi-secretary problem, defined as the gap between the expected offline prophet reward and the reward of the best online policy. Prior work established \(O(\log T)\) regret for …
Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions
We present a new general-purpose algorithm for learning classes of $[0,1]$-valued functions in a generalization of the prediction model, and prove a general upper bound on the expected absolute error of this algorithm in…
PredictionOn Convex Optimization with Semi-Sensitive Features
We study the differentially private (DP) empirical risk minimization (ERM) problem under the semi-sensitive DP setting where only some features are sensitive. This generalizes the Label DP setting where only the label is…
Query lower bounds for log-concave sampling
Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving lower bounds for this task has remained elusive, with lower bounds previously known only in dim…
On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
We study the problem of sequential probability assignment under logarithmic loss, both with and without side information. Our objective is to analyze the minimax regret -- a notion extensively studied in the literature -…