acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Nonparametric Teaching via Geometry

Abstract

Nonparametric teaching studies how example selection can accelerate learning in reproducing kernel Hilbert spaces (RKHS). Existing formulations adopt a first-order perspective, selecting examples with large functional gradients while retaining the learner's native RKHS geometry. Through Mercer spectral analysis, we explain how this fixed geometry links the RKHS cost of prediction errors to the kernel-scaled response of first-order updates. To address the resulting spectral imbalance, we propose Geometry-Aware Teaching (GAT), a second-order framework that integrates curvature-aware batch selection with preconditioned functional updates. For realizable squared loss on finite pools, we justify its teaching score through a common lower bound on prediction-risk decrease and establish convergence guarantees for GAT and first-order teaching baselines. These guarantees distinguish first-order dependence on kernel conditioning from GAT's dependence on batch geometry. With exact batch selection and preconditioning, this spectral independence extends to GAT's prediction trajectory, which remains invariant to positive kernel-eigenvalue rescaling under a fixed teaching protocol. To identify the contribution of example selection, we further establish finite-horizon teaching optimality for a fixed preconditioned learner in a complete pool space. Empirical results confirm the practical benefits of GAT.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Nonparametric teaching, Functional Preconditioning, Geometry-Aware learning

Reviews

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

This paper proposes Geometry-Aware Teaching (GAT), which combines curvature-aware example selection with preconditioned updates in RKHS. The authors analyze the spectral limitations of existing first-order teaching methods and show that GAT can mitigate the dependence on kernel conditioning. They also provide convergence guarantees and establish finite-horizon optimality under specific assumptions. Experiments on function fitting and image reconstruction show faster convergence than first-order teaching baselines.

Critical strengths

S1. The theoretical analysis is generally well structured. The paper provides convergence guarantees with detailed proofs, and the overall theoretical development seems reasonable to me.

S2. The empirical results support the proposed method. The experiments show consistent improvements over the first-order baselines across several function fitting and reconstruction tasks.

Critical weaknesses

W1. The teaching-specific theoretical contribution is unclear.

Much of the analysis, including the spectral-bias argument and the benefits of preconditioning, seems closely related to standard kernel optimization theory. While the paper establishes convergence guarantees, I am not sure what new theoretical insight comes specifically from the teaching formulation rather than the use of a second-order learner. It would be helpful to clarify this distinction, particularly in relation to existing kernel/NTK-based analyses.

W2. The broader significance is unclear to me.

I found it difficult to see what broader insight this paper provides beyond the specific setting studied. Prior work has introduced the nonparametric teaching framework or connected it to practical neural learners. Here, the main analysis focuses on fixed-feature least squares, and the experiments are largely limited to function fitting and reconstruction. Beyond extending the framework to second-order updates, I would appreciate a clearer explanation of what new understanding of teaching or learning emerges from this work.

W3. The empirical contribution of the teaching strategy could be clearer.

The main experiments compare GAT with first-order baselines, making it difficult to separate the effects of selection and preconditioning. While Appendix F provides controlled comparisons and shows additional gains from GAT selection, these gains are relatively modest compared to those from preconditioning. I think the paper should place more emphasis on these controlled results to clarify the contribution of the teaching strategy itself.

Questions for authors

I would appreciate clarification on the points raised in the weaknesses above, particularly regarding the teaching-specific contribution and broader significance of the work.

2 comments
AuthorsOpenReview ↗

Response to the Review [1/2]

We thank the reviewer for finding the theoretical analysis well structured and the overall development reasonable, with detailed proofs supporting the convergence guarantees. We also appreciate the recognition of consistent empirical improvements over baselines across function-fitting and reconstruction tasks.

W1. The teaching-specific theoretical contribution is unclear.

The new teaching-specific insight is that update geometry determines how batch selection contributes to convergence and can make sequential example selection optimal over every finite teaching budget.

Classical NTK theory [1] characterizes how gradient descent changes network predictions. EigenPro [2] modifies kernel geometry to accelerate the learner’s updates. GAT studies how a teacher should select examples in that geometry and what the resulting adaptive decisions guarantee.

Lemmas 6–7 and Theorem 8 make this distinction explicit. Lemma 6 establishes a risk-decrease lower bound with a common coefficient across candidate batches. Exact GAT selection maximizes this guarantee. The refined convergence bound then retains the gain achieved by the actual selected batch:

