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.
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.
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.
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…
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.
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.
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.
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.
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.
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 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.
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.
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 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.
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.
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.
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…
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.
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.
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…
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…
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…
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.
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.
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.
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.
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…
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.
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.
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 …
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…
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.
For a surface in the 3-dimensional real projective space, we define a Gauss map, which is a quadric in and called the first-order Gauss map. It will be shown that the surface is a Demoulin surface if and only if the first-order Gauss map is conformal, and the surface is a projective minimal coincidence …
A wide class of regularization problems in machine learning and statistics employ a regularization term which is obtained by composing a simple convex function ωwith a linear transformation. This setting includes Group Lasso methods, the Fused Lasso and other total variation methods, multi-task learning methods and man…
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.
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.
New sampling method guarantees approximate first-order stationary points for non-convex functions.
problem Sampling from non-log-concave densities with non-convex potential functions.
method Averaged Langevin Monte Carlo with complexity analysis.
result Langevin Monte Carlo outputs a sample with ε-relative Fisher information after O(L²d²/ε²) iterations.
OSGM uses online learning to adapt stepsize for faster convergence.
problem Improving convergence rates of first-order methods.
method OSGM combines online learning and feedback functions to adjust stepsize.
result OSGM achieves convergence rates asymptotically no worse than optimal.
A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraintsmath.OC
Unified analysis of first-order methods for smooth games using IQCs.
problem Certify convergence rates of first-order methods for smooth and strongly-monotone games.
method Adapted integral quadratic constraints (IQCs) to study first-order methods and derive tight upper bounds of convergence rates.
result First global convergence rate for the negative momentum method with iteration complexity.
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.
Develops first-order methods for average-reward MDPs with strong guarantees.
problem Lack of strong theoretical guarantees for first-order methods in AMDPs.
method Average-reward stochastic policy mirror descent (SPMD) and variance-reduced temporal difference (VRTD) methods.
result Establishes sample complexity results for solving AMDPs.
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.
Examines how first-order differential operators can be equivalently transformed.
problem Equivalence of first-order linear differential operators.
method Discussion of equivalency transformations.
result Explains how first-order differential operators can be transformed equivalently.
The paper analyzes reinforcement learning methods for estimating weights and quality functions with fast convergence rates.
problem Estimating weights and quality functions in reinforcement learning with function approximation.
method The paper uses minimax methods for estimating marginal importance weights and q-functions.
result The minimax approach enables fast rates of convergence for weights and quality functions, achieving first-order efficiency.