CS Paper Radar

Contact Geometry and Covariance Deficits in Volume-Sampled Least Squares

Kihun Rhee, Hanjoon Byun, Junpyo Seo

cs.LG stat.ML ·submitted 2026-08-27 09:38 UTC · v3

Abstract

We classify when ordinary fixed-size volume sampling followed by unweighted least squares attains its sharp coefficient-covariance ceiling on a fixed design. For a real whitened design without coloops and a fixed positive-loss residual, the contact space is unchanged at every strict-interior sample size. Its possible nonzero values form a finite orthogonal family: each maximal parallel class of normalized Naimark-complement rows determines a deletion nullspace of dimension one less than the class size. A single residual attains an entire query precisely when the query range lies in one class space. The proof starts from two-sided Loewner comparison of every normalized covariance deficit with an explicit leave-one-out operator, using supported omission moments and reverse deletion. Residual augmentation provides resolvent and second-moment upper bounds, while complement geometry yields query-specific margins, angular concentration, local alignment, and a multi-output energy obstruction. Exact families give closed-form margins and covariances, exhibit support-boundary jumps, and approach the ceiling despite a uniformly positive geometric margin. Finally, the same moment identities give upper and lower bounds on expected fixed-query squared-loss excess. The subset draw is the only randomness; all support and endpoint restrictions are explicit.

Comment
55 pages. Revised title and substantially reorganized theoretical exposition. Includes contact-space and whole-query classification, all-size leave-one-out covariance-deficit comparisons, quantitative contact geometry, and query-risk bounds, with proofs, exact constructions, and ancillary exact-arithmetic checks

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Calibration and Sharp Risk Geometry for Volume-Sampled Ridge Regression

cs.LG math.STstat.ML ·2026-10-06 ·Kihun Rhee
theory similarity 0.68
Abstract · 66 pages, 0 figures

We study ridge regression from exactly $s$ distinct rows of a fixed design. Responses are fixed, and only the subset is random. The determinant law and selected ridge fit share one positive definite penalty. Established mean identities and exponential-family duality give the unique penalty that matches a prescribed full-data ridge fit in expectation. It exists exactly when $s$ exceeds the target's effective dimension. Our main result concerns centered covariance risk normalized by full-data penalized loss. For balanced signed coordinate replicas, a strict sector inequality gives the sharp risk and all maximizing responses at every budget from the dimension to one below the row count. This holds for any nonzero positive semidefinite query. With the target and query fixed, the maximizing response space is unchanged across these budgets. For general designs, we characterize attainment of a leave-one-out envelope. For existing real equiangular tight frames, flat row query energy characterizes when every nonzero residual response maximizes at two deletions. At three deletions, we give the sharp risk and complete maximizing space for isotropic queries, using unequal triangle weights. The balanced geometry yields a same-sample unbiased ridge--Horvitz--Thompson mixture with lower sharp risk and an exact mean-share improvement boundary. Under full recalibration after feature changes, we prove quadratic regret from searching the complete old maximizing space and a query-uniform bound on the mixture's risk gain. The strongest sector inequalities have exact computer-assisted proofs.

0.20

Common Covariance Geometry and Certification for Brownian Kernel Ladders

cs.LG ·2026-08-25 ·Mahdi Mohammadigohari
similarity 0.58
Abstract

A representation-adaptive kernel class produces, on a fixed sample, a union of reproducing-kernel Hilbert-space ellipsoids rather than one ellipsoid. We introduce the minimum-trace common covariance that dominates the unrestricted empirical union generated by Brownian kernel ladders and develop its statistical, approximation-theoretic, and computational consequences. The covariance value admits exact formulations through absolutely two-summing operators and covariance-dominated multipliers, and it yields a universal Gaussian-complexity bound. A closed last-layer Dirac-trace reduction and a signed Brownian threshold representation convert the generic covariance problem into threshold, graph-coarea, and effective-resistance geometry. These tools give deterministic depth laws, conditional Gaussian reverses, random-design and perturbation transfers, and an exact empirical Kolmogorov-width formula whose leading covariance eigenspaces approximate the complete adaptive ball simultaneously. Finite contact, active semidefinite programs, verified separation, and a convex resistance-design relaxation provide complementary lower and upper certificates. A finite covariance-indexed Brownian path on frozen representations illustrates the distinction between successful covariance certification and predictive selection: all reported path certificates succeed, whereas the locked predictive study misses one predeclared aggregate criterion. The paper thereby identifies one finite-dimensional covariance object linking unrestricted kernel adaptation, Gaussian geometry, common subspaces, and certifiable computation.

