We propose a set of convex low rank inducing norms for a coupled matrices and tensors (hereafter coupled tensors), which shares information between matrices and tensors through common modes. More specifically, we propose a mixture of the overlapped trace norm and the latent norms with the matrix trace norm, and then, w…
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.
169,181 papers · 148 categories
Trend · papers per month
48 results for “convex norms”
New framework for private convex optimization in arbitrary norms.
problem Private optimization of convex functions in non-Euclidean settings.
method Regularized exponential mechanism based on localization tools from convex geometry.
result First optimal privacy-utility tradeoffs for norms and Schatten- norms.
Study on Santaló point for convex bodies in normed spaces.
problem Exploring Santaló point for convex bodies in normed spaces.
method Existence and uniqueness proof for norms, dual Santaló point for smooth curved unit balls.
result Existence and uniqueness of Santaló point for convex bodies in normed spaces.
Optimization problems with rank constraints appear in many diverse fields such as control, machine learning and image analysis. Since the rank constraint is non-convex, these problems are often approximately solved via convex relaxations. Nuclear norm regularization is the prevailing convexifying technique for dealing …
Extends metric to Margulis spacetimes for convex properties.
problem No specific problem stated; extends metric.
method Extends Thurston's asymmetric metric to Margulis spacetimes and proves convex properties.
result Established convex properties of the extended metric.
A result of Bangert states that the stable norm associated to any Riemannian metric on the -torus is strictly convex. We demonstrate that the space of stable norms associated to metrics on forms a proper dense subset of the space of strictly convex norms on . In particular, given a strictly convex …
New algorithms reduce regret for convex bandits with small comparator norms.
problem Optimizing in bandit convex optimization with varying comparator norms.
method Developed algorithms using techniques from full-information setting and new gradient estimators.
result Regret bounds are small when comparator norm is small.
The problem of low-rank approximation with convex constraints, which appears in data analysis, system identification, model order reduction, low-order controller design and low-complexity modelling is considered. Given a matrix, the objective is to find a low-rank approximation that meets rank and convex constraints, w…
We suggest using the max-norm as a convex surrogate constraint for clustering. We show how this yields a better exact cluster recovery guarantee than previously suggested nuclear-norm relaxation, and study the effectiveness of our method, and other related convex relaxations, compared to other clustering approaches.
Most learning methods with rank or sparsity constraints use convex relaxations, which lead to optimization with the nuclear norm or the -norm. However, several important learning applications cannot benefit from this approach as they feature these convex norms as constraints in addition to the non-convex rank a…
New method improves signal estimation by convexifying -norm constraints.
problem Signal estimation with sparsity and smoothness priors.
method Iterative convex conic quadratic relaxations exploiting -norm and smoothness terms.
result Significantly better estimators than -norm approaches and interpretable parameters.
This work simplifies proximal mapping for low-rank norms.
problem Efficient computation of proximal mappings for low-rank inducing norms.
method Reduces proximal mapping to nested binary search, solving simpler problems analytically.
result Simplified computation of proximal mappings for various norms.
The Schatten- norm () has been widely used to replace the nuclear norm for better approximating the rank function. However, existing methods are either 1) not scalable for large scale problems due to relying on singular value decomposition (SVD) in every iteration, or 2) specific to some values, e.g., $1/…
Based on a new atomic norm, we propose a new convex formulation for sparse matrix factorization problems in which the number of nonzero elements of the factors is assumed fixed and known. The formulation counts sparse PCA with multiple factors, subspace clustering and low-rank sparse bilinear regression as potential ap…
Sparse methods for supervised learning aim at finding good linear predictors from as few variables as possible, i.e., with small cardinality of their supports. This combinatorial selection problem is often turned into a convex optimization problem by replacing the cardinality function by its convex envelope (tightest c…
We show that the spectral norm of a random tensor (or higher-order array) scales as under some sub-Gaussian assumption on the entries. The proof is based on a covering number argument. Since the spectral norm is dual to the tensor…
Convexity proven for sums of angles of unitary paths.
problem Proving convexity of sums of eigenvalues of unitary matrices.
method Analyzing paths of unitary matrices and their angles, using operator norms.
result Sum of first m angles of unitary path is convex.
New methods for estimating panel regression models with interactive fixed effects.
problem Estimating panel regression models with interactive fixed effects.
method Nuclear norm regularization and minimization of convex objective functions.
result Consistent estimators with computational advantages over least squares.
Paper proposes equivalent Lipschitz surrogates for zero-norm and rank optimization problems.
problem Optimization problems involving zero-norm and rank functions.
method Reformulate as MPECs, use global exact penalty, eliminate dual variable to get surrogates.
result Obtained equivalent Lipschitz surrogates for zero-norm and rank optimization problems.
Improved Frank-Wolfe algorithm solves convex trace-norm ball problems.
problem Optimizing convex functions over trace-norm balls.
method Rank-k variant of Frank-Wolfe algorithm using top-k singular-vector computation.
result Linear convergence rate for smooth and strongly convex objectives with rank-limited solutions.
Paper solves TRPCA problem for tensor data with new tensor nuclear norm.
problem Exact recovery of tensor low-rank and sparse components.
method Introduces tensor-tensor product and new tensor nuclear norm to solve TRPCA.
result The new tensor nuclear norm guarantees exact recovery of tensor data.
Optimizes exp-concave losses with a new risk bound.
problem Optimizing exp-concave losses with stochastic convex optimization.
method Empirical Risk Minimization with a unified geometric assumption and local norms.
result Provides an excess risk bound.
Paper proposes efficient algorithm for non-convex rank minimization.
problem Efficiently solving rank minimization problems with non-convex penalties.
method Iterative Shrinkage-Thresholding Algorithm (ISTA) for non-convex weighted and reweighted nuclear norm.
result Proves convergence to critical point with rate and outperforms state-of-the-art methods.
Study normal curves in sub-Finsler Lie groups with specific norms, focusing on branching and face stability.
problem Analyzing normal curves in sub-Finsler Lie groups with different norms.
method Using tools from convex analysis, the Pontryagin Maximum Principle is revisited to express the normal equation as a differential inclusion involving the subdifferential of the dual norm.
result Normal curves in polyhedral norms have controls that locally take values in a single face of a sphere with respect to the norm.
We investigate the capacity, convexity and characterization of a general family of norm-constrained feed-forward networks.
Survey on geometry of co-Minkowski space and its affine deformations.
problem Understanding the geometry of co-Minkowski space and its affine deformations.
method Affine deformations of hyperbolic lattices acting on co-Minkowski space, convex core, mean hypersurface, asymmetric norm.
result Existence of a unique mean hypersurface and an asymmetric norm on the space of affine deformations.
New algorithms optimize convex functions with high-order derivatives.
problem Optimizing convex functions with high-order derivatives under various norms.
method Developed a non-Euclidean inexact accelerated proximal point method using an inexact uniformly convex regularizer.
result Showed nearly optimal algorithms for high dimensions in the black-box oracle model for -settings and all .
We consider the problem of recovering a low-rank tensor from its noisy observation. Previous work has shown a recovery guarantee with signal to noise ratio for recovering a th order rank one tensor of size by recursive unfolding. In this paper, we first improve…
Study examines convexity properties of harmonic functions on evolving hypersurfaces.
problem Investigate convexity of harmonic functions on evolving hypersurfaces.
method Consider compact level sets of smooth regular functions, derive a differential inequality for -norms of harmonic functions.
result Obtain a new differential inequality for -norms of harmonic functions over evolving hypersurfaces.
ResNets minimize circuit size for fitting data in HTMC regime.
problem Finding the simplest algorithm that fits data.
method Defining HTMC and ResNet norms to relate circuit size and function fitting.
result Minimizing ResNet norm is equivalent to finding a circuit with minimal nodes.
In this paper, we propose an unifying view of several recently proposed structured sparsity-inducing norms. We consider the situation of a model simultaneously (a) penalized by a set- function de ned on the support of the unknown parameter vector which represents prior knowledge on supports, and (b) regularized in Lp-n…
Paper introduces a new regret measure for online convex optimization with smooth losses.
problem Online convex optimization with smooth losses.
method Introduces a new regret measure that depends on the cumulative squared gradient norm.
result The regret can be arbitrarily sharper than existing measures when losses have vanishing curvature.
We study the stable norm on the first homology of a closed, non-orientable surface equipped with a Riemannian metric. We prove that in every conformal class there exists a metric whose stable norm is polyhedral. Furthermore the stable norm is never strictly convex if the first Betti number of the surface is greater tha…
Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone , a norm and a smooth convex function , we want either 1) to minimize the norm over the intersection of the cone and a level set of , or 2) to minimize over the…
We characterize the three-dimensional spaces admitting at least six or at least seven equidistant points. In particular, we show the existence of norms on admitting six equidistant points, which refutes a conjecture of Lawlor and Morgan (1994, Pacific J. Math \textbf{166}, 55--83), and gives the exist…
AdaGrad-Norm achieves linear convergence for certain functions.
problem Proving linear convergence for specific types of functions.
method Introducing RUIG, a measure of gradient balance; developing a two-stage framework.
result AdaGrad-Norm achieves linear convergence for certain functions.
New method turns optimization algorithms into uniformly stable learning algorithms for non-Euclidean norms.
problem Non-Euclidean norms in binary classification problems.
method Black-box reduction method using uniformly convex regularizers.
result Achieves optimal statistical risk bounds on excess risk for non-Euclidean norms.
The paper refines and generalizes worst-case law invariant convex risk measures.
problem Developing robust convex risk measures under uncertainty sets.
method Generalizing closed forms for worst-case law invariant convex risk measures with uncertainty sets based on norms and moment constraints.
result Explicit closed forms for convex risk measures are developed and assessed through numerical simulations.
Sum-of-norms clustering recovers mixtures of Gaussians even with infinite samples.
problem Recovering a mixture of Gaussians from a large number of samples.
method Sum-of-norms clustering with equal weights, convex optimization.
result Sum-of-norms clustering can recover mixtures of Gaussians even as the number of samples tends to infinity.
In recent years, the nuclear norm minimization (NNM) problem has been attracting much attention in computer vision and machine learning. The NNM problem is capitalized on its convexity and it can be solved efficiently. The standard nuclear norm regularizes all singular values equally, which is however not flexible enou…
This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g. sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of…
Develops exact convex optimization formulations for neural networks.
problem Training two-layer neural networks with rectified linear units.
method Uses semi-infinite duality and minimum norm regularization to develop exact convex optimization formulations.
result Shows equivalence of ReLU networks trained with weight decay to block penalized convex models.
The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancestat.ML
AdaGrad-Norm achieves optimal convergence rates for non-convex objectives without tuning.
problem Optimal convergence rates for non-convex, smooth objectives with adaptive step sizes.
method Adaptive SGD (AdaGrad-Norm) with self-tuning step sizes, analyzing under unbounded gradients and affine variance scaling.
result AdaGrad-Norm achieves order optimal convergence rate of $\mathcal{O}\left(\frac{\mathrm{poly}\log(T)}{\sqrt{T}}
ight)$ under optimal assumptions.
The paper extends inequalities for convex bodies to higher dimensions and various norms.
problem Extending inequalities for convex bodies to higher dimensions and various norms.
method Developed new operators and inequalities for higher-order norms.
result Established th-order isoperimetric inequalities.
Generalizes smoothness conditions for optimization methods.
problem Optimization under non-uniform smoothness conditions.
method Develops a new analysis technique for bounding gradients.
result Obtains convergence rates for gradient descent and Nesterov's method.
Exact partitioning of high-order planted models achieved through convex optimization.
problem Efficiently partitioning hypergraphs generated by high-order planted models.
method Solving a computationally efficient convex optimization problem with a tensor nuclear norm constraint.
result Exact recovery of true underlying cluster structures with high probability.
We discuss structured Schatten norms for tensor decomposition that includes two recently proposed norms ("overlapped" and "latent") for convex-optimization-based tensor decomposition, and connect tensor decomposition with wider literature on structured sparsity. Based on the properties of the structured Schatten norms,…
New curvature measures characterize non-convex Wulff shapes in normed spaces.
problem Characterizing non-convex sets with curvature measures.
method Extending curvature measures to non-convex and non-smooth sets in normed spaces.
result Finite unions of disjoint Wulff shapes are the only sets with proportional curvature measures.