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.
Paper tackles Hessian/Jacobian-free stochastic bilevel optimization with O(ε−1.5) complexity.
problem Nonconvex-strongly-convex bilevel optimization problem.
method FdeHBO optimizer with finite-difference Hessian/Jacobian-vector approximation and momentum.
result FdeHBO achieves O(ε−1.5) iterations for ε-accurate stationary point. 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 algorithm tackles stochastic bilevel optimization under relaxed smoothness conditions.
problem Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions.
method Introduces a novel fully single-loop and Hessian-inversion-free algorithmic framework for stochastic bilevel optimization.
result Demonstrates state-of-the-art oracle complexity results for multi-objective robust bilevel optimization.
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.
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.
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.
First-order method solves stochastic bilevel optimization with linear constraints.
problem Stochastic bilevel optimization with linear constraints and noise.
method Developed a novel framework using gradient-based techniques and smoothed penalty functions.
result Achieved finite-time convergence guarantees for (δ,ε)-Goldstein stationary points. New lower bounds for bilevel optimization with first-order oracles.
problem Complexity of bilevel optimization with first-order oracles.
method Development of hard instances and proof of lower bounds.
result Nontrivial lower bounds for first-order zero-respecting algorithms.
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.
Study analyzes a new algorithm for complex optimization problems.
problem Stochastic bilevel optimisation problems in continuous-time models.
method Continuous-time, two-timescale stochastic approximation algorithm.
result Obtained weak convergence rate using central limit theorem.
New methods solve complex optimization problems without strong convexity assumptions.
problem Complex bilevel optimization problems with minimax lower-level structures.
method Penalty-based first-order methods for bilevel minimax optimization.
result Achieves ε-KKT point with improved oracle complexity. New methods optimize complex optimization problems with improved efficiency.
problem Optimizing complex problems with a convex lower-level objective.
method Uses stochastic cutting planes and conditional gradient updates.
result Improves complexity for both convex and non-convex upper-level functions.
SUSTAIN algorithm tackles stochastic bilevel optimization with near-optimal complexity.
problem Stochastic bilevel optimization problems with specific convexity and smoothness properties.
method SUSTAIN algorithm using single-timescale double-momentum stochastic approximation.
result SUSTAIN achieves near-optimal complexity for finding ε-stationary solutions.
Paper improves stochastic bilevel optimization methods for highly-smooth problems.
problem Finding ε-stationary points in stochastic bilevel optimization. method Proposes F2SA-p methods using pth-order finite differences for hyper-gradient approximation. result Achieves upper complexity bound of ildeO(pε−4−p/2) for pth-order smooth problems. A new framework for bilevel optimization tackles stochastic and global variance reduction.
problem Bilevel optimization challenges in large-scale empirical risk minimization.
method Introducing a novel framework where inner and main variables evolve simultaneously, leading to unbiased estimates and global variance reduction algorithms.
result SABA algorithm achieves $O( rac{1}{T})$ convergence rate and linear convergence under Polyak-Lojasciewicz assumption.
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.
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.
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.
Paper tackles multi-block min-max optimization with applications in deep AUC maximization.
problem Multi-block min-max bilevel optimization with non-convex strongly-concave upper level and strongly convex lower level.
method Single-loop randomized stochastic algorithm for constant number of blocks per iteration.
result Sample complexity of O(1/ε^4) for finding ε-stationary point, matching optimal complexity.
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.
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.
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.
This paper tackles regularization parameter learning in inverse problems using data-driven bilevel optimization.
problem Finding optimal regularization parameters in inverse problems.
method Data-driven bilevel optimization approach, analyzing performance in large data samples.
result The approach can reduce computational cost through online numerical schemes based on stochastic gradient descent.
New method achieves optimal sample complexity without warm-start in bilevel optimization.
problem Optimizing smooth objective functions with fixed point constraints in meta-learning and equilibrium models.
method Fixed point iterations at lower-level and projected inexact gradient descent at upper-level.
result Achieves near optimal sample complexity O(ε−2) and ildeO(ε−1) samples. 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). 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.
This paper tackles Sinkhorn DRO by reformulating it as a bilevel program and proposes sampling-based algorithms.
problem Distributionally robust optimization with ambiguity sets defined via the Sinkhorn discrepancy.
method Primal perspective reformulation as a bilevel program, double-loop and single-loop sampling-based algorithms.
result Simultaneously obtain the optimal robust decision and the worst-case distribution.
Proposes a stochastic method for solving trilevel optimization problems.
problem Efficient and theoretically sound methods for trilevel optimization.
method Stochastic gradient descent method for unconstrained trilevel optimization.
result First convergence theory for stochastic methods in trilevel optimization.
Paper integrates predictive and prescriptive tasks using bilevel optimization.
problem Combining prediction and decision-making in machine learning.
method Bilevel optimization for integrating predictive and prescriptive tasks.
result Improved decision-making through direct integration of predictions.
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.
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.
New method tackles bilevel optimization with polyhedral constraints.
problem Challenges in bilevel optimization with active-set changes and expensive Hessian inversions.
method Logarithmic barrier smoothing and proxy-gradient algorithm for differentiable approximation.
result Stationarity rates of O(K−2/3) in deterministic setting and O(K−2/5) under stochastic noise. New algorithms tackle complex multi-block optimization problems in machine learning.
problem Non-convex multi-block bilevel optimization with hierarchical sampling challenges.
method Blockwise stochastic variance-reduced methods with parallel speedup.
result Achieves matching complexity to single-block problems with parallel speedup.
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.
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.
Unified framework for decentralized bilevel optimization with various heterogeneity-correction strategies.
problem Decentralized bilevel optimization with neighborhood communications and data heterogeneity.
method SPARKLE: Single-loop Primal-dual Algorithm for decentralized bilevel optimization, incorporating various heterogeneity-correction techniques.
result Unified convergence analysis for SPARKLE with state-of-the-art convergence rates compared to existing algorithms.
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 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.
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.
A new method optimizes diffusion models for fine-tuning tasks efficiently.
problem Optimizing diffusion models for downstream tasks using nested bilevel structures.
method Formalizes the challenge as a generative bilevel optimization problem and introduces a first-order bilevel framework.
result Our method outperforms existing fine-tuning and hyperparameter search baselines.
Novel method for bilevel optimization with convex lower-level problem.
problem Minimizing a smooth objective over the optimal solution set of a convex constrained problem.
method Local cutting plane approximation of lower-level solution set combined with conditional gradient updates.
result Achieves optimal iteration complexity for the considered class of bilevel problems.
Paper proposes SMO for solving bilevel optimization problems efficiently.
problem Solving bilevel optimization problems with nonsmooth convex lower-level and nonconvex upper-level objectives.
method Sequential minimax optimization (SMO) method using modified augmented Lagrangian and penalty schemes.
result Improves operation complexity for finding ε-KKT solutions. 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.
Paper tackles bilevel optimization problems using penalty methods.
problem Unconstrained and constrained bilevel optimization problems with nonsmooth lower levels.
method Introduces first-order penalty methods and O(ε−4logε−1) and O(ε−7logε−1) operation complexities. result Establishes operation complexities for finding ε-KKT solutions. New method improves FO-BLO convergence without increasing memory or time complexity.
problem Lack of theoretical understanding of FO-BLO convergence.
method Unbiased first-order bilevel optimization (UFO-BLO) to improve convergence.
result Theoretical guarantee of convergence for FO-BLO-based stochastic optimization.
BILBO optimizes bilevel problems without repeated lower-level optimizations.
problem Challenges in bilevel optimization, especially in noisy, constrained, and derivative-free settings.
method BILevel Bayesian Optimization (BILBO) that optimizes both levels simultaneously, using confidence-bounds and function query selection.
result Theoretical and empirical evidence of BILBO's effectiveness on various problems.
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.