Jun 2025· Journal of computer and system sciences (Print)· Vol abs/2506.10775· 0 citations· 55 references
Computer Science
TL;DR
This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most $(1 + \epsilon) \cdot k^*$ where $\epsilon \ge 0$ and $k^*$ is the minimum error achieved by an optimal monotone classifier.
Abstract
In monotone classification, the input is a multi-set $P$ of points in $\mathbb{R}^d$, each associated with a hidden label from $\{-1, 1\}$. The goal is to identify a monotone function $h$, which acts as a classifier, mapping from $\mathbb{R}^d$ to $\{-1, 1\}$ with a small {\em error}, measured as the number of points $p \in P$ whose labels differ from the function values $h(p)$. The cost of an algorithm is defined as the number of points having their labels revealed. This article presents the first study on the lowest cost required to find a monotone classifier whose error is at most $(1 + \epsilon) \cdot k^*$ where $\epsilon \ge 0$ and $k^*$ is the minimum error achieved by an optimal monotone classifier -- in other words, the error is allowed to exceed the optimal by at most a relative factor. Nearly matching upper and lower bounds are presented for the full range of $\epsilon$. All previous work on the problem can only achieve an error higher than the optimal by an absolute factor.
Let $\mu$ be a log-concave probability measure on $\mathbb R^n$ and let $f\colon\mathbb R^n\to\mathbb R^k$ be a polynomial mapping of degree at most $d$. We show that \[ \mu(f\in A) \le C\bigl(\lambda_k(A)\bigr)^{\frac{1}{k(d-1)+1}} \] for every Borel set $A\subset\mathbb R^k$ whenever the image measure $\mu\circ f^{-1}$ is absolutely continuous. The constant $C$ is independent of the dimension $n$, and the exponent $\frac{1}{k(d-1)+1}$ is sharp. This extends the scalar Carbery--Wright inequality and answers, in the log-concave setting, a question raised by Avni, Glazer, and Larsen. In addition, we show that the density of $\mu\circ f^{-1}$, whenever it exists, belongs to the Nikolskii--Besov space $B^{\frac{1}{k(d-1)+1}}_{1,\infty}(\mathbb R^k)$, with a dimension-free bound for the corresponding norm. A central difficulty in passing from scalar polynomials to vector-valued polynomial mappings is the lack of a suitable nondegeneracy parameter quantifying absolute continuity of $\mu\circ f^{-1}$, as the variance does in the scalar case. Natural candidates such as the covariance matrix or the Jacobian matrix either fail to characterize this property or do not lead to dimension-free estimates. We identify such a parameter and define it to be the covariance matrix of the vector formed by the monomials of degree up to $d^{k-1}$ in the normalized components of $f$. The dimension-free nature of our results allows us to extend Kusuoka's absolute continuity criterion for Gaussian polynomial random vectors to the log-concave setting. Moreover, in this setting, we obtain estimates relating convergence in distribution to convergence in total variation for polynomial random vectors.
Let $\mu$ be an $n$-AD-regular measure in $\mathbb{R}^d$. Chousionis, Garnett, Le and Tolsa [CGLT] proved that $\mu$ is uniformly $n$-rectifiable if and only if the square function built from the density differences $\Delta_\mu(x,r)=\mu(B(x,r))/r^n-\mu(B(x,2r))/(2r)^n$ satisfies a Carleson condition. In this paper we show that the same characterization holds if the density is first composed with a function $F$ which is bi-Lipschitz on the interval $[c_0^{-1},c_0]$ determined by the AD-regularity constant $c_0$. The main example is $F=\log$, introduced in [Le], for which the square function takes the scale-invariant form $\Delta_\mu^{\log}(x,r) = \log\bigl(\mu(B(x,r))/\mu(B(x,2r))\bigr)+n\log 2$. We give a complete proof, extend the statement to the smooth square functions of [CGLT], where the density is replaced by the convolution of $\mu$ with a Gaussian or a more general radial kernel, discuss what happens when $F$ is not bi-Lipschitz, and treat the case $\mu(\mathbb{R}^d)<\infty$, where the behavior of $F$ near zero enters in only one of the two implications. We also show that the qualitative characterization of $n$-rectifiable measures by Tolsa and Toro [TT], in terms of the same square function at $\mu$-almost every point, holds after composition with any locally bi-Lipschitz $F$. This requires neither AD-regularity nor doubling, and for $F=\log$ the condition $\lim_{r\to0}\Delta_\mu(x,r)=0$ becomes $\lim_{r\to0}\mu(B(x,r))/\mu(B(x,2r))=2^{-n}$.
Given integers $r>t\ge1$ and a real number $p>0$, the $(t,p)$-norm $||\mathcal{H}||_{t,p}$ of an $r$-graph $\mathcal{H}$ is the sum of the $p$-th powers of the degrees $d_{\mathcal{H}}(T)$ over all $t$-subsets $T\subseteq V(\mathcal{H})$. When $t=r-1$, this is the codegree $p$-norm. For all sufficiently large $n$, we obtain the following results. The first two apply in both the convex range $p>1$ and the concave range $0<p<1$. First, for $r$-graphs with matching number at most $s$, we determine the maximum $(t,p)$-norm. Second, for $k$-intersecting families, we establish an Erd\H{o}s--Ko--Rado-type theorem for the $(t,p)$-norm. Third, for $P_\ell^r$-free hypergraphs, we determine the maximum $(t,p)$-norm for every $1\le t\le r-1$ and $p>1$. In each of the three settings, we also characterize all extremal families.
Let $A, B \in \mathbb{Z}_{\ge 0}^n$ be nonnegative vectors and let $t = |\operatorname{supp}(A \star B)|$. We give a Las Vegas algorithm that computes $A \star B$ in $O(t \log t)$ expected time. More generally, for every $0<\delta \le \frac{1}{2}$, the algorithm terminates within $O(t \log t \log \frac{1}{\delta})$ time with probability at least $1 - \delta$. The algorithm uses dense convolution, linear hashing, and the length reduction of \cite{BFN22}. Its main ingredient is a carry-free representation of the indices as vectors of constant dimension $d$ whose coordinates have size $O(t / \log t)$. We can then take our hash function to be the inner product with a random element of $\mathbb{F}_p^d$ for a prime $p$ of size $\Omega(t / \log t)$: this preserves addition and gives collision probability exactly $1/p$, while identities regarding the moments of the vectors identify and recover the isolated terms as in \cite{BFN22}. Our expected running time matches that of Jin and Xu~\cite{JX24} while using substantially different tools and yielding a simpler algorithm. Note that their algorithm also terminates within $O(t \log t)$ time with probability at least $1 - \frac{1}{t}$, while our tail bound is weaker.
Let $\Pi$ be a $k\times n$ sparse random matrix. For a fixed $r$-dimensional subspace $V\subset{\mathbb R}^n$, let $U_V:{\mathbb R}^r\to{\mathbb R}^n$ denote an isometry from ${\mathbb R}^r$ onto $V$. The product $\Pi U_V$ is a central model in randomized dimension reduction and has been studied primarily through trace and Gaussian comparison inequalities. In this work, we develop an approach to the spectral norm of the matrix product $\Pi U_V$, based on entropy estimates for level sets of vectors $x\in V$. Combining the method with existing estimates, we show the following. Assume that \[ k\ge C\,r(\log\log r)^2,\qquad p\ge (\log k)/k. \] Let $\Pi$ be a $k\times n$ matrix with i.i.d. entries equidistributed with the product $b\,\xi$, where $b$ is a Bernoulli($p$) random variable and $\xi$ is mean-zero, independent of $b$, and satisfies $|\xi|\le1$ almost surely. Then with high probability \[ \|\Pi U_V\|\le C\sqrt{kp}. \] Matching results hold for other random models with negatively associated entries.
We prove that the $L_1$-discrepancy with arbitrary nonnegative weights suffers from the curse of dimensionality. More precisely, for every $\varepsilon \in (0,1)$ and $d \in \mathbb{N}$, the inverse of the $L_1$-discrepancy satisfies \[ N_{1,+}(\varepsilon, d) \ge \frac{(1-\varepsilon)^2}{1 + \varepsilon} \left( \frac{3+2 \sqrt{3}}{6}\right)^d, \] where $(3+2\sqrt{3})/6 = 1.07735\ldots$. The proof combines a change to a volume-biased probability measure with a fractional-moment estimate for the normalized discrepancy function. The lower bound applies, in particular, to equally weighted point sets. The argument uses the nonnegativity of the weights in an essential way and does not cover arbitrary signed weights.
A new machine-learning framework aims to improve the success rate of computational protein design while moving away from results that reproduce sequences found in nature.
MIT News · Artificial Intelligence· news.mit.eduAug 24, 2026
