acceptodds
Under review as a conference paper at ICLR 2027

Escaping the Variance Trap: Jacobian-Free Dynamics for Root-Finding Bilevel Optimization

Abstract

Many central machine learning tasks, from entropy tuning in reinforcement learning to equilibrating generative adversarial networks, are fundamentally stochastic root-finding problems rather than loss minimization. Yet, they are frequently forced into a minimization framework via squared residuals, introducing a critical flaw we identify as the Variance Trap. Standard bilevel minimization algorithms require estimating hypergradients involving implicit Jacobians; in stochastic settings, these terms act as noise amplifiers, destabilizing convergence. We formalize Root-Finding Bilevel Optimization (RF-BO) as a distinct problem class that bypasses this pathology. We propose a Jacobian-free solution using Two-Time-Scale Stochastic Approximation (TTSA) that updates directly along the root error, structurally avoiding variance amplification. We provide the first non-asymptotic convergence guarantees for TTSA in this setting under Markovian noise. Extensive experiments demonstrate the decisive advantage of this paradigm: compared to squared-residual and implicit-gradient baselines, our framework achieves a 2.6% top-1 accuracy gain in SimCLR, 17 faster convergence in non-linear ODE control where baselines fail, significantly improved entropy stability in reinforcement learning, and an 11.1% quality improvement in generative modeling.

Primary area:
optimization
Keywords:
Machine Learning, Bilevel Optimization, Stochastic 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_tREdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors single out a class of bilevel problems in which the upper level has to drive a residual h(α,θ∗(α))h(\alpha,\theta^*(\alpha)) to zero. Examples include temperature tuning in SAC, the penalty weight in WGAN-GP, the KL penalty in RLHF, and the SimCLR temperature. They propose solving such problems with two-timescale stochastic approximation (TTSA) applied directly to hh, without hypergradients. The paper gives convergence rates under strong convexity and the PL condition, together with a variance comparison against minimizing 12∥h∥2\frac12\|h\|^2. Experiments cover synthetic tasks, control of a stochastic ODE, SAC (Pendulum, HalfCheetah), a multi-agent game, WGAN-GP and SimCLR.

Critical strengths
    1. The unifying observation is helpful. Many procedures that tune a hyperparameter to hit a target statistic are essentially root-finding problems, and reframing them as minimization of 12∥h∥2\tfrac12\|h\|^2 with implicit differentiation is often unnecessary.
    1. The method is straightforward to implement, adds almost no computational overhead, and applies to a broad range of problems.
Critical weaknesses
    1. In my view the theory needs both revision and more careful positioning. The algorithm is the classical TTSA scheme [1], and SAC's automatic temperature adjustment [2] already works this way, which the authors acknowledge. The main text states the results for Markovian noise and calls them the first non-asymptotic analysis in that setting. The proofs, however, rely on conditionally unbiased estimates (Assumption B.5), i.e. martingale-difference noise, and the Markovian case is not treated separately. Non-asymptotic bounds for nonlinear TTSA are already available [3], including under Markovian noise [4,5]. The proof of Theorem 5.5 arrives at two different rates: O(T−r)O(T^{-r}) with r=min⁡(a,2(1−a))r=\min( a,2(1-a) ) in Eq. (19), and then O(T−a)O(T^{-a}); the two disagree for a>2/3a>2/3. Assumption B.6 (strong monotonicity ⟨α−α∗,h(α,θ∗(α))⟩≥ρ∥α−α∗∥2\langle \alpha-\alpha^{\ast}, h(\alpha,\theta^{\ast}(\alpha))\rangle \ge \rho \lVert\alpha-\alpha^{\ast}\rVert^{2} is considerably stronger than Assumption 5.3 as stated in the main text, and it effectively contains the main difficulty for vector-valued α\alpha. Proposition 5.4 compares upper bounds on the variances of two updates that live on different scales, so on its own it does not establish the variance trap.
    1. The experiments do not yet fully support the conclusions. On HalfCheetah, RF-BO ends with a return of 45.5 on one of the five seeds, although the text states that it avoids divergence on all seeds; moreover, returns for all methods (at most about 1200) are several times lower than what SAC typically reaches at 200k steps [2]. On Pendulum, RF-BO's success rate is lower than that of standard SAC (52% vs. 68%), and the final returns agree within the reported spread. SimCLR is trained for 50 epochs on 3 seeds, and the best epoch for every method is close to the last one, so training has not converged; WGAN-GP is evaluated on a one-dimensional mixture of two Gaussians. The paper does include dual-type baselines (standard SAC, and Dual Adam for WGAN-GP), and they update the parameter using the same quantity hh, but with a different optimizer and step-size schedule. It is therefore unclear whether the gains come from the root-finding formulation or from the step-size choice. An ablation that separates the two, and a comparison with PID Lagrangian methods [6], are missing. The motivating RLHF KL-penalty example [7] is not tested experimentally.

