The aggregation with exponential weights (AEW) estimator is not fully understood in the basic setting of model selection aggregation with squared loss. In particular, whether it is minimax-rate optimal in expectation for large enough fixed temperatures and under random design has been an open problem since its introduction, which was explicitly posed by Lecu\'{e} and Mendelson (2013). In this paper, we settle this problem by showing that \emph{without} requiring a Bernstein-type assumption, the AEW indeed achieves the excess risk $T \log (M) / (n+1)$ in expectation, whenever the temperature $T$ satisfies $(L^2/T)\exp(B/T)\leq \mu /2$. Here, the number of dictionary elements is $M$, the estimator has observed $n$ i.i.d. samples from any distribution, and the loss is assumed to be bounded by $B$, $L$-Lipschitz continuous and $\mu$-strongly convex. For squared loss, we show that $T\geq 4 b^2$ suffices when the predictions and labels are $[0,b]$-valued. Because AEW is known to be suboptimal in expectation for temperatures below some constant, this shows that AEW has a sharp phase transition when the temperature is large enough but constant, as conjectured by Lecu\'{e} and Mendelson.
Given $[0,1]$-valued random variables $X_1,\dots,X_n$ such that $\mathbb{E}[X_i | X_1,\dots,X_{i-1}]= \mu$ for all $i$, we propose a new nonasymptotic confidence interval for $\mu$ that is obtained by inverting terminal e-values generated by a novel betting strategy. When the data are iid, its limiting width matches that of the central limit theorem (``Gaussian-efficient''), finally surpassing the inefficient limits of previous betting intervals. Our main conceptual advance involves designing betting fractions that track the conditional rejection probability of the most powerful terminal test in a limiting Gaussian experiment. When one predictable variance estimator is shared across candidate means, the deterministic inversion is an interval for every data sequence and its two endpoints can be found easily. The width can be improved further with external randomization. In simulations, our method yields the tightest intervals to date; for every distribution tested and all sufficiently large $n$, our deterministic version beats STaR-Bets and is competitive with Gaffke, while the randomized improvement beats both. It thus combines finite-sample validity under martingale dependence, easy endpoint computation, Gaussian-efficient inference for iid data, and excellent empirical performance. We also extend the construction and its efficiency theory to sampling without replacement, where it again achieves state-of-the-art empirical performance.
Diego Martinez-Taboada, Aaditya Ramdas· 0 citations
Let $X = (X_1, \ldots, X_n)$ be a random vector from any Borel probability law on $\mathbb{R}_+^n$. We revisit the problem of deriving a lower confidence bound (LCB) on a scalar parameter of that law. We recast classical work, beginning with Buehler, in purely probabilistic terms to form a more accessible and extensible framework. We then specialize the framework to the case where the components of $X$ are independent. In this context, we prove that Gaffke's bound is Buehler optimal for the order that it induces with respect to the maximum marginal mean parameter: $max_{i \in [n]} E_Q[X_i]$, which reduces to the common mean when the $X_i$ are independent and identically distributed. That is to say, no other valid LCB that orders samples in the same way as Gaffke's bound can improve on it with respect to this parameter.
It is shown that the classical Bayesian bootstrap closes this gap in U-calibration, which asks one online probability fore-caster to have low regret for every bounded proper loss, including losses unknown when the forecasts are made.
The power prior of Ibrahim and Chen incorporates historical data into a Bayesian analysis by raising the historical likelihood to a power $a_0 \in [0, 1]$. The choice of the exponent has remained an open question. This paper gives a closed-form answer under the predictive log-loss. For a model with $d$ parameters, a historical sample of size $N_0$, and average Kullback--Leibler divergence $\bar{D}_0$ between the historical and current data-generating distributions, the optimal exponent is $a_0^{*} = d/(2 N_0 \bar{D}_0 + d)$. Equivalently, the optimally borrowed effective sample size obeys the harmonic law $1/E^{*} = 1/N_0 + 2\bar{D}_0/d$: compatible data are pooled in full, and any difference caps the borrowed information at $d/(2\bar{D}_0)$ observations. The result is exact for multinomial data and extends to smooth parametric families. The law benchmarks adaptive borrowing, explains the reported degeneracy of the normalized power prior, and shows that neither subsetting the data nor decaying the exponent improves on the correctly discounted constant.
We study minimax-optimal designs and estimators for estimating the sample average treatment effect in finite population randomized experiments, where both design and estimator are unrestricted. For binary potential outcomes, we show this minimax risk is equivalent to the minimax risk $\rho_n^*$ of an estimation problem with $2$ unknown parameters. We leverage this reduction to establish a second-order risk expansion $\rho_n^* = n^{-1} - Cn^{-4/3} + o_n(n^{-4/3})$ for an explicit constant $C$ related to the Airy function. The minimax risk is attained by Bernoulli randomization with a nonlinear shrinkage estimator. Our results show that standard procedures such as complete randomization with difference in means are only minimax optimal up to first order in $n.$ We derive further results on admissibility of these procedures and discuss the practical implications of our results.
Timothy Sudijono, Edgar Dobriban, E. Tchetgen· 1 citation
We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order $m^{-2}\log^{2}m$, where the number of training samples is of order $m$. For another value of the source parameter, we obtain, for any $\epsilon>0$, bounds of order $m^{-3+\epsilon}$, provided that the capacity parameter exceeds $\epsilon^{-1}$. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.