DeepMVSA is proposed, which re-expresses the minimum-volume principle in neural implicit form and proves a non-asymptotic sample-complexity bound of the polynomial-time benchmark order for a localized surrogate estimator.
Abstract
We study the estimation of a $K$-dimensional simplex from $N$ i.i.d.\ points sampled uniformly from its interior; the observations are convex combinations of $K+1$ unknown prototypes. Existing polynomial-time estimators need cubic per-sample work or $O(NK)$ storage and are impractical at $N\sim 10^6$--$10^8$. We propose DeepMVSA, which re-expresses the minimum-volume principle in neural implicit form: a lightweight coordinate network generates the mixing weights and a triangular LU-type parameterization the dual simplex matrix, reducing the trainable-state memory to $O(K^2)$, independent of $N$, and the cost per data pass to $O(NK^2)$. We prove a non-asymptotic sample-complexity bound of the polynomial-time benchmark order for a localized surrogate estimator; an oracle inequality for every global minimizer of the neural objective, with volume-inflation control and an explicit shrinkage bias; a conditional end-to-end error budget separating statistical, approximation, optimization, and enclosure-residual terms on an explicit envelope event; and two-point lower bounds: at any noise level $\sigma>0$ fixed independently of $N$, the $N^{-1/2}$ scaling is unimprovable in its $N$-exponent. Experiments with up to $N=10^8$ synthetic observations are consistent with the predicted accuracy and scaling, and feasibility on real scenes of $\sim 10^7$ pixels is demonstrated.
Convex regression provides a flexible nonparametric estimation framework while incorporating appropriate shape information. However, its standard least-squares formulation has $O(n^2)$ supporting-hyperplane constraints creating a computational bottleneck as the sample size $n$ increases. We study a $K$-nearest-neighbor...
We study the Sampled-Max Subgradient Method (SMax-SGM) for large convex finite-max problems. Each iteration maximizes over a fresh random subset of the $N$ components and takes one subgradient of the sampled maximizer. The method is therefore stochastic subgradient descent on a sampled-max surrogate. We bound the surro...
E. Gladin, Анна Фёдорровна Попова, Georgii Babinskii· 0 citations
We study sampling from a distribution supported on an unknown compact $d$-dimensional $C^2$ manifold $M\subset\mathbb{R}^D$, observed only through i.i.d. uniform points from $M$. We reconstruct the constraint using an adaptive local-convex-hull estimator and target an ambient distribution penalized by squared distance...
We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon>0$ in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge1$, F$^2$SA-$p$ achieves $\widetilde O(...
Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al.· 0 citations
We propose a novel local-polynomial estimator of the ratio $r=f/g$ of two $d$-dimensional densities $f$ and $g$, from which independent samples are available. The estimator is shown to achieve pointwise minimax optimal rates over H\"older classes of arbitrary smoothness index without additional logarithmic factors, and...
We develop accelerated gradient-free methods for stochastic convex optimization with constraints defined by expectations. Our batched primal-dual sliding method uses two-point evaluations sharing a random sample and guarantees expected objective error and expected maximum constraint violation at most $\varepsilon$. It...
Vadim Abronin, A. Gasnikov, D. Dvinskikh· 0 citations
Related blog posts
MIT News · Artificial Intelligence· news.mit.eduNov 6, 2026
A machine-learning approach called CheMeleon provides a practical way to develop new drugs or other molecules with much less detailed, expensive experimentation.
Learn how Google DeepMind and GovTech Singapore uses lightweight on-device Gemma models to intercept conversational scams in private chats with zero cloud data egress.