References:

    1. V.R.Konda, J.N.Tsitsiklis. Actor-Critic Algorithms. // Advances in Neural Information Processing Systems (NIPS), 1999.
    1. T.Haarnoja, A.Zhou, K.Hartikainen, G.Tucker, S.Ha, J.Tan, V.Kumar, H.Zhu, A.Gupta, P.Abbeel, S.Levine. Soft Actor-Critic Algorithms and Applications. // arXiv:1812.05905, 2018.
    1. T.T.Doan. Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance. // IEEE Transactions on Automatic Control, 68(8):4695--4705, 2023.
    1. T.T.Doan. Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise. // arXiv:2104.01627, 2021.
    1. M.Kaledin, E.Moulines, A.Naumov, V.Tadic, H.-T.Wai. Finite Time Analysis of Linear Two-Timescale Stochastic Approximation with Markovian Noise. // Conference on Learning Theory (COLT), 2020.
    1. A.Stooke, J.Achiam, P.Abbeel. Responsive Safety in Reinforcement Learning by PID Lagrangian Methods. // International Conference on Machine Learning (ICML), 2020.
    1. L.Ouyang et al. Training Language Models to Follow Instructions with Human Feedback. // Advances in Neural Information Processing Systems (NeurIPS), 2022.
Questions for authors
    1. How do the proofs account for Markovian noise, given that Assumption B.5 requires conditionally unbiased estimates? Which of the two rates in the proof of Theorem 5.5 is correct, and what is new in the analysis compared with [3,4,5]?
    1. Which conditions on hh guarantee Assumption B.6 when α\alpha is a vector?
    1. Is the clipping operator TtT_t from Algorithm 1 used in the experiments, and is the same clipping applied to the baselines? Could you compare RF-BO with standard SAC and Dual Adam under the same optimizer and step-size schedule, and with PID Lagrangian methods [6]?
    1. How exactly is the residual hh defined for SimCLR (Table 12 only lists a similarity target of 0.6), and why is this the right target for the temperature τ\tau? What explains the 3.3-point gap over Fixed-Temp when the alignment and uniformity values are nearly identical?
    1. How does this work relate to the concurrent submission Authors (2026) on quantile-guided Huber updates in TTSA, given that Section 3.3 describes normalizing updates by dynamic quantiles?
Reviewer_zfiKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies nested learning tasks in which an upper-level parameter calibrates a statistic of a lower-level trained model. It formulates these tasks as root-finding bilevel optimization (RF-BO) and applies classical two-timescale stochastic approximation (TTSA), combining fast model updates with slow residual-based parameter updates. The paper identifies Jacobian estimation as a potential source of additional noise in squared-residual optimization, presents convergence analyses, and evaluates the approach on synthetic problems, reinforcement learning, contrastive learning, and an illustrative generative-modeling task.

Critical strengths
  1. The paper offers a useful perspective on adaptive calibration. Recognizing that some upper-level tasks seek a target statistic can motivate simpler alternatives to squared-residual optimization. I view the potential contribution as problem reformulation and variance diagnosis, with TTSA serving as an established tool. Bringing these applications together could be valuable even without proposing a new TTSA algorithm.

  2. The approach is simple and shows encouraging empirical results. Direct residual updates avoid explicit differentiation through the lower-level solution. On CIFAR-10, SimCLR achieves a mean best-checkpoint accuracy of 74.72% versus 72.26% for the strongest evaluated baseline, over three seeds. The reduction in entropy deviation on Pendulum, from 0.223 to 0.174, also supports improved calibration in that setting.

