The maximum a posteriori (MAP) configuration of binary variable models with submodular graph-structured energy functions can be found efficiently and exactly by graph cuts. Max-product belief propagation (MP) has been shown to be suboptimal on this class of energy functions by a canonical counterexample where MP conver…
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “suboptimal points”
PE-SVI reduces SVI inference complexity by finding a suitable start point.
problem Complex posterior inference in graphical models leads to suboptimal learning.
method PE-SVI uses a pseudo-encoded start point to reduce gradient steps and step sizes.
result PE-SVI achieves the same ELBo objective as SVI with less than 1% of the required steps.
We show that any smooth bi-Lipschitz can be represented exactly as a composition of functions that are close to the identity in the sense that each is Lipschitz, and the Lipschitz constant decreases inversely with the number of functions com…
Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Pointcs.DS
New algorithm estimates edge density of random graphs robustly, achieving optimal breakdown point.
problem Estimating edge density of Erdős-Rényi graphs under adversarial edge manipulation.
method Sum-of-Squares (SoS) hierarchy, constructing constant-degree certificates for concentration.
result First polynomial-time algorithm with optimal breakdown point and matching error guarantees.
A new measure helps compute suboptimality in entropy-regularized methods.
problem Computing suboptimality in entropy-regularized variational objectives when unnormalised densities are unavailable.
method Introduced 'kernel gradient discrepancy' (KGD) to compute suboptimality explicitly.
result KGD characterizes kernel Stein discrepancy (KSD) in the standard Bayesian context and measures variational gradient size.
Understanding the loss surface of neural networks is essential for the design of models with predictable performance and their success in applications. Experimental results suggest that sufficiently deep and wide neural networks are not negatively impacted by suboptimal local minima. Despite recent progress, the reason…
Two entropy measures quantify suboptimal portfolio performance.
problem Measuring suboptimality in investment portfolios.
method Relative entropy (KL divergence) calculations.
result Suboptimal portfolios appear better than Kelly portfolios under certain measures.
This paper establishes lower bounds for smooth nonconvex finite-sum optimization.
problem Understanding the complexity of finding optimal solutions in nonconvex finite-sum optimization.
method Proving tight lower bounds for the complexity of finding ε-suboptimal points and ε-approximate stationary points.
result Existing algorithms achieve optimal IFO complexity up to logarithmic factors.
Paper explores PG for MCR, finding suboptimal policies but providing bounds.
problem Optimizing coherent risk in MDPs using PG.
method Developed practical PG implementation using state distribution reweighting.
result PG can learn risk-sensitive policies but suboptimality is common.
Novel IRL method identifies suboptimal medical decisions in ICU data.
problem Identifying suboptimal medical decisions in clinical settings.
method Incorporates Inverse Reinforcement Learning with a pruning step to identify and remove suboptimal actions.
result Pruning step effectively identifies clinical priorities and values from suboptimal data.
New suboptimal algorithm for best subset selection in high-dimensional data.
problem Nonconvex and computationally challenging best subset selection in linear regression.
method Introducing a new suboptimal algorithm and comparing it with other popular methods.
result The new procedure is a competitive suboptimal algorithm for high-dimensional data.
New method upsamples sparse, non-uniform point clouds more accurately.
problem Suboptimal results from existing point cloud upsampling methods.
method Imposes manifold distribution constraints using Gaussian functions.
result Generates higher-quality, more uniformly distributed dense point clouds.
Research aims to improve confidence intervals for RKHS elements in online learning.
problem Improper confidence intervals lead to suboptimal regret bounds in kernel-based bandit and reinforcement learning.
method Formalizes the open problem of online confidence intervals in RKHS and reviews existing results.
result Identifies the online nature of observation points as the main challenge for tight confidence intervals.
While the optimization problem behind deep neural networks is highly non-convex, it is frequently observed in practice that training deep networks seems possible without getting stuck in suboptimal points. It has been argued that this is the case as all local minima are close to being globally optimal. We show that thi…
This work ensures policy gradient methods converge to global optima for certain control problems.
problem Non-convex optimization challenges in policy gradient methods for complex control problems.
method Identifies structural properties ensuring non-convex objective functions have no suboptimal stationary points.
result Policy gradient methods converge to global optima under certain conditions, satisfying a Polyak-Lojasiewicz condition.
Safe linear bandits over unknown polytopes avoid safety violations and suboptimal actions.
problem Online approach to linear programming with unknown constraints and risks.
method Doubly-optimistic strategy (DOSS) for safe linear bandits over polytopes.
result DOSS achieves tight bounds on efficacy regret and safety violations.
A new algorithm finds minimizers in dueling optimization with a monotone adversary.
problem Finding minimizers in dueling optimization with a monotone adversary.
method Introduces and studies dueling optimization with a monotone adversary, designs an efficient randomized algorithm.
result Efficient algorithm incurs cost and iteration complexity , asymptotically optimal.
The Lasso is suboptimal in sparse linear regression due to design matrix constraints.
problem The suboptimality of the Lasso estimator in sparse linear regression.
method Characterization of optimal estimation rates and analysis of the Lasso estimator.
result The Lasso is provably minimax rate-suboptimal when the minimum singular value is small.
Paper explores limits of imitation learning in MDPs, setting new suboptimality bounds.
problem Understanding the statistical limits of imitation learning in MDPs.
method Analyzes minimax statistical limits in two settings: pre-interaction and interaction.
result Establishes suboptimality bounds for imitation learning in MDPs, showing improvements with knowledge of transition.
New bounds on adaptivity cost in stochastic optimization.
problem Understanding the cost of changing strategies in stochastic optimization.
method Proving impossibility results for adaptivity in non-smooth stochastic convex optimization.
result Lower bounds on the price of adaptivity for different levels of uncertainty.
Proposes a new algorithm to improve Frank-Wolfe method efficiency.
problem Improves Frank-Wolfe method's stability and efficiency.
method Introduces 1-SFW, a one-sample stochastic Frank-Wolfe algorithm.
result Achieves optimal convergence rate and first-order stationary point.
An Algorithmic Framework for Computing Validation Performance Bounds by Using Suboptimal Modelsstat.ML
Practical model building processes are often time-consuming because many different models must be trained and validated. In this paper, we introduce a novel algorithm that can be used for computing the lower and the upper bounds of model validation errors without actually training the model itself. A key idea behind ou…
Enhances reinforcement learning from sparse data.
problem Limited data for offline reinforcement learning.
method Trajectory-based data augmentation.
result Improves reinforcement learning performance.
New algorithm reduces suboptimality in imitation learning to nearly optimal levels.
problem Statistical limits of imitation learning in MDPs with known transitions.
method Mimic-MD algorithm and reduction to value estimation problem.
result Upper bound of for suboptimality, with efficient computation.
Wide deep neural networks are easy to optimize without constraints.
problem Optimizing wide deep neural networks.
method Analysis of optimization landscapes and empirical-risk minimization.
result Wide neural networks have no confined points, making optimization easier.
New -step policy gradient method avoids local optima in restricted policy classes.
problem Suboptimal local optima in policy gradient methods for restricted policy classes.
method Proposes a -step policy gradient method to escape myopic local optima.
result The method converges to near optimal solutions exponentially close to the optimal deterministic policy.
A new forecasting framework uses suboptimal embeddings to improve multivariate time series prediction.
problem Randomly selecting embeddings or brute force methods often lead to suboptimal forecasts.
method Develops a framework that uses various suboptimal embeddings obtained via combinatorial optimization.
result Achieves the best results among existing frameworks for various datasets.
Least Squares Estimators are suboptimal for 5D convex functions.
problem Suboptimality of Least Squares Estimators in estimating multidimensional convex functions.
method Analysis of natural subclasses of convex functions in random and fixed design settings.
result Risk of LSE is while minimax risk is for .
New study shows exponential lower bound for RL even with constant suboptimality gap.
problem Can RL be sample-efficient with a constant suboptimality gap?
method Analyzes reinforcement learning in the online setting with a linearly realizable optimal Q-function.
result An exponential sample complexity lower bound still holds even with a constant suboptimality gap.
Paper introduces WWAggr for ensemble CPD, improving accuracy and decision threshold selection.
problem Challenges in detecting abrupt distribution shifts in high-dimensional data streams.
method Introduces WWAggr, a novel task-specific ensemble aggregation method based on Wasserstein distance.
result Demonstrates WWAggr outperforms standard aggregation techniques and decision threshold selection.
Training a source model optimally for its own task is suboptimal for downstream transfer.
problem The optimality of a source model for its own task hinders downstream transfer performance.
method Analyzes L2-SP ridge regression, characterizes transfer-optimal source penalty, and identifies alignment-dependent effects.
result Transfer benefits from stronger source regularization when aligned imperfectly, and from weaker regularization when aligned perfectly.
AC-Teach: A Bayesian Actor-Critic Method for Policy Learning with an Ensemble of Suboptimal Teacherscs.LG
AC-Teach uses an ensemble of suboptimal teachers to improve exploration in RL.
problem Improving exploration efficiency in long-horizon tasks with sparse rewards.
method Bayesian Actor-Critic with an ensemble of suboptimal teachers.
result AC-Teach improves sample efficiency over baselines on various tasks.
This study analyzes satellite communication latency using a stochastic geometry model.
problem Latency analysis of LEO satellite relay communication systems.
method Stochastic geometry framework with spherical BPP models, suboptimal satellite relay selection strategy.
result Derives distance distributions and analytical expressions for transmission delays.
Probabilistic Riemannian submanifold learning with wrapped Gaussian process latent variable modelsstat.ML
Latent variable models (LVMs) learn probabilistic models of data manifolds lying in an \emph{ambient} Euclidean space. In a number of applications, a priori known spatial constraints can shrink the ambient space into a considerably smaller manifold. Additionally, in these applications the Euclidean geometry might induc…
Monotone adversarial corruptions degrade optimal learning algorithms.
problem Optimal learning algorithms' reliance on exchangeability and independence is challenged.
method Introduces a monotone adversarial corruption model where an adversary adds monotone corruptions to a clean dataset.
result Optimal learning algorithms achieve suboptimal expected error on new test points.
Algorithm optimizes non-convex functions using dueling comparisons.
problem Optimizing non-convex functions with limited function evaluations.
method COMP-GP-UCB algorithm, leveraging dueling-choice bandits.
result Theoretical guarantee of on simple regret.
A new geometrically-motivated algorithm for nonnegative matrix factorization is developed and applied to the discovery of latent "topics" for text and image "document" corpora. The algorithm is based on robustly finding and clustering extreme points of empirical cross-document word-frequencies that correspond to novel …
IDT learns human preferences from uncertain decisions, even when humans are suboptimal.
problem Learning human preferences from uncertain and suboptimal decisions.
method Inverse decision theory (IDT) framework, statistical analysis of IDT, characterizing sample complexity.
result Learning preferences is easier when decisions are more uncertain, even if humans are suboptimal.
Proposes a curriculum learning algorithm to maximize cumulative return in reinforcement learning.
problem Maximizing cumulative return in reinforcement learning tasks.
method Task sequencing algorithm maximizing cumulative return, using curriculum learning to minimize suboptimal actions.
result Significantly better performance on cumulative return maximization compared to metaheuristic algorithms.
Cross-validation pitfalls in change-point regression are addressed with new approaches.
problem Cross-validation's prediction error-based criterion may lead to under- or over-estimation of change-points.
method Proposes two approaches: absolute error loss and modified holdout sets.
result Consistent estimation of the number of change-points under certain conditions.
Guiding reinforcement learning with suboptimal controllers speeds up training.
problem Sparse rewards in reinforcement learning make exploration inefficient.
method Use a suboptimal controller to guide exploration, applying a Q-filter loss conditionally.
result The approach leads to faster policy refinement and better performance.
Efficient algorithms for -means clustering frequently converge to suboptimal partitions, and given a partition, it is difficult to detect -means optimality. In this paper, we develop an a posteriori certifier of approximate optimality for -means clustering. The certifier is a sub-linear Monte Carlo algorithm b…
Negative momentum accelerates convergence in minimax games but at a suboptimal rate.
problem The convergence rate of negative momentum in minimax games is suboptimal.
method Extending variational inequality formulation, connecting momentum method with Chebyshev polynomials.
result Negative momentum accelerates convergence locally but at a suboptimal rate.
Inferring intent from observed behavior has been studied extensively within the frameworks of Bayesian inverse planning and inverse reinforcement learning. These methods infer a goal or reward function that best explains the actions of the observed agent, typically a human demonstrator. Another agent can use this infer…
The paper corrects bias in fluid approximation for better decision-making in stochastic optimization.
problem Bias introduced by using mean values in fluid approximation leads to suboptimal decisions.
method Identifying a decision-corrected point estimate that yields optimal decisions.
result A corrected point estimate exists under certain conditions and can be computed algorithmically.
In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptim…
Policy gradient methods do not optimize the discounted objective, leading to suboptimal results.
problem Understanding the true optimization objective of policy gradient methods.
method Analyzing the update direction of policy gradient methods and proving it is not the gradient of any function.
result Policy gradient methods do not optimize the discounted objective, leading to suboptimal results.
A bilevel optimization method for reweighting data leads to suboptimal results.
problem Reweighting data for better model performance on a different distribution.
method Formalizes data reweighting as a bilevel optimization problem and analyzes the limitations of classical solvers.
result The final data weights are often very sparse, indicating suboptimal solutions.