0.28

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

cs.LG ·2026-09-03 ·Shi Fu, Huibo Xu, Qixin Zhang, Dacheng Tao
benchmark similarity 0.57
Abstract

Restricted eigenvalue (RE) bounds govern stable recovery by norm-regularized estimators. For isotropic sub-Gaussian measurements, the benchmark sample size is $1+w(A)^2$, where $w(A)$ is the Gaussian width of the normalized descent cone. The COLT 2015 open-problem note (Banerjee et al., 2015) asked whether the same law follows for heavy-tailed designs from a uniform small-ball condition alone. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension-free, arbitrary-set form, and the missing obstruction is simultaneous threshold occupancy. A constant-width polyhedral descent cone with fixed small-ball constants has zero empirical RE on every sample path up to half the ambient dimension. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent-cone section. For every fixed threshold VC dimension $d$, as $β\downarrow0$, the sharp worst-case sample complexity is $Θ(β^{-1}[d\log(1/β)+\log(1/δ)])$. The separation persists under exact isotropy and all finite moments: on the same constant-width cone, Gaussian measurements succeed with $O(1+\log(1/δ))$ samples, whereas an isotropic heavy-tailed design fails pathwise for $n\lesssim\sqrt{p/\log p}$. Gaussian smoothing yields an everywhere-positive $C^\infty$ density while retaining arbitrarily poor RE. Under isotropy, a distribution-free fallback governed by affine dimension times squared enclosing radius is sharp on this family.

0.27

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

cs.CC stat.MLcs.LGmath.ST ·2026-11-02 ·Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao +1 more
theory similarity 0.55
Abstract

We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

0.17

Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

cs.LG cs.ITmath.NAmath.PR+1 ·2026-09-02 ·Piyush Sao
code/data similarity 0.55
Abstract · 41 pages, 6 figures, 4 tables. Reproducibility code: https://github.com/piyush314/random-projection-geometry (pinned as a submodule). Compan…

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to $m=O(\varepsilon^{-2}\log n)$ dimensions preserves pairwise squared distances within relative error $\varepsilon$ with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature $f(D)$ of a squared distance $D$ from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data ($Σ=σ^2 I_d$), we diagonalize this operator in closed form. For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(m/ d)^{k/2}$. This yields three sharp consequences. A rank-$m$ sketch retains at most an $m/d$ fraction of the variance of any feature of one squared distance. If $m\to\infty$ and $m/d\to0$, the expected Kendall correlation is $\frac{2}π\sqrt{m/d}(1+o(1))$; for fixed $q$, nearest- neighbor agreement tends to $1/q$. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when $\log n\ll m\ll d$. After removing scale, Haar-averaged retained covariance-shape information is $(m/d)^2$. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

0.38

When Can Unlabeled Data Pools Replace Membership Queries?

cs.LG ·2026-10-29 ·Dravyansh Sharma
similarity 0.54
Abstract

Membership queries let a learner label arbitrary points and give near-optimal $\tilde O(n\log(1/\eps))$ label complexity for halfspaces under every marginal. A pool learner may label only sampled points. We ask when unlabeled data can replace membership queries. For homogeneous halfspaces the answer depends only on the angular law of $X/\|X\|$. If this law assigns zero mass to every hyperplane through the origin and positive mass to every nonempty open set of directions together with its reflection, a pool learner uses $O(n\log^3n\log(n/(\epsδ)))$ labels, uniformly over all such marginals and targets, without density, moment, concavity or isotropy assumptions. The same label bound holds for non-homogeneous halfspaces under every marginal with full support and no mass on affine hyperplanes, including Gaussians. Dropping either angular assumption admits $Ω(1/\eps)$ pool versus $O(\log(1/\eps))$ membership-query separations, even with unlimited unlabeled data. The price is paid in unlabeled data: in dimension $n\ge3$, for every unlabeled budget fixed in advance, some marginal satisfying both assumptions forces $Ω(1/\eps)$ labels. For isotropic $s$-concave marginals in dimension $n\ge3$, unlimited pools keep logarithmic label rates for every finite $s$. With an unlabeled budget fixed in advance, class-uniform polylogarithmic rates hold exactly for $s>-1/(n+1)$, or $s>-1/n$ under central symmetry, and in the general class the optimal rate between these thresholds is $\tildeΘ(\eps^{-(n-2)/n})$. This extends the range $s\ge-1/(2n+3)$ of previous sample-based guarantees, in the realizable setting.

