arXiv research

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 $C^0$-continuity of the evo…

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…

PF-LaCG removes the need for knowing smoothness and strong convexity parameters for locally accelerated CG.

Strongly convex bodies can be approximated by smooth ones.

Kernel k-Means algorithm improves clustering of non-linear data.

The study explores convex unions and completions in simplicial pseudomanifolds, revealing unexpected behavior.

Global convergence for robust regression problems via IRLS with enhancements.

New FL framework handles non-i.i.d data without strong assumptions.

Strong geodesic convex function and strong monotone vector field of order $m$ on Riemannian manifolds have been established. A characterization of strong geodesic convex function of order $m$ for the continuously differentiable functions has been discussed. The relation between the solution of a new variational inequal…

New algorithms optimize decentralized convex optimization with near optimal communication and computation.

FastAdaBelief improves convergence rate of AdaBelief by exploiting strong convexity.

We identify a condition for regularity of optimal transport maps that requires only three derivatives of the cost function, for measures given by densities that are only bounded above and below. This new condition is equivalent to the weak Ma-Trudinger-Wang condition when the cost is $C^4$. Moreover, we only require (n…

Over-parameterization makes optimization easier for simple neural networks, even with minor extra neurons.

We establish that over a C^{2,1} manifold the exponential map of any Lipschitz connection or spray determines a local Lipeomophism and that, furthermore, reversible convex normal neighborhoods do exist. To that end we use the method of Picard-Lindelof approximation to prove the strong differentiability of the exponenti…

This paper shows how to learn variational inequalities fast with strong monotonicity.

Graphically discrete groups have strong rigidity properties.

Let $U\subseteq\mathbb{R}^{n}$ be open and convex. We show that every (not necessarily Lipschitz or strongly) convex function $f:U\to\mathbb{R}$ can be approximated by real analytic convex functions, uniformly on all of $U$. In doing so we provide a technique which transfers results on uniform approximation on bounded …

STL-SGD accelerates Local SGD by gradually increasing communication periods.

Estimate collapsibility of causal effects in CPDAGs via strong d-convex hulls.

We consider the problem of decentralized consensus optimization, where the sum of $n$ smooth and strongly convex functions are minimized over $n$ distributed agents that form a connected network. In particular, we consider the case that the communicated local decision variables among nodes are quantized in order to all…

Over-the-air computation (AirComp) shows great promise to support fast data fusion in Internet-of-Things (IoT) networks. AirComp typically computes desired functions of distributed sensing data by exploiting superposed data transmission in multiple access channels. To overcome its reliance on channel station informatio…

This paper is concerned with the problem of determining whether a projective-equivalence class of sprays is the geodesic class of a Finsler function. We address both the local and the global aspects of this problem. We present our results entirely in terms of a multiplier, that is, a type (0,2) tensor field along the t…

In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to $\mathit{local~strong~convexity}$ in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation function…

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 $\ell_1$ regularization, linear r…

New algorithms improve distributed optimization under specific conditions.

Harmonic functions on compact symmetric spaces exhibit strong convexity properties.

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…

New framework explains why nonconvex methods work well in low-rank matrix estimation.

This work proposes ACTC for adaptive distributed learning under communication constraints.

Totally geodesic submanifolds in convex cores are properly immersed and have finite volume.

Traditional nearest points methods use all the samples in an image set to construct a single convex or affine hull model for classification. However, strong artificial features and noisy data may be generated from combinations of training samples when significant intra-class variations and/or noise occur in the image s…

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…

Yau's Affine Normal Descent optimizes smooth unconstrained problems with geometrically adapted directions.

A new algorithm solves signed Fréchet regression on manifolds with bounded curvature.

We show that for a very general class of curvature functions defined in the positive cone, the problem of finding a complete strictly locally convex hypersurface in $H^n+1$ satisfying $f(κ)=σ\in(0, 1)$ with a prescribed asymptotic boundary $Γ$ at infinity has at least one smooth solution with uniformly bounded hyperbol…

New method improves optimization and DP in FL.

This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for which both projection into the constrained domain and a linear optimization under the inequality constraint are time-consuming, which render …

Optimal control in changing systems without strong convexity assumptions.

Learning to make decisions from observed data in dynamic environments remains a problem of fundamental importance in a number of fields, from artificial intelligence and robotics, to medicine and finance. This paper concerns the problem of learning control policies for unknown linear dynamical systems so as to maximize…

New guarantees for Group LASSO in sparse convex optimization.

Epoch-GDA achieves optimal convergence rate for SCSC min-max problems.

Recent studies have illustrated that stochastic gradient Markov Chain Monte Carlo techniques have a strong potential in non-convex optimization, where local and global convergence guarantees can be shown under certain conditions. By building up on this recent theory, in this study, we develop an asynchronous-parallel s…

Given a loss function $F:\mathcal{X} \rightarrow \R^+$ that can be written as the sum of losses over a large set of inputs $a_1,\ldots, a_n$, it is often desirable to approximate $F$ by subsampling the input points. Strong theoretical guarantees require taking into account the importance of each point, measured by how …

Improved algorithm reduces communication rounds for distributed online learning.

This paper considers the recovery of a rank $r$ positive semidefinite matrix $X X^T\in\mathbb{R}^{n\times n}$ from $m$ scalar measurements of the form $y_i := a_i^T X X^T a_i$ (i.e., quadratic measurements of $X$). Such problems arise in a variety of applications, including covariance sketching of high-dimensional data…

New algorithm solves saddle point problems in Banach spaces.

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…

Flow deforms locally convex curves to curves of constant k-order width.