CS Paper Radar

Minimax Additive Regression under Unknown Dependent Designs

Baptiste Ferrere, Fabrice Gamboa, Jean-Michel Loubes

cs.LG stat.ML ·submitted 2026-09-30 07:55 UTC · v2
unusual

Abstract

We study additive regression under an unknown and potentially non product design distribution, allowing the number of covariates to grow with the sample size. We consider a coupled class that separately controls the smoothness of the marginal densities and of each additive component multiplied by the corresponding marginal density. Under joint-density bounds that hold uniformly in the dimension and suitable dimension-growth conditions, we establish matching minimax bounds for prediction. With known marginal densities, the classical additive rate is attainable. When the marginals are unknown, this rate is preserved if the densities are at least as smooth as the weighted components. Otherwise, marginal-density smoothness determines the minimax rate over the coupled class. Finally, we recover all additive components with total squared error of the same order as the prediction error.

Closest papers

Nearest neighbours by meaning across the whole index.

Minimax rates for pointwise CATE estimation: the role of design smoothness

cs.LG math.STstat.ML ·2026-10-13 ·Yuxuan Hou, Zhenghan Li
similarity 0.57
Abstract

We study the role of design smoothness in the minimax estimation of conditional average treatment effects at a fixed covariate point. For design densities bounded above and away from zero, without further regularity, we derive upper and lower risk bounds with an arbitrarily small gap in the convergence-rate exponent. Under uniform design, we obtain matching upper and lower bounds at interior points in the regime of low nuisance smoothness. These results show that rough covariate designs can lead to slower rates than uniform designs, even under the same smoothness assumptions on the treatment effect and nuisance functions, highlighting the role of the covariate distribution in pointwise causal estimation.

0.22

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

cs.LG ·2026-10-08 ·Xiaofeng Cao, Junfan Li, Langzhang Liang, Mingwei Xu, Xiao Zhang
publishedtheoryhot direction similarity 0.55
Abstract · This work was accepted by IJTCS-FAW 2026

We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only $b$ out of $d$ attributes per instance for prediction and $b_0\geq 0$ additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.

0.38

Functional linear regression from sparse to dense designs: a pooling-ridge method and minimax optimality

cs.LG stat.MEmath.STstat.ML ·2026-08-26 ·Shunxing Yan, Fang Yao
similarity 0.54
Abstract · The Annals of Statistics

Functional data analysis is an important statistical field that treats data as random functions. In practice, the random functions are often not fully observed but instead measured at discrete times. While simpler problems, such as mean and covariance estimation, have been widely studied for discretely observed data, optimal estimation of linear regression for this data type has remained unsolved for over two decades. To tackle this fundamental challenge, we propose a novel approach, referred to as pooling ridge estimation, which combines the advantages of pooling strategy and RKHS-based method by incorporating the unbiased estimation of operators based on discretely observed measurements from all subjects. This unified estimation framework enables us to achieve minimax optimality in prediction risk in arbitrary sampling schemes ranging from sparse to dense designs, for both scalar-on-function and function-on-function regression models. Such methodological and theoretical advances are obtained for the first time and accurately reveal the influence of discrete sampling. For scalar-on-function regression, the phase transition occurs once, separating the convergence behavior into two distinct regimes. Remarkably, for function-on-function regression, up to three phase transitions may occur, determined by the sampling frequencies of the predictor/response functions. Finally, simulation experiments and two real data examples provide empirical support for the proposed methods.

0.44

Generalized Deep Regression for Repeated Measurements

cs.LG stat.ML ·2026-09-22 ·Kexuan Li
theory similarity 0.51
Abstract

In this paper, we study the estimation of a marginal regression function from independent units with repeated binary, count, or continuous responses using ReLU deep neural networks. In the model, we assume that the dependence is generated by an unobserved random mean function within each unit. We then fit a neural network with a convex generalized regression loss. We show an oracle inequality by separating conditional measurement variation from between-unit variation. In addition, we prove that with $n$ units and $m$ measurements per unit, ReLU networks can attain an integrated mean squared error of order $n^{-1}+(nm)^{-2β/(2β+d)}$, up to logarithmic factors, over $β$-Hölder classes. We also derive a weighted oracle inequality for unequal cluster sizes and a rate for compositionally smooth functions. For pointwise ensemble inference, we give a projection central limit theorem and prove infinitesimal jackknife consistency under an explicit asymptotic linearity condition. Simulations and real data examples are provided to support our theoretical findings and practical implications.

0.31

Marginal-Nonuniform Multiclass Learning

