Nonconvex optimization algorithms with random initialization have attracted increasing attention recently. It has been showed that many first-order methods always avoid saddle points with random starting points. In this paper, we answer a question: can the nonconvex heavy-ball algorithms with random initialization avoi…
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,742 papers · 148 categories
Trend · papers per month
48 results for “saddle point formulation”
New method simplifies optimization landscapes by transforming saddle points.
problem Saddle points hinder non-convex optimization in machine learning.
method Variable elimination algorithms, like VarPro, are compared to reveal geometric insights.
result Variable elimination reshapes critical point structure, creating local maxima from saddle points.
New saddle network architectures preserve convex-concave geometry in optimization problems.
problem Optimization models with convex x and concave y components.
method Structured separable decomposition and saddle network architectures.
result Proven one-dimensional approximation theorem and high accuracy on various test functions.
Oracle-efficient algorithm for offline RL with partial data coverage.
problem Offline reinforcement learning with partial data coverage and constraints.
method PDOCRL, a primal-dual algorithm with decomposed linear-programming formulation.
result Near-optimal, near-feasible policy with \(\widetilde{\mathcal O}(ε^{-2})\) sample guarantee.
We consider the problem of computing optimal policies in average-reward Markov decision processes. This classical problem can be formulated as a linear program directly amenable to saddle-point optimization methods, albeit with a number of variables that is linear in the number of states. To address this issue, recent …
We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allo…
Equivalence of convex optimization, saddle-point problems, and variational inequalities is a well-established concept. The variational inequality (VI) is a static problem which is studied under dynamical settings using a framework called the projected dynamical system, whose stationary points coincide with the static s…
Survey of methods for solving smooth stochastic variational inequalities.
problem Solving smooth (strongly) monotone stochastic variational inequalities.
method Deterministic foundation, general stochastic formulation, finite sum setup, recent advances.
result Review of various methods for solving smooth stochastic variational inequalities.
New method for causal effect estimation with hidden confounders.
problem Estimating causal effects in the presence of hidden confounders.
method Singular value decomposition of a conditional expectation operator followed by saddle-point optimization.
result Our method outperforms existing methods on common benchmarks.
Active learning reduces SP calculations by 90%.
problem Efficiently calculating saddle points in energy functions.
method Active learning framework with GPR and GAD.
result Significant reduction in the number of expensive evaluations.
Study non-convex matrix factorization using Riemannian geometry.
problem Matrix completion via non-convex optimization.
method Optimization over a Grassmannian manifold, analyzing principal angles.
result Geodesically convex region in matrix completion cost function.
We consider discriminative dictionary learning in a distributed online setting, where a network of agents aims to learn a common set of dictionary elements of a feature space and model parameters while sequentially receiving observations. We formulate this problem as a distributed stochastic program with a non-convex o…
OKRidge solves sparse ridge regression problems for nonlinear systems.
problem Identifying sparse governing equations for nonlinear dynamical systems.
method OKRidge algorithm using saddle point formulation and ADMM-based approach with efficient proximal operators.
result OKRidge achieves provable optimality with significantly faster run times than Gurobi.
This paper concerns the recursive utility maximization problem under partial information. We first transform our problem under partial information into the one under full information. When the generator of the recursive utility is concave, we adopt the variational formulation of the recursive utility which leads to a s…
Decentralized learning for GLMs with feature distribution and network connectivity.
problem Optimizing generalized linear models in a decentralized network with feature partitioning.
method Chambolle--Pock primal--dual algorithm applied to an equivalent saddle-point formulation.
result Convergence rates for empirical risk minimization under Lipschitz and square root Lipschitz assumptions.
In this paper we propose a primal-dual proximal extragradient algorithm to solve the generalized Dantzig selector (GDS) estimation problem, based on a new convex-concave saddle-point (SP) reformulation. Our new formulation makes it possible to adopt recent developments in saddle-point optimization, to achieve the optim…
The paper analyzes GTD algorithms with finite-sample bounds.
problem Convergence rate analysis of GTD family of algorithms.
method Formulated as stochastic gradient algorithms and analyzed using saddle-point error.
result Obtained finite-sample bounds on GTD performance.
Generative Adversarial Networks have been shown to be powerful in generating content. To this end, they have been studied intensively in the last few years. Nonetheless, training these networks requires solving a saddle point problem that is difficult to solve and slowly converging. Motivated from techniques in the reg…
New algorithm provably converges to second-order stationary points in NMF.
problem Understanding convergence to local minima in NMF.
method Multiplicative weight update dynamics, concurrent updates, and simplex reduction.
result Provable convergence to second-order stationary points.
Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available for saddle-point optimization has focused on the offline setting. In this paper, we study nonstationar…
FeDualEx tackles saddle point optimization in federated learning with composite objectives.
problem Saddle point optimization with constraints and non-smooth regularization in federated learning.
method Federated Dual Extrapolation (FeDualEx) algorithm for saddle point optimization and composite objectives.
result FeDualEx effectively solves saddle point optimization problems with composite objectives in federated learning.
A new method helps escape saddle points in non-convex optimization.
problem Escaping saddle points in non-convex optimization problems.
method CNC-SCSG method using a separate SGD step to help escape from strict saddle points.
result The method converges to a second-order stationary point with a rate of .
Gradient descent can take exponentially long to escape saddle points in 2D.
problem Worst-case inefficiency of gradient descent in non-convex optimization.
method Analysis of gradient descent's performance on 2D functions.
result Gradient descent can take exponentially long to escape saddle points.
New methods help escape strict saddle points in nonsmooth optimization.
problem Escaping strict saddle points in nonsmooth optimization.
method An inexact stochastically perturbed gradient method applied to the Moreau envelope.
result A variety of algorithms for nonsmooth optimization can efficiently escape strict saddle points of the Moreau envelope.
New insights into matrix factorization show strict saddles have bounded eigenvalues.
problem Understanding the nature of critical points in matrix factorization.
method Analyzing orbits of critical points under the general linear group and identifying canonical points.
result Minimum eigenvalue of strict saddles is not uniformly bounded below zero.
Malware is constantly adapting in order to avoid detection. Model based malware detectors, such as SVM and neural networks, are vulnerable to so-called adversarial examples which are modest changes to detectable malware that allows the resulting malware to evade detection. Continuous-valued methods that are robust to a…
A new algorithm trains deep neural networks by adding neurons greedily.
problem Training deep neural networks efficiently and effectively.
method Neuron Pursuit (NP) algorithm, which alternates between neuron addition and loss minimization.
result The algorithm can train deep neural networks efficiently and effectively.
New method solves saddle-point problems faster than existing methods.
problem Large-scale saddle-point problems in optimization.
method Sequential subspace optimization with proximal regularization.
result Significantly better convergence compared to first-order methods.
Gradient-based optimization methods are the most popular choice for finding local optima for classical minimization and saddle point problems. Here, we highlight a systemic issue of gradient dynamics that arise for saddle point problems, namely the presence of undesired stable stationary points that are no local optima…
We present a novel algorithm for non-linear instrumental variable (IV) regression, DualIV, which simplifies traditional two-stage methods via a dual formulation. Inspired by problems in stochastic programming, we show that two-stage procedures for non-linear IV regression can be reformulated as a convex-concave saddle-…
This paper extends Newton's method to distributed learning, avoiding saddle points and handling Byzantine workers.
problem Avoiding saddle points in distributed non-convex optimization, especially in the presence of Byzantine workers.
method Extends cubic-regularized Newton method to distributed framework, addressing communication bottlenecks and Byzantine attacks.
result The method achieves improved iteration complexity compared to first-order methods, with a 25% improvement in experiments.
PWGF escapes saddle points in nonconvex optimization.
problem Escaping saddle points in nonconvex optimization.
method PWGF uses noisy perturbations via Gaussian process to escape saddle points.
result PWGF achieves second-order optimality for nonconvex objectives.
DLNs dynamics change with variance, leading to saddle-to-saddle training phases.
problem Understanding the dynamics of DLNs with varying initialization variance.
method Analyzing the phase transition of DLNs' dynamics as variance changes.
result Gradient descent visits a sequence of saddles, reaching a sparse global minimum.
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…
Last iterate of Extragradient algorithm converges slower than averaged iterates in saddle point problems.
problem Smooth convex-concave saddle point problems
method Analysis of Extragradient (EG) algorithm convergence rates
result The last iterate of EG converges at a rate of O(1/√T), compared to O(1/T) for averaged iterates
We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each iteration, our method randomly samples a block of coordinates of the primal and dual solutions to update. The linear convergence of our method…
Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equationsmath.OC
New ODE models show saddle-point optimization methods converge differently, with last-iterate convergence for OGDA.
problem Analyzing convergence properties of saddle-point optimization methods.
method High-Resolution Differential Equations (HRDEs) to design differential equation models for saddle-point optimization methods.
result HRDEs reveal last-iterate convergence for Optimistic Gradient Descent Ascent (OGDA) in bilinear games.
Houdini finds high-dimensional saddle points under few constraints.
problem Escaping from saddle points in high-dimensional spaces with constraints.
method Gradient descent methods under logarithmic inequality constraints.
result Polynomial time algorithms for escaping saddle points under constraints.
Extends saddle-point method for large-time volatility smiles.
problem Analyzing large-time volatility smiles in financial models.
method Saddle-point approach to derive large-time model-implied volatility smiles.
result Provides theoretical foundation and wide class of arbitrage-free parametrizations.
Deep ReLU networks escape from the origin via saddle points with a low-rank bias.
problem Understanding the dynamics of gradient descent in deep ReLU networks.
method Analysis of escape directions and singular values of weight matrices.
result The first singular value of the -th layer weight matrix is at least larger than any other singular value.
Paper defines saddle points in asymmetric Dynkin games using martingale theory.
problem Tackles saddle point conditions in asymmetric Dynkin games with partial information.
method Uses martingale theory to identify super and submartingales related to equilibrium payoffs.
result Characterizes saddle point strategies in terms of equilibrium payoffs' dynamics and Doob-Meyer decompositions.
Algorithm classifies saddle-focus singularities in Hamiltonian systems.
problem Classifying nondegenerate saddle-focus singularities in integrable Hamiltonian systems.
method Developed an algorithm based on semi-local equivalence to represent singularities as almost direct products.
result Obtained complete lists of saddle-focus singularities of complexities 1, 2, and 3.
New algorithm solves saddle point problems in Banach spaces.
problem Solving saddle point problems in real reflexive Banach spaces.
method Stochastic Bregman Primal-Dual Splitting Algorithm with relative smoothness and strong convexity assumptions.
result Almost sure convergence to saddle points under various conditions.
Distributionally Robust Optimization with Correlated Data from Vector Autoregressive Processesmath.OC
We present a distributionally robust formulation of a stochastic optimization problem for non-i.i.d vector autoregressive data. We use the Wasserstein distance to define robustness in the space of distributions and we show, using duality theory, that the problem is equivalent to a finite convex-concave saddle point pro…
Classifies Morse flows on 3-sphere with specific saddle connections.
problem Classifying Morse-Smale flows on a 3-sphere with specific saddle connections.
method Used generalized Heegaard diagrams (Pr-diagrams) to classify flows.
result Found all possible, up to homeomorphism, ways to embed two circles in a 2-sphere with no more than 10 points of transversal intersection.
Directional Convergence Near Small Initializations and Saddles in Two-Homogeneous Neural Networkscs.LG
The paper studies neural networks' convergence near origin and saddle points.
problem Directional convergence of neural networks near small initializations and saddle points.
method Gradient flow dynamics analysis of two-homogeneous neural networks.
result Neural networks' weights approximately converge in direction to KKT points for small initializations.
GenFlow optimizes faster, avoiding saddle points in fixed time.
problem Designing efficient optimization algorithms for convex and non-convex functions.
method Introduces GenFlow and momentum variants with fixed-time convergence guarantees.
result GenFlow and momentum variants converge to optimal solutions in fixed time for PL functions and evade saddle points uniformly.
Logistic Q-Learningcs.LG
Proposes a new reinforcement learning algorithm using Q-function.
problem Optimal control in Markov Decision Processes (MDPs).
method Regularized linear-programming formulation, Q-function, saddle-point optimization.
result Demonstrates effectiveness on various benchmark problems.