New algorithm reduces complexity for optimizing complex machine learning tasks.
problem Optimizing complex machine learning objectives like reinforcement learning and portfolio management.
method Developed SARAH-Compositional algorithm using Stochastic Recursive Gradient Descent.
result Achieved optimal IFO complexity bounds for stochastic compositional optimization.
A new method for faster optimization of machine learning problems.
problem Minimization of composition of expected value functions.
method C-SAG, a novel extension of SAG for FS-CEVF problems.
result C-SAG achieves lower oracle query complexity per iteration than C-SVRG and converges faster.
Consider the stochastic composition optimization problem where the objective is a composition of two expected-value functions. We propose a new stochastic first-order method, namely the accelerated stochastic compositional proximal gradient (ASC-PG) method, which updates based on queries to the sampling oracle using tw…
New method solves doubly-nonconvex composite optimization problems.
problem Solving composite optimization problems with both functions nonconvex.
method Stochastic gradient descent with quasiconvex penalty function.
result Convergence properties for doubly-nonconvex composite optimization.
Paper analyzes stability and generalization of SCO algorithms.
problem Understanding how SCO algorithms perform on unseen data.
method Algorithmic stability analysis in statistical learning theory.
result Derives dimension-independent excess risk bounds for SCGD and SCSC.
Paper tackles gradient estimation for large-scale composition problems.
problem Optimization of large-scale composition problems with convex and non-convex structures.
method Stochastically Controlled Stochastic Gradient (SCSG) method for variance reduction.
result Query complexity improved for convex and non-convex problems.
Analysis of a stochastic system showing convergence to an averaged model with Gaussian deviations.
problem Convergence analysis of a perturbed compositional gradient flow system.
method Separation of scales and averaging principle applied to stochastic differential equations.
result The slow motion of the system can be approximated by a standard perturbed gradient flow or SCGD algorithm.
Unified view of gradient-based algorithms for stochastic convex composite optimization.
problem Optimization of stochastic convex composite functions.
method Extend the concept of estimate sequence to cover various gradient-based methods.
result Generic convergence proof and new adaptive SVRG variant.
New method reduces complexity for nonconvex optimization problems.
problem Minimizing composite functions with random or finite sum inner mappings.
method Stochastic composite gradient method with incremental variance reduction.
result Achieves complexity similar to best first-order methods for expected-value and finite-sum nonconvex functions.
New method for optimizing complex composite functions with reduced variance.
problem Optimizing multi-level composite functions with nested random and smooth mappings.
method Normalized proximal approximate gradient (NPAG) method with nested stochastic variance reduction.
result Total sample complexity of O ( ε − 3 ) O(ε^{-3}) O ( ε − 3 ) in expectation and O ( N + N ε − 2 ) O(N+\sqrt{N}ε^{-2}) O ( N + N ε − 2 ) in finite-sum cases. New method solves complex optimization problems efficiently.
problem Optimizing complex functions with inner expectations in machine learning.
method Combines variance reduction methods with duality-free techniques.
result Proves linear convergence for convex and non-convex cases.
Here we study non-convex composite optimization: first, a finite-sum of smooth but non-convex functions, and second, a general function that admits a simple proximal mapping. Most research on stochastic methods for composite optimization assumes convexity or strong convexity of each function. In this paper, we extend t…
New algorithm solves composite optimization problems with unknown expectations.
problem Solving composite optimization problems with unknown statistical expectations.
method Proposes a new stochastic primal-dual algorithm for composite optimization problems with unknown statistical expectations.
result Converges to a saddle point of the Lagrangian function.
Proposes a new model for clustering multiplex networks with compositional data.
problem Clustering multiplex networks with multiple types of relations and compositional data.
method Multiplex Dirichlet stochastic block model for compositional networks.
result Validated through simulation and applied to international export data.
New algorithm framework solves stochastic composite nonconvex optimization problems efficiently.
problem Solving stochastic composite nonconvex optimization problems.
method ProxSARAH framework using SARAH estimator with proximal gradient and averaging steps.
result Achieves best-known complexity bounds with constant and adaptive step-sizes.
The paper develops variance-reduced methods to solve complex optimization problems.
problem Non-convex composition optimization with many inner functions.
method Variance-reduced techniques applied to SGD and SVRG.
result Significant improvement in query complexity for large inner function numbers.
The paper explores local-correlation models for pricing complex financial contracts.
problem Calibrating synthetic quanto forward contracts and composite options.
method Design on-line calibration procedures for local and stochastic volatility models.
result Calibration performance of local-correlation models compared to simpler approximations.
New algorithms solve non-convex optimization problems efficiently.
problem Non-convex stochastic compositional optimization problems.
method Developed two stochastic Gauss-Newton algorithms.
result Established global oracle complexity for stochastic Gauss-Newton methods.
Unified view of stochastic optimization methods with improved convergence and robustness.
problem Stochastic convex composite optimization with noise.
method Estimate sequence approach, accelerated algorithms, robust strategies.
result Optimal complexity accelerated SVRG algorithm robust to noise.
New method solves complex optimization problems with reduced sample complexity.
problem Solving nonconvex stochastic nested optimization problems.
method Stochastic ADMM approach to find ε-stationary points.
result Total sample complexity of O(ε^(-3)) for online case and O((2N_1 + N_2) + (2N_1 + N_2)^(1/2)ε^(-2)) for finite sum case.
Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \mathbf{E}_v [f_v\big(\mathbf{E}_…
Optimizes convergence rate of stochastic proximal algorithms for composite convex problems.
problem Solving composite convex optimization problems with composite regularizers.
method Analyzed proximal stochastic gradient method and randomized incremental proximal method under relaxed variance assumptions.
result Proves O ( 1 / T ) O(1/\sqrt{T}) O ( 1/ T ) convergence rate for last iterate of both algorithms under componentwise convexity and smoothness. New algorithm solves complex optimization problems without needing projections.
problem Optimizing nested functions under convex constraints with noisy evaluations.
method Projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization.
result The algorithm achieves ε ε ε -stationary solutions with complexity bounds independent of ε ε ε and T T T . New hybrid stochastic optimization framework tackles nonconvex problems efficiently.
problem Efficiently solving stochastic composite nonconvex optimization problems.
method Combining two stochastic estimators to create a hybrid one, developing several variants of stochastic gradient methods.
result Achieved best-known complexity bounds for various optimization problems.
FeDualEx tackles saddle point optimization in federated learning with composite objectives.
problem Saddle point optimization with constraints and non-smooth regularization in federated learning.
method Federated Dual Extrapolation (FeDualEx) algorithm for saddle point optimization and composite objectives.
result FeDualEx effectively solves saddle point optimization problems with composite objectives in federated learning.
New PDHG approach tackles high-cost stochastic minimization with linear composite terms.
problem High cost and lack of closed-form proximal mapping for composite regularization terms.
method Stochastic PDHG with data point sampling, high-probability iteration complexity analysis.
result High-probability convergence analysis supports practical performance.
New algorithm tackles nested bi-level optimization problems for robust feature learning.
problem Nested compositional bi-level optimization problems in machine learning.
method Stochastic approximation algorithms for solving nested compositional bi-level optimization problems without matrix inversions.
result Achieves an ε-stationary solution with an oracle complexity of approximately O_T(1/ε^2).
Paper solves robust convex problems with heavy-tailed noise.
problem Solving convex compositional problems with heavy-tailed noise.
method Sub-Gaussian confidence bounds under weak heavy-tailed noise assumptions, using boosting strategy.
result Achieves nearly optimal high probability convergence result.
Improved Q-learning for robot control with faster data-efficiency.
problem Poor data-efficiency and stochasticity in deep Q-learning.
method Composite Q-learning: Decomposes Q-function into short- and long-term predictions.
result Significant learning speedup and improved data-efficiency in robot tasks.
Develops minibatch stochastic proximal gradient for large-scale learning models.
problem Finding optimal predictors with complex regularizers in large-scale learning models.
method Minibatch variants of stochastic proximal gradient algorithm for composite objective functions.
result Minibatch size N N N after O ( 1 N ε ) \mathcal{O}(\frac{1}{Nε}) O ( N ε 1 ) iterations achieves ε − ε- ε − suboptimality in expected quadratic distance. Adaptive sampling method solves constrained and composite optimization problems.
problem Solving constrained optimization problems with stochastic objectives and deterministic constraints.
method Proximal gradient method with adaptive sampling to improve gradient approximation quality.
result Convergence results established for both strongly convex and general convex objectives.
Unified SGD method improves convergence for nested optimization problems.
problem Stochastic nested optimization problems.
method ALTERNATE dESCEN (ALSET) method leveraging hidden smoothness.
result Requires O ( ε − 2 ) {\cal O}(ε^{-2}) O ( ε − 2 ) samples to achieve an ε ε ε -stationary point. Adaptive MAB algorithms handle composite, anonymous feedback without reward interval knowledge.
problem Multi-armed bandit with composite and anonymous feedback, especially without reward interval size knowledge.
method Proposed adaptive algorithms for stochastic and adversarial cases, without reward interval knowledge.
result First algorithm for adversarial case handling non-oblivious adversary and unknown reward interval size.
We consider the minimization of composite objective functions composed of the expectation of quadratic functions and an arbitrary convex function. We study the stochastic dual averaging algorithm with a constant step-size, showing that it leads to a convergence rate of O(1/n) without strong convexity assumptions. This …
Bayesian optimization for composite functions improves efficiency.
problem Optimizing composite functions with expensive derivative-free evaluations.
method Exploits composite structure using multi-output Gaussian process and expected improvement for composite functions.
result Significantly improves sampling efficiency and asymptotically converges to global optimum.
A new hybrid algorithm reduces stochastic gradient evaluations for nonconvex optimization.
problem Solving stochastic composite nonconvex optimization problems efficiently.
method Proposes a new hybrid variance-reduced proximal gradient method with a stochastic gradient estimator.
result Achieves optimal stochastic oracle complexity bound with one less gradient evaluation.
SpiderBoost improves SPIDER's efficiency and applicability in optimization.
problem Optimization of smooth nonconvex functions and handling nonsmooth regularizers.
method SpiderBoost uses a larger constant-level stepsize and proximal mapping for composite optimization, achieving improved oracle complexity.
result SpiderBoost achieves an oracle complexity of O ( min { n 1 / 2 ε − 2 , ε − 3 } ) \mathcal{O}(\min\{n^{1/2}ε^{-2},ε^{-3}\}) O ( min { n 1/2 ε − 2 , ε − 3 }) in composite nonconvex optimization. Paper develops momentum schemes with variance reduction for non-convex composition optimization.
problem Lack of convergence guarantee and efficient momentum design in existing algorithms.
method Develops various momentum schemes with SPIDER-based variance reduction.
result Achieves near-optimal sample complexity and linear convergence rate.
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 algorithms solve complex multi-level optimization problems with improved efficiency.
problem Smooth stochastic multi-level composition optimization problems.
method Two algorithms using moving-average and linearized stochastic estimates.
result Achieved sample complexities of O(1/ε^4) and O(1/ε^6).
Sharp privacy bounds for sequential analysis of sensitive data.
problem Privacy degradation under sequential analysis of sensitive data.
method Edgeworth expansion in f-differential privacy framework.
result Improved privacy bounds under composition with refined approximation accuracy.
We consider in this paper a class of composite optimization problems whose objective function is given by the summation of a general smooth and nonsmooth component, together with a relatively simple nonsmooth term. We present a new class of first-order methods, namely the gradient sliding algorithms, which can skip the…
GFlowNet-EM learns complex latent variable models with discrete structures.
problem Challenges in modeling posteriors over discrete compositional latents with expectation-maximization.
method Uses GFlowNets to learn stochastic policies for sampling from complex posterior distributions.
result GFlowNet-EM enables training expressive LVMs with discrete compositional latents.
New variance-reduction methods solve stochastic composite inclusions.
problem Solving nonmonotone stochastic composite inclusions.
method Developed unbiased and biased variance-reduced estimators for FRBS method.
result Achieved best oracle complexities for finite-sum and expectation settings.
New MAB problem with delayed, anonymous feedback analyzed.
problem Delayed, anonymous feedback in stochastic bandits.
method Phase-based extensions of UCB algorithm for SDCAF.
result Sub-linear regret guarantees for proposed algorithms.
Develops new optimization techniques for decision-making under uncertainty.
problem Decision-making under uncertainty with complex cost functions and nested expectations.
method Introduces Multistage Conditional Compositional Optimization (MCCO) and develops multilevel Monte Carlo techniques.
result New optimization techniques reduce scenario complexity from exponential to polynomial growth.
Accelerates machine learning algorithms for sparse data.
problem Efficiently solving composite convex minimization problems.
method Accelerated dual-averaging primal-dual method for composite convex minimization.
result Demonstrates advantages in handling sparse data both theoretically and empirically.
Develops likelihood-based methods for trawl processes, improving forecasting accuracy.
problem Statistical modeling of trawl processes with heavy tails and long memory.
method Composite likelihood estimation as a stochastic optimization problem, using gradient descent methods.
result New gradient estimators with significantly reduced variance for trawl processes.