# Convex-hull difficulty curriculum

- ID: 2859
- Canonical URL: https://synthcore.org/idea/2859/convex-hull-difficulty-curriculum
- API JSON: https://synthcore.org/api/idea/2859.json
- API Markdown: https://synthcore.org/api/idea/2859.md
- Verification status: unverified
- Source: [arXiv:2608.29972](https://arxiv.org/abs/2608.29972)
- Category: training
- Solves: sample-efficiency, accuracy, generalization
- ML areas: curriculum, embedding, training, data-augmentation
- Math tags: probability, convex-analysis, geometry, large-deviations
- Ratings: usefulness 5/10; difficulty 5/10; novelty 7/10

## Idea description

Interpret the Cramér energy of an embedding as the logarithm of the number of random in-distribution samples required to reach it through a convex hull. Use this quantity to stratify training data into geometric difficulty levels and schedule exposure from low-energy central points toward high-energy boundary points, or preferentially replay high-energy points after the model has learned the core distribution.

## Mathematical statement

The paper identifies \(\exp(\Lambda_K^*(x))\), up to polynomial factors in dimension, with the number of independent samples needed for \(x\) to be captured by their random convex hull. Here \(K\subset\mathbb{R}^d\) is the embedding support, \(x\in\operatorname{int}(K)\), and \(\Lambda_K^*(x)\) is the Cramér transform of the uniform measure on \(K\). The depth comparison \(\Lambda_K^*(x)\le -\log q_K(x)\le \Lambda_K^*(x)+\tfrac12\log d+C\) means that increasing energy corresponds, within an additive \(O(\log d)\) uncertainty, to decreasing half-space centrality. For a finite memory bank \(z_1,\ldots,z_B\), use the regularized empirical energy \(E_i=\max_\theta[\langle\theta,z_i\rangle-\widehat\Lambda(\theta)-\tfrac{\tau^2}{2}\|\theta\|^2]\). Define curriculum bins by empirical quantiles of \(E_i\), avoiding absolute thresholds because the theorem’s additive constant and finite-sample bias are unknown.

## Key formulas

- $$\exp\!\left(\Lambda_K^{*}(x)\right)\ \text{is, up to polynomial factors in }d,\ \text{the number of independent samples needed for }x\text{ to be captured by their random convex hull}$$
- $$\Lambda_{K}^{*}(x)\leq-\log q_{K}(x)\leq\Lambda_{K}^{*}(x)+\frac{1}{2}\log d+C$$
- $$E_i=\max_{\theta\in\mathbb{R}^{d}}\left[\langle\theta,z_i\rangle-\log\left(\frac{1}{B}\sum_{j=1}^{B}e^{\langle\theta,z_j\rangle}\right)-\frac{\tau^2}{2}\|\theta\|_2^2\right]$$
- $$p_t(i)=(1-\rho_t)\frac{1}{N}+\rho_t\frac{\exp(\alpha_t\widetilde E_i)}{\sum_{j=1}^{N}\exp(\alpha_t\widetilde E_j)},\qquad \widetilde E_i=\frac{E_i-\operatorname{median}(E)}{\operatorname{MAD}(E)+\varepsilon}$$

## Implementation notes

Integrate this into the data loader for supervised classification or contrastive representation learning. Maintain a memory bank of embeddings and per-example energies updated every one or two epochs; compute each energy with 3–5 regularized dual-ascent steps and refresh only a random subset to control overhead. Rank training examples by robustly standardized energy \(\widetilde E_i\), divide them into four empirical quantile bins, and define a schedule \(\rho_t\) and \(\alpha_t\): begin with nearly uniform sampling and low \(\alpha_t\), then gradually increase both emphasis on high-energy examples. Use importance weights \(w_i=1/(Np_t(i))\), clipped to `[0.2,5]`, so the curriculum changes sampling without changing the target empirical risk. Pseudocode: `E=update_dual_energy(memory_bank); Etilde=(E-median(E))/(MAD(E)+eps); rho=rho_max*min(1,epoch/warmup); p=(1-rho)/N+rho*softmax(alpha*Etilde); idx=sample(p); loss=clip(1/(N*p[idx]),.2,5)*CE(model(x[idx]),y[idx])`. The paper supplies the geometric interpretation; the schedule, refresh rate, clipping, and \(\alpha_t\) are empirical. Test first on CIFAR-100 with a ResNet-18 against uniform sampling, class-balanced sampling, and loss-based hard-example mining. Measure validation accuracy and loss versus examples seen, rare-subcluster accuracy, calibration on boundary examples, and wall-clock overhead. A successful curriculum should improve accuracy or loss at fixed examples and compute, not merely increase gradient variance.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.