acceptodds
Under review as a conference paper at ICLR 2027

BOLT: Blockwise Residual Ridge Solving for Frozen-Feature Classification

Abstract

Frozen-feature classification repeatedly fits a prediction head on representations produced by a fixed encoder. Although closed-form ridge regression avoids iterative optimization, jointly fitting a wide random-feature head incurs expensive matrix factorizations and large temporary solver memory, while iterative classifier training requires repeated parameter updates. We introduce BOLT (Blockwise Optimizer-free Learning with cyclic refinemenT), a blockwise residual solver for this refitting task. BOLT first decomposes the wide solve into smaller blockwise problems through a sequential residual cascade, enabling a fast one-pass fit. Cyclic refinement then revisits these blocks to correct approximation errors and recover the joint ridge solution, while augmented QR improves numerical stability without forming normal equations. Across five frozen-feature vision benchmarks, BOLT maintains competitive predictive accuracy while substantially reducing peak solver memory compared with the matched joint solve.

Primary area:
optimization
Keywords:
Frozen-feature classification, random features, ridge regression, blockwise optimization, kernel approximation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_CWizOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents BOLT, a blockwise ridge solver for classification on cached, frozen representations. It fits fixed feature blocks sequentially to residual targets, optionally performs damped cyclic refinement, and solves block subproblems using augmented QR. The experiments assess predictive accuracy, fitting time, and peak GPU memory relative to joint ridge and other classifier baselines.

Critical strengths
  1. Substantial memory savings under a matched comparison. Table 1 reports approximately 64–72% reductions in peak allocated GPU memory relative to a joint solver using the same feature bank and regularization. Preserving feature capacity while reducing temporary working memory provides meaningful practical value for repeatedly fitting classification heads.

  2. A clear connection between approximation and refinement. The paper explicitly distinguishes the single-sweep approximation from the limiting joint ridge solution and provides a convergence argument under stated assumptions. Table 4 shows that refinement recovers most of the measured test-accuracy gap. This makes the method’s approximation behavior and computational trade-offs interpretable.

