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.
We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly seek to characterize the minimax number of first order queries required to optimize a convex Lipschitz function subject to a memory constra…
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.
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 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. 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. 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.
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 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. 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.
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. We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algor…
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 . 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.
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.
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 ε.
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.
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.
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.
SARAH and SPIDER are two recently developed stochastic variance-reduced algorithms, and SPIDER has been shown to achieve a near-optimal first-order oracle complexity in smooth nonconvex optimization. However, SPIDER uses an accuracy-dependent stepsize that slows down the convergence in practice, and cannot handle objec…
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…
This paper studies the lower bound complexity for the optimization problem whose objective function is the average of n n n individual smooth convex functions. We consider the algorithm which gets access to gradient and proximal oracle for each individual component. For the strongly-convex case, we prove such an algorith…
Unified approach for first-order methods with Markovian noise in stochastic optimization and variational inequalities.
problem Stochastic optimization problems with Markovian noise.
method Unified theoretical analysis of first-order gradient methods using randomized batching and multilevel Monte Carlo.
result Optimal (linear) dependence on the mixing time of the noise sequence, eliminating previous limiting assumptions.
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.
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.
We simplify deep learning convergence analysis using basic math.
problem Ensuring reliable convergence of optimization algorithms in deep networks.
method Elementary arguments and computations to estimate smoothness constants.
result Systematic computation of smoothness constants for first-order algorithms.
Optimized method tackles convex optimization with heavy-tailed noise.
problem Convex optimization problems with noisy gradients.
method Vanilla stochastic proximal subgradient method without gradient clipping or normalization.
result Achieves optimal complexity for various convex optimization types under heavy-tailed noise.
Method solves complex optimization problems with high probability bounds.
problem Nonlinear equality constrained stochastic optimization problems.
method Step-search sequential quadratic programming method.
result High-probability bound on iteration complexity for first-order stationarity.
Efficient algorithm for contextual bandits with first-order guarantees.
problem Adapting to low noise in contextual bandits.
method Reduction to online regression with logarithmic loss.
result Optimal and efficient first-order guarantees for contextual bandits.
We consider first order gradient methods for effectively optimizing a composite objective in the form of a sum of smooth and, potentially, non-smooth functions. We present accelerated and adaptive gradient methods, called FLAG and FLARE, which can offer the best of both worlds. They can achieve the optimal convergence …
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 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.
New algorithm solves complex minimax problems efficiently.
problem Minimizing and maximizing bilinearly coupled smooth functions.
method Lifted Primal-Dual (LPD) method that optimally handles both smooth and bilinear terms.
result First optimal algorithm achieving the lower complexity bound for the problem.
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.
Paper tackles private optimization for non-smooth objectives efficiently.
problem Private stochastic convex optimization for non-smooth objectives.
method Noisy mirror descent algorithm.
result Achieves optimal rates in statistical complexity and number of queries.
This paper analyzes bias-variance trade-off for clipped SFOMs, improving complexity guarantees for heavy-tailed noise.
problem Improving complexity guarantees for stochastic optimization methods with heavy-tailed noise.
method Novel analysis of bias-variance trade-off in gradient clipping for clipped SFOMs.
result Improved complexity guarantees for clipped SFOMs across various tail indices, including infinite mean noise.
Algorithms for bandit convex optimization and online learning often rely on constructing noisy gradient estimates, which are then used in appropriately adjusted first-order algorithms, replacing actual gradients. Depending on the properties of the function to be optimized and the nature of ``noise'' in the bandit feedb…
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. 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.
New algorithms solve complex multi-level optimization problems with improved efficiency.
problem Smooth stochastic multi-level composition optimization problems.
method Two algorithms using moving-average and linearized stochastic estimates.
result Achieved sample complexities of O(1/ε^4) and O(1/ε^6).
New algorithms optimize actions under time-varying constraints without projecting.
problem Optimizing actions under time-varying constraints without projecting.
method Projection-free algorithms using linear optimization oracle.
result Guaranteed i l d e O ( T 3 / 4 ) ilde{O}(T^{3/4}) i l d e O ( T 3/4 ) regret and O ( T 7 / 8 ) O(T^{7/8}) O ( T 7/8 ) constraints violation. 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.
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 …
A method for finding most influential sets reduces a complex problem to a sequence of simpler top- k k k problems.
problem Identifying most influential subsets in complex models.
method Reduces the problem to a sequence of top- k k k problems using Dinkelbach's method. result The method returns a globally optimal set for the univariate ratio objective, including partial linear models.
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 ) . Paper establishes lower bounds for finite-sum optimization problems using novel construction methods.
problem Lower complexity bounds for finite-sum optimization problems with various component functions.
method Developed novel approach to construct hard instances and analyzed PIFO algorithms.
result Established lower complexity bounds for convex-concave and nonconvex-strongly-concave objectives.
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.
New adaptive step-size method for convex optimization without tuning.
problem Optimizing convex functions efficiently with stochastic gradients.
method Adapted Adaptive Gradient Descent Without Descent to stochastic setting.
result Stochastic gradient descent converges under various assumptions.