&E_{t+1} \leq \left(1-\frac{\nu(2-\nu)\gamma_t}{R^2}\right)E_t,\\ &\gamma_t=\frac{q_t(\mathcal B_t^{\mathrm{GAT}})}{2E_t}\geq1, \end{aligned}$$ where, $E_t$ is the pool prediction risk, $R$ bounds the whitened batch covariance, and $\nu$ is the step-size multiplier. The teacher’s choice directly enters the contraction guarantee through $\gamma_t$. Corollary 9 establishes spectral-rescaling invariance of both the selected batches and the prediction trajectory under its fixed protocol. Proposition 10 gives a stronger teaching comparison: with the preconditioned learner and step size fixed in a complete pool space, GAT minimizes terminal risk over **all legal teaching sequences at every finite budget**. [1] Neural Tangent Kernel: Convergence and Generalization in Neural Networks. NeurIPS, 2018. [2] Diving into the Shallows: A Computational Perspective on Large-Scale Shallow Learning. NeurIPS, 2017. > W2. The broader significance is unclear to me. **The broader contribution is a principle for teaching: examples should be evaluated through the prediction corrections that the learner can obtain from them, so teaching and optimization should be designed together.** The spectral analysis identifies why selecting large functional gradients can leave important prediction errors weakly corrected. Example selection changes the batch covariance, but first-order updates still pass through the kernel scaling. GAT addresses both decisions together by evaluating batches in the geometry used for their updates. Lemma 6 connects this evaluation to a common prediction-risk decrease guarantee. Table 6 demonstrates the practical consequence: the relative ranking of Greedy and GAT selection reverses when the update geometry changes. Thus, improving the learner can also change which teaching rule is effective. The teacher and optimizer cannot be evaluated as independent sources of improvement. The analysis further explains when teaching requires joint batch decisions and when a simple sequential rule is sufficient. In general pools, the curvature-aware score contains interactions between examples, so independently ranking examples need not maximize the batch score. In a complete pool space, preconditioning makes their effects independent. Proposition 10 then proves that selecting the largest remaining residuals minimizes terminal risk over all legal teaching sequences at every finite budget. The same teacher is therefore optimal without advance knowledge of the stopping budget. These results provide concrete guidance for teaching design. The selection criterion should reflect the learner’s prediction response, and batch construction should account for interactions between examples. When the geometry removes those interactions, the analysis identifies a simple rule with an exact budget-allocation guarantee. For neural networks, future work can extend this principle by adapting the teaching criterion to the optimizer and the evolving prediction response during training.
AuthorsOpenReview ↗

Response to the Review [2/2]

W3. The empirical contribution of the teaching strategy could be clearer. “these gains are relatively modest compared to those from preconditioning.”

The fixed-learner improvements are substantial and consistent, while separate controlled experiments test the theory’s predictions.

In Table 8, all selectors share the preconditioner, batch size, and step-size multiplier. At 192 presentations per photograph, GAT reduces chroma MSE relative to Greedy by 17.1% per photograph on average and improves all 200 photographs. At 384 presentations, the mean initial-error-normalized MSE decreases from 0.1058 with Greedy to 0.0633 with GAT, a 40.2% reduction. These gains come from changing the teaching strategy while keeping the learner fixed.

We additionally compare GAT, Greedy, and Random using the same preconditioned learner within each task to isolate the contribution of example selection.

On the original curve task from Figures 1–2, the pool contains 100 points and the learner uses 20 sine modes. All methods share the preconditioner, a batch size of 10, and a step-size multiplier of 1. The table reports the number of example presentations needed to reach each target reduction in initial MSE. Random results average ten runs. (Tables 10 in the revised manuscript)

Target MSE reductionGAT presentationsGreedy presentationsRandom presentations
90%5060127
95%7080166
99%110120249

GAT reaches each target with 8.3–16.7% fewer presentations than Greedy and 55.8–60.6% fewer than Random.

We also reconstruct the original 64 × 64 Cheetah image. All methods share the preconditioner, a batch size of 50, and a step-size multiplier of 1. Random PSNR averages three runs. (Tables 11 in the revised manuscript)

Pixel presentationsGAT PSNR (dB)Greedy PSNR (dB)Random PSNR (dB)
4,10017.1413.089.95
8,20020.5918.1017.10

GAT improves PSNR over Greedy by 4.06 dB and 2.49 dB at the two budgets, corresponding to approximately 60.7% and 43.6% lower MSE. These substantial improvements arise from changing the teaching strategy while keeping the learner fixed.

