Feature Normalization under Finite Training Budgets

Johan Larsson

stat.MLOct 12, 2026

Feature Normalization under Finite Training Budgets

Authors: Johan Larsson

Organizations: Department of Mathematical Sciences, University of Copenhagen, Universitetsparken 5, 2100 Copenhagen, Denmark

Abstract

Standardizing a rare feature can help stochastic gradient descent learn its effect within a finite budget, but it also changes the noise cost of learning. We characterize the lowest rare-subgroup risks attainable by standardized and unscaled training when each chooses a nonnegative constant learning rate and a deterministic stopping time under the same observation cap. For two independent binary features, we derive both optimized risks as prevalence vanishes while the expected number of rare observations remains finite. Uniform control over rates and stopping times reduces each limiting oracle to a scalar minimization. With positive noise, the preferred scaling changes exactly once as we move signal to the rare feature while the limiting risk at initialization stays fixed and positive. The formulas also explain how noise and budget affect the comparison. Separate finite-prevalence bounds favor standardization on a rare-dominant signal family and unscaled training on a common-dominant family. The results concern final iterates with population preprocessing and fresh observations. Exact-moment searches assess the approximation at finite prevalence. In a controlled study, both orderings persist under observation reuse, estimated preprocessing, and intercept fitting when tuning choices are fixed before evaluation. Selecting a predictor after observing training can reverse an ordering, even when selection uses exact population risk.

Figures & tables

Panel of Figure 1 — Figure 1: Normalization changes learning paths, and its effect on risk depends on the signal.

Figure 2: Tuning does not erase the effect of normalization. Independent binary features have prevalences

1/2

and

q=10^{-4}

, with

(\beta_{C}^{*},\beta_{R}^{*})=(0.1,1)

(left) or

(1,0.1)

(right) and noise variance one. Under the stated population setup, curves show the lowest exact rare risk over a finite rate grid and every integer stop within each cap, including zero. Both panels use the same axes, and lower risk is better. This illustrates \cref thm:conference-predictive, which covers all nonnegative constant rates. See \cref sec:predictive-intro-figure for numerical details.

Figure 3: Normalization changes the balance between incomplete learning and training variability, even after tuning. Panels use

(\beta_{C}^{*},\beta_{R}^{*})=(0.1,1)

(left) and

(1,0.1)

(right), with prevalence

q=10^{-4}

, noise variance one, and observation cap

M=20{,}503

. Each method selects its rate and stop to minimize exact rare-subgroup risk over the search grid used in \cref fig:conference-tuned-intro. Bars show the common and rare coefficients’ contributions to that risk. Colors distinguish incomplete learning, feature-sampling variation, and observation noise, as in \cref eq:conference-decomposition. Each method’s two bars sum to its total rare-subgroup risk.

Fresh observations, fitted intercept
	Rare risk		Reduction from calibration		SD-minus-U gap
Selection	U	SD	U	SD	Mean	MCSE
Separate calibration	$0.2409$	$0.1364$	—	—	$-0.1046$	$0.00364$
Validation (2048 rows)	$0.0268$	$0.0344$	$0.2141$	$0.1020$	$+0.0075$	$0.00132$
Exact population risk	$0.0011$	$0.0175$	$0.2399$	$0.1189$	$+0.0164$	$0.00128$
Fresh observations, fixed zero intercept (baseline)

Table 1: Rare risk and gains from selection with

(\beta_{C}^{*},\beta_{R}^{*})=(0.1,1)

q=0.02

, and

M=204

, with fresh observations and population preprocessing. The fitted-intercept arm and baseline (arms 2 and 1 in \cref tab:bridge-arms) share the observation cap and differ only in whether an intercept is fitted; all coefficients are initialized at zero. Positive reductions indicate improvement over the separately calibrated choice for the same scaling; negative SD-minus-U gaps favor SD. Means use 4096 paired evaluation runs. MCSEs refer to the paired gaps and condition on the calibration choices. \Cref sec:bridge-exact-calibration gives exact expected-risk calibration benchmarks for the same candidate family.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Family	Maximum prevalence $Q$	Gap bound	Certificate leaves
Rare	$1/20$	$\Delta_{R}\geq 1/1000$	$77{,}510$
Common	$1/25$	$\Delta_{C}\geq 1/50$	$103$
Rare	$1/50$	$\Delta_{R}\geq 7/1000$	$76{,}623$
Common	$1/50$	$\Delta_{C}\geq 9/200$	$58$
Rare	$10^{-4}$	$\Delta_{R}\geq 11/1000$	$7{,}158$
Common	$10^{-4}$	$\Delta_{C}\geq 11/200$	$105$

Appendix

Table 2: Certified gap bounds for

0<q\leq Q

1\leq\tau\leq 4

