Strong geodesic convex function and strong monotone vector field of order on Riemannian manifolds have been established. A characterization of strong geodesic convex function of order for the continuously differentiable functions has been discussed. The relation between the solution of a new variational inequal…
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 “strong convexity”
FastAdaBelief improves convergence rate of AdaBelief by exploiting strong convexity.
problem Improving convergence rate of AdaBelief without sacrificing generalization ability.
method Designing FastAdaBelief that adjusts step size considering strong convexity.
result Proves regret bound for FastAdaBelief.
Learning Variational Inequalities from Data: Fast Generalization Rates under Strong Monotonicitycs.LG
This paper shows how to learn variational inequalities fast with strong monotonicity.
problem Learning variational inequalities efficiently.
method Extending convex optimization techniques to variational inequalities with strong monotonicity.
result Fast generalization rates of for learning variational inequalities.
Estimate Collapsibility of Causal Effects in Completed Partial DAGs via Strong d-Convex Hullsstat.ML
Estimate collapsibility of causal effects in CPDAGs via strong d-convex hulls.
problem Estimate causal effects in CPDAGs.
method Use strong d-convex hulls to characterize minimal collapsible sets.
result Efficient algorithm for obtaining collapsible sets in DAGs and CPDAGs.
SAGA is a fast incremental gradient method on the finite sum problem and its effectiveness has been tested on a vast of applications. In this paper, we analyze SAGA on a class of non-strongly convex and non-convex statistical problem such as Lasso, group Lasso, Logistic regression with regularization, linear r…
Harmonic functions on compact symmetric spaces exhibit strong convexity properties.
problem Understanding the convexity of harmonic functions on compact symmetric spaces.
method Analyzing the nonnegativity of the Laplacian powers of harmonic functions.
result Harmonic functions on compact symmetric spaces have nonnegative Laplacian powers, demonstrating strong convexity.
We propose a projected semi-stochastic gradient descent method with mini-batch for improving both the theoretical complexity and practical performance of the general stochastic gradient descent method (SGD). We are able to prove linear convergence under weak strong convexity assumption. This requires no strong convexit…
Optimal control in changing systems without strong convexity assumptions.
problem Adversarial changes in convex costs for unknown linear systems.
method Non-convex lower confidence bounds and computationally-efficient regret minimization.
result Achieves -regret rate, optimal compared to best stabilizing controller.
New guarantees for Group LASSO in sparse convex optimization.
problem Sparse convex optimization with vector-valued features.
method Group LASSO regularization and analysis of gradient norms.
result Group LASSO selects the same features as Orthogonal Matching Pursuit.
Epoch-GDA achieves optimal convergence rate for SCSC min-max problems.
problem Solving stochastic min-max problems with strong convexity and strong concavity.
method Epoch-wise stochastic gradient descent ascent method (Epoch-GDA) without additional assumptions.
result Achieves the optimal rate of for the duality gap of general SCSC min-max problems.
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.
We show that an infinite dimensional Lie group in Milnor's sense has the strong Trotter property if it is locally -convex. This is a continuity condition imposed on the Lie group multiplication that generalizes the triangle inequality for locally convex vector spaces, and is equivalent to -continuity of the evo…
The versatility of exponential families, along with their attendant convexity properties, make them a popular and effective statistical model. A central issue is learning these models in high-dimensions, such as when there is some sparsity pattern of the optimal parameter. This work characterizes a certain strong conve…
We propose a DC proximal Newton algorithm for solving nonconvex regularized sparse learning problems in high dimensions. Our proposed algorithm integrates the proximal Newton algorithm with multi-stage convex relaxation based on the difference of convex (DC) programming, and enjoys both strong computational and statist…
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework an…
NAPP-ERM improves ERM with differential privacy guarantees by iteratively achieving target regularization and delivering strong convexity.
problem Over-regularization in privacy-preserving ERM approaches.
method Noise-Augmented Privacy-Preserving Empirical Risk Minimization (NAPP-ERM) with a dual-purpose l2 regularizer and privacy budget retrieval strategy.
result Mitigates over-regularization and achieves strong convexity through a single regularizer.
New findings on strong convexity in triangulations of convex polygons.
problem Understanding the structure of triangulations and their distances.
method Analyzing geodesic paths and flag triangulations in flip-graphs.
result Strong convexity properties of triangulations in convex polygons are not always preserved.
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 …
The Adam algorithm has become extremely popular for large-scale machine learning. Under convexity condition, it has been proved to enjoy a data-dependant regret bound where is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem…
Stochastic approximation (SA) is a classical approach for stochastic convex optimization. Previous studies have demonstrated that the convergence rate of SA can be improved by introducing either smoothness or strong convexity condition. In this paper, we make use of smoothness and strong convexity simultaneously to boo…
SVRG and its variants are among the state of art optimization algorithms for large scale machine learning problems. It is well known that SVRG converges linearly when the objective function is strongly convex. However this setup can be restrictive, and does not include several important formulations such as Lasso, grou…
Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to t…
RR algorithm improves convergence rate without strong convexity assumptions.
problem Minimizing finite-sum functions efficiently.
method Iterative gradient descent with data reshuffling, removing strong convexity assumptions.
result Improved convergence rate and variance for RR, matching lower bounds.
Boosts weak online learners to strong ones with sublinear regret.
problem Online learning agnostic setting without strong guarantees.
method Reduction to online convex optimization, boosting via marginally-better-than-trivial regret guarantees.
result First agnostic online boosting algorithm with sublinear regret.
On a Riemannian manifold, lower Ricci curvature bounds are known to be characterized by geodesic convexity properties of various entropies with respect to the Kantorovich-Rubinstein-Wasserstein square distance from optimal transportation. These notions also make sense in a (nonsmooth) metric measure setting, where they…
Boosting is a popular way to derive powerful learners from simpler hypothesis classes. Following previous work (Mason et al., 1999; Friedman, 2000) on general boosting frameworks, we analyze gradient-based descent algorithms for boosting with respect to any convex objective and introduce a new measure of weak learner p…
Unified convergence analysis of alpha-SVRG under strong convexity.
problem Analyzing the convergence of alpha-SVRG in strongly convex environments.
method Unified convergence rate expression for alpha-SVRG under fixed learning rate, demonstrating faster convergence than SGD and SVRG.
result alpha-SVRG has a faster convergence rate compared to SGD and SVRG under suitable choice of alpha.
New approach to convex hulls for low-rank problems.
problem Characterizing convex hulls for low-rank sets.
method Matrix perspective function and orthogonal projection matrices.
result Strong relaxations for various low-rank problems.
Paper proposes DC functions for better regularization of inverse problems with theoretical guarantees.
problem Improving regularization for ill-posed inverse problems.
method Introduces difference-of-convex (DC) functions and uses them with optimization algorithms like DCA and PSM.
result DC functions yield improved performance and theoretical guarantees compared to weakly convex functions.
New insights show NAG and FISTA converge linearly without knowing strong convexity modulus.
problem Understanding linear convergence of NAG and FISTA without strong convexity modulus knowledge.
method High-resolution ODE framework, dynamically adapting kinetic energy coefficient.
result NAG and FISTA demonstrate linear convergence without requiring strong convexity modulus knowledge.
Global convergence for robust regression problems via IRLS with enhancements.
problem Global convergence for robust regression problems.
method Augmentations to IRLS to ensure global recovery and improved robustness.
result Global recovery guarantees for robust regression problems, outperforming state-of-the-art algorithms.
Strongly convex bodies can be approximated by smooth ones.
problem Approximating strongly convex bodies with smooth ones.
method Using locally strongly convex bodies.
result Smooth approximations of strongly convex bodies exist and can be controlled in terms of Hausdorff distance.
PF-LaCG removes the need for knowing smoothness and strong convexity parameters for locally accelerated CG.
problem Locally accelerated CG requires knowledge of smoothness and strong convexity parameters.
method Parameter-Free Locally Accelerated CG (PF-LaCG) algorithm.
result PF-LaCG achieves local acceleration without requiring knowledge of smoothness and strong convexity parameters.
The paper explores volume product and slicing conjectures using convex body deformations.
problem Volume product and slicing conjectures in convex geometry.
method Study of variational aspects of volume product functional under projective deformations.
result Provides a proof of a theorem by Klartag and identifies critical convex bodies.
Kernel k-Means algorithm improves clustering of non-linear data.
problem Non-convexity of kernel k-Means objective function leads to local minima.
method Generalizes MM approach to solve non-convex problem in kernel and multi-kernel settings.
result Establishes strong consistency guarantees for Kernel Power k-Means.
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 …
Extends boosting to multiclass online agnostic classification.
problem Online multiclass classification with weak learners.
method Reduces multiclass online agnostic boosting to online convex optimization.
result First boosting algorithm for online agnostic multiclass classification.
In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original -dimensional variable to an -d…
New method simplifies checking consistency of differentiable loss functions.
problem Verifying consistency of differentiable loss functions is difficult.
method Developed a new approach called strong indirect elicitation (strong IE) to simplify checking consistency.
result Strong IE is equivalent to calibration for strongly convex, differentiable surrogates.
New methods solve complex optimization problems without strong convexity assumptions.
problem Complex bilevel optimization problems with minimax lower-level structures.
method Penalty-based first-order methods for bilevel minimax optimization.
result Achieves -KKT point with improved oracle complexity.
New DP algorithm improves privacy and efficiency for convex optimization.
problem Efficient, DP algorithms for convex optimization with strong excess risk bounds.
method Output perturbation for a broad class of tilted loss functions.
result Near optimal DP excess risk and runtime bounds for convex optimization.
New method uses momentum to converge in DC optimization with small batches.
problem Lack of convergence properties for stochastic difference-of-convex optimization with small batch sizes.
method Introduces momentum to enable convergence under standard assumptions for any batch size.
result Proves convergence of the algorithm under smoothness and bounded variance assumptions.
Study sharp inequalities for perimeter functionals in capillarity and convex cones.
problem Quantitative isoperimetric inequalities for perimeter functionals in capillarity and convex cones.
method Derivation of Fuglede-type estimates and application of selection principle.
result Sharp quantitative isoperimetric inequalities in strong and barycentric forms.
The proximal inertial gradient descent is efficient for the composite minimization and applicable for broad of machine learning problems. In this paper, we revisit the computational complexity of this algorithm and present other novel results, especially on the convergence rates of the objective function values. The no…
The main goal of this paper is to investigate under which conditions cash-subadditive convex dynamic risk measures are time-consistent. Proceeding as in Detlefsen and Scandolo \cite{detlef-scandolo} and inspired by their result, we give a dual representation of dynamic cash-subadditive convex risk measures (that can al…
In this paper we generalize the framework of the feasible descent method (FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent method (RC-FDM) framework. We show that the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, f…
The paper proves isometric embeddings for smooth manifolds.
problem Embedding smooth manifolds isometrically into Euclidean spaces.
method Nash-Kuiper's convex integration construction and gluing technique.
result Infinitely many global isometric embeddings into 2n-dimensional Euclidean space.
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.