# Adaptive-Batch Proximal Armijo Training

- ID: 1843
- Canonical URL: https://synthcore.org/idea/1843/adaptive-batch-proximal-armijo-training
- API JSON: https://synthcore.org/api/idea/1843.json
- API Markdown: https://synthcore.org/api/idea/1843.md
- Verification status: unverified
- Source: [arXiv:2608.05460](https://arxiv.org/abs/2608.05460)
- Category: optimization
- Solves: stability, sample-efficiency, accuracy
- ML areas: optimizer, training, regularization
- Math tags: optimization, probability, convex-analysis, dynamical-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 5/10

## Idea description

Replace a fixed-batch SGD or proximal-gradient update by a stochastic proximal-subgradient step whose step size is backtracked against an empirical sufficient-decrease condition. If the condition is too noisy or repeatedly fails, enlarge the batch and retry; otherwise retain the current batch, allowing sample size to grow only when needed.

## Mathematical statement

The paper studies the structured objective \(\vPhi(x)=\mathbb{E}_{\mu}[\varphi(\xi,x)]+\psi(x)\), where \(x\in\mathbb{R}^{d}\), \(\varphi(\xi,x)\) is a potentially nonsmooth and nonconvex sample loss, and \(\psi\) is proper, lower semicontinuous, and prox-bounded. For a batch of size \(m_k\), define the empirical objective \(\widehat{\vPhi}_k(x)=m_k^{-1}\sum_{i=1}^{m_k}\varphi(\xi_i,x)+\psi(x)\), and choose a stochastic subgradient \(v_k\in\partial \widehat{\mathbf{E}}_\varphi^{k}(x_k)\), where \(\widehat{\mathbf{E}}_\varphi^{k}(x)=m_k^{-1}\sum_i\varphi(\xi_i,x)\). Proposition 3 states that locally there are \(W\) and \(\vartheta>0\) such that, for any \(x\in W\), \(v\in\partial\mathbf{E}_{\varphi}^{k}(x)\), and \(w\in\operatorname{prox}_{\gamma\psi}(x-\gamma v)\) with \(0<\gamma<\vartheta\), \(\vPhi_k(w)\leq\vPhi_k(x)-\sigma\|w-x\|^2\), where \(\sigma>0\) is the decrease coefficient. The implementation uses the same inequality with an empirical noise allowance \(\epsilon_k\): \(\widehat{\vPhi}_k(w)\leq\widehat{\vPhi}_k(x)-\sigma\|w-x\|^2+\epsilon_k\).

## Key formulas

- $$\min_{x\in\mathbb{R}^{d}}\vPhi(x):=\mathbb{E}_{\mu}\big[\varphi(\xi,x)\big]+\psi(x).$$
- $$\vPhi_k(w)\leq\vPhi_k(x)-\sigma\|w-x\|^{2},$$
- $$w\in\operatorname{prox}_{\gamma\psi}\left(x-\gamma v\right),\quad\text{with }\gamma\in(0,\vartheta).$$
- $$\widehat{\vPhi}_k(x)=\frac{1}{m_k}\sum_{i=1}^{m_k}\varphi(\xi_i,x)+\psi(x),\qquad x_{k+1}=\operatorname{prox}_{\gamma_k\psi}\left(x_k-\gamma_k v_k\right),\qquad \widehat{\vPhi}_k(x_{k+1})\leq\widehat{\vPhi}_k(x_k)-\sigma\|x_{k+1}-x_k\|^2+\epsilon_k.$$

## Implementation notes

(1) Integrate this into the optimizer update for trainable weights \(x\), after backpropagation has produced a minibatch subgradient or gradient \(v_k\). Use a regularizer \(\psi\) with a cheap exact proximal map: group-lasso, elementwise lasso, a parameter-norm constraint, or a blockwise pruning constraint. Do not apply the prox to normalization statistics or optimizer state. Evaluate the loss on a held-out verification minibatch from the same or a larger batch, while evaluating \(\psi\) exactly. (2) Pseudocode: initialize batch size \(m\), step size \(\gamma\), shrink factor \(\beta\in(0,1)\), decrease coefficient \(\sigma\), and tolerance \(\epsilon\). At iteration \(k\), draw a batch \(B_k\) of size \(m_k\), compute \(v_k=\nabla_x[m_k^{-1}\sum_{\xi\in B_k}\varphi(\xi,x_k)]\), propose \(z=\operatorname{prox}_{\gamma\psi}(x_k-\gamma v_k)\), and test \(\widehat{\vPhi}_k(z)\leq\widehat{\vPhi}_k(x_k)-\sigma\|z-x_k\|^2+\epsilon_k\). If the test passes, set \(x_{k+1}=z\) and optionally increase \(\gamma\) by at most \(1/\beta\). If it fails, replace \(\gamma\leftarrow\beta\gamma\) and retry. After two or three failures at the minimum allowed step, double \(m_k\), recompute the gradient and proposal, and retry. Keep \(m_{k+1}\geq m_k\), and cap the batch at the dataset size. (3) The paper supplies the proximal sufficient-decrease structure and the fact that an unbounded, nondecreasing sample sequence can be enough for convergence; the implementation estimates the empirical objective and gradient noise. Set \(\epsilon_k=c\,\widehat{s}_k/\sqrt{m_k}\), where \(\widehat{s}_k\) is the sample standard deviation of per-example losses, or use a conservative fixed fraction of the observed loss decrease. Estimate stationarity with \(r_k=\|x_k-x_{k+1}\|/\gamma_k\), the proximal-gradient residual. (4) First experiment: train a small ResNet-18 on CIFAR-10 and a 2-layer MLP on MNIST, comparing SGD, fixed-batch proximal SGD, and this adaptive method with identical maximum examples and wall-clock accounting. Use group-lasso on convolutional filters as \(\psi\). Measure loss versus examples, rejected proposals, average batch size, gradient evaluations, final accuracy, residual \(r_k\), and achieved sparsity. Success means fewer examples or fewer unstable updates at equal accuracy, monotone smoothed training loss despite increasing nonconvexity, and no significant increase in wall-clock time; a stronger result is equal accuracy with substantially smaller average batches than a conservative fixed-batch baseline.

## Disclaimer

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