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.
New algorithms solve non-convex isotonic regression problems efficiently.
problem Minimizing submodular functions with ordering constraints.
method Discretization schemes leading to zero-th, first, or higher order oracles for efficient optimization.
result Non-convex loss functions can be robust to outliers and still lead to efficient optimization.
Study asks if memory constraints affect optimal convex optimization methods.
problem Characterize the minimax number of queries for convex optimization with memory constraints.
method Analyze first order methods under memory limitations.
result Optimal oracle complexity may be achievable with limited memory.
A new method for faster optimization of noisy functions.
problem Optimizing noisy functions efficiently.
method A universal and adaptive second-order method for convex functions.
result Achieves O ( σ / T ) O(σ/ \sqrt{T}) O ( σ / T ) convergence for stochastic oracles and O ( 1 / T 3 ) O( 1 / T^3) O ( 1/ T 3 ) for deterministic oracles. Improved algorithm finds second-order stationary points in non-convex optimization.
problem Minimizing non-convex objectives while preserving training data privacy.
method SpiderBoost framework with two gradient oracles: precise and less precise.
result Improved rates for finding second-order stationary points.
A new algorithm for solving constrained convex optimization problems efficiently.
problem Constrained convex optimization problems requiring high accuracy solutions.
method Second-Order Conditional Gradient Sliding (SOCGS) algorithm, using projection-free methods to solve quadratic subproblems inexactly.
result Converges quadratically in primal gap after a finite number of linearly convergent iterations.
Piecewise polynomial interpolation-based gradient descent reduces oracle complexity for smooth loss functions.
problem Optimizing empirical risk minimization loss functions
method Piecewise polynomial interpolation-based gradient descent
result Oracle complexity is reduced for smooth loss functions
New methods solve optimization problems with heavy-tailed noise, improving upon existing complexity bounds.
problem Optimization problems with heavy-tailed noise and weakly average smoothness.
method Normalized stochastic first-order methods with Polyak, multi-extrapolated, and recursive momentum.
result First-order oracle complexity results for finding approximate stochastic stationary points under heavy-tailed noise.
Paper establishes tight lower bounds for minimizing certain smooth and convex functions.
problem Minimizing high-order Hölder smooth and uniformly convex functions.
method Analyzes two asymmetric cases of q > p + ν q > p + ν q > p + ν and q < p + ν q < p + ν q < p + ν using worst-case oracle complexities. result Establishes worst-case oracle complexities for reaching an ε-approximate solution.
Paper develops a TR-SSQP method for noisy optimization with heavy-tailed noise.
problem Optimization problems with stochastic objectives and heavy-tailed noise.
method Trust-Region Stochastic Sequential Quadratic Programming (TR-SSQP) method.
result Achieves high-probability first-order and second-order stationarity bounds for heavy-tailed noise.
Study on gradient complexity of private optimization with private oracles.
problem Analyzing the efficiency of differentially private optimization algorithms.
method Lower bounds on the number of first-order oracle queries for private optimization.
result Lower bounds on the number of queries for private optimization algorithms, showing a dimension-dependent runtime penalty.
Improved stochastic approximation method reduces residual error.
problem Reducing residual error in stochastic approximation algorithms.
method Fixed-schedule one-quarter barrier and bias-corrected acceleration.
result Achieves T − 1 / 2 + o ( 1 ) T^{-1/2+o(1)} T − 1/2 + o ( 1 ) residual reduction with O ( 1 ) O(1) O ( 1 ) primitive samples. Improved method reduces projection calls for nonsmooth convex optimization.
problem Optimizing nonsmooth convex functions with convex constraints.
method MOPES and MOLES methods combining Moreau-Yosida smoothing and accelerated first-order schemes.
result Achieves ε ε ε -suboptimality with significantly fewer projection calls. Lower bounds for higher-order methods in non-convex optimization.
problem Proving lower bounds for higher-order methods in smooth non-convex finite-sum optimization.
method Analyzing deterministic and randomized algorithms, proposing a new smoothness assumption.
result Proves optimal lower bounds for simulating pth-order regularized methods on the whole function.
New method accelerates steepest descent for convex optimization.
problem Achieving acceleration for general ℓ p \ell_p ℓ p smooth functions. method Primal-dual iterate sequences with differing norms, implicitly determined interpolation parameter.
result Improves iteration complexity to O ( d 1 − 2 p ) O(d^{1-\frac{2}{p}}) O ( d 1 − p 2 ) for ℓ p \ell_p ℓ p norm smooth problems. New algorithm optimizes convex functions with noisy evaluations in one dimension.
problem Optimizing convex functions with noisy zero-order evaluations in one dimension.
method Proposed a computationally efficient algorithm achieving O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate. result Achieved the optimal O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate, closing the gap in one dimension. Improved zeroth-order algorithms tackle nonconvex minimax problems with reduced complexity.
problem Nonconvex minimax optimization problems in machine learning.
method Design and analysis of Zeroth-Order Gradient Descent Ascent ( exttt{ZO-GDA}) and Zeroth-Order Gradient Descent Multi-Step Ascent ( exttt{ZO-GDMSA}) algorithms.
result Oracle complexity improvements for minimax optimization problems.
New algorithms optimize convex functions with high-order derivatives.
problem Optimizing convex functions with high-order derivatives under various norms.
method Developed a non-Euclidean inexact accelerated proximal point method using an inexact uniformly convex regularizer.
result Showed nearly optimal algorithms for high dimensions in the black-box oracle model for ℓ p \ell_p ℓ p -settings and all q ≥ 1 q \geq 1 q ≥ 1 . New algorithm solves complex optimization problems without needing projections.
problem Optimizing nested functions under convex constraints with noisy evaluations.
method Projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization.
result The algorithm achieves ε ε ε -stationary solutions with complexity bounds independent of ε ε ε and T T T . New method finds stationary points in bilevel optimization problems.
problem Solving nonconvex-strongly-convex bilevel optimization problems.
method Restarted Accelerated HyperGradient Descent (RAHGD) method.
result Achieves best-known theoretical guarantees for finding stationary points in bilevel optimization.
Study improves CTS's approximation regret for combinatorial bandits.
problem Improving CTS's performance on non-exact oracles.
method Develops a new O ( log ( T ) / Δ ) \mathcal{O}(\log(T)/Δ) O ( log ( T ) /Δ ) upper bound for CTS under specific conditions. result First O ( log ( T ) / Δ ) \mathcal{O}(\log(T)/Δ) O ( log ( T ) /Δ ) approximation regret upper bound for CTS. Paper tackles dynamic pricing in a geometrically decaying environment, achieving better occupancy with lower rates.
problem Minimizing expected loss in a dynamically changing environment with decisions dependent on the data distribution.
method Introduces algorithms for information and loss function settings, using repeated decision deployment to allow mixing of the environment.
result Iteration complexity matches first and zero order stochastic gradient methods up to logarithmic factors.
The paper analyzes the complexity of sparse label propagation on networks.
problem Computational complexity of sparse label propagation on network data.
method Characterization of iterations for achieving a prescribed accuracy using a first-order oracle model.
result An upper bound on iterations required for accuracy, showing sharpness for chain structures.
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. SGD's performance improves with critical batch size, minimizing SFO complexity.
problem Optimizing SGD's performance with batch size and learning rate.
method Analysis of SGD using constant and decaying learning rates, focusing on batch size effects.
result SGD with critical batch size minimizes SFO complexity.
New analysis shows Thompson Sampling can work with greedy approximations in combinatorial bandits.
problem Thompson Sampling's theoretical limits with greedy approximations in combinatorial semi-bandits.
method Study with greedy oracle, providing lower and upper bounds on regret.
result First theoretical results showing TS can work with greedy approximations, breaking misconceptions.
Improved non-smooth optimization methods achieve faster convergence rates.
problem Non-smooth optimization problems, especially in ℓ ∞ \ell_\infty ℓ ∞ and ℓ 1 \ell_1 ℓ 1 -SVM. method Higher-order accelerated methods, leveraging recent advances in smooth convex optimization.
result Achieved O ( ε − 4 / 5 ) O(ε^{-4/5}) O ( ε − 4/5 ) iteration complexity for ℓ ∞ \ell_\infty ℓ ∞ regression, breaking previous barriers. Paper introduces structured sparsity estimators for Generalized Linear Models.
problem Estimating structured sparsity in GLMs with debiased estimators.
method Extends Stucky and van de Geer's results to GLMs with structured sparsity.
result Proves oracle inequalities for structured sparsity estimators in GLMs.
Propose an XMSE-aware mixed estimator for EB that interpolates between ML and EB shrinkage.
problem Kernel-based EB estimation may be worse than ML when the kernel is poorly aligned with the true parameter.
method An XMSE-aware mixed estimator that interpolates between ML and EB shrinkage.
result Fixed-weight XMSE is a scalar quadratic, yielding a closed-form oracle mixing weight that is no worse than both ML and the base EB estimator at the XMSE scale.
Novel methods for accelerating optimization in complex bilevel and minimax problems.
problem Optimization challenges in bilevel and minimax problems, especially when strong convexity assumptions are not met.
method Accelerated fully first-order methods for Bilevel Optimization (BLO) and Minimax Optimization (NCSC).
result State-of-the-art complexity for finding approximate second-order stationary points in BLO and NCSC.
Reduces non-convex optimization to finding local minima using gradients.
problem Finding local minima in non-convex optimization problems.
method Reduces non-convex optimization to gradient-based methods.
result Turns various optimization algorithms into local minimum finding methods.
A new method reduces the complexity of decentralized optimization.
problem Decentralized stochastic non-convex optimization over a network.
method GT-HSGD, a hybrid variance-reduced method.
result Achieves an oracle complexity of O(n^(-1)ε^(-3)) for small ε.
Lower bounds found for nonconvex-strongly-concave min-max optimization problems.
problem Finding stationary points in nonconvex-strongly-concave min-max optimization.
method Provided lower bounds for first-order oracle complexity.
result Lower bounds of Ω(√κε⁻²) for deterministic oracles and Ω(√κε⁻² + κ¹/₃ε⁻⁴) for stochastic oracles.
Quadratic memory is essential for optimal convex optimization queries.
problem Optimal query complexity for convex optimization and feasibility problems.
method Lower bounds on query complexity for convex optimization and feasibility problems.
result Center-of-mass algorithms are Pareto-optimal for both convex optimization and feasibility problems.
SpiderBoost improves SPIDER's efficiency and applicability in optimization.
problem Optimization of smooth nonconvex functions and handling nonsmooth regularizers.
method SpiderBoost uses a larger constant-level stepsize and proximal mapping for composite optimization, achieving improved oracle complexity.
result SpiderBoost achieves an oracle complexity of O ( min { n 1 / 2 ε − 2 , ε − 3 } ) \mathcal{O}(\min\{n^{1/2}ε^{-2},ε^{-3}\}) O ( min { n 1/2 ε − 2 , ε − 3 }) in composite nonconvex optimization. Paper establishes lower bounds for optimization of convex functions.
problem Lower bounds for optimization of convex functions with gradient and proximal oracle access.
method Developed a novel construction to prove lower bounds for strongly-convex case.
result Lower bound matches upper bound of existing algorithm Point-SAGA.
New algorithms solve convex optimization problems with limited memory.
problem Solving convex optimization problems with constrained memory.
method Recursive cutting-plane algorithms dividing variables into blocks.
result Achieves optimal memory usage and oracle complexity in certain regimes.
The paper analyzes the efficiency of gradient estimation methods in noisy function evaluations.
problem Estimating gradients of smooth functions using noisy function evaluations.
method Information-theoretic lower bounds and finite difference method analysis.
result The finite difference method is not minimax optimal, suggesting room for improvement in gradient estimation.
Paper tackles sampling from non-log-concave distributions using denoising diffusion.
problem Sampling from non-log-concave distributions efficiently.
method DDMC framework, Zeroth-Order Diffusion Monte Carlo (ZOD-MC) algorithm.
result ZOD-MC achieves inverse polynomial dependence on sampling accuracy, efficient for low dimensions.
Unified theory for UCB policies in total and max bandit problems.
problem Order optimality of UCB policies in max bandit problems.
method Unified definition of UCB policy using oracle quantity and failure count.
result UCB policies are order optimal in both total and max bandit problems.
New algorithms ensure reproducibility and optimal convergence in convex optimization.
problem Trade-off between reproducibility and convergence rate in convex optimization.
method Regularization-based algorithms for smooth convex minimization and minimax optimization.
result Achieves optimal reproducibility and near-optimal gradient complexity for various oracle settings.
Study efficient algorithms for nonconvex optimization with state-dependent Markov data.
problem Stochastic optimization with Markovian data and state-dependent transition kernels.
method Projection-based and projection-free algorithms for constrained nonconvex problems.
result The number of oracle calls to achieve an ε ε ε -stationary point is O ( 1 / ε 2.5 ) \mathcal{O}(1/ε^{2.5}) O ( 1/ ε 2.5 ) . Develops accelerated methods for optimization using low-dimensional projected-gradient information.
problem Optimization with low-dimensional projected-gradient information and Nesterov acceleration.
method Randomized-subspace Nesterov accelerated gradient methods for smooth convex and strongly convex optimization.
result Established accelerated oracle-complexity guarantees and unified basis for comparing sketch families.
New algorithm reduces online learning error for unknown feature distributions.
problem Oracle-efficient hybrid online learning with unknown feature and label distributions.
method Computational efficient online predictor using ERM oracle for finite-VC and fat-shattering classes.
result Oracle-efficient sublinear regret bounds for hybrid online learning with unknown feature generation.
New methods boost first-order optimization with faster rates.
problem Designing efficient first-order methods for convex problems.
method Shifted objective function with interpolation condition.
result New schemes achieve faster convergence rates.
A novel distributed method tracks gradients for convex optimization over networks.
problem Distributed optimization of strongly-convex functions over a network.
method S-AB algorithm using auxiliary variables and row/column stochastic weights.
result Linear convergence to a neighborhood of the global minimizer.
In this work we introduce a conditional accelerated lazy stochastic gradient descent algorithm with optimal number of calls to a stochastic first-order oracle and convergence rate O ( 1 ε 2 ) O\left(\frac{1}{\varepsilon^2}\right) O ( ε 2 1 ) improving over the projection-free, Online Frank-Wolfe based stochastic gradient descent of Hazan an…
Finite-sum optimization problems are ubiquitous in machine learning, and are commonly solved using first-order methods which rely on gradient computations. Recently, there has been growing interest in \emph{second-order} methods, which rely on both gradients and Hessians. In principle, second-order methods can require …