The mechanism experiments explain why the selection rule matters. Figure 7 crosses selection rules with first-order and preconditioned updates and shows that their relative ordering reverses when the update geometry changes. Appendix F.2 tests Corollary 9 across kernel condition numbers from 1 to 1,000. The selected batches remain identical and predictions agree to numerical precision. These results corroborate the predicted relationship between teaching and update geometry. Together with the fixed-learner gains, they support both GAT’s joint design and the effectiveness of its teaching decisions.

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

This paper extends nonparametric teaching, where a teacher selects examples to speed up functional gradient descent in an RKHS, from first-order to second-order. A Mercer analysis shows the fixed RKHS geometry causes two spectral effects. Small-eigenvalue components are up-weighted in the RKHS error , and first-order updates damp them by a factor λk\lambda_k. Geometry-Aware Teaching (GAT) selects the size-BB batch maximizing qt(B)=⟨∇FB,Ht−1∇FB⟩q_t(\mathcal B)=\langle \nabla F_{\mathcal B}, H_t^{-1}\nabla F_{\mathcal B}\rangle under the full-pool Hessian, the learner then takes a preconditioned step. Theory proved linear-rate bounds for GAT, invariance of GAT's trajectory to rescaling the kernel eigenvalues, and finite-horizon optimality of GAT's selection for a fixed preconditioned learner when the pool spans the space. Then showed GAT converges faster than Greedy and Random, e.g. 24.3 dB vs 16.4 / 14.9 dB PSNR on cheetah at t=300t=300.

Critical strengths

The Mercer analysis makes precise why first-order teaching is slow on small-eigenvalue components: 1/λk1/\lambda_k weighting in RKHS error and λk\lambda_k damping in the update. The theory is sound, showing risk-decrease lower bounds, explicit dependence on κ\kappa versus batch concentration RR, and exact invariance under eigenvalue rescaling.

Critical weaknesses
  1. Most of the reported gain comes from preconditioning, not teaching. Figures 1–3 and the headline numbers compare GAT against Greedy and Random with first-order learners, so they measure Newton-type preconditioning by the full-pool Hessian, a classical way to remove kernel ill-conditioning, more than better example selection. The paper's own controls show the selection effect is conditional, GAT's selection is worse than Greedy at every C>1C>1: A8A_8 = 0.471 vs 0.452, 0.642 vs 0.578, 0.749 vs 0.649 (Table 6).
  2. Novelty and positioning. Removing the kernel-eigenvalue factor by preconditioning, and the resulting affine invariance (Cor 9), are standard properties of Newton-type methods. The setting assumes a teacher that knows the target pool values and a learner with the exact full-pool Hessian. With that, the full-pool preconditioned learner already solves the realizable problem in very few steps.
Questions for authors
  1. Can you report the main experiments (Figs 1–3, the PSNR numbers) against Greedy and Random with the same preconditioned learner as the primary comparison?
  2. Besides Prop 10 (d=nd=n), is there any regime where GAT's selection provably beats Random selection under the same preconditioner?
  3. How does GAT compare with established preconditioned kernel solvers (EigenPro, FALKON, conjugate gradient) at matched compute? Why is example selection preferable to simply preconditioning?
  4. What is the intended practical setting?
2 comments
AuthorsOpenReview ↗

Response to the Review [1/2]

We thank the reviewer for recognizing that the Mercer analysis explains both the inverse-eigenvalue weighting of RKHS error and the weak first-order correction of small-eigenvalue components. We appreciate the assessment of the theory as sound, including the risk-decrease bounds, the explicit dependence on kernel conditioning versus batch concentration, and exact invariance under eigenvalue rescaling.

W1 / Q1. “Most of the reported gain comes from preconditioning, not teaching.” “...against Greedy and Random with the same preconditioned learner as the primary comparison?”

We would like to clarify that Figures 1–3 evaluate the complete GAT framework. The following additional comparisons isolate selection while keeping the preconditioned learner fixed.

On the original 100-point curve with 20 sine modes, all selectors share the preconditioner, batch size B=10B=10, and step-size multiplier ν=1\nu=1. Random averages ten runs. (shown in the Table 10 in the revised manuscript)

Target reduction in initial MSEGAT presentationsGreedy presentationsRandom presentations
90%5060127
95%7080166
99%110120249

GAT saves 8.3–16.7% of Greedy’s presentations and 55.8–60.6% of Random’s presentations across these targets.

We also evaluate cheetah image teaching corresonding to Figure 3. All selectors share the preconditioner, B=50B=50, and ν=1\nu=1. Random averages three runs. (shown in the Table 11 in the revised manuscript))

