Two classes of methods have been proposed for escaping from saddle points with one using the second-order information carried by the Hessian and the other adding the noise into the first-order information. The existing analysis for algorithms using noise in the first-order information is quite involved and hides the es…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “First-order algorithms”
New algorithm reduces online decision-making regret with efficient LP re-solving and parallel first-order method.
problem Worse regret guarantees and high computational cost of LP-based OLP algorithms.
method Combines LP-based and first-order OLP methods, re-solving LP subproblems periodically and using parallel first-order method.
result Achieves regret, balancing computational efficiency and superior regret guarantee.
Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcs.LG
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.
The filtering-clustering models, including trend filtering and convex clustering, have become an important source of ideas and modeling tools in machine learning and related fields. The statistical guarantee of optimal solutions in these models has been extensively studied yet the investigations on the computational as…
CEFOL uses deep learning for dynamic programming with recursive utility.
problem Challenges in solving dynamic programming problems with recursive utility.
method Introduces a separate neural network for certainty equivalent, uses first-order optimality conditions to learn value and policy functions.
result CEFOL achieves high accuracy in learning value and policy functions, matching VFI benchmarks.
Efficient RNN algorithm guarantees convergence in online learning.
problem Online nonlinear regression with RNNs.
method First-order training algorithm with convergence guarantee.
result The algorithm converges to optimum network parameters.
Improved first-order algorithm for entropy regularized OT with faster convergence.
problem Solving entropy regularized optimal transport efficiently.
method Accelerated primal-dual stochastic mirror descent algorithm with variance reduction.
result Improved rate from to .
New algorithms optimize constrained problems faster, avoiding full set optimization.
problem Optimizing constrained problems efficiently and quickly.
method Designing accelerated first-order algorithms that avoid full set optimization.
result Proved convergence to stationary points in nonconvex settings and accelerated rates in convex settings.
New memory-query tradeoffs for convex optimization algorithms.
problem Optimizing memory usage for convex optimization algorithms.
method Analyzing randomized first-order algorithms for minimizing convex functions.
result Cutting plane methods are optimal in terms of memory and query complexity.
Basic Inequalities for First-Order Optimization with Applications to Statistical Risk Analysismath.ST
New inequalities help optimize first-order algorithms for statistical risk analysis.
problem Optimizing first-order iterative algorithms for statistical risk analysis.
method Introducing basic inequalities that connect implicit and explicit regularization.
result The basic inequalities translate the number of iterations into an effective regularization coefficient.
Memory-constrained algorithms need superlinear memory for efficient convex optimization.
problem Efficiently minimizing convex functions with limited memory.
method Analyzing first-order algorithms with superlinear memory constraints.
result Superlinear memory is necessary for optimal performance in convex optimization.
Unified bounds for iterative algorithms with Gaussian data matrices.
problem Establishing non-asymptotic bounds for iterative algorithms with Gaussian data.
method Explicit coupling between iterates and Gaussian process with deterministic covariance.
result Tight, dimension-free bounds for generalized first-order methods.
This paper improves online learning algorithms for LP problems, achieving better regret bounds.
problem Achieving optimal regret bounds in online linear programming.
method Develops a new framework for first-order online learning algorithms under certain error bound conditions.
result First-order learning algorithms achieve regret in continuous support and regret in finite support, improving over .
Paper develops fast method for computing optimal transport.
problem Efficient computation of optimal transport distance between distributions.
method Entropy-regularized extragradient method for first-order optimization.
result Achieves state-of-the-art runtime guarantees and good numerical performance.
Generalizes Hamiltonian theory for variational problems, applied to first order gravity.
problem Formulating Hamiltonian field theory for variational problems of general nature.
method Introduces a generalized Hamiltonian formalism without requiring a Hamiltonian section.
result Develops a novel multisymplectic Hamiltonian field theory for first order gravity.
New algorithm for safer machine learning with different testing and training distributions.
problem Challenges in modern machine learning where training and testing distributions differ.
method First-order optimization algorithm for superquantile-based learning.
result Promising numerical results show the approach's effectiveness.
BMM algorithm improves convergence for nonconvex optimization problems.
problem Constrained nonsmooth nonconvex optimization problems.
method Block majorization-minimization with diminishing radius.
result Improved convergence rate for nonconvex optimization problems.
We establish that first-order methods avoid saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical s…
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…
Geodesic convexity generalizes the notion of (vector space) convexity to nonlinear metric spaces. But unlike convex optimization, geodesically convex (g-convex) optimization is much less developed. In this paper we contribute to the understanding of g-convex optimization by developing iteration complexity analysis for …
We analyze stochastic gradient algorithms for optimizing nonconvex problems. In particular, our goal is to find local minima (second-order stationary points) instead of just finding first-order stationary points which may be some bad unstable saddle points. We show that a simple perturbed version of stochastic recursiv…
A new algorithm solves bilevel optimization with linear constraints.
problem Solving bilevel optimization problems with coupled linear constraints.
method Penalty and augmented Lagrangian methods reformulate the problem; a single-loop, first-order algorithm proposed.
result Improved convergence rates compared to prior methods.
We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine learning where the datasets are large and have to be stored on different machines. We design a distributed stochastic variance reduced gradien…
In this paper, we consider first-order convergence theory and algorithms for solving a class of non-convex non-concave min-max saddle-point problems, whose objective function is weakly convex in the variables of minimization and weakly concave in the variables of maximization. It has many important applications in mach…
In this paper, we study optimization methods consisting of iteratively minimizing surrogates of an objective function. By proposing several algorithmic variants and simple convergence analyses, we make two main contributions. First, we provide a unified viewpoint for several first-order optimization techniques such as …
We present a predictor-corrector framework, called PicCoLO, that can transform a first-order model-free reinforcement or imitation learning algorithm into a new hybrid method that leverages predictive models to accelerate policy learning. The new "PicCoLOed" algorithm optimizes a policy by recursively repeating two ste…
New method for tuning Graphical Lasso hyperparameters.
problem Tuning hyperparameters of Graphical Lasso.
method Bilevel optimization with first-order method.
result Derivation of Graphical Lasso Jacobian.
Recent applications that arise in machine learning have surged significant interest in solving min-max saddle point games. This problem has been extensively studied in the convex-concave regime for which a global equilibrium solution can be computed efficiently. In this paper, we study the problem in the non-convex reg…
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.
Paper proposes an algorithm to solve complex minimax problems efficiently.
problem Stochastic nonconvex-concave minimax problems in various fields.
method Accelerated first-order regularized momentum descent ascent algorithm (FORMDA).
result Achieves best-known complexity bound of for single-loop algorithms.
A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singletoncs.LG
New framework tackles bi-level optimization without LLS condition.
problem Bi-level optimization problems without LLS condition.
method Bi-level Descent Aggregation (BDA) framework, proving convergence without LLS condition.
result Proves convergence of BDA without LLS condition.
First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functionscs.LG
First order methods can take extremely long to find global minima of non-convex functions.
problem Finding global minimizers of non-convex functions.
method Designing a family of non-convex functions and using statistical lower bounds for parameter estimation.
result First order methods can take exponential time to converge to a global minimizer.
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.
Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oraclescs.LG
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.
Novel BSG method for efficient stochastic optimization.
problem Efficient optimization of non-convex surfaces in stochastic settings.
method Binary search combined with first order gradient optimization.
result BSG produces more promising results and better generalization than other methods.
LMC algorithm converges to target in Chi-squared and Renyi divergence.
problem Sampling from target distribution using LMC with strong dissipativity and smoothness conditions.
method LMC algorithm with strong dissipativity and first-order smoothness, initialized with Gaussian.
result LMC reaches ε-neighborhood of target in Chi-squared and Renyi divergence in O(λ²dε⁻¹) steps.
Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisemath.OC
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.
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatormath.OC
In this paper, we propose a new technique named \textit{Stochastic Path-Integrated Differential EstimatoR} (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order method…
New methods bound estimation error in high-dimensional statistical problems.
problem Fundamental limits of first order methods in high-dimensional estimation.
method Introduces general first order methods for high-dimensional regression and low-rank matrix estimation.
result Derives optimal lower bounds on estimation error for these methods.
A new method speeds up quantum state estimation.
problem Exponential growth in sample size and dimension for quantum state tomography.
method Stochastic mirror descent with Burg entropy.
result Optimization error vanishes at a rate.
We consider empirical risk minimization of linear predictors with convex loss functions. Such problems can be reformulated as convex-concave saddle point problems, and thus are well suitable for primal-dual first-order algorithms. However, primal-dual algorithms often require explicit strongly convex regularization in …
Adaptive learning rate algorithms such as RMSProp are widely used for training deep neural networks. RMSProp offers efficient training since it uses first order gradients to approximate Hessian-based preconditioning. However, since the first order gradients include noise caused by stochastic optimization, the approxima…
Information geometry applies concepts in differential geometry to probability and statistics and is especially useful for parameter estimation in exponential families where parameters are known to lie on a Riemannian manifold. Connections between the geometric properties of the induced manifold and statistical properti…
A new first-order sampler improves diffusion probabilistic model sampling quality.
problem The belief that first-order methods are inherently slower for diffusion probabilistic model sampling.
method A novel training-free, first-order sampler that approximates the forward-value evaluation via a one-step lookahead predictor.
result The proposed sampler provably approximates the ideal forward-value trajectory while retaining first-order convergence and can improve sample quality under the same NFE budget.
State evolution beyond first-order methods I: Rigorous predictions and finite-sample guaranteesmath.ST
New method predicts state evolution for non-first-order algorithms on nonconvex problems.
problem Analyzing nonconvex optimization problems with random data.
method Developed a state evolution for a broader class of algorithms including first-order and saddle point updates.
result Established rigorous state evolution predictions and finite-sample guarantees for non-first-order methods.
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.
Standard gradient descent methods are susceptible to a range of issues that can impede training, such as high correlations and different scaling in parameter space.These difficulties can be addressed by second-order approaches that apply a pre-conditioning matrix to the gradient to improve convergence. Unfortunately, s…
We provide two fundamental results on the population (infinite-sample) likelihood function of Gaussian mixture models with components. Our first main result shows that the population likelihood function has bad local maxima even in the special case of equally-weighted mixtures of well-separated and spherical…