, and

\sigma^{2}=1

. Each bound holds throughout the corresponding signal family. Certificate leaves count the accepted boxes in the interval certificates.

$\nu$	$L_{U}$	$L_{S}$	Preferred scaling
0	0.067668	0.069359	U
0.1	0.109877	0.103572	S
1	0.256267	0.232599	S
100	0.500000	0.502306	U

Appendix

Table 3: Limiting oracle risks across noise variances for

s=0.1

r=1

, and

\tau=2

. The preferred scaling has the smaller risk: U at the smallest and largest noise variances shown, and S at the intermediate values.

Figure 4: Additional common features change the cost of normalization at fixed signal strength. The sums of squared common and rare coefficients are

(s,r)=(0.01,1)

(left) or

(1,0.01)

(right), with noise variance one. Caps are

M=102

q=0.02

and

M=20{,}002

q=10^{-4}

, giving

Mq(1-q)\approx 2

. Curves show SD-minus-U rare risk after separate searches over finite stable-rate grids and all integer stops; negative values favor SD. Each panel has its own vertical scale. \Cref sec:common-block-numerics gives all settings and checks.

Figure 5: Dimension comparisons across all three prevalences and budgets. The top row uses

(s,r)=(0.01,1)

and the bottom row uses

(1,0.01)

, holding total squared signal fixed within each row. Negative SD-minus-U rare risk favors standardization. Each scaling searches its own finite grid of stable rates and every integer stop through the cap. The rows have different vertical scales. At the larger prevalences, the size of SD’s rare-signal advantage can decrease after initially increasing with dimension.

Panel of Figure 6 — Figure 6: Exact finite-grid selections approach the limiting oracle predictions. Colored curves connect finite-grid results; black dashed curves connect limiting predictions at the sampled settings. Panels (b)–(d) use nominal target budgets, so coarse caps also reflect rounding. Lines do not certify intervening crossing locations.

Arm	Sampling	Estimated preprocessing	Intercept
1	Fresh	None	Fixed zero
2	Fresh	None	Fitted from zero
3	Reuse	None	Fixed zero
4	Reuse	Scales	Fixed zero
5	Reuse	None	Fitted from zero
6	Reuse	Scales	Fitted from zero

Appendix

Table 4: Matched training arms, in the order shown in \cref fig:bridge-controlled. Centering and scales use population values unless listed as estimated. “None” denotes no estimated preprocessing. U uses divisor one in every arm. Every fitted intercept is unscaled and uses the same learning rate as the transformed coefficients.

Figure 7: Both calibrated risk orderings persist across the eight training arms. Negative SD-minus-U rare risk favors SD. Colors distinguish the three caps; bars show two paired Monte Carlo standard errors over 4096 evaluation replications, conditional on the calibration choices. The last two rows successively add empirical centering and response-mean initialization to reuse with estimated scales and a fitted intercept. These comparisons concern two signal pairs and finite searches, not the full theorem families.

Figure 8: Changing selection on the same candidate paths at the largest cap for each prevalence. Calibrated choices are fixed before evaluation; the other points select by rare validation loss with the indicated sample size. Negative gaps favor SD. The blue curve includes all changes through arm 8. Bars show two paired Monte Carlo standard errors, conditional on the calibration choices. All panels share the same vertical scale and limits, with linear spacing between

-0.05

and

0.05

and logarithmic spacing outside this interval to keep both small and large gaps visible. Tick labels give the original risk differences. Lines connect discrete selection procedures and do not imply monotonic behavior with sample size.

Fitted intercept
Selection	Scaling	Median	5th pct.	95th pct.	Worse (%)
Exact risk	U	$0.1456$	$0.0067$	$0.7747$	$0.0$
Exact risk	SD	$0.0626$	$0.0012$	$0.4083$	$0.0$
Validation (2048)	U	$0.1204$	$-0.0268$	$0.7455$	$13.3$
Validation (2048)	SD	$0.0477$	$-0.0282$	$0.3915$	$22.3$
Fixed zero intercept (baseline)

Appendix

Table 5: Selection-gain distributions for the example in \cref tab:bridge-selection: fresh observations,

q=0.02

M=204

, and

(\beta_{C}^{*},\beta_{R}^{*})=(0.1,1)

. Quantiles use 4096 evaluation runs. “Worse” is the percentage with negative gain, meaning higher population rare risk than the calibrated predictor of the same scaling.

Figure 9: Empirical cumulative distributions of selection gains for \cref tab:bridge-gain-distributions. A curve farther to the right indicates larger gains. The horizontal scale is symmetric logarithmic, linear for absolute gains at most

0.05

; negative gains mean selection worsens risk. Both arms and scalings use the same 4096 evaluation streams.