Pixel presentationsGAT PSNR (dB)Greedy PSNR (dB)Random PSNR (dB)
4,10017.1413.089.95
8,20020.5918.1017.10

At 4,100 presentations, GAT exceeds Greedy by 4.06 dB and Random by 7.19 dB. These controls establish a clear contribution from selection under the same learner.

Table 6 explicitly highlights why selection and updates should be designed together. The cited values use first-order updates. At C=64C=64, GAT selection and Greedy yield first-pass mean normalized errors of 0.7493 and 0.6489. With the common preconditioned learner, their ordering reverses to 0.3015 and 0.3983. This reversal supports the central design of GAT: evaluate examples in the geometry governing their learning effects. The fixed-learner controls explain selection, while the original figures evaluate the joint framework.

W2. “Removing the kernel-eigenvalue factor by preconditioning, and the resulting affine invariance (Cor 9), are standard properties of Newton-type methods.” "...solves the realizable problem"

Corollary 9 concerns the adaptive teaching process, including which batches are selected, rather than only cancellation of a spectral factor in an update. Equation (17) expresses both the score and update through the teacher-controlled batch covariance. Under the fixed protocol, positive eigenvalue rescaling therefore preserves every candidate score, the selected batches, and the complete prediction trajectory. A preconditioned update alone does not determine the teacher’s choices.

Nonparametric teaching asks how example presentations guide a learner toward a specified target function [1]. Knowing the target enables the teacher to choose examples, while the learner follows its specified update rule. Returning a full-pool solution changes that protocol instead of determining how best to teach within it. This perspective already supports neural training through target mappings in INRs [2], graph property learners [3], and attention learners [4]. GAT develops the joint treatment of presentation and update geometry within this framework.

[1] Nonparametric Iterative Machine Teaching. ICML, 2023.

[2] Nonparametric Teaching of Implicit Neural Representations. ICML, 2024.

[3] Nonparametric Teaching for Graph Property Learners. ICML, 2025.

[4] Nonparametric Teaching for Attention Learners. ICLR, 2026.

AuthorsOpenReview ↗

Response to the Review [2/2]

Q2. Besides Prop 10 (d=n), is there any regime where GAT's selection provably beats Random selection?

Yes. The selection gain in Eq. (22) yields a finite-budget guarantee for general batch sizes, and the original curve experiment satisfies it with d<nd<n.

Under Assumption 5, fix the same initialization, batch size, preconditioner H−1H^{-1}, and step size ηA=ν/R\eta_A=\nu/R, with 0<ν≤10<\nu\leq1. Evaluate the gain along GAT’s own trajectory using the batches actually selected:

γt=qt(BtGAT)2EtGAT.\gamma_t=\frac{q_t(\mathcal B_t^{\mathrm{GAT}})}{2E_t^{\mathrm{GAT}}}.

For any budget T≥1T\geq1 with positive pre-update risks, GAT achieves strictly lower risk than Random in expectation whenever

γˉT=1T∑t=0T−1γt>2R−ν2−ν.\bar\gamma_T = \frac{1}{T}\sum_{t=0}^{T-1}\gamma_t > \frac{2R-\nu}{2-\nu}.

Random draws a fresh uniform size-BB subset at each update, giving E[QBt∣Ft]=I\mathbb E[Q_{\mathcal B_t}\mid\mathcal F_t]=I. Its mean whitened error therefore satisfies E[aT]=(1−ηA)Ta0\mathbb E[a_T]=(1-\eta_A)^T a_0. Since risk is half the squared norm of the whitened error, Jensen’s inequality gives