0.28

Improved Leverage Score Sampling for Constrained Active Linear Regression

cs.LG stat.MLmath.NA ·2026-11-18 ·Aarshvi Gajjar, Syamantak Kumar, Aditya Makkar, Christopher Musco, Joey Zhou
top venuetheory similarity 0.53
Abstract · To appear in NeurIPS 2026 (Spotlight)

In this paper we study active learning for constrained linear regression. Given a design matrix $A\in\mathbb{R}^{n\times d}$, a constraint set $C\subseteq\mathbb{R}^d$, and query access to $b\in\mathbb{R}^n$, we seek an approximate solution to $\min_{x\in C}\|Ax-b\|_2^2$ using as few queries as possible. This problem arises in many scientific and engineering applications, and randomized leverage score sampling provides a powerful method to solve it. However, existing leverage score methods ignore the constraint or encode it through ridge regularization, suffering unfavorable query complexity for anisotropic constraint sets. We propose ellipsoid-regularized leverage scores, where we approximate the constraint set by an outer ellipsoid and use its shape matrix to bias sampling toward directions that matter under the constraint geometry. We prove that the query complexity is governed by an anisotropic effective dimension $d_{\text{eff}}(C)\le d$. With appropriate parameters, $O(d_{\text{eff}}(C)\log d/\varepsilon^2)$ queries suffice to return a point in $C$ with objective value at most $(1+\varepsilon)$ times the optimum. This bound can substantially improve on the standard leverage-score bound, since anisotropic constraints can make $d_{\text{eff}}(C)$ much smaller than $d$. For convex constraints, we improve the dependence on $\varepsilon$ from $1/\varepsilon^2$ to $1/\varepsilon$. We also prove two lower bounds: first, the $d/\varepsilon^2$ dependence is unavoidable without convexity assumptions on $C$, and second, in some regimes, the effective dimension dependence $d_{\mathrm{eff}}(C)/\varepsilon$ is necessary for ellipsoidal constraints. Experiments on synthetic regression problems and a parametric heat conduction problem show lower regression error than standard baselines for similar query budget.

0.34

Estimating the Volume of a Union of Convex Bodies

cs.DS ·2026-11-04 ·Eeshan Banerjee, Aranya Kumar Bal, Debabrota Basu, Sourav Chakraborty, Debarshi Chanda +1 more
similarity 0.53
Abstract

The \textit{Union Volume Estimation problem}, i.e. yielding an $(\varepsilon, δ)$-approximation of the volume of the union of convex bodies, is a classical problem in computational geometry and formal methods. In this paper, we first detect where and why the efficient union volume estimators with approximate sampling and PAC volume estimation oracles fail. Specifically, we show that having only TV-distance guarantees on the approximate sampler does not suffice, and demonstrate this bottleneck by constructing the sunflower families of convex bodies. In this context, we propose the concept of \textit{tail-controlled samplers} that can yield with high-probability almost-$\ell_{\infty}$ closeness. Secondly, we leverage this concept to propose a generic algorithmic framework \texttt{Alpona} that properly combines a PAC volume computation and approximate point sampling oracles with tail-controls to yield an $(\varepsilon, δ)$-estimate of the union volume for any collection of convex bodies. We show that \texttt{Alpona} needs only linear (in number of convex bodies) oracle calls to be $(\varepsilon, δ)$-correct. Finally, we provide a tail-controlled analysis of the Hit-and-Run sampler~\citep{lovasz2006fast}. We further provide a novel geometric analysis to improve the required walk length of Hit-and-Run. We further instantiate \texttt{Alpona}'s correctness for the sparse frequency streams of convex bodies: a special case of the union volume estimation problem where no convex body intersects more than $τ$ many other bodies.

0.10