This paper characterizes exp-concavity of proper composite losses and transforms mixable losses into exp-concave ones.
problem Understanding and transforming mixable losses into exp-concave ones for better online prediction strategies.
method Characterization of exp-concavity, mixability condition, and approximation approach for multi-class losses.
result Complete characterization of exp-concavity for proper composite losses and transformation of mixable losses into exp-concave ones.
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 O ( d / n + log ( 1 / δ ) / n ) O( d / n + \log( 1 / δ) / n ) O ( d / n + log ( 1/ δ ) / n ) excess risk bound. Paper proposes robust dictionary learning using concave losses.
problem Sensitivity to outliers in traditional dictionary learning methods.
method Generic framework based on concave losses, with results on composition of concave functions.
result Method better detects outliers and generates better dictionaries.
The paper extends mixability theory to function-valued forecasts, proving various loss functions are mixable.
problem Efficient aggregation of functional and probabilistic forecasts in online prediction games.
method Adapting mixable and exponentially concave loss functions to function-valued forecasts.
result Various loss functions used for probabilistic forecasting are mixable (exp-concave).
The overarching goal of this paper is to derive excess risk bounds for learning from exp-concave loss functions in passive and sequential learning settings. Exp-concave loss functions encompass several fundamental problems in machine learning such as squared loss in linear regression, logistic loss in classification, a…
Simple analysis for fast rates in empirical minimization with concave losses and convex regularization.
problem Fast rates in empirical minimization with concave losses and convex regularization.
method Simple analysis using covering number and concentration inequality.
result First result of fast rates with high probability for exponential concave empirical risk minimization.
Solves learning halfspaces with Massart noise for log-concave distributions.
problem Learning halfspaces with Massart noise in distribution-specific PAC model.
method Identifies a smooth non-convex surrogate loss and uses SGD to solve the learning problem.
result First computationally efficient algorithm for learning halfspaces with Massart noise for a broad family of distributions.
New algorithm reduces dynamic regret for exp-concave losses.
problem Minimizing dynamic regret in online learning with exp-concave losses.
method Integrates KKT conditions to achieve optimal dynamic regret.
result Achieves dynamic regret of i l d e O ∗ ( n 1 / 3 C n 2 / 3 ∨ 1 ) ilde O^*(n^{1/3}C_n^{2/3} \vee 1) i l d e O ∗ ( n 1/3 C n 2/3 ∨ 1 ) . SA algorithms control dynamic regret in non-stationary settings with strong convexity or exp-concavity.
problem Non-stationary Online Convex Optimization with dynamic regret control.
method Strongly Adaptive (SA) algorithms view dynamic regret as path variation of the comparator sequence.
result SA algorithms achieve i l d e O ( T V T ∨ log T ) ilde O(\sqrt{TV_T} \vee \log T) i l d e O ( T V T ∨ log T ) and i l d e O ( d T V T ∨ d log T ) ilde O(\sqrt{dTV_T} \vee d\log T) i l d e O ( d T V T ∨ d log T ) dynamic regret for strongly convex and exp-concave losses, respectively. Near-logarithmic regret per switch achieved for mixable/exp-concave losses.
problem Online optimization of mixable loss functions with dynamic environments.
method Online mixture framework using static solvers and hyper-expert creations.
result Near-logarithmic regret per switch with sub-polynomial complexity.
Optimal convex loss function improves regression coefficient estimation.
problem Asymptotic variance improvement in linear regression estimation.
method Score matching extension for log-concave projection.
result Semiparametric estimator attains minimal asymptotic covariance.
Improved online convex optimization with delayed feedback using curvature.
problem Online convex optimization with curved losses and delayed feedback.
method Variant of follow-the-regularized-leader and Online Newton Step algorithm with adaptive learning rate.
result Regret bounds of order min { σ max ln T , d t o t } \min\{σ_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\} min { σ m a x ln T , d tot } for exp-concave losses. Study optimal consumption for loss-averse agents considering past spending peaks.
problem Optimal consumption for loss-averse agents with reference to past spending maximum.
method Adopted S-shaped utility, concave envelope, HJB variational inequality, dual transform, and smooth-fit conditions.
result Obtained piecewise closed-form solutions for optimal consumption and investment control.
The paper extends risk measures to two-step approximations and studies log-concave distributions.
problem Extending classical risk measures to two-step approximations.
method Optimization problem for determining optimal regime thresholds and values for log-concave distributions.
result Conditions for the uniqueness of regime changing in log-concave distributions.
Gradient descent finds halfspaces with low error for agnostic learning.
problem Agnostic learning of linear halfspaces with convex surrogates.
method Gradient descent on convex surrogates for zero-one loss.
result Gradient descent finds halfspaces with error O ( O P T 1 / 2 + ε ) O(\mathsf{OPT}^{1/2} + \varepsilon) O ( OPT 1/2 + ε ) in poly time and sample complexity. Efficiently learns Single-Index Models with constant factor approximation.
problem Learning Single-Index Models under L 2 2 L_2^2 L 2 2 loss with unknown link functions. method An efficient algorithm using alignment sharpness for optimization.
result Achieves constant factor approximation to optimal loss for various distributions and link functions.
Theory integrates loss aversion into expected utility for monetary returns.
problem Modeling loss aversion in expected utility theory.
method Develops state-dependent linear utility functions incorporating loss aversion.
result Contracts from monopolists in insurance markets.
Paper develops new methods for binary classification with complex performance measures.
problem Complex performance measures in binary classification are not decomposable and require new theoretical and methodological developments.
method Identifies Karmic and threshold-quasi-concavity properties, and develops a computationally practical plug-in classifier.
result Bayes optimal classifier is a threshold function of conditional probability, leading to practical classification error analysis.
Paper analyzes adversarial dynamics in neural networks.
problem Vulnerability of neural networks to adversarial perturbations.
method Analyzed the dynamics of maximization step in adversarial training.
result Projected gradient ascent finds a local maximum in polynomial iterations.
Optimizes investment under uncertain time horizons with non-concave utility.
problem Optimizing investment decisions with non-concave utility and uncertain time horizons.
method Established necessary and sufficient conditions for optimality, suggested recursive procedure for non-concave utility.
result Optimal investment strategies under uncertain time horizons exhibit multimodal distribution, indicating flexibility in switching between local maximizers.
Study minimax risk of score estimation for log-concave distributions.
problem Minimizing risk in score estimation for log-concave distributions.
method Developed subclasses of log-concave densities and constructed a locally adaptive, multiscale estimator.
result Established minimax rates for score estimation over specific subclasses of log-concave densities.
A new algorithm reduces online exp-concave optimization runtime.
problem Minimizing regret in online learning with exponentially concave losses.
method LightONS, a variant of Online Newton Step (ONS), reduces runtime to O ( d 2 T + d ω T log T ) O(d^2 T + d^ω\sqrt{T \log T}) O ( d 2 T + d ω T log T ) . result Optimal regret with reduced runtime to O ( d 2 T + d ω T log T ) O(d^2 T + d^ω\sqrt{T \log T}) O ( d 2 T + d ω T log T ) . Optimal trading strategy under market resistance and concave price impact model.
problem Optimal trading in a market with endogenous resistance and concave price impact.
method Modeling market resistance, deriving a stochastic Fredholm equation, proving existence and uniqueness, proposing an iterative scheme.
result Existence and uniqueness of optimal control under certain conditions, exponential convergence of iterative scheme.
We solve ReLU regression with efficient approximations for various distributions.
problem Finding the best fitting ReLU function with square loss from unknown distributions.
method Introduced efficient constant-factor approximation algorithm and polynomial-time approximation scheme.
result First constant-factor approximation algorithm for ReLU regression with weak concentration conditions.
A new method lifts training of input-convex neural networks to avoid dead weights and plateaued loss.
problem Training input-convex neural networks with non-negative weights.
method Introduces a hypernetwork that emits non-negative weights from a summary of the input batch, adding stochasticity to soften the loss landscape.
result The lift method achieves lower test loss than projected gradient descent and direct softplus reparametrization.
Paper examines costs of using wrong price impact models in trading.
problem Misspecifying price impact models in trading predictions.
method Derives formulas for misspecification costs and applies to trading data.
result Misspecification costs are asymmetric, affecting profits and losses.
Paper proposes robust risk measures for non-negative risks with partial information.
problem Tackles robustness of distortion risk measures under distributional uncertainty.
method Introduces new uncertainty sets and derives closed-form expressions for risk maximization.
result Derives closed-form expressions for risk maximization over uncertainty sets.
Reduces dynamic regret to static problem in RKHS.
problem Minimizing cumulative loss in online convex optimization.
method Reduces dynamic regret to static regret problem in RKHS.
result Optimal dynamic regret guarantees for linear losses and new bounds for exp-concave and improper linear regression.
Optimizes bond portfolios to avoid worst-case losses.
problem Finding the worst-case value of a bond portfolio over a range of yield curves and spreads.
method Solves a convex-concave saddle point optimization problem to find the worst-case value and construct a robust portfolio.
result Constructs a bond portfolio that includes the worst-case value, ensuring robustness against market uncertainties.
New PG losses improve decision optimization in misspecified models.
problem Improving decision optimization in models that are not perfectly specified.
method Introducing Perturbation Gradient (PG) losses to connect decision loss with directional derivatives and optimizing using gradient techniques.
result PG losses yield best-in-class policies asymptotically, even in misspecified settings.
New method recovers signals from saturated data using linear loss and nonconvex penalties.
problem Signal recovery from saturated measurements with sign information loss.
method Linear loss and nonconvex penalties (e.g., minimax concave penalty, sorted ℓ1 norm).
result Estimation error is bounded and recovery performance improved.
Improved regret bounds for adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Truncated continuous exponential weights algorithm over the probability simplex, analyzing with linear bandit setting without contexts.
result Second-order bound of i l d e O ( K d V T ) ilde O(K\sqrt{d V_T}) i l d e O ( K d V T ) and first-order bound of i l d e O ( K d L T ∗ ) ilde O(K\sqrt{d L_T^*}) i l d e O ( K d L T ∗ ) . Neural networks can interpolate noisy data and still generalize well.
problem Generalization of neural networks trained on noisy data.
method Two-layer neural networks trained to interpolation by gradient descent on corrupted labels.
result Neural networks can achieve zero training error and optimal test error.
New loss functions optimize pricing policies using transaction data, ensuring expected revenue guarantees.
problem Optimizing pricing policies with transaction data where valuation data is not directly observed.
method Introducing convex loss functions for contextual pricing, focusing on log-concave valuation distributions.
result Proved expected revenue bounds for generalized hinge and quantile pricing loss functions.
Paper proposes an online learning method with multi-level adaptivity for diverse loss functions.
problem Online learning with unknown types and curvatures of functions.
method Multi-layer online ensemble approach with gradient variations.
result Achieves improved regret bounds for different types of loss functions.
Analyzes alternating minimization for nonconvex sets in high-dimensional statistics.
problem Optimizing loss functions over nonconvex sets in high-dimensional statistics.
method Local concavity coefficients for nonconvex sets, alternating minimization, inexact algorithms.
result Reveals distinctions between alternating and non-alternating methods, provides convergence conditions.
Paper proposes new loss functions for training energy networks.
problem Challenges in computing gradients for training energy networks.
method Proposes generalized Fenchel-Young losses for efficient gradient computation.
result Demonstrates the calibration of excess risk for linear-concave energies.
Novel framework for portfolio selection considering utility and risk.
problem Maximizing utility subject to risk constraints with various utility and risk functionals.
method General framework accommodating non-concave utilities and non-convex risk measures. Characterization of well-posedness using a simple either-or criterion.
result Minimal condition for well-posedness: either utility or risk must be sensitive to large losses.
Gradient descent learns a neuron in noisy data.
problem Learning a single neuron with adversarial label noise.
method Gradient descent on the L 2 2 L_2^2 L 2 2 -loss. result Efficient approximate learners for various distributions and activations.
This paper tackles robust control of noisy systems with uncertain distributions.
problem Optimal control of sampled-data stochastic systems with multiplicative noise and distributional ambiguity.
method Develops a convex relaxation to handle the ``concave-max'' geometry and derives a probabilistic performance guarantee.
result Derives an explicit, non-asymptotic bound on the duality gap and proves robust viability conditions.
RSGDA improves convergence rates for nonconvex-strongly concave optimization.
problem Optimization of nonconvex-strongly concave problems.
method Randomized Stochastic Gradient Descent Ascent (RSGDA) with optimal loop sizes.
result First almost sure convergence rates for SGDA algorithms on nonconvex-strongly concave settings.
New algorithms minimize dynamic regret in non-stationary online learning.
problem Universal dynamic regret minimization under exp-concave and smooth losses.
method Strongly Adaptive algorithms with a path variational based on second order differences of the comparator sequence.
result Achieve a dynamic regret of i l d e O ( d 2 n 1 / 5 C n 2 / 5 ∨ d 2 ) ilde O(d^2 n^{1/5} C_n^{2/5} \vee d^2) i l d e O ( d 2 n 1/5 C n 2/5 ∨ d 2 ) , optimal modulo dependencies. Study on optimal fees in hedge funds with first-loss compensation.
problem Determining the best fee structure for hedge funds with first-loss compensation.
method Solved the manager's non-concave utility maximization problem, calculated Pareto optimal first-loss schemes, and maximized a decision criterion on this set.
result Traditional fees are not Pareto optimal, and the preferred first-loss coverage guarantee varies with investor and market factors.
Concave elliptic operators yield concave functions on cohomology.
problem Understanding concave functions on cohomology.
method General construction of concave elliptic operators.
result Generalized Khovanskii-Teissier inequalities.
Gaptron algorithm reduces mistakes in online multiclass classification.
problem Online multiclass classification with limited information.
method Randomized first-order algorithm exploiting the gap between zero-one loss and surrogate losses.
result First linear time algorithm with O ( K T ) O(K\sqrt{T}) O ( K T ) expected regret. MetaCURL tackles non-stationary MDPs with optimal dynamic regret.
problem Online learning in non-stationary Markov decision processes.
method MetaCURL uses a meta-algorithm with multiple black-box algorithms and a sleeping expert framework.
result Achieves optimal dynamic regret without prior knowledge of MDP changes.
The paper establishes conditions for strict power concavity in convolutions.
problem Conditions for strict power concavity in convolutions.
method Analyzes sufficient conditions for strict parabolic power concavity of convolutions.
result Establishes sufficient conditions for strict power concavity of convolutions.
Adversarial training improves robustness of halfspaces in noisy data.
problem Learning robust halfspaces in the presence of label noise.
method Adversarial training with binary cross-entropy or nonconvex sigmoidal loss.
result Adversarial training yields robust halfspaces with improved classification error.