\geq (1-\eta_A)^{2T}E_0.$$ For GAT, Eq. (21) bounds each risk factor by $1-\nu(2-\nu)\gamma_t/R^2$. These factors are nonnegative because $\gamma_t\leq R^2$. Multiplying them and applying the arithmetic–geometric mean inequality yields $$E_T^{\mathrm{GAT}} \leq \prod_{t=0}^{T-1} \left(1-\frac{\nu(2-\nu)}{R^2}\gamma_t\right)E_0 \leq \left(1-\frac{\nu(2-\nu)}{R^2}\bar\gamma_T\right)^T E_0.$$ The stated threshold makes this upper bound strictly smaller than Random’s lower bound. Because Eq. (21) holds for every candidate batch, the comparison also applies to approximate search using its achieved scores. The original curve task provides such a case with $d=20$, $n=100$, and $B=10$. Its settings give $R=10$, $\nu=0.1$, and $\eta_A=0.01$, so the threshold is approximately 10.47. Using the batches selected by the approximate search in Appendix C.2, we obtain $\bar\gamma_{50}=13.38$ and $\bar\gamma_{500}=10.96$. The condition holds at all six budgets reported in Table 3. For example, after 50 updates, GAT’s MSE is 0.16757. From the same initial MSE of 0.78350, Random under the same preconditioner and step size has expected MSE at least $$0.78350(0.99)^{100}\approx0.2868.$$ Thus, the comparison establishes a strict teaching advantage on the original finite-rank minibatch task with the learner held fixed. > Q3. “How does GAT compare with established preconditioned kernel solvers (EigenPro, FALKON, conjugate gradient)?” Nonparametric teaching asks how a teacher can guide a learner toward a specified target function through example presentations [1]. GAT addresses this question by jointly designing batch evaluation and learner updates. CG, FALKON, and EigenPro focus on accelerating numerical optimization. Benchmarking these methods as standalone solvers therefore addresses a different research question and falls outside the scope of this teaching study. To address the practical concern, we additionally examine our teaching principle with an EigenPro learner. Its minibatch updates allow us to compare teaching strategies while keeping the learner fixed. We adapt GAT’s batch evaluation to EigenPro’s spectral preconditioner and compare GAT–EigenPro with Greedy–EigenPro under the same learner configuration and teaching budget. We evaluate color teaching on 90 held-out BSDS500 images containing 49,686 pixels each. Every update presents four pixels from a shared 64-pixel candidate pool. GAT scores batches using EigenPro’s preconditioner, while Greedy ranks pixels by RKHS gradient norm. At 256 presentations per image (Table 9 in the revised manuscript): | EigenPro batch selection | Chroma MSE in squared CIELAB units | |---|---:| | Random | 31.26 | | Greedy | 30.44 | | GAT | **28.80** | GAT reduces mean MSE by approximately 5.4% relative to Greedy and 7.9% relative to EigenPro’s random sampling. This supplementary comparison examines whether matching teaching to learner geometry provides benefits over Greedy within an established method for accelerating kernel learning. > Q4. “What is the intended practical setting?” The paper provides *a function-space foundation for jointly designing training-example presentation and learner updates*. Its practical setting is iterative approximation of a target mapping. The teacher controls which examples are presented, while the optimizer determines how those examples change predictions. The theory connects these decisions to risk reduction and finite-budget teaching guarantees. The reconstruction and real-image tasks instantiate this setting directly. The additional CIFAR-100 (Appendix G.3, Table 14).and EigenPro experiments extend the evaluation to neural features and an established kernel learner. Future work can incorporate evolving neural-network update geometry into teachers for INR, graph, and attention learners, building on the existing applications of nonparametric teaching [2–4].
Reviewer_L8KMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces geometry-aware teaching (GAT), which extends nonparametric machine teaching from first-order gradients to second-order information. The central idea is conventional teaching suffers from kernel-induced spectral imbalance, where small-eigenvalue directions learn slowly. GAT jointly uses Hessian-aware example selection and preconditioned functional updates to mitigate this issue. Experiments show effectiveness of the method.

Critical strengths
  • The connection between RKHS geometry, kernel spectral imbalance, and teaching efficiency is intuitive and clearly explained.

  • The paper establishes convergence bounds, spectral-rescaling invariance, and finite-horizon optimality under specified conditions.

  • Experimental results are good. GAT consistently improves early-stage teaching efficiency compared to a few baselines.

Critical weaknesses
  • The novelty is actually limited. On one hand, the central idea largely combines classical Hessian preconditioning with adaptive batch selection. The novelty beyond established second-order optimization could be better articulated. On the other hand, I think generalizing iterative machine teaching to second-order update is an incremental idea, given that second-order update is a natural improvement over first-order gradient update. The experimental benefits is hence quite expected.

  • Similar to previous machine teaching analysis, the assumptions can be quite strong and not applicable to practical scenarios.

  • The scalability of the teaching algorithm to practical scenarios is quite limited. Current experiments only focus on relatively small kernel-based reconstruction problems.

Questions for authors
  • Please justify why second-order information is important for machine teaching. While I know it can definitely improve teaching efficiency, it also introduces significant amount of computational overhead. I find this modification unnecessary and also doesn't match our practice, where we usually only use gradient-based learning for neural networks.

  • How to address the inherent scalability issue? While I appreciate the usefulness of teaching algorithms in general, the fact that the second-order teaching is even harder to scale is a huge problem. If it cannot be addressed, I don't think it is of any practical values.