cs.LG stat.ML ·2026-11-06 ·Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri, Maximilian Thiessen
top venue similarity 0.51
Abstract · Accepted at NeurIPS 2026

We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest.

0.45

Exact Global Minimax Risk near Nonidentification

cs.LG stat.MLmath.ST ·2026-10-23 ·Kaiyue Yang, Yunan Wu
similarity 0.51
Abstract

We study squared-error estimation when a nuisance parameter is unidentified on a submodel but affects a target that vanishes there. For models with higher-order profile expansions, we give sufficient conditions under which the largest critical-path minimax risk is the exact asymptotic minimax risk over the full parameter space. An efficient observable feature, negligible calibration error and stable recovery yield one estimator attaining the leading constant uniformly, with the profile coordinates unknown. The estimator uses calibration estimates, a local feature mean and an empirical recovery feature. The constant is expressed through a bounded-normal decision problem. We verify the conditions in two models. In centered Gaussian logistic errors-in-variables regression with one surrogate and two unknown variances, we determine the fifth-order global coefficient risk and its exact constant. A sparse extension separates variance-decomposition uncertainty from direction estimation and specifies when the scalar constant is preserved. In a degree-balanced replicated-network model, we determine the sixth-order global edge-contrast risk when block proportions are unknown. Triangles identify a parameter combination; a bowtie supplies the additional information needed for the contrast.

0.29

On the Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization with Exact Proximal Oracles

cs.LG ·2026-11-03 ·Yuxing Peng, Zhiqing Tang, Weijia Jia
similarity 0.50
Abstract · 50 pages, including appendices and references. Lean 4 formalization of the lower bounds in the ancillary files

Finite-sum nonconvex-strongly-concave minimax problems arise in adversarial training and distributionally robust learning. Their known lower bounds cover only linear-span algorithms, zero-respecting algorithms, or a restricted proximal protocol. They leave open the power of exact component proximal steps, whose responses are global saddle points of regularized component problems and can expose directions that gradients do not reveal. We show that neither unrestricted adaptivity nor exact proximal access improves the polynomial complexity. We consider $n$ components with joint mean-squared smoothness $L$ and condition number $κ$, started from a point with primal gap at most $Δ$ and joint gradient norm at most $\sqrt{2LΔ}$. For $\varepsilon^2/(LΔ)$ below a universal constant, every randomized adaptive algorithm with exact component values, gradients, and proximal responses needs $Ω(n+\min\{\sqrt n\,κ,n^{3/4}\sqrtκ\}LΔ/\varepsilon^2)$ component queries in the worst case to find an $\varepsilon$-stationary point of the value function. A method using only component gradients attains this rate up to a factor $\log^2(2+κ)$, including initialization. Zhou (arXiv:2610.04944) concurrently proves the same rate for zero-respecting first-order methods. In our hard instances, every component admits proximal steps with the same step sizes, and a response for a component reveals hidden directions only up to the first one assigned to another component.

0.23

Agnostic Smoothed Online Regression with Adversarial Responses

cs.LG stat.MLmath.ST ·2026-09-26 ·Xuanyu Chen, Yue Yu
theory similarity 0.50
Abstract · 29 pages, 1 table

We study smoothed online prediction with bounded adversarial responses. This widely studied framework bridges i.i.d. sampling and adversarial covariate selection through a smoothness parameter $\textsf{C}_{\textsf{cov}}$, which bounds conditional covariate densities relative to a fixed, unknown base measure. We propose \textsc{Hedge-Cover}, an information-theoretic algorithm that achieves sublinear regret $\widetilde{O}(\sqrt{\text{Pdim}(\mathcal{F}) \textsf{C}_{\textsf{cov}} T})$ for function classes with bounded pseudo-dimension. The algorithm aggregates a carefully constructed family of experts using \textsc{Hedge}, with a prior that links regret to the number of disagreements between a consistent selector and a target function. We bound this number by exploiting covariate smoothness. This answers an open problem posed in \cite{blanchard2025agnostic} on the minimax optimal adaptive regret of the smoothed online regression problem. We establish a matching lower bound for the class of linear predictors. The main intricacy of the lower bound lies in explicitly constructing a challenging sequential covariate distribution supported on mutually orthogonal hyperplanes. This construction may be of independent technical interest. Finally, we revisit the well-specified setting and quantify the effect of response noise. For conditionally $ν^2$-subGaussian responses, we extend the existing lower bound under realizable responses by showing that the minimax expected regret is $Ω((1\vee ν)\sqrt{(\textsf{C}_{\textsf{cov}}-1)dT})$ for a function class of VC dimension $d$. A corresponding upper bound for ERM matches this dependence on $ν$.

0.25