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…
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 “restricted strong convexity”
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.
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…
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…
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.
In this paper, we consider stochastic dual coordinate (SDCA) {\em without} strongly convex assumption or convex assumption. We show that SDCA converges linearly under mild conditions termed restricted strong convexity. This covers a wide array of popular statistical models including Lasso, group Lasso, and logistic reg…
Paper proves PI consensus algorithm converges exponentially under restricted secant inequality.
problem Proving convergence of PI consensus algorithm without convexity.
method Lyapunov theory, restricted secant inequality, rate-matching discretization, local pre-conditioning.
result Exponential convergence of PI consensus algorithm for non-convex functions.
Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraintstat.ML
We consider forward-backward greedy algorithms for solving sparse feature selection problems with general convex smooth functions. A state-of-the-art greedy method, the Forward-Backward greedy algorithm (FoBa-obj) requires to solve a large number of optimization problems, thus it is not scalable for large-size problems…
We introduce scattering-symplectic manifolds, manifolds with a type of minimally degenerate Poisson structure that is not too restrictive so as to have a large class of examples, yet restrictive enough for standard Poisson invariants to be computable. This paper will demonstrate the potential of the scattering symplect…
Convergence rate of Bayesian tensor estimator: Optimal rate without restricted strong convexitystat.ML
In this paper, we investigate the statistical convergence rate of a Bayesian low-rank tensor estimator. Our problem setting is the regression problem where a tensor structure underlying the data is estimated. This problem setting occurs in many practical applications, such as collaborative filtering, multi-task learnin…
The dueling bandit is a learning framework wherein the feedback information in the learning process is restricted to a noisy comparison between a pair of actions. In this research, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and …
Strong convergence of the thresholding scheme for the mean curvature flow of mean convex setsmath.AP
Study shows thresholding scheme converges for mean curvature flow of convex sets.
problem Analyzing convergence of thresholding scheme for mean curvature flow.
method Time discretization using Merriman, Bence and Osher's scheme, focusing on two-phase mean convex settings.
result Time-integrated energy of approximation converges to limit's energy in minimizing movements interpretation.
This paper advances FL algorithms for composite optimization and statistical recovery.
problem Federated learning optimization and statistical recovery in composite settings.
method Proposes Fast Federated Dual Averaging for strongly convex and smooth loss, and Multi-stage Federated Dual Averaging for restricted strongly convex and smooth loss.
result Establishes state-of-the-art iteration and communication complexity, and high probability complexity bound with linear speedup.
We connect high-dimensional subset selection and submodular maximization. Our results extend the work of Das and Kempe (2011) from the setting of linear regression to arbitrary objective functions. For greedy feature selection, this connection allows us to obtain strong multiplicative performance bounds on several meth…
We provide new approximation guarantees for greedy low rank matrix estimation under standard assumptions of restricted strong convexity and smoothness. Our novel analysis also uncovers previously unknown connections between the low rank estimation and combinatorial optimization, so much so that our bounds are reminisce…
Statistical Convergence Rates of Optimal Transport Map Estimation between General Distributionsmath.ST
The paper improves OT map estimation rates without strict assumptions.
problem Estimating optimal transport maps under practical conditions.
method Developed new convergence rates and scalable algorithms.
result Improved convergence rates for OT map estimation without restrictive assumptions.
Study risk bounds for distributed ERM with general loss functions and hypothesis spaces.
problem Limited theoretical analysis for distributed ERM with general loss functions and hypothesis spaces.
method Derive tight risk bounds under assumptions on hypothesis space and loss function.
result Developed more general risk bound for distributed ERM without strong convexity restriction.
Frank-Wolfe algorithm (FW) and its variants have gained a surge of interests in machine learning community due to its projection-free property. Recently people have reduced the gradient evaluation complexity of FW algorithm to for the smooth and strongly convex objective. This complexity result is esp…
The study explores convex unions and completions in simplicial pseudomanifolds, revealing unexpected behavior.
problem Understanding the behavior of convex unions in simplicial pseudomanifolds.
method Generalization to simplicial pseudomanifolds, considering PL homeomorphisms and edge subdivisions.
result Unexpected behavior in convex unions and completions, including empty contraction spaces and large/small contraction spaces.
ARHT algorithm improves sparsity guarantees in convex optimization.
problem Optimizing convex functions with sparsity constraints.
method Adaptively Regularized Hard Thresholding (ARHT) algorithm.
result ARHT achieves sparsity bound of γ=O(κ), matching theoretical limits.
We study how the existence of a negatively pinched Kähler metric on a domain in complex Euclidean space restricts the geometry of its boundary. In particular, we show that if a convex domain admits a complete Kähler metric, with pinched negative holomorphic bisectional curvature outside a compact set, then the boundary…
New method improves optimization and DP in FL.
problem Combining strong DP and optimization in FL.
method Combining clipping, momentum, and error feedback.
result Optimal convergence rate and near optimal DP guarantees.
Characterizes symplectic rational homology ball fillings of Seifert fibered spaces.
problem Understanding which Seifert fibered spaces can be boundaries of symplectic rational homology balls.
method Analyzes convex boundaries and Lagrangian disk fillings of Legendrian knots.
result Strong restrictions on which Seifert fibered spaces can bound symplectic rational homology balls.
We consider the class of optimization problems arising from computationally intensive L1-regularized M-estimators, where the function or gradient values are very expensive to compute. A particular instance of interest is the L1-regularized MLE for learning Conditional Random Fields (CRFs), which are a popular class of …
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…
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.
Algorithm samples from composite log-concave distributions using gradient evaluations and restricted Gaussian oracles.
problem Sampling from composite log-concave distributions with limited gradient evaluations.
method Proximal gradient algorithm with RGO for and strong/strongly convex conditions for .
result Achieves error in total variation distance in iterations.
We propose a generic framework based on a new stochastic variance-reduced gradient descent algorithm for accelerating nonconvex low-rank matrix recovery. Starting from an appropriate initial estimator, our proposed algorithm performs projected gradient descent based on a novel semi-stochastic gradient specifically desi…
A new algorithm estimates sparse gradients on graphs with improved risk bounds.
problem Estimating sparse gradients on graph-structured data.
method Tree-Projected Gradient Descent algorithm for gradient-sparse parameters.
result Achieves risk bound of .
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.
Active-set algorithm improves Cox regression for shape-restricted covariates.
problem Improving Cox regression for shape-restricted covariates.
method Shape-restricted inference using active-set optimization for spline basis expansion.
result Active-set algorithm produces accurate linear covariate effect estimates.
In this essay, we study the sufficient and necessary conditions for a Randers metrc to be of constant Ricci curvature without the restriction of strong convexity (regularity). The classification result for the case is provided, which is similar to the famous Bao-Robles-Shen's result for strongly convex Rand…
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.
Sparse regression models are increasingly prevalent due to their ease of interpretability and superior out-of-sample performance. However, the exact model of sparse regression with an constraint restricting the support of the estimators is a challenging (\NP-hard) non-convex optimization problem. In this paper…
New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.
problem Sampling uniformly from convex bodies efficiently.
method Markov chain Monte Carlo with proximal sampler and restricted Gaussian oracle.
result Efficient implementation of RGO for uniform sampling on convex bodies.
Paper relaxes SGD privacy and generalization guarantees for non-smooth convex losses.
problem Privacy and generalization in SGD for non-smooth convex losses.
method Relaxes Lipschitz and strong smoothness assumptions to Hölder smoothness, proving -DP and optimal excess risk.
result Noisy SGD with -Hölder smooth losses achieves optimal excess risk with linear gradient complexity for .
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…
A new line search rule improves support recovery in high-dimensional data.
problem Support recovery in high-dimensional data analysis with penalty.
method Data-driven line search rule for adaptive step size determination.
result Proves error bound without restrictions on cost functional.
Estimation in generalized linear models (GLM) is complicated by the presence of constraints. One can handle constraints by maximizing a penalized log-likelihood. Penalties such as the lasso are effective in high dimensions, but often lead to unwanted shrinkage. This paper explores instead penalizing the squared distanc…
We consider a global, nonlinear version of the Whitney extension problem for manifold-valued smooth functions on closed domains , with non-smooth boundary, in possibly non-compact manifolds. Assuming is a submanifold with corners, or is compact and locally convex with rough boundary, we prove that the restrictio…
Short proof of Strong Haken Theorem for 3-manifolds.
problem Proving Scharlemann's Strong Haken Theorem for 3-manifolds.
method Short proof using sphere complexes.
result Short proof of Scharlemann's Strong Haken Theorem.
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.
One of the mysteries in the success of neural networks is randomly initialized first order methods like gradient descent can achieve zero training loss even though the objective function is non-convex and non-smooth. This paper demystifies this surprising phenomenon for two-layer fully connected ReLU activated neural n…
We provide a framework to approximate the 2-Wasserstein distance and the optimal transport map, amenable to efficient training as well as statistical and geometric analysis. With the quadratic cost and considering the Kantorovich dual form of the optimal transportation problem, the Brenier theorem states that the optim…
Paper proposes sparse classification method for high-dimensional data.
problem Sparse classification in high-dimensional data with positive-confidence samples.
method Developed a novel sparse-penalization framework using L1, SCAD, and MCP penalties for convex and non-convex shrinkage.
result Proved near minimax-optimal sparse recovery rates under Restricted Strong Convexity condition.
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 SAGA algorithm with decreasing step for stochastic optimization.
problem Analysis of SAGA algorithm and its convergence properties.
method Introducing a new λ-SAGA algorithm with decreasing step, investigating convergence and establishing a central limit theorem.
result Established convergence and central limit theorem for λ-SAGA algorithm.