Active Regression for Single-Index Models with Unknown Link Functions

• URL: http://arxiv.org/abs/2608.01287v1
• Date: Sun, 02 Aug 2026 14:53:41 GMT
• Title: Active Regression for Single-Index Models with Unknown Link Functions
• Abstract summary: This paper studies active regression for single-index models under general $ell_p$-loss with an unknown $1$-Lipschitz link function $f$.<n>The results close much of the remaining gap in active $ell_p$-regression for single-index models.
• Score: 9.93804255192388
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies active regression for single-index models under general $\ell_p$-loss with an unknown $1$-Lipschitz link function $f$, formulated as $\min_{f,x} \|f(Ax)-b\|_p^p$ with full access to $A$ but coordinate-query access to $b$. Prior work established upper bounds for known link functions for all $p\geq 1$ and for unknown link functions only in the $p=2$ case, together with lower bounds for $p\leq 2$. This work addresses the more challenging setting of unknown link functions and general $p \geq 1$. A non-adaptive sampling algorithm is presented that achieves a $(1+ε)$-approximation using $O(d^{p/2\vee 1}/ε^{p\vee 2}\operatorname{poly}\log(n/ε))$ queries. Nearly tight lower bounds are also established for $p>2$. These results close much of the remaining gap in active $\ell_p$-regression for single-index models.

Related papers

• Covering a Few Submodular Constraints and Applications [2.243805796685295]
  We consider the problem of covering multiple submodular constraints.<n>For covering multiple submodular constraints we obtain a randomized bi-criteria approximation that for any given integer $alpha ge 1$ outputs a set $S$ such that $f_i(S) ge$ $(1-1/ealpha -epsilon)b_i$ for each $i in [r]$ and $mathbbE[c(S)] le (1+epsilon)alpha cdot sfOPT$.
  arXiv  Detail & Related papers  (2025-07-14T03:32:42Z)
• Near-optimal Active Regression of Single-Index Models [5.081060114892763]
  This work presents the first algorithm that provides a $(1+varepsilon)$-approximation solution by querying $tildeO(dfracp2vee 1/varepsilonpvee 2)$ entries of $b$.
  arXiv  Detail & Related papers  (2025-02-25T13:58:06Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
  arXiv  Detail & Related papers  (2024-06-04T15:50:42Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Online Lewis Weight Sampling [62.38157566916501]
  Cohen and Peng introduced Lewis weight sampling to the theoretical computer science community. Several works have extended this important primitive to other settings, including the online coreset, sliding window, and adversarial streaming models. We design the first nearly optimal $ell_p$ subspace embeddings for all $pin(0,infty)$ in the online coreset, sliding window, and the adversarial streaming models.
  arXiv  Detail & Related papers  (2022-07-17T19:40:51Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  We study active sampling algorithms for linear regression, which aim to query only a small number of entries of a target vector. We show that this dependence on $d$ is optimal, up to logarithmic factors. We also provide the first total sensitivity upper bound $O(dmax1,p/2log2 n)$ for loss functions with at most degree $p$ growth.
  arXiv  Detail & Related papers  (2021-11-09T00:20:01Z)
• Semi-supervised Active Regression [21.51757844385258]
  This paper studies the use of partially labelled, potentially biased data for learning tasks. The learner has access to a dataset $X in mathbbRd | X min_beta in mathbbRd | X beta - Y |2 end2 equation while making few additional label queries.
  arXiv  Detail & Related papers  (2021-06-12T03:28:43Z)
• Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank Approximation [23.06440095688755]
  A common technique for compressing a neural network is to compute the $k$-rank $ell$ approximation $A_k,2$ of the matrix $AinmathbbRntimes d$ that corresponds to a fully connected layer (or embedding layer) Here, $d$ is the number of the neurons in the layer, $n$ is the number in the next one, and $A_k,2$ can be stored in $O(n+d)k)$ memory instead of $O(nd)$. This
  arXiv  Detail & Related papers  (2020-09-11T20:21:42Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

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.