Non-Stationary Functional Bilevel Optimization

• URL: http://arxiv.org/abs/2601.15363v1
• Date: Wed, 21 Jan 2026 14:35:23 GMT
• Title: Non-Stationary Functional Bilevel Optimization
• Authors: Jason Bohne, Ieva Petrulionyte, Michael Arbel, Julien Mairal, Paweł Polak,
• Abstract summary: Functional bilevel optimization (FBO) provides a powerful framework for hierarchical learning in function spaces.<n>We propose SmoothFBO, the first algorithm for non-stationary FBO with both theoretical guarantees and practical scalability.
• Score: 21.88474848102693
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Functional bilevel optimization (FBO) provides a powerful framework for hierarchical learning in function spaces, yet current methods are limited to static offline settings and perform suboptimally in online, non-stationary scenarios. We propose SmoothFBO, the first algorithm for non-stationary FBO with both theoretical guarantees and practical scalability. SmoothFBO introduces a time-smoothed stochastic hypergradient estimator that reduces variance through a window parameter, enabling stable outer-loop updates with sublinear regret. Importantly, the classical parametric bilevel case is a special reduction of our framework, making SmoothFBO a natural extension to online, non-stationary settings. Empirically, SmoothFBO consistently outperforms existing FBO methods in non-stationary hyperparameter optimization and model-based reinforcement learning, demonstrating its practical effectiveness. Together, these results establish SmoothFBO as a general, theoretically grounded, and practically viable foundation for bilevel optimization in online, non-stationary scenarios.

Related papers

• Stochastic Regret Guarantees for Online Zeroth- and First-Order Bilevel Optimization [23.138958400600526]
  Online bilevel optimization (OBO) is a powerful framework for machine learning problems where both outer and inner objectives evolve over time.<n>Current OBO approaches rely on deterministic textitwindow-smoothed regret minimization, which may not accurately reflect system performance when functions change rapidly.<n>We introduce a novel search direction and show that both first- and zeroth-order (ZO) OBO algorithms leveraging this direction achieve sublinear stochastic bilevel regret without window smoothing.
  arXiv  Detail & Related papers  (2025-11-03T00:29:36Z)
• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand.<n>We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• MARINA-P: Superior Performance in Non-smooth Federated Optimization with Adaptive Stepsizes [57.24311218570012]
  We extend the non-smooth convex theory of EF21-P (Anonymous 2024) and MARINA-P (arXiv:2402.06412) in the non-size convex setting.<n>We provide theoretical guarantees under constant, decreasing, and adaptive (aktypetype) steps.
  arXiv  Detail & Related papers  (2024-12-22T16:18:34Z)
• Online Nonconvex Bilevel Optimization with Bregman Divergences [3.237380113935023]
  We introduce an online bilevel (SOB) method for updating outer-level variables using an average of recent variance rates. This approach is superior to the setting offline bilevel (OBO) as rates of hyperlevel benchmarks highlight the superior performance and efficiency.
  arXiv  Detail & Related papers  (2024-09-16T17:01:27Z)
• A Convex-optimization-based Layer-wise Post-training Pruner for Large Language Models [24.185245582500876]
  We introduce FISTAPruner, the first post-training pruner based on convex optimization models and algorithms. FISTAPruner incorporates an intra-layer cumulative error correction mechanism and supports parallel pruning. We evaluate FISTAPruner on models such as OPT, LLaMA, LLaMA-2, and LLaMA-3 with 125M to 70B parameters under unstructured and 2:4 semi-structured sparsity.
  arXiv  Detail & Related papers  (2024-08-07T12:33:46Z)
• Non-Convex Bilevel Optimization with Time-Varying Objective Functions [57.299128109226025]
  We propose an online bilevel optimization where the functions can be time-varying and the agent continuously updates the decisions with online data. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions.
  arXiv  Detail & Related papers  (2023-08-07T06:27:57Z)
• Model-based Causal Bayesian Optimization [78.120734120667]
  We propose model-based causal Bayesian optimization (MCBO) MCBO learns a full system model instead of only modeling intervention-reward pairs. Unlike in standard Bayesian optimization, our acquisition function cannot be evaluated in closed form.
  arXiv  Detail & Related papers  (2022-11-18T14:28:21Z)
• A General Recipe for Likelihood-free Bayesian Optimization [115.82591413062546]
  We propose likelihood-free BO (LFBO) to extend BO to a broader class of models and utilities. LFBO directly models the acquisition function without having to separately perform inference with a probabilistic surrogate model. We show that computing the acquisition function in LFBO can be reduced to optimizing a weighted classification problem.
  arXiv  Detail & Related papers  (2022-06-27T03:55:27Z)
• Feedback Gradient Descent: Efficient and Stable Optimization with Orthogonality for DNNs [3.42658286826597]
  We propose a novel method, named Feedback Gradient Descent (FGD), to our knowledge, the first work showing high efficiency and stability simultaneously. In the extensive image classification experiments, FGD comprehensively outperforms the existing state-of-the-art methods in terms of accuracy, efficiency, and stability.
  arXiv  Detail & Related papers  (2022-05-12T03:47:27Z)
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs [113.8752163061151]
  We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs)<n>We propose the underlineperiodically underlinerestarted underlineoptimistic underlinepolicy underlineoptimization algorithm (PROPO)<n>PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement.
  arXiv  Detail & Related papers  (2021-10-18T02:33:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.