2 comments
AuthorsOpenReview ↗

Response to the Review [1/2]

We thank the reviewer for finding the connection between RKHS geometry, spectral imbalance, and teaching efficiency intuitive and clearly explained. We appreciate the recognition of our convergence bounds, spectral-rescaling invariance, and finite-horizon optimality under the stated conditions, as well as the consistent improvements in teaching efficiency.

W1. “the central idea largely combines classical Hessian preconditioning with adaptive batch selection.”

GAT shows how changing the learner’s geometry changes what should be taught, and proves when the resulting teaching policy is optimal. Our spectral analysis separates kernel scaling from the batch covariance controlled by the teacher. GAT then uses the same curvature operator to evaluate batches and apply their updates. This connects example selection to the function changes it produces.

Lemma 6 justifies the score through a common lower bound on prediction-risk decrease. Lemma 7 and Theorem 8 show how the selected batch enters convergence. At positive-error states along the exact-selection GAT trajectory,

&E_{t+1} \leq \left(1-\frac{\nu(2-\nu)\gamma_t}{R^2}\right)E_t,\\ &\gamma_t=\frac{q_t(\mathcal B_t^{\mathrm{GAT}})}{2E_t}\geq1. \end{aligned}$$ The selected score therefore directly controls the contraction guarantee. Corollary 9 further establishes invariance of the scores, selected batches, and prediction trajectory under spectral rescaling within the stated setting. Proposition 10 proves optimality over all legal teaching sequences at every finite budget in a complete pool space. These results establish consequences for **teaching decisions and their allocation over time**, beyond the convergence properties of a preconditioner. Table 6 experimentally reveals the insight on **the interaction between teaching and learning.** It crosses selection rules with both update types on the same target problems. At feature contrast $C=64$, the first-pass mean normalized MSE is: | Selection rule | First-order update | Preconditioned update | |---|---:|---:| | Greedy | **0.6489** | 0.3983 | | GAT selection | 0.7493 | **0.3015** | The relative ranking of the teachers reverses when the update geometry changes. The same reversal occurs at $C=4$ and $C=16$, as summarized in Figure 7(b). Thus, the effect of teaching depends on how the learner uses the selected examples. GAT analyzes and exploits this interaction through a coordinated design of batch evaluation and functional updates. > W2. “the assumptions can be quite strong and not applicable to practical scenarios.” The assumptions make **the teaching comparison identifiable and analytically precise**. The realizability and positive-curvature conditions follow established settings in teaching and least-squares convergence analysis, while the batch covariance bound is automatic. Nonparametric iterative teaching assumes that the initial and target functions belong to the same RKHS [1]. Interpolation is also central to the least-squares convergence analysis [2]. Positive-definite covariance is typically assumed [3]. In our finite working space, this condition means that the pool identifies every direction. The footnote following Assumption 5 shows $$H_{\mathcal B}\preceq\frac{n}{B}H,$$ so every finite pool admits the bound $R=n/B$. Positive definiteness means that the pool identifies the chosen working space. Realizable squared loss permits exact risk analysis, whereas the additional condition $d=n$ is needed specifically for the stronger finite-horizon optimality result. The method is also evaluated beyond realizability. Appendices F.3–F.4 use low-rank learners on contour and color teaching tasks across 200 BSDS500 photographs. With a common preconditioner, GAT reduces per-image MSE relative to Greedy by 11.8% and 17.1%, respectively. Thus, **the practical evaluation extends beyond the setting used to obtain exact theoretical guarantees**. [1] Nonparametric Iterative Machine Teaching. ICML, 2023. [2] The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning. ICML, 2018. [3] Accelerating Stochastic Gradient Descent for Least Squares Regression. COLT, 2018.
AuthorsOpenReview ↗

Response to the Review [2/2]

W3 / Q2. “Current experiments only focus on relatively small kernel-based reconstruction problems.” “How to address the inherent scalability issue?”

We would like to clarify that Appendix F also evaluates contour and color teaching on 200 real photographs, alongside controlled tests of selection–update interaction and spectral invariance. These experiments examine both practical teaching gains and the mechanisms predicted by the analysis.