Critical weaknesses
  1. The contribution boundary and practical implications are not sufficiently clear. Classical TTSA already addresses coupled root-finding, including nonlinear settings with Markovian noise (Doan, 2021). The paper should explain what new understanding follows from the RF-BO formulation beyond this framework and existing calibration practices. The variance diagnosis motivates avoiding noisy Jacobian estimates, but a useful framework should also clarify when direct residual updates are appropriate and what limits their stability. Synthetic examples with deliberately large injected Jacobian noise illustrate a possible failure mode; additional discussion is needed to connect this setting to the practical applications.

  2. The experiments do not adequately distinguish the proposed mechanism from optimization choices. Standard SAC already updates temperature using an entropy-residual dual gradient without differentiating through the trained policy (Haarnoja et al., Eq. (18)). Thus, the improvement over Original-SAC cannot directly demonstrate the benefit of removing Jacobian estimation. A matched comparison controlling learning-rate schedules, temperature parameterization, and optimizer choices would help identify the contribution of timescale separation. For SimCLR, the paper should specify the residual corresponding to the similarity target of 0.6 in Table 12 and explain how that target was chosen. The fixed-temperature tuning range and best-checkpoint selection protocol are also important for interpreting the reported accuracy gain. Moreover, Table 4 reports lower success for RF-BO than Original-SAC (52% versus 68%), so the entropy-tracking improvement should be distinguished from broader task-performance claims.

  3. The relationship between the theoretical assumptions and practical training remains unclear. The analysis relies on lower-level regularity and stable residual dynamics, while the GAN and SimCLR experiments involve complex nonconvex training. The paper would benefit from explaining which assumptions are plausible in these applications and which results should be interpreted as empirical observations beyond the guarantees. A focused sensitivity study of the lower/upper update ratio, or a diagnostic that temporarily freezes the upper variable and measures subsequent lower-level relaxation, could provide evidence for the proposed tracking mechanism. This would make the connection between timescale separation and practical stability more convincing.

Questions for authors
  1. Contribution and scope: What specific new insight does RF-BO provide beyond existing coupled-root TTSA and adaptive calibration methods? What practical guidance does the framework offer on when direct residual updates should be preferred?

  2. Experimental attribution: Can the authors clarify the exact difference from standard SAC and provide a focused comparison with matched optimization settings? Please also specify the SimCLR residual, justify the target selection, and explain the fixed-temperature tuning and checkpoint-selection protocols.

  3. Practical tracking: Can the authors discuss the applicability of the stability assumptions to GAN/SimCLR and provide a small diagnostic or update-ratio ablation supporting the claim that the lower-level model adequately tracks the changing upper-level parameter?

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

This paper introduces root-finding bilevel optimization (RF-BO) and proposes a Jacobian-free method based on two-timescale stochastic approximation (TTSA). The authors analyze variance amplification in stochastic Jacobian estimation (the "Variance Trap") and provide convergence guarantees and empirical results.

Critical strengths
  • The Variance Trap provides an interesting perspective on stochastic Jacobian estimation.
  • The experiments suggest potential benefits of Jacobian-free updates.
Critical weaknesses
  • Limited novelty: RF-BO appears to be a special case of the TTSA framework of Doan (2022), which already considers nested root-finding and convergence of both fast and slow variables. The proposed algorithm and convergence analysis largely follow this framework.
  • Strong assumption and unfair theoretical comparison: Assumption 5.3 requires global asymptotic stability of the limit ODE governing the slow timescale, which is a very strong assumption. In contrast, existing bilevel methods such as Kwon et al. (2023) and Hu et al. (2023) establish stationary-point guarantees without this assumption. The theoretical comparisons, particularly Table 1, do not adequately account for this substantial difference in assumptions.
Questions for authors
  • Beyond the extension to the PL setting in Theorem 5.6, what are the main theoretical contributions of Theorems 5.5 and 5.6 compared to existing TTSA results, particularly Doan (2022)?
  • How can the theoretical comparisons with existing bilevel methods be justified given the additional global stability assumption?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.