Proposes a new algorithm for nonconvex sparse learning problems that converges quickly.
problem Nonconvex sparse learning problems in high dimensions.
method Combines proximal Newton algorithm with DC programming for multi-stage convex relaxation.
result Achieves quadratic convergence and finds sparse approximate local optima.
Simple stochastic Newton and cubic Newton methods with fast convergence.
problem Minimizing large numbers of smooth and strongly convex functions.
method Stochastic Newton and cubic Newton methods with simple local linear-quadratic rates.
result Local linear-quadratic convergence results with fast adaptation to problem's curvature.
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.
Gradient shrinking solitons from Ricci flows terminating in cones.
problem Understanding Ricci flows that terminate in cones.
method Proving properties of Ricci flows with quadratic curvature decay and cone convergence.
result Ricci flows terminating in cones are gradient shrinking solitons.
Improved DANE algorithm for faster convergence in distributed machine learning.
problem Challenges in convergence of DANE algorithm for general convex functions.
method Introducing variants of DANE with backtracking line search and heavy-ball method.
result Proved global and local convergence rates for quadratic and non-quadratic strongly convex functions.
Alt-GDA outperforms Sim-GDA in minimax games with near-optimal local convergence.
problem Minimax optimization convergence rate comparison
method Alternating Gradient Descent-Ascent (Alt-GDA) vs. Simultaneous Gradient Descent-Ascent (Sim-GDA)
result Alt-GDA achieves near-optimal local convergence rate for strongly convex-strongly concave problems, while Sim-GDA converges slower.
New tensor recovery method uses Riemannian optimization on Segre manifold.
problem Recovering low-rank tensors from noisy measurements.
method Riemannian Gradient Descent (RGD) and Riemannian Gauss-Newton (RGN) algorithms over the Segre manifold.
result Proven convergence rates for RGD and RGN under mild noise assumptions.
Scalable method completes ill-conditioned matrices from few samples.
problem Matrix completion from few samples for ill-conditioned matrices.
method Iterative algorithm combining IRLS, smoothing Newton, and proximal gradient methods.
result Local quadratic convergence rate and well-conditioned linear systems.
We investigate a class of quadratic-exponential growth BSDEs with jumps. The quadratic structure introduced by Barrieu & El Karoui (2013) yields the universal bounds on the possible solutions. With local Lipschitz continuity and the so-called A_gamma-condition for the comparison principle to hold, we prove the existenc…
New analysis improves SGD for robust and quantile regression with sub-quadratic convergence.
problem Improving SGD for robust and quantile regression with sub-quadratic convergence.
method Piecewise Lyapunov function for first-order differentiable functions.
result First geometrical convergence result for sub-quadratic SGD.
The paper studies quadratic neural networks, proving existence of spurious minima and saddle points.
problem Understanding the loss landscape of neural networks with quadratic activations.
method Theoretical analysis of mean squared error loss for neural networks with quadratic activations.
result Proves existence of spurious local minima and saddle points in the training landscape of deep overparameterized quadratic neural networks.
Policy-gradient algorithms fail to converge to Nash equilibria in continuous state and action space games.
problem Policy-gradient algorithms lack convergence guarantees in multi-agent continuous state and action space games.
method Analysis of gradient-play in linear quadratic games, showing non-convexity and counterexamples.
result Policy-gradient algorithms can avoid Nash equilibria in certain continuous state and action space games.
Policy gradient converges to globally optimal policy in nearly linear-quadratic systems.
problem Finding optimal policies in nonlinear control systems with partial information.
method Policy gradient algorithm designed for nearly linear-quadratic regulators with small Lipschitz nonlinear components.
result Policy gradient algorithm converges to globally optimal policy with linear rate.
A general class of Newton algorithms on Graßmann and Lagrange-Graßmann manifolds is introduced, that depends on an arbitrary pair of local coordinates. Local quadratic convergence of the algorithm is shown under a suitable condition on the choice of coordinate systems. Our result extends and unifies previous convergenc…
The paper tackles control policy learning for unknown systems using convex optimization.
problem Learning control policies for unknown linear dynamical systems to maximize a quadratic reward function.
method Sequential convex programming to optimize expected reward over posterior system parameter distribution.
result The method achieves reliable local convergence and robust stability, demonstrated with strong performance and robustness in simulations and real-world applications.
Policy optimization converges to Nash equilibria in zero-sum LQ games.
problem Finding Nash equilibria in zero-sum linear quadratic games.
method Developed three projected nested-gradient methods to converge to NE.
result Policy optimization methods converge to Nash equilibria in zero-sum LQ games.
Efficient algorithms compute lambda quantiles for robust portfolio optimization.
problem Computing lambda quantiles efficiently and robustly.
method Λ-Newton-Bis algorithm combining Newton's method and bisection, interval analysis for multiple roots.
result Demonstrated computational efficiency and practical relevance in portfolio optimization.
New Q-Newton's method avoids saddle points and converges quadratically.
problem Optimizing functions with saddle points and ensuring convergence guarantees.
method Modified New Q-Newton's method with Backtracking line search.
result Theorem for Morse functions: quadratic convergence to local minima.
Unified Newton-type methods for convex optimization using generalized self-concordant functions.
problem Designing efficient Newton-type methods for convex optimization.
method Introducing generalized self-concordant functions and developing Newton-type methods.
result Unified framework for global and local convergence of Newton-type methods.
New insights into convergence and accuracy trade-offs in federated and meta-learning.
problem Understanding the trade-offs between convergence and accuracy in federated and meta-learning.
method Generalized local update methods, proving equivalence to first-order optimization on a surrogate loss.
result Novel convergence rates and insights into the importance of algorithmic choices in communication-limited settings.
We propose HAMSI (Hessian Approximated Multiple Subsets Iteration), which is a provably convergent, second order incremental algorithm for solving large-scale partially separable optimization problems. The algorithm is based on a local quadratic approximation, and hence, allows incorporating curvature information to sp…
Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resourc…
Derivative-free method solves stochastic optimization problems with noisy objectives and constraints.
problem Solving nonlinear optimization problems with stochastic objectives and deterministic constraints using only zero-order information.
method Derivative-Free Stochastic Sequential Quadratic Programming (DF-SSQP) method using simultaneous perturbation stochastic approximation (SPSA) for gradient and Hessian estimation.
result Global almost-sure convergence of the DF-SSQP method under standard assumptions, with local asymptotic normality and statistical inference.
We discuss the geometry of some arithmetic orbifolds locally isometric to a product of real hyperbolic spaces of dimension two and three, and prove that certain sequences of non-uniform orbifolds are convergent to this space in a geometric ("Benjamini--Schramm") sense for hyperbolic three--space and a product of hyperb…
QMME balances cost and speed in convex optimization.
problem Slow convergence of first-order methods and high cost of second-order methods.
method Minimizing quadratic majorants with fixed curvature at each iteration.
result QMME framework achieves sequential convergence under standard assumptions.
SGD and stochastic gradient descent converge at optimal rates for certain non-convex functions.
problem Optimal convergence rates for non-convex functions under gradient noise.
method Geometric interpretation of the PL-condition to analyze convergence rates.
result Convergence rates of SGD and stochastic gradient descent match those of strongly convex quadratics.
In this paper, we study the efficiency of a {\bf R}estarted {\bf S}ub{\bf G}radient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an ε-optimal solution with a lower complexity than the SG m…
Paper develops RGN method for estimating low-rank tensors from noisy measurements.
problem Estimating low-rank tensors from noisy linear measurements.
method Riemannian Gauss-Newton (RGN) method for efficient low-rank tensor estimation.
result First local quadratic convergence guarantee of RGN for low-rank tensor estimation in noisy settings.
Neural networks with Xavier initialization converge to global minimum in the scaling limit.
problem Optimizing neural networks with Xavier initialization in the large network limit.
method Stochastic analysis and convergence to a random ODE with a Gaussian distribution.
result The neural network converges to a global minimum in the limit, with zero loss.
Study shows a linear quadratic regulator's imitation learning converges globally.
problem Global convergence of imitation learning for linear quadratic regulators.
method Analyzed alternating gradient algorithm and established Q-linear rate of convergence.
result Established a unique saddle point for globally optimal policy and reward function.
Yau's Affine Normal Descent optimizes smooth unconstrained problems with geometrically adapted directions.
problem Optimizing smooth unconstrained problems with geometrically adapted directions.
method Yau's Affine Normal Descent (YAND) uses the equi-affine normal of level-set hypersurfaces as search directions.
result YAND converges globally under standard smoothness assumptions and locally quadratically near nondegenerate minimizers.
SCAFFOLD improves Federated Learning by reducing client-drift and speeding up convergence.
problem Federated Learning's performance is limited by client-drift in heterogeneous data.
method SCAFFOLD uses control variates to correct client-drift and improve convergence.
result SCAFFOLD requires fewer communication rounds and is not affected by data heterogeneity.
In this paper, we present a novel penalty approach for the numerical solution of continuously controlled HJB equations and HJB obstacle problems. Our results include estimates of the penalisation error for a class of penalty terms, and we show that variations of Newton's method can be used to obtain globally convergent…
New method shows Hessian estimator from random samples converges to true Hessian on complex manifolds.
problem Uncertainty in Hessian estimator accuracy on complex manifolds with boundaries and nonuniform sampling.
method Locally fitting quadratic polynomials, rigorous theoretical analysis under mild conditions.
result The Hessian estimator asymptotically converges to the true Hessian, even near boundaries.
Local update methods' performance depends on learning rates, affecting convergence rates and alignment with true loss.
problem The performance of local update methods in federated learning and meta-learning is sensitive to learning rates.
method Proved that local update methods perform SGD on a surrogate loss function, characterized the surrogate loss, and derived convergence rates.
result Proper learning rate tuning is crucial for near-optimal behavior in communication-limited settings.
Complex-valued neural networks avoid spurious local minima.
problem Finding spurious local minima in neural networks.
method Proved no spurious local minima for shallow complex neural networks with quadratic activations.
result Complex-valued weights eliminate spurious local minima in neural networks.
Stochastic second-order methods converge fast under interpolation conditions.
problem Minimizing smooth and strongly-convex functions efficiently.
method Regularized subsampled Newton method (R-SSN) and stochastic BFGS algorithms.
result R-SSN achieves global linear convergence and quadratic rate in a local neighbourhood.
New method solves large-scale QCPs using low-discrepancy sequences.
problem Solving large-scale Quadratically Constrained Quadratic Programs (QCQP).
method Transforming QCQP into a linear problem via low-discrepancy sampling.
result Approximate solutions converge to true solutions and have finite sample error bounds.
Local SGD outperforms minibatch SGD for quadratic objectives.
problem Theoretical foundations of local SGD are lacking.
method Proved local SGD strictly dominates minibatch SGD for quadratic objectives and accelerated local SGD is minimax optimal.
result Local SGD does not dominate minibatch SGD in general convex objectives.
Enhances BO in high dimensions with Newton methods.
problem Challenges in scaling BO to high-dimensional spaces.
method Construct multiple local quadratic models using gradients and Hessians from a global GP, and select new sample points by solving bound-constrained quadratic programs.
result Outperforms existing high-dimensional BO techniques on synthetic and real-world applications.
GEORCE computes geodesics quickly and accurately.
problem Computing geodesics on Riemannian and Finsler manifolds is difficult and inefficient.
method GEORCE transforms geodesic computation into a discrete control problem.
result GEORCE achieves global convergence and quadratic local convergence.
This paper analyzes saddle points and minimax points in non-convex smooth games.
problem Understanding local optimal points in non-convex smooth games.
method Comprehensive analysis of local minimax points, including their optimality conditions and stability.
result Local saddle points are uniformly local minimax points under mild continuity assumptions.
New bounds on optimal transport regularization show faster convergence rates than previously known.
problem Understanding the localization rate of Quadratically Regularized Optimal Transport (QOT) optimizers.
method Established lower bounds and derived mean-squared deviation controls for QOT optimizers.
result Lower bound of support concentration rate εd+21 in directed Hausdorff distance. The paper extends a variance gamma model to quadratic functions, reducing arbitrage and computational costs.
problem Creating an arbitrage-free interpolation for option pricing models.
method Generalizing the local variance gamma model to a piecewise quadratic local variance function.
result The quadratic model results in an arbitrage-free interpolation of class C3, reducing knots and computational cost.
NOHD optimizes multi-agent systems by decomposing dynamics into irrotational and solenoidal components.
problem Non-stationarity and conflicting interests in multi-agent learning problems.
method NOHD (Newton Optimization on Helmholtz Decomposition) decomposes system dynamics into irrotational and solenoidal components.
result NOHD ensures quadratic convergence in purely irrotational and solenoidal systems and attracts to stable fixed points in general multi-agent systems.
Policy gradient methods find Nash equilibrium in noisy games.
problem Finding Nash equilibrium in noisy games.
method Policy gradient methods with noise added.
result Policy gradient methods converge to Nash equilibrium in noisy games.
BBVI with STL converges geometrically under perfect specification, with quadratic variance bound.
problem Convergence rate of BBVI with STL estimator.
method Proved geometric convergence rate with quadratic variance bound for BBVI with STL estimator.
result BBVI with STL converges geometrically under perfect variational family specification.
Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coo…