The implementation reuses the fixed pool Hessian and avoids exhaustive batch enumeration in the main experiments, which shows the practicability of GAT. Appendix C.2 specifies exact selection by sorting for complete pool spaces and approximate joint batch search for low-rank tasks. Table 9 (Table 12 in the revised manuscript) tests the search against exhaustive selection on reduced 24-point contour pools, attaining 99.86% of the optimal score on average. Table 10 (Table 13 in the revised manuscript) reports computation including curvature construction, selection, and learner updates.

Further, we additionally evaluate CIFAR-100 classification on a 50,000-image training pool. A least-squares classifier uses frozen DINOv2-B/14 features projected to 512 dimensions, with the eight leading principal coordinates scaled fourfold. Each teacher selects 32 examples from the same 96 candidates at each update. The results below average the five paired seeds, at 24,992 example presentations. (i.e., Table 14 in the revised manuscript)

TeacherLearnerTest (%)Head training (s)Total including feature extraction (s)
GreedyFirst-order86.871.11556.840
RandomPreconditioned87.041.02456.749
GreedyPreconditioned88.151.10656.831
GATPreconditioned88.491.24556.970

With the empirical-Hessian preconditioner held fixed, GAT improves accuracy over Greedy by 0.34 percentage points.

Q1. “Please justify why second-order information is important for machine teaching”

Second-order information matters because effective teaching must account for how the learner converts examples into prediction corrections. GAT aligns its selection criterion with those learning effects.

Table 6 demonstrates why this coordination matters. At C=64C=64, GAT reduces error from 0.3983 to 0.3015 relative to Greedy under the same preconditioned learner, a 24.3% reduction. The relative ranking reverses under first-order updates. Adapting the teacher to the update geometry therefore yields gains beyond preconditioning alone.

Figures 4 and 6 illustrate how GAT allocates presentations accordingly. In Figure 4, its later batches select pixels across the face and surrounding fur, whereas Greedy concentrates more heavily around the eye and muzzle contours. In Figure 6, GAT shifts from bright background regions toward the lower image and later foreground locations. Random distributes presentations without accounting for the remaining prediction errors.

The rationale for these allocations follows from the update dynamics. In these tasks, each GAT presentation removes 75% of the selected pixel’s squared error and leaves other pixels unchanged. Its curvature-aware score therefore selects exactly the batch producing the largest immediate risk reduction. As these errors shrink, the teacher redirects presentations toward larger remaining errors.

For neural-network training, the implication is to develop teachers together with the optimizer. Rescaling parameter-update directions can change which examples most effectively correct the network’s predictions. Our RKHS analysis establishes this dependence explicitly and motivates evaluating examples through their learning effects, instead of carrying an unchanged selection criterion across different update rules.

Comments on the paper

4 comments
AuthorsOpenReview ↗

Rebuttal Revision Comment

We thank all reviewers again for their constructive feedback. We have updated the manuscript to incorporate the following additional experiments from the rebuttal:

  • We added comparisons of GAT, Greedy, and Random under the same preconditioned learner on the original curve task and Cheetah reconstruction (Appendix F.6, Tables 10–11).
  • We evaluated the teaching strategies with a fixed EigenPro learner on grayscale-to-color teaching (Appendix F.5, Table 9).
  • We added CIFAR-100 classification experiments on a 50,000-image training pool (Appendix G.3, Table 14).

We welcome further questions and discussion.

AuthorsOpenReview ↗

Thank You for the Positive Feedback on W2 and W3

Thank you for the follow-up and for recognizing the common-learner evidence and the co-design principle.

“what the teaching formulation adds beyond preconditioning”

GAT gives the co-design principle a concrete theoretical and algorithmic form in nonparametric teaching. Building on the first-order NT formulation [1], it studies how learning geometry shapes the entire teaching process. Curvature influences both which batches the teacher selects and how those batches change the learner. Each update changes the learner’s state, which in turn changes subsequent teaching decisions.

Knowing that an update is well conditioned does not determine what this adaptive teaching sequence will achieve. GAT addresses this additional problem by connecting the teacher’s decisions to the learner’s functional response. Its analysis distinguishes the limitations imposed by kernel geometry from the contribution of selected examples, and its method uses this understanding to construct the teaching criterion and learner update together. The contribution therefore lies in explaining and designing the resulting teaching process, beyond the properties of the preconditioner itself.

GAT provides a principled way to translate advances in the learner into more effective teaching. Our controlled experiments show that changing the update geometry can reverse which teaching strategy is more effective (Table 6 in the revised manuscript). This is a qualitative consequence: a teaching strategy that is preferable for one learner can become inferior when the learner’s geometry changes. GAT makes this dependence part of the formulation, analysis, and algorithm, providing a systematic way to adapt teaching to how the learner actually responds.

