Finding efficient and provable methods to solve non-convex optimization problems is an outstanding challenge in machine learning and optimization theory. A popular approach used to tackle non-convex problems is to use convex relaxation techniques to find a convex surrogate for the problem. Unfortunately, convex relaxat…
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 “convex function learning”
Faster algorithms solve convex function learning problems.
problem Approximating arbitrary convex functions in various learning tasks.
method 2-block ADMM method with closed-form block computations.
result Converges with for convex Lipschitz regression.
Extends DCP framework to Hadamard manifolds for geodesically convex functions.
problem Verifying convexity in nonlinear programs on Hadamard manifolds.
method Introduces Disciplined Geodesically Convex Programming (DGCP) framework, defining compositions and transformations for geodesically convex functions.
result Allows verification of geodesic convexity for a broader range of functions, including statistical estimators and matrix-valued optimization.
HyCNNs improve convex function learning and optimal transport.
problem Learning and optimizing convex functions efficiently.
method Combining Maxout networks and ICNNs to create a new neural architecture.
result HyCNNs require fewer parameters and outperform existing methods in convex tasks.
Paper introduces a new kernel model for PSD-valued functions with theoretical guarantees and applications.
problem Enforcing positive semi-definiteness (PSD) in function models with good performance and theoretical guarantees.
method Kernel sum-of-squares model for PSD-valued functions, extending previous models for non-negative scalar functions.
result The model constitutes a universal approximator of PSD functions and can represent any smooth and strongly convex function.
Regularized empirical risk minimization with constrained labels (in contrast to fixed labels) is a remarkably general abstraction of learning. For common loss and regularization functions, this optimization problem assumes the form of a mixed integer program (MIP) whose objective function is non-convex. In this form, t…
SGD converges to global minimum for certain non-convex functions.
problem Theoretical challenges in optimizing non-convex functions in machine learning.
method Perturbed SGD on a broad class of non-convex functions.
result SGD converges to global minimum for certain non-convex functions.
This paper studies quasar-convex functions to improve optimization methods.
problem Improving optimization methods for non-convex functions.
method Study of first order methods for quasar-convex functions.
result Proves complexity upper bounds similar to convex functions.
We introduce a novel algorithm for solving learning problems where both the loss function and the regularizer are non-convex but belong to the class of difference of convex (DC) functions. Our contribution is a new general purpose proximal Newton algorithm that is able to deal with such a situation. The algorithm consi…
First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functionscs.LG
First order methods can take extremely long to find global minima of non-convex functions.
problem Finding global minimizers of non-convex functions.
method Designing a family of non-convex functions and using statistical lower bounds for parameter estimation.
result First order methods can take exponential time to converge to a global minimizer.
Muon fails to converge on convex Lipschitz functions.
problem Understanding the convergence of Muon on convex and Lipschitz functions.
method Analyzing Muon's performance on convex and Lipschitz functions without error feedback.
result Muon does not converge on convex and Lipschitz functions, regardless of learning rate schedule.
To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existi…
In this paper, we present a novel and principled approach to learn the optimal transport between two distributions, from samples. Guided by the optimal transport theory, we learn the optimal Kantorovich potential which induces the optimal transport map. This involves learning two convex functions, by solving a novel mi…
CoNES optimizes blackbox functions using convex optimization and information geometry.
problem Optimizing high-dimensional blackbox functions efficiently.
method Formulated as a convex program that adapts evolutionary strategies gradient estimates.
result Vastly outperforms conventional blackbox optimization methods on benchmarks and MuJoCo tasks.
Learning with a {\it convex loss} function has been a dominating paradigm for many years. It remains an interesting question how non-convex loss functions help improve the generalization of learning with broad applicability. In this paper, we study a family of objective functions formed by truncating traditional loss f…
Set-functions appear in many areas of computer science and applied mathematics, such as machine learning, computer vision, operations research or electrical networks. Among these set-functions, submodular functions play an important role, similar to convex functions on vector spaces. In this tutorial, the theory of sub…
Study improves estimation of functions from noisy data using convex penalties.
problem Estimating functions from noisy point evaluations of linear operators.
method Tikhonov regularization with convex and -homogeneous penalty functionals.
result Derives concentration rates for regularized solutions in symmetric Bregman distance.
New algorithm for online learning in episodic MDPs with convex objectives.
problem Online episodic convex reinforcement learning.
method Online mirror descent algorithm with varying constraint sets and exploration bonus.
result Near-optimal regret bounds for online CURL without prior knowledge of transition function.
AGGLIO optimizes non-convex functions with local convexity guarantees.
problem Optimizing non-convex functions with local convexity.
method Stage-wise, graduated optimization technique for locally convex functions.
result Global convergence to the global optimum for non-convex and locally convex objectives.
We introduce a generic scheme to solve nonconvex optimization problems using gradient-based algorithms originally designed for minimizing convex functions. Even though these methods may originally require convexity to operate, the proposed approach allows one to use them on weakly convex objectives, which covers a larg…
This paper introduces Jensen, an easily extensible and scalable toolkit for production-level machine learning and convex optimization. Jensen implements a framework of convex (or loss) functions, convex optimization algorithms (including Gradient Descent, L-BFGS, Stochastic Gradient Descent, Conjugate Gradient, etc.), …
Unified analysis of multi-attribute graph learning with non-convex penalties.
problem Graph inference from multi-attribute data.
method Penalized log-likelihood objective function with ADMM and local linear approximation.
result Local consistency in support recovery and precision matrix estimation for non-convex penalties.
New saddle network architectures preserve convex-concave geometry in optimization problems.
problem Optimization models with convex x and concave y components.
method Structured separable decomposition and saddle network architectures.
result Proven one-dimensional approximation theorem and high accuracy on various test functions.
Reward suffices for convex MDPs, expanding RL to new problems.
problem Capturing goals as convex functions of stationary distribution.
method Reformulated as a min-max game using Fenchel duality.
result Convex MDPs require non-stationary reward functions.
This paper proposes a new global optimization algorithm using deep learning.
problem Developing efficient algorithms for global optimization of non-convex functions.
method Two-phase approach: minimization phase with model-driven deep learning, escaping phase with reinforcement learning.
result The proposed algorithm significantly outperforms classical optimization methods and handles ill-posed functions.
We focus on the problem of minimizing a convex function over a convex set given queries to a stochastic first order oracle. We argue that the complexity of convex minimization is only determined by the rate of growth of the function around its minimizer , as quantified by a Tsybakov-like noise co…
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningmath.OC
Majorization-minimization algorithms consist of successively minimizing a sequence of upper bounds of the objective function. These upper bounds are tight at the current estimate, and each iteration monotonically drives the objective function downhill. Such a simple principle is widely applicable and has been very popu…
Paper reveals hidden convexities in deep learning models using sparse signal processing.
problem Non-convex loss functions in deep learning models complicate optimization and theoretical understanding.
method Developed convex equivalences of ReLU NNs and their connections to sparse signal processing models.
result Recent research has uncovered hidden convexities in certain NN architectures, notably two-layer ReLU networks and other architectures.
New algorithm solves complex non-convex problems efficiently.
problem Non-smooth non-convex problems with weakly convex and strongly concave components.
method Stochastic Moreau envelope approximate gradient method (SMAG).
result First single-loop algorithm with state-of-the-art convergence rate.
The paper studies quasi--convex functions and their applications in optimization.
problem Optimization problems with quasi--convex functions.
method Definition and study of -convex, quasi--convex, and related functions.
result Applications of quasi--convex functions in optimization problems.
SGD converges to global minimum for structured non-convex functions.
problem Optimizing non-convex functions using SGD with slow convergence rates.
method Convergence theorems for SGD on structured non-convex functions, including Quasar and PL conditions.
result SGD converges to global minimum for specific non-convex functions under certain conditions.
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
Expanding FCCO to non-smooth weakly-convex problems, improving deep learning performance.
problem Addressing the limitations of current FCCO methods by tackling non-smooth weakly-convex problems.
method Developed a single-loop algorithm for non-smooth weakly-convex FCCO and extended it to tri-level problems.
result Established the complexity for finding ε-stationary points in the Moreau envelop of the objective function.
Optimizers find approximate global minima in non-convex problems.
problem Understanding why local methods solve non-convex optimization problems.
method Formalizing the hypothesis that many local minima are approximately global minima.
result Most local minima of practical non-convex objectives are approximately global minima.
The paper addresses learner privacy in convex optimization with feedback.
problem Privacy risks from eavesdropping adversaries observing learner's queries.
method Optimally obfuscating learner's queries to make their learned optimal value hard to estimate.
result Query complexity overhead is additive in in the minimax formulation, multiplicative in in the Bayesian formulation.
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…
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…
This paper improves convergence guarantees for SGD algorithms in non-convex smooth functions.
problem Theoretical convergence properties of SGD algorithms for non-convex smooth functions.
method Analysis of SGD algorithms with arbitrary data ordering for non-convex smooth functions.
result Enhanced convergence guarantees for incremental gradient and single shuffle SGD, improving the optimization term of convergence guarantee.
Human computation or crowdsourcing involves joint inference of the ground-truth-answers and the worker-abilities by optimizing an objective function, for instance, by maximizing the data likelihood based on an assumed underlying model. A variety of methods have been proposed in the literature to address this inference …
RO-TD learns sparse value functions efficiently.
problem Learning sparse value functions efficiently.
method RO-TD integrates off-policy convergent gradient TD methods and online convex regularization.
result RO-TD learns sparse value functions with low computational complexity.
In this paper, we introduce the first principled adaptive-sampling procedure for learning a convex function in the norm, a problem that arises often in the behavioral and social sciences. We present a function-specific measure of complexity and use it to prove that, for each convex function , our …
Difference of convex (DC) functions cover a broad family of non-convex and possibly non-smooth and non-differentiable functions, and have wide applications in machine learning and statistics. Although deterministic algorithms for DC functions have been extensively studied, stochastic optimization that is more suitable …
Learning with non-modular losses is an important problem when sets of predictions are made simultaneously. The main tools for constructing convex surrogate loss functions for set prediction are margin rescaling and slack rescaling. In this work, we show that these strategies lead to tight convex surrogates iff the unde…
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 …
Develops a new theory of loss functions for statistical machine learning.
problem Evaluation of solutions in binary and multiclass classification problems.
method Defines loss functions as subgradients of support functions of convex sets, enabling a calculus of losses.
result Provides a novel perspective on losses and develops a calculus that interpolates between different losses.
In this paper, we study adaptive online convex optimization, and aim to design a universal algorithm that achieves optimal regret bounds for multiple common types of loss functions. Existing universal methods are limited in the sense that they are optimal for only a subclass of loss functions. To address this limitatio…
Convergence rates for the stochastic gradient descent method for non-convex objective functionsmath.NA
We prove the local convergence to minima and estimates on the rate of convergence for the stochastic gradient descent method in the case of not necessarily globally convex nor contracting objective functions. In particular, the results are applicable to simple objective functions arising in machine learning.
Paper develops compact formulations for optimization problems with rank-one convex functions and indicator variables.
problem Optimization problems involving rank-one convex functions with support constraints.
method Perspective reformulation techniques to exploit conic structure and establish convex hull results.
result Systematic perspective formulations for convex hull descriptions of sets with nonlinear separable or non-separable objective functions and combinatorial constraints.