Many classical algorithms are found until several years later to outlive the confines in which they were conceived, and continue to be relevant in unforeseen settings. In this paper, we show that SVRG is one such method: being originally designed for strongly convex objectives, it is also very robust in non-strongly co…
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,657 papers · 148 categories
Trend · papers per month
48 results for “convex objects”
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 …
Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descentcs.LG
Unified framework for analyzing neural networks trained by gradient descent.
problem Lack of generalizable guarantees for neural networks trained by gradient descent.
method Proxy convexity and proxy Polyak-Lojasiewicz inequalities.
result Unified guarantees for neural networks trained by gradient descent.
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…
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.
New algorithms optimize non-smooth, non-convex objectives with improved complexity.
problem Optimizing non-smooth, non-convex stochastic objectives.
method Reduction to online learning, applying optimistic online learning techniques.
result Improved complexity for finding -stationary points.
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.
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…
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problemmath.OC
Novel method for bilevel optimization with convex lower-level problem.
problem Minimizing a smooth objective over the optimal solution set of a convex constrained problem.
method Local cutting plane approximation of lower-level solution set combined with conditional gradient updates.
result Achieves optimal iteration complexity for the considered class of bilevel problems.
Paper analyzes convergence of stochastic methods under heavy-tailed noise.
problem Analyzing convergence of stochastic methods under heavy-tailed noise.
method Investigates vanilla and clipped stochastic subgradient descent methods.
result Demonstrates convergence properties under sub-Weibull and p-BCM noise assumptions.
A new algorithm reduces communication rounds for distributed convex optimization.
problem Efficiently solving convex optimization problems in distributed systems.
method Proposes a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization.
result Reduces the number and frequency of communication rounds compared to existing methods.
We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\varep…
New methods boost first-order optimization with faster rates.
problem Designing efficient first-order methods for convex problems.
method Shifted objective function with interpolation condition.
result New schemes achieve faster convergence rates.
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.
We solve a portfolio selection problem with four objectives, finding convex scalarizations for part of the Pareto front.
problem Portfolio selection with four objectives: mean, variance, skewness, and kurtosis.
method Linearly scalarize MVSK objectives into a convex polynomial over the probability simplex, compute optimizers for each .
result Identify a set of hyper-parameters for which the scalarization is convex, allowing computation of part of the Pareto front.
Conditional stochastic optimization covers a variety of applications ranging from invariant learning and causal inference to meta-learning. However, constructing unbiased gradient estimators for such problems is challenging due to the composition structure. As an alternative, we propose a biased stochastic gradient des…
We address the problem of estimating a sparse low-rank matrix from its noisy observation. We propose an objective function consisting of a data-fidelity term and two parameterized non-convex penalty functions. Further, we show how to set the parameters of the non-convex penalty functions, in order to ensure that the ob…
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…
Boosting is a popular way to derive powerful learners from simpler hypothesis classes. Following previous work (Mason et al., 1999; Friedman, 2000) on general boosting frameworks, we analyze gradient-based descent algorithms for boosting with respect to any convex objective and introduce a new measure of weak learner p…
We consider the stochastic composition optimization problem proposed in \cite{wang2017stochastic}, which has applications ranging from estimation to statistical and machine learning. We propose the first ADMM-based algorithm named com-SVR-ADMM, and show that com-SVR-ADMM converges linearly for strongly convex and Lipsc…
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.
Statistical mechanics of the inverse Ising problem and the optimal objective functioncond-mat.dis-nn
The inverse Ising problem seeks to reconstruct the parameters of an Ising Hamiltonian on the basis of spin configurations sampled from the Boltzmann measure. Over the last decade, many applications of the inverse Ising problem have arisen, driven by the advent of large-scale data across different scientific disciplines…
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 proximal inertial gradient descent is efficient for the composite minimization and applicable for broad of machine learning problems. In this paper, we revisit the computational complexity of this algorithm and present other novel results, especially on the convergence rates of the objective function values. The no…
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.
MixMin finds optimal data mixtures for better model performance.
problem Finding the best data mixtures for improved model performance is challenging.
method Developed a gradient-based approach for optimizing a convex bi-level objective.
result MixMin mixtures uniformly improved model performance across various tasks.
New framework for optimizing machine learning risks.
problem Optimizing non-decomposable machine learning objectives.
method Empirical X-risk minimization (EXM) framework with algorithmic techniques.
result Developed algorithms for solving EXM with smooth non-convex objectives.
Standard stochastic optimization methods are brittle, sensitive to stepsize choices and other algorithmic parameters, and they exhibit instability outside of well-behaved families of objectives. To address these challenges, we investigate models for stochastic minimization and learning problems that exhibit better robu…
Stochastic structured prediction under bandit feedback follows a learning protocol where on each of a sequence of iterations, the learner receives an input, predicts an output structure, and receives partial feedback in form of a task loss evaluation of the predicted structure. We present applications of this learning …
We study convergence properties of Stochastic Gradient Descent (SGD) for convex objectives without assumptions on smoothness or strict convexity. We consider the question of establishing that with high probability the objective evaluated at the candidate minimizer returned by SGD is close to the minimal value of the ob…
We develop mask iterative hard thresholding algorithms (mask IHT and mask DORE) for sparse image reconstruction of objects with known contour. The measurements follow a noisy underdetermined linear model common in the compressive sampling literature. Assuming that the contour of the object that we wish to reconstruct i…
Convex Optimization with an Interpolation-based Projection and its Application to Deep Learningcs.LG
A new projection method for convex optimization reduces computation costs.
problem Efficiently projecting points into convex sets for deep learning.
method Interpolation-based projection for cheaper computation.
result The proposed method converges for linear and convex constraints.
We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gra…
We present a stochastic setting for optimization problems with nonsmooth convex separable objective functions over linear equality constraints. To solve such problems, we propose a stochastic Alternating Direction Method of Multipliers (ADMM) algorithm. Our algorithm applies to a more general class of nonsmooth convex …
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescs.LG
In this work we introduce a new optimisation method called SAGA in the spirit of SAG, SDCA, MISO and SVRG, a set of recently proposed incremental gradient algorithms with fast linear convergence rates. SAGA improves on the theory behind SAG and SVRG, with better theoretical convergence rates, and has support for compos…
Study KKT conditions for multi-objective optimization on Hadamard manifolds.
problem Optimizing multi-objective interval-valued functions on Hadamard manifolds.
method Developed KKT conditions for Pareto optimal solutions under different ordering and convexity notions.
result Results are more general than on Euclidean spaces.
Dual optimization for convex constrained objectives without the gradient-Lipschitz assumptionstat.ML
The minimization of convex objectives coming from linear supervised learning problems, such as penalized generalized linear models, can be formulated as finite sums of convex functions. For such problems, a large set of stochastic first-order solvers based on the idea of variance reduction are available and combine bot…
SUSTAIN algorithm tackles stochastic bilevel optimization with near-optimal complexity.
problem Stochastic bilevel optimization problems with specific convexity and smoothness properties.
method SUSTAIN algorithm using single-timescale double-momentum stochastic approximation.
result SUSTAIN achieves near-optimal complexity for finding ε-stationary solutions.
Motivated by big data applications, first-order methods have been extremely popular in recent years. However, naive gradient methods generally converge slowly. Hence, much efforts have been made to accelerate various first-order methods. This paper proposes two accelerated methods towards solving structured linearly co…
Non-convex optimization is ubiquitous in machine learning. Majorization-Minimization (MM) is a powerful iterative procedure for optimizing non-convex functions that works by optimizing a sequence of bounds on the function. In MM, the bound at each iteration is required to \emph{touch} the objective function at the opti…
Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectivescs.LG
This paper analyzes SGD with increasingly weighted averaging for optimization and generalization.
problem Improving optimization and generalization for non-strongly convex objectives.
method Comprehensive analysis of increasingly weighted averaging schemes for convex, strongly convex, and non-convex objectives.
result The weight affects both optimization and generalization errors, revealing a trade-off.
Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we cons…
New DRO algorithm finds robust models without strong assumptions.
problem Learning robust models against distribution shift.
method Non-convex, non-smooth, non-asymptotic convergence guarantees for DRO.
result Algorithm finds first-order stationary points efficiently.
AEGD optimizes non-convex functions with dynamic energy updates.
problem Optimizing non-convex functions efficiently and robustly.
method Adaptive Gradient Descent (AEGD) with a dynamically updated energy variable.
result AEGD achieves energy-dependent convergence rates for both convex and non-convex objectives.
DFFL tackles federated learning with heterogeneous objectives and constraints.
problem Federated learning with clients having different objectives and feasible regions.
method Derived heterogeneity bounds for cost-vector distances and support-function/shape-distance terms. Lifted pointwise bounds to local-versus-federated excess-risk comparison.
result Federation is beneficial when the statistical advantage of pooling exceeds a client-specific heterogeneity penalty.
Improved Clipped-SGD achieves near-optimal heavy-tailed statistical estimation in streaming settings.
problem High-dimensional heavy-tailed statistical estimation in streaming with memory constraints.
method Stochastic convex optimization with Clipped-SGD, proving near-optimal sub-Gaussian statistical rates.
result Clipped-SGD achieves an error of with probability .
What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneitycs.LG
Improved Local SGD convergence for general convex objectives with bounded second-order heterogeneity.
problem Understanding when and why Local SGD outperforms alternatives in distributed optimization.
method Established improved convergence guarantees for Local SGD on general convex objectives under bounded second-order heterogeneity.
result Upper bounds for Local SGD are nearly tight, providing a sharper convergence theory.
A generalized optimistic method for saddle point problems with improved complexity.
problem Solving convex-concave saddle point problems efficiently.
method Proposes a generalized optimistic method that includes the optimistic gradient method as a special case, handling constrained saddle point problems with composite objective functions and arbitrary norms.
result Best-known global iteration complexity bounds for first-, second-, and higher-order methods.