Lower bounds for geodesically convex optimization show curvature negatively impacts complexity.
problem Understanding the impact of curvature on the query complexity of geodesically convex optimization.
method Building on recent lower bounds, the study proposes and proves new lower bounds for various settings of geodesically convex optimization.
result Negative curvature is detrimental to the complexity of geodesically convex optimization.
New lower bounds for gradient methods in strongly convex finite-sum optimization.
problem Developing tight lower bounds for randomized gradient methods in finite-sum optimization.
method Deriving tight lower complexity bounds for SAG, SAGA, SVRG, SARAH, and related methods.
result Tight matches between lower bounds and upper bounds for various methods under specific conditions.
Lower bound for complexity of finding flex points on cubic curves.
problem Finding flex points on cubic plane curves.
method Bounding the Schwarz genus of a cover associated to the problem.
result Lower bound for topological complexity close to optimal.
Lower bound on stretch factor for periodic maps.
problem Finding a lower bound on stretch factors for periodic maps.
method Using core characteristic of end-periodic homeomorphisms, we derive a lower bound on the Handel-Miller stretch factor.
result The derived bound is sharp and measures topological complexity.
We establish a lower bound on the complexity orientable locally orientable geometric 3-orbifolds in terms of Delzant's T-invariants of their orbifold-fundamental groups, generalizing previously known bounds for complexity of 3-manifolds.
Lower bounds and upper bounds on sample complexity for identifying linear dynamical systems.
problem Identifying an unknown linear dynamical system with limited data.
method Sample complexity lower and upper bounds, persistent excitation condition, active learning algorithm.
result Lower and upper bounds share the same dependency on key problem parameters.
Paper establishes first instance-dependent lower bound for PAC reinforcement learning.
problem Identifying near-optimal policies in tabular MDPs with minimal samples.
method Proposes instance-dependent lower bound for sample complexity.
result Lower bound closely matches PEDEL algorithm's sample complexity.
Lower bounds found for nonconvex-strongly-concave min-max optimization problems.
problem Finding stationary points in nonconvex-strongly-concave min-max optimization.
method Provided lower bounds for first-order oracle complexity.
result Lower bounds of Ω(√κε⁻²) for deterministic oracles and Ω(√κε⁻² + κ¹/₃ε⁻⁴) for stochastic oracles.
Paper tightens lower bounds on decentralized training complexity.
problem Understanding and optimizing iteration complexity in decentralized training.
method Proved a tight lower bound on iteration complexity and proposed DeTAG algorithm.
result DeTAG achieves the theoretical lower bound with only a logarithmic gap.
Improved lower bounds on 2-bridge link complexity.
problem Finding minimal triangulations of 2-bridge link complements.
method Explicit angle structures and volume estimates.
result Explicit lower bounds on link complexity.
Paper establishes lower bounds for finite-sum optimization problems using novel construction methods.
problem Lower complexity bounds for finite-sum optimization problems with various component functions.
method Developed novel approach to construct hard instances and analyzed PIFO algorithms.
result Established lower complexity bounds for convex-concave and nonconvex-strongly-concave objectives.
The paper sets information-theoretic lower bounds for neural networks' parameter recovery and excess risk.
problem Establishing sample complexity lower bounds for neural network parameters and excess risk.
method Using information-theoretic tools, the paper proves lower bounds by constructing a generative network.
result Proves information-theoretic lower bounds for exact parameter recovery and positive excess risk.
New lower bounds for bilevel optimization with first-order oracles.
problem Complexity of bilevel optimization with first-order oracles.
method Development of hard instances and proof of lower bounds.
result Nontrivial lower bounds for first-order zero-respecting algorithms.
New algorithm for multi-fidelity bandits reduces costs and improves regret.
problem Optimizing decisions with varying costs and accuracy in multi-fidelity bandits.
method Cost complexity bounds, algorithmic framework, elimination-based algorithm.
result New regret definition and matching upper and lower bounds for elimination-based algorithm.
Paper establishes new lower bounds for MDPs with changing transition kernels.
problem Minimizing sample complexity and regret in non-stationary MDPs.
method Developed novel lower bounds and constructed hard MDPs.
result Proved Ω((H3SA/ε2)log(1/δ)) sample complexity lower bound. The paper introduces gapped scale-sensitive dimensions to improve learning rate bounds.
problem Improving lower bounds on rates of convergence in statistical and online learning.
method Introducing and analyzing gapped scale-sensitive dimensions for function classes.
result Gapped dimensions lead to stronger lower bounds on offset Rademacher averages.
New SQ lower bounds show learning mixtures of bounded covariance Gaussians is hard.
problem Learning mixtures of Gaussians with bounded covariance matrices is hard.
method Statistical Query (SQ) lower bounds.
result Any SQ algorithm requires complexity at least dΩ(1/ε) for learning mixtures of bounded covariance Gaussians. Unified framework for lower bounds in interactive decision making.
problem Challenges in interactive decision making, especially bandits and reinforcement learning.
method Interactive Fano method and Fractional Covering Number.
result Unified characterization of learnability for stochastic bandit problems and tight lower bounds for interactive decision making.
The study sets limits on the complexity of Klein geometries.
problem Understanding the complexity of Klein geometries.
method Simple upper and lower bounds for the order of Klein geometries.
result Established upper and lower bounds for the order of Klein geometries.
The paper sets lower bounds for sampling non-log-concave distributions using Fisher information.
problem Understanding the complexity of sampling non-log-concave distributions.
method Proves two lower bounds using Fisher information in the context of sampling.
result Lower bounds on the complexity of sampling non-log-concave distributions, ruling out high-accuracy algorithms.
Paper finds at least 6 fixed points for a specific circle action on a 10D manifold.
problem Finding the minimum number of fixed points for a circle action on a 10D almost complex manifold.
method Established a lower bound by showing the non-existence of a circle action with 4 fixed points.
result There are at least 6 fixed points for a circle action on a 10D compact almost complex manifold.
This paper sets a lower bound for sample complexity in inverse reinforcement learning.
problem Finding a reward function that generates a desired optimal policy in MDPs.
method Information-theoretic lower bound using geometric construction and Fano's inequality.
result An O(nlogn) sample complexity lower bound for IRL problems. Uniform bounds for Green's function on Kähler manifolds derived from complex Monge-Ampère equations.
problem Uniform bounds for Green's function on Kähler manifolds.
method Auxiliary Monge-Ampère equations, non-linear proof.
result Uniform lower bounds for the Green's function on Kähler manifolds.
We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from com…
Paper finds a lower bound for estimating low-rank matrices in logistic regression.
problem Estimating low-rank coefficient matrices in logistic regression.
method Derives a minimax lower bound on the risk.
result The bound depends on matrix dimensions, rank, and sample size.
In three-dimensional computational topology, the theory of normal surfaces is a tool of great theoretical and practical significance. Although this theory typically leads to exponential time algorithms, very little is known about how these algorithms perform in "typical" scenarios, or how far the best known theoretical…
Study on scalar curvature bounds and manifold topological complexity.
problem Understanding the topological complexity of manifolds with scalar curvature constraints.
method Introduced a small scale index theorem to establish bounds for Gromov's simplicial norm.
result Upper bound for Gromov's simplicial norm established in terms of scalar curvature, volume, and injectivity radius.
The standard interpretation of importance-weighted autoencoders is that they maximize a tighter lower bound on the marginal likelihood than the standard evidence lower bound. We give an alternate interpretation of this procedure: that it optimizes the standard variational lower bound, but using a more complex distribut…
Study on Kähler manifolds shows rigidity of eigenvalues with positive Ricci bound.
problem Optimal rigidity results for eigenvalues on Kähler manifolds with positive Ricci lower bound.
method Established optimal rigidity results for eigenvalues on Kähler manifolds with positive Ricci lower bound.
result Complex projective space is the only Kähler manifold with the largest multiplicity of the first eigenvalue.
Lower bounds for PL 4-manifolds with boundary are improved.
problem Estimating PL 4-manifolds with boundary.
method Proved inequalities for regular genus and gem-complexity.
result Improved lower bounds for PL 4-manifolds with boundary.
We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on…
Smooth finite-sum optimization has been widely studied in both convex and nonconvex settings. However, existing lower bounds for finite-sum optimization are mostly limited to the setting where each component function is (strongly) convex, while the lower bounds for nonconvex finite-sum optimization remain largely unsol…
Study near-optimal bounds for learning Gaussian halfspaces with random noise.
problem Learning general halfspaces with Gaussian distribution and random classification noise.
method Established nearly-matching algorithmic and SQ lower bounds, developed a computationally efficient learning algorithm.
result Sample complexity of learning algorithm is O(d/ε+d/(max{p,ε})2), SQ lower bound is Ω(d1/2/(max{p,ε})2). Given a sequence of complete(compact or noncompact) Kähler manifolds Min with bisectional curvature lower bound and noncollapsed volume, we prove that the pointed Gromov-Hausdorff limit is homeomorphic to a normal complex analytic space. The complex analytic structure is the natural "limit" of complex structure of …
New SQ lower bound shows complexity nearly matches known upper bound for smoothed agnostic learning.
problem Smoothed agnostic learning of halfspaces under subgaussian distributions.
method Statistical Query (SQ) lower bound using moment-matching hard distribution and linear programming duality.
result First non-trivial lower bound on complexity nearly matches known upper bound.
In this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is monotone if, for any pair of domain elements x and y such that x⪯y, p(x)≤p(y). To understand the sample complexity of this problem, we intro…
The paper studies privacy-protected BAI with fixed confidence, deriving lower bounds and proposing an adaptive algorithm.
problem Privacy-protected Best Arm Identification (BAI) in data-sensitive applications.
method Derives lower bounds on sample complexity, proposes AdaP-TT algorithm with Laplace noise, and validates with experiments.
result AdaP-TT matches the sample complexity lower bound up to constants in the high-privacy regime.
Lower bounds for higher-order methods in non-convex optimization.
problem Proving lower bounds for higher-order methods in smooth non-convex finite-sum optimization.
method Analyzing deterministic and randomized algorithms, proposing a new smoothness assumption.
result Proves optimal lower bounds for simulating pth-order regularized methods on the whole function.
The study analyzes batched methods for early stopping in stochastic multi-armed bandits.
problem Early stopping in stochastic multi-armed bandits with fixed confidence.
method Instance-dependent lower bounds and a general batched algorithm with upper bounds.
result Upper and lower bounds on the number of batches and sample complexity.
In this short note we determine the greatest lower bounds on Ricci curvature for all Fano T-manifolds of complexity one, generalizing the result of Chi Li. Our method of proof is based on the work of Datar and Székelyhidi, using the description of complexity one special configurations given by Ilten and Süß.
We show that the correction terms in Heegaard Floer homology give a lower bound to the the genus of one-sided Heegaard splittings and the Z2--Thurston norm. Using a result of Jaco--Rubinstein--Tillmann, this gives a lower bound to the complexity of certain closed 3--manifolds. As an application, we compute…
The paper extends statistical estimation techniques under differential privacy.
problem Establishing sample complexity bounds for estimation tasks under differential privacy.
method Proposes analogues of Le Cam's method, Fano's inequality, and Assouad's lemma under central differential privacy.
result Optimal sample complexity bounds for discrete distribution estimation under total variation and ℓ2 distances. PCA-Net combines PCA and neural networks for operator approximation, with new bounds on complexity.
problem Developing approximation theory for PCA-Net architecture.
method Combines PCA and neural networks, derives universal approximation results and lower bounds on complexity.
result PCA-Net can overcome the curse of parametric complexity for specific operators.
We suggest a general oracle-based framework that captures different parallel stochastic optimization settings described by a dependency graph, and derive generic lower bounds in terms of this graph. We then use the framework and derive lower bounds for several specific parallel optimization settings, including delayed …
This paper improves the convergence rates of bilevel optimization algorithms.
problem Improving the convergence rates of bilevel optimization algorithms.
method Provided lower complexity bounds and proposed an accelerated bilevel optimizer.
result AccBiO achieves optimal results under certain conditions.
In Kähler-Einstein case of positive scalar curvature and even complex dimension, an improved lower bound for the first eigenvalue of the Dirac operator is given. It is shown by a general construction that there are manifolds for which this new lower bound itself is the first eigenvalue.
Lower bounds for PI on multi-action MDPs are established, showing complexity grows with action count.
problem Establishing the minimum number of iterations for PI to converge on MDPs with multiple actions.
method Developed lower bounds for a specific PI variant on multi-action MDPs, scaling with action count.
result A particular PI variant can take Ω(kn/2) iterations to terminate, scaling with action count. Study energy-minimizing maps in projective spaces, proving sharp bounds.
problem Finding optimal mappings in projective spaces.
method Proving lower bounds and characterizing energy-minimizing maps.
result Sharp lower bounds and characterization of energy-minimizing maps.