This work establishes uniform convergence of subdifferentials in stochastic optimization.
problem Understanding how empirical stationary points approximate population ones in nonsmooth, nonconvex stochastic optimization.
method Reduction principle for weakly convex stochastic objectives, focusing on subgradient convergence.
result Sharp uniform convergence rates for subdifferential mappings in stochastic convex-composite optimization.
Counterexamples show failure of uniform laws of large numbers for subdifferentials.
problem Failure of uniform laws of large numbers for subdifferentials under natural assumptions.
method Univariate and bivariate random Lipschitz and convex functions with smooth pieces.
result Counterexamples demonstrate failure of uniform laws of large numbers for subdifferentials.
Paper explores subdifferential chain rules for matrix factorization and related machine learning models.
problem Clarke subdifferential chain rules for matrix factorization and factorization machines.
method Analyzes conditions for subdifferential chain rules to hold, especially for overparameterized models.
result Subdifferential chain rules hold for matrix factorization and factorization machines under certain conditions.
Study on tensor nuclear norm's decomposability and subdifferential.
problem Understanding tensor nuclear norm in higher-order tensors.
method Showed decomposability over specific subspaces, derived subdifferential inclusions, and studied subgradients.
result Established the statistical performance of tensor robust principal component analysis.
The paper tackles finding stationary points in stochastic convex optimization problems.
problem Finding stationary points for stochastic convex optimization problems.
method The approach relies on dimension theory to decompose the graph of the subdifferential of a convex function, showing how stochastic sampling preserves 'pieces' of these graphs, and allowing effective application of proximal-point-like methods.
result The paper provides convergence guarantees for finding stationary points in stochastic convex optimization problems.
We investigate the notion of H-subdifferential and H-normal map of a function on the Heisenberg group, based on its sub-Riemannian structure. In particular, a characterization of the convexity of a function is given via the nonemptiness of the H-subdifferential at every point.
The paper proves functions with specific Taylor expansions have null image sets.
problem Functions with certain Taylor expansions and subdifferentials.
method Proving functions with specific Taylor expansions have null image sets.
result The image of the set of critical points with specified Taylor expansions and subdifferentials is a Lebesgue-null set.
The paper defines subdifferentials on Hadamard manifolds and identifies conditions for Fenchel conjugate equality.
problem Understanding convex analysis on Riemannian manifolds.
method Using Busemann functions to define subdifferentials and investigate Fenchel conjugate equality.
result Identifies conditions for equality in the Fenchel-Young inequality on Hadamard manifolds.
Simplified GMF functions for solving matrix optimization problems.
problem Matrix optimization problems, especially inverse problems, regularization, and learning.
method Simplified support function and subdifferential representations for GMF functions.
result Ready computation of geometric objects previously unavailable.
New framework for studying eigenvalue functionals of metrics.
problem Understanding critical points of eigenvalue functionals.
method Clarke subdifferential theory to unify previous research.
result Unified understanding of critical metrics and new examples.
Mirror flows converge to a limiting flow with a convex potential.
problem Incremental learning in mirror flows
method Rescaled trajectories converge to a limiting mirror flow
result Primal variable minimizes the loss over a time-dependent hypothesis set
New algorithms optimize spectral risk measures, improving interpolation between average and worst-case performance.
problem Optimizing spectral risk measures for learning systems.
method Developed stochastic algorithms to optimize spectral risk measures by characterizing their subdifferential and addressing challenges like biasedness of subgradient estimates and non-smoothness.
result Our approach outperforms out-of-the-box stochastic subgradient and dual averaging methods in optimizing spectral risk measures.
Random convex analysis tackles problems in random environments.
problem Dealing with problems in random environments like conditional convex risk measures.
method Developing random convex analysis over random locally convex modules, establishing inferior limit behavior, continuity, subdifferentiability, and approximating ε-subdifferentials.
result Established relationships among subdifferentiability, Gâteaux-differentiability, and Fréchet-differentiability for proper L0-convex functions. Screening rules help identify active sets in optimization problems.
problem Identifying active sets in optimization problems.
method Screening rules based on subdifferential sets and optimality conditions.
result The number of iterations needed depends only on the convergence rate.
Characterizes infinite harmonic maps using 1-currents.
problem Defines critical points of a non-differentiable functional.
method Uses subdifferential and geometric condition in terms of 1-currents.
result Geometric condition equivalent to criticality in terms of 1-currents.
We establish some perturbed minimization principles, and we develop a theory of subdifferential calculus, for functions defined on Riemannian manifolds. Then we apply these results to show existence and uniqueness of viscosity solutions to Hamilton-Jacobi equations defined on Riemannian manifolds.
Study proves convergence of subgradients for optimal transport-based objectives.
problem Ensuring statistical consistency and optimization stability in transport-based models.
method Proves graphical convergence of subdifferentials to the subdifferential of the population objective.
result Standard subgradient methods consistently approach stationary points of the population-level problem.
We propose a new class of convex penalty functions, called \emph{variational Gram functions} (VGFs), that can promote pairwise relations, such as orthogonality, among a set of vectors in a vector space. These functions can serve as regularizers in convex optimization problems arising from hierarchical classification, m…
The concept of subdifferentiability is studied in the context of C1 Finsler manifolds (modeled on a Banach space with a Lipschitz C1 bump function). A class of Hamilton-Jacobi equations defined on C1 Finsler manifolds is studied and several results related to the existence and uniqueness of viscosity solutions…
SGD avoids critical points on weakly convex functions.
problem Non-convergence of SGD to critical points on specific manifolds.
method Stochastic subgradient descent, Verdier stratification, angle condition.
result SGD converges to local minimizers on weakly convex functions.
Given a real-valued function defined on the Heisenberg group, we provide a definition of abstract convexity and Fenchel transform that takes into account the sub-Riemannian structure of the group. In our main result, we prove that, likewise the Euclidean case, a convex function can be characterized via its iterated Fen…
New examples of sub-Riemannian structures satisfying Minimizing Sard conjecture found.
problem Finding complete sub-Riemannian structures satisfying the Minimizing Sard conjecture.
method Techniques from nonsmooth analysis and geometric measure theory.
result Complete sub-Riemannian structures associated with distributions of co-rank 2 or generic distributions of rank ≥ 2 satisfy the Minimizing Sard conjecture.
The subdifferential of convex functions of the singular spectrum of real matrices has been widely studied in matrix analysis, optimization and automatic control theory. Convex analysis and optimization over spaces of tensors is now gaining much interest due to its potential applications to signal processing, statistics…
Study currents from semi-convex functions, apply to Hessian measures.
problem Understanding currents from semi-convex functions.
method Analyze integer multiplicity rectifiable currents from subgradient graphs of semi-convex functions.
result Weak continuity theorem for currents with pointwise convergence.
We introduce a proximal subdifferential and develop a calculus for nonsmooth functions defined on any Riemannian manifold M. We give several applications of this theory, concerning: 1) differentiability and geometrical properties of the distance function to a closed subset C of M; 2) solvability and implicit func…
Unified framework for pattern recovery in penalized and thresholded estimation.
problem Pattern recovery in penalized and thresholded estimation methods.
method Defining a novel pattern notion based on subdifferentials, introducing accessibility and noiseless recovery conditions.
result Unified and extended conditions for pattern recovery in a broad class of penalized estimators.
Risk measures are linked to probability structures, and a maximal domain is constructed.
problem Linking risk measures to probability structures and defining a maximal domain.
method Constructing a maximal domain respecting ambiguity and discussing properties.
result A meaningful underlying probability structure is implied by risk measures.
A new screening rule improves SLOPE efficiency for high-dimensional data.
problem Efficiently selecting relevant predictors in high-dimensional data.
method Developed a screening rule for SLOPE based on its subdifferential.
result The screening rule improves SLOPE's performance significantly in high-dimensional settings.
We propose an approach to multivariate nonparametric regression that generalizes reduced rank regression for linear models. An additive model is estimated for each dimension of a q-dimensional response, with a shared p-dimensional predictor variable. To control the complexity of the model, we employ a functional fo…
In this paper we propose a novel gradient algorithm to learn a policy from an expert's observed behavior assuming that the expert behaves optimally with respect to some unknown reward function of a Markovian Decision Problem. The algorithm's aim is to find a reward function such that the resulting optimal policy matche…
We consider the problem of estimating an unknown signal x0 from noisy linear observations y=Ax0+z∈Rm. In many practical instances, x0 has a certain structure that can be captured by a structure inducing convex function f(⋅). For example, ℓ1 norm can be used to encourage a sparse solution. T…
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.
Generalizes Fenchel conjugation to nonlinear functions on arbitrary sets.
problem Extending Fenchel conjugation to functions on arbitrary sets without structure.
method Replacing linear test functions with nonlinear ones, investigating properties including biconjugation.
result Derived further results on smooth manifolds and Lie groups, relating to convexity.
Study shows convergence of stochastic gradient method for unregularized Wasserstein optimization.
problem Wasserstein distributionally robust optimization under potential distribution shifts.
method Regularized approximation with stochastic gradient methods, convergence analysis.
result Stochastic gradient method converges to subgradients of unregularized objective as regularization vanishes.
Given a real-valued function c defined on the cartesian product of a generic Carnot group $\G$ and the first layer V1 of its Lie algebra, we introduce a notion of c horizontal convex (c H-convex) function on $\G$ as the supremum of a suitable family of affine functions; this family is defined pointwisely, and …
Adaptive learning method for stochastic programs with latent uncertainty.
problem Stochastic programming problems with implicitly decision-dependent uncertainty.
method Adaptive learning-based surrogate method integrating simulation and statistical estimates.
result Established non-asymptotic convergence rate analysis for enhanced stability and efficiency.
This work shows how to compute subderivatives efficiently without errors.
problem Inefficient and incorrect computation of subderivatives in ML libraries.
method Developed a method to compute provably correct generalized subderivatives at a cost close to the function itself.
result Provable correct generalized subderivatives can be computed at a cost within a factor of 6 of the function itself.
DFR reduces the computational cost of sparse-group lasso and adaptive sparse-group lasso.
problem Sparse-group lasso's computational expense and need for tuning.
method Dual Feature Reduction (DFR) using strong screening rules and dual norms.
result DFR drastically reduces computational cost without affecting solution optimality.
Study on portfolio optimization and risk analysis, proving non-uniqueness and suggesting a method to resolve it.
problem Non-uniqueness in solution of portfolio optimization and risk analysis problems.
method Proof of non-uniqueness, introduction of Stainer point as a unique subgradient.
result Identification of a unique 'special' subgradient to resolve non-uniqueness in portfolio optimization and risk analysis.
The study analyzes robustness of estimators in linear models with adversarial errors.
problem Analyzing robustness of estimators in linear models with adversarial errors.
method Develops a general theory for minimum norm interpolating estimators and RERM in linear models without conditions on errors.
result Quantitative bound for the prediction error relating it to Rademacher complexity, norm of minimum norm interpolator of errors, and subdifferential size.
We extend the well-known BFGS quasi-Newton method and its memory-limited variant LBFGS to the optimization of nonsmooth convex objectives. This is done in a rigorous fashion by generalizing three components of BFGS to subdifferentials: the local quadratic model, the identification of a descent direction, and the Wolfe …
We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corrup…
DCCNNs reduce computational overhead and ambiguity in convolutional neural networks.
problem Reducing computational overhead and ambiguity in convolutional neural networks.
method Introducing a primal learning problem and constructing a dual convex training program, using Fenchel conjugates and Karush-Kuhn-Tucker conditions.
result Eliminates ambiguity and reduces computational overhead in constructing a large kernel matrix.
The abstract discusses convergence properties of Lipschitz functions and sets defined by equations.
problem Convergence of Lipschitz functions and sets defined by equations.
method Painlevé-Kuratowski convergence applied to Lipschitz functions and sets defined by equations.
result Generalizations and reverses of classical theorems on convergence of functions and sets.
Sign-RIP improves robust low-rank matrix recovery by preserving norms even with corrupted measurements.
problem Robust low-rank matrix recovery in the presence of corrupted measurements.
method Proposed Sign-RIP, a robust restricted isometry property.
result Sign-RIP guarantees uniform convergence of subdifferentials in robust low-rank matrix recovery.
A fast sketching algorithm solves regularized least squares problems efficiently.
problem Solving large-scale optimization problems with convex or nonconvex regularization.
method Sketching for Regularized Optimization (SRO) algorithm that generates a sketch of the original data matrix and solves the sketched problem.
result General theoretical results for the approximation error between the original and sketched problems, including minimax rates for sparse signal estimation.
The paper describes flows of MMD functionals with distance kernel and quantile functions.
problem Wasserstein gradient flows of MMD functionals with negative distance kernel.
method Characterization via Cauchy problem on L2(0,1), solution via subdifferential construction. result Flow invariance and smoothing properties on subsets of C(0,1), absolute continuity of initial measures. In this paper we study general Schatten-p quasi-norm (SPQN) regularized matrix minimization problems. In particular, we first introduce a class of first-order stationary points for them, and show that the first-order stationary points introduced in [11] for an SPQN regularized vector minimization problem are equiva…