Fitted intercept
Selection	Scaling	Common	Intercept	Rare	Cross	Total
Calibrated	U	$0.0142$	$0.0573$	$0.1677$	$0.0018$	$0.2409$
Calibrated	SD	$0.0015$	$0.0013$	$0.1326$	$0.0009$	$0.1364$
Exact risk	U	$0.0008$	$0.2208$	$0.2235$	$-0.4439$	$0.0011$
Exact risk	SD	$0.0005$	$0.0033$	$0.0201$	$-0.0064$	$0.0175$
Validation (2048)	U	$0.0131$	$0.2311$	$0.2362$	$-0.4536$	$0.0268$

Appendix

Table 6: Mean rare-risk contributions for the primary example in \cref tab:bridge-selection, using the same 4096 paired evaluation runs. Columns give

e_{C}^{2}/8

a^{2}/2

d^{2}/2

ad

, and their sum. Rounding can obscure exact addition. The baseline’s centered intercept and cross terms are exactly zero.

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 584 papers

Oct 12, 2026

Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features

We study the last iterate of stochastic gradient descent (SGD) on streaming least squares with discretely distributed features (Slock's model), which decouples the dynamics across eigendirections. Under power-law source and capacity conditions, we derive the exact finite-time risk and asymptotic equivalents of constant and Warmup-Stable-Decay (WSD) schedules. With a tuned base learning-rate, the resulting scaling law decays as

Θ(T^{-q})

, where

T

is the horizon, and

q

is independent of the cooldown length

c \in (0,1]

but is strictly smaller for the constant schedule: any cooldown of fixed relative length

c > 0

, however short, improves the risk by a polynomial factor, while its length only affects the constant, which is minimized by linear decay (

c = 1

). Finally, we show that the optimal risk depends on the batch size

b

and horizon

T

only through

bT

, up to a critical batch size.

Noé Colomban, Francis Bach, Fabian Schaipp

Inria - École Normale Supérieure PSL Research University

Learning Rate Scheduling Stochastic Gradient Descent Linear Regression Streaming Algorithms

Ask PDF

Oct 9, 2026

Beyond Second-Order Information: Paid Logistic Regression with Noisy Features

We consider online binary prediction with paid stochastic features, where the learner can spend resources to obtain better observations of the underlying features. This setting is motivated by applications such as medical testing, where additional cost can provide more precise measurements of patient's features for predicting a binary outcome. At each round, a latent feature is drawn i.i.d., the response is generated through a logistic model, and the learner chooses how much to pay before observing a noisy version of the feature. The goal of learner is to jointly control prediction loss and acquisition cost. In contrast to the former result on the online linear regression with paid features, covariance information alone is no longer sufficient: two noise distributions with the same covariance may induce different optimal logistic losses, and lower variance can even lead to higher loss. Under a structural ordering in which larger payments yield better observations by removing independent noise, we obtain

\widetilde O(\sqrt{T})

regret when the noise structure is known and

\widetilde O(T^{2/3})

regret when it is unknown, with matching lower bounds up to logarithmic factors.

Sanghwa Kim, Kyoungseok Jang, Se-Young Yun

Kim Jaechul Graduate School of AI, KAIST Seoul 02455, Republic of Korea · Department of AI, Chung-Ang University Soeul 06974, Republic of Korea

Online Learning Logistic Regression Cost-Sensitive Learning

Ask PDF

Mar 2, 2026

Scaling Laws of SignSGD in Linear Regression: When Does It Outperform SGD?

We study scaling laws of signSGD under a power-law random features (PLRF) model that accounts for both feature and target decay. We analyze the population risk of a linear model trained with one-pass signSGD on Gaussian-sketched features. We express the risk as a function of model size, training steps, learning rate, and the feature and target decay parameters. Comparing against the SGD risk analyzed by Paquette et al. (2024), we identify a drift-normalization effect and a noise-reshaping effect unique to signSGD. We then obtain compute-optimal scaling laws under the optimal choice of learning rate. Our analysis shows that the noise-reshaping effect can make the compute-optimal slope of signSGD steeper than that of SGD in regimes where noise is dominant. Finally, we observe that the widely used warmup-stable-decay (WSD) schedule further reduces the noise term and sharpens the compute-optimal slope, when feature decay is fast but target decay is slow.

Jihwan Kim, Dogyoon Song, Chulhee Yun

Seoul National University & KAIST InnoCORE LLM · University of California, Davis · KAIST

Sign-Based Optimization Random Feature Methods Linear Regression Scaling Laws Stochastic Gradient Descent

Ask PDF

Abstract

Statistical Learning Theory

Explore similar work

Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features

Beyond Second-Order Information: Paid Logistic Regression with Noisy Features

Scaling Laws of SignSGD in Linear Regression: When Does It Outperform SGD?