The fixed-EigenPro experiment demonstrates the practical consequence. With an established learner’s preconditioner and step size already fixed, GAT achieves better learning at the same presentation budget (Table 9). The framework therefore has value beyond the particular teacher–learner pair developed in our analysis: it also provides a way to obtain additional learning efficiency from an existing preconditioned learner.

We believe this combination constitutes a substantive contribution: a geometric formulation that advances our understanding of nonparametric teaching, an algorithm that makes this understanding actionable, and controlled evidence that it improves learning beyond the gains from preconditioning alone. We will make this more explicit in the main text and would appreciate your reconsideration of W1 and your overall assessment in this light.

[1] Nonparametric Iterative Machine Teaching. ICML, 2023.

AuthorsOpenReview ↗

Follow-up Before the Discussion Deadline

We thank the reviewers for their time and constructive feedback. As the discussion period approaches its deadline (November 18, 11:59 pm AoE), we would appreciate any further comments on our responses and the additional theoretical and experimental results. We hope these clarifications address the remaining concerns and would welcome the opportunity to discuss any outstanding questions before the discussion closes.

Thank you for the follow-up and the continued discussion.

GAT beats random condition cannot be identified in advance

Our Q2 result provides a sufficient condition for GAT to achieve strictly lower risk than Random’s expected risk under the same preconditioner, initialization, and step size. It covers general batch sizes beyond the complete-pool setting.

The condition has an analytically specified threshold and can be verified from GAT’s selection scores and risks along its own trajectory, without observing Random’s outcomes. On the original low-rank curve, the average selection gain at 50 updates is 13.38, exceeding the threshold of 10.47. This establishes a provable selection advantage over Random under the same learner in an original minibatch task beyond the complete-pool setting.

still no comparison against preconditioned kernel solvers at matched compute

CG (conjugate gradient) and FALKON address the numerical solution of a kernel optimization problem. Our teaching problem asks how examples should be selected to guide a learner toward the target function under its specified update rule. We therefore use EigenPro as the learner and compare teaching strategies while keeping its preconditioner and update rule fixed.

At 256 presentations per image across 90 images, mean chroma MSE decreases from 31.26 with Random and 30.44 with Greedy to 28.80 with GAT (Table 9 in the revised manuscript). This comparison isolates what teaching decisions contribute within an established preconditioned learner. The reported advantage concerns learning progress at a matched presentation budget.

practical setting is vague

The teacher operates as the batch-selection component of an iterative training process, using available target values and current learner predictions. Our experiments instantiate this setting directly.

In EigenPro color teaching, the learner predicts chroma from pixel coordinates and lightness, while the teacher selects the pixels used for each update. In CIFAR-100, the teacher selects labeled examples for training a classifier on frozen visual features (Appendices F.5 and G.3 in the revised manuscript). In both cases, the practical decision is how to allocate training examples in accordance with the learner’s update geometry.

the selection gain is not substantial in cifar-100

CIFAR-100 evaluates whether GAT’s joint design extends to classification on frozen neural features with a 50,000-image training pool. At each update, all teachers select 32 examples from the same 96 candidates, allowing the framework to operate through bounded batch search.

At 24,992 example presentations, GAT achieves a mean accuracy of 88.49% across the five prespecified paired seeds, compared with 86.87% for Greedy with first-order updates. With the preconditioned learner held fixed, Greedy and Random achieve 88.15% and 87.04%, respectively (Table 14 in the revised manuscript).

the invariance argument still looks like a standard Newton property

Classical Newton invariance provides the foundation for the preconditioned update. The teaching-specific issue is how this property is preserved through adaptive example selection. Greedy weights squared residuals by the kernel diagonal, so kernel eigenvalue rescaling can change its selected examples even with exact preconditioning. Corollary 9 establishes that GAT preserves its candidate scores, adaptive batch sequence, and prediction trajectory under the stated setting.

The importance of designing selection and updates together is also demonstrated by Table 6. At contrast 64, GAT selection has higher first-pass error than Greedy with first-order updates (0.7493 versus 0.6489), but lower error with preconditioned updates (0.3015 versus 0.3983). The preferred selection rule therefore changes with the learner’s update geometry.

Our theoretical contribution connects this joint design to risk descent through Lemma 6–Theorem 8. Proposition 10 further establishes finite-budget teaching optimality for a fixed preconditioned learner in the complete-pool regime. These results address how teaching decisions and learner updates jointly determine learning progress.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.