Critical weaknesses
  1. Limited additional methodological contribution. As the manuscript acknowledges, the forward cascade is the first Gauss–Seidel/BCD cycle from zero initialization, and refinement continues the block updates with damping. lgorithm 3 in "Large Scale Kernel Learning using Block Coordinate Descent"(https://arxiv.org/pdf/1602.05310) already describe the corresponding random-feature ridge block minimization, up to regularization normalization and choices of block visitation. The convergence proof also specializes standard BCD results. The potentially distinctive contribution therefore lies primarily in the implementation and empirical trade-offs for frozen-feature refitting. I remain unconvinced that the current evidence establishes sufficient additional practical insight or benefit over established blockwise ridge solving.

  2. Incomplete evidence for the practical trade-off relative to the existing BCD baseline. Table 2 reports higher mean accuracy for BCD-Classic than either BOLT variant, but provides no corresponding fitting-time or peak-memory measurements. Its sweep budget, visitation order, damping, stopping rule, and numerical solver are also insufficiently specified. Table 4 shows that increasing refinement from one to twenty sweeps improves accuracy from 74.69% to 76.72% while increasing fitting time from approximately 0.95 s to 15.95 s. This characterizes BOLT’s internal trade-off, but leaves its comparative value unclear. Resource measurements for the existing BCD baseline under the same cached-input protocol are important for assessing the practical contribution.

Questions for authors
  1. How does BCD-Classic differ from BOLT-Sweep in sweep budget, visitation order, initialization, damping, and numerical solver? Which differences explain the accuracy results in Table 2?

  2. Can you report fitting time and peak memory for BCD-Classic at comparable optimization error or predictive accuracy, specifying whether feature matrices and block factorizations are cached or recomputed? Appendix C.4 demonstrates a synthetic stability benefit for augmented QR; how does this choice affect the practical time–accuracy–memory trade-off?

1 comment

Thank you for recognizing BOLT's memory savings and refinement mechanism. We tested solver settings, caching, and numerical accuracy.

Contribution and related work. BOLT combines a full-bank residual pass, damped refinement, and augmented QR for refitting classifiers on cached frozen representations. It shares the cited algorithm's BCD foundation. QR, damping, and block order affect numerical behavior and finite-sweep iterates. We will add a direct technical comparison with Algorithm 3 of the cited work.

Q1. How does BCD-Classif differ from BOLT-Sweep in sweep budget, visitation order, initialization, damping, and numerical solver? Which differences explain the accuracy results in Table 2?

For consistency with our tables, we refer to this method as BCD-Classic. The core implementation starts from zero, visits blocks in forward order, and uses alpha=1 and augmented QR. It runs for at most five cycles, with a relative coefficient-change threshold of 1e-3. It caches block features but recomputes QR factors. BOLT-Sweep uses three alternating sweeps with alpha=0.8, also starting from zero with QR block solves. We apply the damped update to the stored prediction coefficients:

Wknew=(1−α)Wkold+αWkexact.W_k^{\mathrm{new}}=(1-\alpha)W_k^{\mathrm{old}}+\alpha W_k^{\mathrm{exact}}.

Our new controls fix the feature bank, targets, regularization, initialization, and block solver. On CIFAR-100/ViT (2,048 RBF features, block width 256, ridge=0.1), three paired seeds gave:

SweepsAlphaOrderAccuracy (%)
30.8Alternating77.48
30.8Forward77.63
31.0Alternating77.60
31.0Forward77.76
51.0Forward78.09

The results show how damping, order, and sweep budget affect accuracy under the same ridge objective.

We also checked Figure 3(b)'s ReLU setting: 6 blocks of 192, ridge=0.01, alpha=0.8, and alternating sweeps. Across ten paired seeds on CIFAR-100/ViT, refinement reduced the mean accuracy gap to joint QR from 1.977 percentage points after one sweep to 0.011 after twenty sweeps. The mean absolute gap was 0.065 points; 8 of 10 seeds were within 0.1 points. The main and audit implementations matched in test accuracy across 40 checks. With the same feature bank partitioned into four, six, or eight blocks, the mean gaps after twenty sweeps were 0.012, 0.011, and 0.043 points, respectively.

Q2. Can you report fitting time and peak memory for BCD-Classic at comparable optimization error or predictive accuracy, specifying whether feature matrices and block factors are cached or recomputed? Appendix C.4 demonstrates a synthetic stability benefit for augmented QR; how does this choice affect the practical time–accuracy–memory trade-off?

First, we compared three caching strategies using the same block updates. For 20 forward BCD sweeps with alpha=1 in the RBF setting above, all three gave identical objective values and 78.82% accuracy:

FeaturesQR factorsFit (s)Peak (MiB)
RecomputedRecomputed1.8769516.5
CachedRecomputed1.5662858.3
RecomputedCached0.5288860.1

All three had a normalized objective gap of 0.04495 to joint QR. Because objective values and accuracy matched, this comparison isolates the cost of caching. The cache policies change computational cost without changing the measured solution quality. Reusing QR factors reduced fitting time by about 3.5x. Timings include preparation, feature construction, factorization, and updates, but exclude diagnostic evaluation. The five-dataset comparisons use three paired seeds and three timing runs per seed.

Second, for each pre-specified objective-gap threshold, we recorded the first checkpoint that met it, using FP64 augmented QR as the reference. Both methods could run up to 1,000 sweeps or 120 s. On CIFAR-100/ViT with ReLU features, cached BOLT and BCD reached a normalized gap below 1e-3 in 0.420 s and 0.422 s. Both had the same measured peak GPU allocation of 507.9 MiB under the matched implementation and caching policy. This shows comparable refinement costs at the same tolerance. Streamed QR required 0.146 s and 439.5 MiB. All three seeds met the threshold. Reported times are averaged over three runs for each of three seeds.

Third, checks on real feature matrices found both low-precision factorization failures and loss of positive definiteness during accumulation. In one R18 case at width 8,192, the minimum eigenvalue was about -0.0089 after FP32 accumulation versus 0.1 after FP64 accumulation. This shows a practical failure mode of forming normal equations in low precision. We include streamed QR as a numerically stable joint baseline.

Within each comparison, software, hardware, cached inputs, and feature settings were matched. Memory figures are peak PyTorch-allocated GPU memory.

Reviewer_eDwbOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper looks at refitting closed-form ridge heads on frozen, cached encoder features, where a joint solve over a wide random-feature bank is costly in compute and solver memory. BOLT instead splits the bank into K blocks and fits them one after another, each on the residual left by the earlier ones. This pass is essentially one Gauss-Seidel cycle of block coordinate descent, so it only approximates the joint solution; optional damped cyclic sweeps then re-solve each block against the current global residual, and a standard BCD argument shows this converges to the joint ridge minimizer. Each block is solved with augmented QR so the condition number isn't squared. On five frozen-feature vision benchmarks, a single pass uses about a third of the matched joint solve's peak memory while giving up a couple of points of accuracy, and further refinement sweeps close most of that gap.

Critical strengths

Theorem 1 and Proposition 1 are correct; the memory reduction is real and is measured against the right control.

Critical weaknesses
  • Sec. 5.3 states that BOLT-Block's fit time is slightly higher than the joint solve on the four non-flowers datasets. Table 1 says the opposite and Table 6 lists ~1.1 times speedups on all four.

  • The algorithm already exists, and the paper doesn't confront it. Tu, Roelofs, Venkataraman & Recht (2016, arXiv:1602.05310) minimize 1n∣ZW−Y∣F2+λ′∣W∣F2\frac{1}{n}\\|Z W-Y\\|_F^2+\lambda^{\prime}\\|W\\|_F^2 over random-feature blocks (eq. 1 with λ=nλ′\lambda=n \lambda^{\prime}). Their Algorithm 3 starts at W=0W=0, removes a block's old contribution from the running prediction, solves the block ridge problem on the partial residual, and sweeps again

\begin{equation*} W_k^{+}=\left(Z_k^{\top} Z_k+\lambda I\right)^{-1} Z_k^{\top}\left(Y-\sum_{j \neq k} Z_j W_j\right) . \end{equation*}

That is BOLT with α=1\alpha=1 : the first sweep from zero is the "residual cascade", later sweeps are "cyclic refinement". Huang et al. (ICASSP 2014) also fit random-feature blocks on residuals, with factor reuse. What's left (augmented QR, a fixed α=0.8\alpha=0.8, fixed block order, cached encoder features) are standard choices, and Theorem 1 is, as App. A. 1 itself says, a specialization of Tseng/Wright with no rate, so it can't explain why 1-20 sweeps should be a good trade-off. This is the main reason I lean reject.

Questions for authors
  • Was the code run per Algorithm 1 or per Figure 2? They differ. Figure 2 accumulates Lk=L_k= Lk−1+αZkβkL_{k-1}+\alpha Z_k \beta_k with unscaled βk\beta_k, then sweeps with Rkwithout =Y−(L−Zkβkold )R_k^{\text {without }}=Y-\left(L-Z_k \beta_k^{\text {old }}\right) and L←L \leftarrow L+Zk(βknew −βkold )L+Z_k\left(\beta_k^{\text {new }}-\beta_k^{\text {old }}\right), which preserves C=L−∑kZkβkC=L-\sum_k Z_k \beta_k, so it solves ridge against Y−CY-C, not YY. With K=n=m=c=1,Z=Y=1,λ=1,α=0.8K=n=m=c=1, Z=Y=1, \lambda=1, \alpha=0.8 : the forward pass gives β=0.5\beta=0.5 (already optimal), L=0.4L=0.4; the sweep moves to β=0.55\beta=0.55 and stays, with L(0.55)=0.505>\mathcal{L}(0.55)=0.505> 0.5. If the code follows the figure, Fig. 3(b) and Tables 4-5 converge to the wrong point.

  • What exactly is BCD-Classic (sweeps, order, damping, stopping rule), and what do you consider the delta over Tu et al. 2016 / Huang et al. 2014?

1 comment

Thank you for noting the memory result. We checked the algorithm and timing claims. BOLT-Block is one pass; BOLT-Sweep adds damped visits; BCD-Classic is the undamped forward-sweep baseline.

Contribution and prior work. Tu et al. (2016, Algorithm 3) and Huang et al. (ICASSP 2014) use residual block updates for random-feature ridge regression. We have added both comparisons and now describe the convergence theorem as a guarantee for our implementation, without claiming a new block update or convergence rate. BOLT evaluates finite-sweep accuracy, time, and GPU memory for classifiers on cached ResNet/ViT features, with augmented QR and a joint QR control on the same feature bank. Tu et al. is an arXiv preprint; the revised paper includes a direct technical comparison. At width 4,096 on CIFAR-100/ViT (three seeds), one-pass BOLT versus joint QR used 531/2,529 MiB, took 0.317/0.455 s, and reached 78.89/80.84% accuracy. This study is separate from Table 1.

Q1. Did the code follow Algorithm 1 or Figure 2? Do Figure 3(b) and Tables 4-5 converge to the wrong point? The main implementation stores the damped block coefficients. Let L be their summed prediction. Each visit, including the first, computes Uk=ridge(Zk,Y−L+ZkWk)U_k = ridge(Z_k, Y - L + Z_k W_k), then Wk+=(1−α)Wk+αUkW_k^+ = (1-α)W_k + αU_k and L+=L+Zk(Wk+−Wk)L^+ = L + Z_k(W_k^+ - W_k). Thus L remains the prediction of the stored coefficients after every visit. The submitted Figure 2 scales L but retains an unscaled coefficient, giving the offset in the reviewer's example; Algorithm 1 does not state the first-visit damping. Both have been revised to match the implemented update.

For one block, every solve returns the same ridge optimum. Each damped visit multiplies the remaining coefficient error by 1-α, so the coefficient converges to that optimum from zero initialization. With the reviewer's Z = Y = λ = 1 and α = 0.8, the stored coefficient is 0.4, 0.48, 0.496, ... and converges to 0.5. The corresponding ridge objective is 0.52, 0.5008, 0.500032, ... and converges to 0.5. Figure 3(b) and Tables 4-5 use this update. We also reran Figure 3(b)'s six-block ReLU setting on ten paired seeds, evaluating the training objective against FP64 joint QR on the same feature bank. The mean fraction of initial optimization error remaining fell from 11.82% after one pass to 0.44% after twenty; it decreased for every seed. The mean test-accuracy gap to matched joint QR fell from 2.032 to 0.061 percentage points (mean absolute gap 0.087).

Q2. What is BCD-Classic, and what differs from Tu/Huang? BCD-Classic starts at zero, visits fixed RBF blocks in forward order, uses augmented QR with α = 1, and stops after at most five sweeps or when the maximum relative coefficient change is below 0.001. All 15 pooled runs reached five sweeps. BOLT-Sweep starts at zero and uses three alternating sweeps with α = 0.8. Tu/Huang establish the residual block update. Our comparison measures its finite-sweep behavior and GPU resource use for a fixed cached encoder feature bank.

We controlled feature bank, targets, ridge value (0.1), initialization, and augmented-QR solver on CIFAR-100/ViT (2,048 RBF features, eight blocks, three paired seeds). Error remaining means the fraction of the initial objective gap to FP64 joint QR:

SweepsαOrderAccuracy (%)Error remaining (%)
11.0Forward76.7415.28
30.8Alternating77.4210.97
30.8Forward77.5310.32
31.0Alternating77.5310.95
31.0Forward77.729.92
51.0Forward78.048.10
Joint QR--79.41about 0

At three sweeps, undamped forward visits did best in this setting. With the bank already cached on GPU, solver-only times for one-pass BOLT, three-sweep BOLT, five-sweep BCD, and FP32 joint QR were 0.101, 0.302, 0.503, and 0.150 s. Peak PyTorch allocations were about 679 MiB for block solves and 1,706 MiB for joint QR. These are solver-only times; Table 1 reports full fitting time.

The submitted Table 2 BOLT-Sweep row came from a separate experimental script whose revisit update omitted the old-coefficient term. After correction, we reran all five datasets with the original seeds: mean accuracy changed from 84.13% to 84.37%. The revised table reports the new per-dataset values. We also rechecked BOLT-Block, BCD-Classic, and joint QR in the current software environment. Figure 3(b) and Tables 4-5 used the correct update above.

Sec. 5.3 timing. The original sentence was incorrect. Per-seed records and Tables 1 and 6 show BOLT-Block fitted 1.11-1.14 times faster on the four non-Flowers datasets and 1.57 times faster on Flowers102. We corrected the sentence and describe the width-2,048 gains as modest.

Reviewer_ntmmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Authors introduce BOLT, which is a blockwise residual ridge-regression solver for classification using frozen feature representations. Given a fixed encoder and a collection of random-feature blocks, BOLT replaces a single joint ridge-regression solve with a sequence of smaller closed-form problems.

To improve accuracy, BOLT introduces optional cyclic refinement, revisiting feature blocks using the current global residual. The authors establish that these updates correspond to cyclic block coordinate descent and converge to the unique joint ridge minimizer under positive regularization.

The authors evaluate BOLT across five frozen-feature vision benchmarks using ResNet, ViT, DINOv2, and handcrafted representations. Comparisons include a matched joint ridge solver, block coordinate descent, kernel approximation approaches, and iterative classification heads. The results demonstrate reductions of approximately 64–72% in peak solver memory on representative tasks, with modest fitting-time improvements.

Critical strengths
  1. BOLT replaces a large joint ridge-regression factorization with smaller blockwise solves while retaining the prescribed random-feature bank. This reduces temporary solver-memory requirements without reducing the number of available features. The reported peak-memory reductions of approximately 64–72% relative to the matched joint solver are meaningful, particularly for repeated classifier fitting when the full joint system is expensive to factorize.

  2. The paper explicitly characterizes the one-pass residual cascade as an approximation to joint ridge regression and connects cyclic refinement to block coordinate descent on a strongly convex objective. The convergence analysis establishes that repeated block updates approach the same unique optimum as joint ridge regression. Experiments demonstrate this behavior: on CIFAR-100/ViT, additional refinement reduces the accuracy gap to the joint solver from 2.11 to 0.08 percentage points. This provides a first principle mechanism for trading additional fitting computation against approximation error, rather than relying on an uncontrolled heuristic.

Critical weaknesses
  1. The paper explicitly shows that BOLT's sequential residual cascade corresponds to the first Gauss–Seidel cycle of block coordinate descent initialized at zero, while the proposed cyclic refinement simply continues these updates. The convergence guarantee consequently follows from established results for block coordinate descent on strongly convex objectives.

All of this is useful, but the paper does not clearly identify a new algorithmic mechanism beyond this application of existing numerical methods. This is essential because the main theoretical and algorithmic contributions appear to follow directly from established optimization techniques.

  1. Although there is improvement to fitting time, it incurs substantial accuracy losses on some datasets. For example, on CIFAR-100/ResNet-18, BOLT loses 3.93 percentage points relative to the matched joint solver while saving only 23 milliseconds. On CIFAR-100/ViT, the corresponding loss is 2.67 points for an 18-millisecond reduction.

The authors propose cyclic refinement to address this gap, but refinement introduces significant additional computation. These results raise doubts about whether BOLT occupies a favorable accuracy–latency operating point once approximation error is controlled.

Questions for authors

Q1 The paper establishes that BOLT's initial residual cascade is the first Gauss–Seidel cycle of block coordinate descent, while cyclic refinement corresponds to subsequent cycles. Could you please clarify the algorithmic contribution beyond standard block coordinate descent and augmented QR ridge solving?

Q2 The one-pass BOLT solver incurs noticeable accuracy losses relative to joint ridge regression, while cyclic refinement substantially increases fitting time. Could the authors provide a complete accuracy-versus-wall-clock comparison against the matched joint solver?

Q3 Since the feature blocks and regularization coefficient remain fixed, the augmented QR factorization for each block can be computed once and reused across subsequent refinement sweeps with changing residual targets. Does the implementation already cache and reuse these factorizations?

1 comment

Thank you for recognizing BOLT's memory savings and the connection between finite-sweep approximation and joint ridge fitting. We address your three questions below with additional controlled experiments.

Q1

BOLT provides a blockwise residual ridge solver for repeatedly fitting classifiers on cached, frozen representations. It uses the full, fixed random-feature bank and combines three components: a one-pass fit based on smaller blockwise solves; cyclic refinement toward the same joint ridge solution; and augmented QR subproblems that avoid explicitly forming normal equations.

For total width h=Km, blockwise fitting replaces a width-h factorization with K width-m solves, reducing temporary working storage without discarding features. Refinement then revisits the same blocks to reduce approximation error without changing the feature maps or inference architecture. Under the theorem's assumptions, including positive regularization and fixed blocks, these updates converge to the unique joint ridge minimizer.

The BCD interpretation explains why refinement approaches the joint solution. We will clarify how BOLT relates to existing random-feature BCD methods. We will also explain which parts use standard BCD and QR, and how BOLT combines them to address the fitting task and its accuracy-time-memory trade-offs.

Q2

We compared the methods on all five benchmark settings, using three paired random-feature seeds and three timing repetitions per seed. The methods share the feature bank, target encoding, and regularization. Representative RBF results (8 blocks of 256, ridge=0.1) are:

DatasetMethodAcc. (%)Fit (s)Peak (MiB)
CIFAR-100/R18Joint QR67.270.16151387.6
One sweep, alpha=163.330.1230465.7
20 forward sweeps, alpha=1, cached QR66.190.4331809.6
CIFAR-100/ViTJoint QR79.510.17721438.4
One sweep, alpha=176.950.1288516.5
20 forward sweeps, alpha=1, cached QR78.820.5288860.1

Relative to materialized joint QR, the one-pass solver reduces peak memory by 66.4% and 64.1%. The table also shows the accuracy loss and the extra refinement time.

Separately, we verified Figure 3(b)'s ReLU configuration: 6 blocks of 192, ridge=0.01, alpha=0.8, and alternating sweeps. Across ten pre-specified paired seeds on CIFAR-100/ViT, corrected refinement reduced the mean accuracy gap from 1.977 percentage points after one sweep to 0.011 after twenty sweeps. The mean absolute gap was 0.065 points, with 8/10 seeds within 0.1 points. The main implementation and a separate audit implementation produced the same test accuracy in 40 checks spanning two datasets, ten seeds, and one/twenty sweeps. These results show that refinement largely recovers the joint model's predictive accuracy. The normalized objective gap remains 0.00442, so we distinguish predictive agreement from numerical convergence.

We also added a row-streamed joint Cholesky control. Its FP32 variant reached 79.52% on CIFAR-100/ViT at 515.9 MiB, although its coefficients differed from the QR reference. We will report this control alongside materialized joint QR and discuss memory and numerical accuracy separately.

Q3

The main implementation recomputes QR during refinement. Appendix B.1 already notes reuse across right-hand sides; we have now implemented and evaluated factor caching.

For 20 undamped forward sweeps, caching reduced fitting time from 1.7946 to 0.4331 s on R18 (4.1x) and 1.8769 to 0.5288 s on ViT (3.5x). Peak memory increased from 465.7 to 809.6 MiB and from 516.5 to 860.1 MiB, respectively. Cached and recomputed runs had identical recorded objectives and accuracies. Preparation and factorization costs are included; diagnostic evaluation time is excluded.

All methods in each supplementary comparison were evaluated in the same software and hardware environment on RTX 3090 GPU, using identical cached features and matched experimental settings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.