New framework solves dynamic bilevel optimization problems in reinforcement learning.
problem Dynamic objective functions in reinforcement learning and human feedback.
method Principled penalty-based methods for bilevel reinforcement learning.
result Demonstrated effectiveness of penalty-based algorithms in simulations.
New method circumvents non-convexity in bilevel RL via hyper-gradient.
problem Non-convexity in lower-level RL problems in bilevel reinforcement learning.
method Characterizing hyper-gradient via fully first-order information, circumventing convexity assumption.
result Developed model-based and model-free algorithms with convergence rate O(ε−1). This paper proposes a gossip-based algorithm for distributed bilevel optimization over networks.
problem Distributed bilevel optimization over networks with limited communication.
method Gossip-based distributed bilevel learning algorithm.
result Achieves optimal sample complexities for general and strongly convex objectives.
New approach to bilevel optimization for machine learning using functional methods.
problem Solving bilevel optimization problems in machine learning, especially with over-parameterized neural networks.
method Functional point of view, scalable and efficient algorithms for functional bilevel optimization.
result Demonstrates benefits of functional approach on instrumental regression and reinforcement learning tasks.
New analysis improves understanding of bilevel optimization stability and generalization.
problem Understanding how well bilevel optimization algorithms generalize.
method Algorithmic stability arguments and generalization bounds for three bilevel minimax solvers.
result Precise trade-off between algorithmic stability, generalization gaps, and practical settings.
SmoothFBO tackles non-stationary functional bilevel optimization.
problem Current FBO methods are limited to static offline settings and perform poorly in online, non-stationary scenarios.
method SmoothFBO introduces a time-smoothed stochastic hypergradient estimator with a window parameter to handle non-stationarity.
result SmoothFBO achieves sublinear regret and outperforms existing methods in non-stationary hyperparameter optimization and model-based reinforcement learning.
The paper analyzes convergence rates of bilevel optimization algorithms and introduces a new stochastic algorithm.
problem Nonconvex-strongly-convex bilevel optimization problems in machine learning.
method Comprehensive convergence rate analysis for deterministic bilevel optimization using AID and ITD, and a novel stochastic algorithm stocBiO.
result Theoretical convergence rates for AID and ITD methods, and stocBiO's superior performance.
New method solves complex bilevel optimization problems.
problem Challenging bilevel optimization problems in machine learning.
method Penalty-based bilevel gradient descent (PBGD) algorithm.
result PBGD algorithm converges for constrained bilevel problems.
CB-RL solves complex decision-making problems with contextual information and exogenous events.
problem Optimal policy in strategic decision-making problems that depend on environmental configuration and exogenous events.
method Contextual Bilevel Reinforcement Learning (CB-RL) with a stochastic Hyper Policy Gradient Descent (HPGD) algorithm.
result Demonstrated convergence and performance of the HPGD algorithm for reward shaping and tax design.
A new method solves bilevel optimization problems in competitive Markov games.
problem Capturing competitive structures in RL with multiple interacting policies.
method Penalty-augmented Nikaido-Isoda descent-ascent (PANDA) method.
result PANDA converges to stationary points without convexity assumptions.
This work tackles the challenge of aligning generative models without explicit reward signals.
problem Aligning generative models without explicit reward signals.
method A Bilevel Optimization framework where the reward function is treated as the optimization variable of an outer-level problem.
result Theoretical analysis and insights generalize to tabular classification and model-based reinforcement learning.
Paper tackles low sample and communication complexities in decentralized bilevel optimization.
problem Decentralized bilevel optimization problems with limited computation and communication capabilities.
method Proposes INTERACT and SVR-INTERACT algorithms to achieve low sample and communication complexities.
result Achieves both low sample and communication complexities for solving decentralized bilevel optimization problems.
Meta-learning balances task-specific modeling and optimization complexity.
problem Balancing accurate task-specific modeling with ease of optimization in meta-learning.
method Theoretical and empirical analysis of trade-off between modeling and optimization in meta-learning.
result Explicit bounds on modeling and optimization errors for non-convex and linear regression problems.
Unified analysis of neural networks in NPIV using 2SLS and MFLD.
problem Global convergence of neural networks in NPIV.
method Lifted perspective through MFLD, penalty gradient approach for bilevel optimization.
result First global convergence result of neural networks for 2SLS in NPIV.
This thesis analyzes and improves convergence rates of bilevel optimization algorithms in machine learning.
problem Convergence analysis and algorithm design for bilevel optimization in machine learning.
method Comprehensive convergence rate analysis for both problem-based and algorithm-based bilevel optimization formulations.
result First lower bounds and matching upper bounds for bilevel optimization, and new stochastic algorithms with lower complexity.
New Hessian-free method improves bilevel optimization for meta-learning.
problem Efficiently solving bilevel optimization problems with limited second-order information.
method Proposes a new Hessian-free method that approximates the response Jacobian matrix via optimization path differences.
result Demonstrates superior performance on meta-learning tasks compared to baseline methods.
A new algorithm tackles bilevel optimization with multiple inner minima.
problem Challenges in bilevel optimization with multiple inner minima.
method Reformulated as constrained optimization, solved via primal-dual bilevel optimization (PDBO) algorithm.
result First non-asymptotic convergence guarantee for bilevel optimization with multiple inner minima.
Develops a new method for efficient stochastic bilevel optimization.
problem Stochastic bilevel optimization problems in machine learning applications.
method Single-Timescale stochAstic BiLevEl optimization (STABLE) method.
result Achieves the same order of sample complexity as stochastic gradient descent for single-level optimization.
SAIL improves online alignment of large language models with minimal feedback.
problem Offline RLHF methods often lead to sub-optimal performance due to fixed preference datasets.
method SAIL uses bilevel optimization and a single-level first-order method to iteratively refine model alignment.
result SAIL significantly improves alignment performance on open-sourced datasets with minimal computational overhead.
This paper optimizes multi-channel sequential advertising to maximize cumulative revenue.
problem Maximizing cumulative revenue in multi-channel sequential advertising under a budget constraint.
method Formulated as a dynamic knapsack problem, proposed a bilevel optimization framework with action space reduction.
result Significantly improved cumulative revenue compared to state-of-the-art baselines.
Improved bilevel model solves complex machine learning problems faster and more accurately.
problem Complex hierarchical machine learning problems with inner and outer problem correlation.
method Proposed an improved bilevel model with theoretical guarantees and empirical validation.
result Empirical results show our model outperforms current bilevel models significantly.
Bilevel Continual Learning improves continual learning by transferring knowledge effectively.
problem Catastrophic forgetting and poor generalization in continual learning.
method Bilevel optimization and dual memory management strategies.
result BCL achieves effective knowledge transfer and alleviates catastrophic forgetting.
BOML unifies meta-learning methods into a common bilevel optimization framework.
problem Meta-learning methods with diverse modeling aspects.
method Modularized bilevel optimization library in Python.
result Unified solution for various meta-learning formulations.
Despite the empirical success of the actor-critic algorithm, its theoretical understanding lags behind. In a broader context, actor-critic can be viewed as an online alternating update algorithm for bilevel optimization, whose convergence is known to be fragile. To understand the instability of actor-critic, we focus o…
New algorithms reduce bilevel optimization complexity to ε^(-1.5).
problem Efficiently solving bilevel optimization problems in machine learning.
method Proposed two new algorithms: one using momentum-based recursive iterations, the other using recursive gradient estimations.
result Achieved computational complexity of ε^(-1.5), significantly faster than previous methods.
New methods solve complex optimization problems in machine learning.
problem Challenges in stochastic bilevel optimization with constraints and high variables.
method Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problems.
result Comprehensive convergence theory for both unconstrained and constrained cases.
Semiparametric method removes bias in functional bilevel gradient estimation.
problem First-order bias in plug-in hypergradient when lower-level problem is nonparametric.
method Semiparametric debiasing theory based on efficient influence function leads to cross-fitted orthogonal hypergradient estimator.
result Asymptotic normality and uniform control over outer parameter established for the estimator.
A new method tackles bilevel optimization using Lanczos process for efficient hyper-gradient computation.
problem Efficiently solving large-scale bilevel optimization problems with gradient-based methods.
method Constructing low-dimensional approximate Krylov subspaces with the Lanczos process to approximate the Hessian inverse vector product.
result Demonstrates a O(ε−1) convergence rate and efficiency in synthetic and deep learning tasks. New algorithm achieves linear speedup in non-i.i.d. federated bilevel learning.
problem Linear speedup in convergence for non-i.i.d. datasets in federated bilevel optimization.
method Proposes FedMBO with a novel client sampling scheme for non-i.i.d. datasets.
result Achieves a convergence rate of O(1/√(nK) + 1/K + √n/K³/²).
Paper tackles efficient SGD methods for constrained bilevel optimization.
problem Stochastic bilevel optimization with equality constraints.
method Alternating implicit projected SGD and its variants.
result Achieves sample complexity matching state-of-the-art for unconstrained problems.
Optimizes bilevel empirical risk minimization with improved oracle calls.
problem Optimizing bilevel empirical risk minimization problems.
method Proposes a bilevel extension of the SARAH algorithm.
result Demonstrates improved oracle calls to achieve stationarity.
Novel approach trains ASR models with less supervision using bilevel optimization.
problem Training acoustic models for ASR with minimal supervision.
method Bilevel optimization with unsupervised and supervised losses.
result Achieves superior performance compared to existing methods.
Solving a bilevel optimization problem is at the core of several machine learning problems such as hyperparameter tuning, data denoising, meta- and few-shot learning, and training-data poisoning. Different from simultaneous or multi-objective optimization, the steepest descent direction for minimizing the upper-level c…
Develops an algorithm for bilevel optimization with coupled constraints.
problem Challenges in bilevel optimization with coupled constraints.
method Primal-dual-assisted penalty approach and a fully first-order algorithm (BLOCC).
result Established rigorous convergence theory and demonstrated effectiveness on real-world applications.
We introduce a framework based on bilevel programming that unifies gradient-based hyperparameter optimization and meta-learning. We show that an approximate version of the bilevel problem can be solved by taking into explicit account the optimization dynamics for the inner objective. Depending on the specific setting, …
A bilevel optimization method for reweighting data leads to suboptimal results.
problem Reweighting data for better model performance on a different distribution.
method Formalizes data reweighting as a bilevel optimization problem and analyzes the limitations of classical solvers.
result The final data weights are often very sparse, indicating suboptimal solutions.
The paper compares unrolling and bilevel optimization for learning variational models.
problem Learning variational models in supervised learning.
method Analyzes unrolling and bilevel optimization approaches for variational models.
result Unrolling can be better than bilevel optimization, but performance depends on parameters.
New method creates coresets for deep neural networks efficiently.
problem Efficiently handling large data streams with limited resources.
method Cardinality-constrained bilevel optimization for deep neural networks.
result Demonstrated efficient generation of coresets for deep neural networks.
AdaSDBO solves decentralized bilevel optimization without problem parameters, achieving competitive performance.
problem Decentralized bilevel optimization problems without known parameters.
method AdaSDBO, a fully problem-parameter-free algorithm with adaptive stepsizes.
result AdaSDBO achieves a convergence rate of $\widetilde{\mathcal{O}}\left(\frac{1}{T}
ight)$, matching state-of-the-art methods up to polylogarithmic factors.
Single-timescale analysis improves convergence in multi-sequence stochastic approximation.
problem Finite-time convergence of nonlinear stochastic approximation with multiple coupled sequences.
method Smoothness property of fixed points and analysis of fine-grained single-timescale SA.
result Improved iteration complexity for achieving ε-accuracy in multi-sequence single-timescale SA.
Framework solves bilevel optimization on manifolds.
problem Solving bilevel optimization problems with manifold constraints.
method Hypergradient estimation strategies on manifolds, convergence and complexity analyses.
result Efficacy demonstrated through various applications.
New method reduces labeling costs in semi-supervised learning.
problem Efficiently label data with limited labeled samples.
method Formulates batch acquisition as bilevel optimization.
result Shows effectiveness in keyword detection tasks.
Paper extends MLFD to signed measures via bilevel approach.
problem Risk minimization for infinite width neural networks and sparse deconvolution.
method Bilevel reduction to extend MLFD to signed measures, investigating convergence rates.
result Improved convergence rates for bilevel MFLD in low-noise regime and local exponential convergence for single neuron learning.
A large portion of passenger requests is reportedly unserviced, partially due to vacant for-hire drivers' cruising behavior during the passenger seeking process. This paper aims to model the multi-driver repositioning task through a mean field multi-agent reinforcement learning (MARL) approach that captures competition…
This paper improves the convergence rates of bilevel optimization algorithms.
problem Improving the convergence rates of bilevel optimization algorithms.
method Provided lower complexity bounds and proposed an accelerated bilevel optimizer.
result AccBiO achieves optimal results under certain conditions.
New algorithm improves understanding of decentralized SBO transient iteration complexity.
problem Limited understanding of how network topology, data heterogeneity, and nested structures affect SBO.
method D-SOBA framework with two variants: D-SOBA-SO and D-SOBA-FO, providing non-asymptotic convergence analysis and transient iteration complexity.
result First theoretical understanding of how network topology, data heterogeneity, and nested structures influence decentralized SBO.
NHGD solves bilevel optimization problems with reduced computational time.
problem Solving bilevel optimization problems with high computational cost.
method Exploits statistical structure of inner optimization to use empirical Fisher matrix as Hessian surrogate, enabling parallel optimization and approximation.
result NHGD achieves error bounds and sample complexity guarantees matching state-of-the-art methods, with significantly reduced computational time.
Proposes a gradient-based bilevel optimization method for efficient hyperparameter tuning.
problem Efficiently tuning hyperparameters in machine learning models.
method Gradient-based bilevel optimization approach.
result The proposed method is multiple times faster than existing techniques.