A new method solves complex constrained minimax problems.
problem Solving constrained minimax optimization problems.
method First-order augmented Lagrangian method.
result Established an operation complexity of .
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,657 papers · 148 categories
Trend · papers per month
48 results for “first order methods”
Optimal first-order methods are shown to be fundamental limits in functional estimation.
problem Optimal functional estimation under weak conditions.
method Formalization of functional estimation with black-box nuisance function estimates and derivation of minimax lower bounds.
result First-order methods are optimal under weak conditions, but higher-order methods can outperform them when nuisance function structure is known.
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…
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.
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 new method solves a complex optimization problem efficiently.
problem Nonconvex-strongly-concave constrained minimax optimization.
method First-order augmented Lagrangian method with a first-order subproblem solver.
result Achieves improved operation complexity for finding solutions.
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.
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.
A framework for decentralized optimization using first-order methods.
problem Optimization of finite sums over networked nodes.
method Decentralized first-order gradient and stochastic methods.
result General framework for undirected and directed networks.
DEO uses gradient information to escape saddle points in neural networks.
problem Training deep neural networks struggles with flat regions and saddle points.
method Dimer-Enhanced Optimization (DEO) uses gradient information to estimate curvature and escape saddle points.
result DEO improves training efficiency and performance compared to standard first-order methods.
Develops a first-order interior-point method for solving constrained variational inequalities.
problem Solving constrained variational inequalities with nontrivial constraints.
method ADMM-based interior-point method for constrained VIs (ACVI).
result First-order interior-point method with global convergence guarantees for general cVI problems.
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.
First-order stochastic methods are the state-of-the-art in large-scale machine learning optimization owing to efficient per-iteration complexity. Second-order methods, while able to provide faster convergence, have been much less explored due to the high cost of computing the second-order information. In this paper we …
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.
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.
A new method learns node embeddings for signed directed networks by capturing both first-order and high-order topologies.
problem Learning representative node embeddings for signed directed networks considering both first-order and high-order topologies.
method Proposes a decoupled variational embedding (DVE) method that leverages a specially designed auto-encoder structure to capture both first-order and high-order topologies.
result Extensive experiments on real-world datasets show the effectiveness of DVE in link sign prediction and node recommendation tasks.
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.
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.
A guide for solving first-order elliptic boundary value problems.
problem Solving first-order elliptic boundary value problems on manifolds.
method Operator methods and general elliptic boundary conditions.
result Characterization of a new subclass of elliptic boundary conditions.
Paper improves stochastic bilevel optimization methods for highly-smooth problems.
problem Finding -stationary points in stochastic bilevel optimization.
method Proposes FSA- methods using th-order finite differences for hyper-gradient approximation.
result Achieves upper complexity bound of for th-order smooth problems.
In this paper, we provide an overview of first-order and second-order variants of the gradient descent method that are commonly used in machine learning. We propose a general framework in which 6 of these variants can be interpreted as different instances of the same approach. They are the vanilla gradient descent, the…
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.
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.
A geometric Laplace methodmath.DG
Geometrically reformulates the Laplace method for optimal transport.
problem Approximating integrals using the Laplace method without geometric interpretation.
method Introduces the Kim-McCann Riemannian metric to give a geometric formulation of the Laplace method.
result Expresses the first-order term of the Laplace method using geometric objects.
First-order ANIL learns shared representations even with overparametrization.
problem Lack of theoretical evidence for model-agnostic meta-learning (ANIL) learning shared representations.
method First-order ANIL with a linear two-layer network architecture, showing asymptotically low-rank solutions with overparametrization.
result First-order ANIL learns linear shared representations, even with overparametrization, and performs well in adaptation.
New method accelerates steepest descent for convex optimization.
problem Achieving acceleration for general smooth functions.
method Primal-dual iterate sequences with differing norms, implicitly determined interpolation parameter.
result Improves iteration complexity to for norm smooth problems.
First-order methods such as stochastic gradient descent (SGD) are currently the standard algorithm for training deep neural networks. Second-order methods, despite their better convergence rate, are rarely used in practice due to the prohibitive computational cost in calculating the second-order information. In this pa…
New methods reduce constraint violations to certainty in stochastic optimization.
problem Finding a point with certain constraint satisfaction and near-stationarity.
method Single-loop variance-reduced stochastic first-order methods with truncated momentum schemes.
result Achieves strong convergence guarantees for -stochastic stationary points with certain constraint satisfaction.
This is the first in a series of papers in which we study an efficient approximation scheme for solving the Hamilton-Jacobi-Bellman equation for multi-dimensional problems in stochastic control theory. The method is a combination of a WKB style asymptotic expansion of the value function, which reduces the second order …
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.
In this paper we study general Schatten- quasi-norm (SPQN) regularized matrix minimization problems. In particular, we first introduce a class of first-order stationary points for them, and show that the first-order stationary points introduced in [11] for an SPQN regularized minimization problem are equiva…
First order discretizations of Langevin diffusion can achieve better generalization error with additional smoothness assumptions.
problem Analyzing generalization error for first order discretizations of Langevin diffusion.
method Providing a sufficient smoothness condition to show that first order methods can achieve arbitrarily runtime complexity for a given expected generalization error.
result First order methods can achieve arbitrarily runtime complexity with additional smoothness assumptions.
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…
Second-order methods improve differential privacy in convex optimization.
problem Improving differential privacy in convex optimization.
method Developed a private variant of the regularized cubic Newton method for strongly convex loss functions.
result Achieves quadratic convergence and optimal excess loss for strongly convex loss functions.
Second-order optimizers retain residual information after data deletion, affecting machine unlearning.
problem Residual information in second-order optimizers after data deletion.
method Comparison of first-order and second-order learners, eigendecomposition analysis.
result Second-order optimizers retain residual information, not detectable by first-order analysis.
Paper introduces STSL, a second-order Tweedie sampler for efficient posterior sampling in inverse problems.
problem Computational challenges in sampling from posterior distributions using latent diffusion models.
method Introduces STSL, a novel second-order Tweedie sampler with tractable reverse process.
result STSL achieves 4X and 8X reduction in neural function evaluations compared to state-of-the-art solvers.
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 …
Computation of first-order Greeks for barrier options using chain rules for Wiener path integralsq-fin.MF
This paper presents a new methodology to compute first-order Greeks for barrier options under the framework of path-dependent payoff functions with European, Lookback, or Asian type and with time-dependent trigger levels. In particular, we develop chain rules for Wiener path integrals between two curves that arise in t…
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.
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 convergence for stochastic oracles and for deterministic oracles.
Unified framework for analyzing batch updating methods with noisy gradients.
problem Analyzing convergence of batch updating methods with noisy gradients and approximations.
method Unified framework using convergence of stochastic processes.
result Establishes a general theorem for most known convergence results.
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 provide improved convergence rates for various \emph{non-smooth} optimization problems via higher-order accelerated methods. In the case of regression, we achieves an iteration complexity, breaking the barrier so far present for previous methods. We arrive at a similar rate fo…
Logistic regression is one of the most popular methods in binary classification, wherein estimation of model parameters is carried out by solving the maximum likelihood (ML) optimization problem, and the ML estimator is defined to be the optimal solution of this problem. It is well known that the ML estimator exists wh…
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…
A first-order model for a stock market assigns to each stock a return parameter and a variance parameter that depend only on the rank of the stock. A second-order model assigns these parameters based on both the rank and the name of the stock. First- and second-order models exhibit stability properties that make them a…
Many problems in machine learning and game theory can be formulated as saddle-point problems, for which various first-order methods have been developed and proven efficient in practice. Under the general convex-concave assumption, most first-order methods only guarantee an ergodic convergence rate, that is, the uniform…
Compensation methods correct overestimation of adversarial robustness in neural networks.
problem Overestimation of adversarial robustness using first-order attack methods.
method Proposed compensation methods address inaccurate gradient computation and reduce backpropagations.
result Empirical evaluation of adversarial robustness is improved with these methods.